Buchumschlag

An Optimal Sauer Lemma Over $k$-ary Alphabets

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hanneke, Steve, Meng, Qinglin, Moran, Shay, Shaeiri, Amirreza
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Machine Learning Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

Optimal Mistake Bounds for Transductive Online Learning
von: Chase, Zachary, et al.
Veröffentlicht: (2025)

Multiclass Transductive Online Learning
von: Hanneke, Steve, et al.
Veröffentlicht: (2024)

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
von: Fioravanti, Simone, et al.
Veröffentlicht: (2024)

A Theory of Universal Agnostic Learning
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
von: Filmus, Yuval, et al.
Veröffentlicht: (2023)

Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

List Sample Compression and Uniform Convergence
von: Hanneke, Steve, et al.
Veröffentlicht: (2024)

Data Selection for ERMs
von: Hanneke, Steve, et al.
Veröffentlicht: (2025)

On the ERM Principle in Meta-Learning
von: Alon, Yannay, et al.
Veröffentlicht: (2024)

Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
von: Filmus, Yuval, et al.
Veröffentlicht: (2024)

The unstable formula theorem revisited via algorithms
von: Malliaris, Maryanthe, et al.
Veröffentlicht: (2022)

Agnostic Online Learning and Excellent Sets
von: Malliaris, Maryanthe, et al.
Veröffentlicht: (2021)

Adversarial Resilience in Sequential Prediction via Abstention
von: Goel, Surbhi, et al.
Veröffentlicht: (2023)

Private List Learnability vs. Online List Learnability
von: Hanneke, Steve, et al.
Veröffentlicht: (2025)

On the Learning Curves of Revenue Maximization
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

Dual VC Dimension Obstructs Sample Compression by Embeddings
von: Chase, Zachary, et al.
Veröffentlicht: (2024)

Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
von: Cohen, Alon, et al.
Veröffentlicht: (2025)

Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts
von: Vanderbush, Knut, et al.
Veröffentlicht: (2026)

Constructing $k$-ary Orientable Sequences with Asymptotically Optimal Length
von: Gabrić, Daniel, et al.
Veröffentlicht: (2024)

Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
von: da Cunha, Arthur, et al.
Veröffentlicht: (2023)

Optimal Reconstruction from Linear Queries
von: Filmus, Yuval, et al.
Veröffentlicht: (2026)

Black-White Cell Capacity in $k$-ary Words and Permutations
von: Fried, Sela
Veröffentlicht: (2025)

On Characterizing Learnability for Adversarial Noisy Bandits
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

Universal Multiclass Transductive Online Learning
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

When More Data Doesn't Help: Limits of Adaptation in Multitask Learning
von: Hanneke, Steve, et al.
Veröffentlicht: (2026)

The Dimension of Self-Directed Learning
von: Devulapalli, Pramith, et al.
Veröffentlicht: (2024)

Universal rates of ERM for agnostic learning
von: Hanneke, Steve, et al.
Veröffentlicht: (2025)

Learning from Snapshots of Discrete and Continuous Data Streams
von: Devulapalli, Pramith, et al.
Veröffentlicht: (2024)

Universal Rates of Empirical Risk Minimization
von: Hanneke, Steve, et al.
Veröffentlicht: (2024)

Adversarially Robust PAC Learnability of Real-Valued Functions
von: Attias, Idan, et al.
Veröffentlicht: (2022)

A Theory of Optimistically Universal Online Learnability for General Concept Classes
von: Hanneke, Steve, et al.
Veröffentlicht: (2025)

The Coverage Depth Problem in DNA Storage Over Small Alphabets
von: Bertuzzo, Matteo, et al.
Veröffentlicht: (2025)

Extremal Problems for the Family of $k$-Strongly Connected Digraphs
von: Wang, Qinglin, et al.
Veröffentlicht: (2026)

Paint cost spectrum of perfect $k$-ary trees
von: Mafunda, Sonwabile, et al.
Veröffentlicht: (2024)

Robustness of the Sauer-Spencer Theorem
von: Allen, Peter, et al.
Veröffentlicht: (2025)

Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees
von: Alston, Brandon, et al.
Veröffentlicht: (2024)

A Complete Characterization of Learnability for Stochastic Noisy Bandits
von: Hanneke, Steve, et al.
Veröffentlicht: (2024)

Approximately Optimal Core Shapes for Tensor Decompositions
von: Ghadiri, Mehrdad, et al.
Veröffentlicht: (2023)

The Optimal Approximation Factor in Density Estimation
von: Bousquet, Olivier, et al.
Veröffentlicht: (2019)