2024/07/02 by Jaron Kent-Dobias, Kent-Dobias, Jaron · 1 citation
Mathematics · Computer Science · Engineering · #Advanced Optimization Algorithms Research #Metaheuristic Optimization Algorithms Research #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2407.02092
Optimization seeks extremal points in a function. When there are superextensively many optima, optimization algorithms are liable to get stuck. Under these conditions, generic algorithms tend to find marginal optima, which have many nearly flat directions. In a companion paper, we introduce a technique to count marginal optima in random landscapes. Here, we use the statistics of marginal optima calculated using this technique to produce generic bounds on optimization, based on the simple principle that algorithms will overwhelmingly tend to get stuck only where marginal optima are found. We demonstrate the idea on a simple non-Gaussian problem of maximizing the sum of squared random functions on a compact space. Numeric experiments using both gradient descent and generalized approximate message passing algorithms fall inside the expected bounds.