Cover Image

Optimal Mistake Bounds for Transductive Online Learning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chase, Zachary, Hanneke, Steve, Moran, Shay, Shafer, Jonathan
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Optimal Sauer Lemma Over $k$-ary Alphabets
by: Hanneke, Steve, et al.
Published: (2026)

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
by: Fioravanti, Simone, et al.
Published: (2024)

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

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

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

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

Agnostic Online Learning and Excellent Sets
by: Malliaris, Maryanthe, et al.
Published: (2021)

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

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

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

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

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

Private List Learnability vs. Online List Learnability
by: Hanneke, Steve, et al.
Published: (2025)

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

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

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

The unstable formula theorem revisited via algorithms
by: Malliaris, Maryanthe, et al.
Published: (2022)

On the Learning Curves of Revenue Maximization
by: Hanneke, Steve, et al.
Published: (2026)

Adversarial Resilience in Sequential Prediction via Abstention
by: Goel, Surbhi, et al.
Published: (2023)

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

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

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

Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
by: Cohen, Alon, 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)

Online Set Learning from Precision and Recall Feedback
by: Cohen, Lee, et al.
Published: (2026)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
by: Dmitriev, Daniil, et al.
Published: (2024)

Optimal Reconstruction from Linear Queries
by: Filmus, Yuval, et al.
Published: (2026)

Which Algorithms Have Tight Generalization Bounds?
by: Gastpar, Michael, et al.
Published: (2024)

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

Bounds on the price of feedback for mistake-bounded online learning
by: Geneson, Jesse, et al.
Published: (2024)

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

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

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

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

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

Improved Generalization Bounds for Transductive Learning by Transductive Local Complexity and Its Applications
by: Yang, Yingzhen
Published: (2023)

Theoretical Insights into Line Graph Transformation on Graph Learning
by: Yang, Fan, et al.
Published: (2024)