A Converse to Banach's Fixed Point Theorem and its CLS Completeness

Introduction

Several widely used computational methods are fixed point iteration methods. These include gradient descent, the power iteration method, alternating optimization, the expectation-maximization algorithm, $k$-means clustering, and others. In several important applications, we have theoretical guarantees for the convergence of these methods. For example, convergence to a unique solution can be guaranteed when the method is explicitly, or can be related to, gradient descent on a convex function [BTN01, Nes13, BV04]. More broadly, convergence to a stationary point can be guaranteed when the method is, or can be related to, gradient descent; for some interesting recent work on the limit points of gradient descent, see [PP16, LSJR16] and their references.

Ultimately, all fixed point iteration methods aim at converging to a fixed point of their iteration map. For global convergence to a unique solution, it should also be the case that the fixed point of the iteration map is unique. It is, thus, unsurprising that another widely used approach for establishing convergence of these methods is by appealing to Banach’s fixed point theorem. To recall, consider an iteration map $x_{t+1}\leftarrow f(x_{t})$, where $f:{\cal D}\rightarrow{\cal D}$, and suppose that there is a distance metric $d$ such that $({\cal D},d)$ is a complete metric space and $f$ is contracting with respect to $d$, i.e. for some constant $c<1$, $d(f(x),f(y))\leq c\cdot d(x,y)$, for all $x,y\in{\cal D}$. Under this condition, Banach’s fixed point theorem guarantees that there is a unique fixed point $x^{*}=f(x^{*})$. Moreover, iterating $f$ is bound to converge to $x^{*}$. Specifically, the $t$-fold composition, $f^{[t]}$, of $f$ with itself satisfies: $d(f^{[t]}(x_{0}),x^{*})\leq c^{t}d(x_{0},x^{*})$, for any starting point $x_{0}$.

Given Banach’s theorem, if you established that your iteration method is contracting under some distance metric $d$, you would also have immediately proven that your method converges and that it may only converge to a unique point. Moreover, you can predict how many steps you need from any starting point $x_{0}$ to reach an approximate fixed point $x$ satisfying $d(f(x),x)<\epsilon$ for some accuracy $\epsilon$.Indeed, it can be easily shown that $d(f^{[t+1]}(x_{0}),f^{[t]}(x_{0}))\leq c^{t}d(x_{1},x_{0})$. So $t=\log_{1/c}{d(x_{1},x_{0})\over\epsilon}$ steps suffice. Alas, several widely used fixed point iteration methods are not generally contracting, or only contracting in a small neighborhood around their fixed points and not the entire domain where they are defined. At least, this is typically the case for the metric $d$ under which approximate fixed points, $d(f(x),x)<\epsilon$, are sought. There is also quite an important reason why they may not be contracting: several of these methods may in fact have multiple fixed points.

Given the above motivation, our goal in this paper is to investigate the extent to which Banach’s fixed point theorem is a universal analysis tool for establishing that a fixed point iteration method both converges and globally converges to a unique fixed point. More precisely, our question is the following: if an iterative map $x_{t+1}\leftarrow f(x_{t})$ for some $f:{\cal D}\rightarrow{\cal D}$ converges to a unique fixed point $x^{*}$ from any starting point, is there always a way to prove this using Banach’s fixed point theorem? Additionally, can we always use Banach’s fixed point theorem to compute how many iterations we would need to find an approximate fixed point $x$ of $f$ satisfying $d(x,f(x))<\epsilon$, for some distance metric $d$ and accuracy $\epsilon>0$?

We study this question from both a mathematical and a computational perspective. On the mathematical side, we show a strong converse of Banach’s fixed point theorem, saying the following: given an iterative map $x_{t+1}\leftarrow f(x_{t})$ for some $f:{\cal D}\rightarrow{\cal D}$, some distance metric $d$ on ${\cal D}$ such that $({\cal D},d)$ is a complete and proper metric space, and some accuracy $\epsilon>0$, if $f$ has a unique fixed point that the $f$-iteration converges to from any starting point, then for any constant $c\in(0,1)$, there exists a distance metric $d_{c}$ on $\cal D$ such that:

$d_{c}$ certifies uniqueness and convergence to the fixed point, by satisfying $d_{c}(f(x),f(y))\leq c\cdot d_{c}(x,y)$, for all $x,y\in{\cal D}$;

$d_{c}$ allows an analyst to predict how many iterations of $f$ would suffice to arrive at an approximate fixed point $x$ satisfying $d(x,f(x))<\epsilon$; notice in particular that we are interested in finding an approximate fixed point with respect to the original distance metric $d$ (and not the constructed one $d_{c}$).

Our converse theorem is formally stated as Theorem 1 in Section 3. In the same section we discuss its relationship to other known converses of Banach’s theorem known in the literature, in particular Bessaga’s and Meyers’s converse theorems. The improvement over these converses is that our constructed metric $d_{c}$ is such that it allows us to bound the number of steps requied to reach an approximate fixed point according to the metric of interest $d$ and not just $d_{c}$; namely Property 2 above holds. We discuss this further in Section 3.3. Section 3.2 provides a sketch of the proof, and the complete details can be found in Appendix B.

While the proof of Theorem 1 is non-constructive, it does imply that Banach’s fixed point theorem is a universal analysis tool for establishing global convergence of fixed point iteration methods to unique solutions. Namely, it implies that one can always find a witnessing metric. We illustrate this by studying an important such method: power iteration. The power iteration method is a widely-used and well-understood method for computing the eigenvalues and eigenvectors of a matrix. It is well known that if a matrix $A$ has a unique principal eigenvector, then the power method starting from a vector non-perpendicular to the principal eigenvector will converge to it. This is shown using a potential function argument, outlined above and in Appendix A.2, which also pins down the rate of convergence.

