EUROPT 2025
Abstract Submission

533. Computer-aided analysis of relatively inexact gradient descent in smooth convex optimization

Invited abstract in session TC-8: Systematic and computer-aided analyses V: Tools for systematic studies of first-order algorithms, stream Systematic and computer-aided analyses of optimization algorithms.

Tuesday, 14:00-16:00
Room: B100/7007

Authors (first author is the speaker)

1. Pierre Vernimmen
ICTEAM, UCLouvain
2. François Glineur
ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain)

Abstract

In this work, we analyze relatively inexact gradient descent, which is a version of gradient descent using at each step an approximation of the gradient. We call it relatively inexact as we require that the norm of the error is bounded by a fraction of the norm of the gradient itself. We prove that the method converges in gradient norm, and derive its exact worst-case convergence rate for any stepsize when performing one iteration. We also show that these tight rates belong to three distinct regimes. Two regimes (short and long steps) are simple adaptations of the exact case, corresponding to simple univariate worst-case functions (Huber or quadratic). The third intermediate regime does not occur in the exact case and corresponds to a bivariate worst-case function.

We also demonstrate how relatively inexact gradients naturally occur in the context of compressed gradient descent, in which the gradient is stored using a small number of bits of information. This compression technique is frequently used when computing on GPUs.

Finally, we conduct a numerical experiment using several first-order methods (classical gradient descent, long-step methods and accelerated methods) to check their robustness to relative inexactness empirically in a more practical setting. We also propose and test a simple and universal way to adapt methods to deal with relative inexactness, namely, to shorten all step sizes by a well-chosen factor.

Keywords

Status: accepted

Back to the list of papers