Algorithm-independent bounds on complex optimization through the statistics of marginal optima
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911965422551040 |
|---|---|
| author | Kent-Dobias, Jaron |
| author_facet | Kent-Dobias, Jaron |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02092 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithm-independent bounds on complex optimization through the statistics of marginal optima Kent-Dobias, Jaron Disordered Systems and Neural Networks Statistical Mechanics 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. |
| title | Algorithm-independent bounds on complex optimization through the statistics of marginal optima |
| topic | Disordered Systems and Neural Networks Statistical Mechanics |
| url | https://arxiv.org/abs/2407.02092 |