Anderson acceleration of the proximal point method: the exact adaptive minimax, a spectral phase transition, and optimal safeguarding
\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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.24643
curl -X POST /api/v1/records/arxiv/2607.24643/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.24643/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'