Moreau Envelopes for Non-Smooth Non-Convex Optimization

31 concepts30 papers1 proposal

In smooth optimization, tracking algorithmic progress is straightforward: we follow the gradient, and when its norm $\|\nabla f(x)\|$ drops below a threshold $\epsilon$, we know we are close to a stationary point. However, modern machine learning increasingly relies on objectives that are both non-smooth and non-convex—such as neural networks with ReLU activations, adversarial training losses, and distributionally robust objectives.

In these non-smooth landscapes, standard gradients do not exist everywhere, and subgradients fail as a metric for convergence. Consider the simple non-smooth function $f(x) = |x|$. At the minimum ($x=0$), the subgradient is the entire interval $[-1, 1]$. Yet, for any $x > 0$, no matter how close to zero, the subgradient is exactly $\{1\}$. Because the subgradient norm does not shrink as we approach the minimum, it cannot serve as a reliable indicator of proximity to an optimal point.

To evaluate convergence and design stable algorithms in these jagged landscapes, researchers use a mathematical smoothing mechanism known as the Moreau envelope.

The Intuition of the Moreau Envelope

The Moreau envelope $M_\lambda f$ of a function $f$ is an infimal convolution that constructs a smooth, lower approximation of the original objective. Mathematically, it is defined as:

$$M_\lambda f(x) = \inf_{y} \left\{ f(y) + \frac{1}{2\lambda} \|x - y\|^2 \right\}$$

Intuitively, the Moreau envelope can be thought of as a regularized minimization problem. For a given point $x$, it balances two competing goals: finding a point $y$ where the original function $f(y)$ is small, and ensuring that $y$ does not stray too far from $x$. The parameter $\lambda > 0$ controls this trade-off, acting as a smoothing parameter.

The unique minimizer $y$ that solves this optimization problem is known as the proximal operator, denoted as $\text{prox}_{\lambda f}(x)$. As Mikael Johansson et al. note in Anderson Acceleration of Proximal Gradient Methods, this construction provides a continuously differentiable surrogate function. It allows researchers to define and track stationarity in settings where the underlying objective function lacks well-defined or continuous gradients.

Why the Envelope's Gradient Measures Stationarity

The core reason the Moreau envelope works so well as an analytical tool lies in a remarkable property of its gradient:

$$\nabla M_\lambda f(x) = \frac{1}{\lambda} \left( x - \text{prox}_{\lambda f}(x) \right)$$

Even if $f$ is highly non-smooth and jagged, $M_\lambda f$ is continuously differentiable. More importantly, the norm of this gradient, $\|\nabla M_\lambda f(x)\|$, serves as a mathematically rigorous proxy for stationarity.

To see why, suppose that an algorithm reaches a point $x$ where the gradient of the Moreau envelope is small, meaning $\|\nabla M_\lambda f(x)\| \le \epsilon$. By definition, this implies that the distance between $x$ and its proximal point $\hat{x} = \text{prox}_{\lambda f}(x)$ is at most $\lambda \epsilon$. From the optimality conditions of the proximal step, it also guarantees that there exists a subgradient $g \in \partial f(\hat{x})$ such that $\|g\| \le \epsilon$.

Therefore, a small envelope gradient provides a dual guarantee: the current point $x$ is physically close to a proximal point $\hat{x}$, and that proximal point is nearly stationary under the original non-smooth function.

This mechanism is widely used to prove the convergence of optimization algorithms. For example, Ahmet Alacaoglu et al. in Convergence of adaptive algorithms for constrained weakly convex optimization rely on the gradient of the Moreau envelope to establish the first near-optimal convergence rates for adaptive algorithms like AMSGrad on non-smooth, constrained landscapes. Similarly, Francesco Rinaldi in A zeroth order method for stochastic weakly convex optimization leverages this gradient norm to provide formal convergence guarantees for derivative-free (zeroth-order) stochastic methods.

Unlocking Weakly Convex and Structural Properties

The Moreau envelope is particularly powerful when applied to weakly convex functions. A function $f$ is $\rho$-weakly convex if the function $x \mapsto f(x) + \frac{\rho}{2}\|x\|^2$ is convex. This class of functions is broad enough to encompass many non-convex objectives used in deep learning, such as compositions of smooth functions with convex regularizers or Lipschitz continuous functions.

If we choose the smoothing parameter $\lambda < 1/\rho$, the Moreau envelope is guaranteed to be fully smooth with a Lipschitz continuous gradient, effectively eliminating the analytical challenges of non-convexity and non-smoothness simultaneously.

