PaperlayerView exact revision on arXiv

Source-linked AI summary

Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations

Junzi Zhang, Brendan O'Donoghue, Stephen Boyd

arXiv:1808.03971v1math.OC

TL;DR

The paper addresses the lack of globally convergent acceleration for general non-smooth fixed-point problems under only non-expansiveness. It stabilizes type-I Anderson acceleration with regularization, restarting, and safeguarding, and reports greater robustness and efficiency than original AA-I in extensive experiments, while providing no convergence rate.

  • Problem

    The gap is globally convergent acceleration for general non-smooth fixed-point problems without assumptions beyond non-expansiveness.

  • Method

    The method stabilizes type-I Anderson acceleration using Powell-type regularization, restart checking, and safe-guarding steps.

  • Results

    Extensive numerical results across nine problem-algorithm combinations show the modified algorithm is more robust and efficient than original AA-I.

  • Takeaways & Limitations

    The method provides globally convergent acceleration for a larger class of first-order methods represented by non-expansive fixed-point iterations.

  • Takeaways & Limitations

    The analysis establishes convergence but does not provide a convergence rate or formally prove faster convergence than vanilla KM.

Abstract

from arXiv · show

We consider the application of the type-I Anderson acceleration to solving general non-smooth fixed-point problems. By interleaving with safe-guarding steps, and employing a Powell-type regularization and a re-start checking for strong linear independence of the updates, we propose the first globally convergent variant of Anderson acceleration assuming only that the fixed-point iteration is non-expansive. We show by extensive numerical experiments that many first order algorithms can be improved, especially in their terminal convergence, with the proposed algorithm. Our proposed method of acceleration is being implemented in SCS 2.0, one of the default solvers used in the convex optimization parser-solver CVXPY 1.0.

1 Introduction

The paper studies fixed-point problems with potentially non-smooth, non-expansive mappings and seeks acceleration beyond vanilla Krasnosel’skiı̆-Mann iteration. It positions limited-memory type-I Anderson acceleration as an underdeveloped approach whose global theory is missing under these relaxed conditions.

  • Motivation: Vanilla KM iteration is globally convergent for non-expansive mappings but can be extremely slow at moderate or high accuracy.Acceleration requires trading additional per-iteration work against fewer iterations.
  • Motivation: Fixed-point problems model applications including convex optimization, Nash equilibria, and Bellman operators.For convex optimization, the iteration mapping is typically non-expansive and its fixed points correspond to, or are closely related to, solutions of the original problem.
  • Theory gap: Existing convergence analyses generally require differentiability, structural symmetry, non-singularity, contractivity, or line search.These requirements exclude many projection- and proximal-operator-based algorithms and can make expensive function evaluations prohibitive.
  • Approach: The paper focuses on type-I Anderson acceleration, a less explored variant whose systematic treatment in optimization applications remains limited.AA-I is presented as elegant and effective in some applications but more vulnerable to instability than AA-II.
  • Theory gap: The authors identify no prior global convergence result for limited-memory AA-I under merely non-expansive, potentially non-smooth fixed-point iterations.Earlier related results are local or assume continuous differentiability and additional nonsingularity conditions.

2 Type-I Anderson acceleration

Type-I Anderson acceleration maintains a limited memory of prior steps and chooses dynamic weights through an approximate Jacobian of the residual. Its quasi-Newton formulation minimizes deviation from the identity subject to multi-secant constraints, but can become ill-conditioned when stored updates lose rank.

  • Quasi-Newton connection: The AA-I update is closely related to the type-I Broyden quasi-Newton method through rank-one updates.This contrasts with AA-II, which approximates an inverse Jacobian and corresponds to type-II Broyden updates.
  • Algorithmic framework: AA generalizes KM by combining images of several previous iterates with dynamically selected weights.The memory size m_k determines how many prior steps contribute to the next iterate.
  • Type-I formulation: AA-I approximates the residual Jacobian with B_k minimizing ∥B_k−I∥_F subject to the multi-secant condition B_kS_k=Y_k.The method assumes invertibility of B_k when forming the update.
  • Implementation: AA-I can compute its inverse-Jacobian expression by inverting only a small m_k × m_k matrix.The explicit formula follows from the Woodbury identity.
  • Failure mode: The iteration may get stuck or become ill-conditioned when B_k, S_k, or Y_k is approximately rank-deficient.This rank deficiency is identified as a major source of numerical instability in AA-I.

3 Stabilized type-I Anderson acceleration

