# Faster Differentially Private Convex Optimization via Second-Order Methods

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

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model](https://mlsanity.com/paper/1907.04164/) (2019)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019)
- [Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent](https://mlsanity.com/paper/2006.06783/) (2020)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016)
- [Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods](https://mlsanity.com/paper/2003.13607/) (2020)
- [Composition Theorems for Interactive Differential Privacy](https://mlsanity.com/paper/2207.09397/) (2022)
- [Concurrent Composition Theorems for Differential Privacy](https://mlsanity.com/paper/2207.08335/) (2022)
- [Sub-Sampled Newton Methods II: Local Convergence Rates](https://mlsanity.com/paper/1601.04738/) (2016)

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

- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Shifted Interpolation for Differential Privacy](https://mlsanity.com/paper/2403.00278/) (2024)
- [Bounding the Excess Risk for Linear Models Trained on Marginal-Preserving, Differentially-Private, Synthetic Data](https://mlsanity.com/paper/2402.04375/) (2024)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems](https://mlsanity.com/paper/2407.12396/) (2024)
- [Purifying Approximate Differential Privacy with Randomized Post-processing](https://mlsanity.com/paper/2503.21071/) (2025)
- [Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacy](https://mlsanity.com/paper/2408.04315/) (2024)
- [Differentially Private Hyperparameter Tuning using Local Bayesian Optimization](https://mlsanity.com/paper/2502.06044/) (2025)
- [Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation](https://mlsanity.com/paper/2506.02563/) (2025)
- [Multi-Class Support Vector Machine with Differential Privacy](https://mlsanity.com/paper/2510.04027/) (2025)
- [Correlating Cross-Iteration Noise for DP-SGD using Model Curvature](https://mlsanity.com/paper/2510.05416/) (2025)
- [Differentially Private Truncation of Unbounded Data via Public Second Moments](https://mlsanity.com/paper/2602.22282/) (2026)
- [DP-KFC: Data-Free Preconditioning for Privacy-Preserving Deep Learning](https://mlsanity.com/paper/2605.13418/) (2026)

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