Can it be over fitting when validation loss and validation accuracy is both increasing? Training a simple neural network over a very sparse matrix (Has 2400 features and 18000 train rows) for a binary classification problem. At the end of 1st epoch validation loss started to increase, whereas validation accuracy is also increasing. Can i call this over fitting? I'm thinking of stopping the training after 6th epoch. My criteria would be: stop if the accuracy is decreasing. Is there something really wrong going on? 
ps: I have perfectly balanced binary classification dataset and a random classifier would result around %50 accuracy.

 A: Yes, absolutely. First of all, overfitting is best judged by looking at loss, rather than accuracy, for a series of reasons including the fact that accuracy is not a good way to estimate the performance of classification models. See here:
https://stats.stackexchange.com/a/312787/58675
Why is accuracy not the best measure for assessing classification models?
Classification probability threshold
Secondly, even if you use accuracy, rather than loss, to judge overfitting (and you shouldn't), you can't just look at the (smoothed) derivative of accuracy on the test curve, i.e., if it's increasing on average or not. You should first of all look at the gap  between training accuracy and test accuracy. And in your case this gap is very large: you'd better use a scale which starts either at 0, or at the accuracy of the random classifier (i.e., the classifiers which assigns each instance to the majority class), but even with your scale, we're talking a training accuracy of nearly 100%, vs. a test accuracy which doesn't even get to 65%.
TL;DR: you don't want to hear it, but your model is as overfit as they get.
PS: you're focusing on the wrong problem. The issue here is not whether to do early stopping at the 1th epoch for a test accuracy of 55%, or whether to stop at epoch 7 for an accuracy of 65%. The real issue here is that your training accuracy (but again, I would focus on the test loss) is way too high with respect to your test accuracy. 55%, 65% or even 75% are all crap with respect to 99%. This is a textbook case of overfitting. You need to do something about it, not focus on the "less worse" epoch for early stopping. 
A: There is at least two possible cause to this curve variation in this case that can happen. The reasonable possible distinctions that we can assume by looking at this graphical dataset, is as follow :
1- This training network indicate validation loss because the model is overfitting.
This answer here could be is a personal review by myself while studying this subject, and having hard time to come over the conclusion. There is many answer here, but the ideal choice would be the number 1 answer that i have mentioned.
2- Other possible cause would be that this training network have unknown variante or error in the trained dataset, like a spontaneous reaction for example.
Feel free to comment.  
