# Private Component-by-Component Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 25 references that are in the map.
- First posted on arXiv 4 Oct 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [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)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [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)
- [Efficient Private Algorithms for Learning Large-Margin Halfspaces](https://mlsanity.com/paper/1902.09009/) (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)
- [On Differentially Private Linear Algebra](https://mlsanity.com/paper/2411.03087/) (2024)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems](https://mlsanity.com/paper/2504.19001/) (2025)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)

## Abstract (arXiv)

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by k components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy varepsilon, pays only widetilde O(√k/varepsilon) overhead relative to the active sample requirement of a single component learning step at target accuracy Theta(α/k). For learning d-dimensional halfspaces over a finite coordinate grid of size L, exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl'os, and Stemmer [STOC '23] yields a realizable sample complexity of widetildeOleft(frac1varepsilon α· mind2.5 log^*L, :: d2.5 + d1.5 2log^*Lright), which improves on the previously known bound of widetildeOleft(frac1varepsilon α·minfrac1α· d5.5log^*L,:: d2.52log^*Lright). We also apply the framework to Boolean compositions: given proper private learners for classes H1,ldots,Hk, we obtain a proper private learner for G(H1,ldots,Hk) for any fixed Boolean function G:0,1k→0,1. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from widetilde O(k/varepsilon) to widetilde O(√k/varepsilon).