mlsanityData to 7 Oct 2026

Faster Differentially Private Convex Optimization via Second-Order Methods

arXiv 2305.13209 ↗First posted 22 May 2023cs.LG cs.CR math.OCcited by 13

Not on the map. Why?

Abstract (arXiv)

Differentially private (stochastic) gradient descent is the workhorse of DP private machine learning in both the convex and non-convex settings. Without privacy constraints, second-order methods, like Newton's method, converge faster than first-order methods like gradient descent. In this work, we investigate the prospect of using the second-order information from the loss function to accelerate DP convex optimization. We first develop a private variant of the regularized cubic Newton method of Nesterov and Polyak, and show that for the class of strongly convex loss functions, our algorithm has quadratic convergence and achieves the optimal excess loss. We then design a practical second-order DP algorithm for the unconstrained logistic regression problem. We theoretically and empirically study the performance of our algorithm. Empirical results show our algorithm consistently achieves the best excess loss compared to other baselines and is 10-40x faster than DP-GD/DP-SGD.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 26 of its 55 references that are in the map. First posted on arXiv 22 May 2023.

Builds on

26 of 55 references.

References · 26

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2021Convex optimizationcited by 2,479
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  6. 2019R'enyi Differential Privacy of the Sampled Gaussian Mechanismcited by 199
  7. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  8. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  9. 2016Concentrated Differential Privacycited by 139
  10. 2019Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Modelcited by 116
  11. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  12. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
14 more
  1. 2017Efficient Private ERM for Smooth Objectivescited by 61
  2. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  3. 2019RSN: Randomized Subspace Newtoncited by 34
  4. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  5. 2015Convergence rates of sub-sampled Newton methodscited by 32
  6. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  7. 2021Differentially private inference via noisy optimizationcited by 27
  8. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 25
  9. 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
  10. 2016Sub-sampled Newton Methods with Non-uniform Samplingcited by 21
  11. 2020Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methodscited by 16
  12. 2022Composition Theorems for Interactive Differential Privacycited by 10
  13. 2022Concurrent Composition Theorems for Differential Privacycited by 8
  14. 2016Sub-Sampled Newton Methods II: Local Convergence Ratescited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 5; 2026: 2.

13 papers.

Sort:

  1. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  2. 2024Shifted Interpolation for Differential Privacycited by 10
  3. 2024Bounding the Excess Risk for Linear Models Trained on Marginal-Preserving, Differentially-Private, Synthetic Datacited by 3
  4. 2024Private Geometric Mediancited by 3
  5. 2024Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systemscited by 3
  6. 2025Purifying Approximate Differential Privacy with Randomized Post-processingcited by 2
  7. 2024Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacycited by 1
  8. 2025Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellationcited by 1
  9. 2025Multi-Class Support Vector Machine with Differential Privacycited by 1
  10. 2025Correlating Cross-Iteration Noise for DP-SGD using Model Curvaturecited by 1
  11. 2025Differentially Private Hyperparameter Tuning using Local Bayesian Optimizationcited by 0
  12. 2026Differentially Private Truncation of Unbounded Data via Public Second Momentscited by 0
1 more
  1. 2026DP-KFC: Data-Free Preconditioning for Privacy-Preserving Deep Learningcited by 0