Optimistic Rates for Multiclass PAC Learning

• URL: http://arxiv.org/abs/2608.10869v1
• Date: Tue, 11 Aug 2026 12:46:03 GMT
• Title: Optimistic Rates for Multiclass PAC Learning
• Abstract summary: Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct.<n>For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_DS$, the optimal excess risk is known at the two endpoints.<n>We close the gap: at every fixed oracle risk $Lstar$, the optimal excess risk is $widetilde(sqrtLstar d_N/n+d_DS/n)$, uniformly in the alphabet size.
• Score: 39.91890433860882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk is known at the two endpoints ($d_{DS}/n$ realizable, $\sqrt{d_N/n}+d_{DS}/n$ agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk $L^\star$, the optimal excess risk is $\widetildeΘ(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size, attained by a learner that knows neither $L^\star$ nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-$k$ compression rule that empirically dominates a comparator $h$ has population risk at most $L(h)+O(\sqrt{L(h)Γ}+Γ)$ with $Γ=(k\log n+\log(1/δ))/n$, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed $L^\star$, by a pair-Assouad scheme calibrated to $L^\star$ and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best $r$-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor $r$ from the known realizable list lower bound.

Related papers

• Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting [20.06940271479014]
  We extend the Side-Channel Existence Theorem to $k$ classes via the per-class decomposition $I(X;Y)=sum_i_i D_mathrmKL(P_Y|i|P_Y)$, with defense cost modelled by per-class Wasserstein-1 constraints.<n>Three results follow: (1) a summation-form MI lower bound over all active classes; (2) a cascade critical cost theorem and a per-class budget corollary, nonzero where the uniform-budget bound vanishes; (3) an accuracy $mathrmAcc*
  arXiv  Detail & Related papers  (2026-09-06T00:48:40Z)
• Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
  The 2026 disproof of Erds's unit-distance conjecture and Sawin's quantitative refinement show that the maximum number $u(n)$ of unit distances among $n$ planar points can exceed $n1+varepsilon$ for a fixed positive $varepsilon$.<n>This report treats Sawin's parameter selection as a nonlinear integer optimization problem and develops an open-source Python pipeline for certificates involving prime sets $T$ and $S_Q$.
  arXiv  Detail & Related papers  (2026-06-02T10:05:23Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals [38.241216472571786]
  We show that the standard multiclass perceptron requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals.<n>We develop a sharper localization-based framework which leads to error $O(mathrmopt)+$ for $k=3, and error $mathrmpoly(k)mathrmopt+$ for geometrically regulark-class linear classifiers.
  arXiv  Detail & Related papers  (2026-05-20T17:19:30Z)
• Generalized $\mathbb{Z}_p$ toric codes as qudit low-density parity-check codes [5.692499671837265]
  We study two-dimensional translation-invariant CSS stabilizer codes over prime-dimensional qudits on the square lattice under twisted boundary conditions.<n>We find that the best observed $k d2$ at $n$ increases with $p$, with an empirical relation $k d2 = 0.0541, n2ln p + 3.84, n$, compatible with a Bravyi--Poulin--Terhal-type tradeoff when the interaction range grows with system size.
  arXiv  Detail & Related papers  (2026-02-23T18:59:31Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  We study the problem of contextual semi-bandits, where input contexts are mapped into subsets of size $m$ of a collection of $K$ possible actions.<n>Motivated by prototypical applications of contextual bandits, we focus on the $s$-sparse regime.<n>Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors.
  arXiv  Detail & Related papers  (2025-02-13T12:13:25Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  It is shown for the first time that this assumption is not required for convergence and finer results.<n>Rates of convergence are obtained for the standard algorithm and for estimates obtained via the averaging technique of Polyak and Ruppert.<n>Results from numerical experiments illustrate that $beta_theta$ may be large due to a combination of multiplicative noise and Markovian memory.
  arXiv  Detail & Related papers  (2024-05-28T05:11:05Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels. When restricting labels $x_i$ to binary values, the problem is NP-hard. We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
  arXiv  Detail & Related papers  (2021-06-03T07:22:48Z)
• (Locally) Differentially Private Combinatorial Semi-Bandits [26.462686161971803]
  We study Combinatorial Semi-Bandits (CSB) that is an extension of classic Multi-Armed Bandits (MAB) under Differential Privacy (DP) and stronger Local Differential Privacy (LDP) setting.
  arXiv  Detail & Related papers  (2020-06-01T04:23:27Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.