# Non-realizability of some big mapping class groups

Lei Chen and Yan Mary He

###### Abstract.

In this note, we prove that the compactly supported mapping class group of a
surface containing a genus $3$ subsurface has no realization as a subgroup of
the homeomorphism group. We also prove that for certain surfaces with order
$6$ symmetries, their mapping class groups have no realization as a subgroup
of the homeomorphism group. Examples of such surfaces include the plane minus
a Cantor set and the sphere minus a Cantor set.

##  1\. introduction

In this paper, we study the generalized Nielsen realization problem for
mapping class groups of infinite type surfaces. Let $X$ be a surface. We say
that $X$ is finite type if its fundamental group $\pi_{1}(X)$ is finitely
generated and $X$ is infinite type if $\pi_{1}(X)$ is not finitely generated.
The mapping class group
$\operatorname{Mod}(X):=\pi_{0}(\operatorname{Homeo}^{+}(X))$ of $X$ is the
group of path-connected components of the orientation preserving homeomorphism
group $\operatorname{Homeo}^{+}(X)$ of $X$. In particular,
$\operatorname{Mod}(X)$ is called a big mapping class group if $X$ is an
infinite type surface.

For any surface $X$, there is a natural forgetful homomorphism

$p_{X}:\operatorname{Homeo}^{+}(X)\to\operatorname{Mod}(X)$

sending an orientation preserving homeomorphism of $X$ to its mapping class.
We say that $p_{X}$ has a section if there is a homormorphism
$\rho:\operatorname{Mod}(X)\to\operatorname{Homeo}^{+}(X)$ such that the
composition $p_{X}\circ\rho$ equals the identity map. The generalized Nielsen
realization problem asks if the forgetful map $p_{X}$ has a section or not.
The importance of this problem in geometric topology is its relation to the
existence of flat structures on the universal $X$-bundle. We will give more
details in Section 2. In general, we expect that $p_{X}$ not to have sections
if the fundamental group $\pi_{1}(X)$ is not abelian.

For finite type surfaces, Nielsen posed the realization question for finite
subgroups of $\operatorname{Mod}(X)$ in 1943 and Kerckhoff [12] showed that a
lift always exists for finite subgroups of $\operatorname{Mod}(S_{g})$, where
$S_{g}$ is the closed surface of genus $g\geq 2$. The first result on the
Nielsen realization problem for the whole mapping class group is a theorem of
Morita [14] that when $g\geq 18$, there is no section for the projection
$p_{S_{g}}$ to the group of orientation preserving $C^{2}$-diffeomorphisms.
Then Markovic [13] showed that $p_{S_{g}}$ does not have a section for $g\geq
6$ (Chen–Salter [8] later gave an elementary proof of the same result with the
lowest possible genus bound). Franks–Handel [9], Bestvina–Church–Suoto [3] and
Salter–Tshishiku [16] have also obtained the non-realization theorems for
$C^{1}$-diffeomorphisms. Recently, Chen [6] proved that braid group $B_{n}$
has no realization in the group of homeomorphisms for $n\geq 6$ and
Chen–Markovic [7] proved that the Torelli group has no realization in the
group of area-preserving homeomorphisms. The current big open problem in this
area is whether every finite index subgroup of the mapping class group has
realization as homeomorphisms or not. We refer the readers to the survey paper
of Mann–Tshishiku [15] for more history and previous results.

For infinite type surfaces, the finite subgroup realization has been
established in a recent paper of Afton–Calegari–Chen–Lyman [1]. More
precisely, they showed that any finite subgroup of the big mapping class group
$\operatorname{Mod}(X)$ can be realized as a subgroup of homeomorphisms of $X$
where $X$ is an orientable infinite type surface with or without boundary. In
this paper, we study the Nielsen realization problem for the compactly
supported mapping class group $\operatorname{Mod}_{c}(X)$ where $X$ is any
surface containing a genus 3 subsurface. Removing the compact support
condition, we also study the Nielsen realization problem for the entire big
mapping class group $\operatorname{Mod}(X)$ for certain surfaces $X$ which
admit an order 6 symmetry.

###  1.1. Statement of results

Let $X$ be a surface. Recall that a homeomorphism of $X$ is compactly
supported if it is the identity map outside of a compact subset of $X$. Let
$\operatorname{Homeo}^{+}_{c}(X)$ be the group of orientation preserving
compactly supported homeomorphisms of $X$. The compactly supported mapping
class group $\operatorname{Mod}_{c}(X)$ of $X$ is the connected component
group of $\operatorname{Homeo}^{+}_{c}(X)$. We refer the interested reader to
the survey paper of Aramayona–Vlamis [2, Chapter 2.4] for more details.

Our first theorem concerns realizability of $\operatorname{Mod}_{c}(X)$ where
$X$ is a surface containing a genus $3$ subsurface.

######  Theorem 1.1.

If $X$ is a surface which contains a genus $3$ subsurface, then the projection
map

$p_{S}^{c}:\operatorname{Homeo}^{+}_{c}(X)\to\operatorname{Mod}_{c}(X)$

has no sections.

To prove the theorem, we use Markovic’s minimal decomposition theory [13].
Suppose on the contrary that there exists a section
$\rho_{c}:\operatorname{Mod}_{c}(X)\to\operatorname{Homeo}_{c}^{+}(X)$. Then
using Markovic’s minimal decomposition theory, we find a subsurface of $X$
having genus $3$ and one boundary component on which we can realize the
mapping class group $\operatorname{Mod}(S_{3,1})$ as a subgroup of
$\operatorname{Homeo}^{+}(S_{3,1})$. Here $\operatorname{Homeo}^{+}(S_{3,1})$
is the group of orientation preserving homeomorphisms of a genus $3$ surface
fixing a point and $\operatorname{Mod}(S_{3,1})$ is the connected component
group of $\operatorname{Homeo}^{+}(S_{3,1})$. However, this is a contradiction
to the following theorem.

######  Theorem 1.2.

The natural projection map
$p_{S_{3,1}}:\operatorname{Homeo}^{+}(S_{3,1})\to\operatorname{Mod}(S_{3,1})$
has no sections.

To prove this theorem, we use the Birman-Hilden theory and a theorem of the
first author’s that $\operatorname{Mod}(S_{0,7,1})$ has no realizations in
$\operatorname{Homeo}^{+}(S_{0,7,1})$. Here $\operatorname{Mod}(S_{0,7,1})$ is
the mapping class group of a surface of genus 0 fixing 2 sets of points, where
one set contains 7 points and the other set contains one point.

If we remove the compact support condition in Theorem 1.1 and consider the
Nielsen realization problem for the entire big mapping class group, it seems
impossible that Markovic’s theory can be directly applied to this non-
compactly supported case. This is due to the fact that the shadowing property
of local Anosov map fails to work if the realization of a mapping class does
not have compact support.

However, for some special infinite type surfaces, we do obtain non-
realizability results for the entire big mapping class group.

######  Theorem 1.3.

Let $X=\mathbb{R}^{2}\setminus\mathcal{C}$ or
$X=\mathbb{S}^{2}\setminus\mathcal{C}$ where $\mathcal{C}$ is a set which can
be arranged as in Figure 1 so that Lemma 5.1 holds. Then the map
$p_{X}:\operatorname{Homeo}^{+}(X)\to\operatorname{Mod}(X)$ has no sections.

Examples of such set $\mathcal{C}$ include the Cantor set and 6 copies of a
cardinal set $\omega^{\alpha}+1$. A key consequence of this choice of
$\mathcal{C}$ is that the surface $X=\mathbb{R}^{2}\setminus\mathcal{C}$ (or
$X=\mathbb{S}^{2}\setminus\mathcal{C}$) admits an order 6 symmetry.

To prove the theorem, we use this order 6 mapping class to construct a
finitely generated subgroup $\Gamma$ of $\operatorname{Mod}(X)$ that has no
realization as homeomorphisms of $X$. More specifically, suppose on the
contrary that there exists a section
$\rho:\operatorname{Mod}(X)\to\operatorname{Homeo}^{+}(X)$. Then we will show
that the realization of every element in $\Gamma$ has the same set of fixed
points which does not contain any point in $\mathcal{C}$. However, there
exists an order 5 element in $\Gamma$ whose realization fixes a point in
$\mathcal{C}$, which is a contradiction.

We point out that if $X$ is the plane minus a Cantor set, then any countable
subgroup of $\operatorname{Homeo}^{+}(S^{1})$ can be embedded into
$\operatorname{Homeo}^{+}(X)$ by Calegari–Chen in the proof of [5, Theorem
5.1]. In particular, any countable subgroup of $\operatorname{Mod}(X)$ can be
embedded into $\operatorname{Homeo}^{+}(X)$. Therefore, the finitely generated
subgroup $\Gamma$ that we construct in Section 3 has an embedding into
$\operatorname{Homeo}^{+}(X)$ but such an embedding is not a realization. In
contrast, $\operatorname{Mod}(S_{g})$ for a genus $g>2$ surface has no
embedding into $\operatorname{Homeo}^{+}(S_{g})$ by Franks–Handel [10,
Corollary 1.3].

###  1.2. Organizaiton of the paper

The paper is organized as follows. In Section 2, we give geometric
interpretation of the generalized Nielsen realization problem. In Section 3,
we give a brief overview of Markovic’s minimal decomposition theory. We prove
Theorem 1.1 and Theorem 1.2 in Section 4. Finally, we prove Theorem 1.3 in
Section 5.

### Acknowledgement

We would like to thank Danny Calegari for suggesting [5, Theorem 5.1] and Jing
Tao for useful comments.

##  2\. Geometric interpretation

In this section, $X$ can be any manifold. The main motivation to study the
generalized Nielsen realization problem is its connection to $X$-bundles.

An $X$-bundle is a fiber bundle $\pi:E\to B$ whose fiber is the manifold $X$
and whose structure group is $\operatorname{Homeo}^{+}(X)$. In particular,
there is an open cover $\\{U_{i}\\}$ for the base $B$ such that the bundle is
trivial on each $U_{i}$, i.e. $\pi^{-1}(U_{i})=U_{i}\times X$ and the trivial
bundles are glued by transition functions $U_{i}\cap
U_{j}\to\operatorname{Homeo}^{+}(X)$. The universal $X$-bundle
$E\operatorname{Homeo}^{+}(X)$ is an $X$-bundle whose base is the classifying
space $B\operatorname{Homeo}^{+}(X)$. The universality of the bundle is given
in the following sense. Given any map from a CW-complex $B$ to
$B\operatorname{Homeo}^{+}(X)$, we obtain an $X$-bundle $E\to B$ by pulling
back the universal $X$-bundle as shown in the following diagram.

${E}$${E\operatorname{Homeo}^{+}(X)}$${B}$${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}B\operatorname{Homeo}^{+}(X)}$

Let $\operatorname{Homeo}^{+}(X)^{\delta}$ be the discrete group of
$\operatorname{Homeo}^{+}(X)$. Then $\operatorname{Homeo}^{+}(X)^{\delta}$
also has its classifying space $B\operatorname{Homeo}^{+}(X)^{\delta}$. We
have the following natural forgetful map

$\pi_{X}:B\operatorname{Homeo}^{+}(X)^{\delta}\to
B\operatorname{Homeo}^{+}(X).$

Let $\widetilde{B}$ be the universal cover of $B$. We say that an $X$-bundle
over $B$ has a topological flat structure if this bundle is
$\widetilde{B}\times X/\pi_{1}(B)$ where the action is given by deck
transformations on $\widetilde{B}$ and a homomorphism
$\pi_{1}(B)\to\operatorname{Homeo}^{+}(X)$ on $X$. For this reason, whether
the universal $X$-bundle has a flat structure corresponds to whether the map
$\pi_{X}$ has a section. However, a section $s$ of $\pi_{X}$ gives the
following homomorphism by taking fundamental groups

$\pi_{1}(B\operatorname{Homeo}^{+}(X))=\pi_{0}(\operatorname{Homeo}^{+}(X))=\operatorname{Mod}(X)\xrightarrow{s_{*}}\operatorname{Homeo}^{+}(X)=\pi_{1}(B\operatorname{Homeo}^{+}(X)^{\delta}).$

Therefore, if the map $s$ is a section of $\pi_{X}$ then the map $s_{*}$ is a
section of $\pi_{X*}=p_{X}$. This means that a negative answer of the
generalized Nielsen realization problem for $X$ implies that the universal $X$
bundle has no flat structure. In general, it is hard to compute both the
homology and the homotopy groups of $B\operatorname{Homeo}^{+}(X)$ and
$B\operatorname{Homeo}^{+}(X)^{\delta}$.

##  3\. Markovic’s minimal decomposition theory

In this section, we give a brief overview of Markovic’s minimal decomposition
theory. We start with the definition of an upper semi-continuous decomposition
of a surface.

######  Definition 3.1 ([13, Definition 2.1]).

Let $M$ be a surface. A collection ${\bf S}$ of closed connected subsets of
$M$ is an upper semi-continuous decomposition of $M$ if the following holds:

  1. (1)

If $S_{1},S_{2}\in{\bf S}$, then $S_{1}\cap S_{2}=\emptyset$.

  2. (2)

If $S\in{\bf S}$, then $S$ does not separate $M$; that is $M\setminus S$ is a
connected set.

  3. (3)

We have $M=\cup_{S\in{\bf S}}S$.

  4. (4)

If $S_{n}\in{\bf S}$ for $n\in\mathbb{N}$, is a sequence that has the
Hausdorff limit $S_{0}$, then there exists $S\in{\bf S}$ such that
$S_{0}\subset S$.

######  Definition 3.2 ([13, Definition 2.2]).

Let $M$ be a surface and let $S\subset M$ be a closed, connected subset of $M$
which does not separate $M$. We say that $S$ is acyclic if there is a simply
connected open set $U\subset M$ such that $S\subset U$ and $U\setminus S$ is
homeomorphic to an annulus.

Let ${\bf S}$ be an upper semi-continuous decomposition of $M$. For every
point $p\in M$, there exists a unique $S_{p}\in{\bf S}$ that contains $p$. We
denote by $M_{\bf S}$ the set of all points $p\in M$ such that the
corresponding $S_{p}$ is acyclic.

Now we add some dynamics to an upper semi-continuous decomposition of $M$ by
considering a subgroup $G$ of $\operatorname{Homeo}^{+}(M)$. In particular, we
need the following definition for an upper semi-continuous decomposition of
$M$ to be compatible with $G$.

######  Definition 3.3 ([13, Definition 3.1]).

Let ${\bf S}$ be an upper semi-continuous decomposition of $M$. Let $G$ be a
subgroup of $\operatorname{Homeo}^{+}(M)$. We say that ${\bf S}$ is admissible
for the group $G$ if the following holds:

  1. (1)

Each $\hat{f}\in G$ preserves setwise every component of ${\bf S}$.

  2. (2)

Let $S\in{\bf S}$. Then every point in every frontier component of the surface
$M\setminus S$ is a limit of points from $M\setminus S$ that belong to acyclic
components of ${\bf S}$ (note that not every point of $S$ need to be in a
frontier component of the subsurface $M\setminus S$).

If $G$ is the cyclic group generated by a homeomorphism $\hat{f}:M\to M$, we
say that ${\bf S}$ is an admissible decomposition for $\hat{f}$.

An admissible decomposition ${\bf S}$ for a group $G$ will be called the
minimal decomposition for $G$ if ${\bf S}$ is contained in every admissible
decomposition for $G$.

######  Theorem 3.4 ([13, Theorem 3.1]).

Every subgroup $G$ of $\operatorname{Homeo}^{+}(M)$ has a unique minimal
decomposition.

##  4\. Realization of compactly supported big mapping class groups

In this section, we prove Theorem 1.1 which states that the projection map

$p_{S}^{c}:\operatorname{Homeo}^{+}_{c}(S)\to\operatorname{Mod}_{c}(S)$

has no sections if the surface $S$ contains a subsurface of genus $3$.

We first prove a preliminary result, namely Theorem 1.2, which states that the
natural projection map

$p_{S_{3,1}}:\operatorname{Homeo}^{+}(S_{3,1})\to\operatorname{Mod}(S_{3,1})$

has no sections. Recall that $\operatorname{Homeo}^{+}(S_{3,1})$ is the
orientation preserving homeomorphism group of genus $3$ fixing a point and
$\operatorname{Mod}(S_{3,1})$ is the connected component group of
$\operatorname{Homeo}^{+}(S_{3,1})$.

###### Proof of Theorem 1.2.

Let $x\in S_{3}$ be the marked point on a genus 3 surface $S_{3}$. Let $\tau$
be the hyper-elliptic involution of $S_{3}$ where one of its fixed points is
$x$. Let $\operatorname{SHomeo}^{+}(S_{3,1})$ be the symmetric homeomorphism
group; i.e., the group of homeomorphisms of $S_{3}$ fixing $x$ that commute
with $\tau$. Let $\operatorname{SMod}(S_{3,1})$ be the symmetric mapping class
group under $\tau$ defined as the image of $\operatorname{SHomeo}(S_{3,1})$ in
$\operatorname{Mod}(S_{3,1})$. Then by the Birman–Hilden theory [4] (see also
[11, Theorem 9.2]), we know that the symmetric mapping group satisfies the
following short exact sequence

$1\to\langle\tau\rangle\to\operatorname{SMod}(S_{3,1})\to\operatorname{Mod}(S_{0,7,1})\to
1$

where $\operatorname{Mod}(S_{0,7,1})$ is the mapping class group of surface of
genus $0$ with two sets of marked points where one set contains one point and
the other set contains 7 points. If the projection map $p_{S_{3,1}}$ had a
realization, say $\rho$, then by Ahlfors’ trick, $\rho(\tau)$ is conjugate to
the standard hyper-elliptic involution. It follows that $\tau$ has $8$ fixed
points, one of which is $x$. A section of
$p_{S_{3,1}}|_{\operatorname{SMod}(S_{3,1})}$ gives a section of the map
$p_{S_{0,7,1}}:\operatorname{Homeo}^{+}(S_{0,7,1})\to\operatorname{Mod}(S_{0,7,1})$.
However, this is a contradiction to [6, Theorem 1.1]. ∎

We now prove Theorem 1.1. We remark that we will use intensely results,
definitions and arguments in [13], which will all work if all the elements
used are compactly supported. However, if we try to argue for the non-
compactly supported case, even the shadowing property of the Anosov element
does not work, and seems impossible to repair.

###### Proof of Theorem 1.1.

We prove the theorem by contradiction. Suppose that there exists a section

$\rho_{c}:\operatorname{Mod}_{c}(S)\to\operatorname{Homeo}^{+}_{c}(S)$

of $p_{S}^{c}$. Let $T\subset S$ be the subsurface of genus $3$ with one
boundary component. Then there is an embedding

$i:\operatorname{Mod}(T)\to\operatorname{Mod}_{c}(S).$

We will show that $p_{S}^{c}$ already does not have sections over
$i(\operatorname{Mod}(T))$. Let $c$ be the boundary component of $T$ and let
$T_{c}$ denote the Dehn twist about the curve $c$.

Let $M_{c}$ be the union of acyclic components of the minimal decomposition
for $\rho(T_{c})$. Then by [13, Proposition 4.1] which works for compactly
supported homeomorphisms of infinite type surfaces, we know that $M_{c}$
contains a subsurface $T^{\prime}$ of $S$, which contains a subsurface of
genus at least $1$. Since $T_{c}$ is a Dehn twist which commutes with all the
Dehn twists about curves disjoint from $c$, we know that the end of
$T^{\prime}$ cannot be any curve other than $c$. On the other hand,
$T^{\prime}$ cannot be the whole surface, because otherwise $\rho_{c}(T_{c})$
is homotopic to identity by [13, Theorem 2.1] (see a more complete argument in
[13, Lemma 5.1]). Then we know that $T^{\prime}$ is homotopic to $T$.

Since $\operatorname{Mod}(T)$ commutes with $T_{c}$, we know that
$\rho_{c}(\operatorname{Mod}(T))$ preserves $T^{\prime}$ and is a permutation
of all the acyclic components of $\rho_{c}(T_{c})$ inside $T^{\prime}$. Now we
have an action $\rho^{\prime}$ of $\operatorname{Mod}(T)$ on $T^{\prime}/\sim$
where two points are equivalent if they belong to the same acyclic set in the
minimal decomposition for $\rho_{c}(T_{c})$. Under this action, the element
$\rho^{\prime}(T_{c})$ is identity. Thus this gives a realization of the
homomorphism
$p_{S_{3,1}}:\operatorname{Homeo}^{+}(S_{3,1})\to\operatorname{Mod}(S_{3,1})$,
which does not exist by Theorem 1.2. ∎

##  5\. The proof of Theorem 1.3

In this section, we prove Theorem 1.3. We first prove the theorem for
$X=\mathbb{R}^{2}\setminus\mathcal{C}$ or
$X=\mathbb{S}^{2}\setminus\mathcal{C}$ where $\mathcal{C}$ is a Cantor set.
Then it will be immediate from the proof that the essential property of the
set $\mathcal{C}$ which makes the argument work is Lemma 5.1. Therefore as
long as $\mathcal{C}$ can be arranged as shown in Figure 1 and satisfies Lemma
5.1, Theorem 1.3 is true.

###  5.1. The case of a Cantor set

Let $X$ be the plane minus a Cantor set or the sphere minus a Cantor set. We
first construct a specific subgroup of $\operatorname{Mod}(X)$ and the
relations in it. Then we show that this special subgroup cannot act as
homeomorphisms.

Let $C$ be the standard middle-third Cantor set embedded in the plane
$\mathbb{R}^{2}$. We construct a set of points $C^{\prime}$ in the plane as
follows. Let $D_{1},...,D_{6}$ be the discs as shown in Figure 1. We denote by
$P_{1},...,P_{6}$ the centers of the discs $D_{1},...,D_{6}$ respectively.
Inside each disk $D_{i}$, there is a wedge union $C_{i}$ of $30$ copies of the
standard Cantor set with the center $P_{i}$ as the wedge point. Let
$C^{\prime}$ be the union of $C_{i}$.

Figure 1. Configuration of the Cantor set $C^{\prime}$

We have the following lemma.

######  Lemma 5.1.

The two surfaces $\mathbb{R}^{2}-C^{\prime}$ and $\mathbb{R}^{2}-C$ are
homeomorphic.

###### Proof.

We first show that $C^{\prime}$ is homeomorphic to the Cantor set $C$.
Brower’s theorem states that a topological space is homeomorphic to the Cantor
set $C$ if and only if it is non-empty, perfect, compact, totally
disconnected, and metrizable. By construction, $C^{\prime}$ is clearly non-
empty, perfect, compact, totally disconnected. Moreover, $C^{\prime}$ is
metrizable as it is embedded in $\mathbb{R}^{2}$. Therefore, there exists a
homeomorphism $\varphi:C^{\prime}\to C$. By Schoenflie’s theorem, $\varphi$
extends to a homeomorphism $\tilde{\varphi}:\mathbb{R}^{2}\to\mathbb{R}^{2}$
with $\tilde{\varphi}(C^{\prime})=C$. It follows that
$\mathbb{R}^{2}-C^{\prime}$ is homeomorphic to $\mathbb{R}^{2}-C$. ∎

Now we will study the generalized Nielsen realization problem for
$\mathbb{R}^{2}-C^{\prime}$. Denote by $R(\theta)$ the simultaneous counter-
clockwise rotation of each $D_{i}$ by an angle of $\theta$. To make
$R(\theta)$ a homeomorphism of $\mathbb{R}^{2}-C^{\prime}$, we need to apply a
twist back on an annulus around the disk $D_{i}$. Around each $D_{i}$, Figure
2 represents this homeomorphism. Based on our construction of $C^{\prime}$, we
will consider the angle $\theta$ as an integer multiple of $2\pi/30$.

Figure 2. Rotation $R(\theta)$

######  Definition 5.2 (Rigid half twist).

Let $\sigma_{i}$ be the disc pushing between $D_{i}$ and $D_{i+1}$ clockwise
as shown in Figure 3. We call $\sigma_{i}$ the rigid half twist between
$D_{i}$ and $D_{i+1}$.

Loosely speaking, the map $\sigma_{i}$ moves the discs around in a specified
way while keeping the interior of each disc fixed relative to the center of
the disc.

Figure 3. Disk pushing $\sigma_{1}$

Let $\alpha_{1}$ be the clockwise rotation by $2\pi/6$ of the plane. By
symmetry, we see that $\alpha_{1}$ preserves $C^{\prime}$ and is thus an
element in $\operatorname{Mod}(\mathbb{R}^{2}-C^{\prime})$. Moreover,
$\alpha_{1}$ is an order $6$ element.

######  Definition 5.3 (Rigid rotation).

We define rigid rotation, denoted by $\alpha_{1}^{r}$, to be the disc pushing
following the path as shown in Figure 4.

Figure 4. Rigid rotation $\alpha_{1}^{r}$

Define $\alpha_{2}:=\alpha_{1}\sigma_{5}R(2\pi/30)$. We have the following
relations of all the elements we have defined.

######  Lemma 5.4.

We have the following relations:

  1. (1)

$R(2\pi/30)$ commutes with $\sigma_{i}$,

  2. (2)

$\alpha_{1}(\sigma_{i})\alpha_{1}^{-1}=\sigma_{i+1}$,

  3. (3)

$\alpha_{1}^{r}=\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}\sigma_{5}=\sigma_{6}\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}$,

  4. (4)

$\alpha_{1}=\alpha_{1}^{r}R(2\pi/6)$,

  5. (5)

$\alpha_{2}$ is an order $5$ element.

###### Proof.

  1. (1)

The element $\sigma_{i}$ preserves the support of $R(2\pi/30)$. Outside the
support of $R(2\pi/30)$, they commute because $R(2\pi/30)$ is the identity.
Inside the support of $R(2\pi/30)$, they commute because $\sigma_{i}$ is
rigid.

  2. (2)

This one is given by definition.

  3. (3)

This is a consequence of the same result in the braid group. The point-pushing
version is given by the following fiber bundle

$\operatorname{Homeo}(\mathbb{R}^{2},6pts)\to\operatorname{Homeo}(\mathbb{R}^{2})\to\operatorname{Conf}_{6}(\mathbb{R}^{2})$

where $\operatorname{Homeo}(\mathbb{R}^{2},6pts)$ is the set of homeomorphisms
of $\mathbb{R}^{2}$ fixing $6$ points as a set and
$\operatorname{Conf}_{6}(\mathbb{R}^{2})$ is the configuration space of $6$
distinct unordered points in $\mathbb{R}^{2}$.

Taking the long exact sequence of homotopy groups, we obtain a map

$\pi_{1}(\operatorname{Conf}_{6}(\mathbb{R}^{2}))\to\pi_{0}(\operatorname{Homeo}(\mathbb{R}^{2},6pts)).$

Figure 5 shows the path for the point-pushing of
$\sigma_{1}\sigma_{2}...\sigma_{5}$, from which we can see that the two paths
for the point-pushing of $\alpha_{1}^{r}$ and
$\sigma_{1}\sigma_{2}...\sigma_{5}$ are homotopic to each other.

Figure 5. The path of $\sigma_{1}\sigma_{2}...\sigma_{5}$

In our case, we are dealing with disc-pushing but since all of our mapping
classes are rigid, we obtain the same result.

  4. (4)

This is given by the definition of $\alpha_{1}^{r}$.

  5. (5)

Let us compute $\alpha_{2}^{5}$.

$\displaystyle\alpha_{2}^{5}$
$\displaystyle=\alpha_{1}\sigma_{5}R(2\pi/30)\alpha_{1}\sigma_{5}R(2\pi/30)\alpha_{1}\sigma_{5}R(2\pi/30)\alpha_{1}\sigma_{5}R(2\pi/30)\alpha_{1}\sigma_{5}R(2\pi/30)$
$\displaystyle=\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}R(2\pi/6)$
$\displaystyle=\sigma_{6}\alpha_{1}^{2}\sigma_{5}\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}R(2\pi/6)$
$\displaystyle=\sigma_{6}\sigma_{1}\alpha_{1}^{3}\sigma_{5}\alpha_{1}\sigma_{5}\alpha_{1}\sigma_{5}R(2\pi/6)$
$\displaystyle=...=\sigma_{6}\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}\alpha_{1}^{5}R(2\pi/6)$
$\displaystyle=\alpha_{1}^{r}\alpha_{1}^{-1}R(2\pi/6)$
$\displaystyle=R(-2\pi/6)R(2\pi/6)=1$

Therefore $\rho(\alpha_{2})$ is an order $5$ element

∎

Let $\Gamma$ be the subgroup of
$\operatorname{Mod}(\mathbb{R}^{2}-C^{\prime})$ generated by $\sigma_{i}$ and
$R(2\pi/30)$. We will prove the following proposition which implies Theorem
1.3.

######  Proposition 5.5.

The group $\Gamma$ has no section under $p_{X}$.

###### Proof.

Suppose that $\Gamma$ has a section $\rho$ of $p_{X}$. Then $\rho(\alpha_{1})$
is an order $6$ homeomorphism of $\mathbb{R}^{2}$, which has a unique fixed
point $O$. By the construction of $\alpha_{1}$, we know that $O$ is not a
puncture.

Now we will show that $\\{\rho(\sigma_{i})\\}$ and $\rho(R(2\pi/30))$ both fix
$O$. Since $R(2\pi/30)$ commutes with $\alpha_{1}$, we know that
$\rho(R(2\pi/30))$ fixes $O$. The reason that $\\{\rho(\sigma_{i})\\}$ fixes
$O$ follows from the same argument as in [6]. We include it here for
completeness.

We prove this by explicitly writing $\sigma_{3}$ as a product of elements in
$C(\alpha_{1}^{2})$ and $C(\alpha_{1}^{3})$. Here $C(\alpha_{1}^{j})$ is the
set of elements in $\operatorname{Mod}(X)$ which commute with $\alpha_{1}^{j}$
for $j=2,3$. Let $G$ be the group generated by $C(\alpha_{1}^{2})$ and
$C(\alpha_{1}^{3})$. Since $\rho(C(\alpha_{1}^{3}))$ and
$\rho(C(\alpha_{1}^{2}))$ both fix $O$, every element of $\rho(G)$ fixes $O$.
We first observe that
$\sigma_{1}\sigma_{4},\sigma_{2}\sigma_{5},\sigma_{3}\sigma_{6}\in
C(\alpha_{1}^{3})$ and
$\sigma_{1}\sigma_{3}\sigma_{5},\sigma_{2}\sigma_{4}\sigma_{6}\in
C(\alpha_{1}^{2})$. Now, we start with

$\alpha_{1}^{r}=\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}\sigma_{5}\in G.$

Since $\sigma_{5}\sigma_{2}\in G$, we have that

$\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}\sigma_{5}(\sigma_{5}\sigma_{2})^{-1}\in
G.$

By commutativity of $\sigma_{2}$ and $\sigma_{4}$, we obtain

$\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{2}^{-1}\sigma_{4}\in G.$

Applying the same calculation for $\sigma_{1}\sigma_{4}\in G$, we obtain

$\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{2}^{-1}\sigma_{1}^{-1}\in G.$

Since $\sigma_{1}\sigma_{3}\sigma_{5}\in G$, we obtain

$(\sigma_{1}\sigma_{3}\sigma_{5})^{-1}\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{2}^{-1}\sigma_{1}^{-1}(\sigma_{1}\sigma_{3}\sigma_{5})\in
G.$

But we know that $\sigma_{5}$ commutes with every other element in the above
equation, so we obtain

$\sigma_{3}^{-1}\sigma_{2}\sigma_{3}\sigma_{2}^{-1}\sigma_{3}\in G.$

Since $\sigma_{3}\sigma_{6}\in G$, we obtain

