# Improving the Convergence of Private Shuffled Gradient Methods with Public Data

arXiv: https://arxiv.org/abs/2502.03652 · HTML: https://mlsanity.com/paper/2502.03652/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)

## Abstract (arXiv)

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 (textitDP-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 textitDP-ShuffleG. Our result shows that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD. To address this limitation, we propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization. By alternating optimization steps that use private and public samples, textitInterleaved-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 textitInterleaved-ShuffleG over several baselines.