Quasi Black Hole Effect of Gradient Descent in Large Dimension: Consequence on Neural Network Learning

摘要

The gradient descent to a local minimum is the key ingredient of deep neural networks learning techniques. We consider a function L_m(.) in dimension n with a random set of m absolute minima. When log m = o(n), we show that a gradient descent from an initial random point quasi always ends on a unique local minimum approximately at the centroid of the absolute minima. This fake minimum acts like an absorbing node, but its value by function L_m(.) can be far above the values obtained by L_m(.) on the absolute minima and sometimes gives very bad coefficients for the neural network. Fortunately in most cases the fake minimum leads to a neural network with not so bad prediction, with an error rate of order n^-1/4. The only way to escape the fake minimum is to start a new gradient descent from a new random point and we show that finding a good initial point takes in average time which is at least proportional to e^bn/mn² for some b > 0.