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

Vernimmen, Pierre;Glineur, François
(2025) 5th International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences — Location: Metz, France (4.June.2025)

Files

Robustness-analysis-long-step-accelerated-methods-Vernimmen-Glineur-accepted.pdf
  • Open Access
  • Adobe PDF
  • 621.88 KB
Download

Details

Authors
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Vernimmen, P., & Glineur, F. (2025). Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization. Proceedings of the 5th International Conference on MCO 2025. Published. 5th International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, Metz, France.