# Trade-off Between Dependence and Complexity for Nonparametric Learning -- an Empirical Process Approach

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 158 references that are in the map.
- First posted on arXiv 17 Jan 2024.

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

- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [Learning in Implicit Generative Models](https://mlsanity.com/paper/1610.03483/) (2016)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [How Well Generative Adversarial Networks Learn Distributions](https://mlsanity.com/paper/1811.03179/) (2018)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections](https://mlsanity.com/paper/2107.01718/) (2021)
- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (2021)
- [Theoretical analysis of deep neural networks for temporally dependent observations](https://mlsanity.com/paper/2210.11530/) (2022)
- [Deep Neural Networks for Nonparametric Interaction Models with Diverging Dimension](https://mlsanity.com/paper/2302.05851/) (2023)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Adaptive deep learning for nonlinear time series models](https://mlsanity.com/paper/2207.02546/) (2022)
- [Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression](https://mlsanity.com/paper/1903.05315/) (2019)
- [Wasserstein Mirror Gradient Flow as the limit of the Sinkhorn Algorithm](https://mlsanity.com/paper/2307.16421/) (2023)
- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Excess risk bound for deep learning under weak dependence](https://mlsanity.com/paper/2302.07503/) (2023)
- [Optimal Transport for Stationary Markov Chains via Policy Iteration](https://mlsanity.com/paper/2006.07998/) (2020)
- [Sparse-penalized deep neural networks estimator under weak dependence](https://mlsanity.com/paper/2303.01406/) (2023)
- [On parameter estimation with the Wasserstein distance](https://mlsanity.com/paper/1701.05146/) (2017)
- [Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators](https://mlsanity.com/paper/2006.02044/) (2020)
- [Generalization bounds for nonparametric regression with β-mixing samples](https://mlsanity.com/paper/2108.00997/) (2021)
- [On Learnability under General Stochastic Processes](https://mlsanity.com/paper/2005.07605/) (2020)
- [Deep learning for psi-weakly dependent processes](https://mlsanity.com/paper/2302.00333/) (2023)

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

- [Fast Rates for Nonstationary Weighted Risk Minimization](https://mlsanity.com/paper/2602.05742/) (2026)
- [Forests for Differences: Robust Causal Inference Beyond Parametric DiD](https://mlsanity.com/paper/2505.09706/) (2025)
- [Beyond Discrepancy: Oracle Drift in Nonstationary Weighted Risk Minimization](https://mlsanity.com/paper/2610.13598/) (2026)

## Abstract (arXiv)

Empirical process theory for i.i.d. observations has emerged as a ubiquitous tool for understanding the generalization properties of various statistical problems. However, in many applications where the data exhibit temporal dependencies (e.g., in finance, medical imaging, weather forecasting etc.), the corresponding empirical processes are much less understood. Motivated by this observation, we present a general bound on the expected supremum of empirical processes under standard β/ρ-mixing assumptions. Unlike most prior work, our results cover both the long and the short-range regimes of dependence. Our main result shows that a non-trivial trade-off between the complexity of the underlying function class and the dependence among the observations characterizes the learning rate in a large class of nonparametric problems. This trade-off reveals a new phenomenon, namely that even under long-range dependence, it is possible to attain the same rates as in the i.i.d. setting, provided the underlying function class is complex enough. We demonstrate the practical implications of our findings by analyzing various statistical estimators in both fixed and growing dimensions. Our main examples include a comprehensive case study of generalization error bounds in nonparametric regression over smoothness classes in fixed as well as growing dimension using neural nets, shape-restricted multivariate convex regression, estimating the optimal transport (Wasserstein) distance between two probability distributions, and classification under the Mammen-Tsybakov margin condition -- all under appropriate mixing assumptions. In the process, we also develop bounds on Lr (1≤ r≤ 2)-localized empirical processes with dependent observations, which we then leverage to get faster rates for (a) tuning-free adaptation, and (b) set-structured learning problems.