Consensus-Based Optimization for Saddle Point Problems
arXiv:2212.12334 · doi:10.1137/22M1543367
Abstract
In this paper, we propose consensus-based optimization for saddle point problems (CBO-SP), a novel multi-particle metaheuristic derivative-free optimization method capable of provably finding global Nash equilibria. Following the idea of swarm intelligence, the method employs a group of interacting particles, which perform a minimization over one variable and a maximization over the other. This paradigm permits a passage to the mean-field limit, which makes the method amenable to theoretical analysis and allows to obtain rigorous convergence guarantees under reasonable assumptions about the initialization and the objective function, which most notably include nonconvex-nonconcave objectives.
References in corpus (8)
- A consensus-based model for global optimization and its mean-field limit
- Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
- Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
- On the Global Convergence of Particle Swarm Optimization Methods
- Consensus-Based Optimization on Hypersurfaces: Well-Posedness and Mean-Field Limit
- On the mean-field limit for the consensus-based optimization
- 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