On the Inherent Privacy of Zeroth Order Projected Gradient Descent

2025/07/08 by Devansh Gupta, Meisam Razaviyayn, Gupta, Devansh +3
Computer Science · #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2507.05610

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

Abstract

Differentially private zeroth-order optimization methods have recently gained popularity in private fine tuning of machine learning models due to their reduced memory requirements. Current approaches for privatizing zeroth-order methods rely on adding Gaussian noise to the estimated zeroth-order gradients. However, since the search direction in the zeroth-order methods is inherently random, researchers including Tang et al. (2024) and Zhang et al. (2024a) have raised an important question: is the inherent noise in zeroth-order estimators sufficient to ensure the overall differential privacy of the algorithm? This work settles this question for a class of oracle-based optimization algorithms where the oracle returns zeroth-order gradient estimates. In particular, we show that for a fixed initialization, there exist strongly convex objective functions such that running (Projected) Zeroth-Order Gradient Descent (ZO-GD) is not differentially private. Furthermore, we show that even with random initialization and without revealing (initial and) intermediate iterates, the privacy loss in ZO-GD can grow superlinearly with the number of iterations when minimizing convex objective functions.

Citations

• Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses
• Fine-Tuning Large Language Models with User-Level Differential Privacy
• Private Zeroth-Order Nonsmooth Nonconvex Optimization
• Zeroth-Order Fine-Tuning of LLMs with Extreme Sparsity
• Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark
• How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization
• Private Fine-tuning of Large Language Models with Zeroth-order Optimization
• DPZero: Private Fine-Tuning of Language Models without Backpropagation
• Zeroth-order Optimization with Weak Dimension Dependency
• Fine-Tuning Language Models with Just Forward Passes
• ReSQueing Parallel and Private Stochastic Convex Optimization
• Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
• Private Convex Optimization in General Norms
• Faster Rates of Convergence to Stationary Points in Differentially Private Optimization
• Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
• Private Non-Convex Federated Learning Without a Trusted Server
• Private Convex Optimization via Exponential Mechanism
• Federated Learning with Heterogeneous Differential Privacy
• Opacus: User-Friendly Differential Privacy Library in PyTorch
• Private Federated Learning Without a Trusted Server: Optimal Algorithms\n for Convex Losses
• LoRA: Low-Rank Adaptation of Large Language Models
• Private Stochastic Convex Optimization: Optimal Rates in ℓ₁ Geometry
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time
• LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale
• Private Stochastic Convex Optimization with Optimal Rates
• Private Learning Implies Online Learning: An Efficient Reduction
• Detecting Correlations with Little Memory and Communication
• Collecting Telemetry Data Privately
• Membership Inference Attacks against Machine Learning Models
• Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification
• Optimal rates for zero-order convex optimization: the power of two\n function evaluations
• On the Complexity of Bandit and Derivative-Free Stochastic Convex\n Optimization
• Differentially Private Empirical Risk Minimization
• Online convex optimization in the bandit setting: gradient descent without a gradient

Related

• Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States
• Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners
• Differentially Private Stochastic Gradient Descent with Low-Noise
• Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget
• Private Zeroth-Order Optimization with Public Data