$(\sigma_{3}\sigma_{6})\sigma_{3}^{-1}\sigma_{2}\sigma_{3}\sigma_{2}^{-1}\sigma_{3}(\sigma_{3}\sigma_{6})^{-1}\in
G.$

But we know that $\sigma_{6}$ commutes with every other element in the above
equation, so we obtain

$\sigma_{2}\sigma_{3}\sigma_{2}^{-1}\in G.$

Since $\sigma_{2}\sigma_{5}\in G$, we obtain

$(\sigma_{2}\sigma_{5})^{-1}\sigma_{2}\sigma_{3}\sigma_{2}^{-1}(\sigma_{2}\sigma_{5})\in
G.$

But we know that $\sigma_{5}$ commutes with every other element in the above
equation, so we obtain

$\sigma_{3}\in G.$

By symmetry, we know that $\sigma_{i}\in G$. Since elements of $\rho(G)$ fixes
$O$, we know that $\rho(\alpha_{2})$ also fixes $O$, where
$\alpha_{2}:=\alpha_{1}\sigma_{5}R(2\pi/30)$. However, by definition of
$\alpha_{2}$, the element $\rho(\alpha_{2})$ also fixes a puncture $P_{6}$,
the center of $D_{6}$. This contradicts the fact that $\rho(\alpha_{2})$ is a
finite order homeomorphism of $\mathbb{R}^{2}$, which has a unique fixed
point.

For the sphere minus a Cantor set case, we construct the same group as before.
Now $\rho(\alpha_{1})$ has two fixed points $N$ and $S$ and we use the same
argument to show that $\rho(G)$ will fix $\\{N,S\\}$ as a set. However, as an
order $5$ element, $\rho(\alpha_{2})$ has to fix $\\{N,S\\}$ individually.
This contradicts the fact that $\rho(\alpha_{2})$ also fixes a puncture (which
is the center of a disc) as in the case of the plane minus a Cantor set. ∎

###  5.2. Other cases

We begin with an example where $\mathcal{C}$ is the union of 6 copies of the
set $A$ of cardinal $\omega^{\alpha}+1$. For each copy, we wedge 30 copies of
$A$ at the largest accumulation point $P_{i}$ and make them contained in the
disc $D_{i},i=1,...,6$, similar to the Cantor set in Figure 1. We denote by
$\mathcal{C}^{\prime}$ this particular configuration of these 180 copies of
$A$. Then we see that Lemma 5.1 holds; namely,
$\mathbb{R}\setminus\mathcal{C}$ is homeomorphic to
$\mathbb{R}\setminus\mathcal{C}^{\prime}$. This is because there exists a
homeomorphism $\varphi:\mathcal{C}^{\prime}\to\mathcal{C}$ which extends by
Schoenflie’s theorem, to a homeomorphism
$\tilde{\varphi}:\mathbb{R}^{2}\to\mathbb{R}^{2}$ with
$\tilde{\varphi}(\mathcal{C}^{\prime})=\mathcal{C}$. From here, the rest of
the argument goes through.

Hence, if we can arrange the set $\mathcal{C}$ into the configuration as shown
in Figure 1 so that Lemma 5.1 holds, then Theorem 1.3 holds.

## References

  * ACCL [21] Santana Afton, Danny Calegari, Lvzhou Chen, and Rylee Alanza Lyman.  Nielsen realization for infinite-type surfaces.  Proc. Amer. Math. Soc., 149(4):1791–1799, 2021.
  * AV [20] Javier Aramayona and Nicholas G. Vlamis.  Big mapping class groups: an overview.  In In the tradition of Thurston—geometry and topology, pages 459–496. Springer, Cham, [2020] ©2020.
  * BCS [13] Mladen Bestvina, Thomas Church, and Juan Souto.  Some groups of mapping classes not realized by diffeomorphisms.  Comment. Math. Helv., 88(1):205–220, 2013.
  * BH [73] J. Birman and H. Hilden.  On isotopies of homeomorphisms of Riemann surfaces.  Ann. of Math., 97(2):424–439, 1973.
  * CC [21] Danny Calegari and Lvzhou Chen.  Big mapping class groups and rigidity of the simple circle.  Ergodic Theory Dynam. Systems, 41(7):1961–1987, 2021.
  * Che [19] Lei Chen.  On the nonrealizability of braid groups by homeomorphisms.  Geom. Topol., 23(7):3735–3749, 2019.
  * CM [20] Lei Chen and Vladimir Markovic.  Non-realizability of the Torelli group as area-preserving homeomorphisms.  J. Lond. Math. Soc. (2), 102(3):957–976, 2020.
  * CS [20] Lei Chen and Nick Salter.  Global fixed points of mapping class group actions and a theorem of markovic.  Preprint:https://arxiv.org/abs/2003.02440, 2020.
  * FH [09] John Franks and Michael Handel.  Global fixed points for centralizers and Morita’s theorem.  Geom. Topol., 13(1):87–98, 2009.
  * FH [13] John Franks and Michael Handel.  Triviality of some representations of ${\rm MCG}(S_{g})$ in $GL(n,\mathbb{C})$, ${\rm Diff}(S^{2})$ and ${\rm Homeo}(\mathbb{T}^{2})$.  Proc. Amer. Math. Soc., 141(9):2951–2962, 2013.
  * FM [12] Benson Farb and Dan Margalit.  A primer on mapping class groups, volume 49 of Princeton Mathematical Series.  Princeton University Press, Princeton, NJ, 2012.
  * Ker [83] Steven Kerckhoff.  The Nielsen realization problem.  Ann. of Math. (2), 117(2):235–265, 1983.
  * Mar [07] Vladimir Markovic.  Realization of the mapping class group by homeomorphisms.  Invent. Math., 168(3):523–566, 2007.
  * Mor [87] Shigeyuki Morita.  Characteristic classes of surface bundles.  Invent. Math., 90(3):551–577, 1987.
  * MT [19] Kathryn Mann and Bena Tshishiku.  Realization problems for diffeomorphism groups.  In Breadth in contemporary topology, volume 102 of Proc. Sympos. Pure Math., pages 131–156. Amer. Math. Soc., Providence, RI, 2019.
  * ST [16] Nick Salter and Bena Tshishiku.  On the non-realizability of braid groups by diffeomorphisms.  Bull. Lond. Math. Soc., 48(3):457–571, 2016.


# Worst case tractability of linear problems
in the presence of noise: linear information

Leszek Plaskota  Faculty of Mathematics, Informatics and Mechanics, University
of Warsaw, ul. S. Banacha 2, 02-097 Warsaw, Poland<EMAIL_ADDRESS>https://orcid.org/0000-0001-8704-0790 and  Paweł Siedlecki  Faculty of
Mathematics, Informatics and Mechanics, University of Warsaw, ul. S. Banacha
2, 02-097 Warsaw, Poland<EMAIL_ADDRESS>https://orcid.org/0000-0001-7352-9253

###### Abstract.

We study the worst case tractability of multivariate linear problems defined
on separable Hilbert spaces. Information about a problem instance consists of
noisy evaluations of arbitrary bounded linear functionals, where the noise is
either deterministic or random. The cost of a single evaluation depends on its
precision and is controlled by a cost function. We establish mutual
interactions between tractability of a problem with noisy information, the
cost function, and tractability of the same problem, but with exact
information.

##  1\. Introduction

_Tractability of multivariate problems_ is nowadays one of the most active
areas of _information-based complexity_ ; we mention only the three-volume
monograph [3, 4, 5]. Tractability research concentrates on establishing both
quantitative and qualitative properties of the interplay between the cost and
accuracy of approximation, and the number of variables occurring in a
multivariate computational problem. To the best of the authors’ knowledge, all
tractability research has hitherto concentrated on _exact information_ , i.e.,
information consisting of exact evaluations of information functionals. The
goal of this article is to extend tractability studies to include _noisy
information_ , where observations of functionals are contaminated by some
noise.

We study tractability in the _worst case setting_ , in the presence of
_deterministic_ (bounded) or _random_ (Gaussian) noise. The model of noise and
cost is adopted from [2, 6]. That is, information is built out of a finite
number of noisy evaluations of functionals, which are subject to our choice.
Moreover, prior to their noisy evaluation it is also possible to set required
_precision_ $\sigma,$ which is a bound on the absolute value of the noise in
the deterministic case, and the standard deviation of a Gaussian variable in
the case of random noise. The cost of a single evaluation with a given
precision is controlled by a _cost function_ $\$$, which is a part of the
problem formulation. The higher the precision, the higher the cost.

The main theme of our work is a comparative study of exact and noisy
information from the point of view of tractability of multivariate linear
problems $S_{d}:F_{d}\to G_{d}$ acting between separable Hilbert spaces. We
assume that noisy evaluations of _any_ linear functionals with norm bounded by
one are possible. The focus is on _(strong) polynomial tractability_ , _weak
tractability_ , _intractability_ , and _the curse of dimensionality_. We are
interested in establishing mutual interactions between tractability of a
multivariate problem with noisy information, the cost function, and
tractability of the same problem, but with exact information. In particular,
we seek for conditions guaranteeing equivalence of various tractability
notions for both, the exact and noisy settings.

Such equivalence is established, for instance, for polynomial tractability
provided the cost function grows polynomially. To give a flavor of our
results, suppose that the problem with exact information is polynomially
tractable, i.e., its $(\varepsilon,d)$-complexity is upper bounded by
$Cd^{q}\varepsilon^{-p},$ where $\varepsilon$ is the required error of
approximation, and that the cost function grows polynomially, i.e.,
$\$(\sigma,d)\leq 1+Dd^{t}\sigma^{-2s}.$ Then the same problem with noisy
information is also polynomially tractable. Moreover, its complexity is
essentially bounded as

$\mathrm{comp}_{\$}(\varepsilon,d)\preccurlyeq
d^{\overline{t}+q(\overline{s}+1)}\varepsilon^{-\max\left(p(\overline{s}+1),2\overline{s}\right)},$

where $(\overline{s},\overline{t})=(s,t)$ for bounded noise, and
$(\overline{s},\overline{t})=(s,t)/\max(1,s)$ for Gaussian noise, see Theorem
1 and Theorem 4. We stress that we do not know whether the exponents of
polynomial tractability above are optimal. The point is that, unlike in the
case of exact information, it is generally an open question how to optimally
select functionals when their evaluations are corrupted by noise.

As for the technical part, it turns out that an important role in the analysis
plays the complexity of a one-dimensional problem that relies on approximating
an unknown real parameter from its noisy observations. This problem is trivial
in the case of bounded noise, but far from that in the case of Gaussian noise,
cf. [1, 2]. Some difficulty in showing lower bounds adds the fact that in the
case of random noise one has to consider deterministic as well as randomized
approximations. Indeed, although randomization is formally not allowed in the
problem formulation, it can be mimicked with the help of adaption, cf. [7, 8].

The paper is organized as follows. The scene is formally set in Section 2. The
results for bounded noise are in Section 3, and those for Gaussian noise in
Section 4. The Appendix contains some additional material concerning the
optimal choice of information functionals in the case of bounded and Gaussian
noise.

##  2\. Preliminaries

We consider a _multivariate problem_ $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}$ where

$S_{d}:F_{d}\to G_{d},$

$F_{d}$ and $G_{d}$ are separable Hilbert spaces, both over the reals, and
$S_{d}$ are nonzero continuous linear operators with norms

$\|S_{d}\|=\sup_{\|f\|_{F_{d}}\leq 1}\|S_{d}(f)\|_{G_{d}}.$

###  2.1. Information and approximation

The values $S_{d}(f)$ for $f\in F_{d}$ are approximated based on information
$\mathbf{y}=(y_{1},y_{2},\ldots,y_{n})\in\mathbb{R}^{n}$ about $f,$ which
consists of finitely many noisy values of some functionals at $f.$ That is,

$y_{i}=L_{i}(f)+e_{i},\quad 1\leq i\leq n,$

where $L_{i}$ are in a class $\Lambda_{d}\subset F_{d}^{*}$ of permissible
functionals, and $e_{i}$ is noise. A crucial assumption of the current paper
is that arbitrary continuous functionals with norm at most one are allowed,

$\Lambda_{d}=\\{L\in F_{d}^{*}:\,\|L\|\leq 1\\},$

where $\|L\|=\sup_{\|f\|_{F_{d}}\leq 1}|L(f)|.$ The noise can be deterministic
(bounded) or random (Gaussian),

$|e_{i}|\leq\sigma_{i}\quad\mbox{or}\quad e_{i}\stackrel{{\scriptstyle
iid}}{{\sim}}\mathcal{N}(0,\sigma_{i}^{2}),$

where $\sigma_{i}$ represents precision of the $i$th evaluation, and
$\mathcal{N}(0,\sigma)$ is the standard zero-mean Gaussian distribution with
variance $\sigma^{2}.$ Then an approximation to $S_{d}(f)$ is given as
$\Phi(\mathbf{y}),$ where

$\Phi:Y\to G_{d},$

called an _algorithm_ , is an arbitrary mapping acting on the set $Y$ of all
possible values of information.

We now describe the information more formally. We first deal with
_nonadaptive_ (or parallel) information, in which case the functionals $L_{i}$
and precisions $\sigma_{i}$ are the same for all problem instances $f\in
F_{d}.$ In the case of bounded noise, nonadaptive information is a multi-
valued operator, i.e., $N:F_{d}\to 2^{Y},$ where $2^{Y}$ is the power set of
$Y=\mathbb{R}^{n},$ and

$N(f)=\big{\\{}\big{(}L_{1}(f)+e_{1},L_{2}(f)+e_{2},\ldots,L_{n}(f)+e_{n}\big{)}:\;|e_{i}|\leq\sigma_{i},\,1\leq
i\leq n\big{\\}}.$

Then $\mathbf{y}$ is information about $f$ iff $\mathbf{y}\in N(f).$

In case of Gaussian noise, nonadaptive information $\mathbf{y}$ about $f$ is a
realization of the random variable with $n$ dimensional Gaussian distribution
$\pi_{f}$ whose mean element is $m_{f}=(L_{1}(f),\ldots,L_{n}(f))$ and
correlation matrix
$\Sigma=\mathrm{diag}(\sigma_{1}^{2},\ldots,\sigma_{n}^{2}).$ Therefore
nonadaptive information is now a mapping $N:F_{d}\to\mathcal{P}(Y),$ where
$\mathcal{P}(Y)$ is a set of probability distributions on the Borel sets of
$Y=\mathbb{R}^{n},$ and

$N(f)=\pi_{f}\quad\mbox{for}\quad f\in F_{d}.$

Although we will mainly exploit nonadaptive information in this paper, in a
generic approximation scheme we also allow a more general _adaptive_ (or
sequential) information, where the choice of the successive functionals
$L_{i}$ and precisions $\sigma_{i},$ as well as the number of them, depend on
$f$ and noise via the previously obtained values $y_{1},\ldots,y_{i-1}.$ The
process of obtaining adaptive information $\mathbf{y}=(y_{1},\ldots,y_{n})$
about $f$ can be schematically described as follows:

