Generalization Bounds and Stopping Rules for Learning with Self-Selected Data

• URL: http://arxiv.org/abs/2505.07367v1
• Date: Mon, 12 May 2025 09:06:39 GMT
• Title: Generalization Bounds and Stopping Rules for Learning with Self-Selected Data
• Authors: Julian Rodemann, James Bailie,
• Abstract summary: We prove universal generalization bounds for reciprocal learning using covering numbers and Wasserstein ambiguity sets.<n>We illustrate our bounds and stopping rules for reciprocal learning's special case of semi-supervised learning.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many learning paradigms self-select training data in light of previously learned parameters. Examples include active learning, semi-supervised learning, bandits, or boosting. Rodemann et al. (2024) unify them under the framework of "reciprocal learning". In this article, we address the question of how well these methods can generalize from their self-selected samples. In particular, we prove universal generalization bounds for reciprocal learning using covering numbers and Wasserstein ambiguity sets. Our results require no assumptions on the distribution of self-selected data, only verifiable conditions on the algorithms. We prove results for both convergent and finite iteration solutions. The latter are anytime valid, thereby giving rise to stopping rules for a practitioner seeking to guarantee the out-of-sample performance of their reciprocal learning algorithm. Finally, we illustrate our bounds and stopping rules for reciprocal learning's special case of semi-supervised learning.

Related papers

• Sample Compression for Continual Learning [4.354838732412981]
  Continual learning algorithms aim to learn from a sequence of tasks, making the training distribution non-stationary.<n>We present a new method called 'Continual Pick-to-Learn' (CoP2L), which is able to retain the most representative samples for each task in an efficient way.
  arXiv  Detail & Related papers  (2025-03-13T16:05:56Z)
• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Reciprocal Learning [0.0]
  We show that a wide array of machine learning algorithms are specific instances of one single paradigm: reciprocal learning. We introduce reciprocal learning as a generalization of these algorithms using the language of decision theory. We find that reciprocal learning algorithms converge at linear rates to an approximately optimal model under relatively mild assumptions on the loss function.
  arXiv  Detail & Related papers  (2024-08-12T16:14:52Z)
• Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical [66.57396042747706]
  Complementary-label learning is a weakly supervised learning problem. We propose a consistent approach that does not rely on the uniform distribution assumption. We find that complementary-label learning can be expressed as a set of negative-unlabeled binary classification problems.
  arXiv  Detail & Related papers  (2023-11-27T02:59:17Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• An Information-theoretical Approach to Semi-supervised Learning under Covariate-shift [24.061858945664856]
  A common assumption in semi-supervised learning is that the labeled, unlabeled, and test data are drawn from the same distribution. We propose an approach for semi-supervised learning algorithms that is capable of addressing this issue. Our framework also recovers some popular methods, including entropy minimization and pseudo-labeling.
  arXiv  Detail & Related papers  (2022-02-24T14:25:14Z)
• Universal Online Learning with Unbounded Losses: Memory Is All You Need [10.839359285994636]
  A given learning rule is said to be optimistically universal if it achieves a low long-run average loss. Hanke posed as an open problem whether, for every unbounded loss, the family of processes admitting universal learning are precisely those having a finite number of distinct values. As a consequence, this also offers a dramatically simpler formulation of an optimistically universal learning rule for any unbounded loss.
  arXiv  Detail & Related papers  (2022-01-21T22:03:18Z)
• Improving Self-supervised Learning with Automated Unsupervised Outlier Arbitration [83.29856873525674]
  We introduce a lightweight latent variable model UOTA, targeting the view sampling issue for self-supervised learning. Our method directly generalizes to many mainstream self-supervised learning approaches.
  arXiv  Detail & Related papers  (2021-12-15T14:05:23Z)
• Towards optimally abstaining from prediction [22.937799541125607]
  A common challenge across all areas of machine learning is that training data is not distributed like test data. We consider a model where one may abstain from predicting, at a fixed cost. Our work builds on a recent abstention algorithm of Goldwasser, Kalais, and Montasser ( 2020) for transductive binary classification.
  arXiv  Detail & Related papers  (2021-05-28T21:44:48Z)
• 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)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  We consider a class of bandit algorithms that implement a regularized version of the well-known OFUL algorithm, where the regularization is a square euclidean distance to a bias vector. We show both theoretically and experimentally, that when the number of tasks grows and the variance of the task-distribution is small, our strategies have a significant advantage over learning the tasks in isolation.
  arXiv  Detail & Related papers  (2020-05-18T08:41:39Z)

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.