PaperlayerView exact revision on arXiv

Source-linked AI summary

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

Alexander Rakhlin, Ohad Shamir, Karthik Sridharan

arXiv:1109.5647v7cs.LGmath.OC

TL;DR

The paper investigates whether the known O(log(T)/T) rate makes averaged SGD suboptimal for strongly convex stochastic optimization. It analyzes SGD across smooth and non-smooth settings and shows that smooth problems attain O(1/T), while suffix averaging recovers O(1/T) in the non-smooth case. Experiments support these findings, though the theory does not explain the observed performance of the last iterate in non-smooth problems.

  • Problem

    It was unclear whether averaged SGD’s O(log(T)/T) rate was intrinsic or merely an artifact of analysis, especially compared with methods achieving O(1/T).

  • Method

    The paper directly analyzes standard SGD for strongly convex stochastic problems, comparing last-point and averaging strategies under smooth and non-smooth objectives.

  • Results

    SGD achieves O(1/T) for smooth problems; non-smooth averaged SGD can incur Ω(log(T)/T), while averaging only the last αT points restores O(1/T).

  • Takeaways & Limitations

    A simple modification of SGD’s averaging step can recover the optimal rate without adopting a substantially different algorithm.

  • Takeaways & Limitations

    The current theory does not cover why the last iterate appears to perform well in non-smooth experiments.

Abstract

from arXiv · show

Stochastic gradient descent (SGD) is a simple and popular method to solve stochastic optimization problems which arise in machine learning. For strongly convex problems, its convergence rate was known to be O(\log(T)/T), by running SGD for T iterations and returning the average point. However, recent results showed that using a different algorithm, one can get an optimal O(1/T) rate. This might lead one to believe that standard SGD is suboptimal, and maybe should even be replaced as a method of choice. In this paper, we investigate the optimality of SGD in a stochastic setting. We show that for smooth problems, the algorithm attains the optimal O(1/T) rate. However, for non-smooth problems, the convergence rate with averaging might really be Ω(\log(T)/T), and this is not just an artifact of the analysis. On the flip side, we show that a simple modification of the averaging step suffices to recover the O(1/T) rate, and no other change of the algorithm is necessary. We also present experimental results which support our findings, and point out open problems.

1 Introduction

The paper asks whether standard SGD is truly limited to O(log(T)/T) on strongly convex stochastic problems or whether this rate reflects loose analysis. It shows that smoothness yields optimal O(1/T), while non-smooth problems require modified averaging to recover that rate.

  • Motivation: Strongly convex objectives have a known O(log(T)/T) guarantee for averaged SGD.Strong convexity is relevant to SVMs and other regularized learning algorithms.
  • Motivation: A different, more complex algorithm had already achieved the optimal O(1/T) rate for strongly convex stochastic problems.Its iterations are divided into exponentially increasing epochs, with averaged SGD run within each epoch.
  • Research question: The central question is whether averaged SGD can also achieve O(1/T), rather than being limited by an artifact of loose analysis.The answer matters because a genuine rate gap could favor replacing SGD in practice.
  • Contributions: For smooth strongly convex functions, SGD with or without averaging achieves the optimal O(1/T) convergence rate.This is the paper’s first stated contribution.
  • Contributions: For non-smooth functions, averaged SGD can have an Ω(log(T)/T) rate, showing that the general logarithmic factor is real.The result rules out attributing this rate solely to limitations of the existing analysis.
  • Contributions: Averaging only the last αT points, for arbitrary α ∈(0, 1), recovers O(1/T) without substantially changing SGD.The paper also reports empirical support from artificial and real-world data.

2 Preliminaries

The paper formulates stochastic optimization through an unbiased stochastic-gradient oracle and studies projected SGD with decreasing step sizes and several output rules. Its analysis assumes bounded expected squared stochastic-gradient norms and focuses on strongly convex objectives, optionally with smoothness.

  • Problem setting: The optimization goal is to minimize an unknown convex F over W using only unbiased stochastic subgradient estimates.The analysis bounds F(w_t)−F(w*) in expectation or with high probability.
  • Problem setting: Strong convexity is the main structural assumption, while smoothness with respect to the optimum is an additional property considered later.Strong convexity is defined through a quadratic lower-bound condition, and smoothness is defined relative to w*.
  • Algorithm: SGD queries the stochastic gradient oracle at w_t and updates the iterate using projection onto W.The update is parameterized by step sizes η_1,…,η_T and starts from 0 ∈W.
  • Algorithm: The algorithm can return either the last iterate or an average of the generated points.The standard averaged output is formed from w_1 through w_T.
  • Step sizes: The analysis uses η_t = 1/(λt), representing the relevant Θ(1/t) step-size regime.The paper notes that excessively small step sizes can cause the SGD analysis to fail.
  • Assumptions: The stochastic gradients satisfy E[∥ĝ_t∥2] ≤ G2, an assumption weaker than an almost-sure norm bound.Such bounds may follow from a bounded domain or suitable initialization.