The envelope also preserves and reveals deep structural properties of the underlying function:

Taming Minimax and Compositional Landscapes

Beyond standard minimization, modern machine learning frequently involves minimax optimization (such as Generative Adversarial Networks and adversarial training) and multi-level compositional objectives. These problems are notoriously unstable when the objectives are non-smooth.

In the nonconvex-concave minimax setting, the Moreau envelope serves as a stable surrogate to locate stationary points. Tianyi Lin et al. in On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems and Kiran Koshy Thekumparampil et al. in Efficient Algorithms for Smooth Minimax Optimization use the envelope to define stationarity metrics and accelerate convergence rates. This framework also enables researchers to analyze how well these models perform on unseen data; for instance, Siqi Zhang et al. in Uniform Convergence and Generalization for Nonconvex Stochastic Minimax Problems employ the envelope to derive generalization bounds for stochastic minimax optimization.

When game-theoretic objectives are entirely non-smooth, alternative formulations like variational inequalities are often required. Zeinab Alizadeh et al. in Distributionally Robust Nash Equilibria via Variational Inequalities utilize the Minty Variational Inequality formulation to provide a well-posed gap function, enabling the measurement of convergence toward distributionally robust Nash equilibria without relying on unique gradients.

The envelope's smoothing properties also extend to complex compositional and distributed settings. Quanqi Hu et al. in Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization use the Moreau envelope to rigorously define stationarity for coupled compositional functions, while Shixiang Chen et al. in On Distributed Nonconvex Optimization: Projected Subgradient Method for Weakly Convex Problems in Networks employ it to establish global convergence guarantees for distributed subgradient methods across networks.

Envelopes as Lyapunov Functions for Stability and Robustness

In addition to serving as a passive metric for stationarity, the Moreau envelope can actively guide optimization as a Lyapunov function—a scalar function used to prove the stability of a dynamical system or algorithm. Because the envelope smooths out the jagged edges of the objective while preserving its underlying minimizers, tracking the value of the envelope across iterations allows researchers to prove that an algorithm is steadily making progress.

This approach is highly effective for simplifying stability proofs in non-Euclidean or multi-agent settings:

Enhancing Generalization and Robustness

Replacing a jagged loss landscape with its Moreau envelope also directly improves algorithmic robustness and generalization in practical training loops. Adversarial training often suffers from "robust overfitting," where a model's defense against attacks improves on training data but collapses on test data. To resolve this, Jiancong Xiao in Uniformly Stable Algorithms for Adversarial Training and Beyond introduces an algorithm that optimizes the Moreau envelope of the adversarial loss, proving that this smoothing provides uniform stability and eliminates robust overfitting.

The framework is equally valuable for handling data corruption and complex risk measures. When optimizing in the presence of adversarial data corruption, Shyao Li et al. in Outlier-robust nonsmooth stochastic optimization use an inner-loop solver to approximate the Moreau envelope, using its gradient to safely guide the optimization process away from outliers.

Finally, the envelope allows researchers to maintain theoretical guarantees when optimizing complex risk measures or operating under severe noise. Rufeng Xiao et al. in A Unified Framework for Rank-based Loss Minimization show that envelope smoothing maintains convergence when minimizing non-convex rank-based losses. Similarly, Landi Zhu et al. in Mean-semideviation-based distributionally robust learning with weakly convex losses: convergence rates and finite-sample guarantees use the envelope's gradient norm to evaluate convergence under mean-semideviation risk measures, while Tianxi Zhu et al. in Stochastic Gradient Methods under Heavy-Tailed Noises in Weakly Convex Optimization use it to guarantee robust convergence even when the optimization process is subjected to heavy-tailed noise with infinite variance.

Key Foundational Work

Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization (2020) — contributed 1 concept elements to this direction.
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2020) — contributed 1 concept elements to this direction.
Efficient Algorithms for Smooth Minimax Optimization (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_moreau_envelope_smoothing_proximal_smoot_6d605edb,
  title = {Moreau envelope smoothing (proximal smoothing)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/moreau-envelope-smoothing-proximal-smoothing/rdr_6d605edb23a246d8b1b21be57553cbab},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_moreau_envelope_smoothing_proximal_smoot_6d605edb_v1,
  title = {Moreau envelope smoothing (proximal smoothing)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/moreau-envelope-smoothing-proximal-smoothing/rdr_6d605edb23a246d8b1b21be57553cbab/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake