Aug 2026· 2 citations· ⚡ 1 influential· 26 references
Computer ScienceMathematics
TL;DR
This paper settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Gyorfi, and Lugosi.
Abstract
Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<\delta\le 1/2$, with probability at least $1-\delta$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/\delta))}{n}} +\frac{d+\log(1/\delta)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Gy\"orfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].
Let $X=(X_1,\ldots,X_n)$ be independent nonnegative random variables, not necessarily identically distributed. Let $D=(D_0,D_1,\ldots,D_n)\sim\operatorname{Dir}(1,\ldots,1)$ be independent of $X$, and define $K(x)=\mathbb{P}\{\sum_{i=1}^n x_iD_i\le1\}$. We prove that, for every $n\ge1$, whenever $\mathbb{E} X_i\le1$ fo...
This analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate.
Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss· 1 citation· ⚡1
Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log...
In this paper, we study the sample complexity of the empirical plug-in estimator for the $2$-Gromov-Wasserstein distance $D_2$ between compactly supported probability measures on Euclidean spaces. Let $\mu$ and $\nu$ be supported on compact subsets of $\mathbb{R}^{d_x}$ and $\mathbb{R}^{d_y}$, respectively, and let $\w...
Pui-Kuen Leung, Riku Okada, Samuel Lok-Hei Wong· 0 citations
Given observations $\mathbf x=(x_1,\dots,x_n)$, Gaffke (2005) defined \[ K_n(\mathbf x)=\mathbb{P}_{\mathbf D}\!\left\{\sum_{i=1}^n x_iD_i\le 1\right\}, \qquad (D_0,D_1,\ldots,D_n)\sim\mathrm{Dirichlet}(1,\ldots,1), \] and conjectured that it is a $p$-value whenever the inputs are independent e-values. Recently, Vlassi...
Jiahao Ming, Aaditya Ramdas, Yi Shen et al.· arXiv.org· 4 citations· ⚡1
This work improves the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise.
Steve Hanneke, Hongao Wang, Mingyue Xu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
