# Private optimization in the interpolation regime: faster rates and hardness results

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 31 Oct 2022.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [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)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)

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

- [Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime](https://mlsanity.com/paper/2302.14154/) (2023)
- [The Relative Gaussian Mechanism and its Application to Private Gradient Descent](https://mlsanity.com/paper/2308.15250/) (2023)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)

## Abstract (arXiv)

In non-private stochastic convex optimization, stochastic gradient methods converge much faster on interpolation problems -- problems where there exists a solution that simultaneously minimizes all of the sample losses -- than on non-interpolating ones; we show that generally similar improvements are impossible in the private setting. However, when the functions exhibit quadratic growth around the optimum, we show (near) exponential improvements in the private sample complexity. In particular, we propose an adaptive algorithm that improves the sample complexity to achieve expected error α from fracdvarepsilon √α to frac1αρ + fracdvarepsilon logleft(frac1αright) for any fixed ρ >0, while retaining the standard minimax-optimal sample complexity for non-interpolation problems. We prove a lower bound that shows the dimension-dependent term is tight. Furthermore, we provide a superefficiency result which demonstrates the necessity of the polynomial term for adaptive algorithms: any algorithm that has a polylogarithmic sample complexity for interpolation problems cannot achieve the minimax-optimal rates for the family of non-interpolation problems.