Cover Image

Sample Compression Scheme Reductions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Attias, Idan, Hanneke, Steve, Ramaswami, Arvind
Format:	Preprint
Published:	2024
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
by: Attias, Idan, et al.
Published: (2026)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
by: Attias, Idan, et al.
Published: (2025)

Agnostic Sample Compression Schemes for Regression
by: Attias, Idan, et al.
Published: (2018)

Adversarially Robust PAC Learnability of Real-Valued Functions
by: Attias, Idan, et al.
Published: (2022)

A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
by: Attias, Idan, et al.
Published: (2022)

Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
by: Hanneke, Steve, et al.
Published: (2026)

Optimal Learners for Realizable Regression: PAC Learning and Online Learning
by: Attias, Idan, et al.
Published: (2023)

List Sample Compression and Uniform Convergence
by: Hanneke, Steve, et al.
Published: (2024)

Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals
by: Liu, Ziyi, et al.
Published: (2024)

Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
by: Filmus, Yuval, et al.
Published: (2024)

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
by: Filmus, Yuval, et al.
Published: (2023)

Adaptive Sample Aggregation In Transfer Learning
by: Hanneke, Steve, et al.
Published: (2024)

Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
by: Liu, Ziyi, et al.
Published: (2024)

Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
by: Ryabchenko, Alexander, et al.
Published: (2025)

Dual VC Dimension Obstructs Sample Compression by Embeddings
by: Chase, Zachary, et al.
Published: (2024)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

The Dimension of Self-Directed Learning
by: Devulapalli, Pramith, et al.
Published: (2024)

Learning from Snapshots of Discrete and Continuous Data Streams
by: Devulapalli, Pramith, et al.
Published: (2024)

Universal Rates of Empirical Risk Minimization
by: Hanneke, Steve, et al.
Published: (2024)

On Characterizing Learnability for Adversarial Noisy Bandits
by: Hanneke, Steve, et al.
Published: (2026)

Universal rates of ERM for agnostic learning
by: Hanneke, Steve, et al.
Published: (2025)

Universal Multiclass Transductive Online Learning
by: Hanneke, Steve, et al.
Published: (2026)

A Theory of Optimistically Universal Online Learnability for General Concept Classes
by: Hanneke, Steve, et al.
Published: (2025)

When More Data Doesn't Help: Limits of Adaptation in Multitask Learning
by: Hanneke, Steve, et al.
Published: (2026)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
by: Ryabchenko, Alexander, et al.
Published: (2026)

A Complete Characterization of Learnability for Stochastic Noisy Bandits
by: Hanneke, Steve, et al.
Published: (2024)

A Theory of Universal Agnostic Learning
by: Hanneke, Steve, et al.
Published: (2026)

Uniform Convergence Beyond Glivenko-Cantelli
by: Devale, Tanmay, et al.
Published: (2025)

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
by: Hanneke, Steve, et al.
Published: (2026)

Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
by: Attias, Idan, et al.
Published: (2024)

Positive Distribution Shift as a Framework for Understanding Tractable Learning
by: Medvedev, Marko, et al.
Published: (2026)

Boosting, Voting Classifiers and Randomized Sample Compression Schemes
by: da Cunha, Arthur, et al.
Published: (2024)

Efficient Agnostic Learning with Average Smoothness
by: Hanneke, Steve, et al.
Published: (2023)

Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
by: Cohen, Alon, et al.
Published: (2025)

On the ERM Principle in Meta-Learning
by: Alon, Yannay, et al.
Published: (2024)

Multiclass Transductive Online Learning
by: Hanneke, Steve, et al.
Published: (2024)

Data Selection for ERMs
by: Hanneke, Steve, et al.
Published: (2025)

On Union-Closedness of Language Generation
by: Hanneke, Steve, et al.
Published: (2025)

Proofs as Explanations: Short Certificates for Reliable Predictions
by: Blum, Avrim, et al.
Published: (2025)