(6)
$\displaystyle\left\\{\;\begin{array}[]{llll}y_{1}&=&L_{1}(f)+e_{1},&\quad\sigma_{1},\\\
y_{2}&=&L_{2}(f;y_{1})+e_{2},&\quad\sigma_{2}(y_{1}),\\\
y_{3}&=&L_{3}(f;y_{1},y_{2})+e_{3},&\quad\sigma_{3}(y_{1},y_{2}),\\\
&\cdots&&\\\
y_{n}&=&L_{n}(f;y_{1},y_{2},\ldots,y_{n-1})+e_{n},&\quad\sigma_{n}(y_{1},y_{2},\ldots,y_{n-1}),\end{array}\right.$

where $L_{i}(\,\cdot\,;y_{1},\ldots,y_{i-1})\in\Lambda_{d}.$ The process
terminates when $(y_{1},y_{2},\ldots,y_{n})\in Y,$ where the set $Y$ of all
values of information consists of finite sequences of (possibly) various
lengths. For the termination criterion to be well defined we assume that for
any infinite sequence $(y_{1},y_{2},y_{3}\ldots)$ there is exactly one $n$
such that $(y_{1},\ldots,y_{n})\in Y.$ The corresponding operator $N$ is for
both, bounded and Gaussian noise, determined by the above construction. (In
case of Gaussian noise appropriate measurability assumptions on $L(f;\,\cdot)$
and $\sigma_{i}(\cdot)$ have to be met.) For details, see [6, Sect. 2.7 &
3.7].

###  2.2. Cost function

We assume that we are free to choose the information functionals and
precisions, but we have to pay more for more accurate evaluations. That is,
the cost of a single noisy evaluation of $L(f)$ for $f\in F_{d}$ with
precision $\sigma$ equals $\$(\sigma,d),$ where

$\$:[0,+\infty)\times\\{1,2,3,\ldots\\}\to[1,+\infty]$

is a _cost function_ that is non-decreasing in both $\sigma^{-1}$ and $d.$
Note that $\$\geq 1,$ which corresponds to a natural assumption that one has
to pay at least one unit even for ‘slightest touch’ of a functional. For
instance,

$\$(\sigma,d)=\left\\{\begin{array}[]{rl}+\infty,&0\leq\sigma<\sigma_{0},\\\
1,&\sigma_{0}\leq\sigma,\end{array}\right.$

corresponds to the situation when one can only observe with precision
$\sigma_{0}$ at cost $1$. If, in addition, $\sigma_{0}=0$ then information is
exact at the unit cost for all $\sigma\geq 0$ and $d\geq 1.$ We distinguish
several types of cost functions depending on how they grow as $\sigma^{-1}$
and $d$ increase. In particular, we have:

  * •

polynomial growth in $\sigma^{-1}$ and $d$ iff

$\$(\sigma,d)\leq 1+Dd^{t}\sigma^{-s}\quad\mbox{for all}\;\,d\geq
1\;\mbox{and}\;\sigma\in(0,1),$

where $D,t,s$ are some nonnegative numbers,

  * •

sub-exponential growth in $\sigma^{-1}+d$ iff

$\lim_{\sigma^{-1}+d\to\infty}\frac{\ln\$(\sigma,d)}{\sigma^{-1}+d}=0,$

  * •

exponential growth in $\sigma^{-1}+d$ iff

$\limsup_{\sigma^{-1}+d\to\infty}\frac{\ln\$(\sigma,d)}{\sigma^{-1}+d}>0.$

We will also consider corresponding growths in only one of the variables,
$\sigma^{-1}$ or $d,$ with the other variable fixed. For instance, we have
polynomial growth in $\sigma^{-1}$ iff $\$(\sigma,d)\leq D\psi(d)\sigma^{-s}$
for all $d\geq 1$ and $\sigma\in(0,1),$ or we have sub-exponential growth in
$d$ iff $\lim_{d\to\infty}\ln\$(\sigma,d)/d=0$ for all $\sigma\in(0,1).$

A total cost $\mathrm{cost}^{\mathrm{sett}}_{\$}(N)$ of given information $N$
and error $\mathrm{e}^{\mathrm{sett}}(S_{d},N,\Phi)$ of an algorithm $\Phi$
using it depend on a setting under consideration, and will be defined
separately for each setting. The settings ware distinguished by whether we
have bounded or Gaussian noise.

###  2.3. Tractability notions

For a given setting, let

$\mathrm{comp}^{\mathrm{sett}}_{\$}(\varepsilon,d)=\inf\big{\\{}\mathrm{cost}^{\mathrm{sett}}_{\$}(N):\,N,\Phi\;\mbox{such
that}\;\mathrm{e}^{\mathrm{sett}}(S_{d},N,\Phi)\leq\varepsilon\|S_{d}\|\,\big{\\}}$

be the minimal cost of information sufficient to approximate $S_{d}$ with
(normalized) error $\varepsilon.$ We call
$\mathrm{comp}^{\mathrm{sett}}_{\$}(\varepsilon,d)$ the _information
$(\varepsilon,d)$-complexity_, or simply _$(\varepsilon,d)$ -complexity_ of
our problem. We consider the following tractability notions, cf. [3].

  * •

A multivariate problem $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}$ is _polynomially
tractable_ iff

(7) $\mathrm{comp}^{\mathrm{sett}}_{\$}(\varepsilon,d)\leq
Cd^{q}\varepsilon^{-p}\quad\mbox{for all}\;\,d\geq
1\;\mbox{and}\;\varepsilon\in(0,1),$

where $C,q,p$ are some nonnegative numbers. If, in addition, (7) holds with
$q=0$ then the problem is _strongly polynomially tractable_ , and the infimum
of $p$ satisfying (7) with $q=0$ is the _strong exponent_.

  * •

A problem is _weakly tractable_ iff

$\lim_{\varepsilon^{-1}+d\to+\infty}\frac{\ln\left(\mathrm{comp}^{\mathrm{sett}}_{\$}(\varepsilon,d)\right)}{\varepsilon^{-1}+d}=0.$

  * •

A problem is _intractable_ iff it is not weakly tractable.

  * •

A problem suffers from the _curse of dimensionality_ iff there are
$\varepsilon_{0}>0,$ $C>0,$ and $\gamma>0,$ such that for infinitely many $d$
we have

$\mathrm{comp}^{\mathrm{sett}}_{\$}(\varepsilon_{0},d)\geq C(1+\gamma)^{d}.$

Equivalently, we have the curse iff there is $\varepsilon_{0}>0$ such that

$\limsup_{d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{sett}}_{\$}(\varepsilon_{0},d)\big{)}}{d}>0.$

We will later draw conclusions about tractability in the case of noisy
information assuming we know tractability for exact information. As we already
noticed, in the latter case we have $\$(\sigma,d)=1,$ which means that we just
count the number of functional evaluations. In the two settings considered in
this paper the complexities in the case of exact information are the same and
denoted by

$\mathrm{n}^{\mathrm{w}}(\varepsilon,d),$

where ‘$\mathrm{w}$’ stands for ‘worst’.

##  3\. Worst case setting with bounded noise

In this section we assume that the noise is bounded. That is, information
about $f$ is given as $\mathbf{y}=(y_{1},y_{2},\ldots,y_{n(\mathbf{y})})$
where

$y_{i}=L_{i}(f;y_{1},\ldots,y_{i-1})+e_{i},\qquad|e_{i}|\leq\sigma_{i}(y_{1},\ldots,y_{i-1}).$

The (total) cost of information $N$ is defined as

$\mathrm{cost}^{\mathrm{ww}}_{\$}(N)=\sup_{\|f\|_{F_{d}}\leq
1}\,\sup_{\mathbf{y}\in
N(f)}\sum_{i=1}^{n(\mathbf{y})}\$(\sigma_{i}(y_{1},\ldots,y_{i-1})),$

and the error of an algorithm $\Phi$ using information $N$ as

$\mathrm{e}^{\mathrm{ww}}(S_{d},N,\Phi)=\sup_{\|f\|_{F_{d}}\leq
1}\,\sup_{\mathbf{y}\in N(f)}\|S_{d}(f)-\Phi(\mathbf{y})\|_{G_{d}}.$

We assume that $S_{d}$ is a _compact_ operator which, as well known, is
necessary if we want to assure that
$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)<+\infty$ for all
$\varepsilon>0.$

We now recall some auxiliary facts about the current setting that can be
found, e.g., in [6].

Let $N:F_{d}\to 2^{Y}$ be arbitrary information and
$\mathrm{rad}^{\mathrm{ww}}(N)$ be its _radius_ , i.e., the minimal error that
can achieved using $N.$ If $N$ is nonadaptive and uses $n$ functionals $L_{i}$
with precisions $\sigma_{i}$ then

(8)
$\mathrm{rad}^{\mathrm{ww}}(N)=\max\big{\\{}\|S_{d}(h)\|_{G_{d}}:\;\|h\|_{F_{d}}\leq
1,\,|L_{i}(h)|\leq\sigma_{i},\,1\leq i\leq n\big{\\}}.$

Next we notice that we can restrict our considerations to algorithms using
nonadaptive information. Indeed, for any adaptive information
$N^{\mathrm{ada}}$ of the form (6) and with range $Y^{\mathrm{ada}}$ one can
define nonadaptive information $N^{\mathrm{non}}$ with range
$Y^{\mathrm{non}}=\mathbb{R}^{n}$ where $n$ is such that
$(\underbrace{0,\ldots,0}_{n})\in Y^{\mathrm{ada}}$ and

$(y_{1},\ldots,y_{n})\in N^{\mathrm{non}}(f)\quad\mbox{ iff }\quad
y_{i}=L_{i}(f;\underbrace{0,\ldots,0}_{i-1})+e_{i},\;|e_{i}|\leq\sigma_{i}(\underbrace{0,\ldots,0}_{i-1}),\quad
1\leq i\leq n.$

Then
$\mathrm{rad}^{\mathrm{ww}}(N^{\mathrm{non}})\leq\mathrm{rad}^{\mathrm{ww}}(N^{\mathrm{ada}})$
and
$\mathrm{cost}^{\mathrm{ww}}_{\$}(N^{\mathrm{non}})\leq\mathrm{cost}^{\mathrm{ww}}_{\$}(N^{\mathrm{ada}}),$
which means that adaption does not help. This and (8) imply that

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)=\inf\big{\\{}\mathrm{cost}^{\mathrm{ww}}_{\$}(N):\,N\mbox{-nonadaptive},\;\mathrm{rad}^{\mathrm{ww}}(N)\leq\varepsilon\|S_{d}\|\big{\\}}.$

To avoid notational difficulties, from now on we assume that
$\mathrm{dim}(F_{d})=+\infty,$ which can obviously be done without loss of
generality. Let $\\{f_{d,j}^{*}\\}_{j\geq 1}$ be the complete orthonormal
system of eigenelements of $S_{d}^{*}S_{d}:F_{d}\to F_{d},$ and

$\lambda_{d,1}\geq\lambda_{d,2}\geq\cdots\geq\lambda_{d,j}\geq\cdots$

the corresponding eigenvalues. We have $\|S_{d}\|=\sqrt{\lambda_{d,1}}$ and
$\lim_{j\to\infty}\lambda_{d,j}=0.$ Furthermore, in the noiseless case,
information

(9)
$N_{n}^{d}=\big{(}\langle\,\cdot\,,f_{d,1}^{*}\rangle_{F_{d}},\ldots,\langle\,\cdot\,,f_{d,n}^{*}\rangle_{F_{d}}\big{)}$

is $n$th optimal, and its radius
$\mathrm{rad}^{\mathrm{w}}(N_{n}^{d})=\sqrt{\lambda_{d,n+1}},$ cf. [3]. Hence

(10)
$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)=\min\big{\\{}n:\,\sqrt{\lambda_{d,n+1}}\leq\varepsilon\sqrt{\lambda_{d,1}}\,\big{\\}}.$

We first show a general though important result that will be used later.

######  Lemma 1.

For all $\varepsilon\in(0,1)$ and $d\geq 1$ we have

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\geq\sum_{k=1}^{\mathrm{n}^{\mathrm{w}}(\varepsilon,d)}\$\left(\varepsilon\sqrt{\tfrac{\lambda_{d,1}}{\lambda_{d,k}}},d\right).$

Hence,
$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\geq\max\big{\\{}\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\$(1,d),\,\$(\varepsilon,d)\big{\\}}.$

###### Proof.

Let $N$ be nonadaptive information using $m$ functionals $L_{i}$ with
precisions $\sigma_{i},$ such that
$\mathrm{rad}^{\mathrm{ww}}(N)\leq\varepsilon\|S_{d}\|.$ Assume without loss
of generality that $\sigma_{1}\leq\sigma_{2}\leq\cdots\leq\sigma_{m}.$ To
prove the lemma, it suffices to show that

$\sigma_{k}\leq\varepsilon\sqrt{\tfrac{\lambda_{d,1}}{\lambda_{d,k}}}<1,\qquad
1\leq k\leq\mathrm{n}^{\mathrm{w}}(\varepsilon,d).$

Let $k$ be as above. The inequality ‘$<$’ follows from (10). To show ‘$\leq$’,
define the linear subspace

$V_{k-1}=\big{\\{}f\in F:\;L_{i}(f)=0,\;1\leq i\leq
k-1\,\big{\\}}\qquad(\mbox{where}\;V_{k-1}=F\;\mbox{if}\;k=1).$

Obviously $\mathrm{codim}(V_{k-1})\leq k-1.$ Since for any $h$ with
$\|h\|_{F_{d}}\leq\sigma$ is $|L_{i}(h)|\leq\sigma,$ we have

$\displaystyle{\mathrm{rad}^{\mathrm{ww}}(N_{n})}$ $\displaystyle\geq$
$\displaystyle\max\\{\|S_{d}(h)\|_{F_{d}}:\;\|h\|_{F_{d}}\leq 1,\,h\in
V_{k-1},\,|L_{i}(h)|\leq\sigma_{i},\,k\leq i\leq m\\}$ $\displaystyle\geq$
$\displaystyle\max\\{\|S_{d}(h)\|_{F_{d}}:\;\|h\|_{F_{d}}\leq\sigma_{k},\,h\in
V_{k-1}\\}\,\geq\,\sigma_{k}\sqrt{\lambda_{d,k}},$

where we used the fact that the norm of $S_{d}$ restricted to the subspace
$V_{k-1}$ is at least $\sqrt{\lambda_{k}}.$ Hence
$\sigma_{k}\leq\varepsilon\sqrt{\tfrac{\lambda_{d,1}}{\lambda_{d,k}}}$ since
otherwise we would have
$\mathrm{rad}^{\mathrm{ww}}(N)>\varepsilon\sqrt{\lambda_{d,1}}=\varepsilon\|S_{d}\|.$
∎

To achieve upper bounds on tractability, we will use noisy version of the
nonadaptive information $N_{n}^{d}$ defined in (9). That is, for given $d,n$
and $\sigma_{i}$ we have $\mathbf{y}=(y_{1},\ldots,y_{n})\in N^{d}_{n}(f)$ iff

(11) $y_{i}=\langle
f,f_{d,i}^{*}\rangle_{F_{d}}+e_{i},\quad\mbox{where}\quad|e_{i}|\leq\sigma_{i}.$

The radius of $N_{n}^{d}$ can be estimated from above by the error of the
approximation

$\Phi^{d}_{n}(\mathbf{y})=\sum_{i=1}^{n}y_{i}S_{d}(f_{d,i}^{*}).$

Specifically, using $f=\sum_{i=1}^{\infty}\langle
f,f_{d,i}^{*}\rangle_{F_{d}}f_{d,i}^{*}$ and orthogonality of
$\\{S_{d}(f_{d,i}^{*})\\}_{i\geq 1}$ in $G_{d}$ we have

$\displaystyle\|S_{d}(f)-\Phi^{d}_{n}(\mathbf{y})\|_{G_{d}}^{2}$
$\displaystyle=$
$\displaystyle\bigg{\|}-\sum_{i=1}^{n}e_{i}S_{d}(f_{d,i}^{*})+\sum_{i=n+1}^{+\infty}\langle
f,f_{d,i}\rangle_{F_{d}}S_{d}(f_{d,i}^{*})\bigg{\|}_{G_{d}}^{2}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\lambda_{d,i}|e_{i}|^{2}+\sum_{i=n+1}^{+\infty}\lambda_{d,i}\big{|}\langle
f,f_{d,i}^{*}\rangle_{F_{d}}\big{|}^{2}.$

Taking the suprema with respect to $\|f\|_{F_{d}}\leq 1$ and
$|e_{i}|\leq\sigma_{i}$ we obtain

(12)
$\mathrm{e}^{\mathrm{ww}}(N^{d}_{n},\Phi^{d}_{n})=\sqrt{\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{d,i}+\lambda_{d,n+1}}.$

