A Practical Adaptive Subgame Perfect Gradient Method
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917268762394624 |
|---|---|
| author | Luner, Alan Grimmer, Benjamin |
| author_facet | Luner, Alan Grimmer, Benjamin |
| contents | We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on a (limited) memory/bundle of past first-order information. ASPGM is linesearch-free, parameter-free, and adaptive due to its use of recently developed auto-conditioning, restarting, and preconditioning ideas. We show that ASPGM is competitive with state-of-the-art L-BFGS methods on a wide range of smooth convex problems. Unlike quasi-Newton methods, however, our core algorithm underlying ASPGM has strong, subgame perfect, non-asymptotic guarantees, providing certificates of solution quality, resulting in simple stopping criteria and restarting conditions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21617 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Practical Adaptive Subgame Perfect Gradient Method Luner, Alan Grimmer, Benjamin Optimization and Control We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on a (limited) memory/bundle of past first-order information. ASPGM is linesearch-free, parameter-free, and adaptive due to its use of recently developed auto-conditioning, restarting, and preconditioning ideas. We show that ASPGM is competitive with state-of-the-art L-BFGS methods on a wide range of smooth convex problems. Unlike quasi-Newton methods, however, our core algorithm underlying ASPGM has strong, subgame perfect, non-asymptotic guarantees, providing certificates of solution quality, resulting in simple stopping criteria and restarting conditions. |
| title | A Practical Adaptive Subgame Perfect Gradient Method |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.21617 |