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

• URL: http://arxiv.org/abs/2310.12437v2
• Date: Mon, 17 Jun 2024 22:48:42 GMT
• Title: Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression
• Authors: Ayoub El Hanchi, Murat A. Erdogdu,
• Abstract summary: We show that, in the realizable case, under no moment assumptions, $O(d)$ samples are enough to exactly recover the target. 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.
• Score: 19.31269916674961
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Stability and Sharper Risk Bounds with Convergence Rate $O(1/n^2)$ [23.380477456114118]
  The sharpest known high probability excess risk bounds are up to $Oleft( 1/nright)$ for empirical risk minimization and projected descent via algorithmic stability.
  arXiv  Detail & Related papers  (2024-10-13T07:50:47Z)
• Risk Estimation in a Markov Cost Process: Lower and Upper Bounds [3.1484174280822845]
  We tackle the problem of estimating risk measures of the infinite-horizon discounted cost within a Markov cost process. The risk measures we study include variance, Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR)
  arXiv  Detail & Related papers  (2023-10-17T16:35:39Z)
• On Regression in Extreme Regions [1.0338669373504403]
  This paper focuses on the case of extreme (i.e. very large) observations $X$. Because of their rarity, the contributions of such observations to the (empirical) error is negligible. We show that an empirical and nonasymptotic version of this 'extreme risk', based on a fraction of the largest observations solely, yields good generalization capacity.
  arXiv  Detail & Related papers  (2023-03-06T12:55:38Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  We study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance $tau$. We show the minimax CVaR regret rate is $Omega(sqrttau-1AK)$, where $A$ is the number of actions and $K$ is the number of episodes. We show that our algorithm achieves the optimal regret of $widetilde O(tau-1sqrtSAK)$ under a continuity assumption and in general attains a near
  arXiv  Detail & Related papers  (2023-02-07T02:22:31Z)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  We propose a new method for estimating the minimizer $boldsymbolx*$ and the minimum value $f*$ of a smooth and strongly convex regression function $f$. We derive non-asymptotic upper bounds for the quadratic risk and optimization error of $boldsymbolz_n$, and for the risk of estimating $f*$.
  arXiv  Detail & Related papers  (2022-11-29T18:38:40Z)
• Mitigating multiple descents: A model-agnostic framework for risk monotonization [84.6382406922369]
  We develop a general framework for risk monotonization based on cross-validation. We propose two data-driven methodologies, namely zero- and one-step, that are akin to bagging and boosting.
  arXiv  Detail & Related papers  (2022-05-25T17:41:40Z)
• Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$ [4.1499725848998965]
  We show a high probability excess risk bound with the rate $O(log n/n)$ for strongly convex and Lipschitz losses valid for emphany empirical risk minimization method. We discuss how $O(log n/n)$ high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.
  arXiv  Detail & Related papers  (2021-03-22T17:28:40Z)
• PAC$^m$-Bayes: Narrowing the Empirical Risk Gap in the Misspecified Bayesian Regime [75.19403612525811]
  This work develops a multi-sample loss which can close the gap by spanning a trade-off between the two risks. Empirical study demonstrates improvement to the predictive distribution.
  arXiv  Detail & Related papers  (2020-10-19T16:08:34Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret [115.85354306623368]
  We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels. We propose two provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI) and Risk-Sensitive Q-learning (RSQ) We prove that RSVI attains an $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big)$ regret, while RSQ attains an $tildeObig(lambda
  arXiv  Detail & Related papers  (2020-06-22T19:28:26Z)
• Risk of the Least Squares Minimum Norm Estimator under the Spike Covariance Model [0.0]
  We study risk of the minimum norm linear least squares estimator in when the number of parameters $d$ depends on $n$, and $fracdn rightarrow infty$. We show that in this setting risk of minimum norm least squares estimator vanishes in compare to risk of the null estimator.
  arXiv  Detail & Related papers  (2019-12-31T16:58:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.