In particular, for exact information we restore the known result that
$\mathrm{e}^{\mathrm{ww}}(S_{d},N^{d}_{n},\Phi^{d}_{n})=\sqrt{\lambda_{d,n+1}},$
which is the minimal error when $n$ exact functional evaluations are used. The
cost of such approximation is obviously $\sum_{i=1}^{n}\$(\sigma_{i},d).$

###  3.1. Polynomial tractability

We use the following asymptotic notation. For two nonnegative functions of
$\varepsilon$ and $d$ we write

$\psi_{1}(\varepsilon,d)\preccurlyeq\psi_{2}(\varepsilon,d)\qquad\mbox{iff}\qquad{\psi_{1}(\varepsilon,d)}\leq
A\,{\psi_{2}(\varepsilon,d)},$

for some $A<+\infty$ and all $\varepsilon\in(0,1)$ and $d\geq 1.$

######  Theorem 1.

Consider a multivariate problem $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}.$

  * (i)

The problem with noisy information is polynomially tractable if and only if

    * $\bullet$

it is polynomially tractable for exact information, and

    * $\bullet$

the cost function grows polynomially in $\sigma^{-1}$ and $d.$

  * (ii)

The problem with noisy information is strongly polynomially tractable if and
only if

    * $\bullet$

it is strongly polynomially tractable for exact information, and

    * $\bullet$

the cost function grows polynomially in $\sigma^{-1}$ and is bounded in $d$
for any $\sigma>0.$

  * (iii)

Suppose that $\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq
Cd^{q}\varepsilon^{-p}$ and $\$(\sigma,d)\leq 1+Dd^{t}\sigma^{-2s}.$
If $p=0$ and $s=0$ then
$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\preccurlyeq d^{t+q};$
otherwise

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\,\preccurlyeq\,d^{t+q(s+1)}\left\\{\begin{array}[]{rl}\varepsilon^{-p(s+1)},&\;p(s+1)>2s,\\\
\ln^{s+1}(1/\varepsilon)\,\varepsilon^{-2s},&\;p(s+1)=2s,\\\
\varepsilon^{-2s},&\;p(s+1)<2s.\end{array}\right.$

###### Proof.

Suppose that the problem is polynomially tractable for noisy information,
i.e.,

$\mathrm{comp}^{\mathrm{ww}}(\varepsilon,d)\leq Cd^{q}\varepsilon^{-p}.$

Then we have by Lemma 1 that, on one hand,

$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq\mathrm{comp}^{\mathrm{ww}}(\varepsilon,d)\leq
Cd^{q}\varepsilon^{-p}$

and, on the other hand,

$\$(\sigma,d)\leq\mathrm{comp}^{\mathrm{ww}}(\sigma,d)\leq
1+Cd^{q}\sigma^{-p}.$

This proves the necessary conditions in (i) and (ii). The sufficient
conditions follow from (iii).

In the proof of (iii) we distinguish several cases.

If $s=0$ and $p\geq 0$ then exact observations are possible at cost
$1+Dd^{t},$ and therefore

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\leq(1+Dd^{t})\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq(1+D)Cd^{t+q}\varepsilon^{-p}\preccurlyeq
d^{t+q}\varepsilon^{-p}.$

Assume $s>0.$ We first optimize the cost of obtaining an
$\varepsilon$-approximation using information $N_{n}^{d}$ with precisions
$\sigma_{i}\leq 1$ together with the algorithm $\Phi_{n}^{d}.$ Let
$\mathrm{e}^{\mathrm{ww}}(S_{d},N^{d}_{n},\Phi^{d}_{n})\leq\varepsilon\sqrt{\lambda_{1}}.$
The cost of $N_{n}^{d}$ is upper bounded by

$\psi_{n}(\sigma_{1},\ldots,\sigma_{n})=n+Dd^{t}\sum_{i=1}^{n}\sigma_{i}^{-2s}.$

Minimizing $\psi_{n}$ with respect to the condition
$\mathrm{e}^{\mathrm{ww}}(S_{d},N^{d}_{n},\Phi^{d}_{n})^{2}=\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{d,i}+\lambda_{d,n+1}\leq\lambda_{d,1}\varepsilon^{2}$
we obtain the optimal values

$\hat{\sigma}_{k}^{-2}=\bigg{(}\frac{\lambda_{d,k}}{\lambda_{d,1}}\bigg{)}^{\frac{1}{s+1}}\sum_{i=1}^{n}\bigg{(}\frac{\lambda_{d,i}}{\lambda_{d,1}}\bigg{)}^{\frac{s}{s+1}}\bigg{(}\varepsilon^{2}-\frac{\lambda_{d,n+1}}{\lambda_{d,1}}\bigg{)}^{-1},\qquad
1\leq k\leq n,$

and

$\psi_{n}(\hat{\sigma}_{1},\ldots,\hat{\sigma}_{n})=n+Dd^{t}\left(\sum_{i=1}^{n}\bigg{(}\frac{\lambda_{d,i}}{\lambda_{d,1}}\bigg{)}^{\frac{s}{s+1}}\right)^{s+1}\bigg{(}\varepsilon^{2}-\frac{\lambda_{d,n+1}}{\lambda_{d,1}}\bigg{)}^{-s}.$

Now, taking
$n=\max\big{(}2,\mathrm{n}^{\mathrm{w}}(\varepsilon/\sqrt{2},d)\big{)}$ we
have
$\frac{\lambda_{d,n+1}}{\lambda_{d,1}}\leq\frac{\varepsilon^{2}}{2}<\frac{\lambda_{d,n}}{\lambda_{d,1}}$
and

$\hat{\sigma}_{k}^{-2}\geq\hat{\sigma}_{n}^{-2}=\bigg{(}\frac{\lambda_{d,n}}{\lambda_{d,1}}\bigg{)}^{\frac{1}{s+1}}\sum_{i=1}^{n}\bigg{(}\frac{\lambda_{d,i}}{\lambda_{d,1}}\bigg{)}^{\frac{s}{s+1}}\bigg{(}\varepsilon^{2}-\frac{\lambda_{d,n+1}}{\lambda_{d,1}}\bigg{)}^{-1}\geq
n\bigg{(}\frac{\lambda_{d,n}}{\lambda_{d,1}}\bigg{)}\varepsilon^{-2}>\frac{n}{2}\geq
1,$

i.e., $0<\sigma_{1}\leq\cdots\leq\sigma_{n}<1.$ Then an
$\varepsilon$-approximation is obtained at cost

(13)
$\mathrm{cost}^{\mathrm{ww}}_{\$}(N_{n}^{d})\,\leq\,n+2^{s}Dd^{t}\left(\sum_{i=1}^{n}\left(\frac{\lambda_{d,i}}{\lambda_{d,1}}\right)^{\frac{s}{s+1}}\right)^{s+1}\varepsilon^{-2s}.$

Assume now that we have polynomial tractability for exact information, i.e.,

$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq
Cd^{q}\varepsilon^{-p}\quad\mbox{for}\;d\geq
1\;\mbox{and}\;\varepsilon\in(0,1).$

If $p=0$ then $\lambda_{j}=0$ for $j\geq\lfloor Cd^{q}\rfloor+1$ and we have
from (13) that

$\mathrm{cost}^{\mathrm{ww}}_{\$}(N_{n}^{d})\,\preccurlyeq\,d^{t}\big{\lfloor}Cd^{q}\big{\rfloor}^{s+1}\varepsilon^{-2s}\,\preccurlyeq\,d^{t+q(s+1)}\varepsilon^{-2s}.$

Assume $p>0.$ We need to estimate the ratios $\lambda_{d,j}/\lambda_{d,1}.$
For $1\leq j\leq\lfloor Cd^{q}\rfloor+1$ we have
$\lambda_{d,j}/\lambda_{d,1}\leq 1.$ Let $j\geq\lfloor Cd^{q}\rfloor+2.$ Let
$\varepsilon_{j}\in(0,1)$ be such that $j=Cd^{q}\varepsilon_{j}^{-p}+1.$ Then
$j-1\geq\mathrm{n}^{\mathrm{w}}(\varepsilon_{j},d),$ which implies

$\sqrt{\frac{\lambda_{d,j}}{\lambda_{d,1}}}\leq\varepsilon_{j}=\left(\frac{Cd^{q}}{j-1}\right)^{1/p}.$

Hence for all $j\geq 1$

(14)
$\frac{\lambda_{d,j}}{\lambda_{d,1}}\leq\min\left(1,\Big{(}\frac{Cd^{q}}{j-1}\Big{)}^{2/p}\right).$

Assuming $C\geq 2$ (which can be done without loss of generality) the
estimates (13) and (14) give

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\leq\left\lfloor
Cd^{q}\big{(}\tfrac{\varepsilon}{\sqrt{2}}\big{)}^{-p}\right\rfloor+2^{s}Dd^{t}\Bigg{(}\lfloor
Cd^{q}\rfloor+1+\sum_{j=\lfloor Cd^{q}\rfloor+2}^{\left\lfloor
Cd^{q}({\varepsilon}/{\sqrt{2}})^{-p}\right\rfloor}\left(\frac{Cd^{q}}{j-1}\right)^{\frac{2s}{p(s+1)}}\Bigg{)}^{s+1}\left(\frac{1}{\varepsilon}\right)^{2s}.$

Using the formula

$\sum_{i=k+1}^{n}j^{-\beta}\leq\int_{k}^{n}x^{-\beta}\,\mathrm{d}x=\left\\{\begin{array}[]{rl}\ln
n-\ln k,&\quad\beta=1,\\\
\frac{n^{1-\beta}-k^{1-\beta}}{1-\beta},&\quad\beta\neq
1,\end{array}\right.\\\ $

with $2\leq k+1\leq n$ and $\beta=\frac{2s}{p(s+1)},$ we finally obtain the
desired upper bounds. ∎

######  Remark 1.

The algorithm $\Phi_{n}^{d}$ is not optimal for $N_{n}^{d}$ if information is
contaminated by noise (11). Indeed, we have by (8) that

$\displaystyle\mathrm{rad}^{\mathrm{ww}}(N_{n}^{d})$ $\displaystyle=$
$\displaystyle\max\bigg{\\{}\bigg{(}\sum_{i=1}^{\infty}a_{i}^{2}\lambda_{d,i}\bigg{)}^{1/2}:\;\sum_{i=1}^{n}a_{i}^{2}\leq
1,\;|a_{i}|\leq\sigma_{i},\,1\leq i\leq n\bigg{\\}}$ $\displaystyle=$
$\displaystyle\sqrt{\sum_{i=1}^{\ell}\sigma_{i}^{2}\lambda_{d,i}+\bigg{(}1-\sum_{i=1}^{\ell}\sigma_{i}^{2}\bigg{)}\lambda_{d,\ell+1}}\,=\,\sqrt{\sum_{i=1}^{\ell}\sigma_{i}^{2}(\lambda_{d,i}-\lambda_{d,\ell+1})+\lambda_{d,\ell+1}},$

where $\ell$ is the largest $k$ satisfying $\sum_{i=1}^{k}\sigma_{i}^{2}<1,$
cf. (12). Nevertheless, $\Phi_{n}^{d}$ gives optimal exponents of tractability
when one relies only on information $N_{n}^{d}.$

To see this, let $N_{m}^{d}$ be information (11) that uses precisions
$\sigma_{i}$ and whose radius is at most $\varepsilon\sqrt{\lambda_{d,1}}.$
Then $m\geq n=\mathrm{n}^{\mathrm{w}}(\varepsilon,d).$ A crucial observation
is that, in view of (10) and (1), we then have
$\sum_{i=1}^{n}\sigma_{i}^{2}\leq 1.$ Hence the cost of $N_{m}^{d}$ can be
lower bounded by minimization of $n+\sum_{i=1}^{n}\sigma_{i}^{-2s}$ (which
does not exceed $\mathrm{cost}^{\mathrm{ww}}(N_{m}^{d})$) with respect to the
condition
$\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{d,i}\leq\varepsilon^{2}\lambda_{d,1}$
(which is weaker than
$\mathrm{rad}^{\mathrm{ww}}(N_{m}^{d})\leq\varepsilon\sqrt{\lambda_{d,1}}$).
In this way we obtain

$\mathrm{cost}^{\mathrm{ww}}_{\$}(N_{m}^{d})\,\geq\,n+Dd^{t}\left(\sum_{i=1}^{n}\left(\frac{\lambda_{d,i}}{\lambda_{d,1}}\right)^{\frac{s}{s+1}}\right)^{s+1}\varepsilon^{-2s}.$

This bound differs from the upper bound in (13) at most by the factor of
$2^{s},$ which does not influence the exponents of polynomial tractability.

We believe that the tractability exponents in (iii) of Theorem 1 are best
possible, but a formal justification of this fact is missing. The point is
that these exponents are obtained using particular information $N_{n}^{d}.$ On
one hand, Proposition 1 of Appendix shows that this information is indeed
optimal in some situations, even if we fix precisions $\sigma_{i}.$ On the
other hand, the following example shows that the cost can be sometimes
significantly reduced by applying more sophisticated information.

######  Example 1.

Suppose we approximate vectors $\vec{x}=(x_{1},x_{2})^{T}\in\mathbb{R}^{2}$ in
the $\ell_{2}$ norm. Consider noisy information consisting of $2n$
observations $\mathbf{y}=(\vec{y}_{1}^{\,T},\ldots,\vec{y}_{n}^{\,T}),$ where

(16)
$\mathbb{R}^{2}\ni\,\vec{y}_{i}=(R_{i}\vec{x})^{T}+\vec{e}_{i}\,,\qquad\|\vec{e}_{i}\|_{\infty}\leq\sigma<1,$

and

$R_{i}=\left(\begin{array}[]{rr}\cos\theta_{i}&-\sin\theta_{i}\\\
\sin\theta_{i}&\cos\theta_{i}\end{array}\right),\qquad\theta_{i}=\frac{\pi(i-1)}{2n},\qquad
1\leq i\leq n,$

is the clockwise rotation through the angle $\theta_{i}.$ Note that $n=1$
corresponds to $\mathbf{y}=\vec{x}+\vec{e},$
$\|\vec{e}\,\|_{\infty}\leq\sigma,$ which is the information exploited in the
proof of Theorem 1 for this particular problem.

Using geometrical arguments one can easily show that, given $n\geq 1$ and
$\varepsilon\in(0,1),$ one has to use precision
$\sigma_{n}(\varepsilon)=\varepsilon\cos\big{(}\frac{\pi}{4n}\big{)}$ to get
an $\varepsilon$-approximation of $\vec{x},$ and then the cost of the
$\varepsilon$-approximation equals
$\mathrm{cost}(n,\varepsilon)=2n\$(\sigma_{n}(\varepsilon)),$ where $\$$ is a
cost function. Let $\$(\sigma)=1+\sigma^{-2s}$ with $s>0.$ Then the cost is

(17)
$\mathrm{cost}_{s}(n,\varepsilon)=2n\left(1+\big{(}\varepsilon\cos(\tfrac{\pi}{4n})\big{)}^{-2s}\right).$

Taking $n^{*}=\big{\lceil}\frac{\pi}{4}\sqrt{2s}\,\big{\rceil}$ we have the
asymptotic equality

$\mathrm{cost}_{s}(n^{*},\varepsilon)\approx\pi\sqrt{\frac{s}{2}}\left(1+\sqrt{\mathrm{e}}\,\varepsilon^{-2s}\right)\quad\mbox{as}\quad
s\to\infty,$

where we used the fact that $\lim_{x\to 0}\left(\cos
x\right)^{-1/x^{2}}=\sqrt{\mathrm{e}}.$ Hence for $0<\varepsilon<1$ we have

$\frac{\mathrm{cost}_{s}(1,\varepsilon)}{\mathrm{cost}_{s}(n^{*},\varepsilon)}\approx\frac{2\big{(}1+2^{s}\varepsilon^{-2s}\big{)}}{\pi\sqrt{s/2}\,\big{(}1+\sqrt{\mathrm{e}}\,\varepsilon^{-2s}\big{)}}\approx\frac{2^{s+1}}{\pi\sqrt{s\,\mathrm{e}/2\,}}\,.$

As we can see, for large $s$ the ‘rotated’ information offers a serious
improvement compared to the ‘un-rotated’ information consisting of only $2$
observations as in the case of exact information.

###  3.2. Weak tractability and the curse of dimensionality

######  Theorem 2.

Consider a multivariate problem $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}.$

  * (i)

Suppose that the problem with noisy information is weakly tractable. Then

    * $\bullet$

it is weakly tractable for exact information, and

    * $\bullet$

the cost function grows sub-exponentially in $\sigma^{-1}+d.$

  * (ii)

Suppose that

    * $\bullet$

the problem is weakly tractable for exact information, and

    * $\bullet$

the cost function grows polynomially in $\sigma^{-1}$ and sub-exponentially in
$d.$

Then the same problem with noisy information is weakly tractable.

  * (iii)

Suppose that

    * $\bullet$

the problem is strongly polynomially tractable for exact information with
$p<2,$ and

    * $\bullet$

the cost function grows sub-exponentially in $\sigma^{-1}+d.$

Then the same problem with noisy information is weakly tractable.

###### Proof.

To show (i) we use Lemma 1. On one hand we have
$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d),$
which implies

