AI for Mathematics and Optimization, ETH Zurich, Spring 2026

Nonsmooth DP-SCO: Optimal Rates in Linear Time?

Differential privacy makes a learned model insensitive to any single training sample. Its statistical price is known; the computational price of nonsmoothness is not. Smooth convex losses reach the optimal private risk with \(O(n)\) stochastic first-order calls, but whether general nonsmooth losses can do the same in every dimension regime remains open. Our findings map two scoped barriers and one structured route forward.

Micha Henheik, Filip Oliver Klimoszek, David Korčák, Felix Quernheim

The open problem

The Rate Is Known. The Linear-Time Algorithm Is Not.

We draw \(n\) i.i.d. samples \(S=(\xi_1,\ldots,\xi_n)\) and seek to minimize the population risk

\[ \min_{x\in \mathcal X} F(x) := \mathbb E_{\xi}[f(x;\xi)], \qquad \mathcal X\subset \mathbb R^d. \]

Every sample loss \(f(\cdot;\xi)\) is convex and \(L\)-Lipschitz on a closed convex domain \(\mathcal X\subset\mathbb R^d\) of diameter \(R\), but may be nonsmooth. Differential privacy requires the distribution of the released model to change only slightly when one sample in \(S\) is replaced [14].

Up to constants, the best possible excess population risk is \[ \alpha_\star(R,L) \asymp RL\left( \frac{1}{\sqrt n} + \frac{\sqrt{d\log(1/\delta)}}{n\varepsilon} \right). \] The first term is ordinary statistical error; the second is the unavoidable privacy penalty. The unresolved question is computational: can this rate be reached with only \(O(n)\) stochastic gradient or subgradient evaluations for every \(d\)? Smooth losses can [3]; no such all-regime guarantee is known for general nonsmooth losses [1], [2].

What Was Known

Private ERM/SCO lower bounds and matching algorithms identify \(\alpha_\star(R,L)\) as the right population-risk scale, up to constants [1], [2]. For smooth convex losses, representative templates include noisy or gradient-perturbed SGD [2], privacy amplification by iteration for contractive updates, and phased output perturbation [3]. The latter constructions attain the optimal rate with linear gradient complexity.

For nonsmooth convex losses, the picture is more complicated. Stability of SGD gives optimal rates but with quadratic gradient complexity [4]. Later work by Asi, Feldman, Koren, and Talwar [5] and by Kulkarni, Lee, and Liu [6] reduced the complexity below quadratic, while Carmon, Jambulapati, Jin, Lee, Liu, Sidford, and Tian developed the ReSQue framework, which reaches near-linear complexity in favorable dimension regimes [9]. There are also positive special cases, notably generalized linear losses [7] and nonsmooth problems that can be reformulated as smooth private minimax problems [8].

Known nonsmooth algorithms improve over quadratic time, but the linear-time region does not cover every dimension regime. Here d ≈ nα and gradient complexity is shown as nβ, suppressing logarithms and privacy constants; lower β is better.
Gradient-complexity regimes for nonsmooth DP-SCO A line chart comparing Asi et al., Kulkarni et al., and Carmon et al. across alpha from zero to two. 1 1.25 1.5 0 1 2 α in d ≈ n^α β in complexity n^β near-linear
Carmon et al. [9] Kulkarni et al. [6] Asi et al. [5]

Where Is the Privacy Boundary?

An optimizer may see only private messages about first-order information, keep exact gradients internal and privatize selected states, or perturb only its final estimate. What the optimizer is allowed to see determines which argument applies. Smoothing is different: it provides no privacy by itself, but can make a loss regular enough for a private backend.

Three privacy boundaries. Our barriers cover two restricted access patterns; unrestricted internal and hybrid mechanisms remain open.
  1. At a proxy boundary Private proxy access raw minibatch privatize optimizer Finding 1 · scoped barrier for private proxy oracles
  2. Inside a trusted optimizer Exact internal access exact gradients hybrid private state Open · general nonsmooth \(O(n)\), for every \(d\)
  3. After optimization Perturb the final estimate estimate + noise release Finding 2 · scoped barrier for independent additive noise
Finding 3 · structured route. Residual-space smoothing can enable a smooth private backend; smoothing itself is not a privacy mechanism.

