# On the Sample Complexity of Privately Learning Axis-Aligned Rectangles

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 24 Jul 2021.

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

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [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)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (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)
- [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)
- [Learning Privately with Labeled and Unlabeled Examples](https://mlsanity.com/paper/1407.2662/) (2014)
- [Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity](https://mlsanity.com/paper/2004.07839/) (2020)
- [The Sparse Vector Technique, Revisited](https://mlsanity.com/paper/2010.00917/) (2020)
- [Differentially Private Learning of Geometric Concepts](https://mlsanity.com/paper/1902.05017/) (2019)

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

- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid Xdsubseteqℝd with differential privacy. Existing results show that the sample complexity of this problem is at most minleft d·log|X| ;,; d1.5·left(log^*|X| right)1.5right. That is, existing constructions either require sample complexity that grows linearly with log|X|, or else it grows super linearly with the dimension d. We present a novel algorithm that reduces the sample complexity to only tildeOleftd·left(log^*|X|right)1.5right, attaining a dimensionality optimal dependency without requiring the sample complexity to grow with log|X|.The technique used in order to attain this improvement involves the deletion of "exposed" data-points on the go, in a fashion designed to avoid the cost of the adaptive composition theorems. The core of this technique may be of individual interest, introducing a new method for constructing statistically-efficient private algorithms.