Differentially Private Truncation of Unbounded Data via Public Second Moments
Authors: Zilong Cao, Xuan Bi, Hai Zhang
Organizations: School of Mathematics, Northwest University · Department of Information and Decision Sciences, Minnesota Carlson, University of Minnesota
Data privacy is important in the AI era, and differential privacy (DP) is one of the golden solutions. However, DP is typically applicable only if data have a bounded underlying distribution. We address this limitation by leveraging second-moment information from a small amount of public data. We propose Public-moment-guided Truncation (PMT), which transforms private data using the public second-moment matrix and applies a principled truncation whose radius depends only on non-private quantities: data dimension and sample size. This transformation yields a well-conditioned second-moment matrix, enabling its inversion with a significantly strengthened ability to resist the DP noise. Furthermore, we demonstrate the applicability of PMT by using penalized and generalized linear regressions. Specifically, we design new loss functions and algorithms, ensuring that solutions in the transformed space can be mapped back to the original domain. We have established improvements in the models' DP estimation through theoretical error bounds, robustness guarantees, and convergence results, attributing the gains to the conditioning effect of PMT. Experiments on synthetic and real datasets confirm that PMT substantially improves the accuracy and stability of DP models.
Figures & tables
Figure 1: Simulations on DP-PMTRR, DP-RR and DP-GD.
Figure 2: Simulations with different private data sizes and privacy parameters.
Figure 3: Simulations with different regularization parameters.
Figure 4: Real-world experiments on DP-PMTRR, DP-RR and DP-GD.
Figure 5: Real-world experiments with different private data sizes and privacy parameters.
Figure 6: Real-world experiments with different regularization parameters.
Figure 7: Simulations of DP-PMTLR and DP-LR with different privacy parameters.
Figure 8: Simulations of DP-PMTLR and DP-LR with different regularization parameters.
Figure 9: Real-world experiments of DP-PMTLR and DP-LR with different privacy parameters.
Figure 10: Real experiments of DP-PMTLR and DP-LR with different regularization parameters.
We study differentially private optimization with matrix-orthogonalized momentum. DP-Muon uses conventional global per-example clipping and one Gaussian gradient release per step; matrix updates and auxiliary updates are post-processing. Our main contribution concerns the additional mean distortion created when fresh Gaussian noise passes through a nonlinear matrix map. Conditioning on the actual adaptive history immediately before the current noise yields an exact Gaussian heat identity. For a smooth Newton-Schulz map, first-order DP-MuonBC reduces this conditional output bias from second to fourth order in the fresh noise scale, and an arbitrary-order extension has bias of order 2K+2. We prove matrix-block stationarity bounds under global clipping, retain finite-step orthogonalization error explicitly, and give an exact criterion for improvement of the resulting upper bound. A separate inequality exposes the effect of auxiliary Adam updates. GPT-2 experiments on E2E at four privacy targets favor the reported Muon configurations over Adam baselines in test NLL.
In machine learning, privacy requirements at inference or deployment time often evolve due to changing policies, regulations, or user preferences. In this work, we aim to construct a magnitude of models to satisfy any target differential privacy (DP) requirement without additional training, given a set of existing models trained on the same dataset with different privacy/utility tradeoffs. We propose two post-processing techniques, namely random selection and linear combination, to generate final private models satisfying any target privacy parameter. We provide privacy accounting of these approaches from the lens of R'enyi DP and privacy loss distributions on general problems, as well as on private mean estimation, where we precisely characterize the privacy/utility tradeoffs and compare the two mechanisms. Empirically, we demonstrate the effectiveness of our approaches and validate our analyses on several models and both synthetic and real-world datasets.
We study the problem of differentially private second moment estimation and present a new algorithm that achieve strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. We call an input (m,α,β)-subsamplable if a random subsample of size m (or larger) preserves w.p ≥1−β the spectral structure of the original second moment matrix up to a multiplicative factor of 1±α. Building upon subsamplability, we give a recursive algorithmic framework similar to Kamath et al 2019, that abides zero-Concentrated Differential Privacy (zCDP) while preserving w.h.p. the accuracy of the second moment estimation upto an arbitrary factor of (1±γ). We then show how to apply our algorithm to approximate the second moment matrix of a distribution D, even when a noticeable fraction of the input are outliers.