LM-CMA: An Alternative to L-BFGS for Large-Scale Black Box Optimization

Area of Science:

• Numerical Optimization
• Computational Mathematics
• Machine Learning Algorithms

Background:

• Limited-memory BFGS (L-BFGS) is a standard for continuous optimization when gradient information is accessible.
• Estimating gradients numerically for L-BFGS in black box scenarios can reduce accuracy and cause premature convergence.
• Derivative-free optimization methods are needed for problems where gradient information is unavailable or unreliable.

Purpose of the Study:

• To introduce and evaluate the Limited Memory Covariance Matrix Adaptation Evolution Strategy (LM-CMA) as an alternative to L-BFGS in derivative-free optimization.
• To analyze the performance and properties of LM-CMA on nonlinear, nonconvex, and large-scale optimization problems.
• To compare LM-CMA against established methods like L-BFGS and CMA-ES.

Main Methods:

• LM-CMA is a stochastic, derivative-free algorithm inspired by L-BFGS.
• It samples candidate solutions using a covariance matrix derived from selected direction vectors.
• Cholesky decomposition is employed to achieve memory and time complexity of O(m^2), where m is the number of variables.

Main Results:

• LM-CMA demonstrates invariance to strictly increasing transformations of the objective function.
• The algorithm achieves a memory complexity of O(m^2) and sampling time complexity of O(m^2).
• LM-CMA outperforms CMA-ES on ill-conditioned, nonseparable problems and shows comparable performance to L-BFGS on large-scale smooth and nonsmooth problems.

Conclusions:

• LM-CMA provides an effective derivative-free approach for continuous optimization, particularly in black box settings.
• Its computational efficiency and robustness make it suitable for large-scale and complex optimization tasks.
• LM-CMA represents a significant advancement in derivative-free optimization, offering a competitive alternative to gradient-based methods.