CS Paper Radar

A Sharp Dynamic Haussler Lemma

Shihao Shao, Dacheng Tao

cs.LG cs.DSmath.CO ·submitted 2026-10-21 15:40 UTC · v2
theory

Abstract

Haussler's covering lemma (JCTA 1995) gives the sharp $(C/δ)^d$ metric-entropy bound for binary VC classes under normalized $\ell_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized $\ell_p$, for every $1\le p<\infty$. Writing $d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$, we obtain a global dynamic cover of size at most $(C/\varepsilon^p)^d$ for every horizon and $0<\varepsilon<1/2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0<\varepsilon<1/4$, a matching worst-case lower bound $(c/\varepsilon)^{pd}$ holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of $p$. For $p=2$, this resolves the horizon-independent sequential $\ell_2$ covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For $p=1$, it gives the sharp $(C/δ)^{\operatorname{Ldim}(\mathcal H)}$ global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.

Comment
53 pages. Sharp asymptotic bounds unchanged. Strengthened fixed-class lower-bound construction, expanded technical overview, and clarified proofs

Closest papers

Nearest neighbours by meaning across the whole index.

Bounded Relative Boundary Implies Narrow DNF Approximation

cs.CC cs.DM ·2026-08-31 ·Chenghua Liu, Boning Meng
theory similarity 0.62
Abstract · 13 pages; proof and exposition revised, Lean repository linked

We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

0.35

Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features

cs.LG stat.ML ·2026-10-31 ·Changlong Wu, Wojciech Szpankowski
similarity 0.61
Abstract · 35 pages, 2 figures

We study hybrid online learning with stochastic features and adversarial labels when the feature distribution is unknown. Prior work gave stochastic sequential covers of log-size $O(d\log^2 T)$ for a general VC class and logarithmic bounds only under stronger star-type structure. We show that finite VC dimension alone is enough: every binary class of VC dimension $d$ admits a distribution-blind exact cover with log-size $O(d\log T+\log(1/δ))$, matching the worst-case $Ω(d\log(T/d))$ dependence on the horizon. The key ingredient is a new local cube weight that counts Boolean subcubes incident to each realizable trace. Unlike the equal splits used in earlier constructions, we split mass unevenly according to these cube weights; a coordinate-deletion inequality shows that VC dimension controls the total cost of these splits. This yields, to our knowledge, the first tight $O((d+1)\log T)$ expected worst-case log-loss regret for general VC partitions with unknown i.i.d. features, and an exact polynomial-time implementation for planar affine halfspaces. We also show that the binary phenomenon does not extend from VC dimension to pseudo-dimension: a fixed pseudo-dimension-one sigmoid class requires $Ω(\log^2 T)$ bits for uniform sequential approximation at accuracy $1/T$.

0.14

Near-Optimal List Replicability from Littlestone Dimension

cs.LG ·2026-10-23 ·Ari Blondal, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
theory similarity 0.61
Abstract · 14 pages

We study the list replicability number in the realizable PAC learning framework and prove that every concept class $H$ over a countable domain with Littlestone dimension $d$ and dual VC dimension $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. \] This matches the worst-case lower bound of $2^{Ω(d)}$ up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound $\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of $2^{O_ε(d^2)}$ for fixed accuracy $ε>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $ε$. The $2^{O(d\log d)}$ bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The $2^{O(dv^*)}$ bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.

0.19

Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

cs.LG stat.ML ·2026-11-09 ·Shai Ben-David, Steve Hanneke, Farnam Mansouri, Amirreza Shaeiri
theory similarity 0.59
Abstract

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class $C$. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings. Prior work showed that, when $C$ has finite diameter $K$ and VC dimension $d$, deterministic labels can improve the sample complexity upper bound from the classical agnostic guarantee $O(d/\varepsilon^2)$ to $\widetilde{O}(K/\varepsilon)$, but left a large gap between upper and lower bounds. Our main result sharpens this picture. We prove that every class of VC dimension $d$ and finite diameter $K$ is learnable with sample complexity $\widetilde{O}\left( \frac{K^{1/3} \, d^{2/3}}{\varepsilon} \right)$, and we construct classes for which this bound is tight up to logarithmic factors. We also study the online analogue of this problem and show that the minimax regret is again partly controlled by the diameter of the class. Technically, our upper bounds are obtained via memorization-based learning algorithms that exploit the deterministic label structure.

0.07

Private online learning and prediction for Littlestone classes

cs.LG cs.CRstat.ML ·2026-10-05 ·Amartya Sanyal
theory similarity 0.59
Abstract

