PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Analyses for Non-Smooth Stochastic Gradient Descent

Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa

arXiv:1812.05217v1cs.LGmath.OCstat.ML

TL;DR

The paper asks whether final-iterate SGD achieves tight rates for non-smooth convex optimization, where final-iterate errors are difficult to control. It analyzes projected SGD under stochastic subgradient noise and proves tight high-probability bounds, including optimal suffix-averaging performance. These results resolve the stated open questions about final iterates and show when averaging is necessary.

  • Problem

    The paper addresses whether final-iterate SGD can achieve optimal rates for non-smooth Lipschitz and strongly convex functions, where final-iterate errors need not decrease monotonically.

  • Method

    The paper analyzes projected stochastic gradient descent with noisy subgradient queries, projection onto the feasible set, and problem-dependent step sizes.

  • Results

    The final iterate achieves O(log(T)/T) high-probability error for strongly convex functions and O(log(T)/sqrt(T)) for Lipschitz functions, with matching deterministic lower bounds; suffix averaging achieves tight O(1/T).

  • Takeaways & Limitations

    The log(T) factor is necessary for final iterates, while suffix averaging a constant fraction of iterates achieves the optimal O(1/T) rate in the strongly convex setting.

  • Takeaways & Limitations

    The high-probability analysis controls accumulated martingale noise and avoids the extra log log(T) factor incurred by analyses that control all intermediate times.

Abstract

from arXiv · show

Consider the problem of minimizing functions that are Lipschitz and strongly convex, but not necessarily differentiable. We prove that after $T$ steps of stochastic gradient descent, the error of the final iterate is $O(\log(T)/T)$ with high probability. We also construct a function from this class for which the error of the final iterate of deterministic gradient descent is $Ω(\log(T)/T)$. This shows that the upper bound is tight and that, in this setting, the last iterate of stochastic gradient descent has the same general error rate (with high probability) as deterministic gradient descent. This resolves both open questions posed by Shamir (2012). An intermediate step of our analysis proves that the suffix averaging method achieves error $O(1/T)$ with high probability, which is optimal (for any first-order optimization method). This improves results of Rakhlin (2012) and Hazan and Kale (2014), both of which achieved error $O(1/T)$, but only in expectation, and achieved a high probability error bound of $O(\log \log(T)/T)$, which is suboptimal. We prove analogous results for functions that are Lipschitz and convex, but not necessarily strongly convex or differentiable. After $T$ steps of stochastic gradient descent, the error of the final iterate is $O(\log(T)/\sqrt{T})$ with high probability, and there exists a function for which the error of the final iterate of deterministic gradient descent is $Ω(\log(T)/\sqrt{T})$.

1 Introduction

The paper studies non-smooth convex optimization, where final-iterate errors are difficult to analyze because they need not decrease monotonically. It proves tight high-probability bounds for SGD and shows that averaging is necessary for optimal rates in relevant settings.

  • Non-smooth convex objectives arise in geometric median, minimum s-t cut, and regularized support vector machine problems.
  • The final-iterate error need not decrease monotonically with T, making it difficult to analyze directly.Averaging iterates is a longstanding workaround.
  • O(log(T)/T) expected final-iterate bounds for strongly convex problems were previously known, but their tightness remained open.The question matters because returning the last iterate after T SGD steps is common.
  • The log(T) factor is necessary for Lipschitz and strongly convex functions, even under non-stochastic gradient descent.This establishes tightness of the expected upper bounds due to Shamir and Zhang.
  • Any convex combination of the last k iterates incurs a log(T/k) factor, so optimal suffix averaging must use a constant fraction of the iterates.
  • O(1/T) high-probability error is achieved by suffix averaging, while the final iterate achieves O(log(T)/T) for strongly convex functions.Both bounds are reported as tight; the analogous Lipschitz final-iterate rate is O(log(T)/sqrt(T)).
  • The results connect final-iterate behavior to broader questions about when averaging is required for optimal convergence in iterative methods.

2 Preliminaries

