Pith. sign in

REVIEW 2 major objections 3 minor 57 references

On the Gradient Complexity of Private Optimization with Private Oracles

T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that differentially private optimizers pay a dimension-dependent runtime penalty: in non-smooth convex optimization, any algorithm using a private proxy oracle needs at least on the order of min{L²B²√d/(α²√ρ), d/log(1/α)}

desk verdict First real oracle-complexity lower bounds for private optimization outside local DP, with a genuinely new proof technique — but the DP-SGD upper bound in Theorem 2 has an internal factor-of-rho error that needs fixing. read the letter →

arxiv 2511.13999 v2 pith:EG5N5NDQ submitted 2025-11-17 cs.LG cs.CRmath.OCstat.ML

Michael Menart , Aleksandar Nikolov This is my paper
classification cs.LGcs.CRmath.OCstat.ML MSC 68Q2590C2568P27
keywords differentialprivacyoraclecomplexityconvexoptimizationprivateproxyzero-concentratedgradientDP-SGDquantization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to prove that privacy costs running time, not just accuracy, in convex optimization. It shows that for non-smooth Lipschitz losses, any optimizer that talks to a private proxy oracle — an oracle whose responses are produced by a ρ-zCDP mechanism from a minibatch of true gradients — must make Ω(min{L²B²√d/(α²√ρ), d/log(1/α)}) true gradient evaluations to reach α excess risk, and this is tight in several regimes. In the smooth case, it proves that any (ε,δ)-differentially private optimizer must make Ω(BL√d/(α√log(1/δ)) + min{B²L²/α², n}) oracle calls, nearly matching a modified Phased SGD upper bound. The same information-theoretic machinery yields an Ω(min{d/(α²Γ), d/log(1/α)}) lower bound for oracles that transmit at most Γ bits per message, placing limits on gradient quantization. These are the first oracle-complexity lower bounds for differential privacy outside the local privacy model, and they quantify a dimension-dependent runtime penalty that non-private optimizers do not pay.

What carries the argument

The load-bearing object is a hard loss family combining a Nemirovski-like max over K = Θ(1/α²) random orthonormal vectors with a regularizer 2∥Π_V w∥ that penalizes a random subspace V. The proof tracks, for each problem vector X_k, the conditional mutual information I(W; X_k | X_{−k}, V) instead of the usual I(W; L); this is what makes the Ω(dK) information requirement possible. A zCDP group-privacy argument bounds the leakage per oracle response by ρ times the squared count of how often X_k was returned, a Fano-style lemma forces Ω(d) information about each vector, and a projection argument shows the optimizer cannot shortcut the unpenalized subspace without learning V via Ω(d) queries. In

What would settle it

Construct an α-accurate optimizer that uses a ρ-zCDP private proxy oracle and, with batches chosen non-adaptively within each round, reaches α excess risk on the paper's hard distribution with o(min{L²B²√d/(α²√ρ), d/log(1/α)}) true gradient evaluations; alternatively, exhibit an adaptive-within-batch optimizer achieving the same accuracy with o(√d/(α²√ρ)) evaluations, which would show the non-adaptivity restriction, not privacy itself, drives the lower bound.

Watch

Extended reading notes

Core claim

The central discovery is that the extra cost of privacy shows up in the number of gradient evaluations. For non-smooth losses, the paper constructs a hard distribution of Nemirovski-type functions L(w) = max{max_k |⟨w, X_k⟩ − C₁α|, 2∥Π_V w∥} with random orthonormal problem vectors X_k orthogonal to a random subspace V, and proves via conditional mutual information that any ρ-zCDP private proxy oracle leaks at most ρ times the squared number of times vector k is returned, while solving the problem forces the optimizer to collect Ω(d) nats of information about every problem vector. Summing over K ≈ 1/α² vectors gives the dimension-dependent lower bound. For smooth losses the proof instead redu

Load-bearing premise

