On Empirical Risk Minimization with Dependent and Heavy-Tailed Data
arXiv:2109.02224
Abstract
In this work, we establish risk bounds for the Empirical Risk Minimization (ERM) with both dependent and heavy-tailed data-generating processes. We do so by extending the seminal works of Mendelson [Men15, Men18] on the analysis of ERM with heavy-tailed but independent and identically distributed observations, to the strictly stationary exponentially -mixing case. Our analysis is based on explicitly controlling the multiplier process arising from the interaction between the noise and the function evaluations on inputs. It allows for the interaction to be even polynomially heavy-tailed, which covers a significantly large class of heavy-tailed models beyond what is analyzed in the learning theory literature. We illustrate our results by deriving rates of convergence for the high-dimensional linear regression problem with dependent and heavy-tailed data.
arXiv commentfixed minor typos
References in corpus (11)
- Basic Properties of Strong Mixing Conditions. A Survey and Some Open Questions
- 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
- Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes
- A Kernel Independence Test for Random Processes
- Learning with Square Loss: Localization through Offset Rademacher Complexity
- Statistical Learning with Conditional Value at Risk
- Online Nonparametric Regression
- PAC-Bayesian Bound for the Conditional Value at Risk
- Excess risk bounds in robust empirical risk minimization
- Rademacher complexity of stationary sequences
- Spectral risk-based learning using unbounded losses