We close the circle by studying Banach’s fixed point theorem from a computational standpoint. Recent work of Daskalakis and Papadimitriou [DP11] has identified a complexity class, CLS, where finding a Banach fixed point lies. CLS, defined formally in Section 5, is a complexity class at the intersection of PLS [JPY88] and PPAD [Pap94]. Roughly speaking, PLS contains total problems whose existence of solutions is guaranteed by a potential function argument, while PPAD contains total problems whose existence of solutions is guaranteed by Brouwer’s fixed point theorem. Lots of interesting work has been done on both classes in the past two decades; for a small sample see e.g. [DGP09, CDT09, Rub16, FPT04, SV08, ER17, ABPW17] and their references. CLS, lying in the intersection of PLS and PPAD, contains comptutational problems whose existence of solutions is guaranteed by both a potential function and a fixed point argument.More precisely, it contains all problems reducible to Continuous LocalOpt, defined in Section 5, and which doesn’t necessarily capture the whole intersection of PPAD and PLS.

Unsurprisingly CLS contains several interesting problems, whose complexity is not known to lie in P, but which also are unlikely to be complete for PPAD or PLS. One of these problems is finding a Banach fixed point. Others include the P-matrix Linear Complementarity Problem, finding mixed Nash equilibria of network coordination and congestion games, computational problems related to finding KKT points, and solving Simple Stochastic Games; see [DP11] for precise definitions of these problems and for references. Moreover, recent work has provided cryptographic hardness results for CLS [HY17] based on obfuscation, extending work which proved cryptographic hardness results for PPAD [BPR15, RSS16, KNY17].

Ultimately, the definition of CLS was inspired by a vast range of total problems that could not be properly classified as complete in PPAD or PLS due to the nature of their totality arguments. However, no natural complete problem for this class has been identified, besides Continuous LocalOpt, through which the class was defined. By making our converse to Banach’s fixed point theorem constructive, we show that finding a Banach fixed point is CLS-complete. More precisely, in Section 5 we define problem Banach, whose input is a continuous function $f$ and a continuous metric $d$, and whose goal is to either output an approximate fixed point of $f$ or a violation of the contraction of $f$ with respect to $d$. In Theorem 2 we show that Banach is CLS-complete.It is worth pointing out that, while some problems in CLS (e.g. Banach fixed points, simple stochastic games) have unique solutions, most do not. Given that contraction maps have unique fixed points, the way we bypass the potential oxymoron, is by accepting as solutions violations of contraction.

We note that contemporaneously and independently from our work, Fearnley et al. [FGMS17] have also identified a CLS-complete problem related to Banach’s fixed point theorem. Their problem, called MetametricContraction, takes as input a function $f$ and a metametric $d$, and asks to find an approximate fixed point of $f$, or a violation of the contraction of $f$ with respect to $d$. In comparison to our CLS-completeness results, the CLS-hardness of Banach in our paper is stronger than that of MetametricContraction as the input to Banach is a metric. On the other hand, the containment of MetametricContraction into CLS is stronger than the containment of Banach, as Banach is polynomial-time reducible to MetametricContraction.

Notation and Preliminaries

In Appendix A.1, the reader can find some well-known definitions that we are going to use in the rest of the paper. More precisely in the field of:

Metric Spaces, we define the notion of: distance metric, metric space, diameter, bounded metric space, continuous function, open and closed sets in a metric space, compact set, locally compact metric space, proper metric space, open and closed balls, Cauchy sequence, complete metric space, equivalent metrics, continuity, Lipschitz continuity, contraction property, fixed point.

Because of its importance for the rest of the paper we also give here the definition of a distance metric and metric space.

$d(x,y)\geq 0$ for all $x,y\in\mathcal{D}$.

$d(x,y)=d(y,x)$ for all $x,y\in\mathcal{D}$.

$d(x,y)\leq d(x,z)+d(z,x)$ for all $x,y,z\in\mathcal{D}$. This is called triangle inequality.

Then we say that $d$ is a metric on $\mathcal{D}$, and $(\mathcal{D},d)$ is a metric space.

If a selfmap $f$ has a fixed point and is continuous, we can define the following sequence of points $x_{n+1}=f(x_{n})$ where the starting point $x_{0}$ can be picked arbitrarily. If $(x_{n})$ converges to a point $\bar{x}$ then

This observation implies that a candidate procedure for computing a fixed point of a selfmap $f$ is to iteratively apply the function $f$ starting from an arbitrary point $x_{0}$. If this procedure converges then the limit is a fixed point $x^{*}$ of $f$. We will refer to this method of computing fixed points as the Basic Iterative Procedure.

Arithmetic Circuits.

In Section 5 we work with functions from continuous domains to continuous domains represented as arithmetic circuits. An arithmetic circuit is defined by a directed acyclic graph (DAG). The inputs to the circuit are in-degree nodes, and the outputs are out-degree nodes. Each non-input node is a gate from the set $\{+,-,*,\max,\min,>\}$, performing an operation on the outputs of its in-neighbors. The meaning of the “$>$” gate is $>(x,y)=1$ if $x>y$ and otherwise. We also allow “output a rational constant” gates. These are gates without any inputs, which output a rational constant.

Converse Banach Fixed Point Theorems

We start, in Section 3.1, with an overview of known converses to Banach’s fixed point theorem. We also explain why these converses are not enough to prove that Banach’s fixed point theorem is a universal tool for analyzing the convergence of iterative algorithms. Then, in Section 3.2, we prove a stronger converse theorem that demonstrates the universality of Banach’s fixed point theorem for the analysis of iterative algorithms. Before beginning, we formally state Banach’s fixed Point Theorem. A useful survey of the applications of this theorem can be found in [Con14].

Suppose $d$ is a distance metric function such that $(\mathcal{D},d)$ is a complete metric space, and suppose that $f:\mathcal{D}\rightarrow\mathcal{D}$ is a contraction map according to $d$, i.e.

Then $f$ has a unique fixed point $x^{*}$ and the convergence rate of the Basic Iterative Procedure with respect to $d$ is $c$. That is, $d(f^{[n]}(x_{0}),x^{*})<c^{n}\cdot d(x_{0},x^{*})$, for all $x_{0}$.

The first known converse to Banach’s fixed point theorem is the following [Bes59].

The implication of the above theorem is that, if we want to prove existence and uniqueness of fixed points of $f^{[n]}$ for all $n$, then Banach’s fixed point theorem is a universal way to do it. Moreover, there is a potential function of the form $p(x)=d_{c}(x,f(x))$, where $d_{c}$ is a distance metric, that decreases under successive applications of $f$, and successive applications of $f$ starting from any point $x_{0}$ are bound to converge to the unique fixed point of $f$.

