Cover Image

Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cohen, Alon, Erez, Liad, Hanneke, Steve, Koren, Tomer, Mansour, Yishay, Moran, Shay, Zhang, Qian
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Real Price of Bandit Information in Multiclass Classification
by: Erez, Liad, et al.
Published: (2024)

Fast Rates for Bandit PAC Multiclass Classification
by: Erez, Liad, et al.
Published: (2024)

The Sample Complexity of Multiclass and Sparse Contextual Bandits
by: Erez, Liad, et al.
Published: (2026)

From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards
by: Erez, Liad, et al.
Published: (2025)

Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
by: Sherman, Uri, et al.
Published: (2025)

Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
by: Levy, Orin, et al.
Published: (2025)

Regret Minimization and Convergence to Equilibria in General-sum Markov Games
by: Erez, Liad, et al.
Published: (2022)

Rate-Optimal Policy Optimization for Linear Markov Decision Processes
by: Sherman, Uri, et al.
Published: (2023)

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

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

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

The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization
by: Schliserman, Matan, et al.
Published: (2024)

Learnability Gaps of Strategic Classification
by: Cohen, Lee, et al.
Published: (2024)

Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
by: Sherman, Uri, et al.
Published: (2025)

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

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

Probably Approximately Precision and Recall Learning
by: Cohen, Lee, et al.
Published: (2024)

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

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

Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
by: Schliserman, Matan, et al.
Published: (2025)

The Hidden Cost of Approximation in Online Mirror Descent
by: Schlisselberg, Ofir, et al.
Published: (2025)

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

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

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

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

Cost-Aware Learning
by: Mohri, Clara, et al.
Published: (2026)

A Theoretical Framework for Statistical Evaluability of Generative Models
by: Aiyer, Shashaank, et al.
Published: (2026)

Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation
by: Levy, Orin, et al.
Published: (2026)

Eluder-based Regret for Stochastic Contextual MDPs
by: Levy, Orin, et al.
Published: (2022)

Learning-Augmented Algorithms with Explicit Predictors
by: Elias, Marek, et al.
Published: (2024)

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

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

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

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

Optimal Mistake Bounds for Transductive Online Learning
by: Chase, Zachary, et al.
Published: (2025)

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
by: Aiyer, Shashaank, et al.
Published: (2026)

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

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

Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
by: Chornomaz, Bogdan, et al.
Published: (2025)

Learning from Equivalence Queries, Revisited
by: Braverman, Mark, et al.
Published: (2026)