Enabling Long-range Exploration in Minimization of Multimodal Functions

Jiaxin Zhang, Hoang Tran, Dan Lu, Guannan ZhangOSTI 2023 · OpenAlex

Abstract

We consider the problem of minimizing multi-modal loss functions with a large number of local optima. Since the local gradient points to the direction of the steepest slope in an infinitesimal neighborhood, an optimizer guided by the local gradient is often trapped in a local minimum. To address this issue, we develop a novel nonlocal gradient to skip small local minima by capturing major structures of the loss’s landscape in black-box optimization. The nonlocal gradient is defined by a directional Gaussian smoothing (DGS) approach. The key idea of DGS is to conduct 1D long-range exploration with a large smoothing radius along $d$ orthogonal directions in $\mathbb{R}^d$, each of which defines a nonlocal directional derivative as a 1D integral. Such long-range exploration enables the nonlocal gradient to skip small local minima. The $d$ directional derivatives are then assembled to form the nonlocal gradient. We use the Gauss-Hermite quadrature rule to approximate the $d$ 1D integrals to obtain an accurate estimator. The superior performance of our method is demonstrated in three sets of examples, including benchmark functions for global optimization, and two real-world scientific problems.

Introduction

In many scientific and engineering fields—ranging from hyperparameter tuning in neural networks to structural topology optimization—the primary goal is to identify the global minimum of a complex loss function. However, these functions are frequently "multimodal," characterized by a landscape littered with thousands of local minima.

Standard optimization techniques rely on the local gradient, which identifies the steepest descent within an infinitesimal neighborhood. This "myopic" view often leads optimizers to become trapped in the first local dip they encounter. In "black-box" optimization scenarios, where the functional form is unknown and only point-wise queries are possible, this challenge is amplified. While traditional Gaussian Smoothing (GS) attempts to blur these landscapes to hide local traps, it often fails in high-dimensional spaces due to the noise inherent in standard Monte Carlo sampling.

Methodology: Directional Gaussian Smoothing (DGS)

To overcome the limitations of local search, we introduce Directional Gaussian Smoothing (DGS). This method constructs a "nonlocal gradient" that captures the broad structural trends of a landscape while ignoring high-frequency local noise.

Conceptual comparison of local vs. DGS gradients on a multimodal landscape. The DGS gradient (red) points toward the global structure, whereas the local gradient (blue) is diverted by local minima.

The DGS framework relies on three core innovations:

  1. 1D Long-range Exploration: Instead of smoothing the entire $d$-dimensional space simultaneously, DGS performs 1D explorations along $d$ orthogonal directions. This allows for a significantly larger smoothing radius ($\sigma$), enabling the optimizer to "see" past local bumps and focus on the underlying global structure.
  2. Gauss-Hermite (GH) Quadrature: By reducing the problem to a series of 1D integrals, we can utilize GH quadrature—a highly efficient numerical integration technique. Unlike Monte Carlo sampling, which converges slowly and introduces significant noise, GH quadrature provides an exponentially more accurate estimate of the nonlocal directional derivatives.
  3. Coordinate Rotation and Jitter: To prevent the optimizer from developing "blind spots" relative to the fixed coordinate axes, the system periodically rotates the orthogonal basis and jitters the smoothing radius, ensuring robust exploration.

Experimental Evaluation

We evaluated DGS against state-of-the-art black-box optimizers, including CMA-ES, Evolution Strategies (ES-Bpop), and TuRBO, across several challenging domains:

  • High-Dimensional Benchmarks: Six classic functions (Ellipsoidal, Sharp Ridge, Ackley, Rastrigin, Schaffer’s F7, and Schwefel) were tested in up to 8000 dimensions.
  • Engineering Design: A topology optimization task involving the design of a 2D bridge with 2400 design variables.
  • Scientific Inference: A groundwater modeling problem using neural networks to map hydraulic conductivity.
Performance comparison of DGS against state-of-the-art black-box optimizers across six 2000D benchmark functions. DGS (thick red line) consistently achieves lower loss and faster convergence.

Key Results and Insights

Our experiments revealed that DGS consistently outperforms existing methods in high-dimensional, multimodal environments. On functions like Ackley and Rastrigin, DGS successfully located the global minimum while nearly all baselines remained trapped in local optima.

Furthermore, DGS demonstrated remarkable scalability, maintaining high performance as dimensionality increased from 2000D to 8000D. In practical applications, such as bridge design, DGS produced clear, hierarchical structures that matched theoretical ideals, whereas baselines often resulted in structurally unsound or "blurry" configurations. The accuracy of the DGS search direction—measured by the cosine distance to the true global optimum—was significantly higher than that of competing methods.

Limitations and Future Work

While DGS is highly effective, it requires $M \times d$ function evaluations per iteration (where $M$ is the number of quadrature points), which may be prohibitive under extremely tight evaluation budgets. Additionally, the method is less effective on functions like the Schwefel function, which lack a dominant global structure for smoothing to exploit. Future research will focus on making the smoothing radius and learning rates adaptive to the local landscape and integrating dimension-reduction techniques like "active subspaces" to further enhance efficiency.

Summary updated

Abstract

We consider the problem of minimizing multi-modal loss functions with a large number of local optima. Since the local gradient points to the direction of the steepest slope in an infinitesimal neighborhood, an optimizer guided by the local gradient is often trapped in a local minimum. To address this issue, we develop a novel nonlocal gradient to skip small local minima by capturing major structures of the loss’s landscape in black-box optimization. The nonlocal gradient is defined by a directional Gaussian smoothing (DGS) approach. The key idea of DGS is to conducts 1D long-range exploration with a large smoothing radius along d orthogonal directions in Rd, each of which defines a nonlocal directional derivative as a 1D integral. Such long-range exploration enables the nonlocal gradient to skip small local minima. The d directional derivatives are then assembled to form the nonlocal gradient. We use the Gauss-Hermite quadrature rule to approximate the d 1D integrals to obtain an accurate estimator. The superior performance of our method is demonstrated in three sets of examples, including benchmark functions for global optimization, and two real-world scientific problems.
BibTeX
@inproceedings{zhang2023enabling,
  author = {Jiaxin Zhang and Hoang Tran and Dan Lu and Guannan Zhang},
  title = {{Enabling Long-range Exploration in Minimization of Multimodal Functions}},
  booktitle = {OSTI},
  year = {2023},
}

Loading related content...

Figure