Research map / Learning theory and algorithms / Sample complexity
Improved Sample Complexity for Private Nonsmooth Nonconvex 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 improved differentially private sample complexity for finding Goldstein-stationary points of nonsmooth nonconvex objectives via a single-pass zero-order method with sensitivity-reduced gradient estimators, plus a multi-pass ERM method and an ERM-to-population generalization result.
Problem
Differentially private optimization of stochastic or empirical objectives that are neither smooth nor convex, targeting (alpha,beta)-Goldstein-stationary points with lower sample complexity.
Approach
Reduce gradient-estimator sensitivity with high probability via sub-Gaussian concentration (large number of random directions m), so that the minibatch sensitivity drops by a factor of d, combined with randomized smoothing, O2NC, and the tree mechanism in a single-pass scheme; a multi-pass ERM variant plus a new ERM-to-population Goldstein-stationarity generalization bound.
Key results
- Single-pass DP algorithm needs n = Ω~(sqrt(d)/(αβ^3) + d/(εαβ^2)), a sqrt(d) factor improvement over prior d/(αβ^3)+d^{3/2}/(εαβ^2).
- Multi-pass DP ERM achieves n = Ω~(d^{3/4}/(εα^{1/2}β^{3/2})), sublinear in d for the private term.
- Population generalization holds with an extra d/β^2 term in sample complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the previous single-pass method with the proposed single-pass algorithm | Private nonsmooth nonconvex optimization · Stochastic NSNC optimization | sample complexity: \frac{d}{\alpha\beta^3}+\frac{d^{3/2}}{\varepsilon\alpha\beta^2} -> \frac{\sqrt{d}}{\alpha\beta^3}+\frac{d}{\varepsilon\ | Helped |
| Use a multi-pass private ERM algorithm | Private nonsmooth nonconvex optimization · Empirical NSNC optimization | sample complexity: \frac{d^{3/4}}{\varepsilon\alpha^{1/2}\beta^{3/2}} | Helped |
| Generalize the multi-pass ERM guarantee from empirical to population loss | Proposed multi-pass algorithm · Stochastic NSNC optimization | sample complexity: +\frac{d}{\beta^2} | Mixed |
| Use a first-order gradient oracle instead of a zero-order oracle | Proposed single-pass algorithm · Stochastic NSNC optimization | sample complexity | No clear effect |
| Use a first-order gradient oracle instead of a zero-order oracle | Proposed single-pass algorithm · Stochastic NSNC optimization | oracle calls: \widetilde{\Omega}(d^2) times less | Helped |
| Use Lasry-Lions smoothing and component-wise Goldstein-stationarity | Private empirical NSNC optimization · Empirical NSNC optimization | sample complexity: \widetilde{\Omega}\left(\frac{R^{1/3}L^{4/3}d^{2/3}}{\varepsilon\alpha^{1/3}\beta}\right) | Helped |
Surprising findings
- The non-private sample complexity term has sublinear dimension dependence, contrary to a previous claim of impossibility.
Limitations
- Guarantees are approximate (epsilon,delta)-DP rather than Rényi DP, inherent to conditioning on high-probability events.
- Upper and lower bounds do not match even in the smooth setting.
- Computationally inefficient optimal-smoothing variant is only sketched as evidence.
Experimental setup
Metrics: sample complexity
Baselines: Zhang et al. 2024 single-pass zero-order DP algorithm
Builds on: O2NC randomized smoothing tree mechanism Goldstein stationarity
Closest papers by meaning
- Private Zeroth-Order Nonsmooth Nonconvex Optimization (ICLR 2024 · similarity 0.91)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.90)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.89)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.89)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.89)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 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.