We study distributionally robust PAC learning for the $0$--$1$-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order $k>1$ and radius $ρ\geq 0$. For hypothesis classes with VC dimension $d$, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors.
arXiv:2609.24260v1 Announce Type: cross
Abstract: We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distrib...
By Steve Hanneke, Amirreza Shaeiri
We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over $\mathcal{X} \times \{0,1\}$, as in clas...
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.
By Guangjian Zhang
arXiv:2609. 12590v1 Announce Type: cross Abstract: We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension.
By Weiming Ou, Xiao Wang
arXiv:2606. 29331v1 Announce Type: new Abstract: Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth.
By \c{S}uayp Talha Kocabay, Talha R\"uzgar Akku\c{s}, Kerem Yal\c{c}{\i}n
arXiv:2602. 20971v3 Announce Type: replace-cross Abstract: Bubeck and Selke (2021) propose the connection between the Law of Robustness and robust generalization error as an open problem.
By Mihir More, Aritra Das, Jaee Ponde, Himadri Mandal, Vishnu Varadarajan, Debayan Gupta
arXiv:2608. 06363v1 Announce Type: cross Abstract: Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$.
By Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
arXiv:2607. 16966v1 Announce Type: cross Abstract: Estimating entropy from samples is fundamental in information theory and property testing.
By Arman Adibi, Piotr Krysta
arXiv:2608.24098v1 Announce Type: new
Abstract: Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a $\gamma...
By Pahan Dewasurendra
arXiv:2608. 10869v1 Announce Type: new 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.
By Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
arXiv:2004. 05813v3 Announce Type: replace-cross Abstract: Suppose that we are given independent, identically distributed random samples $x_1,\cdots,x_n$ from a mixture at most $k$ many $d$-dimensional spherical Gaussian distributions $\mu_1,\cdots,\mu_{k_0}$ of identical and known variance $\sigma^2$ in each coordinate, such that the minimum $\ell^2$ distance between two distinct centers $y_l$ and $y_j$ is greater than $2\Delta\sigma \min\{\sqrt{d},\sqrt k\}$, where $\Delta>C_0$, and $C_0$ is a sufficiently large universal constant.
By Somnath Chakraborty, Hariharan Narayanan