Anderson acceleration of the proximal point method: the exact adaptive minimax, a spectral phase transition, and optimal safeguarding
Provides fundamental limits and optimal algorithms for adaptive acceleration of proximal methods, with implications for optimization and monotone inclusion problems.
The paper derives exact minimax complexity bounds for adaptive acceleration of the proximal point method, showing that the optimal polynomial is the Fejér kernel and that a sharp phase transition occurs at spectral floor s ~ 1/K. It also proves that Anderson acceleration requires no safeguarding on linear problems but needs exactly two oracle evaluations per iteration on nonlinear problems.
\noindent We study residual-polynomial acceleration of the proximal point method (PPM) for maximal monotone inclusions, with Anderson acceleration (AA) as the prototypical adaptive scheme. We answer three questions exactly. (i)~The minimax complexity over all adaptive methods is precisely $d_0/(K+1)$ per $K$ resolvent evaluations. The upper bound is attained by the averaged-reflection estimator; the matching lower bound uses an explicit skew-adjoint instance with resolvent eigenvalues at the roots of $u^{K+1}=-1$ and $\csc^2$-distributed masses, on which every degree-$K$ polynomial method satisfies $\|r(y_K)\|\ge 1/(K+1)$. The optimal polynomial is uniquely the Fejér kernel, and the same instance certifies a per-step floor. (ii)~A sharp phase transition separates regimes: Jackson-kernel polynomials achieve $O(d_0/(K^2 s))$ when the spectral floor $s$ satisfies $sK\to\infty$, while at the critical scale $s\asymp 1/K$ the barrier is exactly $1/(K+1)$. The picture extends to normal operators and the nonlinear family $M=S+N_C$. (iii)~On linear problems AA-PPM needs no safeguarding; on nonlinear problems certification of the $O(1/k)$ envelope requires exactly two oracle evaluations per iteration, and this factor is optimal. We also correct and complete the theory for structured problems---affine, strongly monotone, piecewise-affine, and Hölderian growth---and confirm all predictions numerically.