Rate of metastability of an iterative algorithm for quadratic optimization
Paulo Firmino · 2025
Read Rate of metastability of an iterative algorithm for quadratic optimization by Paulo Firmino (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-2506-11342.txt.
Introduction
Paulo Firmino mines a convergence proof for the numbers it hides. His 2025 paper takes a theorem by Xu, that a certain iteration settles strongly onto the solution of a classic quadratic optimization problem, and asks how fast, in a precise proof-theoretic sense. Proof mining extracts quantitative bounds from arguments that seem to give none.
The analysis yields rates of metastability, a weakened but computable form of convergence rate, plus rates of asymptotic regularity for the iterates. For particular sequences the regularity rate comes out quadratic. Such translations matter when an algorithm's guarantee must be a number an engineer can use, not only a limit a theorist can cite.
Catalog record
| CREATOR | Paulo Firmino |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-11342
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rate of metastability of an iterative algorithm for quadratic optimization Paulo Firmino Abstract In this paper, relying on methods from proof mining, we provide a quantitative analysis of a theorem due to Xu [ 20 ] , stating that an iteration strongly converges to the solution of a well known quadratic optimization problem. Rates of metastability and some rates of asymptotic regularity were obtained. We get quadratic rates of asymptotic regularity for particular sequences. † Department of Mathematics, Faculdade de Ciências da Universidade de Lisboa Center for Mathematical Studies, Universidade de Lisboa Campo Grande 016, 1749-016 Lisboa, Portugal E-mail: [email protected] Keywords: Proof Mining, Quadratic Optimization, Nonexpansive mappings, Iterative procedures, Metastability MSC: 03F10, 47H09, 47J25, 47N10 1 Introduction Let H be a real Hilbert space and l\in\mathbb{N} . Xu [ 20 ] considered the well known quadratic optimization problem: \displaystyle\mathrm{(P)}\quad\min_{x\in F}\frac{1}{2}\langle Ax,x\rangle-\langle x,u\rangle (1) where u\in H , A is a strongly positive self-adjoint bounded linear operator and F is the set of common fixed points of T_{0},\ldots,T_{l-1} , a family of nonexpansive mappings on H . Xu would proceed with an iterative approach, defining the following iteration: x_{n+1}=(I-\alpha_{n+1}A)T_{n+1}x_{n}+\alpha_{n+1}u where (\alpha_{n})\subset(0,1] and we define T_{n} for n\geq l as T_{n\bmod l} . Xu proved the following strong convergence result Theorem 1 . [ 20 ] Assume the following hold: 1. \lim_{n}\alpha_{n}=0 and \sum_{n=0}^{+\infty}\alpha_{n}=+\infty , 2. \lim_{n}\frac{\alpha_{n}}{\alpha_{n+l}}=1 or \sum_{n=0}^{+\infty}|\alpha_{n}-\alpha_{n+l}|<+\infty , 3. F=\Fix(T_{l-1}\cdots T_{1}T_{0})=\Fix(T_{0}T_{l-1}\cdots T_{1})=\ldots=\Fix(T_{l-2}\cdots T_{0}T_{l-1}) . Then (x_{n}) converges strongly to the unique solution x^{*} of Problem (P). Our goal is to present a quantitative analysis of Xu’s result and obtain rates of metastability. This form of quantitative analysis of mathematical results emerged from the research program of proof mining [ 11 , 13 , 14 ] , which consists in analysing mathematical proofs using proof-theoretic tools (namely, functional interpretations) with the objective of obtaining additional computational information. Theorems regarding convergence of sequences, as this is the case, are a common interest in proof mining. In such cases, the goal is to obtain quantitative information in the form of rates of metastability and rates of asymptotic regularity. A sequence (x_{n}) is said to be metastable if \forall k\in\mathbb{N}\forall f\in\mathbb{N}^{\mathbb{N}}\exists n\forall i,j\in[n,f(n)]\left(\|x_{i}-x_{j}\|\leq\frac{1}{k+1}\right) A metastability rate consists of a bound \phi(k,f) on n . Metastability is equivalent to the Cauchy property. This equivalence is ineffective. While Cauchy rates (or convergence rates) cannot be extracted in general, metastability rates can, depending on the principles used by the proof. Körnlein [ 15 , 16 ] had obtained rates of metastability of an iteration due to Yamada [ 21 ] regarding a class of variational problems. We show a different approach, and our interest is to focus on the particular case of (P), analysing Xu’s proof of Theorem 1 . We note that, if \|A\|<2 , Xu’s iteration is a particular case of Yamada’s iteration. Xu’s proofs of Theorem 1 involve sequential weak compactness arguments. In this paper we apply the method developed by Ferreira, Leuştean and Pinto [ 7 ] guided by the bounded functional interpretation [ 8 ] for circumventing such arguments and we compute rates of metastability for Xu’s iteration. We obtain rates of (\tilde{T}_{n}) -asymptotic regularity, where \tilde{T}_{i}:=T_{i+l}\cdots T_{i+1} for i\in\mathbb{N} , and common rates of T_{i} -asymptotic regularity for all i . Quadratic rates of (\tilde{T}_{n}) -asymptotic regularity for particular sequences were obtained. 2 Preliminaries and first results Let H be a real Hilbert space and let A be a self-adjoint bounded linear operator on H . More details on these operators can be found, for example, in [ 1 , 3 ] . Let us recall that A is strongly positive if there exists \gamma>0 such that for all x\in H : \langle Ax,x\rangle\geq\gamma\|x\|^{2} (2) The following lemma will be used in the sequel. For the sake of completeness, we prove it here. Lemma 1 . Let A be strongly positive. For any \alpha\in[0,\|A\|^{-1}] : \|I-\alpha A\|\leq 1-\alpha\gamma (3) Proof. We clearly have \|A\|>0 . We have that, given \alpha\in[0,\|A\|^{-1}] , for any x\in H : \langle(I-\alpha A)x,x\rangle=\|x\|^{2}-\alpha\langle Ax,x\rangle\geq\|x\|^{2}-\|A\|^{-1}\|A\|\|x\|^{2}=0 Thus \sup_{\|x\|=1}|\langle(I-\alpha A)x,x\rangle|=\sup_{\|x\|=1}\langle(I-\alpha A)x,x\rangle As \sup_{\|x\|=1}|\langle Ax,x\rangle|=\|A\| we have \|I-\alpha A\|=\sup_{\|x\|=1}\langle(I-\alpha A)x,x\rangle=\sup_{\|x\|=1}(\|x\|^{2}-\alpha\langle Ax,x\rangle)\leq 1-\alpha\gamma ∎ Furthermore, we shall use the following well known inequality in real Hilbert spaces: for all x,y\in H , \|x+y\|^{2}\leq\|x\|^{2}+2\langle y,x+y\rangle (4) 2.1 Quantitative definitions and lemmas Definition 1 . Let (x_{n}) be a sequence in H . 1. Let x\in H . We say \phi:\mathbb{N}\to\mathbb{N} is a rate of convergence of (x_{n}) (to x ) if \forall k\in\mathbb{N}\forall n\geq\phi(k)\left(\|x_{n}-x\|\leq\frac{1}{k+1}\right) 2. We say \phi:\mathbb{N}\to\mathbb{N} is a Cauchy modulus of (x_{n}) if \forall k\in\mathbb{N}\forall n,m\geq\phi(k)\left(\|x_{n}-x_{m}\|\leq\frac{1}{k+1}\right) 3. A function \phi:\mathbb{N}\times\mathbb{N}^{\mathbb{N}}\to\mathbb{N} is a rate of metastability of a sequence (x_{n})\subseteq H if \forall k\in\mathbb{N}\forall f\in\mathbb{N}^{\mathbb{N}}\exists n\leq\phi(k,f)\forall i,j\in[n,f(n)]\left(\|x_{i}-x_{j}\|\leq\frac{1}{k+1}\right) If (a_{n}) is a sequence of non-negative real numbers such that \sum_{n=0}^{+\infty}a_{n}=+\infty then \theta:\mathbb{N}\to\mathbb{N} is a rate of divergence of (a_{n}) if \sum_{n=0}^{\theta(k)}a_{n}\geq k for all k\in\mathbb{N} . Lemma 2 . Assume that a_{n}\leq 1 for all n\in\mathbb{N} and that \theta is a rate of divergence of (a_{n}) . Then \theta(k)\geq k-1 for all k\in\mathbb{N} . Proof. Assume that for some k\in\mathbb{N} , we have that \theta(k)<k-1 , hence \theta(k)\leq k-2 . Then \sum\limits_{i=0}^{\theta(k)}a_{i}\leq\sum\limits_{i=0}^{k-2}a_{i}\leq k-1<k , which is a contradiction. ∎ If (b_{n}) is a sequence of real numbers such that \limsup b_{n}\leq 0 , then \psi:\mathbb{N}\to\mathbb{N} is a \limsup -rate of (b_{n}) if \forall k\in\mathbb{N}\forall n\geq\psi(k)\left(b_{n}\leq\frac{1}{k+1}\right) 2.1.1 Xu’s Lemma In his paper [ 20 ] , Xu uses a lemma regarding the convergence of a sequence of non-negative real numbers. This result would become well known in fixed point theory and is often referred as Xu’s lemma. Proposition 1 (Xu’s Lemma) . [ 20 ] Let (a_{n}) be a sequence in [0,1] , (b_{n}) and (c_{n}) sequences of reals and (s_{n}) a sequence of nonnegative reals such that for all n\in\mathbb{N} , s_{n+1}\leq(1-a_{n})s_{n}+a_{n}b_{n}+c_{n} and \sum\limits_{n=0}^{\infty}a_{n}=+\infty,\ \limsup_{n}b_{n}\leq 0,\ \sum\limits_{n=0}^{\infty}c_{n}<+\infty . Then \lim_{n}s_{n}=0 . As a part of proof mining research, quantitative versions of this lemma were deduced (see [ 19 ] for an overview). In this paper, we use a version corresponding to the particular case of the lemma with (c_{n})\equiv 0 , whose proof can be found in [ 9 , Proposition 4] . Proposition 2 . Let (a_{n}) be a sequence in [0,1] , (b_{n}) a sequence of reals and (s_{n}) sequence of nonnegative reals such that for all n\in\mathbb{N} , s_{n+1}\leq(1-a_{n})s_{n}+a_{n}b_{n} (5) Assume that L\in\mathbb{N}^{*} is an upper bound on (s_{n}) , \sum\limits_{n=0}^{\infty}a_{n} diverges with rate of divergence \theta and \limsup_{n}b_{n}\leq 0 with \limsup -rate \psi . Then \lim_{n}s_{n}=0 with rate of convergence \Sigma_{0} defined by \Sigma_{0}(k)=\theta\left(\psi(2k+1)+\lceil\ln(2L(k+1))\rceil\right)+1. (6) The condition \sum\limits_{n=0}^{\infty}a_{n}=\infty is equivalent to \prod_{n=0}^{\infty}(1-a_{n})=0. As such, we may also consider this condition: \begin{gathered}{\rm A^{\prime}}:\mathbb{N}\times\mathbb{N}\to\mathbb{N}\text{ is a monotone function satisfying}\\ \forall k,m\in\mathbb{N}\,\left(\prod_{i=m}^{{\rm A^{\prime}}(m,k)}(1-a_{i})\leq\frac{1}{k+1}\right),\end{gathered} (7) implying that for each m\in\mathbb{N} , A^{\prime}(m,\cdot) is a rate of convergence towards zero for the sequence \left(\prod_{i=m}^{n}(1-a_{i})\right)_{n} . By saying that {\rm A^{\prime}} is monotone we mean that it is monotone in both variables, \forall k,k^{\prime},m,m^{\prime}\in\mathbb{N}\,\left(k\leq k^{\prime}\land m\leq m^{\prime}\to{\rm A^{\prime}}(m,k)\leq{\rm A^{\prime}}(m^{\prime},k^{\prime})\right). We have this quantitative result involving this condition. For the proof, follow [ 19 , Lemma 3.4] , replacing \varepsilon with \frac{1}{k+1} (see also [ 18 , Lemma 13] ). Lemma 3 . Let (s_{n}) be a bounded sequence of non-negative real numbers and D\in\mathbb{N}