Fast Rates for Regularized Objectives
Published 8 December 2008
Karthik Sridharan, Shai Shalev‐Shwartz, Nathan Srebro
Citations113
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the value attained by the empirical minimizer converges to the optimal value with rate 1/n, which is essential for obtaining certain type of oracle inequalities for SVMs.
Abstract
We study convergence properties of empirical minimization of a stochastic strongly convex objective, where the stochastic component is linear. We show that the value attained by the empirical minimizer converges to the optimal value with rate 1/n. The result applies, in particular, to the SVM objective. Thus, we obtain a rate of 1/n on the convergence of the SVM objective (with fixed regular-ization parameter) to its infinite data limit. We demonstrate how this is essential for obtaining certain type of oracle inequalities for SVMs. The results extend also to approximate minimization as well as to strong convexity with respect to an arbitrary norm, and so also to objectives regularized using other `p norms. 1
Keywords
Computer ScienceDecision Sciences
Lecture notes in computer scienceRademacher and Gaussian Complexities: Risk Bounds and Structural Results
2,111 Citations2001Peter L. Bartlett, Shahar Mendelson
This work investigates the use of certain data-dependent estimates of the complexity of a function class called Rademacher and Gaussian complexities and proves general risk bounds in terms of these complexities in a decision theoretic setting.
Journal of the American Statistical AssociationConvexity, Classification, and Risk Bounds
1,019 Citations2006Peter L. Bartlett, Michael I. Jordan +1 more
A general quantitative relationship between the risk as assessed using the 0–1 loss and the riskAs assessed using any nonnegative surrogate loss function is provided, and it is shown that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function.
The Annals of StatisticsOptimal aggregation of classifiers in statistical learning
577 Citations2004A. B. Tsybakov
The main result of the paper concerns optimal aggregation of classifiers: a classifier that automatically adapts both to the complexity and to the margin, and attains the optimal fast rates, up to a logarithmic factor.
Lecture notes in computer scienceIntroduction to Statistical Learning Theory
490 Citations2004Olivier Bousquet, Stéphane Boucheron +1 more
This tutorial introduces the techniques that are used to obtain results in the form of so-called error bounds in statistical learning theory.
ESAIM Probability and StatisticsTheory of Classification: a Survey of Some Recent Advances
416 Citations2005Stéphane Boucheron, Olivier Bousquet +1 more
Online Learning: Theory, Algorithms, and Applications
316 Citations2007Shai Shalev‐Shwartz
This dissertation describes a novel framework for the design and analysis of online learning algorithms and proposes a new perspective on regret bounds which is based on the notion of duality in convex optimization.
The Annals of StatisticsFast rates for support vector machines using Gaussian kernels
258 Citations2007Ingo Steinwart, Clint Scovel
This work uses concepts like Tsybakov’s noise assumption and local Rademacher averages to establish learning rates up to the order of n −1 for nontrivial distributions and introduces a geometric assumption for distributions that allows us to estimate the approximation properties of Gaussian RBF kernels.
ScholarlyCommons (University of Pennsylvania)On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization
248 Citations2008Sham M. Kakade, Karthik Sridharan +1 more
This work characterizes the generalization ability of algorithms whose predictions are linear in the input vector and provides sharp bounds for Rademacher and Gaussian complexities of (constrained) linear classes, which directly lead to a number of generalization bounds.
Lecture notes in computer scienceLogarithmic Regret Algorithms for Online Convex Optimization
207 Citations2006Elad Hazan, Adam Tauman Kalai +2 more
Applied Physics Letters10.1162/153244302760200713
108 Citations2000
This paper investigates two closely related methods to derive upper bounds on covering numbers for linear function classes by relying on the so-called Maurey's lemma and techniques from the mistake bound framework in online learning.
Lecture notes in computer scienceLocalized Rademacher Complexities
85 Citations2002Peter L. Bartlett, Olivier Bousquet +1 more
New error bounds which are based on the local averages are presented and it is indicated how data-dependent local averages can be estimated without a priori knowledge of the class at hand.
Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms
83 Citations2002Olivier Bousquet
The importance of convexity in learning with squared loss
11 Citations1996Wee Sun Lee, Peter L. Bartlett +1 more
It is shown that if the closure of a function class under the metric induced by some probability distribution is not convex, then the sample complexity for agnostically learning with squared loss is lower than that for agnostic learning, so learning the convex hull provides better approximation capabilities with little sample complexity penalty.
Institute of Mathematical Statistics eBooksA new concentration result for regularized risk minimizers
8 Citations2006Ingo Steinwart, Don Hush +1 more
A new concentration result for regularized risk mini- mizers is established which is similar to an oracle inequality and for regression the results suggest that using the loss function L�(y, t) = |y t| withnear 1 may often be preferable to the usual choice of � = 2.