A Hamilton-Jacobi-based Proximal Operator
arXiv:2211.12997 · doi:10.1073/pnas.2220469120
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.
References in corpus (5)
- Derivative-free optimization methods
- Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling
- A One-bit, Comparison-Based Gradient Estimator
- A Hamilton-Jacobi-based Proximal Operator
- A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization