PaperlayerView exact revision on arXiv

Source-linked AI summary

Anderson Acceleration of Proximal Gradient Methods

Vien V. Mai, Mikael Johansson

arXiv:1910.08590v2math.OCcs.LG

TL;DR

Existing AA convergence guarantees in optimization have largely concerned smooth, unconstrained problems, leaving non-smooth and constrained proximal methods less addressed. This paper adapts AA to proximal gradient methods, establishes local convergence under technical conditions, and shows native AA can fail globally; a guard combines AA’s local adaptation with PGA’s global worst-case guarantees.

  • Problem

    Prior AA convergence guarantees in optimization mainly covered unconstrained or smooth problems, while non-smooth composite settings lacked local guarantees without safeguards.

    Source: §1.1 · p. 2

  • Method

    The paper adapts AA to proximal gradient methods and adds a guard step that preserves PGA’s global worst-case convergence guarantees.

    Source: §1.1 · p. 2, §3 · p. 6, §7 · p. 18

  • Results

    Under mild conditions AA-PGA converges locally, while an analytic smooth, strongly convex example shows native AA can become trapped in a periodic orbit.

    Source: §3.1 · p. 9, §4 · p. 9

  • Takeaways & Limitations

    The guarded scheme combines proximal gradient methods’ global worst-case guarantees with AA’s local adaptation and potential acceleration.

    Source: §1.1 · p. 2, §7 · p. 18

    For BPG, if the optimum lies on the boundary of dom ϕ, the mirror map at the optimum does not exist, complicating general theoretical guarantees.

    Source: §5 · p. 13

Abstract

from arXiv · show

Anderson acceleration is a well-established and simple technique for speeding up fixed-point computations with countless applications. Previous studies of Anderson acceleration in optimization have only been able to provide convergence guarantees for unconstrained and smooth problems. This work introduces novel methods for adapting Anderson acceleration to (non-smooth and constrained) proximal gradient algorithms. Under some technical conditions, we extend the existing local convergence results of Anderson acceleration for smooth fixed-point mappings to the proposed scheme. We also prove analytically that it is not, in general, possible to guarantee global convergence of native Anderson acceleration. We therefore propose a simple scheme for stabilization that combines the global worst-case guarantees of proximal gradient methods with the local adaptation and practical speed-up of Anderson acceleration.

1 Introduction

The introduction motivates local adaptation because global problem constants are often unknown or overly conservative, while existing Anderson acceleration (AA) analyses have focused mainly on smooth or unconstrained settings. The paper proposes AA for proximal gradient methods, studies global convergence and stabilization, and extends the approach to Bregman proximal gradient methods.

1 Introduction

  • Global bounds may poorly reflect changing local behavior, motivating algorithms that adapt and accelerate near the optimum.The introduction notes that strong practical performance may require local adaptation, and that accelerated gradient methods can be sensitive to misspecified strong-convexity parameters.Source: §1 · p. 1

1.1 Related Work

  • Prior AA work on optimization largely addressed unconstrained or linearly constrained problems, with non-smooth composite settings lacking local guarantees without safeguards.The paper identifies reliance on linearization and differentiability of the fixed-point mapping as a barrier to analysis in non-smooth optimization.Source: §1.1 · p. 2
  • The paper proposes AA for classical proximal gradient methods with local convergence under mild conditions, and a guard step that preserves PGA’s global worst-case guarantees.It also constructs a smooth, strongly convex example where native AA fails to converge, and adapts AA to Bregman proximal gradient methods, including mirror descent and NoLips as special cases.Source: §1.1 · p. 2

1.2 Notation

  • The notation section defines R+ as the nonnegative reals and specifies conventions for set interiors, norms, the all-ones vector, and o(t).For x=o(t), the Euclidean norm of x divided by t tends to zero as t tends to zero.Source: §1.2 · p. 2

2 Anderson acceleration

Anderson acceleration (AA) uses recent residuals to choose an extrapolated iterate, and can be implemented with a small least-squares problem. Applied to optimization, it offers local adaptation without requiring problem parameters, while its updates also connect to multi-step methods.

2 Anderson acceleration

  • AA chooses coefficients to minimize the residual of a combination of recent iterates, then applies the mapping to the extrapolated point.For affine mappings, the residual-minimization formulations are equivalent; with memory m=0, AA reduces to fixed-point iteration.Source: §2 · p. 3
  • The coefficient problem can be solved as a least-squares problem, with QR updates making the added computation negligible relative to evaluating the mapping.The stated practical memory range is typically m between 1 and 10.Source: §2 · p. 4

