Neural Network accuracy and loss guarantees?

Question

This question is part of a sample exam that I'm working on to prepare for the real one. I've been stuck on this one for quite a while and can't really motivate my answers since it keeps referring to guarantees, can someone explain what guarantees we can have in a neural network such as the one described?

Network description:

Assume a deep neural network (DNN) that takes as input images images of handwritten digits (e.g., MNIST). The input network consists of 28x28 = 784 input units, a hidden layer of logistic units, and a softmax group of 10 units as the output layer. The loss function is the cross-entropy. We have many training cases and we always compute our weight update based on the entire training set, using the error backpropagation algorithm. We use a learning rate thats small enough for all practical purposes, but not so small that the network doesnt learn. We stop when the weight update becomes zero. For each of the following questions, answer yes or no, and explain very briefly.

Questions:

1. Will this DNN configuration enable the the weights to minimize the loss value (there may be multiple global optima)?

2. Does this DNN configuration guarantee that the loss reduces on every step? We use our network to classify images by simply seeing which of the 10 output units gets the largest probability when the network is presented with the image, and declaring the number of that output unit to be the networks guessed label.

3. Does this DNN configuration guarantee that the number of mistakes that the network makes on training data (by following this classification strategy) never increases?

Answer 1

For my answers, I assume you are talking about batch (not mini-batch or stochastic) gradient descent.

1. No. Assume you initialize all weights with the same value. Then all gradients (in the same layer) will be the same. Always. Hence the network effectively only learns one parameter per layer. It is possible (and likely) that this is neither a gloabl nor a local minimum of the network (which has more parameters).
2. Yes, as the learning rate is "small enough for all practical purposes". (No, if you use SGD or mini-batch gradient descent)
3. Usure. I think the correct answer is "No, the network can make more mistakes in between with cross entropy.". It is certainly sure to improve CE loss while at the same time getting worse at accuracy (see proof below). However, I'm not sure if the gradient would ever lead to such a result.

Example for 3

#!/usr/bin/env python

from math import log

def ce(vec):
    """index 0 is the true class."""
    return -(log(vec[0]) + sum([log(1-el) for el in vec[1:]]))

a = [0.1001, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.0999]
print(ce(a))
b = [0.49, 0.51, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
print(ce(b))

gives:

ce(a) = 3.24971912864
ce(b) = 1.42669977575

Hence the cross entropy loss dropped (as expected), the probability for the correct class increased (as expecte) but it makes a mistake (if you simply take the argmax).

Answer 2

A guarantee is a proof that some algorithm will always have a certain performance (or the performance will never be worse than the guarantee). In general there are not a whole lot of theoretical guarantees for NNs. But this question is sufficiently limited in scope that some guarantees hold.

1. This question is maybe a little ambiguous, but I would lean towards answering "no". The question is asking whether the training will lead to a minimum, but they don't specify whether the minimum needs to be a global or a local minimum. If you simply descend down the gradient of the loss function (as we are doing here), you are extremely likely to end up at a local minimum, though unlikely to end up at a global minimum. However, in practice local minima are not much worse than global minima. I say that this is extremely likely to happen because there is a very small chance that you could accidentally land right on a saddle point. This would be a point with a vanishing gradient that is not a local minimum, and training would stop when you land there. (Or, even more unlikely, you could be very unlucky and start on a local maximum!) If they're looking for guarantees, you can't guarantee that that won't happen. But if the DNN is fairly large and the weight initialization is random, you can guarantee that it almost surely won't happen, so there is an argument to be made in favor of "yes".

2. Yes. Since we are descending the gradient of the loss function, the loss function can never increase on any step. (This is assuming the loss function is reasonably smooth.)

EDIT: After some discussion in another answer I have decided that my original answer was incorrect. My updated answer is below:

3. No. Although training will decrease the overall cross-entropy of the entire training set, it is possible that the cross-entropy on a single case will increase. It is therefore possible to construct a training set such that the classifications remain the same from one step to the next for all cases except this one particular example, which moves from a correct classification to an incorrect classification. The overall cross-entropy on the training set will decrease, but the accuracy will increase.