Source-linked AI summary
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
Ohad Shamir, Tong Zhang
TL;DR
Classical SGD guarantees often assume smooth objectives, leaving non-smooth applications such as support-vector machines insufficiently covered. This paper proves finite-sample last-iterate bounds without smoothness and develops averaging schemes that attain optimal rates, including a simple on-the-fly alternative to suffix averaging.
Problem
Classical non-asymptotic SGD analyses often require smoothness assumptions that fail for non-smooth objectives such as SVM hinge-loss optimization.
Method
The paper analyzes individual SGD iterates and suffix averaging, and introduces polynomial-decay averaging as a simple running scheme computable on-the-fly.
Results
O(log(T)/T) strongly-convex and O(log(T)/√T) general-convex expected optimization-error bounds hold for the last iterate without smoothness assumptions, while suffix and polynomial-decay averaging attain optimal rates.
Takeaways & Limitations
Last-iterate SGD performance is provably close to optimal averaging rates, and polynomial-decay averaging offers an equally rate-optimal scheme that is easy to compute online.
Takeaways & Limitations
Suffix averaging requires knowing the stopping time in advance or storing all iterates, limiting its use when termination is determined empirically.
Abstract
from arXiv · showhide
Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth objective functions such as support vector machines. In this paper, we investigate the performance of SGD without such smoothness assumptions, as well as a running average scheme to convert the SGD iterates to a solution with optimal optimization accuracy. In this framework, we prove that after T rounds, the suboptimality of the last SGD iterate scales as O(log(T)/\sqrt{T}) for non-smooth convex objective functions, and O(log(T)/T) in the non-smooth strongly convex case. To the best of our knowledge, these are the first bounds of this kind, and almost match the minimax-optimal rates obtainable by appropriate averaging schemes. We also propose a new and simple averaging scheme, which not only attains optimal rates, but can also be easily computed on-the-fly (in contrast, the suffix averaging scheme proposed in Rakhlin et al. (2011) is not as simple to implement). Finally, we provide some experimental illustrations.
1 Introduction
The paper studies SGD for non-smooth convex optimization, addressing gaps in finite-sample guarantees for individual iterates and practical averaging. It establishes new last-iterate bounds and introduces an on-the-fly averaging scheme with optimal convergence rates.
- Motivation: Non-smooth objectives such as SVM hinge-loss problems fall outside classical smoothness-based SGD analyses.Existing non-smooth analyses mainly concern online learning and averaged iterates.
- Open issues: Prior results left unclear whether the last iterate wT has useful finite-sample guarantees, especially for general convex functions.They also focused on averaging substantial portions of the trajectory rather than only recent iterates.
- Contributions: O(log(T)/T) strongly-convex and O(log(T)/√T) general-convex expected optimization-error bounds hold for every individual iterate wT without smoothness assumptions.The general-convex result is presented as the first finite-sample individual-iterate bound for non-smooth convex SGD, to the authors’ knowledge.
- Contributions: The analysis improves the expected suffix-averaging error bound from O((1 + log(1/(1−α)))/(αT)) to O(log(1/min{α,1−α})/T).Suffix averaging averages the last αT iterates.
- Contributions: Polynomial-decay averaging achieves optimal convergence rates while remaining simple to compute on-the-fly, unlike suffix averaging.The paper also includes a simple experimental study of the discussed averaging schemes.
2 Preliminaries
The paper analyzes first-order stochastic optimization for convex and strongly convex functions over a convex domain. Its guarantees use unbiased stochastic subgradients, bounded stochastic-gradient second moments, bounded domain diameter for general convex objectives, and a standard strongly-convex step size.
- Problem setting: F is convex on a closed convex domain W, has a minimizer w*, and may additionally be λ-strongly convex for λ > 0.General convexity corresponds to setting λ = 0 in the strong-convexity inequality.
- Stochastic oracle: The stochastic oracle returns a random vector ĝ with E[ĝ] ∈ ∂F(w), and the goal is to minimize F(w̄) − F(w*) using at most T oracle calls.The framework applies to learning problems with sampled examples.
- Step size: ηt = 1/(λt) is the standard strongly-convex step-size assumption used for the analysis.A step size c/(λt) with c ≥ 1 can be handled through a lower strong-convexity parameter λ′ = λ/c.
- Boundedness assumptions: The analysis assumes E[||ĝt||^2] ≤ G^2 and, for general convex objectives, a bounded domain diameter supw,w′∈W ||w − w′|| ≤ D.These conditions control stochastic-gradient magnitude and the feasible-set geometry.
3 Convergence of Individual SGD Iterates
The paper proves individual-iterate convergence bounds for non-smooth SGD by comparing later iterates with earlier ones rather than only with the optimizer. The resulting bounds support both strongly convex and general convex objectives under stated step-size and boundedness assumptions.
- Proof technique: The analysis replaces the standard comparator w* with the earlier iterate wT−k, which enables bounds on individual later iterates.This comparison is the proof’s crucial trick for deriving individual-iterate guarantees.
- Proof technique: The proof recursively relates expected function values of later iterates to averages over suffixes of the trajectory.It defines suffix averages and repeatedly sums the resulting inequalities before applying bounds on the remaining terms.
- Strongly convex case: The strongly convex proof controls the target iterate by analyzing the expected average of the last k + 1 iterates and bounding the resulting harmonic terms.The argument invokes an existing suffix-average bound and uses a logarithmic upper bound on the harmonic sum.
- General convex case: For general convex non-smooth objectives, a similar technique yields an individual-iterate bound under bounded domain and expected subgradient-norm assumptions.The result uses step sizes ηt = c/t with c > 0, together with diameter and gradient bounds.
4 Averaging Schemes
The section compares averaging schemes for SGD, showing that suffix averaging achieves optimal rates while polynomial-decay averaging combines optimal convergence with on-the-fly computation. It also establishes logarithmic-rate guarantees for individual iterates.
- Individual iterates: O(log(T)/T) expected error holds for individual iterates in the strongly-convex case, while the general convex case has the corresponding O(log(T)/√T) rate.These bounds require no smoothness assumptions and concern the last iterate rather than an averaged output.
- Averaging schemes: Simple averaging is already optimal up to constants for general convex functions, whereas strongly-convex problems require more targeted averaging schemes.The section therefore focuses mainly on strongly-convex averaging schemes.
- Suffix averaging: α-suffix averaging improves the prior bound to O(log(1/min{α,1−α})/T), while retaining optimal dependence on T.The improvement makes choosing α more flexible than under the earlier bound.
- Suffix averaging: General convex α-suffix averaging admits an upper bound of order log(1/α)/T, improving on existing techniques that imply order 1/(αT).The analysis is stated for α-suffix averaging, with αT assumed integral in the theorem setup.
- Practical considerations: Suffix averaging requires storing iterates or knowing the stopping time in advance, limiting flexibility when termination is determined empirically.Polynomial-decay averaging is presented as avoiding this implementation constraint.
- Polynomial-decay averaging: Polynomial-decay averaging weights later iterates more heavily, achieves optimal rates up to constants, and remains computable on-the-fly.The parameter η controls the decay; η = 0 recovers standard averaging, while η > 0 reduces earlier iterates’ weights.
5 Experiments
The experiments evaluate polynomial-decay averaging on three binary classification datasets using an SVM objective and compare it with suffix and simple averaging. Polynomial-decay averaging performs best or nearly best across all cases, while simple averaging is significantly worse.
- Experimental setup: Three binary classification datasets were evaluated with SGD on a support vector machine optimization problem.The datasets were ccat, cov1, and astro-ph.
- Experimental setup: The comparison included polynomial-decay averaging with η = 3, suffix averaging with α = 1/2, and simple averaging of all iterates.Each method was evaluated using the same experimental setup across the datasets.
- Experimental setup: The plots show training error over 10 repetitions as a function of iteration count on log-log axes.Test-set results were omitted because they were very similar to the training results.
- Results: Polynomial-decay averaging achieved the best or almost-best performance in all cases, while suffix averaging performed similarly.The observed comparison supports the method’s practical performance across the evaluated datasets.
- Results: Simple averaging of all iterates was significantly suboptimal compared with polynomial-decay and suffix averaging.This matched the earlier reported behavior of simple averaging.
6 Discussion
The discussion highlights polynomial-decay averaging and new finite-sample iterate bounds as central contributions, while identifying unresolved questions about last-iterate tightness and variability.
- Polynomial-decay averaging is as simple to compute as standard averaging while achieving better theoretical and practical performance.
- New finite-sample bounds cover individual SGD iterates for convex and strongly convex problems without smoothness assumptions.
- The techniques may extend beyond standard gradient descent to mirror descent and non-Euclidean norms.
- The tightness of the O(log(T)/T) last-iterate rate for strongly convex problems remains open.
- High-probability individual-iterate bounds, especially in the strongly convex case, remain another open question because last iterates may exhibit high variability.
ASTRO
This passage set consists primarily of bibliographic entries spanning stochastic approximation, stochastic optimization, online convex programming, and stochastic subgradient methods.
- The references include a foundational book on stochastic approximation and recursive algorithms.
- The bibliography includes work on projected stochastic subgradient descent and smoothing for nonsmooth minimization.
- Several cited works address stochastic convex optimization and strongly convex stochastic optimization.
- Other entries concern support-vector-machine optimization, online convex programming, and the question of whether averaging is needed.