Unfortunately, $d_{c}$ cannot provide any information about the number of steps that the Basic Iterative Procedure needs before computing an approximate fixed point under some metric $d$ of interest. The reason is that, after $\log_{c}\varepsilon$ steps of the Basic Iterative Procedure, we only have $d_{c}(x_{n},f(x_{n}))\leq\varepsilon$. However, $d_{c}$ might not have any relation to $d$, hence an approximate fixed point under $d_{c}$ may not be one for $d$. So Bessaga’s theorem is not useful for bounding the running time of iterative methods for approximate fixed point computation.

Given the above discussion, it is reasonable to expect that a converse to Banach’s theorem that is useful for bounding the running time of approximate fixed point computation methods should take into account, besides the function $f$ and its domain $\mathcal{D}$, the distance metric $d$ under which we are interested in computing approximate fixed points. One step in this direction has already been made by Meyers [Mey67].

Let $(\mathcal{D},d)$ be a complete metric space, where $\mathcal{D}$ is compact, and suppose that $f:\mathcal{D}\rightarrow\mathcal{D}$ is continuous with respect to $d$. Suppose further that $f$ has a unique fixed point $x^{*}$, that the Basic Iterative Method converges to $x^{*}$ from any starting point, and that there exists an open neighborhood $U$ of $x^{*}$ such that $f^{[n]}(U)\rightarrow\{x^{*}\}$. Then, for any $c\in(0,1)$, there exists a distance metric $d_{c}$, which is topologically equivalent to $d$, such that $(\mathcal{D},d_{c})$ is a complete metric space and $f$ is a contraction map with respect to $d_{c}$ with contraction $c$.

Compared to Bessaga’s theorem, the improvement offered by Meyer’s Theorem is that, instead of the existence of an arbitrary metric, it proves the existence of a metric that is topologically equivalent to the metric $d$. However, this is still not enough to bound the number of steps needed by the Basic Iterative Procedure in order to arrive at a point $x_{n}$ such that $d(x_{n},f(x_{n}))\leq\varepsilon$. Our goal in the next section is to close this gap. We will also replace the compactness assumption with the assumption that $(\mathcal{D},d)$ is proper, so that the converse holds for unbounded spaces.

2 A New Converse to Banach’s Fixed Point Theorem

The main technical idea behind our converse to Banach’s fixed point theorem is to adapt the proof of Meyers’s theorem to get a distance metric $d_{c}$ with the property $d_{c}(x,y)\geq d(x,y)$ everywhere, except maybe for the region $d(x,x^{*})\leq\varepsilon$. This implies that, if we guarantee that $d_{c}(x_{n},x^{*})\leq\varepsilon$, then $d(x_{n},x^{*})\leq\varepsilon$.

Suppose $(\mathcal{D},d)$ is a complete, proper metric space, $f:\mathcal{D}\to\mathcal{D}$ is continuous with respect to $d$ and the following hold:

for every $x\in\mathcal{D}$, the sequence $(f^{[n]}(x))$ converges to $x^{*}$ with respect to $d$; moreover there exists an open neighborhood $U$ of $x^{*}$ such that $f^{[n]}(U)\to\{x^{*}\}$.

Then, for every $c\in(0,1)$ and $\varepsilon>0$, there exists a distance metric function $d_{c,\varepsilon}$ that is topologically equivalent to $d$ and is such that $(\mathcal{D},d_{c,\varepsilon})$ is a complete metric space and

The proof of our Theorem 1 adapts the construction of Meyers’s proof, to ensure that (2b) is satisfied. We give here a proof sketch postponing the complete details to Appendix B, where we repeat also all the technical details proven by Meyers [Mey67].

The construction of the metric $d_{c}$ follows is done in three steps:

Starting from the original metric $d$, a non-expanding closure of $d$ is defined as the metric $d_{M}(x,y)=\sup_{i\geq 0}d(f^{(i)}(x),f^{(i)}(y))$. This is topologically equivalent to $d$, but ensures that the images of any two points are at least as close in $d_{M}$ as the original two points (non-expanding property).

Notice that as $d_{M}(x,y)\geq d(x,y)$ for all points $x,y\in\mathcal{D}$, if we ensure that Property (2b) holds with respect to $d_{M}$ for the final constructed metric $d_{c,\varepsilon}$, it will also hold with respect to the original metric $d$.

Given $d_{M}$, the construction proceeds by defining a function $\rho_{c,\varepsilon}$ which satisfies (2a). This function achieves contraction by a constant $c<1$ by counting the number of steps required to reach an $\varepsilon$-ball close to the fixed point.

While for the original proof of Meyer any such $\varepsilon$-ball suffices, in order to guarantee Property (2b), our proof requires a set $S$ of points with small diameter with respect to $d$ such that performing an iteration of $f$ on any one of them results in a point still in the set $S$. We show that such a set always exists in Lemma 5 in Appendix B.

This guarantees that $\rho_{c,\varepsilon}(x,y)\geq d_{M}(x,y)$ if $\max\{d(x^{*},x),d(x^{*},y)\}\geq\varepsilon$, and therefore Property (2b) is preserved.

The function $\rho_{c,\varepsilon}$ satisfies all required properties other than triangle inequality and thus is not a metric. However, it can be converted into one.

Given $\rho_{c,\varepsilon}$, we construct the sought after metric $d_{c,\varepsilon}$ by taking it equal to the $\rho_{c,\varepsilon}$-geodesic distance (metric closure of $\rho_{c,\varepsilon}$). This directly converts $\rho_{c,\varepsilon}$ into a metric. We show that after this operation Properties (2a) and (2b). This is done in Lemma 9 and Lemma 10 in Appendix B.

3 Corollaries of Theorem 1

Property (2b) of the metric output by Theorem 1 has some interesting corollaries that we would not be able to get using the known converses to Banach’s theorem discussed in Section 3.1. The first one is that we can now compute, from $d_{c,\varepsilon}$, the number of iterations needed in order to get to within $\varepsilon$ of the fixed point $x^{*}$ of $f$ from any starting point $x_{0}\in\mathcal{D}$.

