Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression
Abstract
We study the performance of empirical risk minimization on the $p$-norm linear regression problem for $p \in (1, \infty)$. We show that, in the realizable case, under no moment assumptions, and up to a distribution-dependent constant, $O(d)$ samples are enough to exactly recover the target. Otherwise, for $p \in [2, \infty)$, and under weak moment assumptions on the target and the covariates, we prove a high probability excess risk bound on the empirical risk minimizer whose leading term matches, up to a constant that depends only on $p$, the asymptotically exact rate. We extend this result to the case $p \in (1, 2)$ under mild assumptions that guarantee the existence of the Hessian of the risk at its minimizer.
Cite
Text
El Hanchi and Erdogdu. "Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression." Neural Information Processing Systems, 2023.Markdown
[El Hanchi and Erdogdu. "Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/hanchi2023neurips-optimal/)BibTeX
@inproceedings{hanchi2023neurips-optimal,
title = {{Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression}},
author = {El Hanchi, Ayoub and Erdogdu, Murat A},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/hanchi2023neurips-optimal/}
}