mlsanityData to 14 Oct 2026

Differentially Private Online-to-Batch for Smooth Losses

arXiv 2210.06593 ↗First posted 12 Oct 2022cs.LG cs.CRcited by 5

Not on the map. Why?

Abstract (arXiv)

We develop a new reduction that converts any online convex optimization algorithm suffering O(√T) regret into an ε-differentially private stochastic convex optimization algorithm with the optimal convergence rate tilde O(1/√T + √d/ε T) on smooth losses in linear time, forming a direct analogy to the classical non-private "online-to-batch" conversion. By applying our techniques to more advanced adaptive online algorithms, we produce adaptive differentially private counterparts whose convergence rates depend on apriori unknown variances or parameter norms.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 18 of its 42 references that are in the map. First posted on arXiv 12 Oct 2022.

Builds on

18 of 42 references.

References · 18

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2017Renyi Differential Privacycited by 650
  4. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  5. 2021Differentially Private Fine-tuning of Language Modelscited by 400
  6. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  9. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  10. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 125
  11. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  12. 2022Toward Training at ImageNet Scale with Differential Privacycited by 87
6 more
  1. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  2. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  3. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  4. 2022Large Scale Transfer Learning for Differentially Private Image Classificationcited by 41
  5. 2022Private Adaptive Optimization with Side Informationcited by 38
  6. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21

Built on by

Cited by year

Citing papers per year: 2024: 4; 2025: 1.

5 papers.

  1. 2024Efficient and Near-Optimal Noise Generation for Streaming Differential Privacycited by 17
  2. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  3. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  4. 2024Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batchescited by 1
  5. 2025Private Geometric Median in Nearly-Linear Timecited by 1