\documentclass[preprint]{elsarticle}
\usepackage{amsmath,amsthm}
\usepackage[english]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}

\tolerance 1800
\renewcommand{\thesubsection}{\arabic{subsection}}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newcommand{\WW}{\mathcal W_2^n(\mathbb R_+)}
\newcommand*{\cd}{(\cdot)}
\newcommand{\Lt}{L_2(\mathbb R_+)}
\newcommand{\ww}{W_2^n(\mathbb R_+)}
\newcommand{\ii}{\int_{\mathbb R_+}}
\newcommand{\wx}{\widehat x}
\newcommand{\ov}{\overline}
\newcommand{\wm}{\widehat m}
\newcommand*{\la}{\langle}
\newcommand*{\ra}{\rangle}
\newcommand*{\LL}{\mathcal L}
\newcommand*{\wl}{\widehat\lambda}
\newcommand*{\Wr}{W_\infty^r([-1,1])}
\newcommand*{\WR}{\mathcal W_2^r(\mathbb T)}
\newcommand*{\wva}{\widehat\varphi}
\newcommand*{\Wrt}{W_2^r(\mathbb T)}
\newcommand*{\lT}{L_2(\mathbb T)}
\newcommand*{\lN}{l_2^{2N+1}}
\newcommand*{\ta}{\widetilde a}
\newcommand*{\tb}{\widetilde b}
\newcommand*{\wa}{\widehat a}
\newcommand*{\wb}{\widehat b}
\newcommand*{\wpp}{\widehat s}
\newcommand*{\wP}{\widehat{\mathbf p}}
\newcommand*{\wA}{\widehat A}
\newcommand*{\wB}{\widehat B}
\newcommand*{\pp}{\mathbf p}
\newcommand*{\yy}{\mathbf y}
\newcommand*{\ppp}{\widehat p}

\DeclareMathOperator*{\gr}{gr}
\DeclareMathOperator*{\infp}{inf\vphantom p}
\DeclareMathOperator*{\co}{co}
\DeclareMathOperator*{\bco}{bco}
\DeclareMathOperator*{\RE}{Re}
\DeclareMathOperator*{\grad}{grad}
\DeclareMathOperator*{\card}{card}
\DeclareMathOperator*{\sign}{sign}

\begin{document}
\begin{frontmatter}
\title{Generalized Adaptive versus Nonadaptive Recovery from Noisy Information}
\author{K.~Yu.~Osipenko\fnref{myfootnote1}}
%\cortext[cor]{Corresponding author}
\fntext[myfootnote1]{The research was carried out with the financial support of the Russian Foundation for Basic Research (grant no.\ 17-01-00649)}
\address{Moscow State University,\\
Institute for Information Transmission Problems,
Russian Academy of Sciences, Moscow}
\ead{kosipenko@yahoo.com}
\begin{abstract}
The article is devoted to a generalized setting of adaptive recovery from noisy information. We extend some known results for this setting and obtain sufficient conditions under which adaption does not help for recovery of linear operators. For recovery of linear functionals we give necessary and sufficient conditions for the existence of an optimal nonadaptive linear method which gives the same error as optimal adaptive methods.
\end{abstract}

\begin{keyword}
optimal recovery \sep adaptive and nonadaptive methods \sep adaptive radius of information
\MSC[2010] 41A65 \sep 41A45 \sep 41A46 \sep 49N30
\end{keyword}

\end{frontmatter}

\section{Introduction}

Let $X$ be a linear space, $Z$ be a normed linear space, $T\colon X\to Z$ be a linear operator and $W\subset X$. We consider the problem of recovery of $T$ on the set $W\subset X$ by noisy information about elements from $W$. Suppose that there is a family $\mathcal I$ of linear information operators $I_p\colon X\to Y$, $p\in\Omega$, where $\Omega$ is some set and $Y$ is a normed linear space. All linear spaces are considered over the field of real or complex numbers. Let us choose $n$ parameters $p_1,\ldots,p_n\in\Omega$ and assume that for all $x\in W$ we know $y_1,\ldots,y_n\in Y$ such that
$$\|I_{p_j}x-y_j\|_Y\le\delta,\quad\delta\ge0.$$

As recovery methods we consider all possible mappings $\varphi\colon Y^n\to Z$. The error of a method $\varphi$ is defined as follows
$$e_n(T,W,\mathcal I,\delta,\pp,\varphi)=\sup_{\substack{x\in W,\ \yy=(y_1,\ldots,y_n)\in Y^n\\\|I_{p_j}x-y_j\|_Y\le\delta,\ j=1,\ldots,n}}\|Tx-\varphi(\yy)\|_Z;$$
here $\pp=(p_1,\ldots,p_n)$.
The quantity
$$E_n(T,W,\mathcal I,\delta)=\inf_{p_1,\ldots,p_n\in\Omega\vphantom{Y^n}}\inf_{\varphi\colon Y^n\to Z}e_n(T,W,\mathcal I,\delta,\pp,\varphi)$$
is called the $n$th optimal nonadaptive recovery error. Parameters $\ppp_1,\ldots,\ppp_n$ and the method $\wva$ we call optimal if
$$e_n(T,W,\mathcal I,\delta,\wP,\wva)=E_n(T,W,\mathcal I,\delta),\quad\wP=(\ppp_1,\ldots,\ppp_n).$$

