Private Stochastic Convex Optimization: Optimal Rates in Linear Time

Understand

We study differentially private (DP) algorithms for stochastic convex optimization: the problem of minimizing the population loss given i.i.d.

• samples from a distribution over convex loss functions.
• A recent work of Bassily et al.
• (2019) has established the optimal bound on the excess population loss achievable given $n$ samples.