3 Smooth Functions

For strongly convex functions that are smooth with respect to the optimum, the paper proves that SGD’s last iterate and averaged iterate both converge at the optimal O(1/T) rate. The proof connects distance-to-optimum control with smoothness.

  • Last iterate: SGD’s last iterate achieves an O(1/T) rate when F is strongly convex and smooth with respect to w*.The theorem assumes E[∥ĝ_t∥2] ≤ G2 and η_t = 1/(λt).
  • Proof strategy: The last-iterate result follows from a key lemma for strongly convex objectives together with the definition of smoothness.The lemma uses the same decreasing step size and expected gradient-norm condition.
  • Averaged iterate: The averaged iterate also achieves the optimal O(1/T) rate for smooth strongly convex F.This establishes that standard averaging is sufficient under the smoothness condition.
  • Proof intuition: The proof intuition is that SGD iterates approach w* at a rate whose averaged squared distance is on the order of 1/T, after which smoothness controls the objective error.The argument relates iterate-distance bounds to the performance of the averaged point.

4 Non-Smooth Functions

For non-smooth strongly convex objectives, averaged SGD can genuinely have an Ω(log(T)/T) convergence rate, rather than this logarithm being merely an analysis artifact. This lower bound can persist even when the optimum lies in the interior, while non-smoothness includes losses such as hinge loss.

  • Non-smooth functions: Non-smoothness means no constant μ satisfies the smoothness condition uniformly over the domain; hinge loss is an example.This section considers the general case where F is strongly convex but not smooth.
  • Lower bound: Ω(log(T)/T) is a lower bound for averaged SGD on some non-smooth strongly convex stochastic problems.When c is constant and η_t = c/t, the lower bound has this rate.
  • Lower bound: The logarithmic factor is a property of the SGD algorithm, not merely a shortcoming of standard online analysis.A different algorithm can achieve O(1/T) in the non-smooth case, whereas averaged SGD cannot always do so.
  • Lower bound: An optimum at the boundary can make averaging harmful because SGD approaches it from only one direction.The paper then extends this intuition beyond boundary optima.
  • Interior optima: Ω(log(T)/T) can remain unavoidable even when the optimum lies well inside the domain.The construction uses a non-smooth function that forces iterates to approach the optimum from one direction.
  • Construction: The lower-bound construction uses a 1-strongly convex function, a bounded stochastic-gradient oracle, and step sizes η_t = c/t.The theorem applies for sufficiently large T and specified initialization conditions.

5 Recovering an O(1/T) Rate for SGD with α-Suffix Averaging

A simple change to SGD’s output rule—averaging only a constant-fraction suffix of iterates—recovers the optimal O(1/T) rate for strongly convex, potentially non-smooth objectives.

  • Implication: Suffix averaging obtains the optimal rate without replacing standard SGD with a substantially different algorithm.The paper contrasts this modification with epoch-based and other specialized algorithms.
  • Method: O(1/T) convergence is achieved by averaging only the last αT SGD iterates, rather than all T iterates.Here α is any constant in (0, 1), with αT and (1 − α)T assumed integral.
  • Guarantee: The resulting α-suffix averaging bound is O(G2/λT) for any constant α ∈(0, 1).The theorem assumes step sizes ηt = 1/λt, λ-strong convexity, and E[∥ˆgt∥2] ≤G.
  • Guarantee: The guarantee remains optimal even when F is not smooth, unlike the last-iterate comparison whose bound degrades as smoothness weakens.The paper compares suffix averaging with the last-iterate result for smooth functions and notes the contrast for less-smooth functions.
  • Practical consideration: If all iterates cannot be stored or T is unknown, exponentially increasing epochs can maintain an average corresponding to a constant-portion suffix.The paper also suggests guessing when a constant portion of the iterates has passed, because the results are robust to α.

