# Generalization and Robustness of Batched Weighted Average Algorithm with V-geometrically Ergodic Markov Data

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2014.

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

- [Adaptive Group Lasso Neural Network Models for Functions of Few Variables and Time-Dependent Data](https://mlsanity.com/paper/2108.10825/) (2021)
- [Posterior concentration and fast convergence rates for generalized Bayesian learning](https://mlsanity.com/paper/2111.10243/) (2021)
- [EnSolver: Uncertainty-Aware Ensemble CAPTCHA Solvers with Theoretical Guarantees](https://mlsanity.com/paper/2307.15180/) (2023)
- [A Generalization Bound of Deep Neural Networks for Dependent Data](https://mlsanity.com/paper/2310.05892/) (2023)

## Abstract (arXiv)

We analyze the generalization and robustness of the batched weighted average algorithm for V-geometrically ergodic Markov data. This algorithm is a good alternative to the empirical risk minimization algorithm when the latter suffers from overfitting or when optimizing the empirical risk is hard. For the generalization of the algorithm, we prove a PAC-style bound on the training sample size for the expected L1-loss to converge to the optimal loss when training data are V-geometrically ergodic Markov chains. For the robustness, we show that if the training target variable's values contain bounded noise, then the generalization bound of the algorithm deviates at most by the range of the noise. Our results can be applied to the regression problem, the classification problem, and the case where there exists an unknown deterministic target hypothesis.