Distributed Mini-Batch SDCA

By Martin Takác, Peter Richtárik, Nati Srebro. 2015

50 citations recorded by the source corpus.

We present an improved analysis of mini-batched stochastic dual coordinate ascent for regularized empirical loss minimization (i.e. SVM and SVM-type objectives). Our analysis allows for flexible sampling schemes, including where data is distribute across machines, and combines a dependence on the smoothness of the loss and/or the data spread (measured through the spectral norm).

Subfields: Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture

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 Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “As the size of the mini-batch grows, this can slow them down in terms of overall runtime, and can even lead to divergence in practice (Takáč et al., 2013; Takáč et al., 2015; Richtárik and Takáč, 2016; Marecek et al., 2015).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “This does not need to be an issue, if a dual version of coordinate descent is used — in which the distribution is done by data points [94] followed by works on Communication Efficient Dual Cooridante Ascent, described in next section.”
Distributed optimization with arbitrary local solvers (2015, background): “…with the massive growth of available datasets, major roadblocks still persist in the distributed setting, where data no longer ﬁts in the memory of a single computer, and computation must be split across multiple machines in a network [3, 7, 12, 18, 22, 28, 32, 34, 37, 46, 50, 58, 60, 62, 76].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “However, with the massive growth of available datasets, major roadblocks still persist in the distributed setting, where data no longer fits in the memory of a single computer, and computation must be split across multiple machines in a network [19, 111, 106, 8, 149, 53, 173, 57, 32, 108, 166, 167, ”
Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, background): “This improves upon the result obtained in Shalev-Shwartz and Zhang (2013); Takáč et al. (2015); Takáč et al. (2013), where only a sublinear rate was derived.”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “This is what the SDCA method [34] and its various extensions [36] do.”
Gradient Diversity Empowers Distributed Learning (2017, methodology): “Mini-batch SDCA [38, 42] has been proposed for regularized convex problems.”
The Effect of Network Width on the Performance of Large-batch Training (2018, methodology): “Mini-batch algorithms can be combined with accelerated gradient descent algorithms [32], or using dual coordinate descent [33, 34].”
Primal-Dual Rates and Certificates (2016, methodology): “To be precise, our shown convergence rate for the general algorithms is dependent on the spectral norm of the data, see also (Takáč et al., 2013; 2015).”
A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (2018, background): “(Recht et al., 2011), Distributed SDCA (Takáč et al., 2015), Distributed SVRG (Lee et al., 2015; Zhao & Li, 2016), ASAGA (Leblond et al., 2017), ProxASAGA (Pedregosa et al., 2017)).”
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging (2016, background): “Non-Stochastic Approximation: In order to utilize the recent developments in computing frameworks, there has been a number of efforts in developing distributed/parallel machine learning algorithms that utilize multi-core [4, 5, 21, 22, 27, 24] and multi-machine [2, 3, 6, 23, 7] computing frameworks.”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, methodology): “Other algorithms include accelerated methods (Cotter et al., 2011), mini-batch SDCA (Shalev-Shwartz and Zhang, 2013, Takáč et al., 2015), and the combination of mini-batching and variance reduction such as Acc-Prox-SVRG (Nitanda, 2014) and mS2GD (Konečn`y et al., 2016).”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, methodology): “Parallelization via mini-batching has been studied in Cotter et al. (2011); Tak´ac et al. (2013); Shalev-Shwartz and Zhang (2013b); Tak´ac et al. (2015).”
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization? (2015, methodology): “There has been an enormous interest in large-scale machine learning problems and many parallel [4, 11] or distributed algorithms have been proposed [1, 16, 12, 14, 8].”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, methodology): “Therefore in practice, it is necessary to do a trade-off by using the mini-batch update approach (Takac et al., 2013; Takáč et al., 2015).”