PaperlayerView exact revision on arXiv

Source-linked AI summary

A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Yuchen Zhang, Percy Liang, Moses Charikar

arXiv:1702.05575v3cs.LGmath.OCstat.ML

TL;DR

The paper asks how SGLD can optimize non-convex objectives despite poor local minima and potentially exponential mixing times. It analyzes hitting times to arbitrary target sets using a restricted-Cheeger-constant framework, proving polynomial-time population-risk guarantees under empirical-population closeness and stronger learnability for noisy linear classification.

  • Problem

    Non-convex empirical risks can contain poor local minima absent from a uniformly close population risk, while existing noise and mixing-time analyses do not guarantee polynomial-time escape or optimization.

  • Method

    The paper bounds SGLD’s hitting time to arbitrary sets using the restricted Cheeger constant and develops vector-field techniques to lower bound it.

  • Results

    SGLD reaches an approximate local minimum of the population risk in polynomial time under pointwise empirical-population closeness and handles Massart noise below 0.5 for linear classification.

  • Takeaways & Limitations

    SGLD can avoid shallow empirical-risk minima and provide polynomial-time guarantees for selected optimality sets without requiring polynomial mixing time.

  • Takeaways & Limitations

    The current analysis does not apply to over-specified models when empirical risk can fall far below population risk, and it does not resolve poor population local minima.

Abstract

from arXiv · show

We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm's hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is point-wise close to the (smooth) population risk, then the algorithm achieves an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD improves on one of the best known learnability results for learning linear classifiers under the zero-one loss.

1 Introduction

The paper develops a hitting-time analysis of SGLD for non-convex optimization, targeting arbitrary sets rather than mixing times. This framework addresses shallow empirical-risk minima and supports polynomial-time guarantees for population-risk optimization and noisy linear classification.

  • Motivation: Non-convex optimization must address sub-optimal local minima that gradient descent cannot escape, including poor minima in empirical risks uniformly close to population risks.Figure 1 illustrates that empirical risk can contain local minima absent from the population risk.
  • Motivation: Gradient-noise methods can escape strict saddle points, but they do not guarantee escape from shallow local minima.The paper contrasts bounded gradient noise with Langevin noise, whose scale can dominate the gradient for sufficiently small stepsizes.
  • Contributions: The analysis bounds SGLD’s hitting time to an arbitrary set, obtaining polynomial rates for appropriately chosen targets even when mixing time may be exponential.This differs from prior analyses centered on convergence to a stationary distribution or global minima.
  • Contributions: SGLD reaches an approximate local minimum of a smooth population risk in polynomial time when the empirical risk is pointwise close to it, excluding empirical-only minima.The stability result applies when the function perturbation is O(1/ξ) in ℓ∞-norm.
  • Contributions: For linear classifiers under zero-one loss, SGLD handles Massart noise up to any constant below 0.5, improving over a prior bound of at most 1.8 × 10^-6.The application concerns non-convex and non-smooth empirical risk minimization.
  • Techniques: The restricted Cheeger constant connects objective geometry and SGLD hitting time, with the hitting-time bound polynomial in its inverse.It is defined through surface-area-to-volume ratios under a measure proportional to e^(-f(x)).

2 Algorithm and main results

