# ~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 32 references that are in the map.
- First posted on arXiv 11 Nov 2022.

## Builds on (most cited first, 16 of 16)

- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [Concurrent Composition of Differential Privacy](https://mlsanity.com/paper/2105.14427/) (2021)
- [Learning Privately with Labeled and Unlabeled Examples](https://mlsanity.com/paper/1407.2662/) (2014)
- [Composition Theorems for Interactive Differential Privacy](https://mlsanity.com/paper/2207.09397/) (2022)
- [Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity](https://mlsanity.com/paper/2004.07839/) (2020)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Private Approximations of a Convex Hull in Low Dimensions](https://mlsanity.com/paper/2007.08110/) (2020)

## Built on by (most cited first, 18 of 18)

- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [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)
- [Protecting the Undeleted in Machine Unlearning](https://mlsanity.com/paper/2602.16697/) (2026)
- [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)
- [Private Truly-Everlasting Robust-Prediction](https://mlsanity.com/paper/2401.04311/) (2024)
- [An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1](https://mlsanity.com/paper/2505.06581/) (2025)
- [Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model](https://mlsanity.com/paper/2301.09203/) (2023)
- [On the Inherent Privacy of Zeroth Order Projected Gradient Descent](https://mlsanity.com/paper/2507.05610/) (2025)
- [Private Prediction via Shrinkage](https://mlsanity.com/paper/2602.05219/) (2026)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)
- [Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe](https://mlsanity.com/paper/2607.07209/) (2026)
- [Machine Unlearning as Private Retroactive Algorithms](https://mlsanity.com/paper/2609.05329/) (2026)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O(xi-1 log(1/β)) (for generalization error xi with confidence 1-β). The private version of the problem, however, is more challenging and in particular, the sample complexity must depend on the size |X| of the domain. Progress on quantifying this dependence, via lower and upper bounds, was made in a line of works over the past decade. In this paper, we finally close the gap for approximate-DP and provide a nearly tight upper bound of tildeO(log^* |X|), which matches a lower bound by Alon et al (that applies even with improper learning) and improves over a prior upper bound of tildeO((log^* |X|)1.5) by Kaplan et al. We also provide matching upper and lower bounds of tildeTheta(2log^*|X|) for the additive error of private quasi-concave optimization (a related and more general problem). Our improvement is achieved via the novel Reorder-Slice-Compute paradigm for private data analysis which we believe will have further applications.