We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction, the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction, we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension $d$. First, we prove that every $(ε,δ)$-private online learner has a deterministic realisable stream of length $T$ on which the mistake bound is at least $\mathbb E [M_T]= O\left(\frac dε\log^{2/3} T\right)$. In particular, this is the first non-trivial lower in the range $1/T<δ<1/\log T)$ left open in earlier works[SR22,DSS24,LWY24]. Second, we prove that for every class of of Littlestone dimension $d$, there exists an $(ε,δ)$-jointly private predictor with at most $2^{2^{cd^2}}ε^{-2}\log^2(2/(εδ))$ expected mistakes, independently of $T$, for some absolute constant $c>0$. Thus, for every fixed class of finite Littlestone dimension when $δ=Θ(1/\log T)$, private learning requires $O\left(\log^{2/3} T\right)$ expected mistakes, whereas private prediction admits $O(\log\log T^2)$.

0.40

Beyond the Static Barrier for Ordinary Dynamic Approximate Membership

cs.DS cs.CCcs.IT ·2026-08-23 ·Qizhi Chen, Zhebei Shen, Zhehan Yu
theory similarity 0.58
Abstract

We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\varepsilon\in(0,1)$, a capacity-$n$ ordinary dynamic filter over a universe of size $u$, with zero false negatives, pointwise false-positive probability at most $\varepsilon$, arbitrary history dependence, a free public random tape, and at most $H$ bits of persistent state, satisfies \[ H\ge \bigl(\log_2(1/\varepsilon)+a_\varepsilon^{\rm c}\bigr)n-o(n), \] under only $u/n\to\infty$. The constant $a_\varepsilon^{\rm c}$ is an explicit variational threshold obtained by preserving the dependence between the parent accepted mass and the successor reservoir. The structural step is a common-continuation transport lemma. A joint posterior KL bound gives a branch-specific survivor support; the same legal delete--insert word transports that support to one successor state, forcing an accepted reservoir. We then keep the parent outside mass $1-X$ in the conditional-entropy argument instead of replacing it by $1-\varepsilon$. This yields a two-variable analytic envelope, with no selected thresholds, dyadic witnesses, or numerical assumptions.

0.23

Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes

cs.CG ·2026-10-01 ·Eunku Park
theory similarity 0.58
Abstract

We study coresets for farthest-point queries in hyperbolic space. Given a nonempty finite set $P \subset \mathbb{H}^D$ and $0<\varepsilon \le 1$, we seek a coreset $P_{\varepsilon} \subseteq P$ whose farthest distance from every query point underestimates that of $P$ by at most an additive $\varepsilon$ and retains at least a $1-\varepsilon$ fraction of it. For every fixed $D \ge 2$, we prove that the optimal worst-case coreset size is $Θ\bigl(\varepsilon^{-(D-1)/2}\bigr)$. Our main geometric ingredient is an exact reduction from hyperbolic queries to an upper envelope on the ideal boundary. In the hyperboloid model, each input point induces a positive boundary-score function whose logarithm gives its asymptotic distance offset along geodesic rays. We define the \emph{ideal-boundary envelope} as the pointwise maximum of these functions and prove that the supremum additive loss over all queries equals the maximum logarithmic gap between the input and coreset envelopes. For the upper bound, we move the minimum-enclosing-ball center to the origin and normalize the spatial coordinates, obtaining a bounded Euclidean point set whose boundary envelope is bounded away from zero. A standard Euclidean kernel then approximates all directional score maxima simultaneously, and the structure theorem yields both guarantees. For the lower bound, a spherical packing on a fixed-radius hyperbolic sphere, together with antipodal queries and the hyperbolic cosine law, makes every input point indispensable, matching the upper bound even for either guarantee separately.

0.36

VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning

cs.LG stat.MLmath.DG ·2026-11-09 ·Gokul Bhusal, Delanna Do, Ekaterina Merkurjev, Kevin Miller, Stephan Wojtowytsch
theory similarity 0.58
Abstract · 19 pages + appendices

We compute the VC-dimension of metric ball classifiers in the model spaces of Riemannian geometry (Euclidean, spherical, hyperbolic) and present upper and lower bounds on the VC-dimension of metric balls in several other situations, including general normed vector spaces (potentially infinite VC-dimension), vector spaces with $\ell^p$-norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for $p=1$), flat tori, and general Riemannian manifolds (arbitrarily large VC-dimension after a conformal change). In several situations where the VC-dimension is large or even infinite, we prove generalization bounds under additional assumptions on the data distribution using covering arguments. Both in the VC-dimension and covering setting, we consider data on low-dimensional subsets of high-dimensional Euclidean spaces. As an application, we consider coverage-based algorithms in active learning.

0.29