The paper analyzes SGLD through hitting times to target sets rather than mixing times, using the restricted Cheeger constant to obtain polynomial-time guarantees for non-convex optimization. These guarantees extend to approximate local minima and remain stable under uniformly small objective perturbations.

  • Algorithm: SGLD performs stochastic gradient descent with Gaussian noise, constrains iterates to the parameter space, and returns the best iterate across kmax steps.The stochastic gradient is unbiased, and the analyzed variant selects the iterate with minimum objective value rather than returning the last iterate.
  • Restricted Cheeger constant: The restricted Cheeger constant measures boundary-to-volume connectivity under µf(x) proportional to e^-f(x), linking geometry to the probability of escaping subsets.The hitting time is polynomial in the inverse restricted Cheeger constant.
  • Stability and ERM: The restricted Cheeger constant is stable under uniform perturbations, enabling analysis through a nearby function and supporting ERM guarantees for population risks close to empirical risks.For ERM, SGLD can reach an approximate local minimum of the smooth population risk in polynomial time, excluding minima existing only in the empirical risk.
  • Generic hitting-time bound: Theorem 1 bounds hitting time to any target set U under assumptions on the parameter space, smooth objective, and stochastic-gradient tails, with kmax polynomial in the stated hyperparameters.The guarantee holds with probability at least 1 −δ for sufficiently small stepsize η and a specified choice of D.
  • Generic hitting-time bound: Unlike mixing-time analyses that can be exponentially slow for non-convex functions, the hitting-time framework can achieve polynomial rates for appropriately chosen target sets.The iteration bound is governed by the restricted Cheeger constant, and the analysis uses a time-reversible Markov chain and restricted conductance.
  • Approximate local minima: Combining the generic theorem with a restricted-Cheeger lower bound yields polynomial-time finding of an approximate local minimum for sufficiently smooth objectives.The result also gives analogous bounds for global minima of convex functions and approximate stationary points of smooth functions.

3 Applications to empirical risk minimization

The paper applies SGLD to empirical risk minimization by smoothing potentially non-smooth empirical risks and exploiting closeness to a smooth population risk. Under stated assumptions, this yields polynomial-time guarantees for reaching approximate population-risk local minima.

  • Guarantee: Under the theorem’s conditions, SGLD reaches an approximate local minimum of the population risk in polynomial time, despite optimizing a non-smooth empirical risk.The result follows by combining the generic hitting-time theorem with lower bounds on the population-risk restricted Cheeger constant.
  • Assumptions: The analysis assumes a suitable parameter space, a Lipschitz and smooth population risk, pointwise closeness between empirical and population risks, and uniformly bounded loss.The assumptions also allow the empirical risk itself to be non-smooth or discontinuous.
  • Smoothing the empirical risk: SGLD runs on a smoothed approximation of the empirical risk, enabling stochastic-gradient optimization when the original loss is non-differentiable or has unbounded gradients.Gaussian smoothing produces a computable stochastic gradient and is specifically useful for zero-one loss and other non-smooth objectives.
  • Stability transfer: The smoothed empirical risk remains close enough to the population risk that the restricted Cheeger constant and hitting-time guarantees transfer between them.For sufficiently small smoothing, the approximation error is bounded, and the stability property controls the resulting change in the Cheeger constant.
  • Guarantee: The resulting iteration complexity is polynomial in the problem parameters, dimension, approximation and confidence terms, and relevant smoothness or geometric quantities.The bound includes polynomial dependence on B, log(1/δ), d, and h^-1, with additional stated parameter dependencies.

4 Learning linear classifiers with zero-one loss

The paper studies learning linear classifiers under zero-one loss, where empirical-risk optimization is non-convex, discontinuous, and has zero gradients almost everywhere. Under a Massart-noise model, smoothed SGLD achieves approximate population-risk optimization with polynomial complexity.

  • Problem: The model assumes uniformly spherical features, an unknown unit target vector, and Massart-corrupted labels with noise below one-half away from the decision boundary.The feature-label setting and noise conditions define the learning problem analyzed in the theorem.
  • Problem: Zero-one-loss empirical risk is non-convex and discontinuous, with zero gradients almost everywhere, so ordinary gradient descent cannot optimize it.The paper therefore applies SGLD to a smoothed version of the objective.
  • Noise model: The noise model permits arbitrary Massart noise through an arbitrarily small q0 and allows completely random observations at the decision boundary.This is broader than the stronger noise constraint used by Awasthi et al.
  • Method: SGLD optimizes a smoothed empirical-risk function in a compact parameter space and uses uniform convergence plus a restricted-Cheeger lower bound in the proof.The proof combines population-risk regularity and empirical-risk convergence with geometric escape analysis.
  • Result: The algorithm returns a solution satisfying F(bx) ≤ F(x∗) + ϵ with probability at least 1 −δ, using time polynomial in d, 1/q0, 1/ϵ, and log(1/δ).The theorem also requires a sample size condition depending on q0, ϵ, δ, and dimension.

5 Conclusion

The paper analyzes SGLD through hitting times rather than mixing times, obtaining polynomial-time guarantees for selected optimality sets even when mixing may be exponential. It also identifies important limitations and open directions.

  • Conclusion: The analysis establishes polynomial-time guarantees for reaching certain optimality sets regardless of an exponential mixing time.This contrasts with analyses that connect Langevin algorithms to diffusion mixing behavior.
  • Limitations and future work: The current analysis does not apply to over-specified models because their empirical risk can fall far below the population risk, violating Corollary 2’s assumption.The paper suggests studying whether over-specification might improve the restricted Cheeger constant.
  • Limitations and future work: Avoiding poor local minima of the population risk remains open, and the paper proposes investigating whether careful initialization can prevent SGLD from reaching them.This limitation is distinct from escaping local minima that exist only in the empirical risk.

A Restricted Cheeger constant is strictly positive

The appendix proves positivity of the restricted Cheeger constant on finite-diameter convex parameter spaces under a measurable-set condition. The proof combines isoperimetry, measure comparisons, and the definition of restricted conductance.

  • Proof strategy: The proof starts from an isoperimetric inequality for convex spaces and applies it to the function-induced measure associated with the zero function.The resulting measure comparisons control boundary growth relative to volume.
  • Proof strategy: Restricting A to V allows the complement term to be bounded using the neighborhood Vϵ, which yields a lower bound in the restricted-Cheeger definition.The argument proceeds through inequalities involving Aϵ and Vϵ.
  • Extension: For bounded f, the stability property transfers the positivity result from the zero function to the function-induced measure for f.This extends the conclusion beyond the constant-zero objective.
  • Proposition: For a convex parameter space with finite diameter and a measurable V whose small neighborhoods do not fill K, the restricted Cheeger constant is strictly positive.The proposition applies to any bounded function f: K → R.
  • Connection to hitting time: The broader hitting-time analysis constructs a reversible Metropolis-Hastings chain and relates SGLD hitting time to restricted conductance.A closeness lemma supplies a conductance-based bound for the approximating chain.

B.2 Proof of the theorem

The proof bounds SGLD’s hitting time by comparing reversible Markov chains and controlling their conductance under sufficiently small stepsizes. It then extends the standard-setting result to non-standard noise scaling.

  • Standard setting: Theorem 4 bounds the hitting time to an arbitrary neighborhood Uρ with probability at least 1−δ under a sufficiently small stepsize.The bound depends on the restricted Cheeger constant C=C_f(K\U) and problem parameters.
  • Non-standard setting: In the non-standard setting, replacing (η,f) by (η/ξ,ξf) preserves the iteration and risk bounds while adding polynomial dependence on ξ to the iteration numerator.The substitution also changes (B,L,G,η0,bmax) to (ξB,ξL,ξG,η0/ξ,bmax/ξ).
  • Standard setting: The chain πf is time-reversible with stationary distribution µf(x) proportional to e^−f(x).Its transition kernel is implemented through a Metropolis-Hastings construction.
  • Standard setting: The auxiliary chain eπf differs from πf by forcing rejection after reaching Uρ and accepting admissible proposals outside Uρ.This construction supports a comparison between the modified chain and the original reversible chain.
  • Standard setting: For sufficiently small η, the two chains are ε-close, with ε controlled by η, d, G, and L, enabling a conductance-based hitting-time bound.The proof chooses η so that the closeness condition required by the auxiliary-chain lemma holds.
  • Standard setting: The SGLD chain can be generated as a subsequence of the auxiliary chain, so its hitting time is bounded by the auxiliary chain’s hitting time.The subsequence retains exactly the SGLD transition kernel while omitting delta-distribution proposals.

C Proof of Proposition 1

The proposition lower bounds the restricted Cheeger constant by exploiting an isoperimetric inequality and concentration of the tilted measure ξf near a global minimum. A sufficiently large ξ makes the complement of U have measure at most one-half.

  • C Proof of Proposition 1: The proof applies an isoperimetric inequality for log-concave distributions to lower bound the restricted Cheeger constant.The set V is chosen as K\U and the objective is scaled to ξf.
  • C Proof of Proposition 1: Inside a radius-r neighborhood of a global minimum, the density under µξf is at least e^(ξϵ/2) times the density on K\U.The radius is chosen as r=ϵ/(2G).
  • C Proof of Proposition 1: A contained ball around the global minimum supplies enough mass for the comparison with K\U.For the unit-ball geometry, a ball of radius r/2 is constructed inside B(x*;r)∩K.
  • C Proof of Proposition 1: Choosing ξ large enough ensures µξf(K\U)≤1/2, satisfying the precondition needed for the isoperimetric lower bound.The proof uses the condition ξ≥2d log(4G/ϵ)/ϵ.

D Proof of Lemma 1

The proof establishes a restricted Cheeger lower bound by analyzing a small deformation of sets along a vector field. Local injectivity, Jacobian expansions, and density changes determine the resulting measure growth.

  • D Proof of Lemma 1: The map π(x)=x−ϵφ(x) is continuous and one-to-one when ϵ is sufficiently small.The Lipschitz property of φ gives a positive lower bound on distances between distinct mapped points.
  • D Proof of Lemma 1: A compact-set partition approximates A by subsets of diameter at most ϵ^2 and places their union inside Aδ.This controls the geometric error in the set deformation.
  • D Proof of Lemma 1: The Jacobian of π is expanded around each partition point with a remainder bounded by C1ϵ^2.The matrix H is the Jacobian of φ.
  • D Proof of Lemma 1: The density µf at the mapped point is approximated with a remainder bounded by C2ϵ^2, and subsequent expansions introduce another O(ϵ^2) remainder.These estimates quantify how the deformation changes measure.
  • D Proof of Lemma 1: Combining the Jacobian and density estimates yields a lower bound on the measure of π(B), and taking ϵ→0 completes the restricted Cheeger argument.The divergence relation tr(H(x))=div φ(x) enters the final bound.

E Proof of Proposition 3

The proof constructs a vector field from the gradient and Hessian of f, then bounds its divergence through eigenvalue and gradient-size cases. These bounds yield a restricted Cheeger lower bound for points outside approximate local minima.

  • E Proof of Proposition 3: The proof defines g(x)=||∇f(x)||2 and constructs a vector field using a matrix function of the Hessian.The matrix function is defined through a polynomial expansion and differentiated as needed.
  • E Proof of Proposition 3: The constructed field satisfies ||φ(x)||2≤1 and remains feasible near the boundary under the stated stepsize conditions.The argument uses positive semidefiniteness and an upper spectral bound on A(x).
  • E Proof of Proposition 3: The divergence calculation is expressed through the derivative matrix D of A(x)∇f(x), whose trace equals div(A(x)∇f(x)).Third-derivative tensor terms appear when differentiating the vector field.
  • E Proof of Proposition 3: When g(x)<ϵ, approximate-local-minimum conditions imply a sufficiently negative smallest Hessian eigenvalue, which controls the first divergence term.The proof separately bounds the remaining Hessian-gradient and third-derivative contributions.
  • E Proof of Proposition 3: When g(x)≥ϵ, the proof drops the negative-curvature implication while retaining the bounds for the other divergence terms.Combining both cases completes the divergence estimate.

F Proof of Theorem 2

The proof smooths the empirical risk and constructs an unbiased stochastic gradient satisfying the assumptions needed for the general SGLD hitting-time theorem. It then transfers the resulting risk and iteration bounds through restricted-Cheeger-constant stability.

  • Smoothing and stochastic gradients: The stochastic gradient g is an unbiased estimator of ∇˜fσ and satisfies the required exponential-moment bound.The construction uses bounded loss values and Gaussian perturbations.
  • Applying the hitting-time theorem: Theorem 1 converts the restricted Cheeger constant into a polynomial hitting-time bound under sufficiently small stepsize.The proof applies the theorem after verifying the smoothness, boundedness, and stochastic-gradient conditions.
  • Applying the hitting-time theorem: Perturbation stability shows that the restricted Cheeger constants of ˜fσ and ˜Fσ differ by only a constant multiplicative factor.Uniform closeness of the empirical and auxiliary smoothed risks supports this comparison.
  • Smoothing and stochastic gradients: The smoothed empirical risk ˜fσ is differentiable and (2B/σ2)-smooth.Gaussian convolution provides differentiability, while boundedness of f yields the stated smoothness constant.

