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:
- Variational Convexity: Pham Duy Khanh et al. in Variational Convexity of Functions and Variational Sufficiency in Optimization demonstrate that a non-smooth function exhibits variational convexity if and only if its Moreau envelope is locally convex. This equivalence allows researchers to apply classical convex optimization tools directly to non-smooth, non-convex problems.
- Finite-Time Convergence: Andrew Eberhard et al. in Finite-Time Nonconvex Optimization Using Time-Varying Dynamical Systems show that Moreau envelopes preserve underlying Kurdyka–Łojasiewicz (KL) properties. This preservation allows finite-time convergence techniques designed for smooth continuous-time dynamical systems to be applied to non-smooth optimization landscapes.
- Bilevel Optimization: In bilevel problems where the follower has multiple optimal responses, the leader's hyper-objective becomes non-smooth. He Chen et al. in Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization show that identifying underlying weak convexity or concavity via set-valued mappings allows algorithms to compute strong stationary points that were previously considered unreachable.
- Variable Smoothing: To bridge the gap between fast smooth optimization and slower subgradient methods, Axel Böhm in Variable Smoothing for Weakly Convex Composite Functions maps the mathematical relationship between two Moreau envelopes with different smoothing parameters, showing how dynamically adjusting $\lambda$ controls the distance to critical points.
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:
- Non-Lipschitz Continuity: Puya Latafat et al. in Bregman Finito/MISO for Nonconvex Regularized Finite Sum Minimization without Lipschitz Gradient Continuity utilize a Bregman-Moreau envelope as a Lyapunov function to reveal a hidden smoothness in non-separable objectives, simplifying convergence proofs for coordinate descent methods.
- Stochastic Games: In multi-agent reinforcement learning, Zaiwei Chen et al. in Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games apply a generalized Moreau envelope to the Nash gap. This construction creates a smooth Lyapunov function that enables gradient-based stability analysis for non-smooth stochastic approximations.
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.