Differentially Private Optimization for Non-Smooth Objectives

This direction is split into other directions: non-smooth private optimization. Its last version stays readable and citable here.

Version 1 of 1120 papers143 conceptsfrozen 2026-10-04

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:

Why This Matters

The shift toward non-smooth private optimization is not just a theoretical exercise. It enables DP to be applied to:

  1. 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.
  2. 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.
  3. 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.

Papers in this version

Showing 60 of 120 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_differentially_private_optimization_for__55c3a0fb,
  title = {Differentially Private Optimization for Non-Smooth Objectives},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/differentially-private-optimization-for-non-smooth-objectives/rdr_55c3a0fb5b3e4b1ba0611392cf89fb4b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_differentially_private_optimization_for__55c3a0fb_v1,
  title = {Differentially Private Optimization for Non-Smooth Objectives},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/differentially-private-optimization-for-non-smooth-objectives/rdr_55c3a0fb5b3e4b1ba0611392cf89fb4b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}