Mini-Batch Primal and Dual Methods for SVMs

By Martin Takác, Avleen Singh Bijral, Peter Richtárik, Nati Srebro. 2013

197 citations recorded by the source corpus.

We address the issue of using mini-batches in stochastic optimization of SVMs. We show that the same quantity, the spectral norm of the data, controls the parallelization speedup obtained for both primal stochastic subgradient descent (SGD) and stochastic dual coordinate ascent (SCDA) methods and use it to derive novel variants of mini-batched SDCA. Our guarantees for both methods are expressed in terms of the original nonsmooth primal problem based on the hinge-loss.

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

Training Region-Based Object Detectors with Online Hard Example Mining (2016, background): “One concern over using only N = 2 images per batch is that it may cause unstable gradients and slow convergence because RoIs from an image may be highly correlated [31].”
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, background): “There have been some attempts to understand the interplay between the mini-batch size and computational efﬁciency, e.g., [TBRS13, LZCS14] in the standard non-interpolated regime.”
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).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “In other words, for α = 2/3, we need P ≤ X1/3: the number of machines as to be smaller than the number of iterations to the power 1/3, in other words, for 1000 iterations, one could only use 10 machines to reach the asymptotic regime where OSA performs similarly to MBA.”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “While mini-batch and parallel SGD are very well studied (Takáč et al., 2013; Zinkevich et al., 2010b), the theoretical understanding of local SGD variants is less clear.”
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).”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “Note that the result is a direct generalization of Lemma 1 in (Takáč et al., 2013) to the c > 1 case.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “For a theoretical analysis for convex functions we refer the reader to [66, 64, 65] and [87, 93] for SVM problems.”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “…regimesn≫ d andn≪ d. −6 10 −4 10 −2 10 0 10 2 Time (s) COCOA (β k =1) mini−batch−CD (β k =10) local−SGD (β k =1) mini−batch−sgd (β k =10) In Figure3 we explore the effect ofH , the computation-communication trade-off factor, on the convergence of COCOA for the Cov dataset on a cluster of 4 nodes.”
Distributed optimization with arbitrary local solvers (2015, background): “In general, one would intuitively expect that the optimal choice would be to have Θ such that T A (Θ) = O (1) × c . values In practice, however, the best strategy for any given local solver is to try several for the number of local iterations to estimate the optimal choice.”
Semi-Stochastic Gradient Descent Methods (2013, background): “[10] extends the primal-dual framework to the parallel/mini-batch setting.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “An algorithm of specific interest to solve problem (1) is mini-batch SGD (Dekel et al., 2012; Takáč et al., 2013), a parallel version of stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski et al.”
Fast distributed coordinate descent for non-strongly convex losses (2014, background): “1 The problem that we solve is the SVM dual problem (for more details, see [10, 11]).”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, neutral): “SVM SGD/SDCA [26,27,29] d λ AGD [2,18,19] dn √ 1 λ This paper d ( n + min{ 1 λ , √ n λ } )”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, background): “This resulted in an interest in parallel [16, 21, 3, 15] and distributed [14] coordinate descent methods.”
A-Fast-RCNN: Hard Positive Generation via Adversary for Object Detection (2017, background): “It has been shown that using all examples is often not the optimal solution [33, 39] and selecting hard examples is better.”
Parallel coordinate descent methods for big data optimization (2012, background): “Further papers on various aspects of the topic of parallel CDMs, building on the work in this paper, include [3,17,18,25].”