The paper formulates projected SGD for convex minimization using a stochastic subgradient oracle and projection oracle. It specifies normalized assumptions and step sizes while distinguishing final-iterate, uniform-averaging, and suffix-averaging outputs.

  • The optimization problem minimizes a convex function over a closed, convex subset X of R^n using noisy subgradient queries.The oracle returns an unbiased stochastic subgradient conditioned on previous calls.
  • Evaluating the objective accurately can require Θ(T^2) samples, whereas SGD uses only O(T) samples.This motivates obtaining high-probability guarantees from a single execution rather than selecting the best among many trials.
  • The analysis normalizes strong convexity and Lipschitz parameters to 1 and assumes stochastic-gradient noise has norm at most 1 almost surely.The arguments are stated to generalize to sub-Gaussian noise.
  • The algorithm may output the final iterate, an average of all iterates, or an average of a final fraction of iterates.These choices motivate the paper's separate analyses of final and averaged outputs.
  • The standard step sizes are η_t = Θ(1/t) for strongly convex functions and η_t = Θ(1/sqrt(t)) for Lipschitz functions.The analyses use η_t = 1/t for strongly convex functions and η_t = 1/sqrt(t) for Lipschitz functions.
  • Projected SGD updates each iterate by taking a stochastic subgradient step and projecting the result back onto X.The update is y_t+1 ← x_t − η_t ĝ_t before projection.

3 Our Contributions

The paper establishes tight final-iterate error bounds for nonsmooth stochastic gradient descent, including matching deterministic lower bounds and optimal high-probability suffix-averaging guarantees.

  • Strongly convex and Lipschitz functions: O(log(T) log(1/δ)/T) high-probability upper bound holds for the final iterate on strongly convex, Lipschitz functions.The result assumes bounded stochastic-gradient noise and step size η_t = 1/t.
  • Strongly convex and Lipschitz functions: Ω(log(T)/T) lower bound holds even for non-stochastic gradient descent on strongly convex, Lipschitz functions.The lower-bound construction uses a function parameterized by T.
  • Strongly convex and Lipschitz functions: O(log(T) log(1/δ)/T) upper and matching logarithmic lower bounds show that the final-iterate rate is tight up to confidence dependence.The bounded-noise assumption can be relaxed to a sub-Gaussian condition, and linear dependence on log(1/δ) is necessary in the strongly convex case.
  • Lower bounds: Any weighted average of the last k iterates incurs a log(T/k) factor, so suffix averaging needs a constant fraction of iterates to attain O(1/T).This lower bound applies to the strongly convex construction and explains why short suffixes cannot achieve the optimal rate.
  • Convex and Lipschitz functions: The same lower-bound approach constructs a 1-Lipschitz convex function whose final iterate has a logarithmic error penalty.The construction also shows the function value can strictly increase during the first T iterations.
  • High-probability suffix averaging: Theorem 3.7 gives an optimal high-probability bound for averaging the last half of the iterates.The bound improves prior suffix-averaging and EpochGD results that incurred a log log(T) factor in high probability.

4 Techniques

The analysis controls dependent stochastic noise through new martingale tools and iterate-distance bounds, while explaining deterministic lower bounds via repeated nonsmooth turns in high dimensions.

  • Final iterate: High-probability analysis must control a zero-mean martingale whose accumulated noise depends nontrivially on previous iterates.This dependence makes concentration for the final iterate substantially harder than expectation analysis.
  • Final iterate: A generalized Freedman inequality handles martingales whose total conditional variance depends recursively on the martingale itself.This avoids controlling every intermediate iterate and thereby avoids the extra log log(T) factor associated with prior analyses.
  • Final iterate: A new Euclidean-distance bound between SGD iterates supports error comparisons across iterations through the subgradient inequality.The bound is stronger than naive quadratic-in-time estimates in the strongly convex case.
  • Suffix averaging: Suffix averaging requires bounding only the terminal martingale value, rather than controlling the process at every time step.Earlier all-time analyses incurred log log(T), while the paper develops a recursive probabilistic tool for the terminal quantity.
  • Suffix averaging: Recursive moment-generating-function bounds remove the nonlinear dependence and noise term from the relevant recurrence.This produces a cleaner route to the stochastic-process bound used in the analysis.
  • Deterministic lower bound: The deterministic lower bound forces error to increase for Ω(T) consecutive iterations by exploiting nearly orthogonal nonsmooth directions in sufficiently high dimensions.Convexity is preserved while successive gradient steps encounter new nondifferentiable points.

5 Lower bound on error of final iterate, strongly convex case

