Stochastic dual coordinate ascent methods for regularized loss

By Shai Shalev-Shwartz, Tong Zhang. 2012

1,080 citations recorded by the source corpus.

Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. This paper presents a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications.

Subfields: Artificial Intelligence, 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 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 .”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, neutral): “[27] Shai Shalev-Shwartz and Tong Zhang.”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “At each step t , sample i with probability p ti proportional to the individual Fenchel duality gap: Deﬁne the non-uniformity of the duality gaps as the ratio between their quadratic mean and their arithmetic mean: Take χ a lower bound on these non-uniformity over all trajectories, for all time steps”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, background): “It is a surprising recent finding [11, 5, 9, 6] that the finite sum structure of f allows for significantly faster convergence in expectation.”
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “The Stochastic Dual Coordinate Descent (SDCA) [2] method on the surface appears quite different from the other methods considered.”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “nchel-Rockafellar dual of (7.9) when F^ i() = 2()2 for all i2f1;:::;dgis given by F dual(v) = 1 n Xn j=1 F~? j( v j) 2 2 1 n Xn j=1 v jx j 2 : The stochastic dual coordinate ascent (SDCA) method [145] applied to a function of this form has an iteration similar to (7.6), except that negative gradie”
Federated Learning: Collaborative Machine Learning without Centralized Training Data (2022, neutral): “Another possibility is applying RCD to the dual problem of (1), which is called stochastic dual coordinate descent [26].”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “…et al. (2018) propose a multi-task learning framework for federated learning and its related optimization algorithm, which extends early works SDCA (Shalev-Shwartz and Zhang, 2013; Yang, 2013; Yang et al., 2013) and CO-COA (Jaggi et al., 2014; Ma et al., 2015; Smith et al., 2016) to the federated…”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “These works reduce communication overhead by proposing algorithm-speciﬁc approaches, such as solving a dual problem (Shalev-Shwartz & Zhang, 2013; Takác et al., 2013; Jaggi et al., 2014) or employing a different optimization algorithm (Rakhlin et al., 2012; Zhang & Lin, 2015).”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “For non-smooth losses such as SVMs, the analysis of Shalev-Shwartz and Zhang (2013a) provides a O (1 /t ) rate, and for smooth losses, a faster linear rate.”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “While one could use any of recent fast algorithms for ﬁnite sums [17, 4, 19, 3] with comparable results, we highlight the consequences of applying the S VRG algorithm [6, 8] as a local solver in I NEXACT D ANE .”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “This implies that the population suboptimality Zhang et al. (2013) argued that the dependence on the sample size mn above is essentially optimal: the dominant term (as n → ∞ , and in particular when n m ) scales as 1 / ( nm ) , which is the same as for the empirical minimizer ˆ w (as in eq.”
Distributed Coordinate Descent Method for Learning with Big Data (2013, background): “Methods of this type, in various settings, were studied by several authors, including Hsieh et al. (2008); Shalev-Shwartz & Tewari (2009); Nesterov (2012); Richtárik & Takáč (2012c); Necoara et al. (2012); Tappenden et al. (2013b); Shalev-Shwartz & Zhang (2013b); Lu & Xiao (2013).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The work [88] was ﬁrst to show that by applying RCD [79] to the dual problem, one also solves the primal problem (1).”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “Modern large-scale machine learning applications require scaling stochastic optimization algorithms [30, 28, 15, 11] to distributed computational architectures [10, 39, 12, 20, 19, 38] or multicore systems [26, 9, 22, 25].”
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)).”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “Using the setup of [13], we assume the regularizer is the `2-norm for convenience.”