PaperlayerView exact revision on arXiv

Source-linked AI summary

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

Zeyuan Allen-Zhu

arXiv:1801.02982v3cs.LGcs.DSmath.OCstat.ML

TL;DR

The paper addresses the difficulty of finding small-gradient points efficiently in stochastic optimization, where this goal can require new algorithmic ideas even for convex objectives. It introduces SGD variants using Nesterov’s tricks and applies the techniques to non-convex optimization, with SGD3 achieving an optimal-up-to-log-factors rate.

  • Problem

    Finding points with small gradients is harder than standard stochastic optimization and can require new algorithmic ideas, including beyond accelerated gradient descent.

  • Method

    The paper designs SGD2 and SGD3 using Nesterov’s tricks, then applies the techniques to non-convex optimization through SGD4 and SGD5.

  • Results

    SGD3 finds a point with gradient norm at most ε in a rate proportional to ε^-2 log^3(1/ε), which is optimal up to logarithmic factors.

  • Takeaways & Limitations

    The techniques provide improved stochastic rates for convex small-gradient optimization and extend to standard non-convex optimization tasks.

  • Takeaways & Limitations

    When finding approximate local minima, the method omits the proximal term because defining local minima with that term can be tricky, and second-order smoothness is required.

Abstract

from arXiv · show

Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives $f(x)$. However, in terms of making the gradients small, the original SGD does not give an optimal rate, even when $f(x)$ is convex. If $f(x)$ is convex, to find a point with gradient norm $\varepsilon$, we design an algorithm SGD3 with a near-optimal rate $\tilde{O}(\varepsilon^{-2})$, improving the best known rate $O(\varepsilon^{-8/3})$ of [18]. If $f(x)$ is nonconvex, to find its $\varepsilon$-approximate local minimum, we design an algorithm SGD5 with rate $\tilde{O}(\varepsilon^{-3.5})$, where previously SGD variants only achieve $\tilde{O}(\varepsilon^{-4})$ [6, 15, 33]. This is no slower than the best known stochastic version of Newton's method in all parameter regimes [30].

1 Introduction

The paper studies stochastic optimization rates for finding small gradients, where the convex problem lacked tight bounds and standard objective-value guarantees were insufficient. It introduces recursive regularization-based SGD methods that improve convex rates and extend to nonconvex stationary-point and local-minimum tasks.

  • T ∝ ε^-8/3 was the best recorded convex stochastic rate, with improvement posed as an open question.
  • Convex stochastic optimization: SGD2 achieves T ∝ ε^-5/2, while SGD3 improves this to T ∝ ε^-2 log^3 1/ε, optimal up to logarithmic factors.
  • Finding small gradients is central for nonconvex optimization and can support faster nonconvex machine-learning algorithms.
  • Convex stochastic optimization: SGD3 improves the best known convex rate and approaches the lower bound Ω(V/ε^2) for stochastic-gradient samples.
  • Algorithmic approach: The convex methods use recursive warm starts and regularization, while the nonconvex extension recursively minimizes strongly convex regularized objectives.
  • Nonconvex applications: SGD4 targets small gradients in σ-bounded nonconvex optimization, and SGD5 targets (ε, δ)-approximate local minima under first- and second-order smoothness assumptions.

2 Preliminaries

The preliminaries establish notation for norms, eigenvalues, convexity, smoothness, gradient mappings, and Fenchel duality used throughout the paper.

  • The paper uses the Euclidean norm, uniformly random index notation, gradients, subgradients, and event indicators as basic conventions.
  • For symmetric matrices, A ⪰ B means A − B is positive semidefinite, while λmin and λmax denote extreme eigenvalues.
  • Strong convexity, bounded nonconvexity, and L-smoothness are defined through first-order inequalities and gradient Lipschitzness.
  • For composite F(x) = ψ(x) + f(x), the gradient mapping generalizes the gradient and equals ∇f(x) when ψ is identically zero.
  • Fenchel duality supplies the relation ∇h*(β) = arg max_y{y⊤β − h(y)}, with strong convexity of h implying smoothness of h*.

3 Problem Formalization

The paper formalizes online stochastic composite optimization by measuring stochastic-gradient complexity needed to find points with small gradient mappings under standard convexity and variance assumptions.

  • The main objective is a convex stochastic composite function F(x) = ψ(x) + f(x), with f smooth and possibly σ-strongly convex.
  • The stochastic setting allows n to be extremely large or infinite, with f(x) represented as an expectation over component functions.
  • The component stochastic gradients are assumed to have bounded variance over the domain of ψ.
  • The gradient complexity T counts computations of ∇f_i(x), and the target is a point satisfying ∥G_F,η(x)∥ ≤ ε.
  • Online algorithms have gradient complexity independent of n, unlike offline methods such as GD, AGD, and Katyusha.

4 Review: SGD with Objective Value Convergence

This section reviews classical SGD guarantees for objective-value convergence and derives corresponding gradient-mapping rates under general and strongly convex objectives.

  • SGD repeatedly performs stochastic proximal updates, reducing to ordinary stochastic gradient steps when ψ is identically zero.
  • The objective-value guarantees are presented as classical results for SGD and its decreasing-learning-rate strongly convex variant.
  • When stochastic-gradient variance V is zero, SGD’s convergence rate matches gradient descent, although accelerated gradient descent can be faster.
  • Classical SGD achieves F(x) − F(x*) ≤ O(T^-1/2) and ∥G_F,η(x)∥ ≤ O(T^-1/4) for the general problem.
  • For σ-strongly convex f with σ > 0, the reviewed rates become F(x) − F(x*) ≤ O((σT)^-1) and ∥G_F,η(x)∥ ≤ O((σT)^-1/2).

5 An Auxiliary Lemma on Regularization

The auxiliary analysis studies regularized objectives and shows how approximate stationarity for a strongly convex regularization transfers to approximate stationarity for the original composite objective.

  • The regularized objective adds a quadratic penalty around fixed reference vectors, making the auxiliary function strongly convex.
  • An approximate stationary point of the regularized function is also an approximate stationary point of the original function up to an additive error.
  • The composite-function theorem supports an additional proper convex proximal term without imposing Lipschitz or smoothness assumptions on that term.
  • The analysis uses Fenchel duality and smoothness of the dual induced by strong convexity of the primal function.
  • Gradient-mapping properties relate the minimizer and the auxiliary point through inequalities involving the regularized objective.

6 Approach 3: SGD and Recursive Regularization

SGD3 uses recursively strengthened regularization to convert objective progress into a small gradient mapping for convex stochastic optimization. The construction achieves the theorem’s stated gradient guarantee under strong-convexity and smoothness conditions.

  • Recursive regularization: SGD3 adds logarithmically many regularizers centered at carefully chosen approximate minimizers.Each successive regularizer uses an approximate minimizer of the preceding regularized objective, with regularization parameters doubling across stages.
  • Algorithm: SGD3sc computes each successive approximate minimizer using SGDsc, then returns the final stage after S iterations.The total gradient complexity is summarized through the number of stages and iterations.
  • Algorithm: SGD3 regularizes non-strongly-convex objectives before applying SGD3sc to the resulting strongly convex objective.The added quadratic term makes the regularized objective strongly convex, enabling the strongly convex subroutine.
  • Guarantee: Theorem 3 establishes SGD3’s guarantee for solving the convex stochastic problem from an arbitrary starting vector and admissible learning rate.The theorem is stated for x0 in R^d and η chosen as a constant multiple of the reciprocal smoothness scale.
  • Guarantee: When the objective is σ-strongly convex with σ ∈ (0, L], the theorem applies for T ≥ L.The supplied theorem statement identifies the strong-convexity range and iteration condition.
  • Guarantee: With an appropriate σ, SGD3 finds x satisfying E[∥GF,η(x)∥] ≤ ε in the stated gradient complexity.Expected guarantees can be converted into high-confidence bounds by repeating the algorithm and selecting the point with the smallest estimated gradient mapping.

7 Applications to Non-Convex Optimization

