A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method

By Simon Lacoste-Julien, Mark W. Schmidt, Francis R. Bach. 2012

277 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Numerical Analysis, Optimization & Training, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

In Signal Processing

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “The ‘doubling trick’ uniformly averages all iterates since the last iteration which was a power of 2, and was described by Rakhlin et al. (2012), with experiments for SSG in Lacoste-Julien et al. (2012).”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “It is important to note that in analyses based on the bounded gradient assumption—which was traditionally assumend for analyzing SGD (Lacoste-Julien et al., 2012; Rakhlin et al., 2012)—the diversity in the data distribution on each worker sometimes can be hidden in this generous upper bound and the ”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “It is well-known that an individual run of SGD on a single machine converges as O ( (THBloc) −1), see e.g. (Lacoste-Julien et al., 2012).”
Local SGD Converges Fast and Communicates Little (2018, methodology): “Similar as in [15, 28, 34] we define a suitable averaging scheme for the iterates {x̄t}t≥0 to get the optimal convergence rate.”
Dynamic Model Pruning with Feedback (2020, neutral): “Here we follow Lacoste-Julien et al. (2012) for the general structure, combined with estimates from the error-feedback framework (Stich et al.”
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2012, methodology): “Also, we made no effort to optimize the constants, which can be easily improved for specific choices of η (see the proof as well as the analysis in Lacoste-Julien et al. (2012)).”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, methodology): “We approximate it by the outcome of the subgradient method run for M steps, with a step-size proportional to 2/(m + 2) as suggested in [23].”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, background): “This choice is inspired by the stepsize rule of Lacoste-Julien et al. (2012) for stochastic gradient descent.”
Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions (2018, methodology): “We first apply the projected stochastic subgradient method [12] for T iterations yielding the estimate R := 4(L 2+μ2D2) μ(T+1) = 2D(4L 2+ε2) ε(T+1) .”
Optimal Black-Box Reductions Between Optimization Objectives (2016, background): “Our new reductions also enable researchers to prove lower bounds more broadly [30].”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “Dekel et al. (2012); Lacoste-Julien et al. (2012); Rakhlin et al. (2012); Ghadimi and Lan (2012, 2013b); Hazan and Kale (2014); Bubeck (2014); Dieuleveut et al. (2016) use iterate averaged SGD to achieve minimax rates for various problem classes non-asymptotically.”
Smart "Predict, then Optimize" (2017, background): “In inventory planning problems such as the economic lot sizing problem (Wagner and Whitin (1958)) or the joint replenishment problem (Levi et al. (2006)), the demand is the key input into the optimization model. In practical settings, demand is highly nonstationary and can depend on historical and c”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “We approximate it by the outcome of the subgradient method run for M steps, with a step-size proportional to 2 / ( m + 2) as suggested by Lacoste-Julien et al. (2012).”
Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing (2015, unknown): “Op1{T q-like rate (Shamir, 2011; Lacoste-Julien et al., 2012; Chen et al., 2012).”
Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity (2017, methodology): “der solving this problem via a(potentially stochastic) projected subgradient method. These methods have received much attention lately due to their simplicity and scalability; see [2, 13], as well as [7, 8, 9, 12, 14] for a sample of more recent works. ∗bdg79@cornell.edu; Cornell University, Ithaca ”