To understand why optimizing non-smooth functions under differential privacy (DP) is challenging, we must first understand why privacy mechanisms love smoothness.
At its core, differential privacy requires that an algorithm's output be insensitive to the addition or removal of any single individual's data point. In the context of empirical risk minimization (ERM) or stochastic convex optimization (SCO), this means we must bound the sensitivity of our optimization process.
When an objective function is smooth—meaning it is differentiable and its gradients do not change abruptly—the optimization landscape is stable and predictable. For instance, classic mechanisms like objective perturbation rely on the objective being twice-differentiable so that the Hessian can be used to precisely bound how much the optimal solution shifts when a data point changes, as shown by Kifer et al.. Similarly, output perturbation algorithms leverage smoothness to ensure that standard gradient descent converges quickly and predictably, allowing for tight privacy guarantees with minimal added noise (Zhang et al.).
The Non-Smooth Bottleneck
Modern machine learning frequently relies on functions that are explicitly not smooth. Examples include the hinge loss used in Support Vector Machines (SVMs), absolute error ($L_1$ loss) for robust regression, and $L_1$ regularization (LASSO) for inducing model sparsity.
These functions contain "kinks" or sharp corners where the gradient is discontinuous or undefined. As Rubinstein et al. and Raj et al. identified, these non-differentiable points break standard privacy frameworks. If an algorithm relies on gradients to navigate, a tiny shift in a single data point can push a parameter across a kink, causing the gradient to jump discontinuously. This sudden jump means the local sensitivity of the gradient becomes exceptionally high. To mask this worst-case change and preserve privacy, standard DP-SGD algorithms are forced to clip gradients aggressively or inject massive amounts of noise, severely degrading the model's final accuracy.
Furthermore, this instability introduces a heavy computational penalty. While smooth private optimization can often match non-private convergence rates in near-linear time, non-smooth objectives historically suffered from a "quadratic barrier" in iteration complexity, requiring far more passes over the data to stabilize the noisy optimization path (Bassily et al.).
Paradigm 1: Smoothing the Landscape
The most direct way to handle a non-smooth objective is to approximate it with a smooth one. For example, one can substitute the sharp hinge loss with a continuously differentiable alternative like the Huber loss (Redberg et al.).
However, standard smoothing techniques introduce a delicate trade-off:
- If you smooth the function too aggressively, you distort the optimization landscape, introducing a large approximation error that prevents the algorithm from finding the true minimum.
- If you smooth too conservatively, the gradient's rate of change (the Lipschitz constant of the gradient) remains extremely high, requiring a massive amount of privacy noise.
To resolve this tension, recent methods exploit the structural properties of specific non-smooth constraints. For instance, Chen et al. developed a Convolution-then-Objective Perturbation (C-OP) framework. By leveraging the geometric symmetry of the $L_1$-norm during convolution smoothing, the authors managed to balance the smoothing error and privacy noise perfectly, achieving optimal convergence rates without destroying the underlying sparsity structure.
Paradigm 2: Bypassing Gradients via Geometry and Sampling
Rather than forcing a non-smooth function to look smooth, a parallel line of research designs privacy mechanisms that are inherently indifferent to kinks.
Geometric Subgradient Analysis
Instead of relying on second-order derivatives (Hessians) to bound sensitivity, algorithms can look at the global geometry of the objective function. The K-Norm Gradient (KNG) mechanism, proposed by Awan et al., bypasses differentiability requirements entirely. KNG determines privacy noise by analyzing the geometric properties of the function's subgradients specifically around the optimum. This allows it to privatize inherently non-smooth statistical tools, such as quantile regression, while ensuring the noise vanishes asymptotically as the dataset grows.
Stability through Log-Concave Sampling
Another elegant solution replaces deterministic gradient steps with probabilistic sampling. Drawing from Bayesian privacy principles, Wang et al. demonstrated that drawing a single sample from a posterior distribution via Stochastic Gradient Langevin Dynamics inherently satisfies differential privacy. Because the exponential distribution shifts smoothly even when the underlying loss function has sharp corners, privacy is achieved "for free" without requiring twice-differentiable or strongly convex losses.
Expanding on this intuition, Agarwal et al. developed the POMER algorithm for online convex optimization. By sampling from strongly log-concave distributions, the algorithm achieves optimal regret bounds for non-smooth functions. The randomness of the sampling distribution acts as a natural privacy buffer, completely removing the traditional requirement for Lipschitz gradients.
Achieving Subquadratic Efficiency and Optimal Rates
Ultimately, the goal of this research direction is to make non-smooth private optimization just as computationally efficient as smooth optimization.
To break the historical computational bottlenecks, Kulkarni et al. introduced algorithms capable of solving non-smooth ERM and SCO in subquadratic steps, drastically reducing the number of iterations needed to achieve high utility.
Smooth Private Optimization:
[Stable Gradients] ──> [Low Sensitivity] ──> [Minimal Noise] ──> [Linear Time]
Traditional Non-Smooth Private Optimization:
[Sharp Kinks] ──> [High Sensitivity] ──> [Massive Noise] ──> [Quadratic Time]
Modern Non-Smooth Private Optimization (Sampling/Localization):
[Sharp Kinks] ──> [Log-Concave Sampling / Localization] ──> [Optimal Noise] ──> [Subquadratic Time]
When dealing with high-dimensional data where the choice of geometry dictates performance, Asi et al. developed an iterative localization approach. This method achieves optimal privacy rates specifically within $\ell_1$ geometry for non-smooth objectives, making high-dimensional sparse regression practically viable under privacy constraints. Finally, these algorithmic advances have successfully extended to complex data-collection models; Liu et al. proved that polynomial-time algorithms can achieve optimal convergence rates for both smooth and non-smooth functions even under the stringent constraints of user-level differential privacy.
Key Foundational Work
Large Margin Multiclass Gaussian Classification with Differential Privacy (2010) — contributed 1 concept elements to this direction.
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2012) — contributed 1 concept elements to this direction.
Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression (2012) — contributed 1 concept elements to this direction.