G Proof of Theorem 3

The proof specializes the general hitting-time result to linear classification on an annular parameter space. It identifies a target set of nearly optimal directions, lower-bounds its restricted Cheeger constant, and derives polynomial risk and iteration guarantees.

  • Problem setup and assumptions: The parameter space is the annulus K = {x ∈ R^d : 1/2 ≤ ∥x∥2 ≤ 1}, enlarged to an auxiliary set for verifying assumptions.The proof checks the theorem’s geometric and regularity conditions on this setup.
  • Problem setup and assumptions: The population risk F is 3-Lipschitz continuous, while uniform convergence gives supx∈K |f(x) − F(x)| ≤ ν with high probability.The required empirical-population closeness follows from a sufficiently large sample size.
  • Target set and geometric bound: For small enough α0, the angular target set U contains nearly optimal solutions.The proof uses inequality (94) to establish this target-set property.
  • Target set and geometric bound: The restricted Cheeger constant satisfies C(ξF)(K\U) ≥ c2d when ξ is chosen at least on the order specified by Lemma 9.This geometric lower bound drives the iteration-complexity estimate.
  • Final guarantee: With α0 := arcsin(ϵ/12) and sufficiently small ν, SGLD achieves F(bx) ≤ F(x∗) + ϵ in polynomially many iterations.The iteration complexity is polynomial in (d, 1/q0, 1/ϵ, log(1/δ)).

G.1 Proof of Lemma 8

The proof verifies Lemma 8 for the linear-classifier population risk by establishing Gaussian-noise containment, Lipschitz continuity, and uniform convergence of empirical risk to population risk.

  • Gaussian perturbations: A sufficiently small stepsize h ensures Gaussian perturbations remain in the enlarged parameter region with probability bounded below by a constant.The proof selects h proportional to d^-2 and obtains a probability lower bound of 1/3.
  • Lipschitz continuity: The population risk F is 3-Lipschitz on the enlarged set K.The bound follows by relating differing zero-one losses to sign changes and angular separation.
  • Uniform convergence: Linear classifiers have VC-dimension d + 1, yielding a polynomial uniform-convergence requirement for supx∈K |f(x) − F(x)| ≤ ν.The resulting sample threshold satisfies n0 ≲ d/ν2 up to poly-logarithmic factors.

G.2 Proof of Lemma 9

The proof lower-bounds the restricted Cheeger constant for the population-risk problem by smoothing the potentially non-differentiable risk and constructing a feasible vector field with positive directional progress.

  • Smoothing and vector-field construction: Because F may be non-differentiable, the proof introduces the Gaussian-smoothed approximation ˜Fσ before applying the Cheeger lower-bound lemma.The smoothed function is continuously differentiable and converges uniformly to F as σ → 0.
  • Smoothing and vector-field construction: The vector field φδ is constructed so that x − ϵφδ(x) remains in K for sufficiently small ϵ.This verifies the feasibility condition required by the geometric lemma.
  • Cheeger lower bound: The proof concludes the Cheeger lower bound by combining the smoothed-risk gradient representation with the limiting argument σ → 0.This transfers the geometric estimate from ˜Fσ back to the population-risk setting.
  • Directional risk behavior: Moving from x to x − ϵx∗ does not decrease the population risk under the Massart noise model.The proof establishes F(x − ϵx∗) − F(x) ≥ 0 through the loss-change event and the noise condition.
  • Cheeger lower bound: The directional construction and angular decomposition produce a lower bound proportional to d for points outside the target angular set.The final bound uses the condition involving d3/2q0sin2(α0).
Loading 1702.05575v3…