PaperlayerView exact revision on arXiv

Source-linked AI summary

An Alternative View: When Does SGD Escape Local Minima?

Robert Kleinberg, Yuanzhi Li, Yang Yuan

arXiv:1802.06175v2cs.LG

TL;DR

The paper asks why SGD can converge to better local minima than GD in non-convex neural-network training, where the role of noise and step size remains incompletely explained. It views SGD as optimization of noise-smoothed loss functions and proves that one-point convexity of those functions lets SGD approach and remain near a target with constant probability. Experiments find locally favorable one-point-convex properties along neural-network SGD trajectories, while the target need not be globally optimal and a deep-network proof remains open.

  • Problem

    Why SGD can converge to better local minima than GD remains unclear, especially because existing non-convex analyses mainly study small step sizes despite large steps helping escape minima.

  • Method

    The paper analyzes SGD through auxiliary iterates and models it as approximate gradient descent on the loss convolved with the step-size-scaled gradient-noise distribution.

  • Results

    Under one-point convexity of the convolved loss toward x*, the theorem says SGD can escape other local minima, approach x*, and stay nearby with constant probability.

  • Takeaways & Limitations

    The framework provides a broader-than-convex class of functions where SGD provably works and helps explain its tendency to avoid sharp minima in favor of flat ones.

  • Takeaways & Limitations

    The target x* need not be globally optimal for the original loss, and proving local one-point convexity for deep neural networks remains open.

Abstract

from arXiv · show

Stochastic gradient descent (SGD) is widely used in machine learning. Although being commonly viewed as a fast but not accurate version of gradient descent (GD), it always finds better solutions than GD for modern neural networks. In order to understand this phenomenon, we take an alternative view that SGD is working on the convolved (thus smoothed) version of the loss function. We show that, even if the function $f$ has many bad local minima or saddle points, as long as for every point $x$, the weighted average of the gradients of its neighborhoods is one point convex with respect to the desired solution $x^*$, SGD will get close to, and then stay around $x^*$ with constant probability. More specifically, SGD will not get stuck at "sharp" local minima with small diameters, as long as the neighborhoods of these regions contain enough gradient information. The neighborhood size is controlled by step size and gradient noise. Our result identifies a set of functions that SGD provably works, which is much larger than the set of convex functions. Empirically, we observe that the loss surface of neural networks enjoys nice one point convexity properties locally, therefore our theorem helps explain why SGD works so well for neural networks.

1 Introduction

The paper reframes SGD as approximate gradient descent on loss functions smoothed by gradient noise, addressing why SGD can outperform GD on non-convex neural-network objectives. Under one-point convexity of the smoothed functions, SGD can escape sharp minima, approach a target, and remain nearby with constant probability.

  • Motivation: SGD’s noise and step size are studied to explain why it can reach better local minima than GD, beyond existing small-step non-convex analyses.Prior work links noise to escaping saddle points and improving generalization, while empirical schedules use large steps for escape and smaller steps for refinement.
  • Alternative view: The analysis introduces auxiliary iterates yt = xt − η∇f(xt), showing that SGD’s update can be examined through the sequence yt → yt+1.These auxiliary vectors are not computed by SGD; they provide an analysis tool for decomposing each stochastic step.
  • Alternative view: SGD approximately performs gradient descent on gt(y) = Eωt[f(y − ηωt)], the original loss convolved with the η-scaled gradient-noise distribution.Convolution smooths short-range fluctuations, potentially eliminating sharp local minima while preserving broader regions.
  • Main result: If the convolved functions satisfy one-point strong convexity toward x*, the theorem states that SGD approaches x* and remains close for future steps with probability at least 1/2.The guarantee requires smoothness, bounded noise, a bounded step size, and a sufficiently large initial horizon T1, followed by any T2 additional steps.
  • Implications: The framework explains why SGD can escape sharp minima with small diameters and favor flat minima, while experiments report locally favorable one-point-convex behavior along neural-network SGD trajectories.The target x* need not be the global optimum of the original loss, and proving the local property for deep networks remains open.

2 Motivating Example

The motivating example shows how SGD’s noise smooths a spiky loss, removing many spurious minima while creating a trade-off between insufficient and excessive noise.

  • A spiky approximately convex function can contain many local minima that trap gradient descent, despite a desired solution at x* = 0.
  • SGD instead operates on convolved versions of the loss that are smoother and contain fewer local minima.The convolution-based view treats gradient noise as the smoothing mechanism.
  • Small noise may leave non-convex regions and spurious minima, whereas excessive noise can overwhelm the gradient and produce random-walk behavior.
  • Iteratively restarting within progressively smaller regions and noise levels can bring SGD close to 0 with decent probability.A first restart uses noise level 0.15 inside [−1.5, 1.5].

3 Main Theorem