$\lim_{\varepsilon^{-1}+d\to\infty\,}\frac{\ln\big{(}\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\big{)}}{\varepsilon^{-1}+d}\leq\lim_{\varepsilon^{-1}+d\to\infty\,}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\big{)}-\ln\big{(}\$(1,d)\big{)}}{\varepsilon^{-1}+d}=0.$

On the other hand
$\$(\sigma,d)\leq\mathrm{comp}^{\mathrm{ww}}_{\$}(\sigma,d),$ which implies

$\lim_{\sigma^{-1}+d\to\infty\,}\frac{\ln\big{(}\$(\sigma,d)\big{)}}{\sigma^{-1}+d}\leq\lim_{\sigma^{-1}+d\to\infty\,}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\sigma,d)\big{)}}{\sigma^{-1}+d}=0.$

Now we show (ii). Suppose that $\$(\sigma,d)\leq 1+D\sigma^{-2s}\kappa(d)$
where $\lim_{d\to\infty}\ln\big{(}\kappa(d)\big{)}/d=0.$ Proceeding as in the
proof of (iii) of Theorem 1 we get from (13) that

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\leq
n+2^{s}D\,\kappa(d)\,n^{s+1}\varepsilon^{-2s}\quad\mbox{where}\quad
n=\mathrm{n}^{\mathrm{w}}\big{(}\varepsilon/\sqrt{2},d\big{)}.$

Hence, if the problem is weakly tractable for exact information, then

$\displaystyle\lim_{\varepsilon^{-1}+d\to\infty\,}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\big{)}}{\varepsilon^{-1}+d}$
$\displaystyle=$
$\displaystyle\lim_{\varepsilon^{-1}+d\to\infty\,}\frac{\ln\big{(}\kappa(d)\big{)}+(s+1)\ln
n+2s\ln(1/\varepsilon)}{\varepsilon^{-1}+d}$ $\displaystyle=$
$\displaystyle(s+1)\lim_{\varepsilon^{-1}+d\to\infty\,}\frac{\ln\big{(}\mathrm{n}^{\mathrm{w}}(\varepsilon/\sqrt{2},d)\big{)}}{\varepsilon^{-1}+d}=0,$

which means that the problem with noisy information is also weakly tractable.

To show (iii), suppose that the problem with noisy information is strongly
tractable for exact information, $\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq
C\varepsilon^{-p}$ where $p<2.$ Then, by (14),

$A:=\sum_{j=1}^{\infty}\frac{\lambda_{d,j}}{\lambda_{d,1}}\leq
1+C^{2/p}\sum_{j=1}^{\infty}j^{-2/p}\leq 1+\frac{p\,C^{2/p}}{2-p}<+\infty.$

Let

$n=\mathrm{n}^{\mathrm{w}}\bigg{(}\frac{\varepsilon}{\sqrt{2}},d\bigg{)}\leq
C\bigg{(}\frac{\sqrt{2}}{\varepsilon}\bigg{)}^{p}.$

For the algorithm $\Phi_{n}^{d}$ using noisy information $N_{n}^{d}$ with
fixed precision $\sigma=\frac{\varepsilon}{\sqrt{2A}}$ we have by (12) that

$\mathrm{e}^{\mathrm{ww}}(S_{d},N_{n}^{d},\Phi_{n}^{d})=\sqrt{\sigma^{2}\sum_{i=1}^{n}\lambda_{d,i}+\lambda_{d,n+1}}\leq\sqrt{\lambda_{d,1}}\,\sqrt{\sigma^{2}A+\frac{\lambda_{d,n+1}}{\lambda_{d,1}}}\leq\sqrt{\lambda_{d,1}}\,\sqrt{\frac{1}{2}\varepsilon^{2}+\frac{1}{2}\varepsilon^{2}}=\sqrt{\lambda_{d,1}}\,\varepsilon,$

and

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\leq\mathrm{cost}^{\mathrm{ww}}(N_{n}^{d})=n\,\$\bigg{(}\frac{\varepsilon}{\sqrt{2A}},d\bigg{)}\leq
C\bigg{(}\frac{\sqrt{2}}{\varepsilon}\bigg{)}^{p}\$\bigg{(}\frac{\varepsilon}{\sqrt{2A}},d\bigg{)}.$

Hence

$\displaystyle\lim_{\varepsilon^{-1}+d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\big{)}}{\varepsilon^{-1}+d}$
$\displaystyle\leq$ $\displaystyle\lim_{\varepsilon^{-1}+d\to\infty}\frac{\ln
C+p\big{(}\tfrac{1}{2}\ln
2+\ln(\frac{1}{\varepsilon})\big{)}+\ln\$\big{(}\frac{\varepsilon}{\sqrt{2A}},d\big{)}}{\varepsilon^{-1}+d}$
$\displaystyle=$
$\displaystyle\sqrt{2A}\lim_{\varepsilon^{-1}+d\to\infty}\,\frac{\ln\$\big{(}\frac{\varepsilon}{\sqrt{2A}},d\big{)}}{\frac{\sqrt{2A}}{\varepsilon}+d\sqrt{2A}}=0,$

where we used sub-exponential growth of the cost function. ∎

######  Remark 2.

The sufficient conditions in (iii) of Theorem 2 for weak tractability in the
case of noisy information can be generalized as follows. Suppose that

$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq C\varepsilon^{-p}\kappa(d),$

where $\kappa(d)$ grows sub-exponentially in $d.$ Then

$A_{n}^{d}:=\sum_{j=1}^{n}\frac{\lambda_{d,j}}{\lambda_{d,1}}\,\preccurlyeq\,\big{(}\kappa(d)\big{)}^{\frac{2}{p}}\left\\{\begin{array}[]{ll}1,&\;p<2,\\\
\ln n,&\;p=2,\\\ n^{1-2/p},&\;p>2.\end{array}\right.$

Applying the information $N_{n}^{d}$ and algorithm $\Phi_{n}^{d}$ with
$n=\mathrm{n}^{\mathrm{w}}(\frac{\varepsilon}{\sqrt{2}},d)$ and fixed
precision $\sigma=\frac{\varepsilon}{\sqrt{A_{n}^{d}}},$ as in the proof of
Theorem 2, we obtain that
$\mathrm{e}^{\mathrm{ww}}(S_{d},N_{n}^{d},\Phi_{n}^{d})\leq\sqrt{\lambda_{d,1}}\,\varepsilon$
and

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\leq\mathrm{cost}^{\mathrm{ww}}(N_{n}^{d})\preccurlyeq\varepsilon^{-p}\kappa(d)\,\$\big{(}\hat{\varepsilon},d\big{)},$

where

$\hat{\varepsilon}=\hat{\varepsilon}(\varepsilon,d)=\left\\{\begin{array}[]{ll}\varepsilon\,\big{(}\kappa(d)\big{)}^{-1/p},&\;p<2,\\\
\varepsilon\,\big{(}\kappa(d)\ln(\kappa(d)\varepsilon^{-2}\big{)}^{-1/2},&\;p=2,\\\
\varepsilon^{p/2}\big{(}\kappa(d)\big{)}^{-1/2},&\;p>2.\end{array}\right.$

Hence the problem is weakly tractable for noisy information if the cost
function satisfies

(18)
$\lim_{\varepsilon^{-1}+d\to\infty}\,\frac{\ln\$\big{(}\hat{\varepsilon},d\big{)}}{\varepsilon^{-1}+d}=0.$

Observe that (iii) of Theorem 2 is obtained by taking $p<2$ and $\kappa(d)=1,$
in which case $\hat{\varepsilon}=\varepsilon.$

It is not clear whether the condition (18) is not only sufficient, but also
necessary for weak tractability.

Since intractability is defined as the lack of weak tractability, necessary
and sufficient conditions for a problem to be intractable follow immediately
from Theorem 2. We move to the curse of dimensionality.

######  Theorem 3.

Consider a multivariate problem $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}.$

  * (i)

Suppose that

    * $\bullet$

the problem with exact information suffers from the curse of dimensionality,
or

    * $\bullet$

the cost function grows exponentially in $d$ for some $\sigma_{0}\geq 0.$

Then the same problem with noisy information also suffers from the curse.

  * (ii)

Suppose the problem with noisy information suffers from the curse of
dimensionality. Then

    * $\bullet$

the problem with exact information also suffers from the curse, or

    * $\bullet$

the cost function grows faster than polynomially in $\sigma^{-1},$ or grows
exponentially in $d.$

  * (iii)

Suppose the problem with noisy information suffers from the curse of
dimensionality. Then

    * $\bullet$

the problem is not strongly polynomially tractable for exact information, or

    * $\bullet$

the cost function grows exponentially in $d$ for some $\sigma_{0}\geq 0.$

###### Proof.

To show (i) it suffices to use again Lemma 1. If the curse is present for
exact information then, owing to
$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon_{0},d)\geq\mathrm{n}^{\mathrm{w}}(\varepsilon_{0},d)\$(1,1),$
it is also present for noisy information. If the cost function grows
exponentially in $d$ for some $\sigma_{0}>0$ then for
$\varepsilon_{0}=\sigma_{0}$ we have

$\limsup_{d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon_{0},d)\big{)}}{d}\geq\limsup_{d\to\infty}\frac{\ln\big{(}\$(\sigma_{0},d)\big{)}}{d}>0.$

To show (ii), assume that there is no curse for exact information, and
$\$(\sigma,d)\leq 1+D\sigma^{-2s}\kappa(d),$ where
$\lim_{d\to\infty}\ln(\kappa(d))/d=0.$ Then, applying the reasoning from the
proof (ii) of Theorem 2 we get that
$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\leq
n+2^{s}D\kappa(d)n^{s+1}\varepsilon^{-2s}$ with
$n=\mathrm{n}^{\mathrm{w}}(\varepsilon/\sqrt{2},d).$ Hence

$\lim_{d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\big{)}}{d}=(s+1)\lim_{d\to\infty}\frac{\ln\big{(}\mathrm{n}^{\mathrm{w}}(\varepsilon/\sqrt{2},d\big{)}}{d}=0,$

which means that the problem with noisy information does not suffer from the
curse.

And finally, to show (iii) we assume that the problem is strongly polynomially
tractably for exact information, i.e.,
$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq C\varepsilon^{-p},$ and that
$\$(\sigma,d)$ grows sub-exponentially in $d$ for all $\sigma>0.$ Using
$\sum_{j=1}^{n}\lambda_{d,j}/\lambda_{d,1}\leq n$ and proceeding as in the
proof of (iii) of Theorem 2 we obtain for
$n(\varepsilon)=\big{\lceil}C\big{(}\frac{\sqrt{2}}{\varepsilon}\big{)}^{p}\big{\rceil}$
that

$\lim_{d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\big{)}}{d}\leq\lim_{d\to\infty}\frac{\ln\$\big{(}\frac{\varepsilon}{2n(\varepsilon)},\,d\big{)}}{d}=0,$

which means that there is no curse for noisy information. ∎

##  4\. Worst case setting with Gaussian noise

In this section we assume that the noise is random. That is, information about
$f$ is given as $\mathbf{y}=(y_{1},y_{2},\ldots,y_{n(\mathbf{y})})$ where

$y_{i}=L_{i}(f;y_{1},\ldots,y_{i-1})+e_{i},\qquad
e_{i}\sim\mathcal{N}\big{(}0,\sigma_{i}^{2}(y_{1},\ldots,y_{i-1})\big{)},$

and the noise coming from different observations is independent. The (total)
cost of information $N=\\{\pi_{f}\\}_{f\in F},$ where $\pi_{f}$ is the
probability distribution of information $\mathbf{y}$ for given $f,$ is defined
as

$\mathrm{cost}^{\mathrm{wa}}_{\$}(N)=\sup_{\|f\|_{F_{d}}\leq
1}\,\int_{Y}\sum_{i=1}^{n(\mathbf{y})}\$\big{(}\sigma_{i}(y_{1},\ldots,y_{i-1})\big{)}\,\pi_{f}(\mathrm{d}\mathbf{y}),$

and the error of an algorithm $\Phi$ using information $N$ as

$\mathrm{e}^{\mathrm{wa}}(S_{d},N,\Phi)=\sup_{\|f\|_{F_{d}}\leq
1}\,\bigg{(}\int_{Y}\|S_{d}(f)-\Phi(\mathbf{y})\|_{G_{d}}^{2}\,\pi_{f}(d\mathbf{y})\bigg{)}^{1/2}.$

As before, $S_{d}$ are compact operators.

Define an _auxiliary cost function_ $\widehat{\$}$ in such a way that
$\widehat{\$}(\sigma,d)$ is the complexity of approximating a real parameter
$f\in\mathbb{R}$ in the current setting using the cost function
$\$(\,\cdot\,,d).$ (We stress that here $f$ is not restricted to the interval
$[-1,1].$ Possible approximations use noisy observations of $f$ with
adaptively chosen precisions $\sigma_{i}.$)

We clearly have $\widehat{\widehat{\$}}=\widehat{\$},$ and
$\widehat{\$}\leq\$$ since the approximation $\tilde{f}=f+e,$ where
$e\sim\mathcal{N}(0,\sigma^{2}),$ gives error $\sigma$ at cost $\$(\sigma,d).$

######  Lemma 2.

For all $\varepsilon\in(0,1)$ and $d\geq 1$ we have

$\mathrm{comp}^{\mathrm{wa}}_{\$}(\varepsilon,d)\geq\frac{\mathrm{n}^{\mathrm{w}}\big{(}2\,\varepsilon,d\big{)}+1}{4}.$

Also, there is $c\in(0,1)$ such that for all $\varepsilon\in(0,c)$ and $d\geq
1$ we have

$\mathrm{comp}^{\mathrm{wa}}_{\$}(\varepsilon,d)\geq\frac{1}{2}\,\widehat{\$}\bigg{(}\frac{\varepsilon}{c\sqrt{2}},d\bigg{)}.$

###### Proof.

Let an algorithm $\Phi$ using information $N=\\{\pi_{f}\\}_{f\in F}$ be such
that
$\mathrm{e}^{\mathrm{wa}}(S_{d},N,\Phi)\leq\varepsilon\sqrt{\lambda_{1}}.$ Let

$n=\sup_{\|f\|_{F_{d}}\leq
1}\int_{Y}n(\mathbf{y})\,\pi_{f}(\mathrm{d}\mathbf{y}).$

Since $\$\geq 1,$ we have $n\leq\mathrm{cost}^{\mathrm{wa}}_{\$}(N).$ Observe
that any deterministic algorithm that uses noisy information can be
interpreted as a randomized algorithm that uses exact information, where the
noise is treated as a random parameter. Then, by [3, Theorem 4.42], there is
deterministic algorithm using exact information of cardinality $4n-1$ whose
worst case error is at most $2\varepsilon.$ Hence

