2025-11-22T03:37:15.627362

Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound

Liu, Tajbakhsh
Performance analysis of first-order algorithms with inexact oracles has gained recent attention due to various emerging applications in which obtaining exact gradients is impossible or computationally expensive. Previous research has demonstrated that the performance of accelerated first-order methods is more sensitive to gradient errors compared with non-accelerated ones. This paper investigates the nonasymptotic convergence bound of two accelerated methods with inexact gradients to solve deterministic smooth convex problems. Performance Estimation Problem (PEP) is used as the primary tool to analyze the convergence bounds of the underlying algorithms. By finding an analytical solution to PEP, we derive novel convergence bounds of Generalized Optimized Gradient Method (GOGM) and Generalized Fast Gradient Method (GFGM) with inexact gradient oracles following the absolute error bound. The derived bounds allow varying oracle inexactness along the iterations; furthermore, their accumulated error terms are independent of the initial condition and any unknown parameters. Furthermore, we analyze the tradeoff between the vanishing term and the accumulated error in the convergence bound that guides finding the optimal stepsize. Finally, we determine the optimal strategy to set the gradient inexactness along iterations (if possible in a given application), ensuring that the accumulated error remains subordinate to the vanishing term.
academic

Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound

基本信息

  • 论文ID: 2408.00720
  • 标题: Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound
  • 作者: Yin Liu (北京大学), Sam Davanloo Tajbakhsh (俄亥俄州立大学)
  • 分类: math.OC (优化与控制)
  • 发表时间: 2025年10月15日
  • 论文链接: https://arxiv.org/abs/2408.00720

摘要

本文研究了在不精确梯度oracle下加速一阶方法的非渐近收敛界。由于在许多新兴应用中获取精确梯度是不可能的或计算代价昂贵，不精确oracle下一阶算法的性能分析受到广泛关注。先前研究表明，相比非加速方法，加速一阶方法对梯度误差更加敏感。本文使用性能估计问题(PEP)作为主要分析工具，通过找到PEP的解析解，为广义优化梯度方法(GOGM)和广义快速梯度方法(GFGM)在绝对误差界下导出了新的收敛界。

研究背景与动机

问题定义

本文考虑优化问题：

min_{x∈R^d} f(x)

其中f是凸函数且具有Lipschitz连续梯度。在实际应用中，只能获得不精确的梯度估计：

∇̃f(x) = ∇f(x) + e, ||e|| ≤ b

研究动机

  1. 实际需求：在双层优化、组合优化、零阶优化等应用中，获取精确梯度困难或代价昂贵
  2. 理论缺陷：现有分析依赖于强假设条件(如有界可行域)或包含不可量化项
  3. 方法局限：加速方法对梯度误差更敏感，需要更精细的分析

应用场景

  • 双层优化：下层问题只能求解到次优解
  • 组合优化：通过小批量采样估计期望
  • 零阶优化：通过有限差分或高斯平滑估计梯度

核心贡献

  1. 理论突破：导出了iGOGM和iGFGM在绝对误差(AE)条件下的量化收敛界，消除了对未知参数的依赖
  2. 方法创新：通过PEP技术找到了解析可行解，提供了独立于初始条件的累积误差项
  3. 实用指导：分析了收敛率与累积误差的权衡，提供了最优步长选择策略
  4. 最优调度：确定了梯度不精确度的最优设置策略，最小化总计算成本

方法详解

任务定义

研究在绝对误差条件下加速梯度方法的收敛性：

  • 输入：不精确梯度oracle满足 ||∇̃f(x) - ∇f(x)|| ≤ b_x
  • 输出：收敛界 f(x_K) - f* 的上界
  • 约束：f ∈ F_{0,L} (仅凸且L-光滑)

核心算法

iGOGM算法 (Algorithm 2)

输入: z_0 = x_0, A_0 = α_0 = 1, 步长参数{λ_k}
for k = 0 to K-1:
    y_{k+1} = x_k - (1/L)∇̃f(x_k)
    z_{k+1} = z_k - (2/L)α_k∇̃f(x_k)  # 关键：系数为2
    α_{k+1} = (λ_{k+1} + √(4λ_{k+1}A_k + λ²_{k+1}))/2
    A_{k+1} = A_k + α_{k+1}
    x_{k+1} = (1 - α_{k+1}/A_{k+1})y_{k+1} + (α_{k+1}/A_{k+1})z_{k+1}

iGFGM算法 (Algorithm 1)

与iGOGM类似，但第3步系数为1而非2。

技术创新点

1. PEP解析解

通过性能估计问题的对偶形式，找到解析可行解：

