# On the Gradient Complexity of Private Optimization with Private Oracles

arXiv: https://arxiv.org/abs/2511.13999 · HTML: https://mlsanity.com/paper/2511.13999/

## 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 (most cited first, 30 of 34)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Adaptive Gradient Quantization for Data-Parallel SGD](https://mlsanity.com/paper/2010.12460/) (2020)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Advancing Differential Privacy: Where We Are Now and Future Directions for Real-World Deployment](https://mlsanity.com/paper/2304.06929/) (2023)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Scaling Laws for Differentially Private Language Models](https://mlsanity.com/paper/2501.18914/) (2025)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation](https://mlsanity.com/paper/2402.03990/) (2024)
- [Information-constrained optimization: can adaptive processing of gradients help?](https://mlsanity.com/paper/2104.00979/) (2021)

## Built on by (most cited first, 2 of 2)

- [Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation](https://mlsanity.com/paper/2606.00703/) (2026)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)

## 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.