The stabilized method combines Powell-type regularization, restart checking, and residual-based safeguarding to address singularity, rank deficiency, and instability. These modifications yield well-defined bounded updates and support global convergence under non-expansiveness.

  • Global convergence: Safe-guarding checks residual-norm decrease, and together with regularization and restarting leads to global convergence to a solution.The method is designed for general non-expansive, potentially non-smooth fixed-point problems without additional assumptions.
  • Powell regularization: Powell-type regularization modifies the rank-one updates to ensure that B_k remains nonsingular.The regularization parameter θ̄ bridges accelerated updates and the vanilla fixed-point iteration, with θ̄=1 reducing to the latter.
  • Restart checking: Restart checking clears memory when strong linear independence of the updates is threatened or the maximum memory is reached.The rule resets m_k when m_k=m+1 or when ∥ŝ_{k−1}∥_2<τ∥s_{k−1}∥_2.
  • Restart checking: The restart rule guarantees bounded approximate Jacobians, with ∥B_k∥≤3(1+θ̄+τ)^m/(τ^(m−2)).The positive τ threshold enforces a quantitative separation between each update and previous updates.
  • Stability guarantees: Combining modified updates with restarting removes the need for a full-rank assumption on S_k and bounds the inverse H_k.The resulting construction resolves the rank-deficiency problem in the limited-memory update process.

4 Analysis of global convergence

The proof establishes global convergence of Algorithm 3 by showing residuals vanish, distances to fixed points converge, and the iterates converge to a fixed-point solution.

  • Proof structure: The convergence proof proceeds in three steps: residual convergence, convergence of distances to any fixed point, and convergence of the iterates.This structure is stated explicitly for the global-convergence proof.
  • Boundedness: The iterates remain bounded because their distance to any fixed point remains bounded.The boundedness follows from the distance analysis and the nonnegative-distance argument.
  • Residual convergence: The residual norm converges to zero along both Anderson-accelerated and KM iterations.The proof partitions iterations into KAA and KKM and derives vanishing residuals for each subsequence.
  • Distance convergence: For every fixed point y, the distance ∥xk − y∥2 converges to a finite limit.The argument uses a subsequence attaining the lim inf and summable error terms.
  • Iterate convergence: The full sequence xk converges to a solution x⋆ satisfying x⋆ = f(x⋆).A contradiction argument rules out two distinct subsequential limits, while residual convergence identifies the limit as a fixed point.

5 Numerical results

The numerical section compares vanilla methods, limited-memory AA-I, and safeguarded limited-memory AA-I across iteration counts and clock time.

  • Experimental setup: The examples focus on optimization problems and algorithms whose mappings are verified to be non-expansive and equivalent to the original problems.The section specifies the fixed-point mapping for each example and checks the relevant equivalence.
  • Compared algorithms: Each experiment compares a vanilla algorithm, AA-I-m with maximum memory m, and safeguarded AA-I-S-m with maximum memory m.AA-I-S-m uses Algorithm 3, while AA-I-m uses Algorithm 2.
  • Evaluation: The experiments display convergence curves against both clock time and iteration number.This evaluates acceleration using computational time and iteration counts.

5.1 Problems and algorithms

The paper instantiates the fixed-point framework on proximal, projection, splitting, consensus, and conic-optimization algorithms, verifying non-expansiveness and links between fixed points and original solutions.

  • Proximal-gradient examples: Proximal gradient descent uses f(x) = proxαF2(x − α∇F1(x)) for convex closed proper objectives with F1 L-smooth and α ∈ (0, 2/L).Gradient descent and projected gradient descent arise when F2 is respectively zero or an indicator function.
  • Projection and shrinkage: Alternating projection and ISTA are represented by f(x) = ΠCΠD(x) and f(x) = Sαµ(x − α∇F(x)), respectively.Alternating projection targets intersections of closed convex sets, while ISTA covers sparsity-regularized regression.
  • Splitting methods: For DRS, the fixed-point mapping is non-expansive, and convergence of the fixed-point iterates yields convergence of the recovered primal variables to an original solution.The recovered variables are obtained through the resolvent RB.
  • SCS: In SCS, the fixed-point problem is equivalent to the self-dual homogeneous embedding system, so its solution encodes primal-dual solutions or infeasibility and unboundedness certificates.The conic problem is reformulated through the SDHE system and a DRS-based SCS mapping.
  • Contractive mappings: Algorithm 3 remains globally convergent when f is γ-contractive in an arbitrary norm, including norms such as l∞, rather than non-expansive in ℓ2.The paper notes that ℓ2 is essential to its non-expansive analysis, but contractivity in another norm provides a separate guarantee.

