CS Paper Radar

Distribution-Free Halfspace Testing with Samples

Xi Chen, Renato Ferreira Pinto, Nathaniel Harms, Shyamal Patel, Rocco A. Servedio

cs.DS ·submitted 2026-08-11 18:52 UTC · v1
theory

Abstract

We prove a tight $Θ(n/ε)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Proper Agnostic Learning of Halfspaces

cs.DS cs.CCstat.ML ·2026-11-02 ·Anindya De, Elchanan Mossel, Shivam Nadimpalli, Joe Neeman
similarity 0.66
Abstract · 47 pages, 4 figures

We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm1\}^n$. Given query access to an arbitrary function $f:\{\pm1\}^n \to \{\pm1\}$, our algorithm runs in time $\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}$ and outputs a halfspace with error at most $\mathrm{OPT}+\varepsilon$, where $\mathrm{OPT}$ is the error of the best-fitting halfspace for $f$. Previously, even with membership queries, the best known running time was $n^{\mathrm{poly}(1/\varepsilon)}$, achieved by the sample-based algorithm of Kalai, Klivans, Mansour, and Servedio (FOCS 2005). Our algorithm is the first agnostic halfspace learner under the uniform distribution on $\{\pm1\}^n$ whose running time is polynomial in $n$ with an exponent independent of $\varepsilon$. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same $\mathrm{OPT}+\varepsilon$ guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on $\varepsilon$. To our knowledge, this is the first sample-based proper agnostic learner in the Boolean setting with running time $2^{o(n)}$ for every fixed $\varepsilon>0$.

0.33

Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

cs.DS cs.ITstat.ML ·2026-10-08 ·Gautam Kamath
theory similarity 0.61
Abstract

We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde Θ\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde Θ(\log n)$.

0.20

Privacy for Free in Efficient Agnostic Halfspace Learning

cs.LG stat.ML ·2026-11-03 ·Giorgio Racca, Amartya Sanyal, Vikrant Singhal
similarity 0.60
Abstract

We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces. In particular, we study three different settings of agnostic learning: improper learning under Gaussian and log-concave marginals; proper learning under Gaussian marginals; and semi-agnostic learning under Gaussian marginals. In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.

0.15

Near-Linear Lower Bounds for Testing Directed Acyclicity

cs.DS ·2026-11-03 ·Artur Czumaj, Pan Peng, Yuyang Wang
similarity 0.56
Abstract

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

0.24

Preferent Compression Bounds Are Tight

cs.LG eess.SYmath.OCmath.PR ·2026-09-28 ·Dario Paccagnan, Marius Tirlea
published similarity 0.54
Abstract · 14 pages, 6 figures, to appear at the 65th IEEE Conference on Decision and Control (CDC 2026)

The lack of rigorous safety and performance certificates remains a key bottleneck to the deployment of modern learning-based methods. Sample compression has recently emerged as a powerful tool for deriving such certificates, with particularly sharp bounds available for algorithms satisfying a so-called preference property -- also known as stability in the learning theory literature. These bounds find direct application across domains as different as the Scenario Approach, Pick-to-Learn, and Support Vector methods. However, whether they are tight has remained an open problem. In this paper we resolve this question affirmatively and show that the state-of-the-art bound for preferent compressions is provably tight. We establish this by exhibiting an explicit construction based on the uniform distribution and order statistics that attains the bound in the limit. Along the way, we also provide a considerably shorter and more accessible proof of this bound, requiring only elementary counting arguments and no infinite-dimensional duality.

0.35

Multiaccuracy as an Error Benchmark for Learning with Distribution Shift

cs.LG cs.DS ·2026-11-15 ·Konstantinos Stavropoulos
benchmarkposition similarity 0.54
Abstract

Agnostic learning has a well-developed theory of computational and statistical complexity. For learning with distribution shift, even the choice of an appropriate error benchmark remains challenging. Testable learning with distribution shift (TDS) was introduced to develop computational foundations for this setting: using labeled training data and unlabeled test data, the learner must either produce a predictor with low test error or detect distribution shift. However, standard agnostic TDS guarantees allow a constant-factor amplification of the optimum error even when the training and test distributions coincide. They therefore do not directly recover the guarantee of classical agnostic learning. We introduce shift multiaccuracy, a stronger error benchmark inspired by multiaccuracy from algorithmic fairness. This yields a TDS formulation that becomes equivalent to multiaccuracy when there is no shift. Using a recent nontrivial reduction from agnostic learning to multiaccurate prediction from prior work, we obtain the first TDS framework that formally generalizes agnostic learning through an efficient reduction preserving the training marginal. The framework retains existing algorithmic upper bounds and inherits computational lower bounds from agnostic learning. Moreover, we establish a direct connection between our model and identity testing, yielding the first statistical characterization of agnostic TDS learning, in terms of Rademacher complexity. More broadly, we argue that shift multiaccuracy might be of independent interest in unsupervised domain adaptation, as it leads to sharper out-of-distribution generalization guarantees, and can be minimized directly, since its definition does not involve the unobserved test labels.

0.15

Optimal Support Size Testing

cs.IT cs.DSmath.ST ·2026-10-13 ·Qisheng Wang
theory similarity 0.54
Abstract · 12 pages

We present an optimal tester for support size that determines whether an unknown probability distribution is supported on $n$ elements or $\varepsilon$-far away (in total variation distance) with sample complexity $Θ(\frac{n}{\varepsilon\log(n)})$, improving the prior best $O(\frac{n}{\varepsilon\log(n)} \log(\min\{\frac{1}{\varepsilon}, n\}))$ due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.

0.30

Log-optimal two-sample testing by betting

cs.IT math.STstat.MEstat.ML ·2026-11-14 ·Aaditya Ramdas
similarity 0.53
Abstract · 55pgs

For each standard Borel observation space, we construct a single anytime-valid two-sample procedure that is asymptotically log-optimal for every pair of unknown probability laws and every limiting ratio of diverging sample sizes, including zero and infinity. For independent balanced pairs, the optimal log-wealth rate is $2\JS(P,Q)$, where $\JS$ is the Jensen--Shannon divergence. Unequal sizes yield weighted Jensen--Shannon information and the one-sample limit $\log W(n_1,n_2)/n_2\to\KL(Q\|P)$ when $n_1/n_2\to\infty$. Refining finite partitions and logarithmic-loss learning with measurable characteristic kernels provide universal constructions. Our main contribution is the generality of our construction, and its connections to classical batch efficiency notions. Practical implementations allow continuous classifier fine-tuning, as demonstrated on finite alphabets, Gaussian data, and handwritten digits.

0.17