Chaining Bounds for Empirical Risk Minimization

2016/09/07 by G. Gy. Balázs, András György, Balázs, Gábor +3 · 1 citation
Decision Sciences · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical Approximation and Integration #Probabilistic and Robust Engineering Design #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1609.01872

openalex publication_date 2016/09/07 · openalex created_date 2016/09/16 · openalex updated_date 2026/08/01

Abstract

This paper extends the standard chaining technique to prove excess risk upper bounds for empirical risk minimization with random design settings even if the magnitude of the noise and the estimates is unbounded. The bound applies to many loss functions besides the squared loss, and scales only with the sub-Gaussian or subexponential parameters without further statistical assumptions such as the bounded kurtosis condition over the hypothesis class. A detailed analysis is provided for slope constrained and penalized linear least squares regression with a sub-Gaussian setting, which often proves tight sample complexity bounds up to logartihmic factors.

Cited by

• Near-optimal Delta-convex Estimation of Lipschitz Functions

Related

• Excess risk bounds in robust empirical risk minimization
• On the Minimal Error of Empirical Risk Minimization
• On the Variance, Admissibility, and Stability of Empirical Risk Minimization
• Empirical Risk Minimization for Losses without Variance
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions