Inexact Proximal Point Algorithms for Zeroth-Order Global Optimization

Minxin Zhang, Fuqun Han, Yat Tin Chow, Stanley Osher, Hayden SchaefferarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces a new theoretical and practical framework for zeroth-order global optimization using Inexact Proximal Point (IPP) algorithms. By approximating the proximal operator through Gibbs measures and leveraging Tensor Train (TT) decompositions, the authors provide a way to find global minima in high-dimensional, nonconvex landscapes with provable convergence guarantees and significantly better scaling than traditional derivative-free methods.

What Problem Does This Paper Address?

Global optimization is the "holy grail" of many fields, from machine learning to computational biology. However, most real-world functions are nonconvex, meaning they are littered with local minima that trap standard algorithms like gradient descent. Furthermore, in many "black-box" scenarios, we don't have access to gradients (zeroth-order optimization), making the search even harder.

Existing global optimization methods often fall into two traps:

  1. Heuristics: Methods like Genetic Algorithms or Particle Swarm Optimization work well in practice but often lack rigorous convergence guarantees to the global minimum.
  2. The Curse of Dimensionality: Methods that explore the space systematically often see their computational cost explode exponentially as the number of dimensions increases.

The authors aim to bridge this gap by creating an algorithm that is both theoretically sound (it actually converges to the global minimum) and computationally efficient in high dimensions.

Methods

The paper builds on the Proximal Point Method, an iterative approach that simplifies a difficult optimization problem into a series of "proximal" steps. Usually, these steps require solving another optimization problem exactly, which is impractical for nonconvex functions.

The authors' "secret sauce" involves three key components:

  • Gibbs Measures: They transform the optimization problem into an integration problem. Instead of searching for the minimum of a function $\phi$, they calculate the expected value of a random variable under a Gibbs distribution $\exp(-\phi/\delta)$. As the temperature parameter $\delta$ goes to zero, this expectation concentrates precisely on the global minimizer.
  • Tensor Train (TT) Approximation: To avoid the exponential cost of high-dimensional integration, they use the TT-cross algorithm. This technique approximates a high-dimensional tensor (a multi-dimensional grid of function values) using only a small, linear number of function evaluations. This effectively bypasses the curse of dimensionality for functions with low-rank structures.
  • Adaptive IPP Framework: They propose two algorithms:
  • TT-IPP: Uses Tensor Trains for deterministic, high-accuracy estimation of the proximal operator.
  • MC-IPP: Uses Monte Carlo integration with variance reduction (EWMA) for a simpler, stochastic approach.

Datasets

The authors evaluated their algorithms on several fronts:

  • Standard Benchmarks: A suite of classic "difficult" functions including Ackley, Rastrigin, Griewank, and Schaffer, tested in dimensions ranging from $d=4$ to $d=100$.
  • DNA Chain Configuration: A 50-dimensional black-box problem identifying the global minimum energy state of a DNA chain.
  • Portfolio Optimization: A 10-dimensional nonconvex financial risk-parity problem.
  • Hamilton-Jacobi Equations: Using the algorithm to solve complex partial differential equations (PDEs) via the Hopf-Lax formula.

Key Insights and Ideas

  • Optimization as Integration: The most profound insight is the formal link between the proximal operator and the expectation under a Gibbs measure. This allows the authors to use tools from integration (like Monte Carlo and Tensor Trains) to solve optimization problems.
  • The Power of Regularization: The quadratic term in the proximal operator doesn't just help with convergence; it actually "smooths" the Gibbs landscape, making it more concentrated and easier to sample or approximate.
  • Linear Scaling: By using TT-cross, the number of function evaluations required by TT-IPP grows nearly linearly with the dimension $d$, whereas most global solvers grow exponentially.
  • Provable Global Convergence: Unlike many zeroth-order methods, the authors provide a rigorous proof that their inexact iterations still converge to the global minimum, provided the approximation error vanishes over time.

Key Results

  • Efficiency: In high-dimensional tests ($d=100$), TT-IPP achieved target accuracy with orders of magnitude fewer function evaluations than standard competitors like Differential Evolution (DE) or Simulated Annealing (SA).
  • Accuracy: On the 50-dimensional DNA problem, TT-IPP reached an error of $10^{-15}$, while most other methods (CBO, PSO, SA) remained trapped in local minima with errors greater than $1.0$.
  • Robustness: MC-IPP proved to be a strong candidate for resource-constrained scenarios, consistently outperforming other stochastic solvers on $R^{10}$ and $R^{20}$ benchmarks when function evaluations were limited.

Limitations and Future Work

  • Bounded Domains: The TT-IPP algorithm currently requires a predefined, bounded search domain to construct its mesh grid. Extending this to unbounded domains remains a challenge.
  • Initial Setup Cost: Constructing the initial Tensor Train approximation has a non-trivial "up-front" cost in terms of function evaluations, though this pays off in later iterations.
  • Rank Sensitivity: The efficiency of the TT approach depends on the function having a "low-rank" structure. While many physical and engineering problems satisfy this, highly chaotic or truly random functions might struggle.
  • Future Directions: The authors suggest integrating machine learning models to "learn" the proximal operator and exploring more advanced rejection sampling techniques to further improve MC-IPP.

Summary updated

Abstract

This work concerns the zeroth-order global minimization of continuous nonconvex functions with a unique global minimizer and possibly multiple local minimizers. We formulate a theoretical framework for inexact proximal point (IPP) methods for global optimization, establishing convergence guarantees under mild assumptions when either deterministic or stochastic estimates of proximal operators are used. The quadratic regularization in the proximal operator and the scaling effect of a parameter $δ>0$ create a concentrated landscape of an associated Gibbs measure that is practically effective for sampling. The convergence of the expectation under the Gibbs measure as $δ\to 0^+$ is established, and the convergence rate of $\mathcal O(δ)$ is derived under additional assumptions. These results provide a theoretical foundation for evaluating proximal operators inexactly using sampling-based methods such as Monte Carlo (MC) integration. In addition, we propose a new approach based on tensor train (TT) approximation. This approach employs a randomized TT cross algorithm to efficiently construct a low-rank TT approximation of a discretized function using a small number of function evaluations, and we provide an error analysis for the TT-based estimation. We then propose two practical IPP algorithms, TT-IPP and MC-IPP. The TT-IPP algorithm leverages TT estimates of the proximal operators, while the MC-IPP algorithm employs MC integration to estimate the proximal operators. Both algorithms are designed to adaptively balance efficiency and accuracy in inexact evaluations of proximal operators. The effectiveness of the two algorithms is demonstrated through experiments on diverse benchmark functions and various applications.
BibTeX
@misc{zhang2024inexact,
  author = {Minxin Zhang and Fuqun Han and Yat Tin Chow and Stanley Osher and Hayden Schaeffer},
  title = {{Inexact Proximal Point Algorithms for Zeroth-Order Global Optimization}},
  year = {2024},
  eprint = {2412.11485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.11485},
}
Figure