Private Component-by-Component Learning

arXiv:2610.05102v1 Announce Type: new Abstract: 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 arepsilon, pays only widetilde O(sqrt{k}/arepsilon) overhead relative to the active sample requirement of a single component learning step at target accuracy Theta(alpha/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 widetilde{O}left(frac{1}{arepsilon alpha}dot min{d^{2.5} log^*L, :: d^{2.5} + d^{1.5} 2^{log^*L}}right), which improves on the previously known bound of widetilde{O}left(frac{1}{arepsilon alpha}dotmin{frac{1}{alpha}dot d^{5.5}log^*L,:: d^{2.5}2^{log^*L}}right). We also apply the framework to Boolean compositions: given proper private learners for classes H_1,ldots,H_k, we obtain a proper private learner for G(H_1,ldots,H_k) for any fixed Boolean function G:{0,1}^ko{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/arepsilon) to widetilde O(sqrt{k}/arepsilon).

Related

• Differentially-Private Decision Trees and Provable Robustness to Data Poisoning
• Learning Rate Scheduling with Matrix Factorization for Private Training
• Near-Optimal Private Linear Regression via Iterative Hessian Mixing

Source: arXiv cs.LG | 2026-10-06