Source-linked AI summary
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
Simon Lacoste-Julien, Mark Schmidt, Francis Bach
TL;DR
The note addresses convergence analysis for the projected stochastic subgradient method when only unbiased subgradient estimates are available. It introduces a weighted averaging scheme that assigns weight t+1 to iterate w_t, obtaining an O(1/t) rate with a simple proof and implementation. The scheme shows similar empirical performance behavior to existing techniques.
Problem
Projected stochastic subgradient methods require analysis when optimization uses only unbiased subgradient estimates for strongly convex objectives.
Method
The paper introduces weighted averaging that assigns weight t+1 to iterate w_t and analyzes it by summing t-weighted inequalities to obtain a telescoping sum.
Results
O(1/t) rate is obtained for the proposed averaging scheme, while schemes 0 and 1 have O((log t)/t) and schemes 0.5, D, W, and W2 have O(1/t) rates.
Takeaways & Limitations
The proposed scheme is simpler to implement and analyze while exhibiting similar empirical performance behavior to existing techniques.
Takeaways & Limitations
The analysis assumes an increasing filtration and conditionally unbiased subgradient estimates whose conditional expectation is a subgradient at the previous iterate.
Abstract
from arXiv · showhide
In this note, we present a new averaging technique for the projected stochastic subgradient method. By using a weighted average with a weight of t+1 for each iterate w_t at iteration t, we obtain the convergence rate of O(1/t) with both an easy proof and an easy implementation. The new scheme is compared empirically to existing techniques, with similar performance behavior.
1 Introduction
The note studies projected stochastic subgradient optimization for a strongly convex function over a convex set, assuming only unbiased subgradient estimates. The objective has a unique minimizer on the feasible set.
- 1 Introduction: The problem is a strongly convex function f defined on a convex set K.The strong convexity constant is denoted by µ.
- 1 Introduction: The projected stochastic subgradient method operates when only unbiased estimates of f's subgradients are available.The conditional expectation of each estimate is almost surely a subgradient at the previous iterate.
- 1 Introduction: The stochastic process is modeled with an increasing sequence of σ-fields, with w0 ∈ K measurable with respect to F0.This filtration structures the information available at each iteration.
- 1 Introduction: The function has a unique minimizer w∗ on K.
2 Motivating example
The motivating application is an SVM and structured-prediction setting with i.i.d. data and a strongly convex regularized expected loss. The setup supports both unconstrained and compact-constrained projected variants under moment and Lipschitz-type assumptions.
- 2 Motivating example: The main motivating example is SVM optimization and its structured-prediction extensions.The data pairs (x_t, y_t) are assumed independent and identically distributed.
- 2 Motivating example: The objective combines an expected convex loss with quadratic regularization, f(w) = Eℓ(y, w⊤x) + µ/2∥w∥^2.The loss is Lipschitz-continuous and convex in its second variable.
- 2 Motivating example: In the unconstrained setup, K is the whole space and the stochastic subgradient is ℓ′(y_t, w_{t−1}⊤x_t)x_t + µw_{t−1}.Here ℓ′ denotes any subgradient with respect to the loss's second variable.
- 2 Motivating example: If E∥x∥^2 is finite, the unconstrained SVM setup satisfies the stated subgradient-moment assumptions.The resulting bound is expressed using the loss Lipschitz constant and E∥x∥^2.
- 2 Motivating example: A compact convex K provides an alternative projected SVM setting.
3 Convergence analysis
The analysis derives a classical logarithmic-rate bound and then obtains an O(1/T) rate by weighting iterate inequalities and averaging iterates with weights proportional to t+1.
- Classical analysis: Orthogonal projections contract distances, providing the first inequality in the stochastic subgradient convergence analysis.The proof bounds the projected iterate's distance to the optimum by the distance before projection.
- Classical analysis: µ-strong convexity of f supplies the final inequality used to rearrange function-value terms.Expectations are then taken to derive a bound involving function suboptimality.
- Classical analysis: 2µT (1 + log T) appears in the classical summed bound, reflecting the logarithmic factor in the convergence rate.The derivation uses convexity and a telescoping sum.
- New analysis: The proposed analysis sets γ_t = 2/[µ(t + 1)] and multiplies inequality (2) by t before summing.This t-weighting keeps the term involving B^2 constant across the sum.
- New analysis: Weighting iterates by t+1 changes the rate from O(log T/T) to O(1/T).The resulting weighted average is efficiently implementable online.
- Empirical comparison: Figure 1 compares optimization strategies across six datasets, with the objective function plotted against effective passes through the data.The datasets are quantum, protein, sido, rcv1, covertype, and news.
4 Experiments
Experiments on benchmark binary-classification datasets compare six averaging strategies. The proposed t+1 weighting typically performed between the doubling trick and no averaging, while quadratic weighting consistently outperformed linear weighting.
- Experimental setup: Experiments evaluated six averaging strategies on freely available benchmark binary-classification datasets, without projection.The datasets included quantum, protein, sido, rcv1, covertype, and news; regularization was set to λ = 1/n.
- Evaluation: The objective function was plotted against effective passes through the data, using step size 1/µt for all methods.The authors report that this step size performed better than 2/µ(t + 1), while the latter was included for comparison with W.
- Results: Uniform averaging of all iterates was always the worst strategy, whereas second-half uniform averaging was typically among the best when the iterates were actually in their second half.The second-half method’s performance depended on reaching the second half of the iteration sequence.
- Results: The doubling trick typically gave among the best performance across methods, while the proposed weighting typically performed between it and no averaging.No averaging was typically among the worst strategies, except on the sido dataset, where it performed best after 50 passes.
- Results: (t + 1)^2 weighting always outperformed t + 1 weighting.This comparison concerns the two weighted-averaging strategies tested in the experiments.
5 Discussion
The discussion positions the proposed averaging method as a simpler way to obtain O(1/t) convergence for the non-smooth case. It relates the method to prior averaging schemes and distinguishes the proven rates and constants across weighting choices.
- Relation to prior work: The discussion notes that weighting by t + 1 also appears in Nesterov’s deterministic method, which achieves O(1/t^2) for objectives with Lipschitz-continuous gradients.This comparison concerns a different, deterministic smooth optimization setting.
- Relation to prior work: The proposed approach is described as somewhat simpler to implement and analyze than previous approaches for removing the log t term.Earlier approaches include 1/2-suffix averaging, the doubling trick, and epoch-GD.
- Convergence rates: Schemes 0 and 1 have O((log t)/t) rates, whereas schemes 0.5, D, W, and W2 have O(1/t) rates.The discussion states that all schemes presented in the experiments can have their convergence rate proven.
- Convergence rates: General weights t^k for k ≥ 1 and step sizes γ_t = c/(t + b), with c > 1/2 and b ≥ 0, also yield O(1/t), but with constants depending on c and k.The proof is longer because the telescoping sum no longer cancels completely.
- Relation to prior work: Shamir and Zhang independently proposed a related polynomial-decay averaging scheme with ρ_t = (1 + η)/(t + 1 + η), where η ≥ 0 indexes the schemes.Their result gives O(1/t) for η ≥ 2, while the proof here is described as complementary and simpler, with a tighter constant.
- Scope and open question: The note focuses on the non-smooth case and raises whether larger step sizes can improve results there, unlike the cited smooth strongly convex setting.In the smooth strongly convex case, step sizes of the form t^-α with α ∈ (1/2, 1) are reported to give better and more robust rates.
A Finite variance bound for SVM
For the SVM-like objective, the appendix establishes a finite second-moment bound for stochastic subgradients under an expected Lipschitz-like assumption. It uses the regularized subgradient update and induction under step-size and initialization conditions.
- Assumptions: The SVM setting uses z = (x, y), h(z, w) = ℓ(y, w⊤x), and assumes E∥h′(z, w)∥^2 ≤ L^2.Here h′(z, w) denotes any subgradient with respect to the second variable.
- Stochastic gradient construction: With g_t = h′(z_t, w_{t−1}) + µw_{t−1}, the conditional expectation satisfies E(g_t | w_{t−1}) = f′(w_{t−1}).This verifies the stochastic-subgradient condition used by the setup.
- Proof technique: Minkowski’s inequality is applied to control the norm terms in the finite-variance argument.The appendix applies it both in bounding g_t and in the induction for the iterates.
- Finite variance bound: The appendix obtains the required bound (2L)^2 on E∥g_t∥^2 by proving E∥w_{t−1}∥^2 ≤ L/µ.The iterate bound is established by induction.
- Inductive argument: The induction uses the update w_t = (1 − µγ_t)w_{t−1} − γ_t h′(z_t, w_{t−1}).The update follows from applying the subgradient method to the regularized SVM-like objective.
- Inductive argument: The proof assumes γ_t ≤ 1/µ and either γ_1 = 1/µ or E∥w_0∥^2 ≤ L/µ.The step-size condition ensures 1 − µγ_t is nonnegative, and the assumptions provide the induction base case.