Private Decentralized Optimization with Noise Reduction and Bias Correction

Yizhao Fan; Wenjian Luo; Jiaojiao Zhang

cs.LGSep 23, 2026

Private Decentralized Optimization with Noise Reduction and Bias Correction

Authors: Yizhao Fan, Wenjian Luo, Jiaojiao Zhang

Abstract

Private decentralized learning is affected by sampling noise, privacy noise, and decentralized bias under heterogeneous data. We propose Private Recursive Decentralized Optimization (PRDO). PRDO uses recursive estimation with same-batch gradient differences to reduce estimation errors caused by sampling and privacy noise, while its Exact Diffusion component corrects decentralized bias arising from data heterogeneity. Our analysis establishes a nonconvex convergence bound without assuming uniformly bounded data heterogeneity across nodes. It further gives a sufficient condition under which recursive gradient differences yield strictly lower query sensitivity than private Exact Diffusion, together with an example that rigorously satisfies this condition. Experiments show improved accuracy over the evaluated baselines.

Explore similar work

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?
May 8, 2026Andy Dong, Ayfer ÖzgürDifferential Privacy Subsampling
FIBER: A Differentially Private Optimizer with Filter-Aware Innovation Bias Correction
May 5, 2026Duc Dm, Thao Do, Minh Son Hoang +3Differential Privacy Optimizer Design
Differentially Private Natural Gradient Descent
Jul 7, 2026Pan Li, Kai Chen, Shuai Chang +3Differential Privacy Stochastic Gradient Descent

May 8, 2026 · cs.LGJ/K move · Enter open · S save

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?

Andy Dong, Ayfer Özgür

Stanford University

Poisson subsampling is the default sampling scheme in differentially private machine learning, largely because its unstructured randomness yields tractable privacy amplification analyses. Yet this same randomness introduces substantial participation variance: each sample appears in very different numbers of training iterations. In this work, we show that this variance is not merely a practical artifact to be tolerated, but a fundamental source of suboptimal privacy amplification. We prove that Balanced Iteration Subsampling (BIS), a structured scheme in which each sample participates in exactly a fixed number of iterations, achieves stronger privacy amplification than Poisson subsampling and is optimal at both extremes of the noise spectrum (

σ\to 0

and

σ\to \infty

). Our analysis reveals that the privacy-noise tradeoff is governed not by maximizing randomness, but by eliminating participation variance while preserving uniform marginal participation across iterations. To translate this asymptotic theory into finite-noise guarantees, we introduce a practical near-exact Monte Carlo accountant for BIS, which removes the analytical slack of existing RDP and composition-based PLD analyses. Evaluations across more than 60 practical DP-SGD configurations show that BIS consistently outperforms Poisson subsampling in the low-noise regimes most relevant for high-utility private training, reducing the required noise multiplier by up to

9.6\%

. These results overturn the common intuition that more sampling randomness necessarily yields stronger privacy amplification: in DP-SGD, structured participation can be both more practical and more private. Our implementation is available at https://github.com/dong-xin-ao-andy/bis-mc-accountant.

Differential Privacy Subsampling Optimal Sample Complexity Gaussian Noise Distributional Learning Random Machine Learning

Open paper Ask about it PDF

Abstract

Explore similar work

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?

FIBER: A Differentially Private Optimizer with Filter-Aware Innovation Bias Correction

Differentially Private Natural Gradient Descent