mlsanityData to 14 Oct 2026

On the Gradient Complexity of Private Optimization with Private Oracles

arXiv 2511.13999 ↗First posted 17 Nov 2025cs.LG cs.CR math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time Omega(minfrac√dα2, fracdlog(1/α)) is necessary to achieve α excess risk on problems of dimension d when d ≥ 1/α2. Upper bounds via DP-SGD show these results are tight when d>tildeOmega(1/α4). We further show our lower bound can be strengthened to Omega(minfracdbarmα2, fracdlog(1/α) ) for algorithms which use minibatches of size at most barm < √d. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by tildeOmegabig(frac√dα + minfrac1α2, nbig), where n is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most Gamma-bits of information about the gradients in the minibatch, then Omegabig(minfracdα2Gamma, fracdlog(1/α)big) oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 34 of its 55 references that are in the map. First posted on arXiv 17 Nov 2025.

Builds on

34 of 55 references.

References · 34

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2018Sparsified SGD with Memorycited by 376
  4. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  5. 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 242
  6. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 170
  9. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  10. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  11. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  12. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
22 more
  1. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  2. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  3. 2020Adaptive Gradient Quantization for Data-Parallel SGDcited by 45
  4. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  5. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  6. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  7. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  8. 2023Advancing Differential Privacy: Where We Are Now and Future Directions for Real-World Deploymentcited by 27
  9. 2019RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimizationcited by 23
  10. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  11. 2025Scaling Laws for Differentially Private Language Modelscited by 22
  12. 2023Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacycited by 18
  13. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 17
  14. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  15. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  16. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  17. 2024Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisationcited by 11
  18. 2021Information-constrained optimization: can adaptive processing of gradients help?cited by 8
  19. 2024Public-data Assisted Private Stochastic Optimization: Power and Limitationscited by 6
  20. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  21. 2024Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometrycited by 2
  22. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimationcited by 1
  2. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025An Improved Privacy and Utility Analysis of Differentially Private SGD with Bounded Domain and Smooth Losses
  2. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGD
  3. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPs
  4. 2025On the Sample Complexity of Differentially Private Policy Optimization
  5. 2025Differentially Private Policy Gradient
  6. 2026Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
  7. 2021Communication-Efficient Distributed Optimization with Quantized Preconditioners
  8. 2026Smoothed Score Queries and the Complexity of Sampling