An unrestricted learning procedure

DOI10.1145/3361699MaRDI QIDQ5215471zbMATH OpenOpenAlexFDO

Authors Shahar Mendelson

Publication date 11 February 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.05342

zbMATH Keywords

heavy-tailed learning problemsunrestricted learning procedure

Mathematics Subject Classification ID

Statistics of extreme values; tail inference (62G32) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We study learning problems involving arbitrary classes of functions $F$, distributions $X$ and targets $Y$. Because proper learning procedures, i.e., procedures that are only allowed to select functions in $F$, tend to perform poorly unless the problem satisfies some additional structural property (e.g., that $F$ is convex), we consider unrestricted learning procedures that are free to choose functions outside the given class. We present a new unrestricted procedure that is optimal in a very strong sense: the required sample complexity is essentially the best one can hope for, and the estimate holds for (almost) any problem, including heavy-tailed situations. Moreover, the sample complexity coincides with the what one would expect if $F$ were convex, even when $F$ is not. And if $F$ is convex, the procedure turns out to be proper. Thus, the unrestricted procedure is actually optimal in both realms, for convex classes as a proper procedure and for arbitrary classes as an unrestricted procedure.

Recommendations

• Learning without concentration
• Learning without concentration for general loss functions
• scientific article; zbMATH DE number 1552503
• Concentration estimates for learning with unbounded sampling
• The importance of convexity in learning with squared loss

Cited in

(10)

• The softening learning procedure
• On Monte-Carlo methods in convex stochastic optimization
• Distribution-free robust linear regression
• On least squares estimation under heteroscedastic and heavy-tailed errors
• Robust classification via MOM minimization
• Mean estimation and regression under heavy-tailed distributions: A survey
• Regularization, sparse recovery, and median-of-means tournaments
• Extending the scope of the small-ball method
• Stable recovery and the coordinate small-ball behaviour of random vectors
• Covariance estimation: optimal dimension-free guarantees for adversarial corruption and heavy tails

This page was built for publication: An unrestricted learning procedure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215471)