% ===================================================================== \section{Convergence: what it costs to get there}\label{sec:convergence} % ===================================================================== \Cref{sec:existence} showed that for convex problems the \emph{existence} of a minimizer is almost free. This section shows that \emph{convergence to} a minimizer is not. The main character is the plainest algorithm there is: gradient descent \eqref{eq:gd} with constant step $1/L$ on a convex $L$-smooth function. Every optimizer knows that it converges to a minimizer when one exists (in finite dimensions; weakly in Hilbert space), and that $f(x_k)-f^\ast\le LD^2/(2k)$ with $D=\dist(x_0,\argmin f)$. The contrast between these two statements is the subject of this section. The rate for $f(x_k)-f^\ast$ is \emph{uniform}: it depends only on $L$, $D$ and $k$. For the iterates themselves there is no rate depending only on $L$, $D$ and $\eps$, and, as we shall see, not even a computable one in general. The first three results below are known in substance. Their key constructions and arguments are due to Kohlenbach \cite{Kohlenbach2019Moduli}, to Kohlenbach, L\'opez-Acedo and Nicolae \cite{KohlenbachLopezAcedoNicolae2019} and to Neumann \cite{Neumann2015LMCS}, who work with moduli of regularity and with Picard and Krasnosel'ski\u{\i}--Mann iterations of firmly nonexpansive maps; the formulation as convergence theorems for gradient descent and anchored methods, and some of the reversals (for instance the one for the Tikhonov path), are ours. In one dimension firmly nonexpansive maps are \emph{exactly} the gradient-descent maps: $T\colon\R\to\R$ is firmly nonexpansive if and only if it is nondecreasing and $1$-Lipschitz, if and only if $T=I-\frac1Lf'$ for a convex $f$ with $L$-Lipschitz derivative. We restate these three results in the language of optimization because their meaning for optimization is the point of this paper, and we give short proofs, since the one-dimensional instance makes the mechanism transparent. \subsection{Gradient descent is arithmetical comprehension}\label{subsec:gd-aca} \begin{theorem}[Kohlenbach; Neumann]\label{thm:A} Over $\RCA$ the following are equivalent. \begin{enumerate}[label=\textup{(\arabic*)},nosep] \item $\ACA$. \item For every $d\ge1$, every convex $L$-smooth pair $(f,g)$ on $\R^d$ that has a minimizer, and every $x_0\in\R^d$, the gradient-descent sequence \eqref{eq:gd} converges. \item Statement \textup{(2)} for $d=1$. \item For every nondecreasing nonexpansive $T\colon\R\to\R$ that has a fixed point and every $x_0$, the Picard sequence $(T^k x_0)_k$ converges. \end{enumerate} Moreover, the limit problem $\GDL_d\colon(f,g,L,x_0)\mapsto\lim_kx_k$ satisfies $\GDL_d\seqv\lm$ for every $d\ge1$. \end{theorem} The reversal (3)$\Rightarrow$(1) is contained in Kohlenbach's proof that moduli of regularity require $\ACA$ \cite[proof of Theorem 4.4]{Kohlenbach2019Moduli}, which uses the map $\frac12(I+T)$ for the map $T$ below, that is, gradient descent on the same function with step $1/4$; the Weihrauch statement for Krasnosel'ski\u{\i} and Krasnosel'ski\u{\i}--Mann iterations on $[0,1]$ is \cite[Proposition 3.20 and Corollary 3.18]{Neumann2015LMCS}. The function that drives all the lower bounds in this section is \begin{equation}\label{eq:fy} f_y(x)=\sum_{s\ge0}2^{-s-1}\big((y_s-x)_+\big)^2+\big((x-1)_+\big)^2 , \end{equation} built from a nondecreasing sequence $(y_s)$ in $[0,1]$. It is convex and $C^1$ with $f_y'(x)=-\sum_s2^{-s}(y_s-x)_++2(x-1)_+$, which is $2$-Lipschitz, and $\argmin f_y=[\alpha,1]$ with $\alpha=\sup_sy_s$. All of $f_y$ is computable from the data, but the late data enter the gradient with weight $2^{-s}$: gradient descent feels a jump that occurs at stage $s$ only through a pull of order $2^{-s}$. This is why no computable rate can exist. \begin{proof} \emph{(1)$\Rightarrow$(2).} Work in $\ACA$. Fix a minimizer $z$. By \cref{lem:basic}(b) the distances $\norm{x_k-z}$ do not increase, so the sequence is bounded. By the Bolzano--Weierstrass theorem, which holds in $\ACA$ \cite[III.2]{Simpson2009SOSOA}, a subsequence $x_{k_i}$ converges to some $\bar x$. By \cref{lem:basic}(c), $f(x_k)\to f(z)$, so $f(\bar x)=f(z)$ by continuity and $\bar x$ is a minimizer. By \cref{lem:basic}(b) with $z=\bar x$, the distances $\norm{x_k-\bar x}$ do not increase and have $\liminf 0$, hence tend to $0$. \emph{(2)$\Rightarrow$(3)} is trivial. \emph{(3)$\Leftrightarrow$(4).} Adding the two lower inequalities of \eqref{eq:pair} at $(x,y)$ and $(y,x)$ shows that $g$ is nondecreasing, and adding the two upper ones shows that $g$ is $L$-Lipschitz; at a minimizer $z$, the upper inequality with $y=z-g(z)/L$ gives $g(z)=0$. So $T=I-g/L$ is nondecreasing and $1$-Lipschitz and fixes the minimizers. Conversely, given such a $T$, put $L=1$, $g=I-T$ and $f(x)=\int_0^xg$; then $f(y)-f(x)-g(x)(y-x)=\int_x^y(g(t)-g(x))\,dt\in[0,(y-x)^2/2]$, so $(f,g)$ is a convex $1$-smooth pair, and a fixed point of $T$ is a minimizer of $f$. Riemann integrals of Lipschitz functions exist in $\RCA$. \emph{(3)$\Rightarrow$(1).} Over $\RCA$, $\ACA$ is equivalent to the existence of the range of every one-to-one $h\colon\N\to\N$ \cite[Lemma III.1.3]{Simpson2009SOSOA}. Given $h$, let $y_s=\sum_{i\le s}2^{-h(i)-1}$, a nondecreasing sequence in $[0,1)$, and consider $f=f_y$ with $L=2$. The pair $(f,f')$ exists in $\RCA$ (the series converge uniformly on bounded sets with explicit moduli), and $1$ is a minimizer since $f\ge0=f(1)$. Let $x_k$ be the gradient-descent sequence from $x_0=0$, and $T=I-f'/2$, which is nondecreasing. By (3), $x_k\to x_\infty$. \begin{itemize}[nosep,leftmargin=1.5em] \item $Tx_\infty=x_\infty$ by continuity, so $f'(x_\infty)=0$, which forces $y_s\le x_\infty\le1$ for all $s$. \item If $Tz=z$ and $z\ge0$, then $x_k\le z$ for all $k$, by $\Pi^0_1$ induction: $x_0=0\le z$ and $x_{k+1}=Tx_k\le Tz=z$. \item Suppose $y_s\le x_\infty-\eps$ for all $s$. Then $z=x_\infty-\eps$ satisfies $z\ge y_0>0$ and $f'(z)=0$, so $Tz=z$, and the previous item gives $x_\infty\le x_\infty-\eps$, which is absurd. Hence $y_s\to x_\infty$. \end{itemize} Now $m\in\operatorname{ran}(h)$ if and only if $m\in\{h(0),\dots,h(n)\}$ for any $n$ with $x_\infty-y_n<2^{-m-1}$, because a later value $h(i)=m$ would add $2^{-m-1}$ to the sum. Such an $n$ is found by a $\Delta^0_1$ search (\cref{app:formal}), so $\operatorname{ran}(h)$ exists. \emph{Weihrauch.} $\GDL_d\slev\lm$ because the iterates are uniformly computable from the input and converge. Conversely, given a nondecreasing sequence $(y_s)$ in $[0,1]$, the function $f_y$ is uniformly computable and gradient descent from $0$ converges to $\sup_sy_s$ by the argument above. So the monotone convergence problem satisfies $\MCT\slev\GDL_1\slev\GDL_d$, and $\MCT\seqv\lm$ \cite[Fact 11.26]{BrattkaGherardiMarcone2012}. \end{proof} \begin{remark}[What the theorem says, and what it does not]\label{rem:A} \leavevmode \begin{enumerate}[nosep,label=(\alph*)] \item The constructed function has a whole interval $[\alpha,1]$ of minimizers. This is forced: if the minimizer is unique, the limit and a rate are computable (\cref{thm:B}). \item For a computable increasing sequence with non-computable supremum (a Specker sequence \cite{Specker1949}), the iterates have no computable rate of convergence, although $f(x_k)-f^\ast\le LD^2/(2k)$ and $\abs{f'(x_k)}\le2LD/(k-1)$ hold as always \cite[Remark 4.10]{KohlenbachLopezAcedoNicolae2019}, \cite[Corollary 3.19]{Neumann2015LMCS}. \Cref{fig:specker} shows what this looks like: after a late jump of the data, every standard certificate of near-optimality is tiny while the iterate is still far from its limit. \item The equivalence depends on the coding of real numbers. Freund, Pischke and Uftring \cite{FreundPischkeUftring2026Avoiding} code reals by Cauchy sequences \emph{without} a rate; in their setting $\RCA$ proves the monotone convergence theorem \cite[Corollary 7.6]{FreundPischkeUftring2026Avoiding}, and they discuss when iterates of continuous maps exist \cite[Corollary 7.15]{FreundPischkeUftring2026Avoiding}. We expect, but have not checked, that the one-dimensional case of (3) becomes provable in $\RCA$ in their coding. The equivalence with $\ACA$ is a statement about the existence of limits \emph{with} a modulus, which is what a numerical analyst would call ``knowing the limit''. \item The same proofs apply to the proximal point algorithm (which is gradient descent on the Moreau envelope), to Krasnosel'ski\u{\i}--Mann iterations of firmly nonexpansive maps, and to projected gradient methods. An earlier calibration of the same kind concerns linear averaging: the mean ergodic theorem for nonexpansive linear maps on Hilbert space is equivalent to $\ACA$ \cite[Theorem 14.1]{AvigadSimic2006}. \end{enumerate} \end{remark} \begin{figure}[t] \centering \includegraphics[width=\linewidth]{figs/specker_gd.pdf} \caption{Gradient descent on the function $f_y$ of \eqref{eq:fy} for data $y_s$ that start with a jump at stage $0$ and receive late jumps at stages $s=30,300,3000,30000$, computed in $80$-digit arithmetic (\cref{app:experiments}). (a)~The data $y_s$ (plotted against $s$) and the iterate $x_k$ (plotted against $k$). (b)~The value gap and the gradient obey the uniform bounds and are below $10^{-4}$ after the first step, yet the iterate stays at distance about $0.12$ from its limit: the jump at stage $30$ pulls with weight $2^{-30}$, and crossing it alone takes more than $10^9$ steps.} \label{fig:specker} \end{figure} \subsection{The selection principle}\label{subsec:selection} \Cref{thm:convex-rca,thm:A} look contradictory at first sight: a minimizer of a convex function is cheap to \emph{have} but expensive to \emph{reach}. The resolution is that a convergent algorithm does more than find a minimizer: it \emph{selects} one, namely its limit, as a function of the data. In the proof of \cref{thm:A}, gradient descent from $0$ selects the left end point $\alpha$ of $\argmin f_y=[\alpha,1]$, which is the projection of the starting point onto the solution set, and that end point carries the halting problem. Neumann proved the general form of this observation for fixed-point iterations on $[0,1]$: computing the projection of a point onto the fixed-point set of a nonexpansive map, computing the limit of a large class of iterations, and computing a rate of convergence for them, are all Weihrauch equivalent to $\lm$ \cite[Proposition 3.20]{Neumann2015LMCS}. Anchored methods make the selection explicit. They converge \emph{strongly}, even in Hilbert space, and their limit is the projection of the anchor $u$ onto the solution set: the Halpern iteration $x_{k+1}=\beta_{k+1}u+(1-\beta_{k+1})Tx_k$ with $\beta_k\to0$, $\sum_k\beta_k=\infty$ and $\sum_k\abs{\beta_{k+1}-\beta_k}<\infty$ (Wittmann's theorem \cite{Wittmann1992}), and Tikhonov regularization $x_\lambda=\argmin\{f+\frac\lambda2\norm{\cdot-u}^2\}$ as $\lambda\downarrow0$. \begin{theorem}[Selection; after Neumann]\label{thm:D} On the class of convex $2$-smooth functions on $\R$ with a minimizer, the following problems are strongly Weihrauch equivalent to $\lm$: given $f$ and $u$, find $P_{\argmin f}(u)$; find the limit of the Halpern iteration with $\beta_k=1/(k+1)$, anchor $u$ and starting point $x_0=u$ for $T=I-\frac12f'$; find $\lim_{\lambda\downarrow0}x_\lambda$, where $x_\lambda=\argmin\{f+\frac\lambda2(\cdot-u)^2\}$ is the Tikhonov path. Over $\RCA$, the convergence of either of the last two (for all such $f$ and $u$) implies $\ACA$. \end{theorem} \begin{proof} Use $f_y$ with $u=x_0=0$, so that $P_{\argmin f_y}(0)=\alpha=\sup_sy_s$. All three limits are $\alpha$, and the upper bounds are as in \cref{thm:A}; each point $x_\lambda$ of the Tikhonov path is the unique zero of the $\lambda$-strongly increasing function $h=f'+\lambda(I-u)$, which is found uniformly by trisection (since $h(m+\delta)-h(m-\delta)\ge2\lambda\delta$, one of the strict tests $h(m-\delta)<0$, $h(m+\delta)>0$ succeeds), so the path exists in $\RCA$. For the reverse-mathematical statement we cannot use the classical identification of the limit with $\alpha$, since $\alpha$ need not exist in $\RCA$; instead we repeat the comparison argument of \cref{thm:A}. For Halpern with $x_0=u=0$: if $Tz=z\ge0$ then $x_k\le z$ for all $k$, since $x_{k+1}=(1-\beta_{k+1})Tx_k\le(1-\beta_{k+1})z\le z$; and $\abs{x_{k+1}-Tx_k}\le\beta_{k+1}\abs{Tx_k}\to0$, so a limit $x_\infty$ is a fixed point. For Tikhonov: $f'+\lambda I$ is increasing and non-negative at every fixed point $z\ge0$ of $T$, so $0\le x_\lambda\le z\le1$; and $f'(x_\lambda)=-\lambda x_\lambda\to0$, so a limit $x_\infty$ satisfies $f'(x_\infty)=0$. In both cases the remaining two items in the proof of \cref{thm:A} go through unchanged. \end{proof} Together, \cref{thm:convex-rca,thm:A,thm:D} isolate the cost of convergence: it is the cost of the particular \emph{choice} an algorithm makes. A convergent method defines a map $(f,x_0)\mapsto\lim_kx_k$, which is a realizer of convex minimization. Finding \emph{some} minimizer is cheap: the multivalued problem $\CMin_1$ is equivalent to $\IVT$ (\cref{prop:cmin-weihrauch}), and on the hard family $f_y$ the constant choice $1$ is a minimizer. No single-valued realizer is as cheap as the problem itself (a single-valued map below $\Cch_{2^\N}$ is computable \cite{BrattkadeBrechtPauly2012}), and the realizers computed by gradient descent in dimension one and by anchored methods in every dimension select the projection of the starting point or of the anchor onto the solution set, which is as complex as the halting problem. (In dimension $d\ge2$ the limit of gradient descent need not be that projection, but the one-dimensional case already embeds.) This is principle P2 of the introduction, in the precise form that \cref{thm:A,thm:D} prove; whether every limit-computable realizer of convex minimization is $\lm$-hard is \cref{prob:realizers}. Kohlenbach's recent work on moduli of regularity, which shows how such moduli compute zeros and, for convex zero sets, the zero of minimal norm \cite{Kohlenbach2026EPTCS}, is closely related. \subsection{What restores computability: uniqueness and regularity}\label{subsec:regularity} There are two classical ways to remove the choice: make the minimizer unique, or make the distance to the solution set controlled by the objective. In proof mining these are the \emph{modulus of uniqueness} \cite{Kohlenbach1993Chebycheff} and the \emph{modulus of regularity} \cite{KohlenbachLopezAcedoNicolae2019}; in optimization they are strong convexity and error bounds (H\"older, \L{}ojasiewicz, Kurdyka--\L{}ojasiewicz, Hoffman). \begin{proposition}[Kohlenbach, L\'opez-Acedo, Nicolae; Kohlenbach]\label{thm:B} Let $(f,g)$ be a convex $L$-smooth pair on $\R^d$ with $S=\argmin f\neq\emptyset$, and $D=\dist(x_0,S)$. \begin{enumerate}[nosep,label=\textup{(\alph*)}] \item If $S=\{x^\ast\}$, then $x^\ast$ and a rate of convergence of \eqref{eq:gd} are computable from $(f,g,L,x_0)$, uniformly on the class of such instances. \item If $\rho$ is a modulus of regularity, i.e.\ $f(x)-f^\ast<\rho(\eps)$ implies $\dist(x,S)<\eps$ (a modulus of uniqueness when $S$ is a singleton), then $\norm{x_k-\lim_jx_j}<\eps$ for all $k>LD^2/(2\rho(\eps/2))$. \item Over $\RCA$, the existence of a modulus of regularity for every Lipschitz $F\colon[0,1]\to\R$ with a zero is equivalent to $\ACA$, while the mere regularity statement (without a modulus) is equivalent to $\WKL$; the modulus-of-regularity problem is Weihrauch equivalent to $\widehat\LPO\eqv\lm$ \cite[Fact 3.5]{BrattkaGherardiMarcone2012}, and the modulus-of-uniqueness problem is computable \cite{Kohlenbach2019Moduli}. (In $\RCA$ the existence of a modulus of uniqueness needs $\WKL$, as in \cref{subsec:uniqueness}: the compactness of $[0,1]$ costs $\WKL$ in $\RCA$, but is free for computable functions in the Weihrauch setting.) \end{enumerate} \end{proposition} \begin{proof} (a) If $S$ is bounded and nonempty, all sublevel sets of $f$ are bounded \cite[Corollary 8.7.1]{Rockafellar1970}. Search for a rational $R$ with $\min\{f(y):\norm{y-x_0}=R\}>f(x_0)$; the condition is $\Sigma^0_1$ and some $R$ satisfies it, and by convexity $\{f\le f(x_0)\}\subseteq\bar B(x_0,R)$. On this ball $x^\ast$ is the unique point of a co-c.e.\ closed set, hence computable \cite[Corollary 8.9]{BrattkaGherardi2011BSL}. A rate is $\eps\mapsto$ the first $n$ found with $\norm{x_n-x^\ast}<\eps$; it is valid for all $k\ge n$ because $\norm{x_k-x^\ast}$ does not increase. (b) is \cite[Theorem 4.1]{KohlenbachLopezAcedoNicolae2019} with the rate $f(x_k)-f^\ast\le LD^2/(2k)$ of \cref{lem:basic}(c): once $\dist(x_k,S)<\eps/2$, Fej\'er monotonicity gives $\norm{x_m-P_Sx_k}\le\dist(x_k,S)$ for all $m\ge k$, hence $\norm{x_k-x_\infty}\le2\dist(x_k,S)<\eps$. \end{proof} Three comments place this in the optimization landscape. First, the rate in (a) is computable but not bounded in terms of $L$, $D$ and $\eps$ alone: $f(x)=\mu x^2/2$ shows that no bound in terms of $L$, $D$ and $\eps$ alone exists. Uniform bounds are exactly what moduli provide: strong convexity with constant $\mu$ is a modulus of uniqueness $\delta(\eps)=\mu\eps^2/2$; a H\"older error bound $f-f^\ast\ge c\dist(\cdot,S)^p$ is a modulus of regularity $\rho(\eps)=c\eps^p$; for least squares, Hoffman's bound \cite{Hoffman1952} gives $p=2$. Kohlenbach, L\'opez-Acedo and Nicolae show that weak sharp minima, metric subregularity and error bounds are all instances \cite[Section 3]{KohlenbachLopezAcedoNicolae2019}. Second, uniqueness is not \emph{necessary} for computability of a given instance (a solution interval with rational end points gives computable limits); the precise statements are the uniform ones in (a) and (c), and the existential ones in \cref{rem:A}(b). Third, o-minimal geometry explains why regularity is common in practice. Definable (for instance semialgebraic) functions satisfy the Kurdyka--\L{}ojasiewicz inequality \cite{Kurdyka1998,BolteDaniilidisLewis2007}, which is a modulus of regularity in disguise, and this is the basis of the convergence theory of descent methods for tame problems \cite{AttouchBolteSvaiter2013}. Model theory thus guarantees, for a large class of problems, the \emph{existence} of exactly the datum that \cref{thm:B}(c) shows to be non-computable in general. It does not make the datum computable from the data: on the tame family $f_c(x)=\frac c2x^2$, $c\in[0,1]$, with $L=1$ and $x_0=1$, the limit is $0$ for $c>0$ and $1$ for $c=0$, so even here the limit operator computes $\LPO$. \subsection{Between convergence and rates: fluctuations and metastability}\label{subsec:fluct} When no rate of convergence exists, proof mining asks for weaker, finitary information \cite{Tao2008ETDS,AvigadRute2015,KohlenbachSafarik2014}. A sequence $(x_k)$ has \emph{$N$ $\eps$-fluctuations} if there are $i_10$ and every $F\colon\N\to\N$ there is $n\le\Phi(\eps,F)$ with $\norm{x_i-x_j}<\eps$ for all $i,j\in[n,n+F(n)]$. Metastability is the Kreisel no-counterexample interpretation of the Cauchy property, and by Kohlenbach's metatheorems it can be extracted from proofs of convergence. A bound on the number of fluctuations is stronger: it yields a rate of metastability, and it makes the limit \emph{learnable with a bounded number of mind changes}. For Fej\'er monotone sequences in totally bounded spaces, which include gradient descent and the proximal point algorithm in $\R^d$, Kohlenbach, Leu\c{s}tean and Nicolae extracted rates of metastability and bounds on mind changes governed by the modulus of total boundedness; for plain Fej\'er monotonicity in a ball of radius $b$ in $\R^d$ the number of mind changes is of order $(8\sqrt d\,b/\eps)^d$ \cite[Theorem 5.1 and Example 2.8]{KohlenbachLeusteanNicolae2018}. The structure of gradient descent gives a bound that is linear in $D/\eps$. Since the constant $C_d$ below may itself grow exponentially in $d$, the honest gain is that the degree in $D/\eps$ drops from $d$ to $1$; for $D/\eps$ small compared with $d$ the generic bound can be better. Throughout, $C_d$ denotes the constant in the length bound for self-contracted curves recalled below; it depends only on $d$, and for gradient descent with step $1/L$ an explicit admissible value can be read off from the path-length bound of Gupta, Balakrishnan and Ramdas \cite{GuptaBalakrishnanRamdas2021}, which is of order $2^{O(d^2)}$. The key fact is geometric. \begin{lemma}[Self-contraction \cite{GuptaBalakrishnanRamdas2021,BohmDaniilidis2022Ubiquitous}]\label{lem:selfcontracted} Let $f$ be convex and $L$-smooth on a Hilbert space and $x_{k+1}=x_k-t_k\nabla f(x_k)$ with $00$, $(x_k)$ has at most $2C_dD/\eps$ $\eps$-fluctuations. \item $\Phi(\eps,F)=\iter{\tilde F}{N}(0)$, with $\tilde F(n)=n+F(n)$ and $N=\lfloor2C_dD/\eps\rfloor$, is a rate of metastability; it depends on $f$, $L$ and $x_0$ only through $D$. \item There is no dimension-free bound: no function $B\colon(0,\infty)\to\N$ satisfies, for all $d$, all convex $1$-smooth $f$ on $\R^d$ with a minimizer $z$, all $x_0$ and all $\eps>0$, that \eqref{eq:gd} has at most $B(\norm{x_0-z}/\eps)$ $\eps$-fluctuations. Likewise, no rate of metastability depends only on $\norm{x_0-z}$, $\eps$ and $F$. \end{enumerate} \end{proposition} \begin{proof} (a) By Fej\'er monotonicity every $x_k$ lies in $\bar B(z,D)$ for $z=P_{\argmin f}(x_0)$, so the orbit has diameter at most $2D$, and by \cref{lem:selfcontracted} and \cite{DaniilidisDavidDurandCartagenaLemenant2015} its length is at most $2C_dD$. If $i_10$, infinitely many $\eps$-fluctuations. If $B$ existed, choose $K$ so large that $x_0,\dots,x_K$ contain $B(\norm{x_0}/\eps)+1$ of them. By \cref{lem:reflection} with $z=0$, these are also the first $K+1$ iterates of gradient descent for a convex $1$-smooth function on a space of dimension at most $K+2$ with minimizer $0$, a contradiction. For metastability, suppose $\Phi(\eps,F,b)$ were a dimension-free rate, valid whenever $\norm{x_0-z}\le b$. For every $\eps$ and $F$, reflect the first $K=\Phi+\max_{n\le\Phi}F(n)$ iterates of the $\ell^2$ sequence; this shows that $\Phi$ is a rate of metastability for the $\ell^2$ sequence itself, which is therefore Cauchy, a contradiction. \end{proof} That gradient descent in $\ell^2$ can fail to converge in norm, and hence admits no fluctuation bound there, follows from \cite{BauschkeMatouskovaReich2004Projection} and the proof of \cite[Proposition 4.4]{BohmDaniilidis2022Ubiquitous}; it is also known that self-contracted curves in Hilbert space can have infinite length \cite{StepanovTeplitskaya2017}; the restriction to the span of the iterates is the standard device of performance estimation \cite{TaylorHendrickxGlineur2017}. \Cref{thm:E}(c) combines them into a finite-dimensional, quantitative statement: the constant $C_d$ in (a) must tend to infinity, and so must any rate of metastability. An explicit family shows how the number of fluctuations grows with the dimension. \begin{proposition}[Staircase]\label{prop:staircase} For every $d\ge1$ and $\eps>0$ there are a separable convex $1$-smooth function on $\R^d$ with unique minimizer $0$ and a point $x_0$ with $\norm{x_0}=2\sqrt d\,\eps$ such that gradient descent has at least $d$ $\eps$-fluctuations. Consequently $C_d\ge\sqrt d/2$. \end{proposition} \begin{proof} Let $a=2\eps$, $s_i=a2^{-i}$ and $f(x)=\sum_{i=1}^dh_{s_i}(x_i)$, where $h_s$ is the Huber function with $h_s'(t)=\max(-s,\min(s,t))$. From $x_0=(a,\dots,a)$, gradient descent moves coordinate $i$ by $s_i$ per step and reaches $0$ exactly at step $T_i=2^i$. During the steps $k\in[T_{i-1},T_i]$ (with $T_0=2^0=1$) only the coordinates $j\ge i$ move, each by $a2^{i-1-j}$, so $\norm{x_{T_{i-1}}-x_{T_i}}^2=a^2\sum_{j=i}^d4^{i-1-j}\ge a^2/4$. The $d$ consecutive windows give $d$ $\eps$-fluctuations. Since all coordinates decrease monotonically, the orbit has diameter exactly $\norm{x_0}=2\sqrt d\,\eps$, so its length is at least $d\eps$ and at most $C_d\cdot2\sqrt d\,\eps$; hence $C_d\ge\sqrt d/2$. \end{proof} The lower bound $C_d\gtrsim\sqrt d$ matches the known lower bound for path lengths of gradient descent; the best known upper bounds are of the form $2^{O(d\log d)}$ for gradient flow and for gradient descent with steps of order $1/(L\sqrt d)$, and $2^{O(d^2)}$ for step $1/L$ \cite{GuptaBalakrishnanRamdas2021}. The gap is part of \cref{prob:threshold}. \Cref{lem:reflection} is the device behind performance estimation problems \cite{DroriTeboulle2014,TaylorHendrickxGlineur2017}: the first $K$ steps of a first-order method see only a $(K+2)$-dimensional space. \Cref{thm:E} thus makes precise, for gradient descent, a phenomenon that the proof-mining metatheorems explain in general terms (\cref{subsec:logical-form}): bounds extracted from proofs that do not use compactness of the ambient space are dimension-free, and bounds from proofs that do use it (the Bolzano--Weierstrass step in \cref{thm:A}, or the length of self-contracted curves) depend on the dimension, here necessarily. The Halpern iteration, by contrast, converges strongly in Hilbert space by a proof that uses no norm compactness of the space (only weak sequential compactness or projections, which are available uniformly in every Hilbert space), and accordingly it has dimension-free rates of metastability \cite{Kohlenbach2011AdvMath,KohlenbachLeustean2012AdvMath}. \input{convergence_limits}