Differential Privacy (DP) has become the standard for training machine learning models on sensitive data. However, most classical DP algorithms come with a significant mathematical caveat: they require the loss functions to be "smooth." In optimization, smoothness usually means the gradient doesn't change too abruptly (Lipschitz continuity of the gradient).
In the real world, many of our most useful tools are inherently non-smooth. The Hinge loss used in Support Vector Machines has a sharp "elbow." The ReLU activation in neural networks has a dead zone and a sudden kink. Quantile regression uses a "pinball loss" with a sharp corner at zero. For these functions, the gradient can jump instantly, making the model's sensitivity—and thus the required privacy noise—unmanageably high.
Researchers are now bridging this gap, developing techniques to optimize non-smooth objectives without sacrificing privacy or utility.
The Sensitivity Problem
To guarantee privacy, algorithms like DP-SGD add noise to gradients. The amount of noise depends on sensitivity: how much a single person's data can change the output. As Jiaqi Zhang and Liwei Wang note in Efficient Private ERM for Smooth Objectives, smoothness allows us to bound this sensitivity predictably.
When a function is non-smooth, a tiny change in a data point might move the model to a "kink" in the loss landscape where the gradient changes drastically. This instability forces standard DP algorithms to add massive amounts of noise to cover the worst-case scenario, often drowning out the signal entirely. As Haim Kaplan and Uri Stemmer point out in Private Learning of Halfspaces, this structural irregularity makes iterative search methods difficult to apply without compromising accuracy.
Smoothing as a Bridge
The most common way to handle non-smoothness is to "blur" the sharp edges of the function. By approximating a non-smooth function with a smooth one, we can use standard DP tools.
The Moreau Envelope vs. Convolution
Traditionally, researchers used the Moreau Envelope, a mathematical technique that creates a smooth lower bound for a function. However, this often introduces a "smoothing error" that prevents the algorithm from reaching the true optimal solution.
Recent work by Du Chen and Geoffrey A. Chua in Differentially Private Stochastic Convex Optimization under a Quantile Loss Function suggests that convolution smoothing—averaging the function over a small neighborhood—can be more effective. In their framework, C-OP (Convolution-then-Objective Perturbation), they leverage the symmetry of non-smooth norms (like the $L_1$ norm) to achieve near-optimal convergence rates that were previously thought impossible for non-smooth private learners.
Scaling to User-Level Privacy
The challenge intensifies in User-Level Differential Privacy, where the goal is to protect all data points belonging to a single user (common in federated learning). Here, the sensitivity is even higher because a single user might contribute hundreds of samples.
Raef Bassily and Ziteng Sun have shown in User-level Private Stochastic Convex Optimization with Optimal Rates that while smoothing techniques like the Moreau envelope work, they often introduce suboptimal dependencies on the number of users. To solve this, Daogao Liu and Hilal Asi introduced polynomial-time algorithms in User-level Differentially Private Stochastic Convex Optimization that achieve optimal error rates for both smooth and non-smooth functions by combining randomized smoothing with multi-pass gradient descent.
Beyond Gradient Descent
For some non-smooth problems, gradients are so unreliable that researchers are moving away from gradient-based methods entirely:
- Zeroth-Order Optimization: Liang Zhang and Sewoong Oh developed DPZero, which estimates the landscape using only function evaluations, bypassing the need for gradients in non-smooth LLM fine-tuning.
- Fixed-Point Iterations: Edwige Cyffers and Aurélien Bellet reframed optimization as a noisy fixed-point iteration, allowing for private versions of the ADMM algorithm, which is naturally suited for non-smooth constraints.
- Tree Aggregation: To reduce the "privacy tax" over many iterations, Raman Arora and Cristóbal Guzmán utilize tree-based noise aggregation in Faster Rates of Convergence to Stationary Points in Differentially Private Optimization, which helps maintain utility even when the loss landscape is highly irregular.
Why This Matters
The shift toward non-smooth private optimization is not just a theoretical exercise. It enables DP to be applied to:
- Robust Statistics: Using absolute error instead of squared error to handle heavy-tailed data, as explored by Gautam Kamath in Improved Rates for DP SCO with Heavy-Tailed Data.
- Fairness: Implementing discrete, non-smooth constraints to ensure models don't discriminate, a focus of Mohammad Yaghini and Nicolas Papernot in Private Rate-Constrained Optimization.
- Ranking and AUC: Tasks that rely on pairwise comparisons, which Zhiyu Xue and Di Wang have shown are inherently non-smooth in Differentially Private Pairwise Learning Revisited.
By mastering the "jagged" landscapes of non-smooth functions, private machine learning is moving closer to the versatility and performance of its non-private counterparts.