Under the assumptions of Theorem 1, starting from a point $x_{0}\in\mathcal{D}$, and for any constant $c\in(0,1)$, the Basic Iterative Procedure finds a point $x$ such that $d(x,x^{*})\leq\varepsilon$ after

iterations, where $d_{c,\varepsilon/2}$ is the metric guaranteed by Theorem 1.

In Corollary 1, for any given $\varepsilon$ of interest, we have to identify a different distance metric $d_{c,\varepsilon/2}$, guaranteed by Theorem 1, to bound the number of steps required by the Basic Iterative Procedure to get to within $\varepsilon$ from the fixed point. Sometimes we are interested in the explicit tradeoff between the number of steps required to get to the proximity of the fixed point and the amount of proximity $\varepsilon$. To find such a tradeoff we have to make additional assumptions on $f$. A mild assumption that is commonly satisfied by iterative procedures for non-convex problems is that the Basic Iterative Procedure locally converges to the fixed point $x^{*}$. That is, if $x_{0}$ is appropriately close to $x^{*}$, then the Basic Iterative Procedure converges. A common way of proving local convergence is to prove that $f$ is a contraction with respect to $d$ locally for $x,y\in\bar{B}(x^{*},\varepsilon)$. Theorem 1 provides a way to extend this local contraction property to the whole domain $\mathcal{D}$ and get an an explicit closed form of the tradeoff between the number of steps and $\varepsilon$, as implied by the following result.

Under the assumptions of Theorem 1, and the assumption that there exists $0<c<1$, $\delta>0$ such that

starting from any point $x_{0}\in\mathcal{D}$, the Basic Iterative Procedure finds a point $x$ such that $d(x,x^{*})\leq\varepsilon$ after

iterations, where $d_{c,\delta/2}$ is the metric guaranteed by Theorem 1.

Example: The Power Iteration as a Contraction Map

The results of the previous section imply that Banach’s fixed point theorem is a universal analysis tool for establishing global convergence of fixed point iteration methods to unique solutions. While the proof of Theorem 1 is non-constructive, it does imply that one can always find a witnessing metric under which the iterative map is contracting.

In this section, we illustrate this possibility by studying an important iterative method, the power iteration. The power iteration method is a widely-used and well-understood method for computing the eigenvalues and eigenvectors of a matrix. For a given matrix $A$, it is defined as:

It is well known that if a matrix $A$ has a unique principal eigenvector, then the power method starting from a vector non-perpendicular to the principal eigenvector will converge to it. This is shown using a potential function argument, presented in Appendix A.2, which also pins down the rate of convergence.

Our converse to Banach’s theorem, guarantees that, besides the potential function argument, there must also exist a distance metric under which the power iteration is a contraction map. To illustrate our theorem, we identify a new distance metric under which the power method is indeed contracting at the optimal rate.

Moreover, $t=\frac{\log(d(\bm{x}_{0},\bm{v}_{1})/\varepsilon)}{\log(\lambda_{1}/\lambda_{2})}$ iterations suffice to have $\left\|\bm{x}_{t}-\bm{v}_{1}\right\|_{2}\leq d(\bm{x}_{t},\bm{v}_{1})\leq\varepsilon$.

For any vector $\bm{x}$, it holds that $\langle A\bm{x},\bm{v}_{1}\rangle=\lambda_{1}\langle\bm{x},\bm{v}_{1}\rangle.$ We have that

where the inequality is true as the vector $\frac{\bm{x}}{\langle\bm{x},\bm{v}_{1}\rangle}-\frac{\bm{y}}{\langle\bm{y},\bm{v}_{1}\rangle}$ is perpendicular to the principal eigenvector $\bm{v}_{1}$. This shows that $f$ is contracting with respect to $d$ as required.

Using these observations and following the same approach as in Corollaries 1-2 we get the required bound on the number of iterations. ∎

Banach is Complete for CLS

As discussed in Section 1, the complexity class CLS was defined in [DP11] to capture problems in the intersection of PPAD and PLS, such as P-matrix LCP, mixed Nash equilibria of congestion and multi-player coordination games, finding KKT points, etc. It also contains computational variants of finding fixed points whose existence is guaranteed by Banach’s fixed point theorem. In this section, we close the circle by proposing two variants of Banach fixed point computation that are both CLS-complete. Our CLS completeness results are obtained by making our proof of Theorem 1 constructive. We start with a formal definition of CLS, which is defined in terms of the problem Continuous LocalOpt.

Continuous LocalOpt takes as input two functions $f:^{3}\to^{3}$, $p:^{3}\to$, both represented as arithmetic circuits, and two rational positive constants $\varepsilon$ and $\lambda$. The desired output is any of the following:

a point $x\in^{3}$ such that $p(f(x))\geq p(x)-\varepsilon$.

two points $x,x^{\prime}\in^{3}$ violating the $\lambda$-Lipschitz continuity of $f$, i.e. $|f(x)-f(x^{\prime})|_{1}>\lambda|x-x^{\prime}|_{1}$.

two points $x,x^{\prime}$ violating the $\lambda$-Lipschitz continuity of $p$, i.e. $|p(x)-p(x^{\prime})|>\lambda|x-x^{\prime}|_{1}$.

The class CLS is the set of search problems that can be reduced to Continuous LocalOpt.

The variant of Banach’s theorem that is known to belong to CLS is Contraction Map, defined as follows:

Contraction Map takes as input a function $f:^{3}\to^{3}$ represented as an arithmetic circuit and three rational positive constants $\varepsilon$, $\lambda$, $c<1$. The desired output is any of the following (where $d$ represents Euclidean distance):

a point $x\in^{3}$ such that $d(x,f(x))\leq\varepsilon$

two points $x,x^{\prime}\in^{3}$ disproving the contraction of $f$ w.r.t. $d$ with constant $c$, i.e. $d(f(x),f(x^{\prime}))>c\cdot d(x,x^{\prime})$

two points $x,x^{\prime}\in^{3}$ disproving the $\lambda$-Lipschitz continuity of $f$, i.e. $|f(x)-f(x^{\prime})|_{1}>\lambda|x-x^{\prime}|_{1}$.

Contraction Map targets fixed points whose existence is guaranteed by Banach’s fixed point theorem when $f$ is a contraction map with respect to the Euclidean distance. However, it doesn’t capture the full generality of Banach’s theorem, since the latter can be applied to any complete metric space. We thus define a more general problem, Banach that: (i) still lies inside CLS, (ii) captures the generality of Banach’s theorem, (iii) and in fact tightly captures the complexity of the class CLS, by being CLS-complete. This problem is defined as follows:

a point $x\in^{3}$ such that $d(x,f(x))\leq\varepsilon$

two points $x,x^{\prime}\in^{3}$ disproving the contraction of $f$ w.r.t. $d$ with constant $c$, i.e. $d(f(x),f(x^{\prime}))>c\cdot d(x,x^{\prime})$

two points $x,x^{\prime}\in^{3}$ disproving the $\lambda$-Lipschitz continuity of $f$, i.e. $|f(x)-f(x^{\prime})|_{1}>\lambda|x-x^{\prime}|_{1}$.

four points $x_{1},x_{2},y_{1},y_{2}\in^{3}$ with $x_{1}\neq x_{2}$ and $y_{1}\neq y_{2}$ disproving the $\lambda$-Lipschitz continuity of $d(\cdot,\cdot)$, i.e. $|d(x_{1},x_{2})-d(y_{1},y_{2})|>\lambda\left(\left|x_{1}-y_{1}\right|_{1}+\left|x_{2}-y_{2}\right|_{1}\right)$.

We remark that Banach is tightly related to Contraction Map defined above, with the following differences. First, instead of Euclidean distance, the metric with respect to which $f$ is purportedly contacting is provided as part of the input and it is promised to be a metric. Second, we need to add an extra type of accepted solution (Od), which is a violation of the Lipschitz property of that metric. This is necessary to guarantee that the above problem has a solution of polynomial length for any possible input, and in particular is needed to place the above problem in CLS. (It is not needed for the CLS-hardness.)

We give here a sketch of the proof of Theorem 2 and we present the full proof in Appendix C.

Since the inclusion to CLS is a simple argument very similar to the argument from [DP11] that shows that Contraction Map belongs to CLS, we focus here on the hardness proof.

The inspiration of this proof is to make the proof of Theorem 1 constructive in polynomial time. We therefore follow the steps of the proof sketch of Theorem 1 as presented in Section 3.

Step I. Since we don’t have the strong requirement of Theorem 1 to output a metric that is topologically equivalent with some given metric we can use in place of $d_{M}$ any metric $d^{\prime}$ such that $f$ is non-expanding with respec to $d^{\prime}$. Hence we can easily observe that the discrete metric can be used as $d_{M}$.

Step II. The construction of Theorem 1 uses in the definition of $d(x,y)$ the number of times $n(x)$, that we have to apply $f$ on $x$ in order for $f^{[n(x)]}(x)$ to come $\varepsilon$-close to the fixed point $x^{*}$ of $f$. Of course $n(x)$ is not a quantity that can be computed in polynomial time. Instead we show that it suffices to use an upper bound on $n(x)$ which we can get using the potential function, namely $p(x)/\varepsilon$. Of course the operations that we are allowed to use to describe $d$ as an arithmetic circuit are limited and this step appears to need more expressive power that the simple arithmetic operations that we are allowed to use. We give a careful construction that bypasses these difficulties and completes this step of the proof.

Steps III. This step of Theorem 1 is highly non-constructive and hence we cannot hope to replicate it in polynomial time. But we prove that our carefully designed metric already has the triangle inequality and hence the transitive closure step is not necessary.

Acknowledgements

The authors were supported by NSF CCF-1551875, CCF-1617730, CCF-1650733, and a Simons Graduate Research Fellowship.

References

Appendix A Preliminaries

Let $\mathcal{D}$ be a set and $\tau$ a collection of subsets of $\mathcal{D}$ with the following properties.

The empty set $\emptyset\in\tau$ and the space $\mathcal{D}\in\tau$.

If $U_{a}\in\tau$ for all $a\in A$ then $\bigcup_{a\in A}Ua\in\tau$.

Then we say that $\tau$ is a topology on $\mathcal{D}$ and that $(\mathcal{D},\tau)$ is a topological space. We call open sets the members of $\tau$. Also a subset $C$ of $\mathcal{D}$ is called closed if $\mathcal{D}\setminus C$ is an open set, i.e. belongs to $\tau$. Let $(\mathcal{D},\tau)$ be a topological space and $A$ a subset of $\mathcal{D}$. We write

Metric Spaces

The diameter of a set $W\subseteq\mathcal{D}$ according to the metric $d$ is defined as

then $d_{S}$ is called the discrete metric on $\mathcal{D}$.

Remark.

It is very easy to see that discrete metric is indeed a metric, i.e. it satisfies the conditions (i)-(iv).

Let $(\mathcal{D},d)$ and $(\mathcal{X},d^{\prime})$ be metric spaces. A function $f:\mathcal{D}\to\mathcal{X}$ is called continuous if, given $x\in\mathcal{D}$ and $\varepsilon>0$, we can find a $\delta(x,\varepsilon)>0$ such that

We say that a subset $E\subseteq\mathcal{D}$ is open in $\mathcal{D}$ if, whenever $e\in E$, we can find a $\delta>0$ (depending on $e$) such that

The next lemma connects the definition of open sets according to some metric with the definition of open sets in a topological space.

If $(\mathcal{D},d)$ is a metric space, then the collection of open sets forms a topology.

We define the open ball of radius $r$ around $x$ to be $B(x,r)=\{y\in\mathcal{D}|d(x,y)<r\}$.

Closed Sets for Metric Spaces

then we say that $x_{n}\rightarrow x$ as $n\rightarrow\infty$ and that $x$ is the limit of the sequence $(x_{n})$. A set $G\subseteq\mathcal{D}$ is said to be closed if, whenever $x_{n}\in G$ and $x_{n}\rightarrow x$ then $x\in G$. A proof of the following lemma can be found in [Kör10].

