Cover Image

Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

Fuente: arXiv

Saved in:

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

Similar Items

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

Sample Compression Scheme Reductions
by: Attias, Idan, et al.
Published: (2024)

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

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

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

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

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

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

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

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

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

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

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

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

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

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

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

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

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

Optimal Mistake Bounds for Transductive Online Learning
by: Chase, Zachary, 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)

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)

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)

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

Adaptive Sample Aggregation In Transfer Learning
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 Rates of Empirical Risk Minimization
by: Hanneke, Steve, et al.
Published: (2024)

Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs
by: Arnaboldi, Luca, et al.
Published: (2024)

Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
by: Yang, Zixian, et al.
Published: (2025)

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

Individual Regret in Cooperative Stochastic Multi-Armed Bandits
by: Barnea, Idan, et al.
Published: (2024)

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

Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff
by: Qian, Jian, et al.
Published: (2024)

Private List Learnability vs. Online List Learnability
by: Hanneke, Steve, 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)

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