$\mathrm{cost}^{\mathrm{wa}}_{\$}(N,\Phi)\geq
n\geq\frac{\mathrm{n}^{\mathrm{w}}\big{(}2\varepsilon,d\big{)}+1}{4}.$

Taking the infimum with respect to all $\Phi$ and $N$ we obtain the desired
inequality.

To show the second inequality, we estimate the complexity of our problem from
below by the complexity of the same problem, but with error taken over the
interval $[-f_{d,1}^{*},f_{d,1}^{*}]$ where, as before, $f_{d,1}^{*}$ is the
eigenelement corresponding to the largest eigenvalue of $S_{d}^{*}S_{d}.$ This
is equivalent to the one-dimensional problem of approximating a prameter
$f\in[-1,1]$ from its noisy observations that is analyzed in Appendix of [2].
The worst case error of the latter can be lower bounded by the average error
with respect to the two-point probability measure $\mu$ that assigns $1/2$ to
$\pm 1.$ For any adaptive information such average error is not larger than
$c\min(\sigma,1)$ for some $c>0,$ where $\sigma$ is such that

$\sigma^{-2}=\int_{-1}^{1}\int_{Y}\sigma_{\mathbf{y}}^{-2}\,\pi_{f}(\mathrm{d}\mathbf{y})\mu(\mathrm{d}f)=\int_{Y}\sigma_{\mathbf{y}}^{-2}\mu_{1}(\mathrm{d}\mathbf{y}),\qquad\sigma_{\mathbf{y}}^{-2}=\sum_{i=1}^{n(\mathbf{y})}\sigma_{i}^{-2}\big{(}y_{1},\ldots,y_{i-1}\big{)},$

and $\mu_{1}$ is the a priori distribution of information $\mathbf{y}$ on $Y,$
cf. [2, Lemma 3]. Another important property is that for any
$\sigma_{1},\ldots,\sigma_{n}$ and $\sigma$ such that
$\sigma^{-2}=\sum_{i=1}^{n}\sigma_{i}^{-2}$ we have

$\sum_{i=1}^{n}\$(\sigma_{i},d)\geq\widehat{\$}(\sigma,d),$

which follows directly from the definition of $\widehat{\$}.$

Let $A\subset Y$ be the set of all $\mathbf{y}$ such that
$\sigma_{\mathbf{y}}^{-2}\leq 2\sigma^{-2}.$ Then $\mu_{1}(A)\geq 1/2.$ Hence,
if the error is at most $\varepsilon<c$ then $\sigma\leq\varepsilon/c$ and the
cost is at least

$\int_{A}\sum_{i=1}^{n(\mathbf{y})}\$\big{(}\sigma_{i}(y_{1},\ldots,y_{i-1}),d\,\big{)}\,\mu_{1}(\mathrm{d}\mathbf{y})\geq\int_{A}\sum_{i=1}^{n(\mathbf{y})}\widehat{\$}(\sigma_{\mathbf{y}},d)\,\mu_{1}(\mathrm{d}\mathbf{y})\geq\frac{1}{2}\,\widehat{\$}\bigg{(}\frac{\varepsilon}{c\sqrt{2}},d\bigg{)},$

as claimed. ∎

We now show some useful properties of $\widehat{\$}.$ For $d\geq 1,$ define
the two functions, $h_{1}$ and $h_{2,\lambda}.$

$(0,+\infty)\ni x\mapsto
h_{1}(x,d)=\$\bigg{(}\sqrt{\frac{1}{x}},\,d\bigg{)},\qquad\mbox{and}$
$(0,\lambda)\ni x\mapsto h_{2,\lambda}(x,d)=\$\bigg{(}\sqrt{\frac{\lambda
x}{\lambda-x}},\,d\bigg{)}.$

######  Lemma 3.

For any $d\geq 1$ we have the following.

  * (i)

Suppose that $h_{1}(\,\cdot\,,d)$ is concave, and $h_{2,\lambda}(\,\cdot\,,d)$
is convex for all $\lambda$ sufficiently large. Then

$\widehat{\$}(\,\cdot\,,d)=\$(\,\cdot\,,d).$

  * (ii)

Suppose there is a line $\ell(x)=\alpha x$ supporting $h_{1}(\,\cdot\,,d)$ at
some $x_{0}>0,$ i.e., $\ell(x_{0})=h_{1}(x_{0},d)$ and $\ell(x)\leq h(x,d)$
for all $x\geq 0.$ Then for all $\sigma>0$ we have

$\frac{\alpha}{\sigma^{2}}\leq\widehat{\$}(\sigma,d)\leq\bigg{\lceil}\frac{\sigma_{0}^{2}}{\sigma^{2}}\bigg{\rceil}\,\frac{\alpha}{\sigma_{0}^{2}},\qquad\mbox{where}\quad\sigma_{0}^{2}=1/x_{0}.$

  * (iii)

We always have

$\widehat{\$}(\sigma,d)\leq\bigg{\lceil}\frac{\sigma_{0}^{2}}{\sigma^{2}}\bigg{\rceil}\,\$(\sigma_{0},d),\qquad\mbox{for
any}\quad\sigma_{0}>0.$

###### Proof.

(i) We already noticed that $\widehat{\$}\leq\$.$ To bound $\widehat{\$}$ from
below we use the average case complexity of approximating $f\in\mathbb{R}$
from observations of $f$ with Gaussian noise, where the average squared error
and average cost are taken with respect to the one-dimensional Gaussian
distribution $\mu_{\lambda}$ with mean zero and variance $\lambda.$

Consider first nonadaptive information consisting of $n$ observations
$y_{i}=f+e_{i}$ with precisions $\sigma_{i}.$ Then the optimal algorithm is

$\phi^{*}(\mathbf{y})=\frac{\sigma^{2}\lambda}{\sigma^{2}+\lambda}\sum_{i=1}^{n}\frac{y_{i}}{\sigma_{i}^{2}}\,,\quad\mbox{where}\quad\sigma^{-2}=\sum_{i=1}^{n}\sigma_{i}^{-2},$

and its average squared error depends only on $\sigma^{2}$ and $\lambda$ and
equals

$\int_{F}\int_{\mathbb{R}^{n}}|f-\phi^{*}(\mathbf{y})|^{2}\pi_{f}(\mathrm{d}\mathbf{y})\mu_{\lambda}(\mathrm{d}f)=\frac{\sigma^{2}\lambda}{\sigma^{2}+\lambda}\,,$

cf. [6, Sect. 3.5]. By concavity of $h_{1}$ we have

$\displaystyle h_{1}(\sigma^{-2},d)$ $\displaystyle=$ $\displaystyle
h_{1}\bigg{(}\sum_{i=1}^{n}\sigma_{i}^{-2},d\bigg{)}\leq
h_{1}(0,d)+h_{1}\bigg{(}\sum_{i=1}^{n}\sigma_{i}^{-2},d\bigg{)}\leq
h_{1}\bigg{(}\sum_{i=1}^{n-1}\sigma_{i}^{-2},d\bigg{)}+h_{1}(\sigma_{n}^{-2},d)$
$\displaystyle\leq$ $\displaystyle
h_{1}\bigg{(}\sum_{i=1}^{n-2}\sigma_{i}^{-2},d\bigg{)}+h_{1}(\sigma_{n-1}^{-2},d)+h_{1}(\sigma_{n}^{-2},d)\leq\cdots\leq\sum_{i=1}^{n}h_{1}(\sigma_{i}^{-2},d),$

so that $\$(\sigma,d)\leq\sum_{i=1}^{n}\$(\sigma_{i},d).$ This means that the
cheapest way of obtaining an approximation with the average squared error
$\sigma^{2}<\lambda$ using nonadaptive information is to use just one
observation $y=f+e$ with variance
$\sigma_{1}^{2}=\sigma^{2}\lambda/(\lambda-\sigma^{2}),$ for which the cost is

$\psi_{\lambda}(\sigma)=\$\bigg{(}\sqrt{\frac{\sigma^{2}\lambda}{\lambda-\sigma^{2}}},\,d\bigg{)}.$

Since, by assumption, the function
$\sigma\mapsto\psi_{\lambda}(\sqrt{\sigma}\,)$ is convex for large $\lambda,$
we can use [6, Lemma 3.9.2] to claim, that the cost $\psi_{\lambda}(\sigma)$
cannot be reduced using adaptive information. Hence
$\widehat{\$}(\sigma)\geq\psi_{\lambda}(\sigma),$ and letting
$\lambda\to\infty$ we obtain $\widehat{\$}(\sigma)\geq\$(\sigma),$ which
forces $\widehat{\$}(\sigma)=\$(\sigma).$

(ii) If the cost function is $\$_{1}(\sigma,d)=\alpha\sigma^{-2}$ then we have
from (i) that $\widehat{\$}_{1}=\$_{1}.$ (Note that here we violate the
assumption that the cost is at least $1.$) Since
$\$(\,\cdot\,,d)\geq\$_{1}(\,\cdot\,,d)$ then
$\widehat{\$}(\sigma,d)\geq\widehat{\$}_{1}(\sigma,d)=\alpha\sigma^{-2}.$ On
the other hand, we can approximate $f\in\mathbb{R}$ with error $\sigma$ using
$n$ nonadaptive observations with the same precision $\sigma_{0}/\sqrt{n},$
where $n=\lceil\sigma_{0}^{2}/\sigma^{2}\rceil.$ Hence,

$\widehat{\$}(\sigma,d)\leq
n\,\$(\sigma_{0},d)=\bigg{\lceil}\frac{\sigma_{0}^{2}}{\sigma^{2}}\bigg{\rceil}\frac{\alpha}{\sigma_{0}^{2}}.$

(iii) The bound can be easily obtained by repetitive observations of variance
$\sigma_{0}^{2},$ as in (ii). ∎

######  Example 2.

Assume that the cost function grows polynomially,

$\$(\sigma,d)=1+Dd^{t}\sigma^{-2s}.$

For $s\leq 1$ the function $h_{1}(\,\cdot\,,d)$ is obviously concave, and

$x\mapsto
h_{2,\lambda}(x,d)=1+Dd^{t}\bigg{(}\frac{1}{x}-\frac{1}{\lambda}\bigg{)}^{s}$

is convex for all $\lambda>0,$ and therefore $\widehat{\$}=\$.$

For $s\geq 1$ the function $\$(\,\cdot\,,d)$ is supported at
$x_{0}=\big{(}(s-1)Dd^{t}\big{)}^{-1/s}$ by $\ell(x)=\alpha_{d}x,$ where

$\alpha_{d}=s(s-1)^{1/s-1}(Dd^{t})^{1/s}.$

Hence $\widehat{\$}(\sigma,d)$ essentially equals $\alpha_{d}\sigma^{-2}.$

######  Remark 3.

Lemma 2 is an analogue of Lemma 1. In the case of bounded noise the
corresponding auxiliary cost function would always be $\widehat{\$}=\$.$

Similarly to the case of bounded noise, for upper bounds on tractability we
use

(19) $\Phi_{n}^{d}(\mathbf{y})=\sum_{i=1}^{n}y_{i}S_{d}(f_{d,i}^{*}),$

where $y_{i}$ approximates $\langle f,f_{d,i}^{*}\rangle_{F_{d}}$ for all
$f\in F$ with the expected squared error $\sigma_{i}^{2},$ and with cost
$\widehat{\$}(\sigma_{i},d).$ Then, for the corresponding information we have

(20)
$\mathrm{e}^{\mathrm{wa}}(S_{d},N^{d}_{n},\Phi^{d}_{n})=\sqrt{\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{d,i}+\lambda_{d,n+1}}\,,$

and
$\mathrm{cost}^{\mathrm{wa}}_{\$}(N_{n}^{d})=\sum_{i=1}^{n}\widehat{\$}(\sigma_{i},d).$
Note that
$\mathrm{e}^{\mathrm{wa}}(S_{d},N_{n}^{d},\Phi_{n}^{d})=\mathrm{e}^{\mathrm{ww}}(S_{d},N_{n}^{d},\Phi_{n}^{d}),$
where in the deterministic case the noise of $i$th observation is bounded by
$\sigma_{i},$ cf. (12). Hence we can adopt the proof technique from Section
LABEL:sect:bounded with the cost function $\widehat{\$}$ to obtain complexity
bounds in the case of random noise. In particular, Lemma 3(iii) gives the
following general upper bound.

######  Corollary 1.

Suppose that $\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq
Cd^{q}\varepsilon^{-p}.$ Then for any fixed $\sigma_{0}>0$ we have

$\mathrm{comp}^{\mathrm{wa}}_{\$}(\varepsilon,d)\,\preccurlyeq\,\sigma_{0}^{2}\,\$(\sigma_{0},d)\,d^{\,2q}\left\\{\begin{array}[]{rl}\varepsilon^{-2p},&\quad
p>1,\\\ \ln^{2}(1/\varepsilon)\,\varepsilon^{-2},&\quad p=1,\\\
\varepsilon^{-2},&\quad p<1.\end{array}\right.$

###  4.1. Polynomial tractability

######  Theorem 4.

Consider a multivariate problem $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}.$

  * (i)

The problem with noisy information is polynomially tractable if and only if

    * $\bullet$

it is polynomially tractable for exact information, and

    * $\bullet$

the auxiliary cost function grows polynomially in $d$ for some $\sigma_{0}>0.$

  * (ii)

The problem with noisy information is strongly polynomially tractable if and
only if

    * $\bullet$

it is strongly polynomially tractable for exact information, and

    * $\bullet$

the auxiliary cost function is bounded in $d$ for some $\sigma_{0}>0.$

  * (iii)

Suppose that $\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq
Cd^{q}\varepsilon^{-p}$ and $\$(\sigma,d)\leq 1+Dd^{t}\sigma^{-2s}.$
If $p=0$ and $s=0$ then
$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\preccurlyeq d^{t+q};$
otherwise

$\mathrm{comp}^{\mathrm{ww}}_{\$}(\varepsilon,d)\,\preccurlyeq\,d^{\overline{t}+q(\overline{s}+1)}\left\\{\begin{array}[]{rl}\varepsilon^{-p(\overline{s}+1)},&\;p(\overline{s}+1)>2\overline{s},\\\
\ln^{\overline{s}+1}(1/\varepsilon)\,\varepsilon^{-2\overline{s}},&\;p(\overline{s}+1)=2\overline{s},\\\
\varepsilon^{-2\overline{s}},&\;p(\overline{s}+1)<2s,\end{array}\right.$

where $\overline{t}=\min(t,t/s)$ and $\overline{s}=\min(s,1).$

###### Proof.

Suppose the problem with noise is polynomially tractable, i.e.,
$\mathrm{comp}^{\mathrm{wa}}(\varepsilon,d)\leq Cd^{q}\varepsilon^{-p}$ for
$\varepsilon\in(0,1)$ and $d\geq 1.$ Then we have by Lemma 2 that, on one
hand,

$\mathrm{n}^{\mathrm{w}}(\varepsilon,d)\leq
4\,\mathrm{comp}^{\mathrm{wa}}\big{(}\tfrac{\varepsilon}{2},d\big{)}-1\leq
4\,Cd^{q}\big{(}\tfrac{\varepsilon}{2}\big{)}^{-p}\preccurlyeq
d^{q}\varepsilon^{-p},$

and, on the other hand,

$\widehat{\$}(\sigma_{0},d)\leq
2\,\mathrm{comp}^{\mathrm{wa}}\big{(}c\sqrt{2}\,\sigma_{0},d\big{)}\leq
2+2\,Cd^{q}\big{(}c\sqrt{2}\,\sigma_{0}\big{)}^{-p}.$

This proves the necessary conditions in (i) and (ii). The sufficient
conditions follow from Corollary 1. To show (iii) it suffices to note that
$\widehat{\$}(\sigma,d)\preccurlyeq
d^{\,\overline{t}}\sigma^{\,\overline{s}},$ as in Example 2, and use Theorem
1. ∎

######  Remark 4.

As in the case of bounded noise, see Remark 1, for Gaussian noise the
algorithm $\Phi_{n}^{d}$ is not optimal for information $N_{n}^{d};$ however,
one can show that the exponents of tractability in (iii) of Theorem 4 cannot
be improved when one relies only on information $N_{n}^{d}.$ If arbitrary
information is allowed then the optimal exponents are unknown. The point is
that we do not know in general how to optimally choose the information. For a
particular case, see Proposition 2 of Appendix.

###  4.2. Weak tractability and the curse of dimensionality

######  Theorem 5.

Consider a multivariate problem $\mathcal{S}=\\{S_{d}\\}_{d\geq 1}.$

  * (i)

The problem with noisy information is weakly tractable if and only if the same
problem with exact information is weakly tractable.

  * (ii)

The problem with noisy information suffers from the curse of dimensionality if
and only if the same problem with exact information suffers from the curse.

###### Proof.

(i) The necessary condition follows from the first inequality in Lemma 2. For
sufficiency it is enough to consider the information $N_{n}^{d}$ and algorithm
$\Phi_{n}^{d}$ with $n=\mathrm{n}^{\mathrm{w}}(\varepsilon/\sqrt{2},d)$ and
$\sigma_{i}^{2}=\varepsilon^{2}/(2n)$ for all $i.$ Then the error is
$\varepsilon$ and the cost is
$n\,\widehat{\$}(\varepsilon/\sqrt{n},d)\leq\beta n^{2}/\varepsilon^{2}$ for
some $\beta>0.$ This implies

$\lim_{\varepsilon^{-1}+d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{wa}}_{\$}(\varepsilon,d)\big{)}}{\varepsilon^{-1}+d}\leq\lim_{\varepsilon^{-1}+d\to\infty}\frac{\ln\beta+2\ln
n+2\ln(1/\varepsilon)}{\varepsilon^{-1}+d}=0.$

