High training error at the beginning of training a Convolutional neural network

In the Convolutional neural network, I'm working on training a CNN, and during the training process, especially at the beginning of my training I get extremely high training error. After that, this error starts to go down slowly. After approximately 500 Epochs the training error comes near to zero (e.g. 0.006604). Then, I took the final obtained model to measure its accuracy against the testing data, I've got about 89.50%. Does that seem normal? I mean getting a high training error rate at the very beginning of my training process. Another thing I'd like to mention is that I've noticed that every time I reduce the number of hidden nodes, the results become better at the end of my training.

My CNN structure is:

     config.forward_pass_scheme = {'conv_v', 'pool', 'conv_v', 'pool', 'conv_v', 'pool', 'conv_v','full', 'full', 'full', 'out'};

Here are some of my hyper parameters:

      config.learning_rate = 0.01;
      config.weight_range = 2;
      config.decay = 0.0005;
      config.normalize_init_weights = 1;
      config.dropout_full_layer = 1;
      config.optimization = 'adagrad';

Your help and suggestion in this regard is highly appreciated, thank you in advance.