We define the closed ball of radius $r$ around $x$ to be $\bar{B}(x,r)=\{y\in\mathcal{D}|d(x,y)\leq r\}$. A subset $G$ of a metric space $(\mathcal{D},d)$ is called compact if $G$ is closed and every sequence in $G$ has a convergent subsequence. A metric space $(\mathcal{D},d)$ is called compact if $\mathcal{D}$ is compact, locally compact if for any $x\in\mathcal{D}$, $x$ has a neighborhood that is compact and proper if every closed ball is compact.

Complete Metric Spaces

A metric space $(\mathcal{D},d)$ is complete if every Cauchy sequence converges.

Two metrics $d$, $d^{\prime}$ of the same set $\mathcal{D}$ are called topologically equivalent (or just equivalent) if for every sequence $(x_{n})$ in $\mathcal{D}$, $(x_{n})$ is $d$-Cauchy sequence if and only if it is $d^{\prime}$-Cauchy sequence.

Let $(\mathcal{D},d)$ be a metric spaces. A function $f:\mathcal{D}\to\mathcal{D}$ is called continuous with repect to $d$, if given $x\in\mathcal{D}$ and $\varepsilon>0$, we can find a $\delta(x,\varepsilon)$ such that

Lipschitz Continuity

If a function $f:\mathcal{D}\to\mathcal{X}$ is Lipschitz continuous then it is continuous.

A fixed point of a selfmap $f$ is any point $x^{*}\in\mathcal{D}$ such that $f(x^{*})=x^{*}$.

A.2 Introduction to Power Method

and since we assumed that $v_{0}$ is not perpendicular to $q_{1}$ we have that $c_{1}\neq 0$.

Since the eigenvalues are assumed to be real, distinct, and ordered by decreasing magnitude, it follows that

So, as $k$ increases, $A^{k}v_{0}$ approaches $c_{1}\lambda_{1}^{k}q_{1}$, and thus for large values,

The power iteration method is simple and elegant, but suffers some drawbacks. Except from a measure of initial conditions, the method returns a single eigenvector, corresponding to the eigenvalue of largest magnitude. In addition, convergence is only guaranteed if the eigenvalues are distinct—in particular, the two eigenvalues of largest absolute value must have distinct magnitudes. The rate of convergence primarily depends upon the ratio of these magnitudes, so if the two largest eigenvalues have similar sizes, then the convergence will be slow.

In spite of its drawbacks, the power method is still used in many applications, since it works well on large, sparse matrices when only a single eigenvector is needed. However, there are other methods overcoming some of the issues with the power iteration method.

Appendix B Proof of Theorem 1

The proof of Theorem 1, follows the construction of [Mey67]. We give a complete step by step description of this construction. For every step of this construction we explain what it was already proven by Meyers and we additionally prove some properties that are needed in order to satisfy our additional condition (2b).

There exists an open neighborhood $W$ of $x^{*}$ such that

Since $f^{[n]}(U)\rightarrow\{x^{*}\}$, there is an integer $k$ such that $f^{[k]}(U)\subseteq U$. Let

Then for any $x\in W$ and for any $1\leq j\leq k-1$ it holds that $x\in f^{[-j]}(U)$ and thus $f(x)\in f^{[-(j-1)]}(U)$. Moreover $x\in U$, so that $f^{[k]}(x)\in f^{[k]}(U)\subset U$ and thus $f(x)\in f^{[-(k-1)]}(U)$. Hence $x\in W$ implies $f(x)\in W$, which was to be shown. The diameter of $W$ can be bounded by the diameter of $U$ and hence is less that $\varepsilon$.

We now proceed to the main line of the proof. The construction follows three steps:

We first construct a metric $d_{M}$, which is topologically equivalent to $d$, and with respect to which $f$ is non-expanding. It also holds that $d_{M}(x,y)\geq d(x,y)$ for all $x,y\in\mathcal{D}$ and therefore Property (2b) can be transferred from $d_{M}$ to $d$.

Given $d_{M}$, we proceed to construct a “distance” function $\rho_{c,\varepsilon}$, which satisfies (2a) and all the metric properties except maybe for the triangle inequality. Moreover $\rho_{c,\varepsilon}$ satisfies that $\rho_{c,\varepsilon}(x,y)\geq d_{M}(x,y)$ if $\max\{d(x^{*},x),d(x^{*},y)\}\geq\varepsilon$, and therefore (2b) is preserved.

Given $\rho_{c,\varepsilon}$, we construct the sought after metric $d_{c,\varepsilon}$ by taking it equal to the $\rho_{c,\varepsilon}$-geodesic distance. Given the properties of $\rho_{c,\varepsilon}$ and the definition of $d_{c,\varepsilon}$, we can prove that $d_{c,\varepsilon}$ is a metric and Properties (2a) and (2b) hold.

In the fist step of the construction we define an metric $d_{M}$ as

and we show that $f$ is non-expanding with respect to $d_{M}$.

For the $d_{M}$ function defined above we have that:

$d_{M}$ is well defined and satisfies all the metric properties (see Definition 1).

$d_{M}$ is topologically equivalent with $d$.

The proof of Lemma 6 can be found in Section B.2 where for completeness we keep the proofs that were already proved by Meyers’s [Mey67].

For our purposes we also observe that by the definition of $d_{M}$ the following holds

and hence if $d_{M}(x,y)\leq\varepsilon$ then also $d(x,y)\leq\varepsilon$, therefore $d_{M}$ satisfies (2b).

For $x\in K_{0}\setminus\{x^{*}\}$ we set $n(x)=\max_{x\in K_{n}}\{n\}\geq 0$. The fact that $n(x)$ is finite is guaranteed by (4). To see this assume that there is an infinite sequence $n_{1},n_{2},\dots$ such that $x\in K_{n_{i}}$ which implies that $x\in\bigcap_{i=1}^{\infty}K_{i}$ which definitely contradicts (4). We define also $n(x^{*})=\infty$, and for $x\in\mathcal{D}\setminus K_{0}$ set $n(x)=-\min_{f^{[m]}(x)\in K_{0}}\{m\}=\max_{x\in K_{n}}\{n\}<0$ which again is finite because of condition 2. Let $\kappa(x,y)=\min\{n(x),n(y)\}$, we define $\rho_{c}$ to be

