EnKSGD: A Class Of Preconditioned Black Box Optimization And Inversion Algorithms

Brian Irwin, Sebastian Reich

Abstract

In this paper, we introduce the Ensemble Kalman-Stein Gradient Descent (EnKSGD) class of algorithms. The EnKSGD class of algorithms builds on the ensemble Kalman filter (EnKF) line of work, applying techniques from sequential data assimilation to unconstrained optimization and parameter estimation problems. The essential idea is to exploit the EnKF as a black box (i.e. derivative-free, zeroth order) optimization tool if iterated to convergence. In this paper, we return to the foundations of the EnKF as a sequential data assimilation technique, including its continuous-time and mean-field limits, with the goal of developing faster optimization algorithms suited to noisy black box optimization and inverse problems. The resulting EnKSGD class of algorithms can be designed to both maintain the desirable property of affine-invariance, and employ the well-known backtracking line search. Furthermore, EnKSGD algorithms are designed to not necessitate the subspace restriction property and variance collapse property of previous iterated EnKF approaches to optimization, as both these properties can be undesirable in an optimization context. EnKSGD also generalizes beyond the $L^{2}$ loss, and is thus applicable to a wider class of problems than the standard EnKF. Numerical experiments with both linear and nonlinear least squares problems, as well as maximum likelihood estimation, demonstrate the faster convergence of EnKSGD relative to alternative EnKF approaches to optimization.

Introduction

In many scientific and engineering domains, optimization problems involve a "forward model"—a simulation or process that connects inputs to outputs—that acts as a black box. While we can observe the output for a given input, we lack a closed-form mathematical expression for its gradient (Jacobian) or Hessian. This makes traditional gradient-based optimization difficult or impossible without expensive finite-difference approximations.

Standard derivative-free approaches, such as the Ensemble Kalman Filter (EnKF), have been adapted for optimization but face significant hurdles. They typically exhibit slow $1/t$ convergence rates, are often mathematically restricted to $L^2$ (least-squares) loss functions, and suffer from "subspace collapse," where the search becomes trapped within the small subspace defined by the initial ensemble of particles. EnKSGD (Ensemble Kalman-Stein Gradient Descent) is designed to overcome these limitations by combining the robustness of ensemble methods with the mathematical power of Stein’s Identity.

Methodology

The EnKSGD algorithm functions as a preconditioned black box optimizer. It mimics the behavior of a second-order Newton-like method to achieve fast convergence without ever requiring explicit Jacobian or Hessian calculations. The core components of the framework include:

  • Preconditioned Gradient Flow: Rather than following a simple gradient descent path, EnKSGD uses an estimate of the Hessian to precondition the update. This allows the algorithm to navigate narrow, ill-conditioned valleys in the optimization landscape efficiently.
  • Stein’s Identity: The "S" in EnKSGD refers to Stein’s Identity, which the authors use to estimate gradients and Hessians using only the spread of the ensemble. This enables second-order optimization benefits for the computational cost of simple function evaluations.
  • Ensemble Transform Kalman Filter (ETKF) Update: The algorithm employs an efficient time-stepping scheme borrowed from data assimilation to update particle positions.
  • Backtracking Line Search: Unlike many ensemble methods that rely on fixed step sizes, EnKSGD incorporates a standard backtracking line search to ensure that every step results in a sufficient reduction of the objective function.
  • Random $\beta$-Perturbations: To prevent subspace collapse, the algorithm adds controlled random noise to the particles. This ensures the ensemble maintains enough diversity to explore the entire parameter space, breaking the mathematical restriction to the initial ensemble's span.

Experimental Evaluation

The authors evaluated EnKSGD across a variety of challenging synthetic and benchmark scenarios:

  1. Ill-Conditioned Linear Least Squares: Designed to test convergence in difficult geometry.
  2. Nonlinear Least Squares Benchmarks: 11 classic problems, including the Rosenbrock "banana" function, from the NLSProblems.jl suite.
  3. Poisson Regression: A Maximum Likelihood Estimation (MLE) task testing the algorithm's ability to handle non-quadratic loss functions.
  4. Signal Reconstruction: Recovering signals passed through a noisy, nonlinear amplifier model.

Key Results

  • High Precision: In linear tests, EnKSGD reached objective values 10 orders of magnitude lower than standard EnKF or finite-difference gradient descent.
  • Benchmark Dominance: On nonlinear benchmarks, EnKSGD outperformed standard EnKF approaches in approximately 73% of cases. Notably, on the difficult Rosenbrock function, it surpassed standard EnKF by 20 orders of magnitude.
  • Noise Robustness: When stochastic noise was introduced to the black box evaluations, EnKSGD remained stable and converged near the noise floor, whereas traditional finite-difference methods failed.
  • Computational Efficiency: The algorithm achieved these results with a relatively small budget of forward model evaluations (e.g., 500 evaluations), making it viable for computationally expensive simulations.

Discussion and Future Work

EnKSGD demonstrates that by scaling the ensemble covariance correctly, the mean-field equations of an EnKF effectively become a time-rescaled Newton's method. This theoretical foundation allows for derivative-free preconditioning that is both fast and flexible regarding the choice of loss function.

However, several areas for future research remain. The current implementation requires the full dataset for each step; adapting the algorithm for mini-batching is essential for large-scale machine learning applications. Additionally, while empirical results are robust, formal mathematical proofs of convergence for the full EnKSGD algorithm are still being developed. Finally, extending the framework to handle physical or mathematical constraints (e.g., $x > 0$) will be necessary for broader industrial application.

Summary updated

Abstract

In this paper, we introduce the Ensemble Kalman-Stein Gradient Descent (EnKSGD) class of algorithms. The EnKSGD class of algorithms builds on the ensemble Kalman filter (EnKF) line of work, applying techniques from sequential data assimilation to unconstrained optimization and parameter estimation problems. The essential idea is to exploit the EnKF as a black box (i.e. derivative-free, zeroth order) optimization tool if iterated to convergence. In this paper, we return to the foundations of the EnKF as a sequential data assimilation technique, including its continuous-time and mean-field limits, with the goal of developing faster optimization algorithms suited to noisy black box optimization and inverse problems. The resulting EnKSGD class of algorithms can be designed to both maintain the desirable property of affine-invariance, and employ the well-known backtracking line search. Furthermore, EnKSGD algorithms are designed to not necessitate the subspace restriction property and variance collapse property of previous iterated EnKF approaches to optimization, as both these properties can be undesirable in an optimization context. EnKSGD also generalizes beyond the $L^{2}$ loss, and is thus applicable to a wider class of problems than the standard EnKF. Numerical experiments with both linear and nonlinear least squares problems, as well as maximum likelihood estimation, demonstrate the faster convergence of EnKSGD relative to alternative EnKF approaches to optimization.
BibTeX
@article{irwin2024enksgd,
  author = {Brian Irwin and Sebastian Reich},
  title = {{EnKSGD: A Class Of Preconditioned Black Box Optimization And Inversion Algorithms}},
  journal = {SIAM J. Sci. Comput},
  year = {2024},
  doi = {10.1137/23m1561142},
}
Figure