One of the typical examples of this setting is the problem of optimal integration. Let $W$ be a class of functions defined on the segment $[a,b]$. Set
$$Tx=\int_a^bx(t)\,dt,\quad I_{t_j}x=x(t_j),\quad t_j\in[a,b],\ j=1,\ldots,n.$$
Then the problem stated above becomes the problem of choosing optimal method of integration and optimal nodes of integration at which the function should be measured.

In practice, quite often a different approach is used, in which subsequent nodes of
integration are defined on the base of information about function values at the previous nodes.
Such algorithms are called adaptive (or sequential). In this regard, it makes sense to consider
a slightly different (more general) setting of the optimal recovery problem.

Let $\omega_1\in\Omega$ and functions
$$\omega_j\colon Y^{j-1}\to\Omega,\quad j=2,\ldots,n,$$
be given. In case of adaptive information, we assume that for $x\in W$ we know $\yy=(y_1,\ldots,y_n)$ such that
$$\|I_{p_j}x-y_j\|_Y\le\delta,\quad j=1,\ldots,n,$$
where $p_1=\omega_1$ and
\begin{equation}\label{pj}
p_j=\omega_j(y_1,\ldots,y_{j-1}),\quad j=2,\ldots,n.
\end{equation}
As recovery methods we consider all possible mappings
$$\varphi\colon Y^n\to Z.$$

For $x\in W$ we set
$$\Lambda(x)=\{\,(y_1,\ldots,y_n):\|I_{p_j}x-y_j\|_Y\le\delta,\ j=1,\ldots,n\,\},$$
where $p_1=\omega_1$ and $p_j$, $j=2,\ldots,n$, are defined by \eqref{pj}, that is, $\Lambda(x)$ is the set of all possible information $\yy$ about $x$.

The error of a method $\varphi$ is defined as follows
$$e^a_n(T,W,\mathcal I,\delta,\omega,\varphi)=\sup_{\substack{x\in W\\
\yy=(y_1,\ldots,y_n)\in\Lambda(x)}}\|Tx-\varphi(\yy)\|_Z;$$
here $\omega=(\omega_1,\ldots,\omega_n)$.
The value
$$E^a_n(T,W,\mathcal I,\delta)=\inf_{\omega,\varphi}e_n(T,W,\mathcal I,\delta,\omega,\varphi)$$
is called the error of optimal adaptive recovery.

Adaptive methods have a much richer structure and it is natural to expect that the error of adaptive recovery will be smaller than for nonadaptive recovery. This is what happens in a number of problems, such as calculating the root of a function or finding the maximum for an unimodal function (note that in these examples, the operator to be recovered is not linear). However, it turns out that there are cases when adaptive recovery does not give a win. In such cases, instead of complicated adaptive methods, it makes sense to use simpler nonadaptive methods.

The question of whether adaption helps to reduce the error of recovery has been studied in various papers. In \cite{Ba} it was proved that adaptive methods do not help when $T$ is a linear functional and $W$ is a convex and centrally-symmetric set. It was shown in \cite{GM} and \cite{TW} (see also \cite{Pl}) that adaption helps at most twice for recovery of linear operators $T$ over convex and symmetric sets $W$ (we extend this result for the generalized adaption in Theorem~\ref{T2.20}). In \cite{Ba}, \cite{GM}, and \cite{TW} only noiseless situation was considered. An example of such problem (with exact information) where adaption can help was given in \cite{KN1}, \cite{KN2}. It was shown in \cite{Ko}, \cite{No1}, \cite{No2} that for convex but not symmetric sets adaptive information can be significantly better than nonadaptive information.

The results on adaption versus nonadaption in the average case setting may be found in \cite{Was} and \cite{Pla93} (see also \cite{TWW} and \cite{Pl}).

In the present paper we give a generalized setting of adaptive recovery from noisy information and extend some known results for this setting. Our main results are sufficient conditions under which adaption does not help for recovery of linear operators (Theorem~\ref{T3}), an application of this result to recovery of derivatives by noisy information about the Fourier coefficients (Theorem~\ref{T4}), and criterion for the existence of an optimal nonadaptive linear method which gives the same error as optimal adaptive methods for recovery of linear functionals (Theorem~\ref{T5}).

\section{Generalized setting of adaptive recovery}


In adaptive recovery, we can define mappings
\begin{equation}\label{Phy}
\Phi(\yy)=(\omega_1,\omega_2(y_1),\ldots,\omega_n(y_1,\ldots,y_{n-1}))
\end{equation}
which for every $\yy=(y_1,\ldots,y_n)$ give the values of parameters $\pp=(p_1,\ldots,p_n)$ by the formula $\pp=\Phi(\yy)$. We now generalize the adaptive setting by allowing arbitrary mappings $\Phi(\yy)$.

We will consider the following problem of optimal adaptive recovery. Let $X$, $Z$, $T$, and $W$ be as above and $\mathcal Y$ be a linear space. Assume that there is a set of parameters $\mathcal P$ and for every $\pp\in\mathcal P$ a multivalued mapping
$$F_{\pp}\colon W\to\mathcal Y$$
is assigned (that is, for every $x\in W$ \ $F_{\pp}(x)$ is a set from $\mathcal Y$). The mapping $F_{\pp}$ represents the nonadaptive information corresponding to the indices $\pp\in\mathcal P$. Denote by $\mathcal F$ the set of all mappings $F_{\pp}$.

