427. Random embeddings for global optimization: convergence results beyond isotropy
Invited abstract in session MB-2: Optimization and applications, stream Nonsmooth and nonconvex optimization.
Monday, 10:30-12:30Room: B100/7011
Authors (first author is the speaker)
| 1. | Roy Makhlouf
|
| Applied Mathematics (EPL), UCLouvain | |
| 2. | Estelle Massart
|
Abstract
Many 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 low-dimensional 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.
Keywords
- Global optimization
- Large-scale optimization
Status: accepted
Back to the list of papers