Exploiting Structure with Anisotropic Consensus-Based Optimization

arXiv (Cornell University)

Abstract

Anisotropic consensus-based optimization (CBO), a multi-agent metaheuristic derivative-free optimization method, which reliably finds global minima of nonsmooth and nonconvex objective functions while being amenable to rigorous theoretical analysis, automatically detects and exploits additively separable structures of high-dimensional objective functions. This enables the algorithm to mitigate the curse of dimensionality where the objective function decomposes additively into lower-dimensional components. In this paper, we show this property proving that the computational complexity of anisotropic CBO depends exponentially only on the intrinsic dimension $\mathbf{d}$ of the objective function, rather than the ambient dimension $D\gg\mathbf{d}$. Additionally, we demonstrate that the computational complexity depends only on tractability conditions of the lower-dimensional components rather than on the full energy landscape, allowing for a more refined description of the objective function and algorithmic complexity, as the objective function landscape is captured directly at the level of the individual components. Our results highlight the effectiveness of anisotropic CBO for additively separable objective functions provided sufficient alignment between the structure of the anisotropic noise and the separability structure of the objective. This motivates the design of an enhanced algorithm that learns during optimization how to effectively explore the loss landscape by aligning the noise with the structure of the objective function, which we leave for future research. Numerical experiments validate our theoretical results, accentuating the influence of the intrinsic dimensionality $\mathbf{d}$, the level of separability, and the complexity and non-convexity of the objective within the separable components on performance and computational complexity of the anisotropic CBO algorithm.

Authors 3

1. Sabrina Bonandin Aachen Institute for Geometry and Practical Mathematics

   RWTH Aachen University

   Affiliation as printed

   Institute for Geometry and Practical Mathematics , RWTH Aachen University , Templergraben 55 , 52062 Aachen , Germany

2. Konstantin Riedl

   University of Oxford

   Affiliation as printed

   Mathematical Institute , University of Oxford ,

   Radcliffe Observatory , Andrew Wiles Building , Woodstock Rd , Oxford OX2 6GG , United Kingdom

3. Sara Veneruso Aachen Institute for Geometry and Practical Mathematics

   RWTH Aachen University · University of Ferrara

   Affiliation as printed

   Department of Mathematics and Computer Science , University of Ferrara , Via Machiavelli 30 , 44121 Ferrara , Italy

   Institute for Geometry and Practical Mathematics , RWTH Aachen University , Templergraben 55 , 52062 Aachen , Germany