SILO: Smoothed Analysis of Learning from Positive Samples

Abstract

Binary classification from positive-only samples is a variant of PAC learning where the learner receives i.i.d. positive samples and aims to learn a classifier with low error. Previous work by Natarajan, Gereb-Graus, and Shvaytser characterized learnability and revealed a largely negative picture: almost no interesting classes are learnable.

In this work, we initiate a smoothed analysis of positive-only learning. Inspired by the smoothed analysis framework of Spielman and Deng, we assume the distribution of samples is smoothed with respect to a known reference measure. In stark contrast to the worst-case setting, we show that all VC classes become learnable in the smoothed model and we also give an efficient algorithm for any class admitting a certain type of polynomial approximation/

Our results also imply faster or more general algorithms for many seemingly unrelated settings: (1) estimation with unknown-truncation, (2) truncation detection for broad classes, and (3) learning from a list of reference distributions.

Bio

 Manolis Zampetakis is an Assistant Professor of Computer Science at Yale University, where he is also affiliated with the Yale Foundations of Data Science Institute. Before joining Yale, he was a postdoctoral researcher in the EECS Department at UC Berkeley, working with Michael Jordan, and he received his PhD from the EECS Department at MIT under the supervision of Constantinos Daskalakis; he holds a Diploma in Engineering from the National Technical University of Athens. His research spans theoretical machine learning, statistics, optimization, computational complexity, game theory, and mechanism design, with a particular focus on statistical inference from biased data, optimization in multi-agent environments, and the convergence behavior of widely used heuristic methods. His work has been recognized with a Best Paper Award at COLT 2025, the ACM SIGEcom Doctoral Dissertation Award, and a Google PhD Fellowship.