Lower and upper bounds of the convergence rate of gradient methods with composite noise in gradient
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910050839166976 |
|---|---|
| author | Vasin, Artem Gasnikov, Alexander |
| author_facet | Vasin, Artem Gasnikov, Alexander |
| contents | We introduce a detailed analysis of the convergence of first-order methods with composite noise (sum of relative and absolute) in gradient for convex and smooth function minimization. This paper illustrates instances of practical problems where the utilization of inexact oracles becomes necessary, such as biased compressors, use of floating-point arithmetic and gradient-free optimization. We propose an algorithm that optimally accumulates absolute error, with intermediate convergence depending on the relative component of the noise. Usage of restart technique, regularization transformation, and stopping criteria has been demonstrated to yield results for various function classes. Also, gradient descent adaptive to relative error parameter is provided. For relative noise, lower bounds of convergence are given, confirming the dependence of the parameter of the noise on the condition number of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_12376 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Lower and upper bounds of the convergence rate of gradient methods with composite noise in gradient Vasin, Artem Gasnikov, Alexander Optimization and Control We introduce a detailed analysis of the convergence of first-order methods with composite noise (sum of relative and absolute) in gradient for convex and smooth function minimization. This paper illustrates instances of practical problems where the utilization of inexact oracles becomes necessary, such as biased compressors, use of floating-point arithmetic and gradient-free optimization. We propose an algorithm that optimally accumulates absolute error, with intermediate convergence depending on the relative component of the noise. Usage of restart technique, regularization transformation, and stopping criteria has been demonstrated to yield results for various function classes. Also, gradient descent adaptive to relative error parameter is provided. For relative noise, lower bounds of convergence are given, confirming the dependence of the parameter of the noise on the condition number of the problem. |
| title | Lower and upper bounds of the convergence rate of gradient methods with composite noise in gradient |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.12376 |