CS Paper Radar

Private Component-by-Component Learning

Dvir Karni, Eliad Tsfadia

cs.LG cs.CR ·submitted 2026-10-04 10:15 UTC · v1
theory

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 $\varepsilon$, pays only $\widetilde O(\sqrt{k}/\varepsilon)$ overhead relative to the active sample requirement of a single component learning step at target accuracy $Θ(α/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}{\varepsilon α}\cdot \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}{\varepsilon α}\cdot\min\{\frac{1}α\cdot 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\}^k\to\{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(\sqrt{k}/\varepsilon)$.

Closest papers

Nearest neighbours by meaning across the whole index.

Privacy for Free in Efficient Agnostic Halfspace Learning

cs.LG stat.ML ·2026-11-03 ·Giorgio Racca, Amartya Sanyal, Vikrant Singhal
similarity 0.76
Abstract

We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces. In particular, we study three different settings of agnostic learning: improper learning under Gaussian and log-concave marginals; proper learning under Gaussian marginals; and semi-agnostic learning under Gaussian marginals. In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.

0.15

Projection-Based Federated Learning on Compact Submanifolds with Geometry-Independent Differential Privacy

cs.LG stat.ML ·2026-10-24 ·Thibault Pautrel, Florent Bouchard, Guillaume Ginolhac, Ammar Mian, Aurélien Bellet
similarity 0.70
Abstract

Federated learning trains a shared model across clients without exchanging their data, yet the updates they transmit still leak information about individual records. Enforcing differential privacy is harder still when the model parameters lie on a Riemannian manifold. Existing methods rebuild the noise added for privacy in the geometry of each new iterate, aggregate through intrinsic maps that often lack a closed form, and prove convergence only in restricted regimes. We introduce DP-RFedProj, a record-level differentially private federated learning method for compact submanifolds that aggregates through closed-form projections and privatises gradients in a fixed ambient geometry. Each client may run any stochastic first-order optimiser, take several local steps, and participate only intermittently. An explicit record-level $f$-DP guarantee holds for the entire training transcript, independently of the manifold, the aggregation scheme and the local optimiser. We establish convergence of DP-RFedProj when each client runs Riemannian SGD locally and the server aggregates by projected averaging, and show that privacy enters the rate through a term scaling with the manifold's intrinsic dimension rather than the ambient one. Synthetic experiments on federated PCA over the Grassmann manifold corroborate these findings. On EEG motor-imagery classification with SPDNet, whose weights lie on the Stiefel manifold, the method outperforms a Euclidean baseline at every privacy budget considered. In both experimental settings, our accounting requires five to six times less noise than that of the closest prior method for the same budget, which translates into higher utility.

0.18

New Lower Bounds for Private PAC Learning

cs.LG ·2026-10-30 ·Prathamesh Dharangutte, Amartya Sanyal
theory similarity 0.69
Abstract

We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in $\mathcal{G}$ that can be packed independently into a class $\mathcal{H}$, and prove that every $(\varepsilon, δ)$-DP, $(α, β)$-PAC learner for $\mathcal{H}$, possibly improper, uses $Ω\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(α\varepsilon)\right)$ examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into $\mathcal{H}$ and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.

0.03

Private Evaluation of High-Dimensional Functions

cs.CR stat.MLcs.DScs.IT+1 ·2026-10-17 ·Mohammad Afzali, Hassan Ashtiani, Adam Smith
similarity 0.68
Abstract

We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and query access to a function $f$---whose sensitivity may be unknown or unbounded---the goal is to privately output an approximation to $f(S)$. The black-box evaluator can only query the value of $f$ over a down neighborhood of $S$ (i.e., those subsets of $S$ that are obtained by removing a bounded number of elements from $S$). We design generic black-box evaluators for both pure and approximate differential privacy through a reduction to high-dimensional private quasi-concave optimization (QCO). Our black-box evaluator enjoys a geometric notion of utility. Consider the vectors obtained by applying $f$ on sets in a down neighborhood of $S$. With high probability, the evaluator's output is guaranteed to be in the convex hull of these vectors. Our work generalizes the result of Linder et al. [LRSS25] for real-valued function evaluation to high dimensions. It also recovers the private center-point guarantees of Beimel et al. [BMNS19], with an explicit additive approximation to maximum Tukey depth. We also apply our evaluators to user-level quasi-concave and convex optimization, showing how they can improve upon the sample-and-aggregate baseline of Nissim et al. [NRS07] by replacing the multiplicative data overhead with an additive overhead. Finally, we show that our formulation of high dimensional black-box evaluation and high dimensional private QCO are equivalent up to a factor of the dimension: the hardest private evaluation instances already arise from the cases that $f$ is a (non-private) quasi-concave optimizer.

0.20

Nearly Linear Private Learning of Littlestone Classes

cs.LG ·2026-10-16 ·Shay Moran, Chao Yan
theory similarity 0.68
Abstract

