From Privacy to Generalization: Linear Max-Information Bounds for DP-SGD

• URL: http://arxiv.org/abs/2605.26222v1
• Date: Mon, 25 May 2026 18:00:05 GMT
• Title: From Privacy to Generalization: Linear Max-Information Bounds for DP-SGD
• Abstract summary: We prove a finite-sample bound on the approximate max-information of differentially private gradient descent (DP-SGD)<n>We obtain a general-purpose PAC-Bayes generalization bound in which the necessary prior distribution can be learned by DP-SGD, as well as a generalization bound for DP-SGD-trained models themselves.
• Score: 21.925083923451595
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding the relationship between generalization and privacy remains a central challenge in modern machine learning theory, particularly for deep networks trained by variants of differentially private stochastic gradient descent (DP-SGD). In this work we make progress on this persistent open problem by proving a finite-sample bound on the approximate max-information of DP-SGD that exhibits scaling properties comparable with (Dwork et al, 2015)'s classic result for $ε$-differentially private algorithms, namely at most linear in the dataset size. From our result we obtain a general-purpose PAC-Bayes generalization bound in which the necessary prior distribution can be learned by DP-SGD, as well as a generalization bound for DP-SGD-trained models themselves, with a complexity term that is fully explicit and controlled by the optimization hyperparameters.

Related papers

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD.<n>We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• On the Convergence of DP-SGD with Adaptive Clipping [56.24689348875711]
  Gradient Descent with gradient clipping is a powerful technique for enabling differentially private optimization.<n>This paper provides the first comprehensive convergence analysis of SGD with quantile clipping (QC-SGD)<n>We show how QC-SGD suffers from a bias problem similar to constant-threshold clipped SGD but can be mitigated through a carefully designed quantile and step size schedule.
  arXiv  Detail & Related papers  (2024-12-27T20:29:47Z)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Private Fine-tuning of Large Language Models with Zeroth-order Optimization [51.19403058739522]
  Differentially private gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner.<n>We introduce DP-ZO, a private fine-tuning framework for large language models by privatizing zeroth order optimization methods.
  arXiv  Detail & Related papers  (2024-01-09T03:53:59Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• DPGOMI: Differentially Private Data Publishing with Gaussian Optimized Model Inversion [8.204115285718437]
  We propose Differentially Private Data Publishing with Gaussian Optimized Model Inversion (DPGOMI) to address this issue. Our approach involves mapping private data to the latent space using a public generator, followed by a lower-dimensional DP-GAN with better convergence properties. Our results show that DPGOMI outperforms the standard DP-GAN method in terms of Inception Score, Freche't Inception Distance, and classification performance.
  arXiv  Detail & Related papers  (2023-10-06T18:46:22Z)
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent [11.49109939095326]
  We study differentially private empirical risk minimization (DP-ERM) We show theoretically that DP-GCD can achieve a logarithmic dependence on the dimension for a wide range of problems.
  arXiv  Detail & Related papers  (2022-07-04T16:27:00Z)
• Dimension Independent Generalization of DP-SGD for Overparameterized Smooth Convex Optimization [24.644583626705742]
  This paper considers the generalization performance of differentially private convex learning. We demonstrate that the convergence analysis of Langevin algorithms can be used to obtain new generalization bounds with differential privacy guarantees for DP-SGD.
  arXiv  Detail & Related papers  (2022-06-03T22:03:05Z)
• What You See is What You Get: Distributional Generalization for Algorithm Design in Deep Learning [12.215964287323876]
  We investigate and leverage a connection between Differential Privacy (DP) and the notion of Distributional Generalization (DG) We introduce new conceptual tools for designing deep-learning methods that bypass "pathologies" of standard gradient descent (SGD)
  arXiv  Detail & Related papers  (2022-04-07T05:41:40Z)
• Differentially Private Coordinate Descent for Composite Empirical Risk Minimization [13.742100810492014]
  Machine learning models can leak information about the data used to train them. Differentially Private (DP) variants of optimization algorithms like Gradient Descent (DP-SGD) have been designed to mitigate this. We propose a new method for composite Differentially Private Empirical Risk Minimization (DP-ERM): Differentially Private Coordinate Descent (DP-CD)
  arXiv  Detail & Related papers  (2021-10-22T10:22:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.