# Faster Rates of Private Stochastic Convex Optimization

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 31 Jul 2021.

## Builds on (most cited first, 30 of 31)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [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)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent](https://mlsanity.com/paper/2006.06783/) (2020)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case](https://mlsanity.com/paper/1802.04085/) (2018)
- [Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy](https://mlsanity.com/paper/2011.05934/) (2020)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate](https://mlsanity.com/paper/1901.09344/) (2019)
- [Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions](https://mlsanity.com/paper/1805.04577/) (2018)
- [Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations](https://mlsanity.com/paper/1812.06825/) (2018)
- [A Knowledge Transfer Framework for Differentially Private Sparse Learning](https://mlsanity.com/paper/1909.06322/) (2019)
- [A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer](https://mlsanity.com/paper/1709.02909/) (2017)

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

- [Multi-hop Question Answering under Temporal Knowledge Editing](https://mlsanity.com/paper/2404.00492/) (2024)
- [Prompt-SAW: Leveraging Relation-Aware Graphs for Textual Prompt Compression](https://mlsanity.com/paper/2404.00489/) (2024)
- [Leveraging Logical Rules in Knowledge Editing: A Cherry on the Top](https://mlsanity.com/paper/2405.15452/) (2024)
- [Dialectical Alignment: Resolving the Tension of 3H and Security Threats of LLMs](https://mlsanity.com/paper/2404.00486/) (2024)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [MONAL: Model Autophagy Analysis for Modeling Human-AI Interactions](https://mlsanity.com/paper/2402.11271/) (2024)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Private Language Models via Truncated Laplacian Mechanism](https://mlsanity.com/paper/2410.08027/) (2024)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [Differentially Private Stochastic Gradient Descent with Low-Noise](https://mlsanity.com/paper/2209.04188/) (2022)
- [Differentially Private Sparse Linear Regression with Heavy-tailed Responses](https://mlsanity.com/paper/2506.06861/) (2025)

## Abstract (arXiv)

In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) and provide excess population risks for some special classes of functions that are faster than the previous results of general convex and strongly convex functions. In the first part of the paper, we study the case where the population risk function satisfies the Tysbakov Noise Condition (TNC) with some parameter θ>1. Specifically, we first show that under some mild assumptions on the loss functions, there is an algorithm whose output could achieve an upper bound of tildeO((frac1√n+frac√dlog frac1δnε)^fracθθ-1) for (ε, δ)-DP when θ≥ 2, here n is the sample size and d is the dimension of the space. Then we address the inefficiency issue, improve the upper bounds by Poly(log n) factors and extend to the case where θ≥ barθ>1 for some known barθ. Next we show that the excess population risk of population functions satisfying TNC with parameter θ≥ 2 is always lower bounded by Omega((fracdnε)^fracθθ-1)  and Omega((frac√dlog frac1δnε)^fracθθ-1) for ε-DP and (ε, δ)-DP, respectively. In the second part, we focus on a special case where the population risk function is strongly convex. Unlike the previous studies, here we assume the loss function is em non-negative and em the optimal value of population risk is sufficiently small. With these additional assumptions, we propose a new method whose output could achieve an upper bound of O(fracdlogfrac1δn2ε2+frac1nτ) for any τ≥ 1 in (ε,δ)-DP model if the sample size n is sufficiently large.