For the $\rho_{c}$ function defined above we have that:

$\rho_{c}$ is well defined and satisfies the metric properties (see Definition 1), except the triangle inequality (iv).

$f$ is a contraction map with respect to $\rho_{c}$ with contraction constant $c$.

The proof of Lemma 7 is almost immediate from the definition of $\rho_{c}$, but for a detailed explanation we refer to the initial proof by Meyers [Mey67].

In this last step what we do is that we assign the distance between two points to be the length of the shortest path that connects these two points, with the lengths computed according to $\rho_{c}$. Then the distance satisfies the triangle inequality because of the shortest path property.

Formally, denote by $S_{xy}$ the set of chains $s_{xy}=(x=x_{0},x_{1},\dots,x_{m}=y)$ from $x$ to $y$ with associated lengths $L_{c}(s_{xy})=\sum_{i=1}^{m}\rho_{c}(x_{i},x_{i-1})$. We define

For the $d_{c}$ function defined above we have that:

$d_{c}$ is well defined and satisfies all the metric properties (see Definition 1).

$f$ is a contraction map with respect to $d_{c}$ with contraction constant $c$.

$d_{c}$ is topologically equivalent with $d$ and hence $(\mathcal{D},d_{c})$ is a complete metric space.

The proof of Lemma 8 can be found in Section B.2.

We know need to prove two lemmas to prove that Meyers’s construction also satisfies (2b).

Consider any $x\neq x^{*}$ and $y\neq x,x^{*}$ and assume that $y\notin K_{0}$, then

Proof of Lemma 9: By definition any chain $s_{xy}$ either lies in $\mathcal{D}\setminus K_{0}$ entirely, or has a last link which leaves $K_{0}$. If $s_{xy}$ lies in $\mathcal{D}\setminus K_{0}$ entirely then $n(x),n(y)<0$ and hence $d_{c}(x,y)\geq d_{M}(x,y)$. Otherwise we consider the last link that leaves $K_{0}$ and we have that the length between $x$ and $y$ according to $d_{c}$ is greater than the distance with respect to $d_{M}$ of $x$ from $K_{0}$ which gives that

If either $d_{M}(x,x^{*})\leq\varepsilon$ or $d_{M}(y,x^{*})\leq\varepsilon$ then we are done since as we have seen in the construction of $d_{M}$, $d_{M}(x,y)\geq d(x,y)$, thus either $d(x,x^{*})\leq\varepsilon$ or $d(y,x^{*})\leq\varepsilon$ and (2b) is satisfied. So we may assume that $d(x,x^{*})\geq\varepsilon$ and $d(y,x^{*})\geq\varepsilon$. Therefore $x,y\in\mathcal{D}\setminus K_{0}$ and which translates to $n(x),n(y)<0$. So now using Lemma 9 and we get

Now we consider two cases according to the value of $d_{M}(x,K_{0})$. If $d_{M}(x,K_{0})\geq\varepsilon$ then

B.2 Omitted Proof of Lemmas proven by Meyers in [Mey67]

Thus $d_{M}$ is indeed a metric. We now show that $d_{M}$ is topologically equivalent to $d$. From the inequality $d(x,y)\leq d_{M}(x,y)$ it follows that any $d_{M}$-convergent sequence is also $d$-convergent, with the same limit point. To prove the implication in the opposite direction, note that condition 2. of the hypotheses of the theorem implies the existence for each $\eta>0$ of an $N$ such that

For each $x\in\mathcal{D}$, it follows from 2. that

is finite. Since $f$ is continuous, there is an $\delta>0$ so small that $d(x,y)<\delta$ implies

By (3a) we have $f^{[n+N+\nu(x)]}(x)\in f^{[n+N]}(W)$ and $f^{[n+N+\nu(x)]}(y)\in f^{[n+N]}(W)$ for all $n>0$, so that the (11) implies

Thus $d(x,y)\leq\delta$ implies $d_{M}(x,y)\leq\eta$. This shows that a sequence which is $d$-convergent to $x$ is also $d_{M}$-convergent to $x$, completing the proof of topological equivalence. Finally since $d$ and $d_{M}$ are topologically equivalent and $d$ is complete for $\mathcal{D}$ it follows that $d_{M}$ is also complete for $\mathcal{D}$. $\hfill\qed$

Proof of Lemma 8: We will prove that $d_{c}$ is the desired metric. That $f$ is a contraction with constant $c$ with respect to $d_{c}$ follows by applying (7) to the links $[x_{i-1},x_{i}]$ of any chain $s_{xy}$. Clearly $d_{c}$ is symmetric and $d_{c}(x,x)=0$. The triangle law holds since following a $s_{xy}$ with a $s_{yz}$ yields a $s_{xz}$. It remains to show that it is positive definite.

Consider any $x\neq x^{*}$ and $y\neq x$ and assume $n(x)\leq n(y)$ without loss of generality. If $y\neq x^{*}$, any chain $s_{xy}$ either lies in $\mathcal{D}\setminus K_{n(y)+1}$, or has a last link which leaves $K_{n(y)+1}$, so that

The remaining case, $y=x^{*}$ is covered by

Thus $d_{c}$ is a distance metric. We now have to prove that $d_{c}$ is equivalent to $d_{M}$. Let $B_{\nu}=\mathcal{D}\setminus f^{[-\nu]}(W)$ for $\nu\geq 0$, so that the definition of $\nu(x)$ (10) implies $d_{M}(x,B_{\nu(x)})>0$ and $n(x)\geq-\nu(x)$. For any $x\neq x^{*}$, if $y$ obeys

then $n(x)\geq-\nu(x)$, so that (6) and (12), the last with $x$ and $y$ interchanged, imply

Now choose $k(x)>\max\{0,n(x)\}$ such that $z\in K_{k(x)}$ implies $d_{M}(z,x^{*})<d_{c}(x,x^{*})/2$. Then $d_{c}(x,K_{k(x)})\geq d_{c}(x,x^{*})/2$, so that if $y$ obeys

then only chains disjoint from $K_{k(x)}$ need enter (6), implying