Differentially private learning aims to learn from data while protecting individual training examples. For binary classification, finite Littlestone dimension characterizes approximate private PAC learnability (Alon et al., JACM 2022). Understanding how this dimension controls private sample complexity remains a central question. For classes of Littlestone dimension $d$, the first general upper bound was doubly exponential in $d$ (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to $\widetilde O(d^6)$ (Ghazi et al., STOC 2021) and then to $\widetilde O(d^5)$ (Lyu, STOC 2026). We prove a nearly linear upper bound of $O(d\log d)$. Our main algorithmic contribution is a structural exponential mechanism for data-dependent candidate sets equipped with a rank satisfying suitable stability conditions. For natural Littlestone classes such as subspace indicators, this rank has a simple geometric interpretation: it is the codimension. This yields a private PAC learner for subspaces of dimension at most $d$ over any field, with tight linear dependence on $d$ and no dependence on the ambient dimension, improving the quadratic dependence of Kaplan et al. (STOC 2025). Our second contribution is combinatorial: drawing on model-theoretic ideas, we construct a suitable rank for general Littlestone classes and establish the counting bounds required by the mechanism.

0.40

Spectrum Is Not Enough: A Random-Matrix Account of Data-Free Preconditioning for Differentially Private Learning

cs.LG ·2026-10-15 ·Shilin Zhang, Kangning Wang
similarity 0.67
Abstract · 16 pages, 14 figures

At a fixed privacy budget, curvature is exactly the object the budget makes unavailable. A recent answer estimates it from synthetic probes, at neither privacy cost nor distribution shift, and validates a probe by the eigenvalue decay it reproduces. That test reads the spectrum, not the basis, and what a probe reconstructs is unknown. This paper gives a random-matrix account of data-free preconditioning, organized by one dichotomy. Of the two Kronecker factors, the error-signal factor $ G $ and the architecture-determined bulk of the activation factor $ A $ are reconstructible without data up to an explicit error-energy bound; only the data-induced spikes of $ A $ are not. We verify that bound with zero violations along a full training trajectory, though it stays one to nearly three orders of magnitude above the gap it bounds. We locate the failure boundary at a Baik-Ben Arous-Péché threshold: a bulk-only probe suffers an exact damage $s^2/(1-s^2)$ from a spike of strength $s^2$, invisible once its amplitude exceeds the scaled-bulk threshold $( \sqrt {c}/(1+ \sqrt {c}))^{1/2}$, $c = d/n$. The test in use is basis-blind: rotating only the probe eigenbasis at a near-exact matched spectrum inflates the residual by $2.3 \times $ to $89.8 \times $, and a closed-form volume law fixes the within-spectrum ordering of the critical volume while a two-oracle construction proves that no functional of the probe spectrum fixes its magnitude. Over forty seeds on three modalities, per-layer tuning does not transfer to accuracy, no data-free arm beats the flat probe, public-data curvature does on both modalities tested, and the ordering inverts on PathMNIST under real DP noise. The account yields a probe-design protocol and falsifiable predictions for the regimes where data-free curvature can be trusted.

0.31

Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy

cs.LG cs.CRcs.DS ·2026-10-22 ·Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman
publishedtheory similarity 0.66
Abstract · Full version of the SODA 2027 paper

We study learning a discrete distribution under person-level differential privacy in the batched setting. Given $n$ users, each contributing $m$ i.i.d. samples from an unknown distribution $μ$ over $[k]$, we seek an estimate of $μ$ with total-variation error $α$. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure $(\varepsilon,0)$-DP, we achieve $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$, the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate $(\varepsilon,δ)$-DP, we achieve $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon)$. At $δ=2^{-Θ(k)}$, this is $\widetilde O(k)$ for fixed $α,\varepsilon,m$ and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate $O(η\sqrt{\log(1/η)/m})$ and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.

0.32

Certification-Based Differentially Private Learning

cs.LG ·2026-09-30 ·Mihnea Ghitu, Matthew Wicker
similarity 0.66
Abstract

Differential privacy (DP) in machine learning is typically achieved by adding noise to model parameters (private learning) or to model outputs (private prediction). Recent work uses formal methods, namely abstract interpretation, to provide tighter privacy guarantees, but only for private prediction in classification settings. In this work, we investigate the use of formal methods as a general tool for tighter privacy analysis. First, we generalize the abstract gradient training (AGT) framework to private prediction in continuous, unbounded regression. Second, by reducing learning in parameterized models to a regression problem over the parameter space, we introduce Abstract Gradient Sampling (AGS), an algorithm that enables reachability-based analysis to provide guarantees for private learning. In both private prediction and private learning, we provide tightened privacy accounting for the AGT framework and a theoretical analysis demonstrating when our smooth sensitivity upper-bounds yield favourable privacy-utility trade-off. In practice, we validate that our regression bounds are tighter than global-sensitivity baselines on regression benchmarks, and, notably, yield the first finite privacy guarantees in settings where global prediction sensitivity is a priori unbounded. We also find that under matched conditions, our private learning algorithm can outperform standard private learners.

0.29