Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization

By Shai Shalev-Shwartz, Tong Zhang. 2013

473 citations recorded by the source corpus.

We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, methodology): “Thus we obtain ϕ k : Ω k → H k , and for any Algorithm 2 describes this variant of SDCA, biasing the sampling towards examples with large duality gaps g .”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “The algorithm with the surprising name of Proximal-SDCA 2 , option II (Shalev-Shwartz and Zhang, 2016) proposes a solution to this problem.”
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “2 As noted by Shalev-Shwartz & Zhang [11], the update (9) is actually an instance of the proximal operator of the convex conjugate of f j .”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “Further, in subsequent work they obtain a convergence rate in the convex case by adding an explicit strongly-convex regularizer to the problem [Shalev-Schwartz and Zhang, 2014].”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “The proposed technique is a signiﬁcant improvement over simple smoothing techniques used in, e.g., Nesterov (2005); Shalev-Shwartz and Zhang (2014); and Zhang and Lin (2015) that enforce strong convexity by adding a small L 2 term to the objective.”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “…& Tak´aˇc, 2014; 2013b; 2012; Tappenden et al., 2015; Mareˇcek et al., 2014; Fercoq & Richt´arik, 2013; Lu & Xiao, 2013; Fercoq et al., 2014; Qu & Richt´arik, 2014; Qu et al., 2014) (Efﬁcient accelerated variants were considered in (Fercoq & Richt´arik, 2013; Shalev-Shwartz & Zhang, 2013a)).”
Distributed optimization with arbitrary local solvers (2015, background): “It is implicitly chosen by the number of iterations or stopping criterion speciﬁed by the user for the local solver.”
A Universal Catalyst for First-Order Optimization (2015, methodology): “Specifically, we use the concept of estimate sequence from Nesterov [17], whereas the direct proof of [26], in the context of SDCA, does not extend to non-strongly convex objectives.”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, methodology): “Accelerated SDCA [17] achieves a similar complexity using gradient and prox oracle access.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “Examples: P For all of the four ERM cases above, accelerated stochastic methods were introduced in the literature, most notably AccSDCA [33], APCG [22], SPDC [38].”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, background): “We also mention some recent progress in accelerated stochastic coordinate gradient methods [43, 27, 53], which can be more efficient both in theory and practice.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “1 lists several common loss functions together with their convex conjugates `i [164].”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, neutral): “An alternative algorithm is accelerated SDCA [24].”
Semi-stochastic coordinate descent (2014, neutral): “Accelerated [18] and mini-batch [21] variants of SDCA have also been proposed.”
Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms (2015, neutral): “e at larger times. Although there have been some convergence results of the SGA algorithms and theirvariants (Shamir and Zhang,2012; Moulines and Bach, 2011;Needell et al.,2014; Xiao and Zhang, 2014; Shalev-Shwartz and Zhang, 2014; Bach and Moulines, 2013), less is known about their dynamics. For ex”
On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization (2018, methodology): “These methods have been improved using accelerated variants (Shalev-Shwartz and Zhang, 2014; Frostig et al., 2015a; Lin et al., 2015; Defazio, 2016; Allen-Zhu, 2016).”
Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters (2016, methodology): “Comparing to the complexity of APCG, ACDM, or AccSDCA (see (1.1)), ClusterACDM is faster by a factor that is up to Ω ( min{ √ n/s, √ 1/δ} ) .”