1
$\begingroup$

In Deep Learning by Goodfellow et al., I came across the following line on the chapter on Stochastic Gradient Descent (pg. 287):

The main question is how to set $\epsilon_0$. If it is too large, the learning curve will show violent oscillations, with the cost function often increasing significantly.

I'm slightly confused why the loss function would increase at all. My understanding of gradient descent is that given parameters $\theta$ and a loss function $\ell (\vec{\theta})$, the gradient update is performed as follows:

$$\vec{\theta}_{t+1} = \vec{\theta}_{t} - \epsilon \nabla_{\vec{\theta}}\ell (\vec{\theta})$$

The loss function is guaranteed to monotonically decrease because the parameters are updated in the negative direction of the gradient. I would assume the same holds for SGD, but clearly it doesn't. With a high learning rate $\epsilon$, how would the loss function increase in its value? Is my interpretation incorrect or does SGD have different theoretical guarantees than vanilla gradient descent?

$\endgroup$
2
$\begingroup$

The learning rate used in SGD and in most convergence strategies used in artificial network designs is much like the use of voltage dividers in electronic feedback. The differential equations for control theory, developed by Norbert Wiener and others, demonstrated that insufficiently attenuated negative feedback will cause a circuit to destabilize.

Back-propagation with gradient descent is conceptually similar. The main difference is that artificial networks use discrete examples or batches of examples rather than continuous signals. Back-propagation is a strategy to distribute negative feedback throughout the layers of an artificial network using the chain rule, but that is also common in electronic control circuitry.

It is hypothesized, and the evidence is accumulating in support, that more sophisticated strategies to achieve stability using feedback exist in the neural networks of the brain and in the gut of animals. That is likely, and part of the reason arrays of activation functions are called artificially neural.

Those that have studied the mathematics field of chaos understand that discrete systems can fall into oscillation with insufficiently attenuated negative feedback too. In a worse case, a chaotic pattern will emerge at what is called a bifurcation point. Those that work with convergence in machine learning are always working against factors that lead to divergence. However, too much attenuation, which corresponds to too low a learning rate will be highly stable and extremely costly in terms of computing resources, time to converge, or both.

All of this was established in theory in the late nineteenth and early twentieth century. Goodfellow is explaining it to university level students in the context of deep learning, but it is not specific to SGD. In fact SGD is less likely to diverge or go into chaotic states than what the question is calling vanilla gradient descent.

From a mathematicians stoic point of view, calling chaos violent is anthropomorphic, placing human qualities on non-human things. They might point out that some forms of chaos are more stable than constants. There are many forms of mental, metabolic, molecular, and biospheric stasis that have what chaoticians call attractors, and never converge yet maintain a statistical adjacency to their attractor in phase space. For example, using the above list, emotion, glucose, electron shells, and populations show this type of non-constant stability.

That does not help the person using a multilayer-perceptron or convolution kernel hoping to get some ideal set of parameters during training to deploy into a working system in the field. What is desired is reliable, relatively fast, and accurate convergence results.

What practitioners try to avoid is a cost function that diverges. Keep in mind that cost, error, and loss functions are terms used in various contexts in various articles but all represent disparity from some ideal. The function is the mathematical model for that ideal or optimum, not to be confused with the use of the term model in other aspects of AI. Models are used in many places. In SGD, increases in the cost function are indications of instability and reduced likelihood that convergence will occur.

This is the interesting part. Since the cost function represents a surface and the curvature of the surface has curvature (otherwise it could be solved with linear algebra technique without a network) it may not be monotonic. In other words, one cannot determine the mismatch of output values and corresponding labels from the result of the function. The information flow is constrained to be unidirectional.

This means that the existence of local minima can interfere with the search for the global minimum. Mounds, ridges, saddle points, mazes of troughs, and circular ridges may separate the current state of network parameters from those that represent the optimal state sought.

Therein lies the caveat. The cost surface has curvature.

Local minima interfering with search for global minimum

The statement in the question, because of this, is not generally true.

The loss function is guaranteed to monotonically decrease because the parameters are updated in the negative direction of the gradient.

It is true only in specific cases identified by the theory. In the general case, the cost is not guaranteed to decrease and the algorithm is not guaranteed to converge unless a number of constraints are maintained, few of which normally are.

If not sufficiently attenuated, the next estimation to radically overshoot or undershoot the global minimum. To see how this works, look into chaos simulations using the logistic function. As the next estimate amplification increases, the system first goes into oscillation and then into modes of chaos. In the case of artificial networks, the values in the algorithm used can also exceed the range of IEEE floats and throw an exception.

If one studies the theoretical guarantees in the literature and some of the overview theory such as the PAC (probably approximately correct) Learning Framework, and then try to find a business, marketing, defense, industrial, robotic, or financial application for AI that meets all the constraints required to benefit from the theoretical guarantees, the challenge will become clear. A few easy problems exist. Most require expertise, further investigation, proofs of concept, architecture and design skills, and significant development effort to produce satisfactory results.

Once the results are published with the appropriate references to theoretical foundations and the various design choices presented with hindsight, it looks much easier than it was.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.