Generalization bounds for mixing processes via delayed online-to-PAC conversions

• URL: http://arxiv.org/abs/2406.12600v1
• Date: Tue, 18 Jun 2024 13:31:15 GMT
• Title: Generalization bounds for mixing processes via delayed online-to-PAC conversions
• Authors: Baptiste Abeles, Eugenio Clerico, Gergely Neu,
• Abstract summary: We study the generalization error of statistical learning algorithms in a non-i.i.d. setting. We develop an analytic framework for this scenario based on a reduction to online learning with delayed feedback.
• Score: 9.763215134790478
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the generalization error of statistical learning algorithms in a non-i.i.d. setting, where the training data is sampled from a stationary mixing process. We develop an analytic framework for this scenario based on a reduction to online learning with delayed feedback. In particular, we show that the existence of an online learning algorithm with bounded regret (against a fixed statistical learning algorithm in a specially constructed game of online learning with delayed feedback) implies low generalization error of said statistical learning method even if the data sequence is sampled from a mixing time series. The rates demonstrate a trade-off between the amount of delay in the online learning game and the degree of dependence between consecutive data points, with near-optimal rates recovered in a number of well-studied settings when the delay is tuned appropriately as a function of the mixing time of the process.

Related papers

• Structured Prediction in Online Learning [66.36004256710824]
  We study a theoretical and algorithmic framework for structured prediction in the online learning setting. We show that our algorithm is a generalisation of optimal algorithms from the supervised learning setting. We consider a second algorithm designed especially for non-stationary data distributions, including adversarial data.
  arXiv  Detail & Related papers  (2024-06-18T07:45:02Z)
• Online Distributed Learning with Quantized Finite-Time Coordination [0.4910937238451484]
  In our setting a set of agents need to cooperatively train a learning model from streaming data. We propose a distributed algorithm that relies on a quantized, finite-time coordination protocol. We analyze the performance of the proposed algorithm in terms of the mean distance from the online solution.
  arXiv  Detail & Related papers  (2023-07-13T08:36:15Z)
• Online-to-PAC Conversions: Generalization Bounds via Regret Analysis [13.620177497267791]
  We construct an online learning game called the "generalization game" We show that the existence of an online learning algorithm with bounded regret in this game implies a bound on the generalization error of the statistical learning algorithm.
  arXiv  Detail & Related papers  (2023-05-31T09:15:39Z)
• OFedQIT: Communication-Efficient Online Federated Learning via Quantization and Intermittent Transmission [7.6058140480517356]
  Online federated learning (OFL) is a promising framework to collaboratively learn a sequence of non-linear functions (or models) from distributed streaming data. We propose a communication-efficient OFL algorithm (named OFedQIT) by means of a quantization and an intermittent transmission. Our analysis reveals that OFedQIT successfully addresses the drawbacks of OFedAvg while maintaining superior learning accuracy.
  arXiv  Detail & Related papers  (2022-05-13T07:46:43Z)
• Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback [36.05851452151107]
  federated learning (FL) systems need to sample a subset of clients that are involved in each round of training. Despite its importance, there is limited work on how to sample clients effectively. We show how our sampling method can improve the convergence speed of optimization algorithms.
  arXiv  Detail & Related papers  (2021-12-28T23:50:52Z)
• On Covariate Shift of Latent Confounders in Imitation and Reinforcement Learning [69.48387059607387]
  We consider the problem of using expert data with unobserved confounders for imitation and reinforcement learning. We analyze the limitations of learning from confounded expert data with and without external reward. We validate our claims empirically on challenging assistive healthcare and recommender system simulation tasks.
  arXiv  Detail & Related papers  (2021-10-13T07:31:31Z)
• Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning [90.59143158534849]
  The recent emergence of reinforcement learning has created a demand for robust statistical inference methods. Existing methods for statistical inference in online learning are restricted to settings involving independently sampled observations. The online bootstrap is a flexible and efficient approach for statistical inference in linear approximation algorithms, but its efficacy in settings involving Markov noise has yet to be explored.
  arXiv  Detail & Related papers  (2021-08-08T18:26:35Z)
• Contrastive learning of strong-mixing continuous-time stochastic processes [53.82893653745542]
  Contrastive learning is a family of self-supervised methods where a model is trained to solve a classification task constructed from unlabeled data. We show that a properly constructed contrastive learning task can be used to estimate the transition kernel for small-to-mid-range intervals in the diffusion case.
  arXiv  Detail & Related papers  (2021-03-03T23:06:47Z)
• Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity [57.275753974812666]
  Federated learning involves learning from data samples distributed across a network of clients while the data remains local. In this paper, we propose a novel straggler-resilient federated learning method that incorporates statistical characteristics of the clients' data to adaptively select the clients in order to speed up the learning procedure.
  arXiv  Detail & Related papers  (2020-12-28T19:21:14Z)
• Learning low-frequency temporal patterns for quantitative trading [0.0]
  We consider the viability of a modularised online machine learning framework to learn signals in low-frequency financial time series data. The framework is proved on daily sampled closing time-series data from JSE equity markets.
  arXiv  Detail & Related papers  (2020-08-12T11:59:15Z)
• 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.