Smoothed Analysis of Learning from Positive Samples

Binary classification from positive-only samples is a variant of PAC learning where the learner receives i.i.d. positively labeled samples and aims to learn a classifier that, with high probability, achieves low classification error. Previous work by Natarajan [Nat87, STOC], Gereb-Graus [Ger89, Thesis], and Shvaytser [Shv90, Machine Learning] characterized learnability in this setting and revealed a largely negative picture: almost no interesting classes, including two-dimensional halfspaces, are learnable from positive-only examples. This poses significant challenges for the plethora of applications of positive-only learning from bioinformatics to ecology, where practitioners rely on heuristics for learning.

In this work, we initiate a smoothed analysis of positive-only learning. We assume we have access to samples from a reference distribution D such that the true data distribution D ⋆ is smooth with respect to it. Our first result demonstrates that, in stark contrast to the worstcase setting, all VC classes become learnable in the smoothed model, requiring O( VC /ε 2 ) positive samples to guarantee ε-classification error. We then present a computationally efficient algorithm for any concept class that admits poly(ε)-approximation by degree-k polynomials (whose range is lower-bounded by a constant) with respect to D in the L 1 -norm. The algorithm runs in time poly(d k /ε), which qualitatively matches the running time of the L1-Regression algorithm. This smoothed analysis contributes to the growing body of work designing better learning guarantees under smoothness [HRS24, J. ACM] [CKKMS24, COLT].

Our results also imply faster or more general algorithms for the following problems:

1. Estimation under unknown truncation, where we give the first polynomial sample and time algorithm for estimating the parameters of an exponential family distribution from samples truncated to an unknown set S ⋆ that is approximable by non-negativepolynomials in L 1 -norm. This improves upon [KTZ19, FOCS] [LMZ24, FOCS], which required strong approximation with respect to L 2 .

2. Truncation detection, where we present the first algorithm for detecting whether given samples have been truncated (or not) for a broad class of distributions, including nonproduct distributions. This improves upon [DLNS24a, STOC] who were limited to product distributions.

3. Learning with a list of reference distributions, as a corollary of our main result on smoothed analysis. We obtain analogous sample and computational complexity results in the more general setting where we do not have access to (samples from) a reference distribution D but rather only have access to samples from a list of O(1) distributions one of which witnesses the smoothness of D ⋆ . This naturally arises if list-decoding algorithms are used to learn samplers for D ⋆ from corrupted data.

Accepted for presentation at the 58th ACM Symposium on Theory of Computing (STOC), 2026