Learning without concentration
From MaRDI portal
Abstract: We obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used here relies on a `small-ball' assumption and thus holds for classes consisting of heavy-tailed functions and for heavy-tailed targets. The resulting estimates scale correctly with the `noise level' of the problem, and when applied to the classical, bounded scenario, always improve the known bounds.
Recommendations
Cites work
- \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
- A remark on the diameter of random sections of convex bodies
- Best subset selection, persistence in high-dimensional statistical learning and optimization under l₁ constraint
- Bounding the smallest singular value of a random matrix without concentration
- Concentration inequalities. A nonasymptotic theory of independence
- Empirical processes with a bounded \(\psi_1\) diameter
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- Local Rademacher complexities
- Minimax rate of convergence and the performance of empirical risk minimization in phase recovery
- On generic chaining and the smallest singular value of random matrices with heavy tails
- On the singular values of random matrices
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
- Reconstruction and subgaussian operators in asymptotic geometric analysis
- Sharper bounds for Gaussian and empirical processes
- Some limit theorems for empirical processes (with discussion)
- Sparse recovery under weak moment assumptions
- The concentration of measure phenomenon
- Upper and lower bounds for stochastic processes. Modern methods and classical problems
- Weak convergence and empirical processes. With applications to statistics
Cited in
(84)- Simpler PAC-Bayesian bounds for hostile data
- Learning without concentration for general loss functions
- Relative deviation learning bounds and generalization with unbounded loss functions
- Optimal rates of statistical seriation
- Column normalization of a random measurement matrix
- Regularization and the small-ball method. I: Sparse recovery
- Slope meets Lasso: improved oracle bounds and optimality
- Estimation from nonlinear observations via convex programming with application to bilinear regression
- Learning from MOM's principles: Le Cam's approach
- Phase retrieval with PhaseLift algorithm
- Approximating \(L_p\) unit balls via random sampling
- Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
- A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- On Monte-Carlo methods in convex stochastic optimization
- Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
- AdaBoost and robust one-bit compressed sensing
- Proof methods for robust low-rank matrix recovery
- Suboptimality of constrained least squares and improvements via non-linear predictors
- Distribution-free robust linear regression
- On least squares estimation under heteroscedastic and heavy-tailed errors
- Aggregated hold out for sparse linear regression with a robust loss function
- Robust statistical learning with Lipschitz and convex loss functions
- Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics
- Robust machine learning by median-of-means: theory and practice
- Robust classification via MOM minimization
- Complex phase retrieval from subgaussian measurements
- Thin-shell concentration for random vectors in Orlicz balls via moderate deviations and Gibbs measures
- Learning with correntropy-induced losses for regression with mixture of symmetric stable noise
- Convergence rates of least squares regression estimators with heavy-tailed errors
- Solving equations of random convex functions via anchored regression
- Localized Gaussian width of \(M\)-convex hulls with applications to Lasso and convex aggregation
- Mean estimation and regression under heavy-tailed distributions: A survey
- Generalization bounds for non-stationary mixing processes
- On aggregation for heavy-tailed classes
- Regularization, sparse recovery, and median-of-means tournaments
- Posterior concentration and fast convergence rates for generalized Bayesian learning
- Generic error bounds for the generalized Lasso with sub-exponential data
- Performance of empirical risk minimization in linear aggregation
- scientific article; zbMATH DE number 2089350 (Why is no real title available?)
- Quantized compressed sensing: a survey
- Upper bounds on product and multiplier empirical processes
- Low rank matrix recovery from rank one measurements
- Lower Bounds for the Empirical Minimization Algorithm
- Local Rademacher complexity-based learning guarantees for multi-task learning
- Stable low-rank matrix recovery via null space properties
- Regularization and the small-ball method. II: Complexity dependent error rates
- Fast rates for general unbounded loss functions: from ERM to generalized Bayes
- Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
- Fast convex pruning of deep neural networks
- scientific article; zbMATH DE number 7626706 (Why is no real title available?)
- scientific article; zbMATH DE number 7625184 (Why is no real title available?)
- On the geometry of polytopes generated by heavy-tailed random vectors
- On the geometry of random polytopes
- Approximating the covariance ellipsoid
- Extending the scope of the small-ball method
- Sparse recovery under weak moment assumptions
- An unrestricted learning procedure
- Endpoint results for Fourier integral operators on noncompact symmetric spaces
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Variance-based regularization with convex objectives
- Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
- A unified approach to uniform signal recovery from nonlinear observations
- Orthogonal statistical learning
- Mean estimation in high dimension
- The geometric median and applications to robust mean estimation
- Stable recovery and the coordinate small-ball behaviour of random vectors
- Empirical risk minimization for time series: nonparametric performance bounds for prediction
- Low-rank matrix recovery via rank one tight frame measurements
- Covariance estimation with direction dependence accuracy
- Performance of empirical risk minimization for linear regression with dependent data
- Trimmed sample means for robust uniform mean estimation and regression
- Uniform bounds for robust mean estimators
- Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination
- On the robustness of the minimim _2 interpolator
- Improved rates for prediction and identification of partially observed linear dynamical systems
- Generalization bounds: perspectives from information theory and PAC-Bayes
- Noisy recovery from random linear observations: sharp minimax rates under elliptical constraints
- Statistical learnability of smooth boundaries via pairwise binary classification with deep ReLU networks
- Sharp optimality of sparse group LASSO and SLOPE under weaker assumptions
- Letter to the editor. Stable low-rank matrix recovery from 3-designs
- Empirical risk minimization for heavy-tailed losses
- Finite sample behavior of a sieve profile estimator in the single index mode
- Obtaining fast error rates in nonconvex situations
This page was built for publication: Learning without concentration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796408)