The section constructs a T-dependent 1-strongly convex, Lipschitz function whose deterministic final iterate has logarithmic-over-T error, establishing the strongly convex lower bound.

  • Function and oracle: Ω(log(T)/T) final-iterate error is attained by a T-dependent function in the strongly convex, Lipschitz class.The construction uses the Euclidean unit ball and a non-stochastic subgradient oracle.
  • Function and oracle: The function’s subgradient at z_t is h_t + z_t, determined by the active affine component at z_t.The active-index structure follows from the triangular shape of the h_i vectors.
  • Iterate construction: The algorithm’s iterates satisfy x_t = z_t for every t ∈ [T + 1].This is proved by induction using the specified subgradient oracle and the update direction.

6 Lower bound on error of final iterate, Lipschitz case

The section gives an analogous T-dependent construction for merely Lipschitz functions, with step sizes proportional to 1/√t and a logarithmic-over-√T final-iterate lower bound.

  • Construction: Ω(log(T)/√T) final-iterate error is achieved by a T-dependent Lipschitz function.The construction is designed to prove the lower bound stated as (3.3).
  • Construction: The function is defined on the Euclidean unit ball and uses positive parameters a_i and b_i together with vectors h_i.The construction ensures the iterates remain in the feasible unit ball.
  • Oracle and iterates: The non-stochastic oracle returns h_i for the minimum active index, and the iterates satisfy x_t = z_t for every t ∈ [T + 1].The equality follows by induction from the explicit iterate construction and the update rule.
  • Lower-bound evaluation: The final-iterate evaluation proves the stated lower bound and also establishes the additional bounds labeled (3.4) and (3.5).The proof concludes after evaluating the constructed trajectory.

7 Upper bound on error of final iterate, strongly convex case

For 1-strongly convex, 1-Lipschitz functions, the proof decomposes final-iterate error into suffix-average and noise terms, then controls the noise with a generalized Freedman inequality.

  • Error decomposition: The last-iterate error is bounded by suffix-average error, noise terms, and an additive O(log T/T) term.The proof therefore separately controls the suffix average and the martingale noise.
  • Noise control: The noise term Z_T is a martingale whose conditional variance depends on a scaled version of Z_T itself.This self-referential variance relation is the paper’s “chicken and egg” difficulty.
  • Noise control: Theorem 3.3 generalizes Freedman’s inequality to disentangle the martingale from its total conditional variance.The resulting tool is applied after deriving high-probability variance bounds.
  • Distance and suffix average: For every t ≥ 2, the squared distance to the optimum is O(log(1/δ)/t) with probability 1 − δ.These recursive-process bounds also support the suffix-average analysis.
  • Distance and suffix average: The suffix-average error is controlled with high probability, completing the proof of the final-iterate upper bound.The suffix-average result follows from the high-probability distance bounds and concentration for the remaining terms.

8 Upper bound on error of final iterate, Lipschitz case: Proof Sketch

In the merely Lipschitz case, the proof follows the same decomposition but replaces strong-convexity arguments with diameter bounds and Azuma’s inequality for the relevant noise component.

  • Proof structure: The Lipschitz-case proof does not require a high-probability bound on ∥x_t − x*∥².This is the main difference highlighted relative to the strongly convex analysis.
  • Proof structure: The last-iterate error is decomposed into suffix-average error, noise terms, and an additive O(log T/√T) term.The suffix-average component is handled by a standard analysis.
  • Noise control: Azuma’s inequality controls the sum of inner products between oracle noise and iterate displacement using a diameter bound.The bound uses ∥ẑ_t∥ ≤ 1 and the resulting bounded increments.
  • Conclusion: Combining the decomposition and high-probability noise bounds completes the proof of the Lipschitz final-iterate result.The proof proceeds through Lemmas 8.2 and 8.3.
  • Noise control: The generalized Freedman inequality again handles the chicken-and-egg relationship between Z_T and its total conditional variance.Distance estimates for SGD iterates provide the variance control needed for this application.

A Standard results

The appendix collects standard probabilistic, geometric, and algebraic tools used in the analysis, alongside proof steps for lower-bound constructions and a limitation on T-independent examples.

  • Concentration tools: Exponentiated Markov converts moment-generating-function bounds into tail bounds.The appendix also develops related MGF inequalities and concentration lemmas.
  • Algebraic tools: The appendix uses Cauchy–Schwarz, Hölder’s inequality, Hoeffding’s lemma, telescoping sums, and logarithmic inequalities as intermediate tools.
  • Geometric tools: Projection onto a convex set does not increase distance to any point in the set.
  • Lower-bound construction: The lower-bound construction verifies the projected iterates through an induction showing that auxiliary and algorithmic sequences coincide.
  • Lower-bound construction: Any convex combination of the last k iterates inherits a lower-bound argument based on coordinate-wise mass in the constructed iterates.
  • T-independent construction: A single T-independent function can achieve a prescribed lower-bound behavior only along infinitely many T, with a log*(T) loss used to preserve Lipschitzness.The construction concatenates scaled hard instances at separated scales.