6 High-Probability Bounds

The paper extends its expected-suboptimality results to high-probability guarantees under stronger bounded-gradient assumptions. These guarantees incur an additional log(log(T)) factor and depend logarithmically on the confidence parameter.

  • Comparison: The high-probability bounds add a mild log(log(T)) factor compared with the in-expectation bounds.The paper notes that it is unknown whether this factor is necessary.
  • Assumptions: The high-probability analysis assumes almost-surely bounded stochastic gradients, strengthening the expectation-based assumptions used for the earlier bounds.Proposition 1 assumes ∥ˆgt∥2 ≤G2 with probability 1, whereas the preceding bounds were on expected suboptimality.
  • Guarantee: High-probability versions of the main theorems achieve O(log(log(T)/δ)/T) rates with probability at least 1 −δ.The result applies for δ ∈(0, 1/e) and uses a strengthened lemma in the proofs of Theorems 1, 2, and 5.

7 Experiments

Experiments compare four SGD-related algorithms on synthetic smooth and non-smooth strongly convex problems and real-world classification datasets. The results generally support the theory: full averaging performs worst, while suffix averaging and last-iterate SGD perform competitively.

  • Experimental setup: Four methods were evaluated: averaging all T predictors, α-suffix averaging with α=1/2, returning the last predictor, and Epoch-Gd.Sgd-α averages the last T/2 rounds; Epoch-Gd is the algorithm of Hazan and Kale.
  • Synthetic problems: Θ(1/T) convergence was observed for all four methods on the smooth strongly convex synthetic problem.The experiment used W=[−1,1]^5, F(w)=∥w∥^2, and noisy unbiased stochastic gradients.
  • Synthetic problems: Θ(log(T)/T) behavior appeared for Sgd-A on the non-smooth strongly convex problem, while the other three methods appeared to achieve Θ(1/T).Sgd-L and Sgd-α seemed somewhat better than Epoch-Gd.
  • Real-world data: The real-world experiments used ccat, cov1, and astro-ph binary classification datasets with linear-kernel Support Vector Machine objectives.Training and test objective values were reported, with single-example stochastic gradients and no projections.
  • Real-world data: Sgd-A performed worst across the real-world experiments, while Sgd-α and Sgd-L were generally competitive with Epoch-Gd.Sgd-α was slightly better on Cov1, whereas Sgd-L was slightly better on astro-ph and ccat.
  • Synthetic problems: Sgd-L appeared to achieve Θ(1/T) on the non-smooth synthetic problem but showed larger variance than Sgd-α.The authors state that current theory does not cover last-iterate convergence for non-smooth problems.

8 Discussion

The paper concludes that SGD is optimal for smooth strongly convex stochastic optimization, while standard averaging can be suboptimal for non-smooth problems. It identifies unresolved questions about last-iterate convergence and practical averaging choices.

  • Discussion: SGD performs optimally when the strongly convex objective is smooth, but standard averaging can be suboptimal for non-smooth objectives.A simple averaging modification recovers the optimal rate without requiring a substantially different algorithm.
  • Open issues: The non-smooth O(1/T) rate still requires some form of averaging according to the paper’s established theory.This contrasts with empirical evidence that returning the last iterate can perform well.
  • Open issues: The current theory does not establish an O(1/T) rate for SGD without averaging on general strongly convex problems.The paper notes that existing arguments provide only an O(1/T) rate via Lemma 1 and Jensen’s inequality, while practice appears better.
  • Open issues: The paper also leaves open which averaging scheme is best in practice and calls for a fuller empirical study.The conclusion is presented as an open issue rather than a settled recommendation.
  • Step-size discussion: For optimal rates, the appendix focuses on η_t=Θ(1/t), arguing that smaller step sizes cannot move iterates toward the optimum fast enough.For the deterministic quadratic example, it derives the necessary lower bound η_t≥Ω(1/t).
  • Step-size discussion: For a non-smooth strongly convex example, stochastic fluctuations motivate η_t=O(1/t), with a lower bound E[F(w_t)]≥η_t/16 in the proof setting.A similar lower bound is stated for the unconstrained setting.

B Proofs

