The Generalization Ability of Online Algorithms for Dependent Data

DOI10.1109/TIT.2012.2212414zbMATH Open1364.68372arXiv1110.2529OpenAlexW2127684734MaRDI QIDQ2989484FDOQ2989484

Alekh Agarwal, John C. Duchi

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study the generalization performance of online learning algorithms trained on samples coming from a dependent source of data. We show that the generalization error of any stable online algorithm concentrates around its regret--an easily computable statistic of the online performance of the algorithm--when the underlying ergodic process is $$- or $phi$-mixing. We show high probability error bounds assuming the loss function is convex, and we also establish sharp convergence rates and deviation bounds for strongly convex losses and several linear prediction problems such as linear and logistic regression, least-squares SVM, and boosting on dependent data. In addition, our results have straightforward applications to stochastic optimization with dependent data, and our analysis requires only martingale convergence arguments; we need not rely on more powerful statistical tools such as empirical process theory.

Full work available at URL: https://arxiv.org/abs/1110.2529

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Cited In (15)

• Statistical learning based on Markovian data maximal deviation inequalities and learning rates
• Generalization ability of online pairwise support vector machine
• SVM-boosting based on Markov resampling: theory and algorithm
• Generalization bounds for non-stationary mixing processes
• Sampling and empirical risk minimization
• Empirical risk minimization and complexity of dynamical models
• Simpler PAC-Bayesian bounds for hostile data
• Discrepancy-based theory and algorithms for forecasting non-stationary time series
• Stochastic online convex optimization. Application to probabilistic time series forecasting
• Can entropy characterize performance of online algorithms?
• Optimal learning with Bernstein Online Aggregation
• Title not available (Why is that?)
• Prediction of time series by statistical learning: general losses and fast rates
• A generalization bound of deep neural networks for dependent data
• On biased random walks, corrupted intervals, and learning under adversarial design

This page was built for publication: The Generalization Ability of Online Algorithms for Dependent Data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989484)