Suppose also that there is a mapping
$$\Phi\colon\mathcal Y\to\mathcal P.$$
As recovery methods of $T$ we consider all possible mappings
$\varphi\colon\mathcal Y\to Z$.

The error of a method $\varphi$ is defined as follows
$$e^a(T,\mathcal F,\Phi,\varphi)=\sup_{\substack{x\in W\\\yy\in F_{\Phi(\yy)}(x)}}\|Tx-\varphi(\yy)\|_Z,$$
and the value
$$E^a(T,\mathcal F)=\inf_{\Phi\colon\mathcal Y\to\mathcal P}\,\inf_{\varphi\colon\mathcal Y\to Z}e^a(T,\mathcal F,\Phi,\varphi)$$
is called the error of optimal adaptive recovery.

In this setting we do not see the sequential procedure in the explicit form. Nevertheless sequential procedures are included in the set of all mappings $\Phi$ (it suffices to take $\Phi$ in the form \eqref{Phy}).

By the nonadaptive problem of recovery for the considered case we mean the problem of finding the value
\begin{equation}\label{adg}
E(T,\mathcal F)=\inf_{\pp\in\mathcal P}\inf_{\varphi\colon\mathcal Y\to Z}e(T,\mathcal F,\pp,\varphi),
\end{equation}
where
$$e(T,\mathcal F,\pp,\varphi)=\sup_{\substack{x\in W\\\yy\in F_{\pp}(x)}}\|Tx-\varphi(\yy)\|_Z,$$
and also the problem of finding parameters and methods for which the lower bound is attained.

If $\Phi(\yy)=\pp$ for all $\yy\in\mathcal Y$, then
$$e^a(T,\mathcal F,\Phi,\varphi)=e(T,\mathcal F,\pp,\varphi).$$
Therefore,
\begin{equation}\label{adnead}
E^a(T,\mathcal F)\le E(T,\mathcal F).
\end{equation}


\section{Some relations between adaptive and nonadaptive recovery errors}

Set
$$\gr F_{\pp}:=\{\,(x,\yy):x\in W,\ \yy\in F_{\pp}(x)\,\}$$
and
$$F_{\pp}^{-1}(\yy)=\{\,x\in W:(x,\yy)\in\gr F_{\pp}\,\}.$$
Put
$$D(\pp)=\sup_{x\in F_{\pp}^{-1}(0)}\|Tx\|_Z.$$

\begin{theorem}\label{Tadap}
Assume that for all $\pp\in\mathcal P$ the sets $\gr F_{\pp}$ are centrally-symmetric and contain $0$. Then
$$E^a(T,\mathcal F)\ge\inf_{\pp\in\mathcal P}D(\pp).$$
\end{theorem}

\begin{proof}
It follows from the definition of $E^a(T,\mathcal F)$ that for any $\varepsilon>0$ there exist $\widehat\Phi$ and $\wva$ such that
$$e^a(T,\mathcal F,\widehat\Phi,\wva)\le E^a(T,\mathcal F)+\varepsilon.$$
Consider the value $D(\widehat\Phi(0))$. For any $\eta>0$ there exists a $\wx\in F_{\widehat\Phi(0)}^{-1}(0)$ such that
$$\|T\wx\|_Z\ge D(\widehat\Phi(0))-\eta.$$
Since the set $\gr F_{\widehat\Phi(0)}$ is centrally-symmetric $-\wx\in F_{\widehat\Phi(0)}^{-1}(0)$. We have
\begin{multline*}
2(D(\widehat\Phi(0))-\eta)\le2\|T\wx\|_Z=\|T\wx-\wva(0)-(T(-\wx)-\wva(0))\|_Z\\
\le\|T\wx-\wva(0)\|_Z+\|T(-\wx)-\wva(0)\|_Z\le2
e^a(T,\mathcal F,\widehat\Phi,\wva)\\
\le2(E^a(T,\mathcal F)+\varepsilon).
\end{multline*}
This implies that
$$D(\widehat\Phi(0))\le E^a(T,\mathcal F).$$
Consequently,
$$\inf_{\pp\in\mathcal P}D(\pp)\le E^a(T,\mathcal F).$$
\end{proof}

Put
$$e(T,\mathcal F,\pp)=\inf_{\varphi\colon\mathcal Y\to Z}e(T,\mathcal F,\pp,\varphi).$$

\begin{lemma}\label{23L}
Assume that for all $\pp\in\mathcal P$ the sets $\gr F_{\pp}$ are convex and centrally-symmetric. Then for all $\pp\in\mathcal P$
$$e(T,\mathcal F,\pp)\le2D(\pp).$$
\end{lemma}

\begin{proof}
Denote by $\Pr_{\mathcal Y}\gr F_{\pp}$ the set of $\yy\in\mathcal Y$ for which $F_{\pp}^{-1}(\yy)\ne\emptyset$. If $\yy\in\Pr_{\mathcal Y}\gr F_{\pp}$ and $x_1,x_2\in F_{\pp}^{-1}(\yy)$ then in view of convexity and centrally-symmetry of $\gr F_{\pp}$ \ $h=(x_1-x_2)/2\in F_{\pp}^{-1}(0)$. Set
$$\varphi_0(\yy)=\begin{cases}Tx(\yy),&\yy\in\Pr_{\mathcal Y}\gr F_{\pp},\\
0,&\yy\notin\Pr_{\mathcal Y}\gr F_{\pp},\end{cases}$$
where $x(\yy)$ is any element from $F_{\pp}^{-1}(\yy)$. Then for all $\yy\in\mathcal Y$
$$\sup_{x\in F_{\pp}^{-1}(\yy)}\|Tx-\varphi_0(\yy)\|_Z\le2\|Th\|_Z\le2D(\pp),$$
where $h=(x-x(\yy))/2\in F_{\pp}^{-1}(0)$. Thus,
$$e(T,\mathcal F,\pp,\varphi_0)=\sup_{\yy\in\Pr_{\mathcal Y}\gr F_{\pp}\vphantom{F^{-1}}}\,\sup_{x\in F_{\pp}^{-1}(\yy)}\|Tx-\varphi_0(\yy)\|_Z\le2D(\pp).$$
Consequently, for all $\pp\in\mathcal P$
$$e(T,\mathcal F,\pp)\le e(T,\mathcal F,\pp,\varphi_0)\le2D(\pp).$$
\end{proof}

In view of \eqref{adnead} from Theorem~\ref{Tadap} and Lemma~\ref{23L} we have

\begin{theorem}\label{T2.20}
If the sets $\gr F_{\pp}$ are convex and centrally-symmetric for all $\pp\in\mathcal P$, then
$$\frac12E(T,\mathcal F)\le E^a(T,\mathcal F)\le E(T,\mathcal F).$$
\end{theorem}

\begin{theorem}\label{T3}
Assume that for all $\pp\in\mathcal P$ the sets $\gr F_{\pp}$ are centrally-symmetric, contain $0$, and the equality
\begin{equation}\label{DD}
e(T,\mathcal F,\pp)=D(\pp)
\end{equation}
holds. Then
\begin{equation}\label{BE}
E^a(T,\mathcal F)=E(T,\mathcal F).
\end{equation}
\end{theorem}

\begin{proof}
It follows from Theorem~\ref{Tadap} that
$$E(T,\mathcal F)=\inf_{\pp\in\mathcal P}D(\pp)\le E^a(T,\mathcal F).$$
Taking into account \eqref{adnead} we obtain \eqref{BE}.
\end{proof}

Thus, in the case when condition \eqref{DD} holds optimal nonadaptive methods give the same error as optimal adaptive methods. In other words, in this case adaption does not help.

Condition \eqref{DD} is valid when $T$ is a linear functional (see \cite{MO}). But in some cases this condition may  be also valid for linear operators. We give one of such examples.

Let $\mathbb T$ be the interval $[-\pi,\pi]$ with identified endpoints. Denote by $\WR$ the Sobolev space of $2\pi$-periodic functions with absolutely continuous the $(r-1)$st derivative such that the $r$th derivative is in $\lT$. Set
$$\Wrt=\{\, x\cd\in\WR:\|x^{(r)}\cd\|_{\lT}\le1\,\}.$$
Consider the problem of optimal recovery of the $m$th derivative, $0\le m<r$, for functions from the class $\Wrt$ by their inaccurate Fourier coefficients.

Let $A\subset\mathbb Z_+$ and $B\subset\mathbb N$ be finite sets (one of them may be empty). Assume that for every function $x\cd\in\Wrt$ instead of exact values of the Fourier coefficients $a_k$, $k\in A$, and $b_k$, $k\in B$, we know their approximate values $\{\wa_k\}_{k\in A}$ and
$\{\wb_k\}_{k\in B}$ such that
$$|a_k-\wa_k|\le\delta,\quad k\in A,\quad|b_k-\wb_k|\le\delta,\quad k\in B.$$
Denote by $l_\infty^s$ the space $\mathbb R^s$ with the norm $\|\yy\|_{\infty}=\max_{0\le j\le s-1}|y_j|$, where
$\yy=(y_0,y_1,\ldots,y_{s-1})$. Let
$$A=\{\,k_0,k_1,\ldots,k_{N_1}\,\},\quad B=\{\,l_1,\ldots,l_{N_2}\,\},$$
where $k_0<\ldots<k_{N_1}$, $l_1<\ldots<l_{N_2}$ and $\card A+\card B=N_1+1+N_2=s$. Put
$$F_{A,B}x\cd=(a_{k_0},a_{k_1},\ldots,a_{k_{N_1}},b_{l_1},\ldots,b_{l_{N_2}}).$$
Then we may say that we know the vector $\yy\in l_\infty^s$ such that
$$\|F_{A,B}x\cd-\yy\|_{\infty}\le\delta.$$

In this case the error of a method $\varphi\colon\mathbb R^s\to\lT$ is defined as follows
$$e(D^m,\Wrt,F_{A,B},\delta,\varphi)=\sup_{\substack{x\cd\in\Wrt,\ \yy\in l_\infty^s\\
\|F_{A,B}x\cd-\yy\|_{\infty}\le\delta}}\|x^{(m)}\cd-\varphi(\yy)\cd\|_{\lT},$$
where $D^mx\cd=x^{(m)}\cd$.
The quantity
$$e(D^m,\Wrt,F_{A,B},\delta)=\inf_{\varphi\colon l_\infty^s\to\lT}e(D^m,\Wrt,F_{A,B},
\delta,\varphi)$$
is called the error of optimal recovery, and any method $\wva$ for which this infimum is attained is called an optimal method of recovery.

