EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1439. Counter-examples in first-order optimization: a constructive approach
Invited abstract in session WC-32: Computer-Assisted Proofs in Optimization, stream Advances in large scale nonlinear optimization.
Wednesday, 12:30-14:00Room: 41 (building: 303A)
Authors (first author is the speaker)
| 1. | Aymeric Dieuleveut
|
| CMAP (Applied Maths), Ecole Polytechnique, Institut Polytechnique de Paris | |
| 2. | Adrien Taylor
|
| Inria/ENS | |
| 3. | Baptiste Goujaud
|
| CMAP, Ecole Polytechnique |
Abstract
While many approaches were developed for obtaining worst-case complexity bounds for first-order optimization methods in the last years, there remain theoretical gaps in cases where no such bound can be found. In such cases, it is often unclear whether no such bound exists (e.g., because the algorithm might fail to systematically converge) or simply if the current techniques do not allow finding them. In this work, we propose an approach to automate the search for cyclic trajectories generated by first-order methods. This provides a constructive approach to show that no appropriate complexity bound exists, thereby complementing approaches providing sufficient conditions for convergence.
Keywords
- Convex Optimization
- Large Scale Optimization
Status: accepted
Back to the list of papers