Proximal Stochastic Dual Coordinate Ascent

By Shai Shalev-Shwartz, Tong Zhang. 2012

109 citations recorded by the source corpus.

We introduce a proximal version of dual coordinate ascent method. We demonstrate how the derived algorithmic framework can be used for numerous regularized loss minimization problems, including $\ell_1$ regularization and structured output SVM. The convergence rates we obtain match, and sometimes improve, state-of-the-art results.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Mathematical Optimization

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 Management Science and Operations Research

In Mathematical Optimization

Citations in the corpus

A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “The Prox-SVRG method enjoys the same low complexity as that of SDCA [SSZ13, SSZ12] and SAG [RSB12, SRB13], but applies to a more general class of problems, and does not require the storage of the most recent gradient for each component function.”
A Universal Catalyst for First-Order Optimization (2015, methodology): “The resulting algorithm can be interpreted as a variant of proximal SDCA [25] with a different step size and a more practical optimality certificate—that is, checking the optimality condition does not require evaluating a dual objective.”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “Speciﬁcally, this paper focues on importance sampling techniques for Proximal Stochastic Gradient Descent (prox-SGD) [4] and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA) [13].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “The method SDCA [51] for strongly convex composite optimization is a dual coordinate ascent algorithm that performs incremental updates in the primal (1.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “The convergence rate of SGD can be further improved with the so-called variance-reduction technique [9, 11, 17, 24, 25, 31, 32, 35, 36].”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “This paper replaces and improves an earlier arxiv version [25].”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, neutral): “…YES × × 1st general proximal Bradley et al, 2012 [2] 1 YES × 1 -regularized parallel Richt´arik & Tak´aˇc, 2012 [16] YES YES × 1st general parallel S-Shwartz & Zhang, 2012 [19] YES × × 1st primal-dual Necoara et al, 2012 [9] × × × 2-coordinate descent Tak´aˇc et al, 2013 [21] × YES × 1st primal-d.”
Distributed block-diagonal approximation methods for regularized empirical risk minimization (2017, methodology): “The analysis in Yang (2013) then shows that the primal iterates {wt } obtained by substituting the dual iterates {αt } into (5) converges linearly to the optimum when all ξi have Lipschitz continuous gradient and converges with a rate of O(1/ ) when all ξi are Lipschitz continuous by using some proo”
Optimal Black-Box Reductions Between Optimization Objectives (2016, methodology): “We apply AdaptReg to reduce it to Case 1 and apply either APCG [20], an accelerated method, or (Prox-)SDCA [29, 30], a non-accelerated method.”
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives (2015, methodology): “Although many variance-reduction based methods have been proposed, most of them, including SVRG, only has convergence guarantee of problem (1.1) when the objective F ( x ) is strongly convex [3, 10, 21, 22, 26].”
Distributed Optimization for Non-Strongly Convex Regularizers (2016, methodology): “Previous work on SDCA has already, in part, dealt with the problem of applying SDCA to more general settings, both in term of distribution and generalization to different regularizers; in particular two methods have been studied that tried to bridge the gap with gradient descent methods: • ProxSDCA:”
On optimal probabilities in stochastic coordinate descent methods (2013, methodology): “Serial stochastic coordinate descent methods were proposed and analyzed in [6, 13, 15, 18], and more recently in various settings in [12, 7, 8, 9, 21, 19, 24, 3].”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, methodology): “…virtually all existing methods use sampling uniformly at random [Hsieh et al., 2008, Shalev-Shwartz and Tewari, 2011, Lacoste-Julien et al., 2013, Shalev-Shwartz and Zhang, 2012], recently [Nesterov, 2012, Qu and Richt´arik, 2016, Zhao and Zhang, 2014, Allen-Zhu et al., 2016] showed that an…”
Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity (2014, background): “To the best of our knowledge, this is the first work that establishest linear convergence rate for the variance-reduced stochastic gradient algorithms on solving both constrained and regularized problems without strong convexity.”
Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice (2017, methodology): “For other methods that admit a linear convergence rates in terms of duality gap, such as SDCA, MISO/Finito, Catalyst can also be applied as explained in Appendix C. Stopping criteria.”
Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon more (2019, unknown): “• miso : the MISO algorithm of Mairal [2015], which may be seen as a primal variant of SDCA [Shalev-Shwartz and Zhang, 2012]; • catalyst-miso : its accelerated variant, by using the Catalyst approach of Lin et al. [2018]; • qning-miso : its Quasi-Newton variant, by using the QNing approach of Lin et”
Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters (2016, methodology): “Recently, variance-reduction methods were introduced to improve the running time of SGD [6, 7, 13, 19, 22, 23, 25, 27], and accelerated gradient methods were introduced to further improve the running time when the regularization parameter is small [9, 17, 18, 26, 30].”