Scholarlink

<p>This paper is devoted to studying first-order methods for smooth convex optimization with inexact gradients. Unlike the majority of the literature on this topic, we consider the setting of relative rather than absolute inexactness. More precisely, we assume that the additive error in the gradient is proportional to the gradient norm, rather than being globally bounded by some small quantity. We propose a novel analysis of the accelerated gradient method under relative inexactness and strong convexity, improving the bound on the maximum admissible error that preserves the algorithm’s linear convergence. In other words, we analyze the robustness of the accelerated gradient method to relative gradient inexactness. Furthermore, using the Performance Estimation Problem (PEP) technique, we demonstrate that the obtained result is tight up to a numerical constant. Motivated by existing intermediate methods with absolute error, i.e., methods which convergence rates interpolate between the slower but more robust non-accelerated algorithms and the faster yet less robust accelerated algorithms, we propose an adaptive variant of the intermediate gradient method with relative gradient error.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Intermediate Gradient Methods with Relative Inexactness

  • 期刊论文

  • 发表日期：

    2025年8月22日

查看全文
  • Nikita Kornilov,
  • Mohammad Alkousa,
  • Eduard Gorbunov,
  • Fedor Stonyakin,
  • Pavel Dvurechensky,
  • Alexander Gasnikov

摘要

This paper is devoted to studying first-order methods for smooth convex optimization with inexact gradients. Unlike the majority of the literature on this topic, we consider the setting of relative rather than absolute inexactness. More precisely, we assume that the additive error in the gradient is proportional to the gradient norm, rather than being globally bounded by some small quantity. We propose a novel analysis of the accelerated gradient method under relative inexactness and strong convexity, improving the bound on the maximum admissible error that preserves the algorithm’s linear convergence. In other words, we analyze the robustness of the accelerated gradient method to relative gradient inexactness. Furthermore, using the Performance Estimation Problem (PEP) technique, we demonstrate that the obtained result is tight up to a numerical constant. Motivated by existing intermediate methods with absolute error, i.e., methods which convergence rates interpolate between the slower but more robust non-accelerated algorithms and the faster yet less robust accelerated algorithms, we propose an adaptive variant of the intermediate gradient method with relative gradient error.