Generalization Bounds for Dependent Data using Online-to-Batch Conversion
- URL: http://arxiv.org/abs/2405.13666v1
- Date: Wed, 22 May 2024 14:07:25 GMT
- Title: Generalization Bounds for Dependent Data using Online-to-Batch Conversion
- Authors: Sagnik Chatterjee, Manuj Mukherjee, Alhad Sethi,
- Abstract summary: We show that the generalization error of statistical learners in the dependent data setting is equivalent to the generalization error of statistical learners in the i.i.d. setting.
Our proof techniques involve defining a new notion of stability of online learning algorithms based on Wasserstein.
- Score: 0.6144680854063935
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we give generalization bounds of statistical learning algorithms trained on samples drawn from a dependent data source, both in expectation and with high probability, using the Online-to-Batch conversion paradigm. We show that the generalization error of statistical learners in the dependent data setting is equivalent to the generalization error of statistical learners in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process and is independent of the complexity of the statistical learner. Our proof techniques involve defining a new notion of stability of online learning algorithms based on Wasserstein distances and employing "near-martingale" concentration bounds for dependent random variables to arrive at appropriate upper bounds for the generalization error of statistical learners trained on dependent data.
Related papers
- Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective [9.867914513513453]
We present an oracle-efficient algorithm capable of achieving small-loss bounds with improved rates in greater generality than previous work.
We also present a variant for differentially private learning that attains optimal rates, again under our separation condition.
arXiv Detail & Related papers (2025-02-14T16:52:50Z) - Data-dependent and Oracle Bounds on Forgetting in Continual Learning [7.903539618132858]
In continual learning, knowledge must be preserved and re-used between tasks.
We provide both data-dependent and oracle upper bounds that apply regardless of model and algorithm choice.
We derive an algorithm based on our bounds and demonstrate empirically that our approach yields tight bounds on forgetting for several continual learning problems.
arXiv Detail & Related papers (2024-06-13T17:50:51Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
We provide the first oracle-efficient, no-regret algorithms in this setting.
We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
arXiv Detail & Related papers (2022-02-09T19:22:34Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
Pairwise learning refers to learning tasks where the loss function depends on a pair instances.
Online descent (OGD) is a popular approach to handle streaming data in pairwise learning.
In this paper, we propose simple and online descent to methods for pairwise learning.
arXiv Detail & Related papers (2021-11-23T18:10:48Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states.
We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
arXiv Detail & Related papers (2021-08-22T16:00:45Z) - Learning Expected Emphatic Traces for Deep RL [32.984880782688535]
Off-policy sampling and experience replay are key for improving sample efficiency and scaling model-free temporal difference learning methods.
We develop a multi-step emphatic weighting that can be combined with replay, and a time-reversed $n$-step TD learning algorithm to learn the required emphatic weighting.
arXiv Detail & Related papers (2021-07-12T13:14:03Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
We study the fundamental online $k$-server problem in a learning-augmented setting.
We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
arXiv Detail & Related papers (2021-03-02T11:04:33Z) - Batch Value-function Approximation with Only Realizability [17.692408242465763]
We make progress in a long-standing problem of batch reinforcement learning (RL): learning $Qstar$ from an exploratory dataset.
Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure.
We also discuss how BVFT can be applied to model selection among other extensions and open problems.
arXiv Detail & Related papers (2020-08-11T20:09:37Z) - A Constraint-Based Algorithm for the Structural Learning of
Continuous-Time Bayesian Networks [70.88503833248159]
We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks.
We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
arXiv Detail & Related papers (2020-07-07T07:34:09Z) - Tracking Performance of Online Stochastic Learners [57.14673504239551]
Online algorithms are popular in large-scale learning settings due to their ability to compute updates on the fly, without the need to store and process data in large batches.
When a constant step-size is used, these algorithms also have the ability to adapt to drifts in problem parameters, such as data or model properties, and track the optimal solution with reasonable accuracy.
We establish a link between steady-state performance derived under stationarity assumptions and the tracking performance of online learners under random walk models.
arXiv Detail & Related papers (2020-04-04T14:16:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.