2.1 Anderson acceleration for optimization algorithms

  • On quadratic problems, full-information AA is essentially equivalent to GMRES and adapts to the condition number without knowing problem parameters, unlike AGD.The cited rate is attained by AA without knowledge of the problem, whereas AGD requires the largest and smallest eigenvalues to achieve that rate.Source: §2.1 · pp. 4–5
  • In the illustrated quadratic problems, AA initially matches AGD’s 1/k^2 rate before switching to linear convergence, even with small memory.The figure compares AA-GD, GD, AGD, and AGD-Restart on a 100-dimensional problem with 25 nonzero eigenvalues.Source: Figure 1 · p. 4, §2.1 · p. 5

2.2 Anderson acceleration as a multi-step method

  • With memory m=1, AA-GD is analogous to AGD and heavy ball, but combines gradients evaluated at the current and previous iterates.For m>1 it resembles MiFB; unlike AA, MiFB lacks an efficient coefficient-selection method in the cited discussion, restricting its history parameter to 1 or 2.Source: §2.2 · p. 5

3 Anderson Acceleration for Proximal Gradient Method

The section adapts Anderson acceleration to proximal gradient by applying it to an auxiliary fixed-point sequence, avoiding infeasible iterates from direct extrapolation. It establishes local convergence under technical conditions.

3 Anderson Acceleration for Proximal Gradient Method

  • Directly applying AA to the proximal-gradient mapping can produce iterates outside dom h, where ∇f may be undefined; AA-PGA instead accelerates an auxiliary sequence.The auxiliary sequence has no feasibility restrictions, and each AA-PGA step requires one gradient and one proximal evaluation.Source: §3 · p. 6
  • Driving the auxiliary sequence y_k quickly to y* implies that the primal sequence x_k quickly converges to x*.The connection follows from nonexpansiveness of proximal operators.Source: §3 · p. 6
  • AA-PGA applies AA to y_k under g and recovers the primal iterate through the proximal operator.A fixed point y* of g yields an optimal x* = prox_γh(y*).Source: §3 · p. 6

3.1 Local Convergence Guarantees

  • Local analysis addresses the generally nondifferentiable mapping using second-order regularity, including twice epi-differentiable h with a generalized quadratic second-order epi-derivative.The stated setting includes C2 f and polyhedral h; broader examples include partly smooth regularizers such as the nuclear norm.Source: §3.1 · pp. 7–8
  • With the stated assumptions and initialization sufficiently near a fixed point, AA-PGA does not slow PGA in the worst case for any fixed memory m; stronger adaptive rates are expected in most cases.Whether finite-memory AA can guarantee a rate stronger than PGA remains open.Source: §3.1 · p. 9

4 Guarded Anderson Accelerated PGA

The section shows that native Anderson acceleration can fail globally, even on a smooth strongly convex problem, and introduces a guard that preserves PGA’s global convergence rate while retaining AA’s potential for local adaptation.

4 Guarded Anderson Accelerated PGA

  • AA-GD can converge to a periodic orbit instead of the optimum on a smooth, strongly convex unconstrained problem.The example uses a one-dimensional objective and history parameter m = 1.Source: §4 · p. 9
  • A simple safeguarding check can be cheaper to execute than a line search.The section notes that the check often involves only a simple condition.Source: §4 · p. 10
  • The guard accepts an AA step only when it satisfies the sufficient-descent condition; otherwise, it selects the PGA step.This reuses function values more efficiently than comparing the AA and PGA objective values directly, which requires two evaluations per step.Source: §4 · p. 10
  • The resulting method admits PGA’s global convergence rate while retaining the potential for AA’s local adaptation and acceleration.The section describes the guard condition as sufficient for achieving the same convergence rate as PGA.Source: §4 · p. 10

5 Extension to Bregman proximal gradient methods

The section extends Anderson acceleration to Bregman proximal gradient methods by extrapolating dual-space iterates. This avoids primal feasibility issues, though general guarantees are difficult when the solution lies on the boundary of the kernel’s domain.

5 Extension to Bregman proximal gradient methods

  • BPG maps each iterate to dual space for a gradient step, then returns to primal space for the Bregman proximal step.The mirror map is ∇ϕ and its inverse is ∇ϕ∗.Source: §5 · p. 12
  • AA-BPG extrapolates a sequence in the dual space rather than the primal sequence, which is restricted to the constraint set, avoiding feasibility issues.The method applies AA to the BPG fixed-point mapping.Source: §5 · p. 12
  • When the dual iterates converge, Bregman proximal nonexpansiveness can relate their progress to the primal iterates, under conditions such as dom h ⊆ int dom ϕ.The passage says Dϕ(xk, x⋆) is bounded by Dϕ(∇ϕ∗(yk), ∇ϕ∗(y⋆)) in that setting.Source: §5 · p. 13
  • If the solution lies on the boundary of dom ϕ, ∇ϕ may be undefined there, making general AA-BPG guarantees difficult to derive.The section leaves a proof technique that goes beyond linearizing the mapping around the solution as future work.Source: §5 · p. 13
  • A stabilization policy analogous to AA-PGA retains BPG’s convergence rate.Source: §5 · p. 13

