Online-to-PAC Conversions: Generalization Bounds via Regret Analysis

• URL: http://arxiv.org/abs/2305.19674v2
• Date: Thu, 17 Oct 2024 10:51:50 GMT
• Title: Online-to-PAC Conversions: Generalization Bounds via Regret Analysis
• Authors: Gábor Lugosi, Gergely Neu,
• Abstract summary: 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.
• Score: 13.620177497267791
• License:
• Abstract: We present a new framework for deriving bounds on the generalization bound of statistical learning algorithms from the perspective of online learning. Specifically, we construct an online learning game called the "generalization game", where an online learner is trying to compete with a fixed statistical learning algorithm in predicting the sequence of generalization gaps on a training set of i.i.d. data points. We establish a connection between the online and statistical learning setting by showing 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, up to a martingale concentration term that is independent of the complexity of the statistical learning method. This technique allows us to recover several standard generalization bounds including a range of PAC-Bayesian and information-theoretic guarantees, as well as generalizations thereof.

Related papers

• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• An Information-Theoretic Approach to Generalization Theory [27.87324770020133]
  We analyze information-theoretic bounds that quantify the dependence between a learning algorithm and the training data. We show that algorithms with a bounded maximal leakage guarantee generalization even with a constant privacy parameter.
  arXiv  Detail & Related papers  (2024-08-20T10:08:21Z)
• Generalization bounds for mixing processes via delayed online-to-PAC conversions [9.763215134790478]
  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.
  arXiv  Detail & Related papers  (2024-06-18T13:31:15Z)
• 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)
• Zero-Shot Generalization during Instruction Tuning: Insights from Similarity and Granularity [84.12126298229866]
  We show that zero-shot generalization during instruction tuning happens very early. We also show that encountering highly similar and fine-grained training data earlier during instruction tuning, without the constraints of defined "tasks", enables better generalization. For the first time, we show that zero-shot generalization during instruction tuning is a form of similarity-based generalization between training and test data at the instance level.
  arXiv  Detail & Related papers  (2024-06-17T16:40:21Z)
• Generalization Bounds for Dependent Data using Online-to-Batch Conversion [0.6144680854063935]
  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.
  arXiv  Detail & Related papers  (2024-05-22T14:07:25Z)
• An MRP Formulation for Supervised Learning: Generalized Temporal Difference Learning Models [20.314426291330278]
  In traditional statistical learning, data points are usually assumed to be independently and identically distributed (i.i.d.) This paper presents a contrasting viewpoint, perceiving data points as interconnected and employing a Markov reward process (MRP) for data modeling. We reformulate the typical supervised learning as an on-policy policy evaluation problem within reinforcement learning (RL), introducing a generalized temporal difference (TD) learning algorithm as a resolution.
  arXiv  Detail & Related papers  (2024-04-23T21:02:58Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI) Contrary to other CMI bounds, our loo-CMI bounds can be computed easily and can be interpreted in connection to other notions such as classical leave-one-out cross-validation. We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning.
  arXiv  Detail & Related papers  (2022-07-01T17:58:29Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)
• A Modern Introduction to Online Learning [15.974402990630402]
  Online learning refers to the framework of minimization of regret under worst-case assumptions. I present first-order and second-order algorithms for online learning with convex losses.
  arXiv  Detail & Related papers  (2019-12-31T08:16:31Z)

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.