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

Basic Information

• Paper ID: 2408.00720
• Title: Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound
• Authors: Yin Liu (Peking University), Sam Davanloo Tajbakhsh (Ohio State University)
• Classification: math.OC (Optimization and Control)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2408.00720

Abstract

This paper investigates nonasymptotic convergence bounds for accelerated first-order methods under inexact gradient oracles. Since obtaining exact gradients is infeasible or computationally expensive in many emerging applications, performance analysis of first-order algorithms under inexact oracles has received widespread attention. Previous research has shown that accelerated first-order methods are more sensitive to gradient errors compared to non-accelerated methods. This paper employs the Performance Estimation Problem (PEP) as the primary analytical tool, and by finding analytical solutions to the PEP, derives novel convergence bounds for the Generalized Optimized Gradient Method (GOGM) and Generalized Fast Gradient Method (GFGM) under absolute error bounds.

Research Background and Motivation

Problem Definition

This paper considers the optimization problem:

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

where f is a convex function with Lipschitz continuous gradient. In practical applications, only inexact gradient estimates are available:

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

Research Motivation

1. Practical Requirements: In bilevel optimization, combinatorial optimization, and zeroth-order optimization, obtaining exact gradients is difficult or computationally expensive
2. Theoretical Gaps: Existing analyses rely on strong assumptions (e.g., bounded feasible sets) or contain non-quantifiable terms
3. Method Limitations: Accelerated methods are more sensitive to gradient errors, requiring more refined analysis

Application Scenarios

• Bilevel Optimization: Lower-level problems can only be solved to suboptimal solutions
• Combinatorial Optimization: Gradient estimation through mini-batch sampling
• Zeroth-Order Optimization: Gradient estimation via finite differences or Gaussian smoothing

Core Contributions

1. Theoretical Breakthrough: Derives quantified convergence bounds for iGOGM and iGFGM under absolute error (AE) conditions, eliminating dependence on unknown parameters
2. Methodological Innovation: Finds analytical feasible solutions through PEP techniques, providing cumulative error terms independent of initial conditions
3. Practical Guidance: Analyzes the trade-off between convergence rate and cumulative error, providing optimal step-size selection strategies
4. Optimal Scheduling: Determines optimal strategies for setting gradient inexactness, minimizing total computational cost

Methodology Details

Task Definition

Study convergence of accelerated gradient methods under absolute error conditions:

• Input: Inexact gradient oracle satisfying ||∇̃f(x) - ∇f(x)|| ≤ b_x
• Output: Upper bound on convergence error f(x_K) - f*
• Constraint: f ∈ F_{0,L} (convex and L-smooth only)

Core Algorithms

iGOGM Algorithm (Algorithm 2)

Input: z_0 = x_0, A_0 = α_0 = 1, step-size parameters {λ_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)  # Key: coefficient is 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 (Algorithm 1)

Similar to iGOGM, but with coefficient 1 instead of 2 in step 3.

Technical Innovations

1. Analytical PEP Solutions

Through the dual form of the performance estimation problem, analytical feasible solutions are found:

τ = 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. Matrix Decomposition Techniques

Leveraging Schur complement and diagonally dominant matrix properties to ensure positive semi-definite constraints:

• Constructing Gram matrix G = X^T X
• Handling PSD constraints through block matrix decomposition
• Proving that u_i satisfies feasibility conditions

Main Theoretical Results

Theorem 2.2 (iGOGM Convergence Bound)

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

Theorem 2.4 (iGFGM Convergence Bound)

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

Key Characteristics:

• Cumulative error term is independent of initial condition ||x_0 - x*||
• Allows error levels b_k to vary along iterations
• Coefficients u_k can be computed explicitly

Experimental Setup and Results

Numerical Verification

1. Solution Verification: Validates analytical solutions through numerical solving with relative error < 10^{-3}
2. Trade-off Analysis: Analyzes convergence rate versus cumulative error trade-off for OGM-a (α_i = (i+a)/a)
3. Optimal Scheduling: Compares total complexity of fixed error versus optimally varying error

Key Findings

• When a=4, cumulative error is on the order of O(b²K³/L)
• Increasing a reduces cumulative error but decreases convergence rate
• Optimal error scheduling can significantly reduce total η-complexity

Related Work Comparison

Optimal Error Scheduling

Optimization Problem

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)

Power-Law Decay Case

For h(η) = c₁η^{-c₂}, the optimal solution is:

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

Exponential Decay Case

For h(η) = q₁q₂^{-η}, the optimal solution is:

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

Conclusions and Discussion

Main Conclusions

1. First to provide quantified, parameter-independent convergence bounds for accelerated methods under absolute error conditions
2. Cumulative error term is independent of initial conditions, depending only on Lipschitz constant and step-sizes
3. Optimal error scheduling can significantly reduce total computational complexity

Limitations

1. Theoretical results require α_k² < A_k (strict inequality), excluding the standard FGM case where α_k² = A_k
2. Optimal algorithm step-sizes lack recursive structure, making practical implementation difficult
3. Analysis primarily addresses deterministic settings; stochastic cases require further investigation

Future Directions

1. Extension to strongly convex cases and stochastic settings
2. Investigation of more general error conditions
3. Development of practical adaptive error control strategies

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: Fills the gap in analyzing accelerated methods under absolute error conditions
2. Advanced Technical Approach: Innovative application of PEP techniques
3. Strong Practical Utility: Provides computable error bounds and optimal scheduling strategies
4. Comprehensive Analysis: Combines theoretical proofs with numerical verification

Weaknesses

1. Limited Practical Applicability: Non-recursive nature of optimal algorithms restricts practical application
2. Restrictive Conditions: Strict α_k² < A_k condition excludes some important cases
3. Insufficient Experiments: Lacks numerical experiments on practical optimization problems

Impact

This paper provides important theoretical foundations for accelerated optimization under inexact oracles, with guidance for applications in bilevel optimization, combinatorial optimization, and related fields. The application of PEP techniques also provides new methodological approaches for related analyses.

Applicable Scenarios

• Large-scale optimization problems where gradient computation is expensive
• Bilevel and combinatorial optimization problems
• Applications requiring trade-offs between computational precision and iteration count
• Theoretical analysis of zeroth-order optimization methods

References

Key references include Drori & Teboulle's PEP theoretical foundations 18, Kim & Fessler's OGM methods 32,33, and Devolder et al.'s inexact oracle analysis 12.