The boundary matters: differential privacy constrains the released distribution, not every exact gradient computed internally. Mechanisms that fit neither the private-proxy protocol nor independent additive output perturbation remain outside both barriers.

Three Findings

Finding 1 · External theorem

Private Proxy Oracles Face a Superlinear Barrier

Menart and Nikolov study a restricted access model in which a proxy sees raw first-order minibatches but the optimizer receives only a private message; queries within each minibatch are nonadaptive [10]. Their lower bound is external to this project; our contribution is interpreting what its access model means for the DP-SCO runtime gap. For \(L\)-Lipschitz nonsmooth losses on a domain of diameter \(B\), if every proxy response is \(\rho\)-zCDP (zero-concentrated DP) and empirical excess risk \(\alpha\) is achieved in dimension \(d\gtrsim B^2L^2/\alpha^2\), their min-form consequence gives

\[ T_{\rm grad} = \Omega\!\left( \min\left\{ \frac{B^2L^2\sqrt d}{\alpha^2\sqrt\rho}, \frac{d}{\log(BL/\alpha)} \right\} \right). \]

Using their ERM-to-SCO transfer, this can rule out linear time at the target risk in intermediate high-dimensional regimes, depending on the privacy parameters. It covers arbitrary private proxy messages—including noisy gradients or updated model states—but not algorithms that keep exact sensitive gradients internal and privatize a stable release. The insight is the access-model separation, not a universal impossibility result.

Finding 2 · Conditional barrier

High-Dimensional Independent Output Noise Can Overpay

Consider computing a non-private estimate \(A(S)\), then releasing \(A(S)+Z\) with data-independent noise \(Z\). Its effective neighboring dimension is \(k\) at scale \(\Delta\) if there are \(k\) neighboring dataset pairs whose output differences point in orthogonal directions:

