Name
Abstract | ||
|---|---|---|
We study the theoretical convergence properties of random-search methods when optimizing non-convex objective functions without having access to derivatives. We prove that standard random-search methods that do not rely on second-order information converge to a second-order stationary point. However, they suffer from an exponential complexity in terms of the input dimension of the problem. In order to address this issue, we propose a novel variant of random search that exploits negative curvature by only relying on function evaluations. We prove that this approach converges to a second-order stationary point at a much faster rate than vanilla methods: namely, the complexity in terms of the number of function evaluations is only linear in the problem dimension. We test our algorithm empirically and find good agreements with our theoretical results. |
Year | Venue | DocType |
|---|---|---|
2021 | Annual Conference on Neural Information Processing Systems | Conference |
ISSN | Citations | PageRank |
NeurIPS 2021 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aurelien Lucchi | 1 | 0 | 0.34 |
| Orvieto, Antonio | 2 | 0 | 3.04 |
| Adamos Solomou | 3 | 0 | 0.34 |