# On Fundamental Proof Structures in First-Order Optimization

arXiv: https://arxiv.org/abs/2310.02015 · HTML: https://mlsanity.com/paper/2310.02015/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2023.

## Built on by (most cited first, 4 of 4)

- [Towards a Systems Theory of Algorithms](https://mlsanity.com/paper/2401.14029/) (2024)
- [Learning to optimize with convergence guarantees using nonlinear system theory](https://mlsanity.com/paper/2403.09389/) (2024)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)

## Abstract (arXiv)

First-order optimization methods have attracted a lot of attention due to their practical success in many applications, including in machine learning. Obtaining convergence guarantees and worst-case performance certificates for first-order methods have become crucial for understanding ingredients underlying efficient methods and for developing new ones. However, obtaining, verifying, and proving such guarantees is often a tedious task. Therefore, a few approaches were proposed for rendering this task more systematic, and even partially automated. In addition to helping researchers finding convergence proofs, these tools provide insights on the general structures of such proofs. We aim at presenting those structures, showing how to build convergence guarantees for first-order optimization methods.