Generalization Bounds for Dependent Data using Online-to-Batch Conversion

• URL: http://arxiv.org/abs/2405.13666v2
• Date: Wed, 19 Feb 2025 13:27:10 GMT
• Title: Generalization Bounds for Dependent Data using Online-to-Batch Conversion
• Authors: Sagnik Chatterjee, Manuj Mukherjee, Alhad Sethi,
• Abstract summary: We upper bound the generalization error of batch learning algorithms trained on samples drawn from a mixing process. Our work does not require any stability assumptions on the batch learner. We prove that the EWA algorithm, a textbook family of online learning algorithms, satisfies our new notion of stability.
• Score: 0.6144680854063935
• License:
• Abstract: In this work, we upper bound the generalization error of batch learning algorithms trained on samples drawn from a mixing stochastic process (i.e., a dependent data source) both in expectation and with high probability. Unlike previous results by Mohri et al. (2010) and Fu et al. (2023), our work does not require any stability assumptions on the batch learner, which allows us to derive upper bounds for any batch learning algorithm trained on dependent data. This is made possible due to our use of the Online-to-Batch ( OTB ) conversion framework, which allows us to shift the burden of stability from the batch learner to an artificially constructed online learner. We show that our bounds are equal to the bounds in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process. Central to our analysis is a new notion of algorithmic stability for online learning algorithms based on Wasserstein distances of order one. Furthermore, we prove that the EWA algorithm, a textbook family of online learning algorithms, satisfies our new notion of stability. Following this, we instantiate our bounds using the EWA algorithm.

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.