Improving the Convergence of Private Shuffled Gradient Methods with Public Data

Shuli Jiang, Pranay Sharma, Zhiwei Steven Wu, Gauri Joshi
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:2538-2594, 2026.

Abstract

We consider the problem of differentially private ({DP}) convex empirical risk minimization ({ERM}). While the standard {DP}-{SGD} algorithm is theoretically well-established, practical implementations often rely on shuffled gradient methods that traverse the training data sequentially rather than sampling with replacement in each iteration. Despite their widespread use, the theoretical privacy-accuracy trade-offs of private shuffled gradient methods ($\textit{{DP}-ShuffleG}$) remain poorly understood, leading to a gap between theory and practice. In this work, we leverage privacy amplification by iteration (PABI) and a novel application of {Stein}’s lemma to provide the first empirical excess risk bound of $\textit{{DP}-ShuffleG}$. Our result shows that data shuffling results in worse empirical excess risk for $\textit{{DP}-ShuffleG}$ compared to {DP}-{SGD}. To address this limitation, we propose $\textit{Interleaved-ShuffleG}$, a hybrid approach that integrates public data samples in private optimization. By alternating optimization steps that use private and public samples, $\textit{Interleaved-ShuffleG}$ effectively reduces empirical excess risk. Our analysis introduces a new optimization framework with surrogate objectives, varying levels of noise injection, and a dissimilarity metric, which can be of independent interest. Our experiments on diverse datasets and tasks demonstrate the superiority of $\textit{Interleaved-ShuffleG}$ over several baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-jiang26b, title = {Improving the Convergence of Private Shuffled Gradient Methods with Public Data}, author = {Jiang, Shuli and Sharma, Pranay and Wu, Zhiwei Steven and Joshi, Gauri}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {2538--2594}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/jiang26b/jiang26b.pdf}, url = {https://proceedings.mlr.press/v337/jiang26b.html}, abstract = {We consider the problem of differentially private ({DP}) convex empirical risk minimization ({ERM}). While the standard {DP}-{SGD} algorithm is theoretically well-established, practical implementations often rely on shuffled gradient methods that traverse the training data sequentially rather than sampling with replacement in each iteration. Despite their widespread use, the theoretical privacy-accuracy trade-offs of private shuffled gradient methods ($\textit{{DP}-ShuffleG}$) remain poorly understood, leading to a gap between theory and practice. In this work, we leverage privacy amplification by iteration (PABI) and a novel application of {Stein}’s lemma to provide the first empirical excess risk bound of $\textit{{DP}-ShuffleG}$. Our result shows that data shuffling results in worse empirical excess risk for $\textit{{DP}-ShuffleG}$ compared to {DP}-{SGD}. To address this limitation, we propose $\textit{Interleaved-ShuffleG}$, a hybrid approach that integrates public data samples in private optimization. By alternating optimization steps that use private and public samples, $\textit{Interleaved-ShuffleG}$ effectively reduces empirical excess risk. Our analysis introduces a new optimization framework with surrogate objectives, varying levels of noise injection, and a dissimilarity metric, which can be of independent interest. Our experiments on diverse datasets and tasks demonstrate the superiority of $\textit{Interleaved-ShuffleG}$ over several baselines.} }
Endnote
%0 Conference Paper %T Improving the Convergence of Private Shuffled Gradient Methods with Public Data %A Shuli Jiang %A Pranay Sharma %A Zhiwei Steven Wu %A Gauri Joshi %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-jiang26b %I PMLR %P 2538--2594 %U https://proceedings.mlr.press/v337/jiang26b.html %V 337 %X We consider the problem of differentially private ({DP}) convex empirical risk minimization ({ERM}). While the standard {DP}-{SGD} algorithm is theoretically well-established, practical implementations often rely on shuffled gradient methods that traverse the training data sequentially rather than sampling with replacement in each iteration. Despite their widespread use, the theoretical privacy-accuracy trade-offs of private shuffled gradient methods ($\textit{{DP}-ShuffleG}$) remain poorly understood, leading to a gap between theory and practice. In this work, we leverage privacy amplification by iteration (PABI) and a novel application of {Stein}’s lemma to provide the first empirical excess risk bound of $\textit{{DP}-ShuffleG}$. Our result shows that data shuffling results in worse empirical excess risk for $\textit{{DP}-ShuffleG}$ compared to {DP}-{SGD}. To address this limitation, we propose $\textit{Interleaved-ShuffleG}$, a hybrid approach that integrates public data samples in private optimization. By alternating optimization steps that use private and public samples, $\textit{Interleaved-ShuffleG}$ effectively reduces empirical excess risk. Our analysis introduces a new optimization framework with surrogate objectives, varying levels of noise injection, and a dissimilarity metric, which can be of independent interest. Our experiments on diverse datasets and tasks demonstrate the superiority of $\textit{Interleaved-ShuffleG}$ over several baselines.
APA
Jiang, S., Sharma, P., Wu, Z.S. & Joshi, G.. (2026). Improving the Convergence of Private Shuffled Gradient Methods with Public Data. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:2538-2594 Available from https://proceedings.mlr.press/v337/jiang26b.html.

Related Material