Convergence of gradient methods under conditions of absolute and relative inaccuracy

The concept of relative inaccuracy was introduced back in the 60s of the last century in the works of B.T. Polyak. Real machine arithmetic leads to just such a concept. Actually, this is an important question, the answer to which was received by B.T. Pole in his first works on this topic.: how will the gradient method converge in conditions of relative inaccuracy in the gradient? The answer turned out to be very optimistic - if the scale of relative inaccuracy is strictly less than one (that is, noise spoils the direction of the gradient, but cannot reverse it), then convergence does not change (for highly convex problems, linear convergence remains at a slightly slower rate).
However, the usual gradient methods are not optimal! Accelerated methods are optimal methods. And for them, the answer to the question is still open. In this report, we will talk about recent progress in answering the question of how accelerated methods converge under conditions of an absolutely and relatively inaccurate gradient.
In modern applications of optimization algorithms, distributed versions of gradient methods are often used in training large generative models. Communication is becoming a bottleneck. In order to reduce the communication time, various compression and quantization methods are used. In practice, offset gradient compressions are often the most effective. Mathematically, this leads to a relative inaccuracy in the gradient. We will also talk about applications of the obtained results to solving inverse problems.