Research map / Optimization / Nonconvex and smooth optimization
Faster Algorithms for User-Level Private Stochastic Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives faster user-level DP stochastic convex optimization algorithms: a linear-time phased-SGD variant with outlier iterate removal, and accelerated minibatch methods with optimal excess risk at about (mn)^{9/8} (smooth) and n^{11/8}m^{5/4} (non-smooth) gradient complexity.
Problem
User-level differentially private stochastic convex optimization is either slow (requiring (mn)^{3/2} or (mn)^3 gradient computations) or relies on restrictive smoothness and user-count assumptions, limiting practical use.
Approach
Apply private outlier removal to SGD iterates (for linear time) and to minibatch user gradients combined with AboveThreshold, privacy amplification by subsampling, accelerated SGD and iterative localization (for optimal risk with faster runtime), plus randomized smoothing for non-smooth losses.
Key results
- Linear-time algorithm achieves excess risk approximately 1/sqrt(nm eps) + sqrt(d)/(sqrt(nm) eps) under beta < sqrt(nmd), without polynomial-in-d user requirements.
- Accelerated algorithm achieves optimal excess risk for smooth losses with about (mn)^{9/8} gradient computations, versus (mn)^{3/2} previously.
- For non-smooth losses, optimal excess risk with n^{11/8} m^{5/4} gradient computations, faster than prior (nm)^3 by a factor n^{13/8} m^{7/4}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use accelerated minibatch SGD with user-gradient outlier removal and localization | User-level DP SCO with smooth losses · User-level DP SCO, smooth losses | gradient complexity: mn\left(1 + \varepsilon\left(\frac{\beta R}{L}\right)^{1/4}\left((mn)^{1/8} \wedge \left(\frac{\varepsilon^2 n^2 m}{d} \ | Helped |
| apply randomized convolution smoothing before the accelerated algorithm | Accelerated Phased ERM · User-level DP SCO, non-smooth losses | gradient complexity: mn\left(1 +n^{3/8}m^{1/4}\varepsilon^{1/4}\right) versus (nm)^3 + (mn)^2\sqrt{d} | Helped |
| privately remove outlier SGD iterates instead of outlier gradients | Phased SGD with Outlier Iterate Removal · User-level DP SCO, smooth losses | gradient complexity: \leq nm | Helped |
| use randomized convolution smoothing to handle non-smooth losses | Accelerated Phased ERM · User-level DP SCO, non-smooth losses | excess risk: LR \cdot \widetilde{O}\left(\frac{1}{\sqrt{mn}} + \frac{\sqrt{d \log(1/\delta)}}{\varepsilon n \sqrt{m}} \right) | Helped |
Limitations
- Linear-time algorithm does not reach optimal excess risk; the iterate-based outlier removal adds excess noise due to polynomial dependence on T.
- Results are for approximate (eps, delta)-DP only; pure DP rates are left open.
- Assumes n^{1-o(1)} >= log(d)/eps users, with logarithmic user requirement.
Experimental setup
Metrics: excess population risk gradient complexity
Baselines: Level et al. user-level DP SCO algorithm (mn)^{3/2} smooth Ghazi et al. user-level DP SCO with (nm)^3 non-smooth user-level LDP linear-time algorithm
Builds on: FriendlyCore AboveThreshold privacy amplification by subsampling accelerated minibatch SGD (AC-SA) iterative localization
Closest papers by meaning
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.92)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.91)
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.90)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.90)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.89)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.