We are interested in the problem of choosing the parameter $\wP=(\wA,\wB)$, $\card\wA+\card\wB\le N$, so that the error of optimal recovery is minimal. In this problem we would like to consider both non-adaptive methods and adaptive ones. In terms of the general setting here $X=\WR$, $W=\Wrt$, $\mathcal Y=\mathbb R^N$, $T=D^m$, $Z=\lT$,
\begin{gather*}
\mathcal P=\mathcal P_N=\{\,(A,B)\in\mathbb Z_+\times\mathbb N:\card A+\card B\le N\,\},\\
F_{\pp}x\cd=\{\,\yy\in l_\infty^s:\|F_{A,B}x\cd-\yy\|_{\infty}\le\delta\,\},\quad s=\card A+\card B.
\end{gather*}

In \cite{MO1} it was proven that for all $\pp=(A,B)\in\mathcal P_N$
$$e(D^m,\mathcal F,\pp)=e(D^m,\Wrt,F_{A,B},\delta)=\sup_{\substack{x\cd\in\Wrt\\
\|F_{A,B}x\cd\|_{\infty}\le\delta}}\|x^{(m)}\cd\|_{\lT}.$$
Thus, any adaptive method (for example, those that choose the number of each next Fourier coefficient based on the values of the previously calculated coefficients) do not provide an advantage over the optimal non-adaptive method.

By virtue of the above, Theorem~4 of \cite{MO1} implies the following result.

\begin{theorem}\label{T4}
Set
$$\chi_m=\begin{cases}1,&m=0,\\
0,&m\in\mathbb N,\end{cases},\quad\wpp=\max\biggl\{s\in\mathbb Z_+ :
2\delta^2\sum_{k=0}^sk^{2r}<1,\ s\le[(N-\chi_m)/2]\,\biggr\}$$
$($$[a]$ is the integer part of $a$$)$. Then
\begin{multline*}
E^a(D^m,\mathcal F)=E(D^m,\mathcal F)\\
=\sqrt{\frac
1{(\wpp+1)^{2(r-m)}}+\frac{\delta^2}2\chi_m+2\delta^2\sum_{k=1}^{\wpp}k^{2m}
\left(1-\left(\frac k{\wpp+1}\right)^{2(r-m)}\right)},
\end{multline*}
the parameter $\wP=(\wA,\wB)$, where for $m=0$
$$\wA=(0,1,\ldots,\wpp),\quad\wB=(1,\ldots,\wpp),$$
and for $m>0$
$$\wA=(1,\ldots,\wpp),\quad\wB=(1,\ldots,\wpp).$$
The method
\begin{multline*}
\wva(\yy)(t)
=\frac{y_0}2\chi_m\\
+\sum_{k=1}^{\wpp}\left(1-\left(\frac k{\wpp+1}\right)^{2(r-m)}\right) k^m(y_k\cos
(kt+\pi m/2)+y_{k+\wpp}\sin(kt+\pi m/2))
\end{multline*}
is optimal.
\end{theorem}

\section{Criterion for existence of a linear method which is optimal for adaptive and nonadaptive recovery}

Define the mapping $G_\Phi$ by its graph
$$\gr G_\Phi=\{\,(x,\yy)\in W\times\mathcal Y:(x,\yy)\in\gr F_{\Phi(\yy)}\,\}.$$
Let $\yy\in\Pr_{\mathcal Y}\gr G_\Phi$. The value
$$r(T,\mathcal F,\Phi,\yy)=\infp_{z\in Z\vphantom{G_\Phi^{-1}}}\sup_{x\in G_\Phi^{-1}(\yy)}\|Tx-z\|_Z$$
is called the Chebyshev radius of the set $T(G_\Phi^{-1}(\yy))$. It is the radius of the minimal ball containing the given set. If there exists such $z(\yy)\in Z$ that
$$r(T,\mathcal F,\Phi,\yy)=\sup_{x\in G_\Phi^{-1}(\yy)}\|Tx-z(\yy)\|_Z,$$
then $z(\yy)$ is called the Chebyshev center of the set $T(G_\Phi^{-1}(\yy))$.

The value
$$R^a(T,\mathcal F)=\infp_{\Phi\colon\mathcal Y\to\mathcal P}\sup_{\yy\in\Pr_{\mathcal Y}\gr G_\Phi}r(T,\mathcal F,\Phi,\yy)$$
we call the adaptive radius of information in the problem of optimal adaptive recovery.

The analogous value was considered for nonadaptive recovery in \cite{MR}. It is defined as follows
$$R(T,\mathcal F)=\infp_{\pp\in\mathcal P\vphantom{x\in F_{\pp}^{-1}(\yy)}}\sup_{\yy\in\Pr_{\mathcal Y}\gr F_{\pp}\vphantom{x\in F_{\pp}^{-1}(\yy)}}\infp_{z\in Z\vphantom{x\in F_{\pp}^{-1}(\yy)}}\sup_{x\in F_{\pp}^{-1}(\yy)}\|Tx-z\|_Z.$$
It follows from \cite{MR} (see also \cite{MO}) that
\begin{equation}\label{Ch}
E(T,\mathcal F)=R(T,\mathcal F).
\end{equation}
Using the same scheme of proof we obtain the analogous result for adaptive recovery.

\begin{lemma}\label{L2}
The following equality
$$E^a(T,\mathcal F)=R^a(T,\mathcal F)$$
holds.
\end{lemma}