C Proof of Theorem 3.3 and Corollaries

The proof of Theorem 3.3 establishes a martingale concentration result through exponential supermartingales and applies it to bounds involving conditional variance and martingale differences.

  • Theorem 3.3: Theorem 3.3 bounds a martingale difference sequence under conditional exponential-moment assumptions.
  • Proof strategy: The proof constructs an exponential process and shows that it is a supermartingale.The construction uses a parameter c chosen to satisfy the required quadratic relation.
  • Corollaries: The result handles the chicken-and-egg setting where total conditional variance depends on the martingale itself.
  • Corollaries: The proof splits the target event according to whether the conditional-variance bound holds, then applies Theorem 3.3 on the controlled event.
  • Corollaries: A corollary bounds inner products of bounded mean-zero vectors when the cumulative squared norms of predictable vectors are controlled with high probability.

D Proof of Theorem 4.1

The proof of Theorem 4.1 derives recursive and aggregate MGF bounds for a stochastic recurrence, then converts those bounds into high-probability conclusions.

  • Recurrence setup: The recurrence assumes a nonnegative adapted process with contraction, bounded mean-zero noise, and additive terms.
  • MGF analysis: The proof begins by deriving a recursive MGF bound for the process.
  • MGF analysis: Claim D.2 shows that the process has an MGF bounded by exp(λK) for λ ≤ 1/K.
  • High-probability conclusion: The proof combines per-time MGF bounds using a summation lemma and then applies an MGF-to-tail conversion.

E Omitted proofs from Section 7

The omitted proofs develop bounds for strongly convex Lipschitz SGD, control suffix-averaging terms, and extend normalized results to general Lipschitz and strongly convex parameters by scaling.

  • Suffix averaging: Lemma E.1 provides a cumulative inequality for the normalized strongly convex, Lipschitz setting, which is then used to analyze suffix averages.
  • Strongly convex analysis: Strong convexity supplies a quadratic lower bound relating function error to squared distance from the minimizer.
  • Normalized setting: The analysis uses step sizes η_t = 1/t and the uniform gradient bound ∥ĝ_t∥^2 ≤ 4 in the normalized setting.
  • Suffix averaging: The proof bounds the suffix-averaging error by decomposing it into terms and controlling their coefficients and squared-norm contributions.
  • Scaling assumptions: General α-strongly convex and L-Lipschitz functions are reduced to the normalized case through a scaled function and a coupling of SGD executions.
  • Scaling assumptions: The reduction transfers the normalized high-probability theorems to the original parameterized setting.

F.2 Sub-Gaussian Noise

The analysis extends the framework to conditionally sub-Gaussian stochastic subgradients and establishes a high-probability lower bound for the last iterate and suffix average.

  • F.2 Sub-Gaussian Noise: Sub-Gaussian oracle noise replaces the almost-sure bound ∥ˆzt∥≤1, requiring moment-generating-function control for terms previously bounded deterministically.The resulting analysis introduces additional MGFs and retains more random terms in the bounds.
  • F.2 Sub-Gaussian Noise: Ω(log(1/δ)/T) error holds for both the last iterate and suffix average with probability at least δ.This lower bound is stated for the sub-Gaussian-noise extension.
  • F.2 Sub-Gaussian Noise: If T ≥ O(log(1/δ)), then f(x_T+1) ≥ Ω(log(1/δ)/T) with probability at least δ under the specified one-dimensional strongly convex, Lipschitz setup.The setup uses independent random ±1 oracle outputs, step sizes η_t = 1/t, and initial point x_1 = 0.
  • F.2 Sub-Gaussian Noise: The proof tracks the iterates through the random-sign oracle sequence and projection dynamics before deriving the stated lower bound.The recursion begins with y_2 = ˆz_1 and x_2 = y_2 because the first update remains in the domain.
Loading 1812.05217v1…