The proofs develop technical tools for analyzing stochastic gradients and projected iterates in strongly convex optimization. They use martingale concentration, variance control, convexity, and induction-based bounds.

  • Technical results: The appendix collects technical results used in the paper’s other proofs.These include concentration inequalities and bounds on stochastic-gradient behavior.
  • Gradient bounds: Strong convexity implies that expected squared stochastic-gradient norms increase as iterates move farther from the optimum.The proof combines strong convexity, Cauchy–Schwarz, and unbiased-noise properties.
  • Concentration: Freedman’s inequality controls martingale difference sequences using bounded increments and their cumulative conditional variance.The stated theorem provides a probability bound parameterized by a step bound and variance quantity.
  • Concentration: A lemma bounds martingale differences with uniformly bounded increments by discretizing possible variance scales.The proof uses a geometric sequence of variance thresholds and a union-bound-style summation over scales.
  • Iterate bounds: Projection onto a convex domain does not increase distance to any point in that domain, enabling recursive distance bounds for SGD iterates.The proof combines this nonexpansiveness with strong convexity and prior lemmas.

B.3 Proof of Thm. 2

The proof of Theorem 2 analyzes the averaged iterate by expanding its recursive update and bounding the resulting distance terms. Smoothness then converts the distance bound into an objective-gap rate.

  • Averaging recursion: The running average satisfies the recursion ¯w_{t+1}=(t¯w_t+w_{t+1})/(t+1).The proof expands the squared distance of this average from the optimum.
  • Averaging recursion: The squared-distance expansion produces cross terms and squared-distance terms involving ¯w_t and w_{t+1}.Cauchy–Schwarz is used to bound the cross term involving the two iterates.
  • Inductive bound: Induction, initialized using Lemma 2, yields the required bound on the averaged iterate’s distance from the optimum.The proof verifies the recursive estimate across all iterations.
  • Objective-rate conversion: Smoothness gives F(¯w_T)−F(w*)≤(μ/2)∥¯w_T−w*∥^2, converting the distance estimate into the theorem’s convergence result.The final step combines the smoothness inequality with the preceding averaged-distance bound.

B.4 Proof of Thm. 3

The proof analyzes the first coordinate of the SGD iterate by conditioning on whether an auxiliary variable is below or above −1/2. This yields a lower bound on the expected objective gap.

  • The first-coordinate iterate is analyzed separately.
  • Conditioning on Z_t ≤ −1/2 and Z_t > −1/2 decomposes E[w_{t+1,1}] into two conditional contributions.
  • The step-size condition η_t = c/t ≤ 2 applies when t ≥ T_0.
  • The expected objective gap satisfies E[F( w̄_T ) − F(w*)] ≥ 1/(16T).
  • Substituting η_t = c/t completes the required result.

B.5 Proof of Thm. 4

The proof establishes the non-smooth lower-bound behavior by showing that the first coordinate cannot remain substantially negative and repeatedly contributes to the averaged iterate. It then derives the stated objective-gap bound using convexity, strong convexity, and martingale concentration arguments.

  • Whenever w_{t,1} becomes negative, the gradient forces w_{t+1,1} to become significantly positive, producing the Ω(log(T)/T) behavior.The proof describes this as mimicking a constraint that drives the same behavior as the theorem’s example.
  • Lemma 4 shows that w_{t,1} cannot be significantly below zero or remain below zero for more than one iteration.The lemma applies for t ≥ T_0 = max{2, 6c + 1}.
  • The proof lower-bounds the probability that w_{t,1} lies outside [0, c/t] by 3/4 when w_{t−1,1} ≥ 0.The complementary event is bounded using Z_t’s uniform distribution over [−1, 3].
  • The resulting indicators cannot be zero consecutively, yielding a lower bound proportional to (3c/16) times the harmonic sum.
  • The expected objective gap is bounded below by 3c/(16T).
  • For unbounded W, the argument replaces the initial-iteration bound with a coarse bound on how much w_{t,1} can change.The first T_0 step sizes are bounded, and T_0 is treated as essentially constant.
  • The auxiliary analysis rewrites ∥w_{t+1} − w*∥² explicitly and supplies a loose uniform upper bound.
  • The concentration argument treats Z_i = ⟨ẑ_i, w_i − w*⟩ as martingale differences and applies a martingale bound with probability at least 1 − δ.
Loading 1109.5647v7…