The lower bounds hold only when the optimizer fixes all queries in a round before the proxy oracle responds; if within-batch adaptive queries were allowed, the optimizer could fold the whole run into one private oracle call and the dimension-dependent penalty would disappear.

Editorial extensions

If this is right

  • DP-SGD with batch size m needs Ω(min{√d/(α²√ρ), d/log(1/α)}) true gradient evaluations for non-smooth losses, formalizing that small batches degrade private training.
  • In the non-smooth regime d ≥ 1/α⁴, the lower bound is tight: DP-SGD with tuned noise achieves O(L²B²/α² (√d√ρ + d/(m̄ρ))) evaluations.
  • For smooth losses, any (ε,δ)-DP optimizer needs Ω(BL√d/(α√log(1/δ))) oracle calls regardless of ε, and a modified Phased SGD matches this up to log factors.
  • Gradient quantization is fundamentally limited: a Γ-bit proxy oracle forces Ω(min{d/(α²Γ), d/log(1/α)}) evaluations, so compressing gradients to few bits cannot avoid a dimension-proportional cost.
  • DP-SCO is no harder than DP-ERM up to log factors: a reduction lifts an α-accurate DP-ERM solver to population risk with polylog(n) overhead.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The non-adaptivity restriction suggests a narrower reading of the result: the dimension penalty is a property of batched non-adaptive private protocols, and whether fully adaptive private optimizers can evade it remains open.
  • The Γ-bit information-limited lower bound transfers directly to communication-constrained distributed optimization, predicting a d/(α²Γ)-type oracle cost for heavily quantized gradients in the non-smooth regime; this is testable by comparing full-precision and quantized SGD on high-dimensional convex problems.
  • The smooth-case lower bound's independence of ε hints that once target accuracy α is fixed, stronger privacy guarantees do not increase runtime — a prediction that would be falsified by any algorithm whose oracle complexity degrades with smaller ε at fixed α.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies the first-order oracle complexity of differentially private convex optimization. In the non-smooth setting, it introduces a ``private proxy oracle'' model in which the optimizer submits minibatches of queries and receives only privatized messages about the resulting gradients. The main lower bound (Theorem 1) states that any optimizer in this model must make Ω(B²L²√d/(α²√ρ) + B²L²d/(α²\bar m ρ)) true-gradient evaluations, up to a d/log(1/α) cap, when d ≥ 1/α². A matching upper bound is claimed via DP-SGD (Theorem 2). For smooth losses, the paper relaxes the private-oracle assumption and proves a lower bound for any (ε,δ)-DP optimizer: Ω(BL√d/(α√log(1/δ)) + min{B²L²/α², n}) oracle calls (Theorem 3), with a nearly matching upper bound (Theorem 4). A further result (Theorem 5) gives lower bounds for Γ-bit information-limited proxy oracles. The proofs combine a Nemirovski-style hard instance with information-theoretic arguments tracking conditional mutual information about individual problem vectors.

Significance. If the results are correct, this is a significant contribution: it provides the first oracle-complexity lower bounds for differentially private optimization beyond the local privacy model, and it establishes a dimension-dependent runtime penalty for private optimizers. The lower-bound machinery is novel, especially the use of conditional mutual information I(X_k; W | X_{≠k}, V) to bypass the O(d) communication bottleneck of the solution vector. The paper also honestly identifies regime gaps and modeling restrictions. The smooth-case lower bound and the Phased-SGD-based upper bound give a clean characterization up to log factors. The information-limited oracle result is a nice extension connecting to gradient quantization. The paper is mostly well-written and the appendices provide detailed proofs for the main theorems.

