Overcoming the Convexity Constraint in Private Machine Learning

406 concepts243 papers

Mathematical privacy guarantees, such as Differential Privacy (DP) and certified machine unlearning, provide rigorous frameworks for protecting sensitive data. However, the foundational proofs for these guarantees heavily rely on a major assumption: the model's loss landscape must be convex.

While convexity makes the mathematics tractable, it creates a massive gap when applied to modern deep learning. Deep neural networks (DNNs) and graph neural networks (GNNs) operate in highly non-convex landscapes. Consequently, directly applying classical privacy frameworks to deep models either causes the mathematical guarantees to collapse or results in overly pessimistic bounds that destroy model utility.

To bridge this gap, recent research focuses on relaxing convexity constraints, leveraging alternative geometric properties, and designing algorithms that provide robust privacy guarantees within non-convex landscapes.


Why Privacy Proofs Love Convexity

To understand why non-convexity poses a challenge, we must first understand why convexity makes privacy analysis straightforward.

In a convex optimization landscape, the loss surface is a well-behaved bowl with a single global minimum. This predictability yields two crucial properties for privacy:

  1. Bounded Sensitivity: If you add or remove a single data point from the training set, the global minimum shifts only slightly. Algorithms like DP-SGD, introduced by Abadi et al., rely on this predictable sensitivity to determine exactly how much noise must be injected to obscure any individual's contribution.
  2. Optimization Contractivity: As an iterative optimizer moves down a convex bowl, successive steps naturally contract toward the same minimum, regardless of slight variations in the starting point or individual gradients. As demonstrated by Altschuler et al., this contractive property allows privacy loss to stabilize over time, meaning that running more iterations does not necessarily lead to infinite privacy leakage.

How Non-Convexity Shatters the Guarantees

When we transition to non-convex landscapes—characterized by a rugged terrain of local minima, saddle points, and valleys—these nice properties disappear.

The Explosion of Privacy Loss

Without the contractive behavior of convex functions, the optimization path becomes highly sensitive to initial conditions and individual data points. A single gradient update can push the optimizer into an entirely different valley.

Standard privacy analysis frameworks often assume worst-case scenarios, meaning that every additional training epoch is assumed to leak more information. As highlighted by Chourasia et al. and Ye et al., this lack of convexity causes traditional privacy budgets ($\epsilon$) to accumulate pessimistically, suggesting a model is unsafe when it might empirically be secure.

The Instability of Machine Unlearning

The convexity gap is even more pronounced in machine unlearning, where a model must "forget" specific training samples to honor the right to be forgotten.

Convex Landscape:
Dataset A:   \_________*_________/  (Single Global Minimum)
Dataset A-x:  \_________*'________/  (Slightly shifted minimum; easy to patch)

Non-Convex Landscape:
Dataset A:   \_*_/ \___/ \___/       (Optimizer lands in Valley 1)
Dataset A-x:  \___/ \___/ \_*_/       (Trajectory veers into Valley 3; unstable!)

In a convex setting, removing a data point $x$ shifts the global minimum by a small, calculable amount, allowing for efficient, certified updates. But in a non-convex landscape, as Zhang et al. observe, removing a single point can cause the mathematical update tools to become entirely unstable. The trajectory might veer into a completely different local minimum, making it incredibly difficult to prove that the unlearned model is statistically indistinguishable from one trained without the deleted data from scratch. This bottleneck severely limits certified unlearning in deep architectures like GNNs (Yi et al.) and language models (Wei et al.).


Strategy 1: Geometric Relaxations

Instead of forcing models to be strictly convex, one major direction seeks out weaker geometric conditions that still offer mathematical tractability.

The Polyak-Łojasiewicz (PL) Condition

The PL condition does not require a function to have a single bowl shape, but it dictates that the gradient's magnitude must grow relative to the distance from the optimal value. Essentially, it guarantees that there are no flat local minima where an optimizer can get stuck. By leveraging the PL condition, Zhang et al. and Li et al. successfully derived tighter utility and risk bounds for private optimization without relying on strict convexity.

Expected Curvature

Rather than analyzing the absolute worst-case non-convexity of a landscape, researchers have turned to average-case geometry. For instance, Yu et al. demonstrated that because private algorithms inject noise at every iteration, the optimizer effectively "smooths out" the rugged terrain. By analyzing this expected curvature, they proved that gradient perturbation algorithms can exploit the average geometry of the loss surface to achieve significantly better utility than worst-case theories predict.


Strategy 2: Algorithmic Workarounds

A parallel direction bypasses the landscape's geometry entirely by changing how the optimization process is modeled or how the final model is exposed.

Langevin Dynamics

By injecting a specific amount of Gaussian noise into gradient descent, training can be modeled as a continuous physical process known as Langevin diffusion. The advantage here is that Langevin diffusion naturally tends toward a stationary distribution over time.

Using this framework, Chien et al. developed unlearning mechanisms that provide formal privacy guarantees for non-convex problems, demonstrating that noisy trajectories can wash away the influence of deleted data points without requiring a convex landscape.

The Hidden State Threat Model

Traditional differential privacy tracks the privacy leakage of every single intermediate gradient update. If an adversary only has access to the final trained weights—a paradigm known as the hidden state model—the intermediate chaotic steps of non-convex optimization become irrelevant.

Standard DP-SGD:     [Step 1] ──> [Step 2] ──> [Step 3] ──> [Final Model]
                      (Adversary sees every step; privacy leaks continuously)

Hidden State Model:  [  Intermediate Non-Convex Chaos  ] ──> [Final Model]
                      (Adversary only sees final model; privacy stabilizes)

Using this perspective, Chien et al. proved that the privacy loss of Noisy-SGD actually converges to a constant over time, even for non-convex and non-smooth loss functions. Alternatively, Romijnders et al. showed that by using a convex approximation of specific neural network layers (such as two-layer ReLU networks), models can safely unlock these advanced hidden-state privacy amplification benefits while maintaining deep learning capabilities.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 262 papers
  2. Version 1 · 2026-10-04 · 293 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_optimization_gap_convexity_co_a8527885,
  title = {non-convex optimization gap (convexity constraint)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-optimization-gap-convexity-constraint/rdr_a8527885edbf4f1b966cf51eaacc9eaf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_non_convex_optimization_gap_convexity_co_a8527885_v2,
  title = {non-convex optimization gap (convexity constraint)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-optimization-gap-convexity-constraint/rdr_a8527885edbf4f1b966cf51eaacc9eaf/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake