Given that your network architecture is implemented correctly, and as long as they are increasing just slowly, it sounds like a learning rate problem. Probably you are using SGD with a fixed learning rate. You should try to change the optimization method to SGD with Adagrad or Adadelta etc, that are more robust to such problems. More specifically, they are very easy to implement, you can check for more implementation details on Adagrad here: http://xcorr.net/2014/01/23/adagrad-eliminating-learning-rates-in-stochastic-gradient-descent/. If you are using Torch7 (which is my preference), they are both implemented under the optim package. If your are using theano there are several implementations, among others: http://deeplearning.net/tutorial/code/lstm.py. Finally, you can experiment changing the mini-batch size.