\begin{proof}
Let $\varphi\colon\mathcal Y\to Z$ be an arbitrary method of recovery. Then for all $\yy\in\Pr_{\mathcal Y}\gr G_\Phi$
$$r(T,\mathcal F,\Phi,\yy)\le\sup_{x\in G_\Phi^{-1}(\yy)}\|Tx-\varphi(\yy)\|_Z\le e^a(T,\mathcal F,\Phi,\varphi).$$
Taking the upper bound in the left-hand side over all $\yy\in\Pr_{\mathcal Y}\gr G_\Phi$ and then taking the lower bound over all methods, we obtain
$$\sup_{\yy\in\Pr_{\mathcal Y}\gr G_\Phi}r(T,\mathcal F,\Phi,\yy)\le \inf_{\varphi\colon\mathcal Y\to Z}e^a(T,\mathcal F,\Phi,\varphi).$$
Hence
\begin{equation}\label{Eaa}
R^a(T,\mathcal F)\le E^a(T,\mathcal F).
\end{equation}

Let us prove the opposite inequality. Let $\varepsilon>0$. For any $\yy\in\Pr_{\mathcal Y}\gr G_\Phi$ there exists a $z_\varepsilon(\yy)\in Z$ such that
$$\sup_{x\in G_\Phi^{-1}(\yy)}\|Tx-z_\varepsilon(\yy)\|_Z\le r(T,\mathcal F,\Phi,\yy)+\varepsilon.$$
We define the method $\varphi_\varepsilon\colon\mathcal Y\to Z$ as follows
$$\varphi_\varepsilon(\yy)=\begin{cases}z_\varepsilon(\yy),&\yy\in\Pr_{\mathcal Y}\gr G_\Phi,\\
0,&\yy\notin\Pr_{\mathcal Y}\gr G_\Phi.\end{cases}$$
Then
\begin{multline*}
e^a(T,\mathcal F,\Phi,\varphi_\varepsilon)=\sup_{(x,\yy)\in G_\Phi}\|Tx-\varphi_\varepsilon(\yy)\|_Z\\
=\sup_{\yy\in\Pr_{\mathcal Y}\gr G_\Phi\vphantom{G_\Phi^{-1}}}\sup_{x\in G_\Phi^{-1}(\yy)}\|Tx-\varphi_\varepsilon(\yy)\|_Z\le \sup_{\yy\in\Pr_{\mathcal Y}\gr G_\Phi}(r(T,\mathcal F,\Phi,\yy)+\varepsilon).
\end{multline*}
Consequently,
$$E^a(T,\mathcal F)\le R^a(T,\mathcal F)+\varepsilon.$$
In view of arbitrariness of $\varepsilon>0$ we obtain
$$E^a(T,\mathcal F)\le R^a(T,\mathcal F).$$
Together with \eqref{Eaa} this proves the statement of lemma.
\end{proof}

Denote by $\bco A$ the convex balanced hull of $A$. It consists of all elements of the form $$x=\lambda_1x_1+\ldots+\lambda_mx_m,\quad x_j\in A,\ j=1,\ldots,m,\quad\sum_{j=1}^m|\lambda_j|\le1.$$
We define the mapping $\bco F_{\pp}$ by its graph as follows
$$\gr\bco F_{\pp}=\bco\gr F_{\pp}.$$
Denote by $\mathcal F^{bco}$ the set of all mappings $\bco F_{\pp}$.

The idea of obtaining the following result is taking from \cite{MO}.

\begin{theorem}\label{T5}
Let $x'$ be a linear functional on $X$. For the existence of linear nonadaptive method with the optimal parameter $\wP\in\mathcal P$ which is optimal over all adaptive methods it is necessary and sufficient that
\begin{equation}\label{11}
R^a(x',\mathcal F)=R^a(x',\mathcal F^{bco})
\end{equation}
and
\begin{equation}\label{12}
D(\wP)=\inf_{\pp\in\mathcal P}D(\pp).
\end{equation}
\end{theorem}

