H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms

TaeHo Yoon [email protected], Ernest K. Ryu [email protected], Benjamin Grimmer [email protected] · 2025

Read H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms by TaeHo Yoon [email protected], Ernest K. Ryu [email protected], Benjamin Grimmer [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14915.txt.

Introduction

TaeHo Yoon, Ernest K. Ryu, and Benjamin Grimmer characterize every fixed-step algorithm that converges at the best possible rate for a broad problem class. The setting covers nonexpansive fixed-point problems, where a classic method due to Halpern, its dual, and in fact a whole family of methods all hit the same optimal speed. Until now that family had no complete description.

The authors encode each method as a lower triangular matrix of step choices and find special polynomial quantities, called H-invariants, that stay fixed across all optimal methods. Extra certificates mark exactly which matrices in that shared level set are optimal. The theory gives a fresh, complete map of optimal acceleration for first-order methods.

Catalog record

CREATORTaeHo Yoon [email protected], Ernest K. Ryu [email protected], Benjamin Grimmer [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE150 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14915

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms TaeHo Yoon [email protected], Ernest K. Ryu [email protected], Benjamin Grimmer [email protected] Abstract For nonexpansive fixed-point problems, Halpern’s method with optimal parameters, its so-called H-dual algorithm, and in fact, an infinite family of algorithms containing them, all exhibit the exactly minimax optimal convergence rates. In this work, we provide a characterization of the complete, exhaustive family of distinct algorithms using predetermined step-sizes, represented as lower triangular H-matrices, which attain the same optimal convergence rate. The characterization is based on polynomials in the entries of the H-matrix that we call H-invariants , whose values stay constant over all optimal H-matrices, together with H-certificates , of which nonnegativity precisely specifies the region of optimality within the common level set of H-invariants. The H-invariance theory we present offers a novel view of optimal acceleration in first-order optimization as a mathematical study of carefully selected invariants, certificates, and structures induced by them. 1 Introduction In optimization, finding a minimax optimal, or worst-case optimal, algorithm for a given problem class is a standard goal of optimizers. More formally, this goal can be stated as the meta-problem \displaystyle\underset{{\mathcal{A}}\in\mathfrak{A}}{\text{minimize}}\,\,\underset{{\mathcal{P}}\in\mathfrak{P}}{\text{maximize}}\,\,{\mathcal{M}}\left({\mathcal{A}},{\mathcal{P}};N\right) (1) where \mathfrak{A} denotes a class of algorithms (e.g. first, second, or zeroth-order deterministic algorithms, stochastic algorithms using mini-batching, randomized algorithms, etc.), \mathfrak{P} denotes a class of problems (e.g. smooth (strongly) convex minimization, nonsmooth nonconvex minimization, smooth convex-concave minimax optimization, nonexpansive fixed-point problems, etc.), N is the number of accesses to the computation oracle associated with the algorithm class and {\mathcal{M}} is a measure of the performance—error, which is the smaller the better—of an algorithm {\mathcal{A}} for solving {\mathcal{P}} using N oracle accesses. 16 formalized and popularized the idea of studying asymptotically optimal algorithms in the context of minimax optimality 1 1 1 They originally formulated the problem as finding \min\left\{N\,\middle|\,\exists{\mathcal{A}}\in\mathfrak{A}\text{ such that }{\mathcal{M}}({\mathcal{A}},{\mathcal{P}};N)\leq\epsilon\right\} , which is, in the end, equivalent to ( 1 ). . For example, for smooth convex minimization problems, the celebrated accelerated gradient method (AGM) of 18 achieves f(x_{N})-\min_{x}f(x)={\mathcal{O}}\left(N^{-2}\right) , which is optimal up to a constant for ( 1 ) among all deterministic first-order algorithms using the gradient oracle \nabla f(\cdot) . This type of result could be viewed as searching for an approximate solution {\mathcal{A}}\in\mathfrak{A} which solves ( 1 ). Over decades since then, numerous results of the same spirit have appeared in the literature, identifying up-to-constant optimal approximate solutions to ( 1 ). A recently active movement in the field, initiated by 3 ; 9 ; 24 , is to reformulate ( 1 ) into a finite-dimensional optimization problem, compute its numerical solution, and mathematically characterize an optimized solution {\mathcal{A}}_{\star} based on numerical insights. Following this process, 9 identified the optimized gradient method (OGM), which outperforms AGM by a factor \approx 2 , which was later proved to be an exact optimal solution to ( 1 ) for smooth convex minimization ( 5 ) . Taking inspiration from these results, subsequent works have discovered new exact optimal solutions to smooth strongly convex minimization ( 25 ; 2 ) , nonsmooth convex minimization ( 6 ) and composite convex minimization ( 8 ) . For nonexpansive fixed-point problems (equivalently, proximal setting for monotone inclusion problems), 22 first achieved accelerated {\mathcal{O}}(N^{-2}) convergence in squared fixed-point residual, which was later refined to the exact minimax optimal rate ( 14 ; 10 ; 19 ) . While these works represent a clear step toward resolving the meta-problem ( 1 ), they fall short of providing a mathematically complete answer. For nonsmooth convex minimization, there are distinct exact optimal {\mathcal{A}} ’s known ( 17 ; 6 ) , and for nonexpansive fixed-point problems, there are infinitely many exact optimal {\mathcal{A}} ( 29 ) . The discussion of whether known optimal algorithms for ( 1 ) for distinct setups comprise a complete set of solutions is either missing or has been answered in the negative ( 29 ) . To summarize the chronological development of problem ( 1 ) for the nonexpansive fixed-point setting, the literature has progressed through the following three stages: (i) obtaining approximate (up-to-constant optimal) algorithms ( 22 ) ; (ii) identifying an exact optimal algorithm ( 14 ; 10 ; 19 ) ; (iii) recognizing that the exact optimal algorithm is not unique ( 29 ) . The natural next step in this mathematical progression is therefore (iv) determining all exact optimal solutions—which is what we accomplish in this work. We present the complete set of all exact optimal algorithms for nonexpansive fixed-point problems using the notions of H-invariants and H-certificates, thereby demonstrating that a full resolution of ( 1 ) is indeed achievable. 2 Key concepts and main results We consider the fixed-point problems \displaystyle\begin{array}[]{cc}\underset{y\in\mathbb{R}^{d}}{\textrm{find}}&y={\mathbb{T}}(y)\end{array} where {\mathbb{T}}\colon\mathbb{R}^{d}\to\mathbb{R}^{d} is nonexpansive (1-Lipschitz): \left\|{\mathbb{T}}x-{\mathbb{T}}y\right\|\leq\left\|x-y\right\|,\quad\forall x,y\in\mathbb{R}^{d}. We measure an algorithm’s convergence via squared norm of the fixed-point residual, \left\|y-{\mathbb{T}}y\right\|^{2} . Complexity lower bound. There exists a lower bound, Theorem 1 , for deterministic first-order algorithms for solving ( 2 ). This result first considers the class of algorithms \mathfrak{A}_{\text{span}} satisfying the span condition \displaystyle y_{k+1}\in y_{k}+\mathrm{span}\left\{y_{0}-{\mathbb{T}}y_{0},\dots,y_{k}-{\mathbb{T}}y_{k}\right\} and then extends it to the class \mathfrak{A}_{\text{det}} of all deterministic first-order algorithms using the resisting oracle technique of 16 . Theorem 1 ( ( 19 ) ) . Let d\geq 2(N-1) , y_{0}\in\mathbb{R}^{d} and R>0 . For any deterministic first-order algorithm using N-1 operator evaluations, there exists a nonexpansive operator {\mathbb{T}}\colon\mathbb{R}^{d}\to\mathbb{R}^{d} with a fixed point y_{\star} such that \|y_{0}-y_{\star}\|=R , and \displaystyle\left\|y_{N-1}-{\mathbb{T}}y_{N-1}\right\|^{2}\geq\frac{4R^{2}}{N^{2}}=\frac{4\left\|y_{0}-y_{\star}\right\|^{2}}{N^{2}}. Following the formulation and notation of ( 1 ), this states that when \mathfrak{P} is the class of all nonexpansive fixed-point problems (represented by the tuple ({\mathbb{T}},y_{0}) ), \mathfrak{A}=\mathfrak{A}_{\text{det}} and {\mathcal{M}}({\mathcal{A}},{\mathbb{T}},y_{0};N)=\frac{\left\|y_{N-1}-{\mathbb{T}}y_{N-1}\right\|^{2}}{\left\|y_{0}-y_{\star}\right\|^{2}} , then for any {\mathcal{A}}\in\mathfrak{A} , we have \max_{({\mathbb{T}},y_{0})\in\mathfrak{P}}{\mathcal{M}}({\mathcal{A}},{\mathbb{T}},y_{0};N)\geq\frac{4}{N^{2}} . Here we use the convention of denoting the squared fixed-point residual norm for y_{N-1} as {\mathcal{M}}({\mathcal{A}},{\mathbb{T}},y_{0};N) because computing the fixed-point residual itself requires an additional access to the operator evaluation oracle. Optimal Halpern method exactly matches the lower bound. The lower bound of Theorem 1 is matched by the classical Halpern iteration ( 7 ) with optimized interpolation parameters, which we call the Optimal Halpern Method (OHM) : for k=0,1,2,\dots , \displaystyle y_{k+1}=\frac{1}{k+2}y_{0}+\frac{k+1}{k+2}{\mathbb{T}}y_{k}. (OHM) Theorem 2 ( ( 10 ; 14 ) ) . Suppose {\mathbb{T}}\colon\mathbb{R}^{d}\to\mathbb{R}^{d} is nonexpansive and y_{\star}\in\mathrm{Fix}\,{\mathbb{T}} (i.e., y_{\star}={\mathbb{T}}y_{\star} ). Then for any N=1,2,\dots , OHM exhibits the (exact optimal) rate \displaystyle\|y_{N-1}-{\mathbb{T}}y_{N-1}\|^{2}\leq\frac{4\|y_{0}-y_{\star}\|^{2}}{N^{2}}. (3) Again using the notation of ( 1 ), Theorem 2 states that \max_{({\mathbb{T}},y_{0})\in\mathfrak{P}}{\mathcal{M}}({\mathcal{A}},{\mathbb{T}},y_{0};N)\leq\frac{4}{N^{2}} . Combining this with Theorem 1 , we establish the equality, representing minimax optimality: \displaystyle\min_{{\mathcal{A}}\in\mathfrak{A}_{\text{det}}}\,\max_{({\mathbb{T}},y_{0})\in\mathfrak{P}}\,{\mathcal{M}}({\mathcal{A}},{\mathbb{T}},y_{0};N)=\frac{4}{N^{2}}. Class of H-matrix representable algorithms. OHM is a fixed step-size algorithm that admits a representation of the form \displaystyle y_{k+1}=y_{k}-\sum_{j=0}^{k}h_{k+1,j+1}\left(y_{j}-{\mathbb{T}}y_{j}\right) (4) with some predetermined h_{k+1,j+1}\in\mathbb{R} . When an algorithm with N-1 total iterations (operator evaluations of {\mathbb{T}} ) is expressible in the format ( 4 ), we say it is H-matrix representable , and define its H-matrix as the lower triangular matrix H\in\mathbb{R}^{(N-1)\times(N-1)} with \displaystyle(H)_{k,j}=\begin{cases}h_{k,j}&\text{if $j\leq k$}\\ 0&\text{otherwise.}\end{cases} For OHM , in particular, we have \displaystyle\begin{split}&\left(H_{\text{OHM}}\right)_{k,j}=\begin{cases}-\frac{j}{k(k+1)}&\text{if }j<k\\ \frac{k}{k+1}&\text{if }j=k.\end{cases}\end{split} We denote the class of H-matrix representable algorithms by \mathfrak{A}_{\text{H}} , so that we have \mathfrak{A}_{\text{H}}\subset\mathfrak{A}_{\text{span}}\subset\mathfrak{A}_{\text{det}} . Non-uniqueness of minimax optimal algorithms via H-dual. Interestingly, 29 showed that given a fixed N , a minimax optimal H-matrix representable algorithm satisfying ( 3 ) is not

Read the complete text