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 only known for 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 only accessible by (possibly noisy) blackbox samples. We show HJ-Prox is effective numerically via several examples.
Introduction
In the landscape of first-order optimization, gradients and proximal operators are essential tools. While automatic differentiation has simplified gradient computation, proximal operators remain a significant computational bottleneck. Unless a function possesses a well-known closed-form proximal formula, such as the $\ell_1$ norm, practitioners must typically solve a nested optimization sub-problem. This process is computationally expensive and often impractical for complex objectives.
The HJ-Prox algorithm, introduced by Osher, Heaton, and Fung, addresses this by utilizing the physics of partial differential equations (PDEs) to estimate proximal operators from blackbox function samples. This approach is particularly valuable when the objective function is non-differentiable, non-convex, or corrupted by noise.
The HJ-Prox Algorithm
The core innovation of HJ-Prox is the exploitation of the mathematical relationship between proximal operators and the Moreau envelope. The proximal operator of a function $f$ is defined as: $$\text{prox}_{tf}(x) = \text{argmin}_{z} \left( f(z) + \frac{1}{2t} \|z - x\|^2 \right)$$ The Moreau envelope $u(x, t)$ is a smoothed version of $f$, and the proximal operator can be expressed as a function of its gradient: $\text{prox}_{tf}(x) = x - t\nabla u(x, t)$.
HJ-Prox identifies $u$ as the solution to a specific Hamilton-Jacobi equation. By introducing an "artificial viscosity" parameter $\delta$, the equation is transformed into a linear heat equation via the Cole-Hopf transformation. The solution is then formulated as an expectation over a Gaussian distribution, enabling estimation via importance sampling: $$\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 "zeroth-order" method requires only function evaluations, bypassing the need for explicit gradients or analytical formulas.
Experimental Evaluation
The algorithm was tested on several benchmarks, including standard proximals, non-convex functions, and high-dimensional Lasso problems. HJ-Prox demonstrated high fidelity, with estimates closely matching analytical ground truths.
A significant advantage of HJ-Prox is its inherent robustness to noise. The viscosity parameter $\delta$ acts as a tunable smoothing factor, allowing the algorithm to function as a denoiser. In scenarios with noisy function samples, HJ-Prox successfully recovered smooth envelopes where traditional methods might fail.
Furthermore, the use of importance sampling allows the method to overcome the curse of dimensionality typically associated with PDE solvers. Experiments showed that HJ-Prox could effectively solve problems in dimensions as high as 1,000, maintaining accuracy as the number of samples increased. In optimization tasks, the authors demonstrated that replacing standard proximal operators with HJ-Prox (forming "HJ-ISTA") led to convergence to the optimal solution.
Discussion
HJ-Prox offers a versatile framework for optimization, especially in noisy or blackbox settings. However, it is not without limitations. Achieving high precision requires a substantial number of samples, particularly as the viscosity $\delta$ decreases. Additionally, the exponential terms in the sampling formula require careful numerical handling to avoid overflow or underflow. Future work may explore adaptive sampling strategies and broader theoretical convergence guarantees for non-convex functions.
Summary updated