Private Paths to Stability: New Proofs Show DP-SGD Converges Almost Surely

In the high-stakes world of machine learning, where models trained on sensitive data in healthcare or finance must not leak private information, Differentially Private Stochastic Gradient Descent (DP-SGD) has become the go-to algorithm. It offers a mathematically rigorous privacy guarantee by clipping gradients and injecting noise during training. However, a critical theoretical gap has persisted: while prior analyses could show DP-SGD converges in expectation or with high probability, they could not guarantee that a single, actual training run—a trajectory—would stabilize. New research from the University of Waterloo now closes this gap, proving for the first time that DP-SGD and its momentum-based variants converge almost surely, providing a much stronger foundation for deploying private AI in practice.

The paper, authored by Amartya Mukherjee and Jun Liu, tackles this by analyzing the long-run behavior of DP-SGD under standard smoothness and convexity assumptions. The core is that the privacy mechanisms—gradient clipping and Gaussian noise injection—introduce bias and distortion, breaking the unbiased gradient property that classical stochastic gradient descent (SGD) relies on. The authors employ advanced stochastic analysis tools, particularly supermartingale techniques, to show that despite these distortions, the algorithm's iterates do not wander indefinitely. They prove that a weighted average of the gradient norm converges almost surely, implying the best iterate during training approaches an optimum in non-convex settings or the global minimum in strongly convex problems.

Ology extends beyond basic DP-SGD to include momentum variants like Differentially Private Stochastic Heavy Ball (DP-SHB) and Nesterov's Accelerated Gradient (DP-NAG). For these, the researchers construct careful 'energy functions'—combinations of the objective function value and momentum terms—that behave as supermartingales. Under step-size conditions where α_t decays like Θ(1/t^{1-θ}) for θ in (0, 1/2), they demonstrate that these energy functions converge almost surely. A key lemma from prior work on supermartingales is leveraged to handle the cumulative effects of noise and clipping, ensuring the sum of certain gradient-related terms remains finite, which forces convergence.

Are robust across different problem geometries. In non-convex settings, the authors show that min_{1≤i≤t} Φ_i(x_i) = o(1/∑_{i=1}^{t-1} α_i) almost surely, where Φ_t(x) captures gradient norms and clipping effects. For strongly convex functions, a similar guarantee holds for a modified quantity Φ_t^μ(x). Perhaps more impressively, the analysis is extended to prove last-iterate convergence—not just for the best iterate—using an additional oscillation-control lemma. This ensures that the gradient at the final iteration itself goes to zero almost surely, a stronger result that aligns with practical deployment where only the last model is typically used.

Of this work are significant for both theory and practice. By establishing almost sure convergence, it provides 'pathwise stability' guarantees, meaning individual training runs of DP-SGD are reliable and will not diverge due to privacy noise. This strengthens confidence in using DP-SGD for sensitive applications, as practitioners can now rely on single trajectories rather than statistical averages. The paper also highlights that while convergence is assured, the rate may slow with increased noise or tighter clipping—a trade-off that future work could quantify more precisely. These suggest that despite the inherent distortions of differential privacy, the core optimization dynamics remain fundamentally stable.

However, the research has limitations. The analysis assumes standard conditions like L-smoothness and directional invariance of stochastic gradients, which may not hold in all real-world datasets. The step-size requirements, while common in theory, might need adaptation for practical implementations that use constant or adaptive step sizes. Additionally, the paper does not derive explicit convergence rates in terms of the privacy parameters (ε, δ) or the clipping threshold q, leaving open how exactly privacy tightness affects speed. Future work could explore these dependencies and extend the analysis to adaptive s like DP-Adam, where prior research has noted noise can neutralize curvature adaptation.

Reference: Mukherjee, A., & Liu, J. (2025). Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient s. arXiv preprint arXiv:2511.16587v1 [cs.LG].