The paper extends recursive regularization to nonconvex optimization through SGD4 for small gradients and SGD5 for approximate local minima. SGD5 combines regularized SGD steps with curvature detection and saddle-point movement under smoothness assumptions.

  • SGD4: Stationary points: SGD4 targets approximate stationary points of L-smooth functions with σ-bounded nonconvexity.The paper’s goal is a point with small gradient mapping, which equals the gradient when there is no proximal term.
  • SGD4: Stationary points: SGD4 recursively minimizes strongly convex regularized objectives and then applies SGD3sc to reduce the gradient norm.At each stage, the regularizer is centered at the preceding approximate minimizer; the final stage is selected uniformly at random.
  • SGD4: Stationary points: SGD4’s theorem gives an output with E[∥GF,η(x)∥] ≤ ε under the stated initialization, smoothness, regularization, and iteration conditions.The result is stated with gradient complexity O(T), and the expected guarantee can be amplified to high confidence.
  • SGD5: Local minima: SGD5 seeks an (ε, δ)-approximate local minimum satisfying both a small gradient and ∇2f(xout) ⪰ −3δI.Its setting assumes L-smooth individual functions, L2-second-order smoothness, and bounded stochastic-gradient variance.
  • SGD5: Local minima: SGD5 uses Oja’s algorithm to detect negative curvature, then either takes a randomized second-order step or performs a regularized first-order SGD step.The first-order step minimizes a regularized objective with SGD3sc; the curvature threshold and regularization are selected for different parameter regimes.
  • SGD5: Local minima: With probability at least 2/3, SGD5 outputs xout satisfying ∥∇f(xout)∥ ≤ ε and ∇2f(xout) ⪰ −3δI under the theorem’s assumptions.The total gradient complexity is given in the theorem and its corollary, including the reparameterized regime for δ.

A Other Related Work

The related-work discussion distinguishes online and offline stochastic optimization, discusses finite-sum methods, and notes a Moreau-envelope alternative for nonsmooth objectives. It also contrasts the paper’s regularization schedule with prior graduated-regularization analyses.

  • Offline stochastic optimization: Offline stochastic methods allow gradient complexity to depend on the finite-sum size n and include methods such as Katyusha.For strongly convex finite sums, objective-value rates can translate into small-gradient guarantees; the table summarizes these methods for comparison.
  • Online versus offline: Online methods have gradient complexity independent of n, addressing settings where n is extremely large or infinite.The paper classifies SGD and its variants as online, while GD, AGD, and Katyusha are offline.
  • Graduated regularization: Prior graduated-regularization work halves the regularization parameter across logarithmically many rounds, whereas SGD3 doubles it.The paper states that the earlier analysis cannot be applied to its setting.
  • Nonsmooth objectives: For nonsmooth objectives, the paper discusses minimizing the gradient of a Moreau envelope rather than directly finding approximate stationary points.The envelope is smooth when λ > 2σ, and a small envelope gradient implies proximity to a point with a small subgradient under the stated relationship.

B Approach 1: SGD After SGD

SGD1 first obtains a point with good objective value and then applies minibatch SGD to prune the gradient. This yields the paper’s first stochastic reduction from objective accuracy to small-gradient guarantees.

  • Method: SGD1 replaces the direct objective-to-gradient conversion with multiple SGD steps that prune a point’s gradient.The method starts from a point computed by SGD or SGDsc and randomly outputs one of the iterates.
  • Method: SGD1 uses T1 SGD updates with minibatch size T/T1, so the total gradient complexity remains T.Each minibatch is formed from a uniform random subset of component functions.
  • Guarantees: Theorem 1 states guarantees for SGD1 and its strongly convex variant SGD1sc when their parameters are appropriately chosen.Both variants randomly output an iterate from the pruning phase, with expected guarantees that can be amplified to high confidence.
  • Comparison: For ψ(x) ≡ 0, the recorded SGD1 rate is T ∝ ε^-8/3, while acceleration is unnecessary for achieving that rate.The paper attributes the earlier accelerated result to Ghadimi and Lan and states that acceleration only improves lower-order terms.
  • Analysis: The analysis bounds minibatch variance using independent averaging and the assumption E_i∥∇f(x) − ∇f_i(x)∥^2 ≤ V.The proof then telescopes the one-step inequality over the pruning iterations.
  • Analysis: The strongly convex analysis substitutes an objective-gap bound from the strongly convex SGD theorem before balancing the two resulting terms.The final result follows after choosing T1 within [1, T] and randomly selecting among the generated iterates.

