316. An invariance theory for complete characterization of exact optimal fixed-point algorithm family
Invited abstract in session MD-8: Systematic and computer-aided analyses III: noisy gradient methods and fixed-point algorithms, stream Systematic and computer-aided analyses of optimization algorithms.
Monday, 16:30-18:30Room: B100/7007
Authors (first author is the speaker)
| 1. | TaeHo Yoon
|
| Applied Mathematics and Statistics, Johns Hopkins University | |
| 2. | Ernest Ryu
|
| Department of Mathematical Sciences, Seoul National University | |
| 3. | Benjamin Grimmer
|
| Applied Mathematics and Statistics, Johns Hopkins University |
Abstract
For nonexpansive fixed-point problems, both Halpern's method with optimal parameters and its so-called H-dual algorithm exhibit the exact optimal worst-case convergence rates. In this work, we completely characterize the infinite family of distinct algorithms using predetermined step-sizes, represented as lower triangular H-matrices, all of which attain the same optimal convergence rates. The characterization is based on algebraic quantities that we call H-invariants, whose values stay constant over all optimal H-matrices. The theory of H-invariants offers a novel view of optimal acceleration in first-order optimization as an algebraic study of carefully selected invariants and structures induced by them.
Keywords
- Monotone inclusion problems
- Complexity and efficiency of algorithms
- Computer-aided algorithm analysis
Status: accepted
Back to the list of papers