# On Empirical Risk Minimization with Dependent and Heavy-Tailed Data

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 72 references that are in the map.
- First posted on arXiv 6 Sep 2021.

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

- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [Statistical consistency and asymptotic normality for high-dimensional robust M-estimators](https://mlsanity.com/paper/1501.00312/) (2015)
- [Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes](https://mlsanity.com/paper/1605.00252/) (2016)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Statistical Learning with Conditional Value at Risk](https://mlsanity.com/paper/2002.05826/) (2020)
- [A Kernel Independence Test for Random Processes](https://mlsanity.com/paper/1402.4501/) (2014)
- [Sharp Concentration Results for Heavy-Tailed Distributions](https://mlsanity.com/paper/2003.13819/) (2020)
- [High-dimensional vector autoregressive time series modeling via tensor decomposition](https://mlsanity.com/paper/1909.06624/) (2019)
- [Learning without Concentration for General Loss Functions](https://mlsanity.com/paper/1410.3192/) (2014)
- [Learning from weakly dependent data under Dobrushin's condition](https://mlsanity.com/paper/1906.09247/) (2019)
- [PAC-Bayesian Bound for the Conditional Value at Risk](https://mlsanity.com/paper/2006.14763/) (2020)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [Excess risk bounds in robust empirical risk minimization](https://mlsanity.com/paper/1910.07485/) (2019)
- [Statistical Estimation from Dependent Data](https://mlsanity.com/paper/2107.09773/) (2021)
- [On Learnability under General Stochastic Processes](https://mlsanity.com/paper/2005.07605/) (2020)
- [On Monte-Carlo methods in convex stochastic optimization](https://mlsanity.com/paper/2101.07794/) (2021)

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

- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [Towards Robust Offline Reinforcement Learning under Diverse Data Corruption](https://mlsanity.com/paper/2310.12955/) (2023)
- [High-dimensional robust regression under heavy-tailed data: Asymptotics and Universality](https://mlsanity.com/paper/2309.16476/) (2023)
- [Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss](https://mlsanity.com/paper/2402.05928/) (2024)
- [Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptions](https://mlsanity.com/paper/2411.00465/) (2024)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [The noise level in linear regression with dependent data](https://mlsanity.com/paper/2305.11165/) (2023)
- [Dual-Robust Cross-Domain Offline Reinforcement Learning Against Dynamics Shifts](https://mlsanity.com/paper/2512.02486/) (2025)
- [PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs](https://mlsanity.com/paper/2312.09793/) (2023)
- [Trade-off Between Dependence and Complexity for Nonparametric Learning -- an Empirical Process Approach](https://mlsanity.com/paper/2401.08978/) (2024)
- [Rate-Optimal Non-Asymptotics for the Quadratic Prediction Error Method](https://mlsanity.com/paper/2404.07937/) (2024)
- [Neural Network Approximation for Pessimistic Offline Reinforcement Learning](https://mlsanity.com/paper/2312.11863/) (2023)
- [Empirical Risk Minimization for Losses without Variance](https://mlsanity.com/paper/2309.03818/) (2023)
- [Subsampled Ensemble Can Improve Generalization Tail Exponentially](https://mlsanity.com/paper/2405.14741/) (2024)
- [Data Quality in Edge Machine Learning: A State-of-the-Art Survey](https://mlsanity.com/paper/2406.02600/) (2024)
- [TailedTS: Benchmark Dataset for Heavy-Tailed Time Series Prediction and Periodicity Quantification](https://mlsanity.com/paper/2605.16361/) (2026)

## Abstract (arXiv)

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.