\[ A(S'_j)-A(S_j)=\Delta u_j, \qquad j=1,\ldots,k. \]

Privacy must mask every direction. Any such independent additive-noise mechanism that is \((\varepsilon,\delta)\)-DP, for \(\varepsilon\in(0,1)\) and \(\delta\le c_0\varepsilon\) for a sufficiently small universal constant \(c_0\), therefore satisfies

\[ \mathbb E\|Z\|_2 \ge c\,\frac{\Delta\sqrt{k}}{\varepsilon}. \]

If \(k=d\), \(\Delta\gtrsim R/\sqrt n\), and the base estimator has the natural \(O(R/\sqrt n)\) error, the cone loss \(F_0(x)=L\|x-x^\star\|_2\) gives \[ \mathbb E[F_0(A(S)+Z)-F_0(x^\star)] \gtrsim \frac{LR\sqrt d}{\varepsilon\sqrt n} - O\!\left(\frac{LR}{\sqrt n}\right). \] When the leading term dominates, it exceeds the optimal privacy term by roughly \(\sqrt{n/\log(1/\delta)}\).

This is a diagnostic, not a general output-perturbation impossibility. Projection, data-dependent noise, phased mechanisms, and estimators whose neighboring movement is low-dimensional remain outside its scope. The one-dimensional noise ingredient follows the standard approximate-DP tradeoff of Geng, Ding, Guo, and Kumar [13].

Finding 3 · Conditional reduction

Smooth Only the Low-Dimensional Residual

The previous barriers leave room for structure. A more hopeful setting is when the nonsmooth part lives in a small residual space. Generalized linear losses are the motivating case: their nonsmooth part depends only on the scalar \(\langle x_\xi,w\rangle\). We ask what survives when this scalar is replaced by a genuinely \(k\)-dimensional residual:

\[ f(w;\xi) = s(w;\xi) + \psi_\xi(A_\xi w-b_\xi), \qquad A_\xi:\mathbb R^d\to\mathbb R^k,\quad k\ll d. \]

Here \(s(\cdot;\xi)\) is smooth and convex, \(A_\xi\) is linear, and \(\psi_\xi\) is convex, Lipschitz, and potentially nonsmooth. The key assumption is that applying \(A_\xi\) and its adjoint is efficient, while the proximal computation is controlled by the small residual dimension \(k\), rather than \(d\).

Apply the Moreau envelope only to \(\psi_\xi\) [12]. When \(\psi_\xi\) is \(G\)-Lipschitz, smoothing at scale \(\lambda\) adds at most \(\lambda G^2/2\) bias, while the added smoothness scales like \(1/\lambda\), up to constants determined by the residual map. One smoothed gradient requires one prox computation in \(\mathbb R^k\). Choosing \(\lambda\asymp\alpha_\star(R,L)/G^2\) puts the bias at the target risk scale.

If a linear-time smooth DP-SCO backend tolerates the resulting smoothness, the reduction reaches optimal risk with \(O(n)\) gradient/prox evaluations. The gain is computational, not statistical: the privacy penalty still depends on ambient dimension \(d\), while the nonsmooth primitive depends on residual dimension \(k\). Subject to the backend's smoothness requirement, the template extends scalar residual losses to robust multi-output, grouped, and low-rank spectral residuals.

What Remains Open

The center of the map is still blank. A full resolution needs either a general \(O(n)\)-query algorithm at risk \(\alpha_\star\), or a lower bound for unrestricted private algorithms—not just for a chosen noise mechanism.

  • Algorithmic route: control adaptive-point sensitivity without paying too much noise, smoothing bias, or regularization bias. Designs with exact internal access may combine phases, projections, or data-dependent noise while remaining outside both restricted models.
  • Lower-bound route: connect privacy of the released model directly to optimization error. An unrestricted method may compute sensitive gradients internally, so a transcript bound cannot simply assume those gradients are private.
  • Structured route: weaken the smoothness requirement imposed by the private backend, or identify broader classes where the computational dimension of nonsmoothness is smaller than \(d\).

AI Usage

This project is part of the AI for Mathematics and Optimization seminar at ETH Zurich. AI was useful only once we stopped treating it as a source of truth. We used models as a teacher for literature onboarding, a generator of candidate routes, and an adversarial auditor. Claims that survived were checked against papers, hand derivations, and, where feasible, Lean. Our acceptance rule was simple: every claim needed a source theorem, a hand-checkable derivation, or a machine-checked algebraic core.

The most useful outcomes came from failures we could expose. In the functional stochastic localization route [11], models repeatedly applied shared-point stability at different adaptive points. A second argument treated internal gradients as private releases. Explicit counterexamples and a return to the DP definition broke those arguments—and produced the two organizing insights of this post: adaptive-point sensitivity is the bottleneck, and the access boundary determines what a lower bound can claim.

References

  1. R. Bassily, A. Smith, and A. Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. FOCS 2014.
  2. R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta. Private Stochastic Convex Optimization with Optimal Rates. NeurIPS 2019.
  3. V. Feldman, T. Koren, and K. Talwar. Private Stochastic Convex Optimization: Optimal Rates in Linear Time. STOC 2020.
  4. R. Bassily, V. Feldman, C. Guzman, and K. Talwar. Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses. NeurIPS 2020.
  5. H. Asi, V. Feldman, T. Koren, and K. Talwar. Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry. ICML 2021.
  6. J. Kulkarni, Y. T. Lee, and D. Liu. Private Non-Smooth ERM and SCO in Subquadratic Steps. NeurIPS 2021.
  7. R. Bassily, C. Guzman, and M. Menart. Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings. NeurIPS 2021.
  8. L. Zhang, K. K. Thekumparampil, S. Oh, and N. He. Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization. NeurIPS 2022.
  9. Y. Carmon, A. Jambulapati, Y. Jin, Y. T. Lee, D. Liu, A. Sidford, and K. Tian. ReSQueing Parallel and Private Stochastic Convex Optimization. FOCS 2023.
  10. M. Menart and A. Nikolov. On the Gradient Complexity of Private Optimization with Private Oracles. COLT 2026.
  11. A. Gu, B. Shi, and K. Tian. Functional Stochastic Localization. COLT 2026.
  12. Y. Nesterov. Smooth Minimization of Non-Smooth Functions. Mathematical Programming, 2005.
  13. Q. Geng, W. Ding, R. Guo, and S. Kumar. Tight Analysis of Privacy and Utility Tradeoff in Approximate Differential Privacy. AISTATS 2020.
  14. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. TCC 2006.