arXiv Machine Learning
Aug 4
Optimal Unambiguous DNFs and Alon-Saks-Seymour
arXiv:2608. 02533v1 Announce Type: cross Abstract: We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $\Omega(n^2)$.
The Optimal Sample Complexity of Multiclass and List Learning
arXiv:2604. 24749v2 Announce Type: replace Abstract: While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open.
Related stories
Hugging Face Trending Papers
Aug 3
Optimal Unambiguous DNFs and Alon-Saks-Seymour
We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $Ω(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in certificate complexity to a separation in communication complexity.
arXiv Machine Learning
Jul 22
Fundamental limits of distributed multiclass classification from simple binary decisions
arXiv:2607. 19334v1 Announce Type: cross Abstract: We consider the problem of constructing a $K$-class classifier from the combination of $O(\log K)$ simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task.
arXiv Machine Learning
Aug 4
The No-Clash Teaching Dimension is Bounded by VC Dimension
arXiv:2603. 23561v4 Announce Type: replace-cross Abstract: In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching.
arXiv Machine Learning
Sep 25
Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon
The paper revisits realizable multiclass PAC learning with bandit feedback, correcting a previously claimed lower bound on sample complexity. It introduces a new anchored dimension, “aBDS,” and establishes a constant‑free three‑part lower bound, while also providing tighter upper bounds that eliminate dependence on the total label count. The authors demonstrate that the optimal sample complexity can vary dramatically even among classes with identical dimensional profiles, revealing a confidence direct‑sum phenomenon and a rank‑saturation phase transition.
arXiv Machine Learning
Jul 30
On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry
arXiv:2510. 10101v4 Announce Type: replace Abstract: Understanding the interplay between generalization, expressivity, and the geometry of the input space is a central challenge in graph learning.
arXiv Machine Learning
Jun 29
Surprises in Proper Positive-Only Learning
arXiv:2606. 28309v1 Announce Type: cross Abstract: Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.
arXiv Machine Learning
Aug 6
Sample Complexity of Multicalibration for Multilevel Properties
arXiv:2608. 04288v1 Announce Type: new Abstract: Calibration requires a predictor to be unbiased after conditioning on its own predictions.
arXiv Machine Learning
Aug 27
Two Dimensions Govern Agnostic Multiclass Transductive Learning
arXiv:2608. 25326v1 Announce Type: new Abstract: In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels.
arXiv Machine Learning
Jul 28
Learning Distributions from Multiple Data Providers
arXiv:2607. 24732v1 Announce Type: cross Abstract: Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples.
arXiv Machine Learning
Aug 28
Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
The paper investigates fundamental limits of algorithmic principles in multiclass learning, specifically proper learning and regularization. It shows that learning cannot always be reduced to proper learning even with an enlarged hypothesis class, that proper learners may need a sublinear number of errors that can be arbitrarily large, and that regularization (SRM or local) is not universally sufficient. The authors also provide a positive theory giving sufficient conditions for SRM learnability and a characterization via integrability of revealed preferences.
arXiv Machine Learning
Sep 11
Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
The paper extends the study of relatively smart learning, showing that ERM and any proper consistent learner are relatively smart for binary classification in the distribution‑free setting, achieving a quadratic sample‑complexity blowup. It further demonstrates that semi‑supervised relatively smart learning is possible with only a quadratic blowup in unlabeled data and no blowup in labeled data, though this requires a leave‑most‑out transductive approach and incurs intractability when only an agnostic ERM oracle is available. The results clarify the trade‑offs between sample efficiency, label efficiency, and computational tractability in relatively smart learning.