Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor

Maryam Aliakbarpour, Zhan Shi, Ria Stevens, Vincent Wang · 2025

Read Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor by Maryam Aliakbarpour, Zhan Shi, Ria Stevens, Vincent Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01162.txt.

Introduction

Maryam Aliakbarpour and co-authors solve a private version of hypothesis selection, picking the best of many candidate distributions for a data set without leaking the data. Their 2025 paper works under differential privacy. The plain problem is famously cheap, needing few samples and near-linear time, with a known best approximation factor of three.

Prior private methods paid for privacy with quadratic time. The new algorithm runs in nearly linear time in the count of candidates, keeps the optimal factor of three, and adds only a modest sample cost that grows very slowly. That settles an open question posed in 2019. The team frames it as privacy without the old speed penalty.

Catalog record

CREATORMaryam Aliakbarpour, Zhan Shi, Ria Stevens, Vincent Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01162

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor Maryam Aliakbarpour, Zhan Shi, Ria Stevens, Vincent Wang Abstract Estimating the density of a distribution from its samples is a fundamental problem in statistics. Hypothesis selection addresses the setting where, in addition to a sample set, we are given n n candidate distributions—referred to as hypotheses —and the goal is to determine which one best describes the underlying data distribution. This problem is known to be solvable very efficiently, requiring roughly O ⁡ ( log ⁡ n ) O(\log n) samples and running in O ~ ​ ( n ) \tilde{O}(n) time. The quality of the output is measured via the total variation distance to the unknown distribution, and the approximation factor of the algorithm determines how large this distance is compared to the optimal distance achieved by the best candidate hypothesis. It is known that α = 3 \alpha=3 is the optimal approximation factor for this problem. We study hypothesis selection under the constraint of differential privacy . We propose a differentially private algorithm in the central model that runs in nearly-linear time with respect to the number of hypotheses, achieves the optimal approximation factor, and incurs only a modest increase in sample complexity, which remains polylogarithmic in n n . This resolves an open question posed by [Bun, Kamath, Steinke, Wu, NeurIPS 2019]. Prior to our work, existing upper bounds required quadratic time. 1 Introduction The task of accurately estimating the underlying probability distribution that generates a dataset is a fundamental theoretical problem in statistical inference with broad applicability in practical data analysis. A growing concern in modern data analysis is preserving the privacy of the individuals whose data informs these estimations, specifically when dealing with sensitive information. Differential privacy (DP) has emerged as a widely adopted standard in privacy-preserving data analysis [ DMNS06a ] and is currently employed by major entities, such as Google [ EPK14 ] , Apple [ Dif17 ] , and the U.S. Census Bureau [ Abo18 ] . See Section 1.3.1 for more examples. In this paper, we study a specific instance of distribution estimation under the constraint of differential privacy, referred to as Hypothesis Selection . In this problem, we are given a finite collection of n candidate distributions \mathcal{H}\coloneqq\left\{H_{1},H_{2},\ldots,H_{n}\right\} , known as hypotheses, and a dataset of i.i.d. samples drawn from an unknown distribution P . The goal is to select a hypothesis in \mathcal{H} that well-approximates the true data distribution. A long line of research has studied hypothesis selection in the non-private setting [ Yat85 , DL96 , DL97 , DL01 , MS08 , DK14 , SOAJ14 , AJOS14 , AFJ+18 , BBK+21 , ABS23 , AAC+23 , ABS24 ] . These algorithms’ performances are evaluated across three key aspects: i) sample complexity, ii) time complexity, and iii) approximation factor. Early work has shown that hypothesis selection admits highly sample-efficient algorithms, requiring only \Theta(\log n) samples, a logarithmic dependence on the number of hypotheses, and no dependence on the domain size of distributions [ Yat85 , DL96 , DL97 , DL01 ] . The sample efficiency is achieved by only needing to estimate probabilities of O(n^{2}) special sets, called Scheffé sets, according to P (see Equation ( 1 ) for a definition). Moreover, several works [ DK14 , AFJ+18 , ABS23 , ABS24 ] have shown that one can find a valid hypothesis in roughly linear time in n . Another key aspect is the accuracy of the selected hypothesis, measured by the total variation distance to the true distribution. The approximation factor (denoted by \alpha ) measures this distance relative to the minimum distance between P and a hypothesis in \mathcal{H} . A notable lower bound established in [ BKM19 ] shows that achieving \alpha<3 is impossible unless the number of samples is polynomial in the domain size of P . In an interesting development, Aliakbarpour et al. [ ABS24 ] recently proposed an algorithm that simultaneously achieves a logarithmic sample complexity, nearly-linear time complexity, and the optimal approximation factor \alpha=3 , representing a compelling performance in all three critical aspects of this problem. Despite this desirable performance in the non-private setting, the state of the art in the private setting falls short of optimal performance. A naive privatization of Scheffé estimates via Laplace noise leads to an O(n^{2}) sample complexity [ BKSW19 ] . More advanced techniques, including the work of Bun et al. [ BKSW19 ] , offer better sample complexity (logarithmic) but suffer from quadratic time and suboptimal approximation. While Aden-Ali et al. [ AAAK21 ] makes progress on accuracy and proof simplicity, their algorithm also remains computationally expensive with a quadratic time complexity. These limitations naturally lead us to address an open question, first raised in part by Bun et al. [ BKSW19 ] : Does there exist an ideal private hypothesis selection algorithm that offers logarithmic sample complexity, nearly-linear time complexity, and the optimal approximation factor? We present a significant step forward towards this ideal: our algorithm achieves nearly-linear time complexity and the optimal approximation factor with a polylogarithmic sample complexity (which, while not logarithmic, is still considered modest dependence on the number of hypotheses). A formal description of our results can be found in Section 1.2 . Applications: Estimating data distributions is a central component of many scientific tasks, such as estimating species abundance in ecology or analyzing survey results in the social sciences. Hypothesis selection describes a broadly applicable scenario where we can form a finite set of interpretable, noise-free, or otherwise manageable distributions as our candidate hypotheses, and we aim to approximate the potentially noisy and complex unknown distribution with one of the so-called “nicer” candidates (e.g., modeling customer arrival time with Poisson processes). One notable theoretical application of hypothesis selection is agnostic learning of a parametric class of distributions (e.g., mixtures of Gaussians [ SOAJ14 , DK14 , ABM18 , ABH+20 ] , and junta distributions [ ABR16 ] )—via the cover method . The approach is to first select a representative set of parametric distributions, and hypothesis selection then identifies the closest approximation in this set. For a survey, see Diakonikolas [ Dia16 ] . 1.1 Problem setup Let P denote an unknown distribution over a domain \mathcal{X} , and let \mathcal{H}:=\{H_{1},H_{2},\dots,H_{n}\} be a set of n public and known distributions over \mathcal{X} . We define \mathrm{OPT} to be the total variation distance of P and the closest hypothesis in \mathcal{H} . We seek to design a semi-agnostic proper learner such that for every \mathcal{H} and P , the algorithm outputs a hypothesis \hat{H}\in\mathcal{H} such that the total variation distance between \hat{H} and P is within \alpha -times \mathrm{OPT} plus an additive error parameter \sigma , which can be made arbitrarily small with sufficiently many samples. We assume the standard access model of [ DL01 ] , where an algorithm accesses distributions by making queries of the following types: 1. The algorithm can draw i.i.d. samples from the unknown distribution P . 2. The algorithm can compare the PDFs of any two known distributions H_{i},H_{j} at a given point x\in\mathcal{X} . Specifically, it can ask if H_{i}(x)<H_{j}(x) . This is equivalent to determining if x is in the Scheffé

Read the complete text