6 Numerical Experiments

Across constrained logistic regression, nonnegative least squares, and relative-entropy nonnegative regression, the experiments report substantial acceleration from Anderson acceleration; AA-BPG also converges linearly on a hard instance.

6.1 Constrained logistic regression

  • On four ill-conditioned data sets, AA consistently and dramatically improves iteration counts and wall-clock time over standard first-order methods.The guarded method alternates large objective-reducing AA steps with slower PGA steps that guide iterates through difficult regimes.Source: §6.1 · p. 14, Figure 3 · p. 15, Figure 4 · p. 15

6.2 Nonnegative least squares

  • For nonnegative least squares, AA offers significant acceleration and often achieves several orders of magnitude speed-up over popular first-order methods.In one plotted instance, AA appears to identify the solution in finite time, possibly because the optimum lies in the span of past iterates.Source: §6.2 · p. 16, Figure 5 · p. 16

6.3 Relative-entropy nonnegative regression

  • AA-BPG is fastest on both relative-entropy regression instances and achieves linear convergence even on the hard instance.The authors report that this local-strong-convexity adaptation appears consistently across the tested problems and data sets.Source: §6.3 · pp. 16, 18, Figure 7 · p. 17

7 Conclusion

The paper adapts Anderson acceleration to proximal and Bregman proximal gradient methods, combining global worst-case guarantees with potential local acceleration.

7 Conclusion

  • The proposed stabilization retains proximal gradient methods’ global convergence guarantees while adding the potential for local adaptation and acceleration.The conclusion highlights convergence guarantees for non-smooth mappings, infeasibility avoidance, and a simple guard step.Source: §7 · p. 18
  • The paper extends Anderson acceleration to non-Euclidean geometry through an application to the Bregman proximal gradient family.The conclusion presents this as an application of AA to non-Euclidean geometry.Source: §7 · p. 18
  • The authors conclude that Anderson acceleration merits further study because of its simplicity and practical promise.Source: §7 · p. 18

A Proof of Theorem 1

The proof establishes local convergence by bounding the iterates near a fixed point and controlling their residuals under the theorem’s assumptions.

A Proof of Theorem 1

  • The proof uses differentiability near the fixed point to represent the mapping by its Jacobian plus a vanishing local error.It chooses a neighborhood and contraction bounds using the Jacobian norm.Source: A Proof of Theorem 1 · p. 21
  • With a sufficiently close initialization, induction keeps the iterates inside the chosen neighborhood for the indices used by Anderson acceleration.The argument uses the local bounds and the fixed memory limit m.Source: A Proof of Theorem 1 · p. 22
  • The proof bounds successive residuals and uses arbitrary error tolerances to complete the theorem’s convergence claims.The final step invokes the fact that a^(1/k) approaches 1 for any positive a.Source: A Proof of Theorem 1 · p. 23

B Proof of Proposition 1

For AA-GD with history parameter m = 1 and step size γ = 1/L, the proof constructs iterates that recur at +249 and −249, establishing nonconvergence for a stated initial interval.

B Proof of Proposition 1

  • Whenever consecutive iterates are both in [1, +∞), the next iterate is −249; when both are in (−∞, −1], it is +249.These sign-dependent transitions motivate the initial interval used to generate a nonconvergent sequence.Source: B Proof of Proposition 1 · p. 24
  • For x0,x1∈[1,+∞), x2=−249; under the additional condition x1∈[1,245], the iterates satisfy x3∈(−83,−1), x4=+249, x5∈(49.8,83), and x6=−249.Because x5∈(49.8,83)⊂[1,245], the argument repeats with x1 replaced by x5 and x2 by x6. The stated pattern implies AA-GD never converges to the optimal solution.Source: B Proof of Proposition 1 · p. 24
  • For x0 in [2.01, 246.98], a sufficient condition ensures x1 ∈ [1, 245]; the iterates recur at +249 and −249 every four steps, so AA-GD never converges to the optimum.Source: B Proof of Proposition 1 · pp. 24–25
  • The subsequence y_n=x4n+1 follows a contractive fixed-point map on [1, 245] and converges to its unique fixed point, +249.The proof also states that all four subsequences eventually converge.Source: B Proof of Proposition 1 · pp. 24–25

Related papers

Loading 1910.08590v2…