C Approach 2: SGD After Regularization

The approach regularizes F into G, applies a stochastic method to find a stationary point of G, and transfers the result back to F when the regularization is suitably small.

  • Regularization: The method replaces F(x) with a regularized function G(x) using a small parameter σ.This is described as a stochastic generalization of Nesterov’s second trick.
  • Regularization: A stationary point found for G becomes a stationary point for F when σ is sufficiently small.The transfer relies on Lemma 5.1.
  • Guarantee: SGD2 is analyzed for minimizing the regularized objective from a starting vector x0 with σ ∈ (0, L/2].The theorem specifies SGD2’s inputs and assumes x∗ minimizes F.
  • Guarantee: With suitable choices of T1 and σ, SGD2 finds a point whose expected gradient measure for F is at most ε2.The guarantee is stated in terms of E[∥GF,η(x)∥2].
  • Guarantee: The expected guarantee can also be converted into a high-confidence guarantee.The passage attributes this to the same reason as Remark 6.1.

D Proofs for Section 4

This section proves the convex SGD results using standard regret and smoothness inequalities, multistage applications of SGD, and Oja’s algorithm for stochastic eigenvector estimation.

  • Convex SGD analysis: Theorem 4.1(a) bounds the expected objective gap of SGD using the stepsize, stochastic-gradient variance, iteration count, and initial distance to x∗.The bound requires α < 1/L.
  • Convex SGD analysis: Choosing α ≤ 1/(2L) balances the terms and yields an averaged iterate over x1, …, xT.The proof obtains the averaged point by telescoping the per-iteration inequality.
  • Strongly convex analysis: For strongly convex objectives, repeated applications of the basic SGD result produce a tighter guarantee across multiple rounds.The proof uses initial rounds with αk = 1/(2L), followed by additional rounds with increasing iteration lengths.
  • Strongly convex analysis: The total gradient complexity of the multistage procedure is bounded by the combined cost of its rounds.The proof concludes by relating the number of rounds to the final iteration scale.
  • Stochastic eigenvector estimation: Oja’s algorithm estimates eigenvector information from stochastic matrix samples, with repeated runs providing a high-probability guarantee.The analysis bounds the total number of Hessian-vector products by O(T log(1/p)).
  • Stochastic eigenvector estimation: Hessian-vector products allow Oja’s method to estimate the minimum eigenvalue of a stochastic Hessian-related matrix.The construction uses matrices of the form L·I − ∇2fi(x).

E.3 Proof of Theorem 5

The proof of Theorem 5 combines first-order SGD, second-order eigenvector searches, and regularized subproblems, while accounting for objective decrease and the costs of each component.

  • Curvature detection: Oja’s algorithm is used repeatedly to find a direction of sufficiently negative curvature or certify approximate positive semidefiniteness.The proof assumes all Oja calls succeed simultaneously under the stated probability event.
  • Objective decrease: Each second-order step produces expected objective decrease, while the first-order steps contribute a separately bounded decrease.The proof introduces Δ1 and Δ2 to aggregate these two contributions.
  • Regularized subproblem: The final first-order subproblem uses the regularized functions F and G and applies SGD3sc to minimize G.The output xout is analyzed using the guarantee from Theorem 3(a).
  • Accuracy: The output xout is close enough to y that its gradient is at most ε and its Hessian is bounded below by −3δI.This establishes the accuracy conditions used for SGD5.
  • Algorithmic decomposition: SGD5 separates its iterations into first-order and second-order steps, with N1 first-order steps and random variable N2 counting second-order steps.The proof tracks the objective decrease contributed by each type of step.
  • Running time: The total gradient complexity is the sum of the final SGD3sc cost and the costs of the first- and second-order steps.The proof writes this as Tsgd + (N1 + N2) · L2 in the displayed complexity expressions.
Loading 1801.02982v3…