τ = L/(4A_K), v_{i,i+1} = A_i/A_K
u_i = [A_i(1+2α_{i+1})(A_i+2α_iα_{i+1})]/(4LA_K(A_{i+1}-α²_{i+1})) + Σ_{k=i+1}^{K-1} [A_k(1+2α_{k+1})α_iα_{k+1}]/(2LA_K(A_{k+1}-α²_{k+1}))

2. 矩阵分解技术

利用Schur补和对角占优矩阵性质，确保半正定约束：

  • 构造Gram矩阵G = X^T X
  • 通过分块矩阵分解处理PSD约束
  • 证明u_i给出的解满足可行性条件

主要理论结果

定理2.2 (iGOGM收敛界)

f(x_K) - f* - (1/2L)||∇f(x_K)||² ≤ L||x_0-x*||²/(4A_K) + Σ_{k=0}^{K-1} u_k||e_k||²

定理2.4 (iGFGM收敛界)

f(x_K) - f* - (1/2L)||∇f(x_K)||² ≤ L||x_0-x*||²/(2A_K) + Σ_{k=0}^{K-1} u_k||e_k||²

关键特性：

  • 累积误差项独立于初始条件||x_0 - x*||
  • 允许沿迭代变化的误差水平b_k
  • 系数u_k可显式计算

实验设置与结果

数值验证

  1. 解的验证：通过数值求解验证解析解的准确性，相对误差<10^{-3}
  2. 权衡分析：对OGM-a (α_i = (i+a)/a)分析收敛率与累积误差的权衡
  3. 最优调度：比较固定误差vs最优变化误差的总复杂度

关键发现

  • 当a=4时，累积误差在O(b²K³/L)量级
  • 增大a可减少累积误差但会降低收敛率
  • 最优误差调度可显著降低总η-复杂度

相关工作对比

误差条件允许变化误差?迭代复杂度限制条件
BIE 8×O(1/A_K + δ)有界可行集
IFO 12✓O(1/A_K + Σδ_i/A_K)有界可行集
IFO-q 41×O(1/K² + δ/K^{3q/2-1})次梯度条件
AE 58×O(1/K² + R̃_Kδ + Kδ²)未知R̃_K
本文✓O(1/A_K + Σu_kb_k²)无额外假设

最优误差调度

优化问题

min Σ_{k=0}^{K-1} η_k = Σ_{k=0}^{K-1} h^{-1}(b_k)
s.t. Σ_{k=0}^{K-1} u_kb_k² ≤ LR²/(4A_K)

幂律衰减情况

对h(η) = c₁η^{-c₂}，最优解为：

b_k* = √(LR²/(4A_K)) · u_k^{1/(1+2c₂)} / (Σu_j^{1/(1+2c₂)})^{1/2}

指数衰减情况

对h(η) = q₁q₂^{-η}，最优解为：

b_k* = √(LR²/(4KA_Ku_k))

结论与讨论

主要结论

  1. 首次为绝对误差条件下的加速方法提供了量化的、独立于未知参数的收敛界
  2. 累积误差项独立于初始条件，仅依赖于Lipschitz常数和步长
  3. 最优误差调度可显著降低总计算复杂度

局限性

  1. 理论结果要求α_k² < A_k (严格不等式)，排除了标准FGM的α_k² = A_k情况
  2. 最优算法的步长缺乏递归结构，实际实现困难
  3. 分析主要针对确定性设置，随机情况需进一步研究

未来方向

  1. 扩展到强凸情况和随机设置
  2. 研究更一般的误差条件
  3. 开发实用的自适应误差控制策略

深度评价

优点

  1. 理论贡献显著：填补了绝对误差条件下加速方法分析的空白
  2. 技术手段先进：PEP技术的应用富有创新性
  3. 结果实用性强：提供了可计算的误差界和最优调度策略
  4. 分析深入全面：既有理论证明又有数值验证

不足

  1. 实用性受限：最优算法的非递归性质限制了实际应用
  2. 条件限制：严格的α_k² < A_k条件排除了一些重要情况
  3. 实验不足：缺乏在实际优化问题上的数值实验

影响力

本文为不精确oracle下的加速优化提供了重要理论基础，对双层优化、组合优化等应用领域具有指导意义。PEP技术的应用也为相关分析提供了新的方法论。

适用场景

  • 梯度计算代价昂贵的大规模优化问题
  • 双层优化和组合优化问题
  • 需要在计算精度和迭代次数间权衡的应用
  • 零阶优化方法的理论分析

参考文献

关键参考文献包括Drori & Teboulle的PEP理论基础18、Kim & Fessler的OGM方法32,33、以及Devolder等人的不精确oracle分析12。