SVM optimization: inverse dependence on training set size

By Shai Shalev-Shwartz, Nati Srebro. 2008

289 citations recorded by the source corpus.

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

Citations in the corpus

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “[22] Shai Shalev-Shwartz and Nathan Srebro.”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, methodology): “To understand the implication these bounds, we follow the approach described in [3, 12] to analyze large-scale learning algorithms.”
Differentially Private Empirical Risk Minimization (2009, positive): “However, in L1-regularized ERM, one can find a dataset in which a change in one training point can significantly change the solution.”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, background): “SGD originated as “Stochastic Approximation” in the pioneerin g work of Robbins and Monroe [32], and has recently received renewed attention for confrontin g very large scale problems, especially in the context of machine learning [4, 33, 24, 2].”
Privacy-preserving logistic regression (2008, unknown): “We can use an analysis as in [15] to write that: Notice that from Lemma 4, ˆ f λ ( w 2 ) − ˆ f λ ( w 1 ) ≤ 8 d 2 log 2 ( d/δ ) .”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, background): “, [9, 5, 58, 7]) ú “Data” e ort also exhibits a similar behavior in the overdetermined case when a signal prior is used due to noise! Volkan Cevher, Mário Figueiredo, Mark Schmidt, and Quoc Tran-Dinh Convex Optimization for Big Data 17 / 142”
Large-Scale Machine Learning with Stochastic Gradient Descent (2010, methodology): “Similar analyses can be carried out for specific algorithms under weaker assumptions (e.g. Shalev-Shwartz and Srebro (2008)).”
The Tradeoffs of Large Scale Learning (2007, background): “Shalev-Shwartz and Srebro (2008) rigorously extend the analysis to regularized risk formulations with linear parametrization and ﬁnd again that, for learning purposes, SGD algorithms are often more attractive than standard primal or dual algorithms with good optimization complexity (Joachims, 2006;…”
Regularized Policy Iteration with Nonparametric Function Spaces (2016, unknown): “The use of stochastic gradient-like algorithms is especially appealing in the light of results such as Bottou and Bousquet (2008); Shalev-Shwartz and Srebro (2008).”
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning (2011, methodology): “Its analysis has been attacked mainly in three communities: stochas ti pproximation [1, 2, 3, 4, 5, 6], optimization [7, 8], and machine learning [9, 10, 11, 12, 13, 4, 15].”
Stochastic Gradient Descent Tricks (2012, unknown): “[22]).”
Efficient Distributed Linear Classification Algorithms via the Alternating Direction Method of Multipliers (2012, background): “This few number of the iterations can be enough for large-scale classification tasks since the SVM (or logistic regression) uses loss functions that approximate the misclassification errors, and it may not be necessary to minimize these objectives exactly [1, 17].”
Multitask Sparsity via Maximum Entropy Discrimination (2011, methodology): “In fact, if the QP is of a simple SVM-type form, much faster SVM solvers can be used instead of QP (Joachims, 2006; Shalev-Shwartz et al., 2007; Bottou and Bousquet, 2008; Shalev-Shwartz and Srebro, 2008).”
Information-theoretic lower bounds on the oracle complexity of convex optimization (2009, background): “Several authors have recently considered this problem [3, 9], and provided upper bounds for particular algorithms.”
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, background): “Problems of this form arise in machine learning [3, 2, 30, 8], control [5, 7, 15], and wireless communications [27, 23, 24].”