On the Minimal Error of Empirical Risk Minimization
We study the minimal error of the Empirical Risk Minimization (ERM) procedure in the task of regression, both in the random and the fixed design settings. Our sharp lower bounds shed light on the possibility (or impossibility) of adapting to simplicity of the model generating the data. In the fixed design setting, we show that the error is governed by the global complexity of the entire class. In contrast, in random design, ERM may only adapt to simpler models if the local neighborhoods around the regression function are nearly as complex as the class itself, a somewhat counter-intuitive conclusion. We provide sharp lower bounds for performance of ERM for both Donsker and non-Donsker classes. We also discuss our results through the lens of recent studies on interpolation in overparameterized models.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSimilar Papers 제목 키워드 기반
Minimax Limits of k-Fold Cross-Validation via Majority
We study the mean-squared error of $k$-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds $k$. Despite the widespread use of cross-validation, principle…
Binary ClassificationA Mosco sufficient condition for intrinsic stability of non-unique convex Empirical Risk Minimization
Empirical risk minimization (ERM) stability is usually studied via single-valued outputs, while convex non-strict losses yield set-valued minimizers. We identify Painlevé-Kuratowski upper semicontinuity (PK-u.s.c.) as th…
Empirical risk minimization is consistent with the mean absolute percentage error
We study in this paper the consequences of using the Mean Absolute Percentage Error (MAPE) as a measure of quality for regression models. We show that finding the best model under the MAPE is equivalent to doing weighted…
regressionDiametrical Risk Minimization: Theory and Computations
The theoretical and empirical performance of Empirical Risk Minimization (ERM) often suffers when loss functions are poorly behaved with large Lipschitz moduli and spurious sharp minimizers. We propose and analyze a coun…
Generalization BoundsRisk Bounds and Rademacher Complexity in Batch Reinforcement Learning
This paper considers batch Reinforcement Learning (RL) with general value function approximation. Our study investigates the minimal assumptions to reliably estimate/minimize Bellman error, and characterizes the generali…
Learning Theoryreinforcement-learningReinforcement LearningReinforcement Learning (RL)