83. Geometry and the complexity of first-order methods for Lipschitz optimization
Invited abstract in session WB-9: Variational Analysis III, stream Variational analysis: theory and algorithms.
Wednesday, 10:30-12:30Room: B100/8013
Authors (first author is the speaker)
| 1. | Adrian Lewis
|
| School of ORIE, Cornell University |
Abstract
We study first-order optimization algorithms from three geometric viewpoints. We first consider the simple idea of "slope" - a purely metric notion - and its role in popular convergence analyses based on the Kurdyka–Lojasiewicz inequality. We next introduce a measure of nonconvexity, and investigate its influence on the dimension-independent complexity of recent algorithms (Zhang et al, 2020) for optimizing objectives - common in machine learning - that may not be even weakly convex. Finally, we introduce a new local growth condition, inspired by a classical idealized iteration (Goldstein, 1977) for Lipschitz optimization, and explore its impact on near-linear local convergence.
Joint work with Siyu Kong and Tonghua Tian
Keywords
- Non-smooth optimization
- First-order optimization
- Complexity and efficiency of algorithms
Status: accepted
Back to the list of papers