major comments (2)
  1. [Theorem 2 / Appendix B.2, Lemma 11] There is a factor-of-ρ algebraic error in the stated upper bound. For \bar m = ∞, Algorithm 3 sets m = √(d/ρ) and T = B²L²/α², so the oracle complexity is T·m = B²L²√d/(α²√ρ). The theorem and Lemma 11 instead state O(B²L²/α² · (√d√ρ + d/(\bar m ρ))), which for ρ<1 is a factor ρ smaller than the actual calculation. This contradicts Theorem 1, whose first lower-bound term is B²L²√d/(α²√ρ). The same incorrect √ρ appears in the running-time discussion after Theorem 2, where the claimed rate at α = Θ(α*_{ε,δ}) relies on the erroneous bound. The fix is local: replace √ρ by 1/√ρ in Theorem 2, Lemma 11, and the related sentence.
  2. [Section 1.1 / Theorem 1 vs. Theorem 2] Because of the error above, the paper's central tightness claim is not true as written: the stated upper bound would beat the lower bound for ρ<1. The lower-bound proof itself appears coherent; the issue is in the matching upper-bound statement and its proof calculation. The tightness claims in the abstract and Section 1.1 should be re-verified after correcting the upper bound, and the claimed improvement by a √ε factor over previous ERM rates should be re-derived.
minor comments (3)
  1. [Abstract / Section 2] The abstract and Section 1.1 present the results as applying to optimizers interacting with a private proxy oracle, without prominently stating that the lower bound requires the batches of queries within each round to be non-adaptive. The paper itself notes in Section 2 that without this restriction the dimension-dependent penalty disappears. This modeling restriction should be mentioned in the abstract or at least in the results overview.
  2. [Throughout] Minor typographical issues: ``Nermivoski'' should be ``Nemirovski''; ``irregardless'' should be ``regardless''; the notation O_{t,l} is defined but only used in the proof sketch; the proof of Lemma 12 has a line where log(n√ρ/d) is written with a square root that is not typeset consistently. These do not affect the mathematics.
  3. [Section 4, Theorem 3] The statement ``d be larger than some constant'' is vague; the proof seems to require d sufficiently large in the Fano/packing argument. It would be helpful to state the constant explicitly or say ``d ≥ C for a universal constant C'' to match the style of Theorem 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main lower and upper bounds are self-contained; self-citations are auxiliary and not load-bearing.

full rationale

The core derivation chain is not circular. Theorem 1's lower bound is proved in Section 3.1 from an explicit hard distribution (a Nemirovski-like loss with a subspace regularizer), with the required information upper bound (Lemma 1) and information lower bound (Lemmas 2-3 and the Fano variant in Appendix B.1.1) established by direct arguments rather than imported from the paper's own conclusions. No parameter is fitted to force the bound; constants such as C1=480 are proof-administrative. Theorem 5 is the same information argument with the information-capacity bound replaced by a Gamma-bit bound, so it is equally self-contained. The smooth lower bound (Theorem 3) is a reduction from DP mean estimation using standard fingerprinting lemmas and a loss construction whose minimizer encodes the mean; it does not assume the target runtime. The upper bounds (Theorems 2 and 4) are direct analyses of DP-SGD and Phased SGD; their complexity statements are derived from standard SGD and privacy-composition lemmas, not from matching the lower bound. The paper explicitly scopes its non-smooth lower bound to the non-adaptive-batch protocol of Algorithm 1 (Section 2 after Definition 3: 'The non-adaptivity assumption is necessary both for this framework to be meaningful and for our lower bounds to hold'), which is an honest modeling restriction rather than a circular definition. Some auxiliary results are cited from papers co-authored by Menart ([BGM23, Theorem 1] and [ABG+22, Section 5] in Appendix D.1), but these are published theorems with stated assumptions, used only for the DP-ERM/DP-SCO relationship, not for the paper's central lower-bound claims; they are therefore not load-bearing circularity. Any arithmetic or statement-level concerns in the paper (e.g., the exact sqrt(rho) factor in Theorem 2's displayed complexity) are correctness issues, not instances of a claim being assumed by construction, and do not change the circularity verdict.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new physical entities. It relies on standard tools in convex optimization and privacy; the hard-instance constants are proof scaffolding rather than fitted parameters.

