# Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 11 Jun 2025.

## Builds on (most cited first, 4 of 4)

- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Exact Worst-case Performance of First-order Methods for Composite Convex Optimization](https://mlsanity.com/paper/1512.07516/) (2015)
- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)

## Abstract (arXiv)

This work assesses both empirically and theoretically, using the performance estimation methodology, how robust different first-order optimization methods are when subject to relative inexactness in their gradient computations. Relative inexactness occurs, for example, when compressing the gradient using fewer bits of information, which happens when dealing with large-scale problems on GPUs. Three major families of methods are analyzed: constant step gradient descent, long-step methods, and accelerated methods. The latter two are first shown to be theoretically not robust to inexactness. Then, a semi-heuristic shortening factor is introduced to improve their theoretical guarantees. All methods are subsequently tested on a concrete inexact problem, with two different types of relative inexactness, and it is observed that both accelerated methods are much more robust than expected, and that the shortening factor significantly helps the long-step methods. In the end, all shortened methods appear to be promising, even in this inexact setting.