Question: When I train a neural network, I observe an increasing validation loss, while at the same time, the validation accuracy is also increased.

I have read explanations related to the phenomenon, and it seems an increasing validation loss and validation accuracy signifies an overfitted model.

However, I have not really grokked the reasons why an increasing validation loss and validation accuracy signifies an overfitting.

Could you please give the explanations behind this phenomenon?

Answer: 
Let $F : \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a continuous differentiable function and $d \in \mathbb{R}^{n}$. Then $d$ is called a descent direction at position $p \in \mathbb{R}^{n}$, if there is a $R > 0 $ such that $F(p+rd) < F(p)$ for all $r \in (0,R)$.

In simple terms: If we move $p$ in direction of $d$ we can reduce the value of $F$.

Now $d$ is a descent direction at $p$, if $\nabla F(p)^T rd < 0 $ since by definition of gradient $F(p+rd) - F(p) = \nabla F(p)^Trd$ and in order to reduce the function value, we need to have $\nabla F(p)^T rd < 0 $:

For $f(r):= F(p+rd)$ we have $f'(t) = \nabla F(p+rd)^T d$. By assumption, $f'(0) < 0$ holds.

Since $f'(0) = \lim\_{h \rightarrow 0} \frac{f(h)-f(0)}{h}$, we conclude that $d$ must be descent direction.

Therefore, setting $d := -\nabla F(p)$, we have $\nabla F(p)^T (-\nabla F(p)) = - ||\nabla F(p)||\_{2}^{2} < 0 $, if $p$ is not a stationary point.

In particular, we can choose an $p' = p + r'd$ with $F(p') < F(p)$.
This shows that using the negative gradient makes sense.
Computing the gradient gives you the direction where the function increases the most. Consider f: x -> x^2 , the gradient in x=1 is 2, if you want to minimize the function you need to go in the direction of -2, same with x=-1 as the gradient is -2.

And as gradients are usually vectors, I don't know what a positive or negative gradient would be if gradient is something like (-1, 1).

<https://builtin.com/data-science/gradient-descent>