Fetching the paper…
Reading the bibliography…
We study problem-dependent rates, i.e., generalization errors that scale near-optimally with the variance, the effective loss, or the gradient norms evaluated at the "best hypothesis." We introduce a principled framework dubbed "uniform localized convergence," and characterize sharp problem-dependent rates for central statistical learning problems.
Principles of mathematical analysis
Walter Rudin · 1964
Earlier work this paper cites.
Local asymptotic minimax and admissibility in estimation
Jaroslav Hájek · 1972
Earlier work this paper cites.
Limits of experiments
L Le Cam · 1972
Earlier work this paper cites.
On the asymptotic information bound
Aad van der Vaart · 1989
Earlier work this paper cites.
Optimum bounds for the distributions of martingales in banach spaces
Iosif Pinelis · 1994
Earlier work this paper cites.
Lower bounds in pattern recognition and learning
Luc Devroye and Gábor Lugosi · 1995
Earlier work this paper cites.
Majorizing measures: the generic chaining
Michel Talagrand · 1996
Earlier work this paper cites.
Regression shrinkage and selection via the lasso
Robert Tibshirani · 1996
Earlier work this paper cites.
Weak convergence and empirical processes
Aad W Van der Vaart and Jon A Wellner · 1996
Earlier work this paper cites.
Correction:“optimum bounds for the distributions of martingales in banach spaces”[ann. probab. 22 (1994), no. 4, 1679–1706; mr 96b: 60010]
Iosif Pinelis · 1999
Earlier work this paper cites.
Rademacher processes and bounding the risk of function learning
Vladimir Koltchinskii and Dmitriy Panchenko · 2000
Earlier work this paper cites.
Asymptotic statistics
Aad W Van der Vaart · 2000
Earlier work this paper cites.
Pattern classification and learning theory
Gábor Lugosi · 2002
Earlier work this paper cites.
Improving the sample complexity using global data
Shahar Mendelson · 2002
Earlier work this paper cites.
Generalization error bounds for bayesian mixture algorithms
Ron Meir and Tong Zhang · 2003
Earlier work this paper cites.
Optimal rates of aggregation
Alexandre B Tsybakov · 2003
Earlier work this paper cites.
Local rademacher complexities
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson · 2005
Earlier work this paper cites.
Smallest singular value of random matrices and geometry of random polytopes
Alexander E Litvak, Alain Pajor, Mark Rudelson, and Nicole Tomczak-Jaegermann · 2005
Earlier work this paper cites.
Concentration inequalities and asymptotic results for ratio type empirical processes
Evarist Giné and Vladimir Koltchinskii · 2006
Earlier work this paper cites.
A distribution-free theory of nonparametric regression
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk · 2006
Earlier work this paper cites.
Risk bounds for statistical learning
Pascal Massart and Élodie Nédélec · 2006
Earlier work this paper cites.
The EM algorithm and extensions
Geoffrey J McLachlan and Thriyambakam Krishnan · 2007
Earlier work this paper cites.
Tighter bounds for structured estimation
Olivier Chapelle, Chuong B Do, Choon H Teo, Quoc V Le, and Alex J Smola · 2009
Earlier work this paper cites.
On the generalization ability of online strongly convex programming algorithms
Sham M Kakade and Ambuj Tewari · 2009
Earlier work this paper cites.
Empirical bernstein bounds and sample variance penalization
Andreas Maurer and Massimiliano Pontil · 2009
Earlier work this paper cites.
Stochastic convex optimization
Shai Shalev-Shwartz · 2009
Earlier work this paper cites.
Lectures on stochastic programming: modeling and theory
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyński · 2009
Earlier work this paper cites.
Learnability, stability and uniform convergence
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan · 2010
Earlier work this paper cites.
Note on refined dudley integral covering number bound
Karthik Sridharan · 2010
Earlier work this paper cites.
Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d’Eté de Probabilités de Saint-Flour XXXVIII-2008
Vladimir Koltchinskii · 2011
Cited alongside, same era.
Regime change: Bit-depth versus measurement-rate in compressive sensing
Jason N Laska and Richard G Baraniuk · 2012
Cited alongside, same era.
A unified framework for high-dimensional analysis of m m -estimators with decomposable regularizers
Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu · 2012
Cited alongside, same era.
Convergence of stochastic processes
David Pollard · 2012
Cited alongside, same era.
Minimax-optimal rates for sparse additive models over kernel classes via convex programming
Garvesh Raskutti, Martin J Wainwright, and Bin Yu · 2012
Cited alongside, same era.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
An optimal unrestricted learning procedure
Shahar Mendelson · 2017
Later among the works it cites.
Variance-based regularization with convex objectives
Hongseok Namkoong and John C Duchi · 2017
Later among the works it cites.
Lijun Zhang, Tianbao Yang, and Rong Jin · 2017
Later among the works it cites.
Optimal learning via local entropies and sample compression
Nikita Zhivotovskiy · 2017
Later among the works it cites.
Graphical convergence of subgradients in nonconvex optimization and learning
Damek Davis and Dmitriy Drusvyatskiy · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Saeed Ghadimi and Guanghui Lan · 2013
Cited alongside, same era.
Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima
Po-Ling Loh and Martin J Wainwright · 2013
Cited alongside, same era.
Algorithms for direct 0–1 loss optimization in binary classification
Tan Nguyen and Scott Sanner · 2013
Cited alongside, same era.
Logistic regression: Tight bounds for stochastic and online optimization
Elad Hazan, Tomer Koren, and Kfir Y Levy · 2014
Cited alongside, same era.
Sparse recovery under weak moment assumptions
Guillaume Lecué and Shahar Mendelson · 2014
Cited alongside, same era.
Learning without concentration
Shahar Mendelson · 2014
Cited alongside, same era.
Zhaoran Wang, Quanquan Gu, Yang Ning, and Han Liu · 2014
Cited alongside, same era.
Later among the works it cites.
Uniform convergence of gradients for non-convex learning and optimization
Dylan J Foster, Ayush Sekhari, and Karthik Sridharan · 2018
Later among the works it cites.
Size-independent sample complexity of neural networks
Noah Golowich, Alexander Rakhlin, and Ohad Shamir · 2018
Later among the works it cites.
Gradient descent learns linear dynamical systems
Moritz Hardt, Tengyu Ma, and Benjamin Recht · 2018
Later among the works it cites.
An alternative view: When does sgd escape local minima?
Robert Kleinberg, Yuanzhi Li, and Yang Yuan · 2018
Later among the works it cites.
Global convergence of em algorithm for mixtures of two component linear regression
Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, and Damek Davis · 2018
Later among the works it cites.
Regularization and the small-ball method i: sparse recovery
Guillaume Lecué and Shahar Mendelson · 2018
Later among the works it cites.
Fast rates of erm and stochastic approximation: Adaptive to error bound conditions
Mingrui Liu, Xiaoxuan Zhang, Lijun Zhang, Rong Jin, and Tianbao Yang · 2018
Later among the works it cites.
The landscape of empirical risk for nonconvex losses
Song Mei, Yu Bai, and Andrea Montanari · 2018
Later among the works it cites.
Learning without concentration for general loss functions
Shahar Mendelson · 2018
Later among the works it cites.
Robust covariance estimation under l 4 − l 2 l_{4}-l_{2} norm equivalence
Shahar Mendelson and Nikita Zhivotovskiy · 2018
Later among the works it cites.
A geometric analysis of phase retrieval
Ju Sun, Qing Qu, and John Wright · 2018
Later among the works it cites.
High-dimensional probability: An introduction with applications in data science
Roman Vershynin · 2018
Later among the works it cites.
Robust wasserstein profile inference and applications to machine learning
Jose Blanchet, Yang Kang, and Karthyek Murthy · 2019
Later among the works it cites.
Orthogonal statistical learning
Dylan J Foster and Vasilis Syrgkanis · 2019
Later among the works it cites.
Rapid, robust, and reliable blind deconvolution via nonconvex optimization
Xiaodong Li, Shuyang Ling, Thomas Strohmer, and Ke Wei · 2019
Later among the works it cites.
Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi · 2019
Later among the works it cites.
Uniform convergence may be unable to explain generalization in deep learning
Vaishnavh Nagarajan and J Zico Kolter · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint
Martin J Wainwright · 2019
Later among the works it cites.
Lijun Zhang and Zhi-Hua Zhou · 2019
Later among the works it cites.
Sgd converges to global minimum in deep learning via star-convex path
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh · 2019
Later among the works it cites.
Failures of model-dependent generalization bounds for least-norm interpolation
Peter L Bartlett and Philip M Long · 2020
Closest in time.
Near-optimal methods for minimizing star-convex functions and beyond
Oliver Hinder, Aaron Sidford, and Nimit Sohoni · 2020
Closest in time.
On uniform convergence and low-norm interpolation learning
Lijia Zhou, D.J. Sutherland, and Nathan Srebro · 2020
Closest in time.