Pegasos: primal estimated sub-gradient solver for SVM

By Shai Shalev-Shwartz, Yoram Singer, Nati Srebro, Andrew Cotter. 2007

2,352 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training, Statistical Learning Theory

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

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “Stochastic gradient descent (SGD) (Robbins and Monro, 1951; Nemirovski and Yudin, 1978, 1983; Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Hardt et al., 2016), is the workhorse for training supervised machine learning problems that have the generic form (1).”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, background): “SGD updates only involve f ′i(w) for an index i chosen uniformly at random, providing an unbiased gradient estimate, since Ef ′i(w) = f ′(w).”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “Copyright 2013 by the author(s). call to the so-called maximization oracle on each iteration, basic stochastic subgradient methods are still widely used for training structural SVMs (Ratliff et al., 2007; Shalev-Shwartz et al., 2010a).”
On the Equivalence between Herding and Conditional Gradient Algorithms (2012, background): “ −hf,µi − 1 2 kfk2 . The dual function f → minx∈X f(x)−hf,µi−1 2kfk2 is 1-stronglyconcaveand non-diﬀerentiable, and anaturalalgorithmtomaximizeit isthus subgradientascentwith astep sizeequalto 1 t+1 (Shalev-Shwartz et al., 2007), which is known to be equivalent to the primal conditional gradient alg”
Optimization Methods for Large-Scale Machine Learning (2016, background): “Convergence results for SG and its variants are occasionally established using regret bounds as an intermediate step [164, 144, 54].”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, background): “Assumption (ii) is a standard assumption in [26], [27], [38]–[41].”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, neutral): “tion in [5], [18], [20], [23], [33], [39]–[43].”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “This efficiency gain of SGD over GD is very well studied and known to reach up to a factor of n for sum-structured problems, both in theory [1] and practice [2], for n being the training set size.”
Federated Multi-Task Learning (2017, methodology): “See, e.g., a discussion of this method for the SVM models of interest [44].”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, methodology): “The gradient computations for each mini-batch can be parallelized, allowing these methods to perform faster in a distributed framework (see for = b ( i − 1)+1 ( w i , z t ) w i +1 := w i − η ∇ (cid:96) i ( w i )) w i +1 := P W ( w i +1 ) end for Return ¯ w = 1 n =1 w i instance [11]).”
Optimal Distributed Online Prediction Using Mini-Batches (2010, neutral): “The paper is organized as follows.”
Adaptive Bound Optimization for Online Convex Optimization (2010, background): “Many of these algorithms can be thought of as (significant) extensions of online subgradient descent, including (Duchi & Singer, 2009; Do et al., 2009; Shalev-Shwartz et al., 2007).”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “The choice of the step-size parameter β is of paramount significance for the performance of the algorithm, as argued for different but related algorithms by Richtárik & Takáč (2012a); Takáč et al. (2013); Fercoq & Richtárik (2013).”
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.”
Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “Then, the classical battery of convex optimization algorithms may be used, such as gradient descent, stochastic gradient descent (Shalev-Shwartz et al., 2007) or cuttingplanes (Joachims et al.”
Machine Unlearning (2019, methodology): “In summary, slicing can be used for any model that is trained through gradient descent: e.g., logistic regression and neural networks, but also support vector machines in some cases [40].”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, methodology): “Following (Shalev-Shwartz et al., 2011) and (Joachims, 2006), we took λ = 10−4 for ccat, λ = 10−6 for cov1, and λ = 5 × 10−5 for astro-ph.”
Stochastic dual coordinate ascent methods for regularized loss (2012, neutral): “Several authors (e.g. [10, 3]) proved a linear convergence rate for solving SVM with DCA (not necessarily stochastic).”