# Privately Learning Thresholds: Closing the Exponential Gap

arXiv: https://arxiv.org/abs/1911.10137 · HTML: https://mlsanity.com/paper/1911.10137/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2019.

## Built on by (most cited first, 30 of 31)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Multiclass versus Binary Differentially Private PAC Learning](https://mlsanity.com/paper/2107.10870/) (2021)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [Protecting the Undeleted in Machine Unlearning](https://mlsanity.com/paper/2602.16697/) (2026)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Differentially Private Nonparametric Regression Under a Growth Condition](https://mlsanity.com/paper/2111.12786/) (2021)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Differentially Private Medians and Interior Points for Non-Pathological Data](https://mlsanity.com/paper/2305.13440/) (2023)
- [An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1](https://mlsanity.com/paper/2505.06581/) (2025)
- [Private Isotonic Regression](https://mlsanity.com/paper/2210.15175/) (2022)
- [Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model](https://mlsanity.com/paper/2301.09203/) (2023)
- [Private Prediction via Shrinkage](https://mlsanity.com/paper/2602.05219/) (2026)

## Abstract (arXiv)

We study the sample complexity of learning threshold functions under the constraint of differential privacy. It is assumed that each labeled example in the training data is the information of one individual and we would like to come up with a generalizing hypothesis h while guaranteeing differential privacy for the individuals. Intuitively, this means that any single labeled example in the training data should not have a significant effect on the choice of the hypothesis. This problem has received much attention recently; unlike the non-private case, where the sample complexity is independent of the domain size and just depends on the desired accuracy and confidence, for private learning the sample complexity must depend on the domain size X (even for approximate differential privacy). Alon et al. (STOC 2019) showed a lower bound of Omega(log^*|X|) on the sample complexity and Bun et al. (FOCS 2015) presented an approximate-private learner with sample complexity tildeOleft(2log^*|X|right). In this work we reduce this gap significantly, almost settling the sample complexity. We first present a new upper bound (algorithm) of tildeOleft(left(log^*|X|right)2right) on the sample complexity and then present an improved version with sample complexity tildeOleft(left(log^*|X|right)1.5right). Our algorithm is constructed for the related interior point problem, where the goal is to find a point between the largest and smallest input elements. It is based on selecting an input-dependent hash function and using it to embed the database into a domain whose size is reduced logarithmically; this results in a new database, an interior point of which can be used to generate an interior point in the original database in a differentially private manner.