2023/10/19 by Ayoub El Hanchi, Hanchi, Ayoub El, Murat A. Erdogdu +1
Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Mathematical Approximation and Integration #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2310.12437
openalex publication_date 2023/10/19 · openalex created_date 2023/10/21 · openalex updated_date 2026/07/28
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.