\begin{proof}
Necessity. Let the method $\wva(\yy)=\la\yy',\yy\ra$, where $\yy'$ is a linear functional on $Y$, and the parameter $\wP\in\mathcal P$ be such that
$$e(x',\mathcal F,\wP,\wva)=E^a(x',\mathcal F).$$
Assume that $(x,\yy)\in\bco\gr F_{\wP}$. Then
$$(x,\yy)=\sum_{j=1}^m\lambda_j(x_j,\yy_j),$$
where $(x_j,\yy_j)\in\gr F_{\wP}$, $j=1,\ldots,m$, and $\sum_{j=1}^m|\lambda_j|\le1$. Consequently,
\begin{multline*}
|\la x',x\ra-\la\yy',\yy\ra|=\biggl|\sum_{j=1}^m\lambda_j(\la x',x_j\ra-\la\yy',\yy_j\ra)\biggr|\\
\le\max_{1\le j\le m}|\la x',x_j\ra-\la\yy',\yy_j\ra|\le  e(x',\mathcal F,\wP,\wva).
\end{multline*}
This implies that
$$e(x',\bco\mathcal F,\wP,\wva)\le e(x',\mathcal F,\wP,\wva).$$
Since
\begin{equation}\label{Fp}
\gr F_{\pp}\subset\gr\bco F_{\pp},
\end{equation}
we have
$$e(x',\bco\mathcal F,\wP,\wva)\ge e(x',\mathcal F,\wP,\wva).$$
Thus we obtain
\begin{equation}\label{epv}
e(x',\bco\mathcal F,\wP,\wva)=e(x',\mathcal F,\wP,\wva).
\end{equation}
Hence,
$$E(x',\bco\mathcal F)\le e(x',\bco\mathcal F,\wP,\wva)=e(x',\mathcal F,\wP,\wva)=E^a(x',\mathcal F).$$
In view of \eqref{adnead} we obtain
\begin{equation}\label{EaE}
E^a(x',\bco\mathcal F)\le E^a(x',\mathcal F).
\end{equation}
It follows from \eqref{Fp} that $E^a(x',\bco\mathcal F)\ge E^a(x',\mathcal F)$. This with \eqref{EaE} implies that
\begin{equation}\label{EEE}
E^a(x',\bco\mathcal F)=E^a(x',\mathcal F).
\end{equation}
By virtue of Lemma~\ref{L2} we obtain \eqref{11}.

Now we prove \eqref{12}. As it was noted above for linear functionals for any  $\pp\in\mathcal P$ the following equality
\begin{equation}\label{dv}
e(x',\bco\mathcal F,\pp)=D(\pp)
\end{equation}
holds. Taking into account \eqref{epv} and \eqref{EEE} we have
\begin{multline*}
D(\wP)=e(x',\bco\mathcal F,\wP)\le e(x',\bco\mathcal F,\wP,\wva)=e(x',\mathcal F,\wP,\wva)\\
=E^a(x',\mathcal F)=E^a(x',\bco\mathcal F)\le E(x',\bco\mathcal F)=\inf_{\pp\in\mathcal P}D(\pp).
\end{multline*}

Sufficiency. Assume that \eqref{11} and \eqref{12} hold. In view of the fact that the set $\bco\gr F_{\pp}$ is convex and balanced, it follows from \cite{MO} that for any $\pp\in\mathcal P$ there exists a $\wva_{\pp}(\yy)=\la\yy'_{\pp},\yy\ra$ such that
$$e(x',\bco\mathcal F,\pp)=e(x',\bco\mathcal F,\pp,\wva_{\pp}).$$
Set $\wva=\wva_{\wP}$. Then from \eqref{dv} and \eqref{12} we obtain
$$e(x',\bco\mathcal F,\wP,\wva)=E(x',\bco\mathcal F).$$
Moreover, it follows from \eqref{dv} and Theorem~\ref{T3} that
$$E(x',\bco\mathcal F)=E^a(x',\bco\mathcal F).$$
Therefore, taking into account \eqref{epv}, we obtain
\begin{multline*}
e(x',\mathcal F,\wP,\wva)=e(x',\bco\mathcal F,\wP,\wva)=E^a(x',\bco\mathcal F)\\
=R^a(x',\bco\mathcal F)=R^a(x',\mathcal F)=E^a(x',\mathcal F).
\end{multline*}
\end{proof}

The analog of Theorem~\ref{T5} can not be valid for linear operators since equality \eqref{DD} does not imply the existence of linear optimal method even for Hilbert spaces and exact information. We give one simple example which is the modified one from \cite{Os}. Let $X=\mathbb R^3$ with the Euclidean norm. Put
$$W=\{\,x\in\mathbb R^3:|x_1|+2|x_2|\le1,\ |x_3|\le2/15\,\}.$$
It is easy to see that $W$ is a convex and centrally-symmetric set. We consider optimal recovery of linear operator $T\colon\mathbb R^3\to\mathbb R^2$ defined as follows
$$Tx=(x_1,x_2),\quad x=(x_1,x_2,x_3),$$
by exact values of linear functional $Fx=x_1+x_3$ (here we will not mark the dependence on parameters since we have only one parameter). The norm in $\mathbb R^2$ is also Euclidean. We have
$$e(T,F)\ge D=\sup_{\substack{(x_1,x_2,x_3)\in W\\x_1+x_3=0}}||(x_1,x_2)||=\sup_{|x_1|+2|x_2|\le1,\ |x_1|\le2/15}||(x_1,x_2)||=\frac12.$$

Consider the method
$$\varphi_0(\yy)=\begin{cases}0,&|\yy|\le4/15,\\
(\yy,0),&|\yy|>4/15.\end{cases}$$
If $|x_1+x_3|\le4/15$, then
$$|x_1|=|x_1+x_3-x_3|\le|x_1+x_3|+|x_3|\le\frac25.$$
Consequently,
$$\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_1+x_3|\le4/15}}||(x_1,x_2)-
\varphi_0(x_1+x_3)||=\sup_{\substack{(x_1,x_2,x_3)\in
W\\|x_1|\le2/5}}||(x_1,x_2)||=\frac12.$$
If $(x_1,x_2,x_3)\in W$ and $|x_1+x_3|>4/15$, then $|x_1|\ge|x_1+x_3|-|x_3|>2/15$. Consequently, $|x_2|<13/30$. Therefore
\begin{multline*}
\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_1+x_3|>4/15}}||(x_1,x_2)-
\varphi_0(x_1+x_3)||\le\sup_{\substack{(x_1,x_2,x_3)\in W\\|x_2|<13/30}}
||(-x_3,x_2)||\\
<\sqrt{\frac4{225}+\frac{169}{900}}<\frac12.
\end{multline*}
Thus,
$$e(T,F)=D=\frac12.$$

Now we show that for any linear method the error of recovery is greater than $1/2$. For any linear method $\varphi(\yy)=(c_1\yy,c_2\yy)$, $c_1,c_2\in\mathbb R$, we have
$$e(T,F,\varphi)=\sup_{(x_1,x_2,x_3)\in W}\sqrt{(x_1-c_1(x_1+x_3))^2+
(x_2-c_2(x_1+x_3))^2}.$$
If $c_1\le0$, considering the point $(1,0,0)\in W$, we obtain
$$e(T,F,\varphi)\ge\sqrt{(1-c_1)^2+c_2^2}\ge1.$$
If $c_1>0$, considering the point $(0,1/2,2/15\sign c_2)\in W$, we obtain
$$e(T,F,\varphi)\ge\sqrt{c_1^2\frac4{15}+\left(\frac12+|c_2|\frac2{15}\right)^2}>\frac12.$$
Consequently,
$$e(T,F,\varphi)>\frac12=e(T,F).$$



In the last example we see that there is no linear optimal method of recovery but condition \eqref{DD} is satisfied. We give one more example to show that in general this condition is not fulfilled even for Hilbert spaces and exact information.

Let $X=\mathbb R^3$ with the Euclidean norm  $Tx=x$ and $Fx=x_1$, $x=(x_1,x_2,x_3)$. Consider the equilateral triangle $\Delta$ on the plane $x_1=1$ with vertexes at the points $A(1,0,1/\sqrt3)$, $B(1,-1/2,-1/(2\sqrt3))$, $C(1,1/2,-1/(2\sqrt3))$. Put $W=\bco\Delta$ (in other words, $W$ is the convex hull of $\Delta$ and $-\Delta\}$). It may be easily shown that the intersection of $W$ with the plane $x_1=0$ is the equilateral hexagon with the center at origin and with a side equal to $1/2$. Thus,
$$D=\sup_{\substack{x\in W\\Fx=0}}\|Tx\|=\sup_{\substack{x\in W\\x_1=0}}\|x\|=\frac12.$$
On the other hand, in view of \eqref{Ch} (here we do not mark the dependence on parameters again since we have only one parameter) we have
$$e(T,F)\ge\infp_{z\in\mathbb R^3}\sup_{\substack{x\in W\\x_1=1}}\|x-z\|_Z=\frac1{\sqrt3}>\frac12.$$
Consequently, $e(T,F)>D$.

\bigskip

The author is very grateful to the referees for a number of helpful comments and suggestions.


\begin{thebibliography}{11}

\bibitem{Ba} N.S.~Bakhvalov, On the optimality of linear methods for operator approximation in convex classes of functions, USSR Comput. Math. Math. Phys. 11 (1971) 244--249.

\bibitem{GM} S.~Gal, C.A.~Micchelli, Optimal sequential and non-sequential procedures for evaluating a functional, Appl. Anal. 10 (2) (1980) 105--120.

\bibitem{KN1} M.A.~Kon, E.~Novak, On the adaptive and continuous information problems, J. Complexity 5 (1989) 345--362.

\bibitem{KN2} M.A.~Kon, E.~Novak, The adaption problem for approximating linear operators, Bull. Amer. Math. Soc. 23 (1990) 159--165.

\bibitem{Ko} N.P.~Korneichuk, Optimization of active algorithms for recovery of monotonic functions from H\"older's class, J. Complexity 10 (1994) 265--269.

\bibitem{MO} G.G.~Magaril-Il'yaev, K.Yu.~Osipenko, Optimal recovery of functionals based on inaccurate data, Math. Notes 50 (6) (1991) 1274--1279.

\bibitem{MO1} G.G.~Magaril-Il'yaev, K.Yu.~Osipenko, On best harmonic synthesis of periodic functions, J. Math. Sci. 209 (1) (2015) 115--129.

\bibitem{MR} C.A.~Micchelli, T.J.~Rivlin, A survey of optimal recovery, Optimal
estimation in approximation theory, Proc. Internat. Sympos. (Freudenstadt 1976),
Plenum, New York 1977, 1--54.

\bibitem{No1} E.~Novak, Quadrature formulas for convex classes of functions, Ed. H. Bra\ss\ and G. H\"ammerlin, Numerical Integration IV, Birkh\"auser Verlag, Basel, 1993, 283--296.

\bibitem{No2} E.~Novak, The adaption problem for nonsymmetric convex sets, J. Approx. Theory 82 (1) (1995) 123--134.

\bibitem{Os} K.Yu.~Osipenko, Optimal recovery of linear functionals and operators, Communication on Applied Mathematics and Computation 30 (4) (2016) 459-482.

\bibitem{Pla93} L.~Plaskota, A note on varying cardinality in the average case setting, J. Complexity 9 (1993) 458--470.


\bibitem{Pl} L.~Plaskota, Noisy Information and Computational Complexity, Cambridge University Press, 1996.

\bibitem{TWW} J.F.~Traub, G.W.~Wasilkowski, and H. Wo\'zniakowski,
Information--based Complexity, Academic Press, New York, 1988.

\bibitem{TW} J.F.~Traub, H.~Wo\'zniakowski, A General Theory of
Optimal Algorithms, New York, Academic Press, 1980.

\bibitem{Was} G.W.~Wasilkowski, Information of varying cardinality,
J. Complexity 2 (1986) 204--228.


\end{thebibliography}





\end{document}