Fetching the paper…
Reading the bibliography…
The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondr\'{a}k, 2018, 2019), (Bousquet, Klochkov, Zhivotovskiy, 2020) contain a generally inevitable sampling error term of order $\Theta(1/\sqrt{n})$.
Theory of Pattern Recognition
V. Vapnik and A. Chervonenkis · 1974
Earlier work this paper cites.
A finite sample distribution-free performance bound for local discrimination rules
W. H. Rogers and T. J. Wagner · 1978
Earlier work this paper cites.
Distribution-free inequalities for the deleted and holdout error estimates
L. Devroye and T. Wagner · 1979
Earlier work this paper cites.
Distribution-free performance bounds for potential function rules
L. Devroye and T. Wagner · 1979
Earlier work this paper cites.
On the posterior-probability estimate of the error rate of nonparametric classification rules
G. Lugosi and M. Pawlak · 1994
Earlier work this paper cites.
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation
M. Kearns and D. Ron · 1999
Earlier work this paper cites.
Some applications of concentration inequalities to statistics
P. Massart · 2000
Earlier work this paper cites.
Stability and generalization
O. Bousquet and A. Elisseeff · 2002
Earlier work this paper cites.
Local Rademacher complexities
P. L. Bartlett, O. Bousquet, and S. Mendelson · 2005
Earlier work this paper cites.
Empirical minimization
P. L. Bartlett and S. Mendelson · 2006
Earlier work this paper cites.
Prediction, Learning, and Games
N. Cesa-Bianchi and G. Lugosi · 2006
Earlier work this paper cites.
Local Rademacher complexities and oracle inequalities in risk minimization
V. Koltchinskii · 2006
Earlier work this paper cites.
Concentration inequalities for functions of independent variables
A. Maurer · 2006
Earlier work this paper cites.
Logarithmic regret algorithms for online convex optimization
E. Hazan, A. Agarwal, and S. Kale · 2007
Earlier work this paper cites.
On the generalization ability of online strongly convex programming algorithms
S. M. Kakade and A. Tewari · 2008
Earlier work this paper cites.
Fast rates for regularized objectives
K. Sridharan, S. Shalev-Shwartz, and N. Srebro · 2008
Earlier work this paper cites.
Stochastic convex optimization
S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan · 2009
Cited alongside, same era.
Learnability, stability and uniform convergence
S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan · 2010
Cited alongside, same era.
Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems
V. Koltchinskii · 2011
Cited alongside, same era.
Making gradient descent optimal for strongly convex stochastic optimization
A. Rakhlin, O. Shamir, and K. Sridharan · 2012
Cited alongside, same era.
Concentration Inequalities: A Nonasymptotic Theory of Independence
S. Boucheron, G. Lugosi, and P. Massart · 2013
Cited alongside, same era.
Understanding Machine Learning: From Theory to Algorithms
S. Shalev-Shwartz and S. Ben-David · 2014
Cited alongside, same era.
Optimal learning via local entropies and sample compression
N. Zhivotovskiy · 2017
Later among the works it cites.
Stability and generalization of learning algorithms that converge to global optima
Z. Charles and D. Papailiopoulos · 2018
Later among the works it cites.
Generalization bounds for uniformly stable algorithms
V. Feldman and J. Vondrák · 2018
Later among the works it cites.
Data-dependent stability of stochastic gradient descent
I. Kuzborskij and C. Lampert · 2018
Later among the works it cites.
Fast rates of ERM and stochastic approximation: Adaptive to error bound conditions
M. Liu, X. Zhang, L. Zhang, R. Jin, and T. Yang · 2018
Later among the works it cites.
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Convex Optimization: Algorithms and Complexity
S. Bubeck · 2015
Cited alongside, same era.
Fast rates for exp-concave empirical risk minimization
T. Koren and K. Levy · 2015
Cited alongside, same era.
Fast rates in statistical and online learning
T. Van Erven, P. Grunwald, N. A. Mehta, M. Reid, and R. Williamson · 2015
Cited alongside, same era.
Generalization of ERM in stochastic convex optimization: The dimension strikes back
V. Feldman · 2016
Cited alongside, same era.
Train faster, generalize better: Stability of stochastic gradient descent
M. Hardt, B. Recht, and Y. Singer · 2016
Cited alongside, same era.
Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition
H. Karimi, J. Nutini, and M. Schmidt · 2016
Cited alongside, same era.
V. Feldman and J. Vondrák · 2019
Later among the works it cites.
Tight analyses for non-smooth stochastic gradient descent
N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa · 2019
Later among the works it cites.
J. Mourtada and S. Gaïffas · 2019
Later among the works it cites.
Stability of stochastic gradient descent on nonsmooth convex losses
R. Bassily, V. Feldman, C. Guzmán, and K. Talwar · 2020
Later among the works it cites.
Proper learning, Helly number, and an optimal SVM bound
O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy · 2020
Later among the works it cites.
Sharper bounds for uniformly stable algorithms
O. Bousquet, Y. Klochkov, and N. Zhivotovskiy · 2020
Later among the works it cites.
Suboptimality of constrained least squares and improvements via non-linear predictors
T. Vaškevičius and N. Zhivotovskiy · 2020
Later among the works it cites.
SGD generalizes better than GD (and regularization doesn’t help)
I. Amir, T. Koren, and R. Livni · 2021
Closest in time.
Stable sample compression schemes: New applications and an optimal SVM margin bound
S. Hanneke and A. Kontorovich · 2021
Closest in time.
Distribution-free robust linear regression
J. Mourtada, T. Vaškevičius, and N. Zhivotovskiy · 2021
Closest in time.