then with (16) and (17) this implies (14) and hence (15) applies. Thus $d_{c}(x_{n},x)\to 0$ whenever $d_{M}(x_{n},x)\to 0$.

Now if $x=x^{*}$, note first that if $d_{M}(x^{*},y)<d_{M}(x^{*},B_{0})$, then

Also note that for any $\eta>0$, $f^{[n]}(W)\to\{x^{*}\}$ guarantees an $N(\eta)>0$ such that $d_{M}(x^{*},z)<\eta/2$ for all $z\in K_{N(\eta)}$. Then $d_{M}(x^{*},y)>\eta$ implies that $d_{M}(y,K_{N(\eta)})\geq\eta/2$ and thus that

Hence $d_{c}(x_{n},x^{*})\to 0$ if and only if $d_{M}(x_{n},x^{*})\to 0$.

Now exactly as above choose $k((x_{n}))=P>\max{0,N}$ such that $z\in K_{k((x_{n}))}$ implies

for all $p>i$, and using (17) with $k(x)=P$, we have

so that $(x_{n})$ is a $d_{M}$-Cauchy sequence. Therefore since $(\mathcal{D},d_{M})$ is complete, the topological space $(\mathcal{D},d_{c})$ is complete too. $\hfill\qed$

Appendix C Proof of Theorem 2

On route to establishing the CLS-completeness of Banach, we will define an intermediate, syntactic problem MetricBanach, which is similar to Banach except that the function $d$ given in the input is not promised to be a metric, and hence a violation of the metricity of $d$ is accepted as a solution.

a point $x\in^{3}$ such that $d(x,f(x))\leq\varepsilon$

two points $x,x^{\prime}\in^{3}$ disproving the contraction of $f$ w.r.t. $d$ with constant $c$, i.e. $d(f(x),f(x^{\prime}))>c\cdot d(x,x^{\prime})$

two points $x,x^{\prime}\in^{3}$ disproving the $\lambda$-Lipschitz continuity of $f$, i.e. $|f(x)-f(x^{\prime})|_{1}>\lambda|x-x^{\prime}|_{1}$.

four points $x_{1},x_{2},y_{1},y_{2}\in^{3}$ with $x_{1}\neq x_{2}$ and $y_{1}\neq y_{2}$ disproving the $\lambda$-Lipschitz continuity of $d(\cdot,\cdot)$, i.e. $|d(x_{1},x_{2})-d(y_{1},y_{2})|>\lambda\left(\left|x_{1}-y_{1}\right|+\left|x_{2}-y_{2}\right|\right)$.

points $x,y,z\in^{3}$ violating any of the metric properties of $d$ ((i)-(iv) of Definition 1).

Notice that MetricBanach is syntactic, namely for any input there exists a solution. We proceed to show that the problem is CLS-complete.

We first show that MetricBanach belongs to CLS even when we disallow (Oe). Starting from an instance $(f,d,\varepsilon,\lambda,c)$ of Continuous LocalOpt we create the following instance

Now we have to show that any output of the Continuous LocalOpt with input $(f,p,\varepsilon^{\prime},\lambda)$ will give us a output of MetricBanach with input $(f,d,\varepsilon,\lambda,c)$.

(CO1) $\implies$ If $d(f(x),f(f(x)))>c\cdot d(x,f(x))$ then $(x,f(x))$ satisfies (Ob). Otherwise

Therefore $x$ satisfies (Oa) and therefore is a solution of MetricBanach.

(CO3) $\implies$ Without loss of generality let $\left\|x-f(x)\right\|\leq\left\|y-f(y)\right\|$. If $x=f(x)$ then if $d(x,f(x))=0$ we immediately satisfy (Oa) otherwise we satisfy (Oe). Otherwise we can give $x_{1}=x$, $x_{2}=f(x)$, $y_{1}=y$, $y_{2}=f(y)$ and since $x_{1}\neq x_{2}$, $y_{1}\neq y_{2}$ we satisfy (ii) of (Od).

This implies that any output of Continuous LocalOpt at the instance $(f^{\prime},p,\varepsilon^{\prime},\lambda^{\prime})$ can produce an output to the instance $(f,d,\varepsilon,\lambda,c)$ of the MetricBanach problem. Therefore $\textsc{MetricBanach}\in\textsc{CLS}$.

Now we are going to show the opposite direction and reduce Continuous LocalOpt to MetricBanach. Starting from an instance $(f,p,\varepsilon,\lambda)$ of Continuous LocalOpt we define for any $x,y\in^{3}$,

We also remind the reader the definition of the discrete metric

Finally we define the smooth interpolation function for $w\leq 0$

The basic observation about $B\left(\cdot\right)$ since $c<1$ is that $c^{\mathop{\left\lceil\kappa(x,y)\right\rceil}+1}\leq B({\kappa(x,y)})\leq c^{\mathop{\left\lceil\kappa(x,y)\right\rceil}}$.

Based on these definitions we create the following instance of MetricBanach

As in the previous reduction we have to show that any result of the MetricBanach with input $(f,d,\varepsilon^{\prime},\lambda,c)$ will give us a result of Continuous LocalOpt with input $(f,p,\varepsilon,\lambda)$.

(Oa) $\implies$ If $p(f(x))\geq p(x)$ then $x$ satisfies (CO1). Otherwise we can see that $\kappa(x,f(x))=-p(x)/2\varepsilon$ and $x\neq f(x)$ so

so $p(f(x))\geq 0\geq p(x)-\varepsilon$ and so $x$ satisfies (CO1).

(Ob) $\implies$ As in the previous case we may assume that $p(f(x))\leq p(x)-\varepsilon$ and that $p(f(y))\leq p(y)-\varepsilon$. Without loss of generality we can assume that $p(x)>p(y)$. If also $p(f(x))\geq p(f(y))$ then $\kappa(x,y)=-p(x)/\varepsilon$ and $\kappa(f(x),f(y))=-p(f(x))/\varepsilon$. Therefore

Now similarly if $p(f(y))>p(f(x))$ then $p(f(y))>p(x)-\varepsilon$. But by our assumption that $p(x)>p(y)$ we get $p(f(y))>p(y)-\varepsilon$. Therefore $y$ satisfies (CO1).