# Closure Properties for Private Classification and Online Prediction

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2020.

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

- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [On Union-Closedness of Language Generation](https://mlsanity.com/paper/2506.18642/) (2025)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [Fat-Shattering Dimension of k-fold Aggregations](https://mlsanity.com/paper/2110.04763/) (2021)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [On the Learnability of Multilabel Ranking](https://mlsanity.com/paper/2304.03337/) (2023)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy](https://mlsanity.com/paper/2407.20640/) (2024)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2510.01291/) (2025)
- [Encoding orders and trees in real-valued functions](https://mlsanity.com/paper/2607.21761/) (2026)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

Let~cH be a class of boolean functions and consider a it composed class cH' that is derived from~cH using some arbitrary aggregation rule (for example, cH' may be the class of all 3-wise majority-votes of functions in cH). We upper bound the Littlestone dimension of~cH' in terms of that of~cH. As a corollary, we derive closure properties for online learning and private PAC learning. The derived bounds on the Littlestone dimension exhibit an undesirable exponential dependence. For private learning, we prove close to optimal bounds that circumvents this suboptimal dependency. The improved bounds on the sample complexity of private learning are derived algorithmically via transforming a private learner for the original class cH to a private learner for the composed class~cH'. Using the same ideas we show that any (em proper or improper) private algorithm that learns a class of functions cH in the realizable case (i.e., when the examples are labeled by some function in the class) can be transformed to a private algorithm that learns the class cH in the agnostic case.