Anderson acceleration of the proximal point method: the exact adaptive minimax, a spectral phase transition, and optimal safeguarding
arXiv:2607.24643
2026
Dynamics
2 ideas extracted · analyzed Aug 31, 2026
What the math gives to ML
This paper gives an exact minimax characterization of polynomial acceleration for firmly nonexpansive resolvent iterations, showing that arbitrary adaptive affine combinations cannot uniformly beat a residual rate of d_0/(K+1) after K oracle calls. The constructive upper bound is simple: averaging powers of the reflected resolvent yields a telescoping residual identity and is optimal on an explicit skew-adjoint hard instance. The transferable asset is a provably safe fallback accelerator for repeated fixed-point modules such as DEQs, proximal layers, learned denoisers, and monotone optimization layers. The spectral phase transition further suggests using aggressive polynomial filtering only when the local spectrum is separated from 1, while reverting to Fejer averaging near the critical scale.
Ideas from this paper
✗ Failed on benchmark
2026
Replace a slow sequence of resolvent or contractive fixed-point updates by a blockwise averaged-reflection extrapolation. The method computes reflected iterates R^j y_0, averages them with equal weights, and uses the result as the next macro-iterate. Unlike unconstrained Anderson acceleration, this construction has a uniform residual guarantee for every maximal monotone operator.
Useful8/10
Difficulty4/10
Novelty6/10
✗ Failed on benchmark
2026
Use the paper's sharp sK approximately equal to 1 phase transition to choose between conservative Fejer averaging and higher-order polynomial filtering. When the local fixed-point spectrum is separated from eigenvalue 1, use a Jackson-type filter; near the critical regime, use the safe Fejer filter instead of unrestricted Anderson extrapolation.
Useful7/10
Difficulty7/10
Novelty7/10