free parameters (3)
  • C1 = 480
    Constant in the hard loss construction (Section 3.1), chosen to make various probabilistic inequalities work; not fitted to data, but hand-picked.
  • C2 = universal constant (unspecified numeric value)
    Used in the assumption d ≥ C2 B²L²/α²; existence is argued, not given a numeric value.
  • K (number of problem vectors) = 1/(C1² α²)
    Set in the hard instance; governs the trade-off between problem difficulty and dimension.
assumptions (7)
  • standard math Johnson-Lindenstrauss lemma
    Used in Lemma 3 (Appendix B) to show the projection of a random subspace concentrates.
  • standard math Fano's inequality (variant in Lemma 10)
    Used in Lemma 2/B.1 to lower bound mutual information needed for estimation.
  • standard math Packing number bounds for Euclidean balls (Vershynin)
    Used to upper/lower bound entropy of discretized problem vectors.
  • domain assumption zCDP group privacy and Rényi divergence properties
    Relied on in Lemma 1 to bound information leakage from a ρ-zCDP oracle.
  • domain assumption Privacy amplification via subsampling (Lemma 6, modified from BNSV15)
    Used in upper bound (Lemma 12) and smooth upper bound to convert zCDP/tCDP guarantees to (ε,δ)-DP.
  • standard math Convergence rate of SGD with noise (e.g., BFTT19 Lemma 3.3)
    Used in Lemma 11 to show DP-SGD accuracy.
  • standard math Fingerprinting lemma / DP mean estimation lower bound (DSS+15)
    Used in Theorem 6 proof for the smooth lower bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Gradient Complexity of Private Optimization with Private Oracles." pith.science (2026). https://pith.science/paper/EG5N5NDQ

