A Hamilton–Jacobi-based proximal operator

Stanley Osher, Howard Heaton, Samy Wu Fung

In the world of first-order optimization, two tools reign supreme: gradients and proximal operators. While we have become incredibly good at calculating gradients (thanks to automatic differentiation), proximal operators remain a bottleneck. Unless your function has a well-known "closed-form" proximal formula (like the $\ell_1$ norm), you usually have to solve a nested optimization sub-problem, which is computationally expensive and often impractical.

A new paper by Stanley Osher, Howard Heaton, and Samy Wu Fung introduces HJ-Prox, a clever algorithm that uses the physics of partial differential equations (PDEs) to estimate these elusive proximal operators using nothing but blackbox function samples.

TL;DR

HJ-Prox is a novel algorithm that approximates proximal operators by leveraging a deep mathematical connection between Moreau envelopes and Hamilton-Jacobi equations. By applying the Cole-Hopf transformation and importance sampling, it enables "zeroth-order" optimization—solving complex problems using only noisy function evaluations without needing explicit gradients or analytical proximal formulas.

What Problem Does This Paper Address?

Many modern optimization algorithms (like ADMM or ISTA) rely on the proximal operator, defined as: $$\text{prox}_{tf}(x) = \text{argmin}_{z} \left( f(z) + \frac{1}{2t} \|z - x\|^2 \right)$$ This operator is essentially a "step" that balances minimizing the function $f$ with staying close to the current point $x$.

The problem? For most functions $f$, there is no simple formula for this "argmin." Furthermore, in many real-world scenarios, we don't even have a formula for $f$ itself—we only have a "blackbox" oracle that gives us a (potentially noisy) value of $f(x)$ when prompted. Standard techniques fail when the objective is non-differentiable, non-convex, or hidden behind a noisy interface.

Methods

The authors' approach is a beautiful bit of mathematical "connect-the-dots":

  1. The Moreau Envelope: They start with the Moreau envelope $u(x, t)$, a smoothed version of $f$. A known result in variational analysis is that the proximal operator is simply a function of the gradient of this envelope: $\text{prox}_{tf}(x) = x - t\nabla u(x, t)$.
  2. The Hamilton-Jacobi (HJ) Connection: The envelope $u$ is actually the solution to a specific Hamilton-Jacobi equation.
  3. Viscosity & Cole-Hopf: By adding "artificial viscosity" ($\delta$) to the HJ equation, they transform it into a linear heat equation via the Cole-Hopf transformation.
  4. Importance Sampling: The solution to the heat equation can be expressed as a convolution, which is mathematically equivalent to an expectation over a Gaussian distribution.

The Resulting Formula: Instead of solving a minimization problem, HJ-Prox estimates the proximal as a weighted average of samples: $$\text{prox}_{tf}(x) \approx \frac{\mathbb{E}_{y \sim \mathcal{N}(x, \delta t)} [y \cdot \exp(-f(y)/\delta)]}{\mathbb{E}_{y \sim \mathcal{N}(x, \delta t)} [\exp(-f(y)/\delta)]}$$ This allows them to compute the proximal using only function evaluations ($f(y)$), making it a zeroth-order method.

Datasets

The paper evaluates the algorithm on several synthetic but representative benchmarks:

  • Standard Proximals: Functions with known solutions like the $\ell_1$ norm (absolute value), quadratics, and log-barriers.
  • Non-convex Functions: Negative absolute value and negative quadratic functions.
  • The Lasso Problem: A high-dimensional sparse recovery task ($A \in \mathbb{R}^{500 \times 1000}$).
  • Noisy Oracles: A scenario where the objective function is $\ell_1$ norm corrupted by 0.5% Gaussian noise.

Key Insights and Ideas

  • Physics as a Solver: The core "aha moment" is realizing that the diffusion process (the heat equation) naturally "finds" the proximal operator. The viscosity parameter $\delta$ acts as a tunable smoothing factor.
  • Smoothing as a Feature, Not a Bug: Because the algorithm is based on a viscous PDE, it inherently acts as a denoiser. This makes it remarkably robust to noisy objective functions where traditional gradient-based methods would chatter or diverge.
  • Beating the Curse of Dimensionality: PDE solvers usually require a grid, which is impossible in high dimensions. By using importance sampling (Monte Carlo), the authors make the computation feasible in dimensions as high as 1,000.
  • Zeroth-Order Versatility: The algorithm doesn't care if $f$ is differentiable. It only needs to be able to sample $f(y)$.

Key Results

  • High Fidelity: For functions with known proximals, HJ-Prox estimates match the analytical "ground truth" with high accuracy (Fig 2).
  • Robustness to Noise: In experiments with noisy function samples, HJ-Prox successfully recovered smooth Moreau envelopes and accurate proximals where other methods would fail (Fig 4).
  • Optimization Success: The authors implemented "HJ-ISTA" (replacing the standard soft-thresholding with HJ-Prox). It converged to the same solution as the standard Lasso solver, proving it can be dropped into existing optimization frameworks.
  • Efficiency: In high-dimensional constrained problems with noisy oracles, HJ-Prox converged to the optimal solution using as few as 0.1 to 10 oracle calls per dimension per iteration.

Limitations and Future Work

  • Sample Complexity: While importance sampling helps, the algorithm still requires a significant number of samples ($N$) to achieve high precision, especially as the viscosity $\delta$ approaches zero.
  • Numerical Stability: The $\exp(-f(y)/\delta)$ term can easily lead to numerical underflow or overflow. While the authors proposed a rescaling heuristic (Algorithm 1), this remains a delicate balance.
  • Theoretical Bounds: The current convergence proofs primarily cover $\rho$-weakly convex functions. Extending this to broader classes of non-convex functions is a logical next step.
  • Adaptive Sampling: Future work could explore more sophisticated sampling strategies (beyond simple Gaussians) to further reduce the number of function evaluations needed.

Summary updated

Abstract

First-order optimization algorithms are widely used today. Two standard building blocks in these algorithms are proximal operators (proximals) and gradients. Although gradients can be computed for a wide array of functions, explicit proximal formulas are known for only limited classes of functions. We provide an algorithm, HJ-Prox, for accurately approximating such proximals. This is derived from a collection of relations between proximals, Moreau envelopes, Hamilton-Jacobi (HJ) equations, heat equations, and Monte Carlo sampling. In particular, HJ-Prox smoothly approximates the Moreau envelope and its gradient. The smoothness can be adjusted to act as a denoiser. Our approach applies even when functions are accessible only by (possibly noisy) black box samples. We show that HJ-Prox is effective numerically via several examples.
BibTeX
@inproceedings{osher2023hamiltonjacobi,
  author = {Stanley Osher and Howard Heaton and Samy Wu Fung},
  title = {{A Hamilton–Jacobi-based proximal operator}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2023},
  doi = {10.1073/pnas.2220469120},
}

Loading related content...

Figure