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

2025/05/12 by Julian Rodemann, Rodemann, Julian, J.R. Bailie +1 · 3 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Methodology (stat.ME) #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2505.07367

openalex publication_date 2025/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Revisiting the Predictability of Performative, Social Events
• Distributionally Robust Performative Prediction
• Towards Bayesian Data Selection
• Statistical Multicriteria Benchmarking via the GSD-Front
• Semi-Supervised Learning guided by the Generalized Bayes Rule under Soft Revision
• Domain Generalisation via Imprecise Learning
• Credal Learning Theory
• Fair Wasserstein Coresets
• PPI++: Efficient Prediction-Powered Inference
• Bayesian Active Learning in the Presence of Nuisance Parameters
• Cross-Prediction-Powered Inference
• Pseudo Label Selection is a Decision Problem
• Robust Statistical Comparison of Random Variables with Locally Varying Scale of Measurement
• Scaling Data-Constrained Language Models
• Approximately Bayes-Optimal Pseudo Label Selection
• Prediction-Powered Inference
• Game-theoretic statistics and safe anytime-valid inference
• Statistical Comparisons of Classifiers by Generalized Stochastic Dominance
• Training Subset Selection for Weak Supervision
• Performative Power
• Bounding Kolmogorov distances through Wasserstein and related integral probability metrics
• Outlier-robust subsampling techniques for persistent homology
• Outside the Echo Chamber: Optimizing the Performative Risk
• In Defense of Pseudo-Labeling: An Uncertainty-Aware Pseudo-label Selection Framework for Semi-Supervised Learning
• Performative Prediction in a Stateful World
• Performative Prediction
• Pseudo-Labeling and Confirmation Bias in Deep Semi-Supervised Learning
• Complex sampling designs: uniform limit theorems and applications
• Differentiability of the argmin function and a minimum principle for semiconcave subsolutions
• Distributionally Robust Logistic Regression
• Data-driven Distributionally Robust Optimization Using the Wasserstein\n Metric: Performance Guarantees and Tractable Reformulations
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• An Information-Theoretic Analysis of Thompson Sampling
• Algorithms for multi-armed bandit problems
• On the rate of convergence in Wasserstein distance of the empirical\n measure
• Domain Generalization via Invariant Feature Representation
• Statistical Learning Theory: Models, Concepts, and Results
• Strategy Selection in Influence Diagrams using Imprecise Probabilities
• Concentration of Measure and Isoperimetric Inequalities in Product\n Spaces
• Concentration of measure and isoperimetric inequalities in product spaces
• A Generalization of Sampling Without Replacement from a Finite Universe
• Sample Selection Bias as a Specification Error

Cited by

• Performative Learning Theory
• Efficient Generalization via Multimodal Co-Training under Data Scarcity and Distribution Shift
• When Do Credal Sets Stabilize? Fixed-Point Theorems for Credal Set Updates

Related

• Reciprocal Learning
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Chaining Mutual Information and Tightening Generalization Bounds
• Understanding Generalization via Leave-One-Out Conditional Mutual Information
• Statistical and Algorithmic Insights for Semi-supervised Learning with Self-training