@misc{pith2026251113999,
  author       = {Pith},
  title        = {Pith review of: On the Gradient Complexity of Private Optimization with Private Oracles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EG5N5NDQ}},
  note         = {Machine review of arXiv:2511.13999}
}
abstract

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(\min\{\frac{\sqrt{d}}{\alpha^2}, \frac{d}{\log(1/\alpha)}\})$ is necessary to achieve $\alpha$ excess risk on problems of dimension $d$ when $d \geq 1/\alpha^2$. Upper bounds via DP-SGD show these results are tight when $d>\tilde{\Omega}(1/\alpha^4)$. We further show our lower bound can be strengthened to $\Omega(\min\{\frac{d}{\bar{m}\alpha^2}, \frac{d}{\log(1/\alpha)} \})$ for algorithms which use minibatches of size at most $\bar{m} < \sqrt{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 $\tilde{\Omega}\big(\frac{\sqrt{d}}{\alpha} + \min\{\frac{1}{\alpha^2}, n\}\big)$, 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 $\Omega\big(\min\{\frac{d}{\alpha^2\Gamma}, \frac{d}{\log(1/\alpha)}\}\big)$ oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

57 extracted references · 3 canonical work pages

  1. [1]

    Differentially private generalized linear models revisited

    Raman Arora, Raef Bassily, Crist \'o bal Guzm \'a n, Michael Menart, and Enayat Ullah. Differentially private generalized linear models revisited. In Advances in Neural Information Processing Systems , volume 35. Curran Associates, Inc., 2022

    2022

  2. [2]

    Faster rates of convergence to stationary points in differentially private optimization

    Raman Arora, Raef Bassily, Tom\' a s Gonz\' a lez, Crist\' o bal A Guzm\' a n, Michael Menart, and Enayat Ullah. Faster rates of convergence to stationary points in differentially private optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International C...

    2023

  3. [3]

    Bartlett, Pradeep Ravikumar, and Martin J

    Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory , 58(5):3235--3249, 2012. https://doi.org/10.1109/TIT.2011.2182178 doi:10.1109/TIT.2011.2182178

    arXiv 2012

  4. [4]

    Deep learning with differential privacy

    Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security , pages 308--318, 2016

    2016

  5. [5]

    Information-constrained optimization: can adaptive processing of gradients help? In M

    Jayadev Acharya, Clement Canonne, Prathamesh Mayekar, and Himanshu Tyagi. Information-constrained optimization: can adaptive processing of gradients help? In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems , volume 34, pages 7126--7138. Curran Associates, Inc., 2021. UR...

    2021

  6. [6]

    Private stochastic convex optimization: Optimal rates in l1 geometry

    Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in l1 geometry. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning , volume 139 of Proceedings of Machine Learning Research , pages 393--403. PMLR, 18--24 Jul 2021. URL: https://proceedi...

    2021

  7. [7]

    Qsgd: Communication-efficient sgd via gradient quantization and encoding

    Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 30. Curran Associates, Inc., 2017. URL: https...

    2017

  8. [8]

    Communication complexity of distributed convex learning and optimization

    Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1 , NIPS'15, page 1756–1764, Cambridge, MA, USA, 2015. MIT Press

    2015

Show all 57 references
  1. [9]

    Privacy amplification by subsampling: Tight analyses via couplings and divergences

    Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems , 31, 2018

    2018

  2. [10]

    Rothblum, and Thomas Steinke

    Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2018, page 74–86, New York, NY, USA, 2018. Association for Computing Machinery...

    2018

  3. [11]

    Stability and generalization

    Olivier Bousquet and Andr \'e Elisseeff. Stability and generalization. The Journal of Machine Learning Research , 2:499--526, 2002

    2002

  4. [12]

    Stability of stochastic gradient descent on nonsmooth convex losses

    Raef Bassily, Vitaly Feldman, Crist \'o bal Guzm \'a n, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems , 33, 2020

    2020

  5. [13]

    Private stochastic convex optimization with optimal rates

    Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch \' e - Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural...

    2019

  6. [14]

    Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap

    Raef Bassily, Crist \'o bal Guzm \'a n, and Michael Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory ,...

    2023

  7. [15]

    Private algorithms for stochastic saddle points and variational inequalities: Beyond euclidean geometry

    Raef Bassily, Crist\' o bal Guzm\' a n, and Michael Menart. Private algorithms for stochastic saddle points and variational inequalities: Beyond euclidean geometry. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neura...

    2024

  8. [16]

    Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory

    G\' a bor Braun, Crist\' o bal Guzm\' a n, and Sebastian Pokutta. Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Trans. Inf. Theor. , 63(7):4709–4724, July 2017. https://doi.org/10.1109/TIT.2017.2701343 doi:10.1109/TIT.2017.2701343

    2017

  9. [17]

    Complexity of highly parallel non-smooth convex optimization

    Sebastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d\'Alch\' e Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing...

    2019

  10. [18]

    Differentially Private Release and Learning of Threshold Functions

    Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially Private Release and Learning of Threshold Functions . In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , pages 634--649, Los Alamitos, CA, USA, October 2015. IEEE Computer Society...

    2015 doi

  11. [19]

    Concentrated differential privacy: Simplifications, extensions, and lower bounds

    Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors, Theory of Cryptography , pages 635--658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg

    2016

  12. [20]

    Private empirical risk minimization: Efficient algorithms and tight error bounds

    Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS 2014). , pages 464--473. 2014

    2014

  13. [21]

    Fingerprinting codes and the price of approximate differential privacy

    Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing , 47(5):1888--1938, 2018. https://arxiv.org/abs/https://doi.org/10.1137/15M1033587 arXiv:https://doi.org/10.1137/15M1033587 , https://...

    1938 doi

  14. [22]

    Choquette-Choo, Arun Ganesh, and Abhradeep Guha Thakurta

    Christopher A. Choquette-Choo, Arun Ganesh, and Abhradeep Guha Thakurta. Near-optimal rates for o(1)-smooth dp-sco with a single epoch and large batches. In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory ...

    2025

  15. [23]

    Choquette-Choo, H

    Christopher A. Choquette-Choo, H. Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Proceedings of the 40th International Conference on Machine Learning , ICML'23. JMLR.org, 2023

    2023

  16. [24]

    Advancing Differential Privacy : Where We Are Now and Future Directions for Real - World Deployment

    Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Yangsibo Huang, Matthew Jagielski, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, Nicolas Papernot, Ryan Rogers, Milan Shen, Shuang Song, Weijie Su, Andreas Terzis, Abhradeep Thakurta, Sergei Vassil...

    2024

  17. [25]

    Resqueing parallel and private stochastic convex optimization

    Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2031--2058, 2023. https://doi.o...

    2023

  18. [26]

    Differentially private empirical risk minimization

    Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research , 12(Mar):1069--1109, 2011

    2011

  19. [27]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing) . Wiley-Interscience, USA, 2006

    2006

  20. [28]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference , pages 265--284. Springer, 2006

    2006

  21. [29]

    Robust traceability from trace amounts

    Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 650--669, 2015. https://doi.org/10.1109/FOCS.2015.46 doi:10.1109/FOCS.2015.46

    2015 doi

  22. [30]

    Duchi and Martin J

    John C. Duchi and Martin J. Wainwright. Distance-based and continuum fano inequalities with applications to statistical estimation, 2013. URL: https://arxiv.org/abs/1311.2669, https://arxiv.org/abs/1311.2669 arXiv:1311.2669

    2013 arXiv

  23. [31]

    Private stochastic convex optimization: optimal rates in linear time

    Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 439--449, 2020

    2020

  24. [32]

    Roy, and Ali Ramezani-Kebrya

    Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M. Roy, and Ali Ramezani-Kebrya. Adaptive gradient quantization for data-parallel sgd. In Proceedings of the 34th International Conference on Neural Information Processing Systems , NIPS '20, Red Hook, NY, USA, ...

    2020

  25. [33]

    Private convex optimization via exponential mechanism

    Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In Conference on Learning Theory , pages 1948--1989. PMLR, 2022

    1948

  26. [34]

    Lower bounds and nearly optimal algorithms in distributed learning with communication compression

    Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Syst...

    2022

  27. [35]

    Train faster, generalize better: stability of stochastic gradient descent

    Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: stability of stochastic gradient descent. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48 , ICML'16, page 1225–1234. JMLR.org, 2016

    2016

  28. [36]

    Accelerating stochastic gradient descent using predictive variance reduction

    Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems , volume 26. Curran Associates, Inc.,...

    2013

  29. [37]

    Private non-smooth erm and sco in subquadratic steps

    Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems , volume 34, pages 4053--4064. Curra...

    2021

  30. [38]

    Brendan McMahan

    Anastasiia Koloskova, Ryan McKenna, Zachary Charles, John Rush, and H. Brendan McMahan. Gradient descent with linearly correlated noise: Theory and applications to differential privacy. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances i...

    2023

  31. [39]

    Practical and private (deep) learning without sampling or shuffling

    Peter Kairouz, Brendan Mcmahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning , volum...

    2021

  32. [40]

    Private federated learning without a trusted server: Optimal algorithms for convex losses

    Andrew Lowy and Meisam Razaviyayn. Private federated learning without a trusted server: Optimal algorithms for convex losses. In The Eleventh International Conference on Learning Representations , 2023. URL: https://openreview.net/forum?id=TVY6GoURrw

    2023

  33. [41]

    Limits on gradient compression for stochastic optimization

    Prathamesh Mayekar and Himanshu Tyagi. Limits on gradient compression for stochastic optimization. In 2020 IEEE International Symposium on Information Theory (ISIT) , pages 2658--2663, 2020. https://doi.org/10.1109/ISIT44484.2020.9174075 doi:10.1109/ISIT44484.2020.9174075

    2020

  34. [42]

    Ratq: A universal fixed-length quantizer for stochastic optimization

    Prathamesh Mayekar and Himanshu Tyagi. Ratq: A universal fixed-length quantizer for stochastic optimization. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics , volume 108 of Proc...

    2020

  35. [43]

    Differentially private non-convex optimization under the kl condition with optimal rates

    Michael Menart, Enayat Ullah, Raman Arora, Raef Bassily, and Cristobal Guzman. Differentially private non-convex optimization under the kl condition with optimal rates. In Claire Vernade and Daniel Hsu, editors, Proceedings of The 35th International Conference on Algorithmic L...

    2024

  36. [44]

    A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. SIAM Review , 27(2):264--265, 1985. https://arxiv.org/abs/https://doi.org/10.1137/1027074 arXiv:https://doi.org/10.1137/1027074 , https://doi.org/10.1137/1027074 doi:10.1137/1027074

    1985 doi

  37. [45]

    How to dp-fy ml: A practical tutorial to machine learning with differential privacy

    Natalia Ponomareva, Sergei Vassilvitskii, Zheng Xu, Brendan McMahan, Alexey Kurakin, and Chiyaun Zhang. How to dp-fy ml: A practical tutorial to machine learning with differential privacy. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining ...

    2023

  38. [46]

    a is\" a , Joonas J\

    Ossi R\" a is\" a , Joonas J\" a lk\" o , and Antti Honkela. Subsampling is not magic: why large batch sizes work for differentially private stochastic optimisation. In Proceedings of the 41st International Conference on Machine Learning , ICML'24. JMLR.org, 2024

    2024

  39. [47]

    Optimal convergence rates for convex distributed optimization in networks

    Kevin Scaman, Francis Bach, S \'e bastien Bubeck, Yin Tat Lee, and Laurent Massouli \'e . Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research , 20(159):1--31, 2019. URL: http://jmlr.org/papers/v20/19-543.html

    2019

  40. [48]

    Stich, Jean-Baptiste Cordonnier, and Martin Jaggi

    Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. NIPS'18, page 4452–4463, Red Hook, NY, USA, 2018. Curran Associates Inc

    2018

  41. [49]

    Characterizing the accuracy-communication-privacy trade-off in distributed stochastic convex optimization

    Sudeep Salgia, Nikola Pavlovic, Yuejie Chi, and Qing Zhao. Characterizing the accuracy-communication-privacy trade-off in distributed stochastic convex optimization. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International...

    2025

  42. [50]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms . Cambridge university press, 2014

    2014

  43. [51]

    Public-data assisted private stochastic optimization: Power and limitations

    Enayat Ullah, Michael Menart, Raef Bassily, Crist \'o bal A Guzm \'a n, and Raman Arora. Public-data assisted private stochastic optimization: Power and limitations. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024. URL: https://openreview...

    2024

  44. [52]

    High-Dimensional Probability: An Introduction with Applications in Data Science

    Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. https://doi.org/10.1017/9781108231596 doi:10.1017/9781108231596

    2018 doi

  45. [53]

    The min-max complexity of distributed stochastic convex optimization with intermittent communication

    Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory , v...

    2021

  46. [54]

    Tight complexity bounds for optimizing composite objectives

    Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objectives. In Proceedings of the 30th International Conference on Neural Information Processing Systems , NIPS'16, page 3646–3654, Red Hook, NY, USA, 2016. Curran Associates Inc

    2016

  47. [55]

    Communication compression techniques in distributed deep learning: A survey

    Zeqin Wang, Ming Wen, Yuedong Xu, Yipeng Zhou, Jessie Hui Wang, and Liang Zhang. Communication compression techniques in distributed deep learning: A survey. Journal of Systems Architecture , 142:102927, 2023. URL: https://www.sciencedirect.com/science/article/pii/S13837621230...

    2023

  48. [56]

    Gradient perturbation is underrated for differentially private convex optimization

    Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie-Yan Liu. Gradient perturbation is underrated for differentially private convex optimization. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence , IJCAI'20, 2021

    2021

  49. [57]

    Bring your own algorithm for optimal differentially private stochastic minimax optimization

    Liang Zhang, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. Bring your own algorithm for optimal differentially private stochastic minimax optimization. In Advances in Neural Information Processing Systems , volume 35. Curran Associates, Inc., 2022

    2022

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.