5.2 Numerical experiments

The experiments evaluate stabilized and original type-I Anderson acceleration against vanilla first-order methods across diverse problem instances, using iteration and wall-clock convergence curves. The stabilized method generally outperforms the original AA-I, with especially large gains where instability is severe, while safe-guarding adds a modest time cost.

  • Experimental setup: Across more than 80% of tested cases, AA-I-S-m outperforms AA-I-m in iteration count and clock time, and is almost always at least as good.The displayed instances were biased toward difficult cases, but the broader test set showed the same advantage.
  • Experimental setup: The experiments compare residual-norm convergence against iteration number and elapsed time, with residuals normalized by the initial norm and standard termination at tol = 10^-5.Plots label AA-I-m as aa1, AA-I-S-m as aa1-safe, and the vanilla method as origin.
  • Problem instances: 100x-1000x lower residual norms are obtained by AA-I-S-m than gradient descent on regularized logistic regression, while original AA-I-m completely fails.The accelerated residual curves can oscillate, but the objective-value improvement is more stable.
  • Problem instances: On AP for an LP formulation, both AA-I variants outperform vanilla AP in iterations, and AA-I-S-m gives a further slight running-time improvement over AA-I-m.This result is summarized for the residual-norm convergence curves in Figure 4.
  • Problem instances: The best performance in the memory experiment occurs at m = 10 for both accelerated variants, while deviations impede performance and smaller memories are less stable.A reasonably large memory such as m = 5 is described as more stable than a small one.
  • Summary of numerical results: The stabilized method improves over original AA-I-m across cases, with larger gains when original AA-I-m is unstable; safe-guard checks slightly slow runtime but provide a robustness trade-off.Rank-one updates and periodic restarts can also make the stabilized implementation faster than fixed-memory AA-I-m.

6 Extensions to more general settings

The paper extends its convergence analysis beyond fixed non-expansive mappings to quasi-nonexpansive, quasi-contractive, and iteration-dependent settings. Some extensions retain global convergence under additional conditions, while broader cases remain unresolved.

  • Quasi-nonexpansive mappings: The convergence theorem extends from non-expansive to quasi-nonexpansive mappings because the proof only compares arbitrary points with fixed points.
  • Quasi-nonexpansive mappings: The contractive result also holds for quasi-γ-contractive mappings in arbitrary norms, with averaging weight α allowed to equal 1.
  • Iteration-dependent mappings: For iteration-dependent mappings, global convergence is established when every mapping is quasi-nonexpansive and all mappings share the same fixed-point set.
  • Iteration-dependent mappings: The changing-mapping analysis requires residuals to vanish and cluster points to belong to the common fixed-point set; for gradient descent, a step size bounded below ensures these conditions.
  • Open extensions: Global convergence remains unresolved for vanishing step sizes and for non-expansive mappings in changing or arbitrary non-Euclidean norms.

7 Conclusions

The paper presents a modified type-I Anderson acceleration method for general non-smooth non-expansive fixed-point problems and reports stronger robustness and efficiency than original AA-I. It also identifies convergence, stochastic, scope, and rate questions that remain open.

  • The modified AA-I algorithm is designed to be globally convergent for general non-smooth non-expansive fixed-point problems without additional assumptions.
  • Extensive experiments across 9 problem-algorithm combinations show that the modified algorithm is more robust and efficient than original AA-I.
  • Further theorems establish global convergence for value iteration in MDPs and heavy ball methods in quadratic programs.
  • Open questions include general momentum methods, stochastic evaluations, algorithms outside the current non-expansive scope, and theoretical characterization of acceleration rates.

Appendices

The appendices provide proof details for the Anderson approximation and convergence results. They establish algebraic properties of the constructed matrix and complete convergence arguments by separating accelerated and safeguarded iterations.

  • Proof of Proposition 1: The appendix proves the constructed matrix satisfies the interpolation equations on update directions and acts as the identity on their orthogonal complement.
  • Proof of Proposition 1: Invertibility of the combined update and orthogonal-complement bases gives uniqueness of the matrix solution.
  • Proof of Theorem 7: Theorem 7’s proof partitions iterations into AA and KM subsets, treating finite safeguarded iterations separately from the infinite case.
  • Proof of Theorem 7: For accelerated iterations, boundedness follows from the earlier corollary and norm equivalence; safeguarded iterations are instead controlled using contractivity.
  • Proof of Theorem 7: The proof concludes that the iterates converge to the unique fixed point under contractivity.
Loading 1808.03971v1…