Private Component-by-Component Learning

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).