Training Error decreasing with each epoch I am trying to train a VGG-19 neural network on STL-10 dataset containing 5000 images(500 for each class). And the number of output classes is 10.

I have made no changes to the architecture except that I reduced the size of fully-connected layer from 4096 to 2048, keeping the dropout(0.5) same 

[The reason behind doing this is that, since the number of training images is less, so to avoid over-fitting, I decreased the size of fully-connected layer, but I don't know if this is the right thing to do].

I have also used Adam optimiser(learning rate = 0.001) instead of SGD as mentioned in the paper.

I have only run the code for only 4 epochs. And I have observed that although the cost is decreasing by very small amount, but the training accuracy is decreasing.

After the 1st epoch, cost:: 2.304091 and training accuracy:: 11.99%

After the 2nd epoch, cost:: 2.303365 and training accuracy:: 11.249%

After the 3rd epoch, cost:: 2.301936 and training accuracy:: 10.5625%

After the 4th epoch, cost:: 2.30415 and training accuracy:: 8.1249%

I want to know, that is this behavior natural or is it due to some fault in the changes I made in the architecture?
Or using less number of layers would have been better? (For example VGG-16)

(This is my first hands-on neural network experience)
I am not very sure about your case, usually I have seen the same problem but in the other direction, you can take a look here:

Quora loss drecrease, accuaracy constant
Cross validated loss drecrease, accuaracy constant

I would guess that your DNN is getting more answers right but without impoving its confidence  a lot.
Regarding your other questions, I would advise you to start with simplest possible model, for example, in this case it would be using the vgg16 (which is widely more used than the vgg19) and the default parameters ( number of neurons, optimization function...) Once you have something working you can start tuning and modifying things.