MirrorCBO: A consensus-based optimization method in the spirit of mirror descent

Abstract

In this work we propose MirrorCBO, a consensus-based optimization (CBO) method which generalizes standard CBO in the same way that mirror descent generalizes gradient descent. For this we apply the CBO methodology to a swarm of dual particles and retain the primal particle positions by applying the inverse of the mirror map, which we parametrize as the subdifferential of a strongly convex function $\varphi$. In this way, we combine the advantages of a derivative-free non-convex optimization algorithm with those of mirror descent. As a special case, the method extends CBO to optimization problems with convex constraints. Assuming bounds on the Bregman distance associated to $\varphi$, we provide asymptotic convergence results for MirrorCBO with explicit exponential rate. Another key contribution is an exploratory numerical study of this new algorithm across different application settings, focusing on (i) sparsity-inducing optimization, and (ii) constrained optimization, demonstrating the competitive performance of MirrorCBO. We observe empirically that the method can also be used for optimization on (non-convex) submanifolds of Euclidean space, can be adapted to mirrored versions of other recent CBO variants, and that it inherits from mirror descent the capability to select desirable minimizers, like sparse ones. We also include an overview of recent CBO approaches for constrained optimization and compare their performance to MirrorCBO.

66 pages, 18 figures, 19 tables

References in corpus (13)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Array Programming with NumPy
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• A consensus-based model for global optimization and its mean-field limit
• Coherent X-ray Diffractive Imaging; applications and limitations
• On the Global Convergence of Particle Swarm Optimization Methods
• Consensus-Based Optimization on Hypersurfaces: Well-Posedness and Mean-Field Limit
• Consensus-Based Optimization Methods Converge Globally
• Convergence of Anisotropic Consensus-Based Optimization in Mean-Field Law
• Leveraging Memory Effects and Gradient Information in Consensus-Based Optimization: On Global Convergence in Mean-Field Law
• Mirror Descent for Constrained Optimization Problems with Large Subgradient Values
• Polarized consensus-based dynamics for optimization and sampling
• CBX: Python and Julia packages for consensus-based interacting particle methods

Cited by in corpus (1)

• Adversarial flows: A gradient flow characterization of adversarial attacks