Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

By Shai Shalev-Shwartz, Tong Zhang. 2013

154 citations recorded by the source corpus.

Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is often used in practice. Our main contribution is to introduce an accelerated mini-batch version of SDCA and prove a fast convergence rate for this method. We discuss an implementation of our method over a parallel computing system, and compare the results to both the vanilla stochastic dual coordinate ascent and to the accelerated deterministic gradient descent method of Nesterov [2007].

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training, Algorithms & Complexity

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 Statistics and Probability

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Fair Resource Allocation in Federated Learning (2019, background): “…learning faces challenges such as expensive communication, systems heterogeneity (e.g., variability in hardware or network connection) and statistical heterogeneity (i.e., diﬀering local data distributions per device), making it distinct from classical distributed optimization [32, 35, 39].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Mini-batch optimization methods, which involve extending classical stochastic methods to process multiple data points at a time, have emerged as a popular paradigm for distributed machine learning in data center environments [28, 88, 96, 102, 103].”
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.”
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); Richt´arik & Tak´aˇc (2012c); Necoara et al. (2012); Tappenden et al. (2013b); Shalev-Shwartz & Zhang (2013b); Lu & Xiao (2013).”
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)).”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “. These two distributions are quite diﬀerent. In addition, we also provide an importance sampling distribution when the individual loss functions are Lipschitz. We also noticed that a mini-batch SDCA [24] and an accelerated version of prox-SDCA [25] were studied recently by Shalev-Shwartz and Zhang.”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, methodology): “Proximal [28] and accelerated VR methods have also been proposed [19, 25]; we leave a study of such variants of our framework as future work.”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “In ord e to enable parallelism, the idea of mini-batching—using estim a ing the gradient using multiple random i in each iteration—is often employed [21], [22], [23], [24], [18], [25].”
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization (2015, methodology): “Shalev-Shwartz & Zhang (2013b) studied minibatching but in conjunction with acceleration and the QUARTZ method of Qu et al. (2014), which has been analyzed for an arbitrary sampling Ŝ, uses a different primal update than SDNA.”
Accelerating Stochastic Gradient Descent (2017, result): “Acceleration and Finite Sums: As a final remark, there have been results (Shalev-Shwartz and Zhang, 2013; Frostig et al., 2015a; Lin et al., 2015; Allen-Zhu, 2016) that provide accelerated rates for offline stochastic optimization which deal with minimizing sums of convex functions; these results ar”
Stochastic Dual Coordinate Ascent with Alternating Direction Method of Multipliers (2014, methodology): “A mini-batch extension of SDCA is a recent hot topic (Takáč et al., 2013; Shalev-Shwartz and Zhang, 2013b).”
Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses (2015, methodology): “The methods that belong to this category include SAG [2], SDCA [3], SVRG [4], S2GD [5], mS2GD [6], SAGA [7], S2CD [8], QUARTZ [9], ASDCA [10], prox-SDCA [11], IPROX-SDCA [12], A-PROX-SDCA [13], AdaSDCA [14], SDNA [15].”
Minimizing finite sums with the stochastic average gradient (2013, background): “6 of the extended version of this paper we review other algorithms that have been discovered to have similar convergence rates, including stochastic dual coordinate ascent (SDCA) [54], incremental surrogate optimization (MISO) [35], stochastic variance-reduced gradient (SVRG) methods [23,26,34] whic”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “This is what the SDCA method [33] and its various extensions [32] do.”
Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling (2015, methodology): “This is due to a direct bound on the decrease of the primal-dual error of Quartz, without the need to ﬁrst analyze the dual error, in contrast to the typical approach for most of the dual coordinate ascent methods [22, 23, 20, 21, 9].”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, methodology): “Several other mini-batching algorithms have been proposed; including mini-batch proximal algorithms [25, 37, 38], accelerated methods [7], mini-batch SDCA [33, 35], and the combination of mini-batching and variance reduction such as Acc-Prox-SVRG [29] and mS2GD [23].”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, methodology): “Methods based on updating randomly selected dual variables enjoy, in our setting, a linear convergence rate (Shalev-Shwartz & Zhang, 2013b; 2012; Takáč et al., 2013; Shalev-Shwartz & Zhang, 2013a; Zhao & Zhang, 2014; Qu et al., 2014).”
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties (2014, methodology): “. Our discussion there included nonstochastic, cyclic coordinate descent methods [40, 24, 44, 5, 42, 43, 35], synchronous parallel methods that distribute the work of function and gradient evaluation [16, 25, 18, 7, 11, 1, 10, 37], and asynchronous parallel stochastic gradient methods (including the”