Random embeddings for global optimization: Convergence results beyond isotropy

Details

Supervisors

Massart, Estelle

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

enMany real-world optimization problems are high-dimensional, requiring dimensionality reduction techniques to solve them efficiently. Recently, the use of random embeddings was shown to substantially outperform classical methods for Lipschitz continuous objectives with special structure, such as functions with low effective dimension. Tools from conic integral geometry have been used to explore the benefits of random embeddings for global optimization of Lipschitz continuous objectives with no additional structure. These tools allow to derive lower bounds on the probability that a random linear subspace intersects a ball of approximate minimizers, by using the circular cone tangent to the ball. We aim here to extend these results to functions that vary very slowly along a linear subspace, for which we replace the ball of approximate minimizers with an ellipsoid to account for the anisotropic structure of the objective. Our findings offer deeper insights into how the anisotropic structure in high-dimensional functions impacts optimization algorithms.