(ii) The sufficiency follows again from the first inequality in Lemma 2. For
necessity it is enough to consider the same approximation as in (i) to get
that if the problem with exact information does not suffer from the curse then
for all $\varepsilon$ we have

$\lim_{d\to\infty}\frac{\ln\big{(}\mathrm{comp}^{\mathrm{wa}}_{\$}(\varepsilon,d)\big{)}}{d}\leq\lim_{d\to\infty}\frac{\ln\beta+2\ln
n+2\ln(1/\varepsilon)}{d}=0,$

i.e., the problem with noise as well does not suffer from the curse. ∎

## Acknowledgments

The research of the authors was supported by the National Science Centre,
Poland, under project 2017/25/B/ST1/00945.

## References

  * [1] Donoho D.L., Statistical estimation and optimal recovery. Annals of Statistics 22 (1994), pp. 238-270.
  * [2] Morkisz P., Plaskota L., Complexity of approximating Hölder classes from information with varying Gaussian noise. Journal of Complexity 60 (2020) 101497.
  * [3] Novak E., Woźniakowski H., Tractability of Multivariate Problems. Volume I: Linear Information. Tracts in Mathematics 6, EMS 2008.
  * [4] Novak E., Woźniakowski H., Tractability of Multivariate Problems. Volume II: Standard Information for Functionals. Tracts in Mathematics 12, EMS 2010.
  * [5] Novak E., Woźniakowski H., Tractability of Multivariate Problems. Volume III: Standard Information for Operators. Tracts in Mathematics 18, EMS 2012.
  * [6] Plaskota L., Noisy Information and Computational Complexity. Cambridge University Press, Cambridge, 1996.
  * [7] Plaskota L., How to benefit from noise. Journal of Complexity 12 (1996), pp. 175-184.
  * [8] Plaskota L., Worst case complexity of problems with random information noise. Journal of Complexity 12 (1996), pp. 416–439.

## Appendix

Let $F$ and $G$ be unitary spaces with $\dim F=m<+\infty,$ and $S:F\to G$ a
nonsingular linear operator. Let $\\{x_{i}^{*}\\}_{i=1}^{m}$ be an orthonormal
basis in $F$ of eigenelements of the operator $S^{*}S$ and
$\\{\lambda_{i}\\}_{i=1}^{m}$ the corresponding eigenvalues, where
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{m}>0.$

We fix the numbers

$0=\sigma_{1}=\cdots=\sigma_{n_{0}}<\sigma_{n_{0}+1}\leq\cdots\leq\sigma_{n}$

(where $n_{0}=0$ if all $\sigma_{i}$s are positive) and for any functionals
$L_{i}$ define

${\mathrm{R}}^{\mathrm{ww}}(L_{1},L_{2},\ldots,L_{n})=\max\big{\\{}\|Sx\|_{Y}:\;x\in
X,\,|L_{i}x|\leq\sigma_{i},\,1\leq i\leq n\big{\\}}.$

This is obviously the radius of information $y_{i}=L_{i}x+e_{i},$ $1\leq i\leq
n,$ in the worst case setting with bounded noise, $|e_{i}|\leq\sigma_{i},$
where the worst case error is taken with respect to the whole space $F$
(instead of the unit ball of $F$), cf. (8).

######  Proposition 1.

Let $n=m.$ For any functionals $L_{i}$ with $\|L_{i}\|\leq 1$ for $1\leq i\leq
n,$ we have

(21)
${\mathrm{R}}^{\mathrm{ww}}(L_{1},L_{2},\ldots,L_{n})\geq\bigg{(}\sum_{i=n_{0}+1}^{n}\sigma_{i}^{2}\lambda_{i}\bigg{)}^{1/2}.$

The equality above holds for
$L_{i}^{*}=\langle\,\cdot\,,x_{i}^{*}\rangle_{F}.$

###### Proof.

We can assume without loss of generality that the functionals $L_{i}$ are
linearly independent since otherwise
${\mathrm{R}}^{\mathrm{ww}}(L_{1},L_{2},\ldots,L_{n})$ is infinite.

Let $\\{x_{j}\\}_{j=1}^{n}$ be the basis in $F$ that is adjoint to
$\\{L_{i}\\}_{i=1}^{n},$ i.e., $L_{i}x_{j}=\delta_{i,j}$ for $1\leq i,j\leq
n.$ Let

$V_{i}=\mathrm{span}\big{(}x_{j}:\,1\leq j\leq n,\,j\neq i\big{)}.$

Observe that

$\|L_{i}\|=\max_{x\neq 0}\frac{|L_{i}x|}{\|x\|_{F}}=\max_{v\in
V_{i}}\frac{1}{\|x_{i}+v\|_{F}}=\frac{1}{\mathrm{dist}(x_{i},V_{i})}.$

Hence the condition $\|L_{i}\|\leq 1$ is equivalent to

$\mathrm{dist}(x_{i},V_{i})\geq 1.$

Since for any $x=\sum_{j=1}^{n}c_{j}x_{j}\in F$ is $L_{i}x=c_{i},$ inequality
(21) can be equivalently rewritten as

(22)
$\max\Big{\\{}\,\Big{\|}\sum_{i=1}^{n}c_{i}Sx_{i}\Big{\|}_{G}^{2}:\;|c_{i}|\leq\sigma_{i},\,1\leq
i\leq n\Big{\\}}\geq\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{i}.$

To show (22) we use induction on $n.$ For $n=1$ we have

$\max_{|c_{1}|\leq\sigma_{1}}\|c_{1}Sx_{1}\|_{G}^{2}=\max_{|c_{1}|\leq\sigma_{1}}c_{1}^{2}\lambda_{1}=\sigma_{1}^{2}\lambda_{1}.$

Suppose $n\geq 2.$ Let

$W=\mathrm{span}\big{(}Sx_{1},\ldots,Sx_{n-1}\big{)}$

and $Z$ be the subspace of $\mathrm{im}\,A$ that is perpendicular to $W.$ We
obviously have $\dim W=n-1$ and $\dim Z=1.$ Let us decompose $S$ as

$S=P_{W}S+P_{Z}S,$

where $P_{W}$ and $P_{Z}$ are the orthogonal projections onto $W$ and $Z,$
respectively, and denote by

$S_{W}:V_{n}\to G\qquad\mbox{and}\qquad S_{Z}:V_{n}^{\perp}\to G$

the operators $P_{W}S$ and $P_{Z}S$ restricted, respectively, to $V_{n}$ and
$V_{n}^{\perp}.$ Let

$\widehat{\lambda}_{1}\geq\cdots\geq\widehat{\lambda}_{n-1}>0$

be the eigenvalues of $S_{W}^{*}S_{W}:V_{n}\to V_{n},$ and
$\widehat{\lambda}_{n}>0$ be the only eigenvalue of
$S_{Z}^{*}S_{Z}:V_{n}^{\perp}\to V_{n}^{\perp}.$ Observe that for $1\leq i\leq
n-1$ the distance of $x_{i}$ from the subspace
$\mathrm{span}\big{(}x_{j}:\,j\in\\{1,\ldots,n\\}\setminus\\{i,n\\}\big{)}$ is
at least $1.$ Then, by induction hypothesis, there are $c_{i}$ such that
$|c_{i}|\leq\sigma_{i},$ $1\leq i\leq n-1,$ and

$\Big{\|}\sum_{i=1}^{n-1}c_{i}Sx_{i}\Big{\|}_{G}^{2}\geq\sum_{i=1}^{n-1}\sigma_{i}^{2}\widehat{\lambda}_{i}.$

Letting $v$ be the orthogonal projection of $x_{n}$ onto $V^{\perp}$ we also
have that

$\|Sx_{n}\|_{G}^{2}\geq\|P_{Z}Sx_{n}\|_{G}^{2}=\|P_{Z}Sv\|_{G}^{2}=\sigma_{n}^{2}\widehat{\lambda}_{n}.$

Setting $c_{n}=\sigma_{n}$ if
$\big{\langle}\sum_{i=1}^{n-1}c_{i}Sx_{i},Sx_{n}\big{\rangle}_{G}\geq 0,$ and
$c_{n}=-\sigma_{n}$ otherwise, we obtain

$\Big{\|}\sum_{i=1}^{n-1}c_{i}Sx_{i}+c_{n}Sx_{n}\Big{\|}_{G}^{2}\geq\Big{\|}\sum_{i=1}^{n-1}c_{i}Sx_{i}\Big{\|}_{G}^{2}+\big{\|}Sx_{n}\big{\|}_{G}^{2}\geq\sum_{i=1}^{n}\sigma_{i}^{2}\widehat{\lambda}_{i}.$

To complete the proof of (22) it suffices to use the fact that

$\sum_{i=1}^{k}\widehat{\lambda}_{i}\leq\sum_{i=1}^{k}\lambda_{i}\quad\mbox{for}\quad
1\leq k\leq
n-1,\quad\mbox{and}\quad\sum_{i=1}^{n}\widehat{\lambda}_{i}=\sum_{i=1}^{n}\lambda_{i},$

which implies
$\sum_{i=1}^{n}\sigma_{i}^{2}\widehat{\lambda}_{i}\geq\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{i}.$

The remaining part of the proposition is obvious, since orthogonality of
$\\{Sx_{i}^{*}\\}_{i=1}^{n}$ implies that for any $c_{i}$ with
$|c_{i}|\leq\sigma_{i}$ we have

$\Big{\|}\sum_{i=1}^{n}c_{i}Sx_{i}^{*}\Big{\|}_{G}^{2}=\sum_{i=1}^{n}c_{i}^{2}\|Sx_{i}^{*}\|_{G}^{2}=\sum_{i=1}^{n}c_{i}^{2}\lambda_{i}\leq\sum_{i=1}^{n}\sigma_{i}^{2}\lambda_{i}.$

∎

Proposition 1 should be confronted with the related result in the case of
Gaussian noise. Let

${\mathrm{R}}^{\mathrm{wa}}(L_{1},L_{2},\ldots,L_{n})=\inf_{\Phi}\,\sup_{x\in
F}\bigg{(}\int_{\mathbb{R}^{n}}\|Sx-\Phi(\mathbf{y})\|_{G}^{2}\,\pi_{x}(\mathrm{d}\mathbf{y})\bigg{)}^{1/2},$

where $\pi_{f}$ is the $n$-dimensional Gaussian measure with mean
$(L_{1}x,\ldots,L_{n}x)$ and covariance matrix
$\mathrm{diag}(\sigma_{1}^{2},\ldots,\sigma_{n}^{2}),$ be the mimimal error in
the worst case setting with Gaussian noise, where again the worst case error
is taken with respect to the whole space $F.$ In this case the optimal choice
of the functionals $L_{i}$ is known for all $n\geq m,$ but their construction
is much more complicated.

######  Proposition 2.

Let $n\geq m.$ For any functionals $L_{i}$ with $\|L_{i}\|\leq 1$ for $1\leq
i\leq n,$ we have

(23)
${\mathrm{R}}^{\mathrm{wa}}(L_{1},L_{2},\ldots,L_{n})\geq\bigg{(}\sum_{i=n_{0}+1}^{m}\widehat{\sigma}_{i}^{2}\lambda_{i}\bigg{)}^{1/2},$

where $\widehat{\sigma}_{n_{0}+1}\leq\cdots\leq\widehat{\sigma}_{m}$ minimize
the sum $\sum_{i=n_{0}+1}^{m}\eta_{i}^{2}\lambda_{i}$ with respect to all
$\eta_{n_{0}+1}\leq\cdots\leq\eta_{m}$ satisfying

$\sum_{i=k}^{m}\eta_{i}^{-2}\leq\sum_{i=k}^{n}\sigma_{i}^{-2}\quad\mbox{for}\quad
k=n_{0}+1\leq k\leq n,$

and $\sum_{i=n_{0}+1}^{m}\eta_{i}^{-2}=\sum_{i=i_{0}+1}^{n}\sigma_{i}^{-2}.$
The equality in (23) holds for
$L_{i}^{*}=\langle\,\cdot\,,x_{i}^{*}\rangle_{F},$ $1\leq i\leq n_{0},$ and

$L_{n_{0}+i}^{*}=\sigma_{n_{0}+i}\sum_{j=1}^{m-n_{0}}w_{i,j}\langle\,\cdot\,,x_{n_{0}+j}^{*}\rangle_{F},\qquad
1\leq i\leq n-n_{0},$

where the matrix $W=\\{w_{i,j}\\}\in\mathbb{R}^{(n-n_{0})\times(m-n_{0})}$
satisfies

$W^{T}W=\mathrm{diag}\big{(}\widehat{\sigma}_{n_{0}+1}^{-2},\ldots,\widehat{\sigma}_{m}^{-2}\big{)}\quad\mbox{and}\quad\big{\|}W^{T}\vec{e}_{i}\big{\|}_{2}^{2}=\sigma_{n_{0}+i}^{-2},\quad
1\leq i\leq n-n_{0}.$

A proof of this proposition as well as construction of the matrix $W$ can be
derived from Theorems 3.8.1 and 3.8.2 and Lemma 2.8.1 in [6]. One considers
the average case error with respect to the Gaussian measure on
$\mathbb{R}^{m}$ with mean zero and covariance matrix $\lambda I_{m}$ (where
$I_{m}$ is the $m\times m$ identity matrx). The worst case error is obtained
as the limiting case when $\lambda$ increases to infinity.

We add that for $n=m$ we have
$L_{i}^{*}=\langle\,\cdot\,,x_{i}^{*}\rangle_{F}$ for all $1\leq i\leq n$ if
and only if

$\sigma_{n_{0}+i}^{-2}=\frac{\lambda_{n_{0}+i}^{1/2}}{\sum_{j=n_{0}+1}^{n}\lambda_{j}^{1/2}}\sum_{j=n_{0}+1}^{n}\sigma_{j}^{-2}\quad\mbox{for}\quad
1\leq i\leq n-n_{0},$

and then
$\mathrm{R}\big{(}\langle\,\cdot,x_{1}^{*}\rangle_{F},\ldots,\langle\,\cdot,x_{n}^{*}\rangle_{F}\big{)}=\left(\sum_{i=n_{0}+1}^{n}\sigma_{i}^{2}\lambda_{i}\right)^{1/2}.$