The main theorem analyzes SGD through smoothed-gradient geometry: under smoothness, bounded noise, suitable step size, and one-point convexity, SGD approaches and remains near x*.

  • 3 Main Theorem: Under these assumptions, SGD converges toward x* and stays around it after convergence.
  • 3 Main Theorem: The theorem assumes an L-smooth function, bounded gradient noise, a fixed target x*, and a step size satisfying explicit upper bounds.
  • 3 Main Theorem: With probability at least 1/2, SGD is within a bounded neighborhood of x* after T steps and remains there for the subsequent T2 steps.
  • 3 Main Theorem: The guarantee requires a positive lower bound on η for fixed c, so the step size cannot be arbitrarily small.
  • 3 Main Theorem: Restarting SGD with a smaller step size inside a favorable local region can improve the convergence guarantee.
  • 3 Main Theorem: If the step size is too large, even one-point-convex gradients may move the iterate farther from x* rather than closer.
  • 3 Main Theorem: The analysis therefore identifies step-size selection as essential, because both excessively large and excessively small values can fail to provide the desired behavior.

4 Proof for Theorem 1

The proof shows that SGD makes expected progress toward x* under the one-point-convexity assumption, reaches a neighborhood of x*, and remains there with constant probability.

  • Proof strategy: The proof proceeds in four steps: expected progress toward x*, concentration near x*, and high-probability preservation of closeness.The analysis models progress with stochastic noise and combines the steps to prove the theorem.
  • Step 2: Reaching the neighborhood: After sufficiently many steps, expected distance to x* becomes small; Markov’s inequality converts this into a high-probability closeness event.The proof relabels the iterate reached after the initial phase as y0 before analyzing its subsequent stability.
  • Steps 3–4: Staying close: Conditioned on remaining close to x*, the proof constructs a supermartingale and applies Azuma’s inequality to control deviations over time.The event E_t records closeness at all earlier times, while G_t tracks the bounded progress quantity.
  • Steps 3–4: Staying close: If E_{t−1} holds, the Azuma bound implies E_t with high probability, and iterating this claim yields E_{T2} with probability 1−T2/ζ.Combining this preservation argument with the earlier inequality gives the theorem with probability at least 1/2.

5 Empirical Observations

Experiments find that neural-network loss surfaces contain one-point-convex regions along SGD trajectories, including neighborhoods and multiple destinations. Learning-rate schedules influence which local minimum is reached, while VGG is an exception.

  • Neural-network loss surfaces contain many one-point-convex basin regions, and SGD traverses such regions despite overall non-convexity.
  • 5.2 The neighborhood of the trajectory is one point convex: The neighborhood around the SGD trajectory remains one-point convex after convolution with a uniform ball of radius 0.5.
  • 5.2 The neighborhood of the trajectory is one point convex: SGD step length is bounded by 0.5 in the reported experiments, based on gradient norms and the learning-rate schedule.Gradient norms were below 5 before epoch 150 at learning rate 0.1 and below 15 afterward at learning rate 0.01.
  • 5.3 Loss surface is locally a “slope”: VGG did not show the same observations as Resnet and Densenet in the reported experiments.
  • 5.3 Loss surface is locally a “slope”: With 50 random-seed trajectories, inner products toward final solutions were almost always positive: only 0.1% were non-positive for Densenet and 2 of 343,000 for Resnet.
  • 5.4 Spectrum of the local minima: Later starting epochs produced local minima farther from initialization with lower validation and training loss.
  • 5.4 Spectrum of the local minima: The learning-rate schedule determines final-minimum quality: large initial steps avoid bad minima, while shrinking the rate enables convergence to a good minimum.

6 Conclusion

The paper views SGD as operating on a convolved loss function. It argues that one-point convexity of this convolved function lets SGD escape other minima, remain near a target, and aligns with observed neural-network trajectories.

  • SGD is analyzed as operating on a convolved version of the loss function rather than directly on the original loss.
  • When the convolved function is one-point convex around x*, SGD can escape other local minima and stay near x* with constant probability.
  • Experiments find nice local one-point-convex properties along SGD trajectories in modern neural networks.The paper notes that proving this property for deep neural networks remains an open question.

A Discussions on one point convexity

One-point strong convexity around x* in a convex domain makes x* the unique local, and therefore global, minimum there.

  • δ-one-point strong convexity around x* in a convex domain implies that x* is the only local minimum in that domain.The paper identifies this point as the global minimum within the domain.
  • Along the segment from any x to x*, the function decreases toward x*, establishing uniqueness of the minimum.

B Proof for Lemma 5

The proof bounds three summands separately and combines those bounds to establish the lemma without optimizing the constants.

  • The proof bounds each of the three summands on the left-hand side by μ^2b.
  • The authors state that they did not optimize the constants in this proof.
  • Adding the three bounds yields the claimed result.

C Proof for Theorem 3

The proof starts from the gradient-descent update and invokes an inner-product condition involving the desired solution x* and the current iterate x_t.

  • The proof recalls the update x_{t+1} = x_t − η∇f(x_t).
  • It uses the condition ⟨−∇f(x_t), x*−x_t⟩ ≤ c′∥x*−x_t∥^2.
  • The proof relates the negative gradient direction to the displacement from the current iterate x_t toward x*.
Loading 1802.06175v2…