# Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression

arXiv: https://arxiv.org/abs/2310.12437 · HTML: https://mlsanity.com/paper/2310.12437/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 13 of 13)

- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Learning without Concentration for General Loss Functions](https://mlsanity.com/paper/1410.3192/) (2014)
- [Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression](https://mlsanity.com/paper/1907.07167/) (2019)
- [Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors](https://mlsanity.com/paper/2009.09304/) (2020)
- [Improved Iteration Complexities for Overconstrained p-Norm Regression](https://mlsanity.com/paper/2111.01848/) (2021)
- [Iterative Refinement for ℓp-norm Regression](https://mlsanity.com/paper/1901.06764/) (2019)
- [An homotopy method for ℓp regression provably beyond self-concordance and in input-sparsity time](https://mlsanity.com/paper/1711.01328/) (2017)
- [Faster p-norm minimizing flows, via smoothed q-norm problems](https://mlsanity.com/paper/1910.10571/) (2019)
- [Fast Algorithms for ℓp-Regression](https://mlsanity.com/paper/2211.03963/) (2022)

## Built on by (most cited first, 2 of 2)

- [Minimax Linear Regression under the Quantile Risk](https://mlsanity.com/paper/2406.12145/) (2024)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)

## Abstract (arXiv)

We study the performance of empirical risk minimization on the p-norm linear regression problem for p ∈ (1, ∞). 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 ∈ [2, ∞), 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 ∈ (1, 2) under mild assumptions that guarantee the existence of the Hessian of the risk at its minimizer.