Non-Asymptotic Analysis of Online Local Private Learning with SGD

2025/07/09 by Enze Shi, Shi, Enze, Jinhan Xie +7
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Methodology (stat.ME) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2507.07041

openalex publication_date 2025/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Differentially Private Stochastic Gradient Descent (DP-SGD) has been widely used for solving optimization problems with privacy guarantees in machine learning and statistics. Despite this, a systematic non-asymptotic convergence analysis for DP-SGD, particularly in the context of online problems and local differential privacy (LDP) models, remains largely elusive. Existing non-asymptotic analyses have focused on non-private optimization methods, and hence are not applicable to privacy-preserving optimization problems. This work initiates the analysis to bridge this gap and opens the door to non-asymptotic convergence analysis of private optimization problems. A general framework is investigated for the online LDP model in stochastic optimization problems. We assume that sensitive information from individuals is collected sequentially and aim to estimate, in real-time, a static parameter that pertains to the population of interest. Most importantly, we conduct a comprehensive non-asymptotic convergence analysis of the proposed estimators in finite-sample situations, which gives their users practical guidelines regarding the effect of various hyperparameters, such as step size, parameter dimensions, and privacy budgets, on convergence rates. Our proposed estimators are validated in the theoretical and practical realms by rigorous mathematical derivations and carefully constructed numerical experiments.

Citations

• Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach
• Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics
• Dynamic Differential-Privacy Preserving SGD
• Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent
• Differentially private inference via noisy optimization
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
• Interactive versus non-interactive locally differentially private estimation: Two elbows for the quadratic functional
• Context-Aware Local Differential Privacy
• Differentially Private Learning with Adaptive Clipping
• Lower Bounds for Locally Private Estimation via Communication Complexity
• Collecting Telemetry Data Privately
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Membership Inference Attacks against Machine Learning Models
• Minimax Optimal Procedures for Locally Private Estimation
• Statistical consistency and asymptotic normality for high-dimensional\n robust M-estimators
• Acceleration of Stochastic Approximation by Averaging
• A Stochastic Approximation Method

Related

• Online differentially private inference in stochastic gradient descent
• Privacy Loss of Noisy Stochastic Gradient Descent Might Converge Even for Non-Convex Losses
• Differentially Private Stochastic Gradient Descent with Low-Noise
• Differentially Private Distributed Stochastic Optimization with Time-Varying Sample Sizes
• Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods