Black-box Optimizer with Implicit Natural Gradient

Yueming Lyu, Ivor TsangECML-PKDD 2021 · OpenReview

TL;DR

This paper introduces INGO, a novel black-box optimization framework that uses an implicit natural gradient to efficiently update parameters. INGO offers a simpler, more robust, and often more precise alternative to existing methods like CMA-ES, particularly for challenging, ill-conditioned problems.

What Problem Does This Paper Address?

Black-box optimization is crucial for many real-world applications like reinforcement learning and robotics, where the objective function is complex and its gradients are unavailable. Existing methods, such as CMA-ES, can be complex and struggle with high-dimensional or ill-conditioned problems. While natural gradient methods offer theoretical advantages by considering the geometry of the parameter space, directly computing them is often intractable for black-box scenarios. This paper aims to bridge this gap by proposing a novel framework that leverages an implicit natural gradient, making it practical for black-box optimization.

Methods

The core of this work is the Implicit Natural Gradient Optimization (INGO) framework. Instead of directly computing the natural gradient, which requires the inverse of the Fisher Information Matrix (FIM), INGO uses an implicit approach. This is achieved by reformulating the optimization problem in terms of natural parameters of an exponential-family distribution and then deriving an update rule that avoids explicit FIM inversion.

Key aspects of their method include:

  • Exponential-Family Sampling: The black-box optimization problem is relaxed into an expectation over an exponential-family distribution.
  • Implicit Natural Gradient: The update rule is derived such that it implicitly follows the natural gradient direction, leveraging second-order information without explicit FIM computation.
  • Gaussian Sampling: For continuous optimization, they specialize the framework for Gaussian distributions, deriving update rules for the mean ($\mu$) and covariance matrix ($\Sigma$). Notably, they update the inverse of the covariance matrix for improved stability.
  • Stochastic Updates: To handle the lack of direct gradient access, they use Monte Carlo sampling to estimate gradients, making the method suitable for black-box functions.
  • Normalization Trick: To improve stability, they employ a monotonic transformation of function values before updating, which helps mitigate issues with variance.

Datasets

The paper evaluates their methods on several synthetic benchmark test problems, including:

  • Ellipsoid
  • $l_1$-Ellipsoid
  • $l_2$-Ellipsoid
  • Discus
  • Levy
  • Rastrigin10

For reinforcement learning evaluation, they use standard MuJoCo environments:

  • Swimmer
  • HalfCheetah
  • InvertedDoublePendulum
  • HumanoidStandup

Key Insights and Ideas

  • Implicit Natural Gradient is Key: The core innovation is the implicit natural gradient, which allows for the benefits of natural gradient descent (second-order information, geometric understanding) without the computational burden of FIM inversion, making it practical for black-box optimization.
  • Stability Through Inverse Covariance: Updating the inverse of the covariance matrix, rather than the covariance matrix itself, leads to more stable optimization, especially when the variance adaptively decreases.
  • High Precision on Challenging Problems: INGO demonstrates superior performance on difficult, ill-conditioned, and non-smooth functions (like Levy and $l_1$-Ellipsoid) where other methods, including IGO (which uses explicit natural gradients), fail to achieve high precision.
  • Simplicity and Fewer Hyperparameters: Compared to CMA-ES, INGO is presented as simpler and requiring fewer hyperparameters, making it easier to use.
  • Theoretical Guarantees: The authors provide theoretical convergence rate analysis for their continuous optimization methods, even for non-differentiable convex functions, which is a significant theoretical contribution.

Key Results

  • Competitive Performance: INGO achieves competitive performance against state-of-the-art methods like CMA-ES on benchmark problems.
  • Superior Precision: INGO and INGOstep (with full matrix update) achieve significantly higher optimization precision on challenging problems (e.g., Levy, $l_1$-Ellipsoid) compared to IGO.
  • Faster Convergence in RL: In reinforcement learning tasks, INGO (specifically Fast-INGO) shows faster convergence and higher average reward compared to ES and ASEBO, indicating the benefit of second-order information.
  • Theoretical Convergence: The paper proves convergence rates for their continuous optimization methods, including for non-differentiable convex functions.

Limitations and Future Work

  • Assumption of Exponential Family: The theoretical framework is based on exponential-family distributions. While flexible, it might not cover all possible distributions.
  • Full Matrix Update Complexity: While simpler than some methods, the full matrix update for the covariance can still be computationally intensive for very high dimensions. The paper does explore a diagonal version (Fast-INGO) to address this.
  • Future Work: The authors suggest exploring more complex distributions and further investigating the application of their framework to a wider range of real-world problems. They also highlight the potential for adaptive step-size selection and more sophisticated variance reduction techniques.

Summary updated

Abstract

Black-box optimization is primarily important for many computationally intensive applications, including reinforcement learning (RL), robot control, etc. This paper presents a novel theoretical framework for black-box optimization, in which our method performs stochastic updates with an implicit natural gradient of an exponential-family distribution. Theoretically, we prove the convergence rate of our framework with full matrix update for convex functions under Gaussian distribution. Our methods are very simple and contain fewer hyper-parameters than CMA-ES . Empirically, our method with full matrix update achieves competitive performance compared with one of the state-of-the-art methods CMA-ES on benchmark test problems. Moreover, our methods can achieve high optimization precision on some challenging test functions (e.g., $l_1$-norm ellipsoid test problem and Levy test problem), while methods with explicit natural gradient, i.e., IGO with full matrix update can not. This shows the efficiency of our methods.
BibTeX
@inproceedings{lyu2021black,
  author = {Yueming Lyu and Ivor Tsang},
  title = {{Black-box Optimizer with Implicit Natural Gradient}},
  booktitle = {ECML-PKDD},
  year = {2021},
  url = {https://openreview.net/forum?id=xFrbEvueDq},
}
Figure