# Online Infinite-Dimensional Regression: Learning Linear Operators

Vinod Raman  Unique Subedi  Ambuj Tewari

###### Abstract

We consider the problem of learning linear operators under squared loss
between two infinite-dimensional Hilbert spaces in the online setting. We show
that the class of linear operators with uniformly bounded $p$-Schatten norm is
online learnable for any $p\in[1,\infty)$. On the other hand, we prove an
impossibility result by showing that the class of uniformly bounded linear
operators with respect to the operator norm is not online learnable. Moreover,
we show a separation between online uniform convergence and online
learnability by identifying a class of bounded linear operators that is online
learnable but uniform convergence does not hold. Finally, we prove that the
impossibility result and the separation between uniform convergence and
learnability also hold in the agnostic PAC setting.

##  1 Introduction

Learning operators between infinite-dimensional spaces is of fundamental
importance in many scientific and engineering applications. For instance, the
classical inverse problem is often modeled as learning an inverse mapping from
a function space of observed data to the function space of underlying latent
parameters, both of which are infinite-dimensional spaces (Kirsch, 2011;
Tarantola, 2005). Such inverse problems have found widespread applicability in
domains ranging from image processing, X-ray tomography, seismic inversion,
and so forth (Neto and da Silva Neto, 2012; Uhlmann, 2003). In addition, the
solution to a partial differential equation is an operator from a space of
functions specifying boundary conditions to the space of solution functions
(Kovachki et al., 2021; Li et al., 2020). Moreover, many of the traditional
learning settings such as multi-task learning, matrix completion, and
collaborative filtering can be modeled by learning operators between infinite-
dimensional spaces (Abernethy et al., 2009). Finally, many modern supervised
learning applications involve working with datasets, where both the features
and labels lie in high-dimensional spaces (Deng et al., 2009; Santhanam et
al., 2017). Thus, it is desirable to construct learning algorithms whose
guarantees do not scale with the ambient dimensions of the problem.

Most of the existing work in operator learning assumes some stochastic model
for the data, which can be unrealistic in many applications. For instance, the
majority of applications of operator learning are in the scientific domain
where the data often comes from experiments (Lin et al., 2021). Since
experiments are costly, the data arrives sequentially and usually with strong
temporal dependence, which may not be adequately captured by a stochastic
model. Additionally, given the high-dimensional nature of the data, one
typically uses pre-processing techniques like PCA to project the data onto a
low-dimensional space (Bhattacharya et al., 2021; Lanthaler, 2023). Even if
the original data has some stochastic nature, the preprocessing step
introduces non-trivial dependencies in the observations that may be difficult
to capture by a model. Accordingly, it is desirable to construct algorithms
that can handle arbitrary dependencies in the data. In fact, for continuous
problems such as scalar-valued regression, one can obtain guarantees similar
to that of i.i.d. setting without making any stochastic assumptions on the
data (Rakhlin and Sridharan, 2014).

In this paper, we study linear operator learning between two Hilbert spaces
$\mathcal{V}$ and $\mathcal{W}$ in the adversarial online setting, where one
makes no assumptions on the data generating process (Cesa-Bianchi and Lugosi,
2006). In this model, a potentially adversarial nature plays a sequential game
with the learner over $T$ rounds. In each round $t\in[T]$, nature selects a
pair of vectors $(v_{t},w_{t})\in\mathcal{\mathcal{V}}\times\mathcal{W}$ and
reveals $v_{t}$ to the learner. The learner then makes a prediction
$\hat{w}_{t}\in\mathcal{W}.$ Finally, the adversary reveals the target
$w_{t}$, and the learner suffers the loss
$\left\lVert\hat{w}_{t}-w_{t}\right\rVert^{2}_{\mathcal{W}}$. A linear
operator class $\mathcal{F}\subset\mathcal{W}^{\mathcal{V}}$ is online
learnable if there exists an online learning algorithm such that for any
sequence of labeled examples, the difference in cumulative loss between its
predictions and the predictions of the best-fixed operator in $\mathcal{F}$ is
small. In this work, we study the online learnability of linear operators and
make the following contributions:

  * (1)

We show that the class of linear operators with uniformly bounded $p$-Schatten
norm is online learnable with regret
$O(T^{\,\max\\{\frac{1}{2},1-\frac{1}{p}\\}})$. For any $\varepsilon>0$, we
also provide a lower bound of $\Omega(T^{1-\frac{1}{p}-\varepsilon})$, which
essentially matches the upperbound for $p\geq 2$.

  * (2)

We prove that the class of linear operators with uniformly bounded operator
norm is not online learnable. Furthermore, we show that this impossibility
result also holds in the PAC setting, thus rigorously establishing the claim
made by Tabaghi et al. (2019, Remark 1).

  * (3)

Recently, there is a growing interest in understanding when uniform
convergence and learnability are not equivalent (Montasser et al., 2019;
Hanneke et al., 2023). Along this direction, we give a subset of bounded
linear operators for which online learnability and uniform convergence are not
equivalent. We further show that this separation does not occur when the
output space is finite-dimensional.

To prove contribution (1), we upperbound the sequential Rademacher complexity
of the loss class to show that online uniform convergence holds for the
$p$-Schatten class for $p\in[1,\infty)$. For our hardness result stated in
contribution (2), we construct a class with a uniformly bounded operator norm
that is not online learnable. Our construction in contribution (3) is inspired
by and generalizes the example of Natarajan (1989, Page 22), which shows a gap
between uniform convergence and PAC learnability for multiclass
classification. The argument showing that uniform convergence does not hold is
a simple adaptation of the existing proof (Natarajan, 1989). However, since
our loss is real-valued, showing that the class is learnable requires some
novel algorithmic ideas, which can be of independent interest.

###  1.1 Related Works

Regression between two infinite-dimensional function spaces is a classical
statistical problem often studied in functional data analysis (FDA) (Wang et
al., 2016; Ferraty, 2006). In FDA, one typically considers $\mathcal{V}$ and
$\mathcal{W}$ to be $L^{2}[0,1]$, the space of square-integrable functions,
and the hypothesis class is usually the class of kernel integral operators. We
discuss the implication of our results to learning kernel integral operators
in Section 3.1. Recently, de Hoop et al. (2023); Nelsen and Stuart (2021);
Mollenhauer et al. (2022) study learning more general classes of linear
operators. However, all of these works are in the i.i.d. setting and assume a
data-generating process. Additionally, there is a line of work that uses deep
neural networks to learn neural operators between function spaces (Kovachki et
al., 2021; Li et al., 2020). Unfortunately, there are no known learning
guarantees for these neural operators. Closer to the spirit of our work is
that of Tabaghi et al. (2019), who consider the agnostic PAC learnability of
$p$-Schatten operators. They show that $p$-Schatten classes are agnostic PAC
learnable. In this work, we complement their work by showing that $p$-Schatten
classes are also online learnable. Going beyond i.i.d., there is also a line
of work that focuses on learning specific classes of operators from time
series data (Brunton et al., 2016; Klus et al., 2020).

##  2 Preliminaries

###  2.1  Hilbert Space Basics

Let $\mathcal{V}$ and $\mathcal{W}$ be real, separable, and infinite-
dimensional Hilbert spaces. Recall that a Hilbert space is separable if it
admits a countable orthonormal basis. Throughout the paper, we let
$\\{e_{n}\\}_{n=1}^{\infty}$ and $\\{\psi_{n}\\}_{n=1}^{\infty}$ denote a set
of orthonormal basis for $\mathcal{V}$ and $\mathcal{W}$ respectively. Then,
any element $v\in\mathcal{V}$ and $w\in\mathcal{W}$ can be written as
$v=\sum_{n=1}^{\infty}\beta_{n}e_{n}\text{ and
}w=\sum_{n=1}^{\infty}\alpha_{n}\psi_{n}$ for sequences
$\\{\beta_{n}\\}_{n\in\mathbb{N}}$ and $\\{\alpha_{n}\\}_{n=1}^{\infty}$ that
are $\ell_{2}$ summable.

Consider $w_{1},w_{2}\in\mathcal{W}$ such that
$w_{1}=\sum_{n=1}^{\infty}\alpha_{n,1}\,\psi_{n}$ and
$\sum_{n=1}^{\infty}\alpha_{n,2}\,\psi_{n}$. Then, the inner product between
$w_{1}$ and $w_{2}$ is defined as $\left\langle
w_{1},w_{2}\right\rangle_{\mathcal{W}}:=\sum_{n=1}^{\infty}\alpha_{n,1}\alpha_{n,2},$
and it induces the norm $\left\lVert
w_{1}\right\rVert_{\mathcal{W}}:=\sqrt{\left\langle
w_{1},w_{1}\right\rangle}_{\mathcal{W}}=\sqrt{\sum_{n=1}^{\infty}\alpha_{n,1}^{2}}$.
One can equivalently define
$\left\langle\cdot,\cdot\right\rangle_{\mathcal{V}}$ and
$\left\lVert\cdot\right\rVert_{\mathcal{V}}$ to be the inner-product and the
induced norm in the Hilbert space $\mathcal{V}$. When the context is clear, we
drop the subscript and simply write $\left\langle\cdot,\cdot\right\rangle$ and
$\left\lVert\cdot\right\rVert$.

A linear operator $f:\mathcal{V}\to\mathcal{W}$ is a mapping that preserves
the linear structure of the input. That is,
$f(c_{1}v_{1}+c_{2}v_{2})=c_{1}f(v_{1})+c_{2}f(v_{2})$ for any
$c_{1},c_{2}\in\mathbb{R}$ and $v_{1},v_{2}\in\mathcal{V}$. Let
$\mathcal{L}(\mathcal{V},\mathcal{W})$ denote the set of all linear operators
from $\mathcal{V}$ to $\mathcal{W}$. A linear operator
$f:\mathcal{V}\to\mathcal{W}$ is bounded if there exists a constant $c>0$ such
that $\left\lVert f(v)\right\rVert\leq c\left\lVert v\right\rVert$ for all
$v\in\mathcal{V}$. The quantity $\left\lVert
f\right\rVert_{\text{op}}:=\inf\\{c\geq 0\,:\left\lVert f(v)\right\rVert\leq
c\left\lVert v\right\rVert,\forall v\in\mathcal{V}\\}$ is called the operator
norm of $f$. The operator norm induces the set of bounded linear operators,
$\mathcal{B}(\mathcal{V},\mathcal{W})=\\{f\in\mathcal{L}(\mathcal{V},\mathcal{W})\,\mid\left\lVert
f\right\rVert_{\text{op}}<\infty\\},$ which is a Banach space with
$\left\lVert\cdot\right\rVert_{\text{op}}$ as the norm.

For an operator $f\in\mathcal{L}(\mathcal{V},\mathcal{W})$, let
$f^{\star}:\mathcal{W}\to\mathcal{V}$ denote the adjoint of $f$. We can use
$f$ and $f^{\star}$ to define a self-adjoint, non-negative operator
$f^{\star}f:\mathcal{V}\to\mathcal{V}$. Moreover, the absolute value operator
is defined as $|f|:=(f^{\star}f)^{\frac{1}{2}}$, which is the unique non-
negative operator such that $|f|\circ|f|=f^{\star}f$. Given any operator
$g:\mathcal{V}\to\mathcal{V}$, the trace of $g$ is defined as
$\operatorname{tr}(g)=\sum_{n=1}^{\infty}\left\langle
g(e_{n}),e_{n}\right\rangle,$ where $\\{e_{n}\\}_{n=1}^{\infty}$ is any
orthonormal basis of $\mathcal{V}$. The notion of trace and absolute value
allows us to define the $p$-Schatten norm of $f$,

$\left\lVert
f\right\rVert_{p}=\Big{(}\operatorname{tr}(|f|^{p})\Big{)}^{\frac{1}{p}},$

for all $p\in[1,\infty)$. Accordingly, we can define the $p$-Schatten class as

$S_{p}(\mathcal{V},\mathcal{W})=\\{f\in\mathcal{L}(\mathcal{V},\mathcal{W})\mid\left\lVert
f\right\rVert_{p}<\infty\\}.$

A linear operator $f:\mathcal{V}\to\mathcal{W}$ is compact if the closure of
the set $\\{f(v)\mid v\in\mathcal{V},\left\lVert v\right\rVert\leq 1\\}$ is
compact. For a compact linear operator $f:\mathcal{V}\to\mathcal{W}$, there
exists a sequence of orthonormal basis
$\\{\phi_{n}\\}_{n=1}^{\infty}\subset\mathcal{V}$ and
$\\{\varphi_{n}\\}_{n=1}^{\infty}\subset\mathcal{W}$ such that
$f=\sum_{n=1}^{\infty}s_{n}(f)\,\,\varphi_{n}\otimes\phi_{n}$, where
$s_{n}(f)\downarrow 0$ and $\varphi_{n}\otimes\phi_{n}$ denote the tensor
product between $\varphi_{n}$ and $\phi_{n}$. This is the singular value
decomposition of $f$ and the sequence $\\{s_{n}(f)\\}_{n=1}^{\infty}$ are the
singular values of $f$. For $p\in[1,\infty)$, the $p$-Schatten norm of a
compact operator is equal to the $\ell_{p}$ norm of the sequence
$\\{s_{n}(f)\\}_{n\geq 1}$,

$\left\lVert
f\right\rVert_{p}=\left(\sum_{n=1}^{\infty}s_{n}(f)^{p}\right)^{\frac{1}{p}}.$

Moreover, $\left\lVert f\right\rVert_{p}<\infty$ if and only if $f$ is a
compact operator. Thus, every operator in $S_{p}(\mathcal{V},\mathcal{W})$ is
a compact operator. On the other hand, for a compact operator $f$, the
$\ell_{\infty}$ norm of its singular values is equal to its operator norm,
$\left\lVert f\right\rVert_{\text{op}}=\left\lVert
f\right\rVert_{\infty}=\sup_{n\geq 1}|s_{n}(f)|.$ Accordingly, for compact
operators, the operator norm is referred to as $\infty$-Schatten norm, which
induces the class

$S_{\infty}(\mathcal{V},\mathcal{W})=\\{f\in\mathcal{L}(\mathcal{V},\mathcal{W})\mid
f\text{ is compact and }\left\lVert f\right\rVert_{\infty}<\infty\\}.$

Therefore,
$S_{\infty}(\mathcal{V},\mathcal{W})\subset\mathcal{B}(\mathcal{V},\mathcal{W})$.
For a comprehensive treatment of the theory of Hilbert spaces and linear
operators, we refer the reader to Conway (1990) and Weidmann (2012).

###  2.2 Online Learning

Let $\mathcal{X}\subseteq\mathcal{V}$ denote the instance space,
$\mathcal{Y}\subseteq\mathcal{W}$ denote the target space, and
$\mathcal{F}\subseteq\mathcal{L}(\mathcal{V},\mathcal{W})$ denote the
hypothesis class. In online linear operator learning, a potentially
adversarial nature plays a sequential game with the learner over $T$ rounds.
In each round $t\in[T]$, the nature selects a labeled instance
$(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$ and reveals $x_{t}$ to the
learner. The learner then makes a prediction $\hat{y}_{t}\in\mathcal{Y}.$
Finally, the adversary reveals the target $y_{t}$, and the learner suffers the
loss $\left\lVert\hat{y}_{t}-y_{t}\right\rVert^{2}_{\mathcal{W}}$.

We say that the linear operator class $\mathcal{F}$ is online learnable if
there exists an online learning algorithm such that for any sequence of
labeled examples, $(x_{1},y_{1}),...,(x_{T},y_{T})$, the difference in
expected cumulative loss between its predictions and the predictions of the
best-fixed operator in $\mathcal{F}$ is small. We formalize this notion in the
following definition.

######  Definition 1 (Online Linear Operator Learnability).

A linear operator class
$\mathcal{F}\subseteq\mathcal{L}(\mathcal{V},\mathcal{W})$ is online learnable
if there exists an algorithm $\mathcal{A}$ such that for any adaptively chosen
sequence of labeled examples $(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$,
the algorithm outputs $\mathcal{A}(x_{t})\in\mathcal{Y}$ at every iteration
$t\in[T]$ such that its _expected regret_ ,

$R_{\mathcal{A}}(T,\mathcal{F}):=\mathbb{E}\left[\sum_{t=1}^{T}\left\lVert\mathcal{A}(x_{t})-y_{t}\right\rVert^{2}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\left\lVert
f(x_{t})-y_{t}\right\rVert^{2}\right]$

is a non-decreasing sublinear function of $T$.

Unlike when $\mathcal{V}$ is finite-dimensional, the class
$\mathcal{F}=\mathcal{L}(\mathcal{V},\mathcal{W})$ is not online learnable
when $\mathcal{V}$ is infinite-dimensional. Accordingly, we are interested in
understanding for which subsets
$\mathcal{F}\subset\mathcal{L}(\mathcal{V},\mathcal{W})$ is online learning
possible. A general notion of complexity measure called the sequential
Rademacher complexity characterizes online uniform convergence Rakhlin et al.
(2015a, b), and thus provides a sufficient condition for online learnability.

######  Definition 2 (Sequential Rademacher Complexity).

Let $\sigma=\\{\sigma_{i}\\}_{i=1}^{T}$ be a sequence of independent
Rademacher random variables and $(x,y)=\\{(x_{t},y_{t})\\}_{t=1}^{T}$ be a
sequence of functions
$(x_{t},y_{t}):\\{-1,1\\}^{t-1}\to\mathcal{X}\times\mathcal{Y}$. Then, the
sequential Rademacher complexity of the loss class $\\{(v,w)\mapsto\left\lVert
f(v)-w\right\rVert^{2}\,:\,f\in\mathcal{F}\\}$ is defined as

$\emph{\text{Rad}}_{T}(\mathcal{F})=\sup_{x,y}\,\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\,\sum_{t=1}^{T}\sigma_{t}\left\lVert
f(x_{t}(\sigma_{<t}))-y_{t}(\sigma_{<t})\right\rVert^{2}\right],$

where $\sigma_{<t}=(\sigma_{1},\ldots,\sigma_{t-1}).$

If there exists a $B>0$ such that $\sup_{f,v,w}\left\lVert
f(v)-w\right\rVert^{2}\leq B$, then Theorem 1 of Rakhlin et al. (2015b)
implies that the online uniformconvergence holds for the loss class
$\\{(v,w)\mapsto\left\lVert f(v)-w\right\rVert^{2}\,:\,f\in\mathcal{F}\\}$ if
and only if $\text{Rad}_{T}(\mathcal{F})=o(T)$.

##  3 $p$-Schatten Operators are Online Learnable

In this section, we show that the class $S_{p}(\mathcal{V},\mathcal{W})$ is
online learnable. Despite not making any distributional assumptions, the rates
in Theorem 1 match the rates for the PAC setting obtained by Tabaghi et al.
(2019). This complements the results by Rakhlin and Sridharan (2014), who show
that the rates for scalar-valued regression with squared loss are similar for
online and PAC learning.

######  Theorem 1 (Uniformly Bounded Subsets of
$S_{p}(\mathcal{V},\mathcal{W})$ are Online Learnable).

Fix $c>0$. Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert
v\right\rVert\leq 1\\}$ denote the instance space,
$\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert w\right\rVert\leq c\\}$ denote
the target space, and $\mathcal{F}_{p}=\\{f\in
S_{p}(\mathcal{V},\mathcal{W})\,\mid\,\left\lVert f\right\rVert_{p}\leq c\\}$
be the hypothesis class. Then, for any labeled stream, there exists an
algorithm $\mathcal{A}$ such that its expected regret is

$\mathbb{E}\left[\sum_{t=1}^{T}\left\lVert\mathcal{A}(x_{t})-y_{t}\right\rVert^{2}-\inf_{f\in\mathcal{F}_{p}}\sum_{t=1}^{T}\left\lVert
f(x_{t})-y_{t}\right\rVert^{2}\right]\leq
2\,\emph{\text{Rad}}_{T}(\mathcal{F}_{p})\leq
6c^{2}\,T^{\,\max\\{\frac{1}{2},1-\frac{1}{p}\\}}.$

Theorem 1 implies the regret $O(\sqrt{T})$ for $p\in[1,2]$ and the regret
$O(T^{1-\frac{1}{p}})$ for $p>2$. When $p=\infty$, the regret bound implied by
Theorem 1 is vacuous. A similar phase transition was observed in the PAC
setting by Tabaghi et al. (2019). They provide intuition on why
$S_{\infty}(\mathcal{V},\mathcal{W})$ may not be PAC learnable, but do not
provide a proof. In Section 4, we prove that
$S_{\infty}(\mathcal{V},\mathcal{W})$ is neither PAC nor online learnable,
thus rigorously establishing a statement by Tabaghi et al. (2019, Remark 1).

Our proof of Theorem 1 relies on Lemma 2 which shows that the $q$-Schatten
norm of Rademacher sums of rank-1 operators concentrates. The proof of Lemma 2
is in Appendix A.

######  Lemma 2 (Rademacher Sums of Rank-1 Operators).

Let $\sigma=\\{\sigma_{i}\\}_{i=1}^{T}$ be a sequence of independent
Rademacher random variables and $\\{(v_{t},w_{t})\\}_{t=1}^{T}$ be any
sequence of functions
$(v_{t},w_{t}):\\{-1,1\\}^{t-1}\to\\{v\in\mathcal{V}\,:\left\lVert
v\right\rVert\leq c_{1}\\}\times\\{w\in\mathcal{W}\,:\left\lVert
w\right\rVert\leq c_{2}\\}$. Then, for any $q\geq 1$, we have

$\operatorname{\mathbb{E}}\left[\left\lVert\sum_{t=1}^{T}\sigma_{t}\,v_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right\rVert_{q}\right]\leq
c_{1}\,c_{2}\,T^{\max\left\\{\frac{1}{2},\frac{1}{q}\right\\}}$

Lemma 2 extends Lemma 1 in (Tabaghi et al., 2019) to the non-i.i.d. setting.
In particular, the rank-1 operator indexed by $t$ can depend on the Rademacher
subsequence $\sigma_{<t}$, whereas Tabaghi et al. (2019) only consider the
case when the rank-1 operators are independent of the Rademacher sequence. In
addition, Tabaghi et al. (2019) use a non-trivial result from convex analysis,
namely the fact that $A\mapsto\operatorname{tr}(h(F))$ is a convex functional
on the set $\\{F\in\mathcal{T}\mid\text{spectra}(F)\subseteq[\alpha,\beta]\\}$
for any convex function $h$ and the class of finite-rank self-adjoint
operators $\mathcal{T}$. Our proof of Lemma 2, on the other hand, only uses
standard inequalities.

Equipped with Lemma 2, our proof of Theorem 1 follows by upper bounding the
sequential Rademacher complexity of the loss class. Although this proof of
online learnability is non-constructive, we can use Proposition 1 from
(Rakhlin et al., 2012) to design an explicit online learner that achieves the
matching regret given access to an oracle that computes the sequential
Rademacher complexity of the class.

###  3.1 Examples of $p$-Schatten class

In this section, we provide examples of operator classes with uniformly
bounded $p$-Schatten norm.

Uniformly bounded operators w.r.t. $\left\lVert\cdot\right\rVert_{\text{op}}$
when either $\mathcal{V}$ or $\mathcal{W}$ is finite-dimensional. If either
the input space $\mathcal{V}$ or the output space $\mathcal{W}$ is finite-
dimensional, then the class of bounded linear operators
$\mathcal{B}(\mathcal{V},\mathcal{W})$ is $p$-Schatten class for every
$p\in[1,\infty]$. This is immediate because for every
$f\in\mathcal{B}(\mathcal{V},\mathcal{W})$, either the operator
$f^{\star}f:\mathcal{V}\to\mathcal{V}$ or
$ff^{\star}:\mathcal{W}\to\mathcal{W}$ is a bounded operator that maps between
two finite-dimensional spaces. Let $\left\lVert f\right\rVert_{\text{op}}\leq
c$ and $\min\\{\text{dim}(\mathcal{V}),\text{dim}(\mathcal{W})\\}=d<\infty$.
Since $f^{\star}f$ and $ff^{\star}$ have the same singular values and one of
them has rank at most $d$, both of them must have rank at most $d$. Let
$s_{1}\geq s_{2}\ldots\geq s_{d}\geq 0$ denote all singular values of
$f^{\star}f$. Then, $\left\lVert
f\right\rVert_{p}=\left(\sum_{i=1}^{d}s_{i}^{p}\right)^{\frac{1}{p}}\leq
c\,d^{\frac{1}{p}}<\infty,$ where we use the fact that $s_{i}\leq c$ for all
$i$. Since $\left\lVert f\right\rVert_{2}\leq c\,\sqrt{d}$, Theorem 1 implies
that $\mathcal{F}=\\{f\in\mathcal{B}(\mathcal{V},\mathcal{W})\,\mid\left\lVert
f\right\rVert_{\text{op}}\leq c\\}$ is online learnable with regret at most
$6c^{2}d\sqrt{T}$.

Kernel Integral Operators. Let $\mathcal{V}$ denote a Hilbert space of
functions defined on some domain $\Omega$. Then, a kernel
$K:\Omega\times\Omega\to\mathbb{R}$ defines an integral operator
$f_{K}:\mathcal{V}\to\mathcal{W}$ such that
$f_{K}(v(r))=\int_{\Omega}\,K(r,s)\,v(s)\,d\mu(s),$ for some measure space
$(\Omega,\mu)$. Now define a class of integral operators,

$\mathcal{F}=\left\\{f_{K}\,:\,\int_{\Omega}\int_{\Omega}\,|K(r,s)|^{2}\,d\mu(r)\,d\mu(s)\leq
c^{2}\right\\},$

induced by all the kernels whose $L^{2}$ norm is bounded by $c$. It is well
known that $\left\lVert f\right\rVert_{2}\leq c$ for every $f\in\mathcal{F}$
(see (Conway, 1990, Page 267) and (Weidmann, 2012, Theorem 6.11)) . Thus,
Theorem 1 implies that $\mathcal{F}$ is online learnable with regret
$6c^{2}\sqrt{T}$.

##  4 Lower Bounds and Hardness Results

In this section, we establish lower bounds for learning various subsets of
$\mathcal{L}(\mathcal{V},\mathcal{W})$. We first establish a generic lower
bound for a class
$\mathcal{G}^{\gamma}\subset\mathcal{L}(\mathcal{V},\mathcal{W})$ in terms of
a class parameter $\gamma$. Then, for each $p\in[1,\infty]$, we show that we
can pick a $\gamma$ such that $\mathcal{G}^{\gamma}\subseteq
S_{p}(\mathcal{V},\mathcal{W})$. Thus, the lower bound for learning
$\mathcal{G}^{\gamma}$ implies the lower bound for learning
$S_{p}(\mathcal{V},\mathcal{W})$.

######  Lemma 3 (Lower Bounds for Operator Classes with Fixed Decomposition).

Let $\mathcal{V}$ and $\mathcal{W}$ be Hilbert spaces with orthonormal basis
$\\{e_{i}\\}_{i\in\mathbb{N}}$ and $\\{\psi_{i}\\}_{i\in\mathbb{N}}$
respectively. Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert
v\right\rVert\leq 1\\}$ denote the instance space and
$\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert w\right\rVert\leq 1\\}$ denote
the target space. For a sequence $\gamma=\\{\gamma_{n}\\}_{n\in\mathbb{N}}$
such that $\gamma_{n}\in[0,1]$, define the linear operator class

$\mathcal{G}^{\gamma}=\cup_{n\in\mathbb{N}}\,\mathcal{G}_{n}^{\gamma}\quad\text{
where
}\quad\mathcal{G}_{n}^{\gamma}=\left\\{\sum_{i=1}^{n}\sigma_{i}\,\gamma_{i}\,\psi_{i}\otimes
e_{i}\mid\sigma\in\\{\pm 1\\}^{n}\right\\}.$ (1)

Then, for any algorithm, there exists a stream such that its expected regret
is at least $\sum_{t=1}^{T}\gamma_{t}$.

Operator classes like $\mathcal{G}^{\gamma}$, where the singular value
decomposition is known to the learner apriori, are important from a practical
standpoint because learning them reduces to learning the sequence of singular
values (de Hoop et al., 2023).

###### Proof.

Fix an algorithm $\mathcal{A}$, and consider a labeled stream
$\\{(e_{t},\sigma_{t}\psi_{t})\\}_{t=1}^{T}$ where
$\sigma_{t}\sim\text{Unif}(\\{-1,1\\})$. Then, the expected loss of
$\mathcal{A}$ is

$\begin{split}\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert\mathcal{A}(e_{t})-\sigma_{t}\psi_{t}\right\rVert^{2}\right]\geq\sum_{t=1}^{T}\left(\operatorname{\mathbb{E}}\left[\left\lVert\mathcal{A}(e_{t})-\sigma_{t}\psi_{t}\right\rVert\right]\right)^{2}&=\sum_{t=1}^{T}\left(\operatorname{\mathbb{E}}_{\mathcal{A}}\left[\frac{1}{2}\left\lVert\mathcal{A}(x_{t})-\psi_{t}\right\rVert+\frac{1}{2}\left\lVert\mathcal{A}(x_{t})+\psi_{t}\right\rVert\right]\right)^{2}\\\
&\geq\sum_{t=1}^{T}\left(\frac{1}{2}\left\lVert\psi_{t}-(-\psi_{t})\right\rVert\right)^{2}=\sum_{t=1}^{T}\left\lVert\psi_{t}\right\rVert^{2}=T.\end{split}$

The first inequality above is due to Jensen’s, whereas the second inequality
is the reverse triangle inequality.

To establish the upper bound on the optimal cumulative loss amongst operators
in $\mathcal{G}^{\gamma}$, consider the operator
$g_{\sigma}^{\gamma}:=\sum_{t=1}^{T}\sigma_{i}\,\gamma_{i}\,\psi_{i}\otimes
e_{i}$. Clearly,
$g_{\sigma}^{\gamma}\in\mathcal{G}_{T}^{\gamma}\subset\mathcal{G}^{\gamma}$.
Note that
$g_{\sigma}^{\gamma}(e_{t})=\sum_{i=1}^{T}\sigma_{i}\,\gamma_{i}\left\langle
e_{i},e_{t}\right\rangle\psi_{i}=\sigma_{t}\gamma_{t}\,\psi_{t}$ because
$\left\langle e_{i},e_{t}\right\rangle=0$ for all $i\neq t$. Thus, we obtain

$\begin{split}\operatorname{\mathbb{E}}\left[\inf_{g\in\mathcal{G}^{\gamma}}\sum_{t=1}^{T}\left\lVert
g(e_{t})-\sigma_{t}\psi_{t}\right\rVert^{2}\right]\leq\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert
g_{\sigma}^{\gamma}(e_{t})-\sigma_{t}\psi_{t}\right\rVert^{2}\right]=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert\sigma_{t}\,\gamma_{t}\psi_{t}-\sigma_{t}\psi_{t}\right\rVert^{2}\right]=\sum_{t=1}^{T}\left(\gamma_{t}-1\right)^{2},\end{split}$

where the final step follows because
$\left\lVert\sigma_{t}\,\psi_{t}\right\rVert^{2}=1$. Therefore, since
$\gamma_{t}^{2}\leq\gamma_{t}$, the regret of $\mathcal{A}$ is

$\begin{split}\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert\mathcal{A}(e_{t})-\sigma_{t}\psi_{t}\right\rVert^{2}-\inf_{g\in\mathcal{G}^{\gamma}}\sum_{t=1}^{T}\left\lVert
g(e_{t})-\sigma_{t}\psi_{t}\right\rVert^{2}\right]&\geq
T-\sum_{t=1}^{T}\left(\gamma_{t}-1\right)^{2}=\sum_{t=1}^{T}\left(2\gamma_{t}-\gamma_{t}^{2}\right)\geq\sum_{t=1}^{T}\gamma_{t}.\end{split}$

∎

By carefully picking the sequence $\gamma$, we use Lemma 3 to give a lower
bound for $S_{p}(\mathcal{V},\mathcal{W})$ and to show that
$S_{\infty}(\mathcal{V},\mathcal{W})$ is not online learnable. Since
$S_{\infty}(\mathcal{V},\mathcal{W})$ is the set of compact operators in
$\mathcal{B}(\mathcal{V},\mathcal{W})$, our result thus implies that the set
of bounded linear operators is not online learnable. We defer the proofs of
Theorems 4 and 5 to Appendix B.

######  Theorem 4 (Lower Bounds for $S_{p}(\mathcal{V},\mathcal{W})$).

Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert v\right\rVert\leq 1\\}$
denote the instance space, $\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert
w\right\rVert\leq 1\\}$ denote the target space, and $\mathcal{F}_{p}=\\{f\in
S_{p}(\mathcal{V},\mathcal{W})\,\mid\,\left\lVert f\right\rVert_{p}\leq 1\\}$
be the hypothesis class for $p\in[1,\infty)$. Then, for any algorithm
$\mathcal{A}$ and $\varepsilon>0$, there exists a labeled stream such that the
expected regret of any algorithm $\mathcal{A}$ is
$\Omega(T^{1-\frac{1}{p}-\varepsilon})$.

######  Theorem 5 (Uniformly Bounded Subsets of
$S_{\infty}(\mathcal{V},\mathcal{W})$ are Not Online Learnable).

Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert v\right\rVert\leq 1\\}$
denote the instance space, $\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert
w\right\rVert\leq 1\\}$ denote the target space, and
$\mathcal{F}_{\infty}=\\{f\in
S_{\infty}(\mathcal{V},\mathcal{W})\,\mid\,\left\lVert
f\right\rVert_{\infty}\leq 1\\}$ be the hypothesis class. Then, there exists a
labeled stream such that the expected regret of any algorithm $\mathcal{A}$ is
at least $T$.

###  4.1 Lower Bounds in the Agnostic PAC setting

In this section, we study the lower bounds of learning linear operators in the
agnostic PAC framework (see Definition 3). Our result here complements the
work of Tabaghi et al. (2019), who study the agnostic PAC upper bounds of
learning $p$-Schatten class for $p\in[1,\infty)$.

######  Theorem 6 (Agnostic PAC Lower Bounds for
$S_{p}(\mathcal{V},\mathcal{W})$).

Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert v\right\rVert\leq 1\\}$
denote the instance space, $\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert
w\right\rVert\leq 1\\}$ denote the target space, and $\mathcal{F}_{p}=\\{f\in
S_{p}(\mathcal{V},\mathcal{W})\,\mid\,\left\lVert f\right\rVert_{p}\leq 1\\}$
be the hypothesis class. For any $n\in\mathbb{N},\varepsilon>0$ and agnostic
PAC learning algorithm $\mathcal{P}$, there exists a distribution
$\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$ such that with probability at
least $\frac{1}{8}$, the excess risk of $\mathcal{P}$ trained on $n$ i.i.d.
samples from the source distribution $\mathcal{D}$ is at least
$\Omega(n^{-\frac{1}{p}-\varepsilon})$.

We note that the lower bound in Theorem 6 essentially matches the upperbound
provided by Tabaghi et al. (2019). Next, we show that bounded linear operators
are not learnable in the agnostic PAC setting. This shows that the vacuousness
of the bound obtained by Tabaghi et al. (2019, Theorem 2) for $p=\infty$ is
not an artifact of their proof technique but an expected phase transition
given our impossibility result.

######  Theorem 7 (Uniformly Bounded Subsets of
$S_{\infty}(\mathcal{V},\mathcal{W})$ are Not Agnostic PAC Learnable).

Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert v\right\rVert\leq 1\\}$
denote the instance space, $\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert
w\right\rVert\leq 1\\}$ denote the target space, and
$\mathcal{F}_{\infty}=\\{f\in
S_{\infty}(\mathcal{V},\mathcal{W})\,\mid\,\left\lVert
f\right\rVert_{\infty}\leq 1\\}$ be the hypothesis class. For any
$n\in\mathbb{N}$ and agnostic PAC learning algorithm $\mathcal{P}$, there
exists a distribution $\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$ such
that with probability at least $\frac{1}{8}$, the excess risk of $\mathcal{P}$
trained on $n$ i.i.d. samples from the source distribution $\mathcal{D}$ is at
least $\frac{1}{4}$.

##  5 Online Learnability without Online Uniform Convergence

In learning theory, the uniform law of large numbers is intimately related to
the learnability of a hypothesis class. For instance, a binary hypothesis
class is PAC learnable if and only if the hypothesis class satisfies the
i.i.d. uniform law of large numbers (Shalev-Shwartz and Ben-David, 2014). An
online equivalent of this result states that a binary hypothesis class is
online learnable if and only if the hypothesis class satisfies the online
uniform law of large numbers (Rakhlin et al., 2015b). However, in a recent
work, Hanneke et al. (2023) show that uniform convergence and learnability are
not equivalent for online multiclass classification. A key factor in Hanneke
et al. (2023)’s proof is the unboundedness of the size of the label space.
This unboundedness is critical as the equivalence between uniform convergence
and learnability continues to hold for multiclass classification with a finite
number of labels (Daniely et al., 2011). Nevertheless, the number of labels
alone cannot imply a separation. This is true because a real-valued function
class (say $\mathcal{G}\subseteq[-1,1]^{\mathcal{X}}$ where the size of label
space is uncountably infinite) is online learnable with respect to
absolute/squared-loss if and only if the uniform convergence holds (Rakhlin et
al., 2015a). In this section, we show an analogous separation between uniform
convergence and learnability for online linear operator learning. As the
unbounded label space was to Hanneke et al. (2023), the infinite-dimensional
nature of the target space is critical to our construction exhibiting this
separation. Mathematically, a unifying property of Hanneke et al. (2023)’s and
our construction is the fact that the target space $\mathcal{Y}$ is not
totally bounded with respect to the pseudometric defined by the loss function.

The following result establishes a separation between uniform convergence and
learnability for online linear operator learning. In particular, we show that
there exists a class of linear operators $\mathcal{F}$ such that the online
uniform law of large numbers does not hold, but $\mathcal{F}$ is still online
learnable.

######  Theorem 8 (Online Uniform Convergence $\not\equiv$ Online
Learnability).

Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\sum_{n=1}^{\infty}|c_{n}|\leq 1\text{
where }v=\sum_{n=1}^{\infty}c_{n}e_{n}\\}$ be the instance space and
$\mathcal{Y}=\\{v\in\mathcal{V}\mid\left\lVert v\right\rVert\leq 1\\}$ be the
target space. Then, there exists a function class $\mathcal{F}\subset
S_{1}(\mathcal{V},\mathcal{V})\subset S_{\infty}(\mathcal{V},\mathcal{V})$
such that the following holds:

  * _(i)_

$\emph{\text{Rad}}_{T}(\mathcal{F})\geq\frac{T}{2}$

  * _(ii)_

There exists an online learner for $\mathcal{F}$ such that its expected regret
on any stream is at most $2+8\sqrt{T\log{(2T)}}$, a sublinear function of $T$.

###### Proof.

For a natural number $k\in\mathbb{N}$, define an operator
$f_{k}:\mathcal{V}\to\mathcal{V}$ as

$f_{k}:=\sum_{n=1}^{\infty}b_{k}[n]\,\,e_{k}\otimes
e_{n}=e_{k}\otimes\sum_{n=1}^{\infty}b_{k}[n]\,e_{n}$ (2)

where $b_{k}$ is the binary representation of the natural number $k$ and
$b_{k}[n]$ is its $n^{th}$ bit. Define $\mathcal{F}=\\{f_{k}\mid
k\in\mathbb{N}\\}\cup\\{f_{0}\\}$ where $f_{0}=0$ .

We begin by showing that $\mathcal{F}\subset S_{1}(\mathcal{V},\mathcal{V})$.
For any $\alpha,\beta\in\mathbb{R}$ and $v_{1},v_{2}\in\mathcal{V}$, we have

$f_{k}(\alpha v_{1}+\beta v_{2})=\sum_{n=1}^{\infty}b_{k}[n]\,\,\left\langle
e_{n},\alpha v_{1}+\beta v_{2}\right\rangle e_{k}=\alpha f_{k}(v_{1})+\beta
f_{k}(v_{2}).$

Thus, $f_{k}$ is a linear operator. Note that $f_{k}$ is defined in terms of
singular value decomposition, and has only one non-zero singular value along
the direction of $e_{k}$. Therefore,

$\left\lVert
f_{k}\right\rVert_{1}=\sum_{n=1}^{\infty}b_{k}[n]\leq\log_{2}(k)+1,$

where we use the fact that there can be at most $\log_{2}(k)+1$ non-zero bits
in the binary representation of $k$. This further implies that $\left\lVert
f_{k}\right\rVert_{p}\leq\left\lVert
f_{k}\right\rVert_{1}\leq\log_{2}(k)+1<\infty$ for all $p\in[1,\infty]$. Note
that each $f_{k}$ maps a unit ball in $\mathcal{V}$ to a subset of
$\\{\alpha\,e_{k}\,:|\alpha|\leq\log_{2}(k)+1\\}$, which is a compact set for
every $k\in\mathbb{N}$. Thus, for every $k\in\mathbb{N}$, $f_{k}$ is a compact
operator and $f_{k}\in S_{1}(\mathcal{V},\mathcal{V})$. We trivially have
$f_{0}\in S_{1}(\mathcal{V},\mathcal{V})$.

Proof of (i). Let $\sigma=\\{\sigma_{t}\\}_{t=1}^{T}$ be a sequence of i.i.d.
Rademacher random variables. Consider a sequence of functions
$(x,y)=\\{x_{t},y_{t}\\}_{t=1}^{T}$ such that $x_{t}(\sigma_{<t})=e_{t}$ and
$y_{t}(\sigma_{<t})=0$ for all $t\in[T]$. Note that our sequence
$\\{e_{t}\\}_{t=1}^{T}\subseteq\mathcal{X}$. Then, the sequential Rademacher
complexity of the loss class is

$\begin{split}\text{Rad}_{T}(\mathcal{F})=\sup_{x,y}\,\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\sigma_{t}\left\lVert
f(x_{t}(\sigma_{<t}))-y_{t}(\sigma_{<t})\right\rVert^{2}\right]&\geq\operatorname{\mathbb{E}}\left[\sup_{k\in\mathbb{N}}\sum_{t=1}^{T}\sigma_{t}\left\lVert
f_{k}(e_{t})\right\rVert^{2}\right]\\\
&=\operatorname{\mathbb{E}}\left[\sup_{k\in\mathbb{N}}\sum_{t=1}^{T}\sigma_{t}\,b_{k}[t]\right]\\\
&\geq\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\sigma_{t}=1\\}\right]=\frac{T}{2}.\end{split}$

Here, we use the fact that $f_{k}(e_{t})=b_{k}[t]\,e_{k}$ and
$\mathbb{P}[\sigma_{t}=1]=\frac{1}{2}$. As for the inequality
$\sup_{k\in\mathbb{N}}\sum_{t=1}^{T}\sigma_{t}\,b_{k}[t]\geq\sum_{t=1}^{T}\mathbbm{1}\\{\sigma_{t}=1\\}$,
note that for any sequence $\\{\sigma_{t}\\}_{t=1}^{T}$, there exists a
$k\in\mathbb{N}$ (possibly of the order $\sim 2^{T}$) such that $b_{k}[t]=1$
whenever $\sigma_{t}=1$ and $b_{k}[t]=0$ whenever $\sigma_{t}=-1$.

Proof of (ii). We now construct an online learner for $\mathcal{F}$. Let
$(x_{1},y_{1})\ldots,(x_{T},y_{T})\in\mathcal{X}\times\mathcal{Y}$ denote the
data stream. Since $y_{t}$ is an element of unit ball of $\mathcal{V}$, we can
write $y_{t}=\sum_{n=1}^{\infty}c_{n}(t)e_{n}$ such that
$\sum_{n=1}^{\infty}c_{n}^{2}(t)\leq 1$. For each $t\in[T]$, define a set of
indices $S_{t}=\\{n\in\mathbb{N}\,:\,|c_{n}(t)|\geq\frac{1}{2\sqrt{T}}\\}$.
Since

$1\geq\left\lVert
y_{t}\right\rVert^{2}=\sum_{n=1}^{\infty}c_{n}^{2}(t)\geq\sum_{n\in
S_{t}}c_{n}^{2}(t)\geq\sum_{n\in S_{t}}\frac{1}{4T}=\frac{|S_{t}|}{4T},$

we have $|S_{t}|\leq 4T$. Let $\text{sort}(S_{i})$ denote the ordered list of
size $4T$ that contains elements of $S_{i}$ in descending order. If $S_{i}$
does not contain $4T$ indices, append $0$’s to the end of
$\text{sort}(S_{i})$. We let $\text{sort}(S_{i})[j]$ denote the $j^{th}$
element of the ordered list $\text{sort}(S_{i})$.

For each $i\in[T]$ and $j\in[4T]$, define an expert $E_{i}^{j}$ such that

$E_{i}^{j}(x_{t})=\begin{cases}0,\quad\quad\quad\,\,t\leq i\\\
f_{k}(x_{t}),\quad t>i\end{cases},\quad\quad\text{ where
}k=\text{sort}(S_{i})[j].$

An online learner $\mathcal{A}$ for $\mathcal{F}$ runs multiplicative weights
algorithm using the set of experts $\mathcal{E}=\\{E_{i}^{j}\,\mid
i\in[T],j\in[4T]\\}$. It is easy to see that $\left\lVert
f_{k}(x)\right\rVert\leq 1$ for all $x\in\mathcal{X}$. Thus, for any
$\hat{y}_{t},y_{t}\in\mathcal{Y}$, we have
$\left\lVert\hat{y}_{t}-y_{t}\right\rVert^{2}\leq 4$. Thus, for an
appropriately chosen learning rate, the multiplicative weights algorithm
guarantees (see Theorem 21.11 in Shalev-Shwartz and Ben-David (2014)) that the
regret of $\mathcal{A}$ satisfies

$\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert\mathcal{A}(x_{t})-y_{t}\right\rVert^{2}\right]\leq\inf_{E\in\mathcal{E}}\sum_{t=1}^{T}\left\lVert
E(x_{t})-y_{t}\right\rVert^{2}+4\sqrt{2T\ln(|\mathcal{E}|)}.$

Note that $|\mathcal{E}|\leq 4T^{2}$, which implies
$4\sqrt{2T\ln(|\mathcal{E}|)}\leq 8\sqrt{T\ln(2T)}$. We now show that

$\inf_{E\in\mathcal{E}}\sum_{t=1}^{T}\left\lVert
E(x_{t})-y_{t}\right\rVert^{2}\leq\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\left\lVert
f(x_{t})-y_{t}\right\rVert^{2}+2.$

Together, these two inequalities imply that the expected regret of
$\mathcal{A}$ is $\leq 2+8\sqrt{T\ln(2T)}$. The rest of the proof is dedicated
to proving the latter inequality.

Let
$f_{k^{\star}}\in\operatorname*{arg\,min}_{f\in\mathcal{F}}\sum_{t=1}^{T}\left\lVert
f(x_{t})-y_{t}\right\rVert^{2}$. Let $t^{\star}\in[T]$ be the first time point
such that $k^{\star}\in S_{t^{\star}}$ and suppose it exists. Let
$r^{\star}\in[4T]$ be such that
$k^{\star}=\text{sort}(S_{t^{\star}})[r^{\star}]$. By definition of the
experts, we have

$E_{t^{\star}}^{r^{\star}}(x_{t})=f_{k^{\star}}(x_{t})\quad\text{ for
}t>t^{\star},$

thus implying that $\sum_{t>t^{\star}}\left\lVert
E_{t^{\star}}^{r^{\star}}(x_{t})-y_{t}\right\rVert^{2}=\sum_{t>t^{\star}}\left\lVert
f_{k^{\star}}(x_{t})-y_{t}\right\rVert^{2}$. Therefore, it suffices to show
that

$\sum_{t\leq t^{\star}}\left\lVert
E_{t^{\star}}^{r^{\star}}(x_{t})-y_{t}\right\rVert^{2}\leq\sum_{t\leq
t^{\star}}\left\lVert f_{k^{\star}}(x_{t})-y_{t}\right\rVert^{2}+2.$

As $E_{t^{\star}}^{r^{\star}}(x_{t})=0$ for all $t\leq t^{\star}$, proving the
inequality above is equivalent to showing

$\sum_{t\leq t^{\star}}\left\lVert y_{t}\right\rVert^{2}\leq\sum_{t\leq
t^{\star}}\left\lVert f_{k^{\star}}(x_{t})-y_{t}\right\rVert^{2}+2.$

Since $\left\lVert y_{t^{\star}}\right\rVert^{2}\leq 1$, we trivially have
$\left\lVert y_{t^{\star}}\right\rVert^{2}\leq\left\lVert
f_{k^{\star}}(x_{t^{\star}})-y_{t^{\star}}\right\rVert^{2}+1$. Thus, by
expanding the squared norm, the problem reduces to showing

$\sum_{t<t^{\star}}\left(2\left\langle
f_{k^{\star}}(x_{t}),y_{t}\right\rangle-\left\lVert
f_{k^{\star}}(x_{t})\right\rVert^{2}\right)\leq 1.$

We prove the inequality above by establishing

$2\left\langle f_{k^{\star}}(x_{t}),y_{t}\right\rangle-\left\lVert
f_{k^{\star}}(x_{t})\right\rVert^{2}\leq\frac{1}{T}\quad\text{ for all
}t<t^{\star}.$

Let $x_{t}=\sum_{n=1}^{\infty}\alpha_{n}(t)e_{n}$. We have
$f_{k^{\star}}(x_{t})=\sum_{n=1}^{\infty}b_{k^{\star}}[n]\left\langle
x_{t},e_{n}\right\rangle
e_{k^{\star}}=\left(\sum_{n=1}^{\infty}b_{k^{\star}}[n]\alpha_{n}(t)\right)e_{k^{\star}}$.
Defining
$a_{k^{\star}}(t)=\left(\sum_{n=1}^{\infty}b_{k^{\star}}[n]\alpha_{n}(t)\right)$,
we can write

$f_{k^{\star}}(x_{t})=a_{k^{\star}}(t)e_{k^{\star}}\quad\text{ and
}\quad\left\lVert f_{k^{\star}}(x_{t})\right\rVert=|a_{k^{\star}}(t)|.$

So, it suffices to show that
$2\,a_{k^{\star}}(t)\,c_{k^{\star}}(t)-|a_{k^{\star}}(t)|^{2}\leq\frac{1}{T}\text{
for all }t<t^{\star}.$ To prove this inequality, we consider the following two
cases:

  * (I)

Suppose $|a_{k^{\star}}(t)|>2|c_{k^{\star}}(t)|$. Then,
$2\,a_{k^{\star}}(t)\,c_{k^{\star}}(t)-|a_{k^{\star}}(t)|^{2}<|a_{k^{\star}}(t)|^{2}-|a_{k^{\star}}(t)|^{2}=0$.

  * (II)

Suppose $|a_{k^{\star}}(t)|\leq 2|c_{k^{\star}}(t)|$. Then,
$2\,a_{k^{\star}}(t)\,c_{k^{\star}}(t)-|a_{k^{\star}}(t)|^{2}\leq
4\,|c_{k^{\star}}(t)|^{2}<4\,\left(\frac{1}{2\sqrt{T}}\right)^{2}=\frac{1}{T}$
because $k^{\star}\notin S_{t}$ for all $t<t^{\star}$.

In either case,
$2\,a_{k^{\star}}(t)\,c_{k^{\star}}(t)-|a_{k^{\star}}(t)|^{2}\leq\frac{1}{T}\quad\text{for
all }t<t^{\star}$.

Finally, suppose that such a $t^{\star}$ does not exist. Then, our analysis
for the case $t\leq t^{\star}$ above shows that the expert $E_{T}^{1}$ that
predicts $E_{T}^{1}(x_{t})=0$ for all $t\leq T$ satisfies
$\sum_{t=1}^{T}\left\lVert
E_{T}^{1}(x_{t})-y_{t}\right\rVert^{2}\leq\sum_{t=1}^{T}\left\lVert
f_{k^{\star}}(x_{t})-y_{t}\right\rVert^{2}+2.$ ∎

###  5.1  Agnostic PAC Learnability without Batch Uniform Convergence

Although we state Theorem 8 in the online setting, an analogous result also
holds in the agnostic PAC setting. To establish the agnostic PAC analog of
Theorem 8, consider $f_{k}$ defined in (2) and define a class
$\mathcal{F}=\\{f_{k}\mid k\in\mathbb{N}\\}\cup\\{f_{0}\\}$ where $f_{0}=0$.
This is the same class considered in the proof of Theorem 8. Recall that in
our proof of Theorem 8 (i), we choose a sequence of labeled examples
$\\{e_{t},0\\}_{t=1}^{T}$ that is independent of the sequence of Rademacher
random variables $\\{\sigma_{t}\\}_{t=1}^{T}$. Thus, our proof shows that the
i.i.d. version of the Rademacher complexity of $\mathcal{F}$, where the
labeled samples are independent of Rademacher variables, is also lower bounded
by $\frac{T}{2}$. This implies that the class $\mathcal{F}$ does not satisfy
the uniform law of large numbers in the i.i.d. setting. However, using the
standard online-to-batch conversion technique, we can convert our online
learner for $\mathcal{F}$ to an agnostic PAC learner for $\mathcal{F}$ (Cesa-
Bianchi et al., 2004). Therefore, a result analogous to Theorem 3 holds in the
PAC setting as well. This shows a separation between uniform convergence and
PAC learnability of a (sub)-class of linear operators.

##  6 Discussion and Open Questions

In this work, we study the online learnability of linear operators between two
infinite-dimensional Hilbert spaces. In Theorems 1 and 4, we showed that

$\Omega(T^{1-\frac{1}{p}-\varepsilon})\leq\inf_{\mathcal{A}}\,R_{\mathcal{A}}(T,\mathcal{F}_{p})\leq
O(T^{\,\max\\{\frac{1}{2},1-\frac{1}{p}\\}}),$

for every $\varepsilon>0$ and $p\in[1,\infty)$, where
$\mathcal{F}_{p}:=\\{f\in S_{p}(\mathcal{V},\mathcal{W})\,:\,\left\lVert
f\right\rVert_{p}\leq 1\\}$. Note that the lower bound and upper bound are
essentially matching for $p\geq 2$. However, for $p\in[1,2)$, the upperbound
saturates at $\sqrt{T}$, while the lower bound gets progressively worse as $p$
decreases. Given this gap, we leave it open to resolve the following question.

What is the optimal regret of learning $\mathcal{F}_{p}$ for $p\in[1,2)$?

We conjecture that our upperbound in Theorem 1 is loose for $p\in[1,2)$, and
one can obtain faster rates using some adaptation of the seminal Vovk-Azoury-
Warmuth forecaster (Vovk, 2001; Azoury and Warmuth, 2001).

Section 5 shows a separation between online uniform convergence and online
learnability for linear operator learning. The separation is exhibited by a
class that lies in $S_{1}(\mathcal{V},\mathcal{W})\subset
S_{\infty}(\mathcal{V},\mathcal{W})$, but is not a uniformly bounded subset.
We know that there is no separation between online learnability and online
uniform convergence for any subset of $S_{p}(\mathcal{V},\mathcal{W})$ with
uniformly bounded $p$-Schatten norm for $p\in[1,\infty)$. However, it is
unknown whether this is also true for $S_{\infty}(\mathcal{V},\mathcal{W})$.
This raises the following natural question.

Is online uniform convergence and online learnability equivalent for every
$\mathcal{F}\subseteq\\{f\in
S_{\infty}(\mathcal{V},\mathcal{W})\mid\left\lVert f\right\rVert_{\infty}\leq
1\\}$?

In this work, we studied the learnability of uniformly bounded linear
operators between two infinite-dimensional Hilbert spaces. For a given class,
we show that a uniform bound on the $p$-Schatten norm for any $p\in[1,\infty)$
is sufficient for online learnability. However, the example in Theorem 8 shows
that uniform upper bounds on the $p$-Schatten norm for any $p\in[1,\infty]$ is
not necessary for online learnability. It is an interesting future direction
to fully characterize the landscape of learnability for bounded linear
operators. In addition, it is also of interest to extend these results to
nonlinear operators.

## Acknowledgements

We acknowledge the assistance of Judy McDonald in locating a misdelivered
package containing (Shalev-Shwartz and Ben-David, 2014). Without the benefit
of ideas in (Shalev-Shwartz and Ben-David, 2014), this paper would have never
been written. VR acknowledges the support of the NSF Graduate Research
Fellowship.

## References

  * Abernethy et al. [2009] Jacob Abernethy, Francis Bach, Theodoros Evgeniou, and Jean-Philippe Vert.  A new approach to collaborative filtering: Operator estimation with spectral regularization.  _Journal of Machine Learning Research_ , 10(3), 2009.
  * Azoury and Warmuth [2001] Katy S Azoury and Manfred K Warmuth.  Relative loss bounds for on-line density estimation with the exponential family of distributions.  _Machine learning_ , 43:211–246, 2001.
  * Bhattacharya et al. [2021] Kaushik Bhattacharya, Bamdad Hosseini, Nikola B Kovachki, and Andrew M Stuart.  Model reduction and neural networks for parametric pdes.  _The SMAI journal of computational mathematics_ , 7:121–157, 2021.
  * Brunton et al. [2016] Steven L Brunton, Joshua L Proctor, and J Nathan Kutz.  Discovering governing equations from data by sparse identification of nonlinear dynamical systems.  _Proceedings of the national academy of sciences_ , 113(15):3932–3937, 2016.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Cesa-Bianchi et al. [2004] Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  On the generalization ability of on-line learning algorithms.  _IEEE Transactions on Information Theory_ , 50(9):2050–2057, 2004.
  * Conway [1990] John B Conway.  A course in functional analysis (1990).  _Graduate Texts in Mathematics_ , 1990.
  * Daniely et al. [2011] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  In Sham M. Kakade and Ulrike von Luxburg, editors, _Proceedings of the 24th Annual Conference on Learning Theory_ , volume 19 of _Proceedings of Machine Learning Research_ , pages 207–232, Budapest, Hungary, 09–11 Jun 2011. PMLR.
  * de Hoop et al. [2023] Maarten V de Hoop, Nikola B Kovachki, Nicholas H Nelsen, and Andrew M Stuart.  Convergence rates for learning linear operators from noisy data.  _SIAM/ASA Journal on Uncertainty Quantification_ , 11(2):480–513, 2023.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Ferraty [2006] Frédéric Ferraty.  _Nonparametric functional data analysis_.  Springer, 2006.
  * Hanneke et al. [2023] Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari.  Multiclass online learning and uniform convergence.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 5682–5696. PMLR, 2023.
  * Kirsch [2011] Andreas Kirsch.  _An introduction to the mathematical theory of inverse problems_ , volume 120.  Springer, 2011.
  * Klus et al. [2020] Stefan Klus, Feliks Nüske, Sebastian Peitz, Jan-Hendrik Niemann, Cecilia Clementi, and Christof Schütte.  Data-driven approximation of the koopman generator: Model reduction, system identification, and control.  _Physica D: Nonlinear Phenomena_ , 406:132416, 2020.
  * Kovachki et al. [2021] Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar.  Neural operator: Learning maps between function spaces.  _arXiv preprint arXiv:2108.08481_ , 2021.
  * Lanthaler [2023] Samuel Lanthaler.  Operator learning with pca-net: upper and lower complexity bounds.  _arXiv preprint arXiv:2303.16317_ , 2023.
  * Li et al. [2020] Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar.  Fourier neural operator for parametric partial differential equations.  _arXiv preprint arXiv:2010.08895_ , 2020.
  * Lin et al. [2021] Chensen Lin, Zhen Li, Lu Lu, Shengze Cai, Martin Maxey, and George Em Karniadakis.  Operator learning for predicting multiscale bubble growth dynamics.  _The Journal of Chemical Physics_ , 154(10), 2021.
  * Mollenhauer et al. [2022] Mattes Mollenhauer, Nicole Mücke, and TJ Sullivan.  Learning linear operators: Infinite-dimensional regression as a well-behaved non-compact inverse problem.  _arXiv preprint arXiv:2211.08875_ , 2022.
  * Montasser et al. [2019] Omar Montasser, Steve Hanneke, and Nathan Srebro.  Vc classes are adversarially robustly learnable, but only improperly.  In _Conference on Learning Theory_ , pages 2512–2530. PMLR, 2019\.
  * Natarajan [1989] Balaubramaniam Kausik Natarajan.  _Some results on learning_.  Carnegie Mellon University, the Robotics Institute, 1989.
  * Nelsen and Stuart [2021] Nicholas H Nelsen and Andrew M Stuart.  The random feature model for input-output maps between banach spaces.  _SIAM Journal on Scientific Computing_ , 43(5):A3212–A3243, 2021.
  * Neto and da Silva Neto [2012] Francisco Duarte Moura Neto and Antônio José da Silva Neto.  _An introduction to inverse problems with applications_.  Springer Science & Business Media, 2012.
  * Rakhlin and Sridharan [2014] Alexander Rakhlin and Karthik Sridharan.  Online non-parametric regression.  In _Conference on Learning Theory_ , pages 1232–1264. PMLR, 2014\.
  * Rakhlin et al. [2015a] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning via sequential complexities.  _J. Mach. Learn. Res._ , 16(1):155–186, 2015a.
  * Rakhlin et al. [2015b] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  _Probability theory and related fields_ , 161:111–153, 2015b.
  * Rakhlin et al. [2012] Sasha Rakhlin, Ohad Shamir, and Karthik Sridharan.  Relax and randomize: From value to algorithms.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Reed and Simon [1975] Michael Reed and Barry Simon.  _II: Fourier analysis, self-adjointness_ , volume 2.  Elsevier, 1975.
  * Santhanam et al. [2017] Venkataraman Santhanam, Vlad I Morariu, and Larry S Davis.  Generalized deep image to image regression.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5609–5619, 2017.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, USA, 2014.
  * Tabaghi et al. [2019] Puoya Tabaghi, Maarten de Hoop, and Ivan Dokmanić.  Learning schatten–von neumann operators.  _arXiv preprint arXiv:1901.10076_ , 2019.
  * Tarantola [2005] Albert Tarantola.  _Inverse problem theory and methods for model parameter estimation_.  SIAM, 2005.
  * Uhlmann [2003] Gunther Uhlmann.  _Inside out: inverse problems and applications_ , volume 47.  Cambridge University Press, 2003.
  * Vovk [2001] Volodya Vovk.  Competitive on-line statistics.  _International Statistical Review_ , 69(2):213–248, 2001.
  * Wang et al. [2016] Jane-Ling Wang, Jeng-Min Chiou, and Hans-Georg Müller.  Functional data analysis.  _Annual Review of Statistics and its application_ , 3:257–295, 2016.
  * Weidmann [2012] Joachim Weidmann.  _Linear operators in Hilbert spaces_ , volume 68.  Springer Science & Business Media, 2012.

##  Appendix A Upperbound Proofs for Online Setting

Our proof of Theorem 1 also relies on the following technical Lemma.

######  Lemma 9.

Let $v\in\mathcal{V}$, $w\in\mathcal{W}$, and
$f\in\mathcal{L}(\mathcal{V},\mathcal{W})$. Then, we have $\left\langle
f(v),w\right\rangle=\operatorname{tr}(f\circ(v\otimes w))$.

###### Proof.

(of Lemma 9) Let $\\{\psi_{n}\\}_{n=1}^{\infty}$ be an orthonormal basis of
$\mathcal{W}$ and $w=\sum_{n=1}^{\infty}\alpha_{n}\psi_{n}$ for an $\ell_{2}$
summable sequence $\\{\alpha_{n}\\}_{n\in\mathbb{N}}$. Then, by definition of
the trace operator, we have

$\operatorname{tr}(f\circ(v\otimes w))=\sum_{n=1}^{\infty}\left\langle
f\circ(v\otimes
w)(\psi_{n}),\psi_{n}\right\rangle=\sum_{n=1}^{\infty}\left\langle\alpha_{n}\,f(v),\psi_{n}\right\rangle=\left\langle
f(v),\sum_{n=1}^{\infty}\alpha_{n}\psi_{n}\right\rangle=\left\langle
f(v),w\right\rangle,$

which completes our proof. ∎

###  A.1 Proof of Lemma 2

Let $F=\sum_{t=1}^{T}\sigma_{t}\,v_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})$. Since

$\text{rank}\left(F\right)\leq\sum_{t=1}^{T}\text{rank}\left(\sigma_{t}\,v_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right)\leq T,$

$F$ can have at most $T$ non-zero singular values. Let $\\{s_{t}\\}_{t=1}^{T}$
be the singular values of the operator $F$, possibly with multiplicities.
Then, for $q\in[1,2)$, we have

$\begin{split}\left\lVert
F\right\rVert_{q}=\left(\sum_{t=1}^{T}s_{t}^{q}\right)^{\frac{1}{q}}\leq\left(\left(\sum_{t=1}^{T}(s_{t}^{q})^{\frac{2}{q}}\right)^{\frac{q}{2}}\,\left(\sum_{t=1}^{T}1^{\frac{2}{2-q}}\right)^{\frac{2-q}{2}}\right)^{\frac{1}{q}}=\left(\sum_{t=1}^{T}s_{t}^{2}\right)^{\frac{1}{2}}\,T^{\frac{1}{q}-\frac{1}{2}}=\left\lVert
F\right\rVert_{2}\,T^{\frac{1}{q}-\frac{1}{2}},\end{split}$

where the inequality is due to Hölder. As for $q\geq 2$, we trivially have
$\left\lVert F\right\rVert_{q}\leq\left\lVert F\right\rVert_{2}$. In either
case, we obtain

$\left\lVert
F\right\rVert_{q}\leq\max\left\\{T^{\frac{1}{q}-\frac{1}{2}},1\right\\}\,\,\left\lVert
F\right\rVert_{2}.$

Hence, to prove Lemma 2, it suffices to show that

$\operatorname{\mathbb{E}}[\,\left\lVert F\right\rVert_{2}]\leq
c_{1}\,c_{2}\,T^{\frac{1}{2}}.$

Recall that by definition of the $2$-Schatten norm, we have $\left\lVert
F\right\rVert_{2}=\sqrt{\operatorname{tr}\left(F^{\star}F\right)}$. Using
linearity of trace and Jensen’s inequality gives
$\operatorname{\mathbb{E}}\left[\sqrt{\operatorname{tr}\left(F^{\star}F\right)}\right]\leq\sqrt{\operatorname{tr}\left(\operatorname{\mathbb{E}}\left[F^{\star}F\right]\right)}$.
Then,

$\begin{split}\operatorname{\mathbb{E}}\left[F^{\star}F\right]&=\operatorname{\mathbb{E}}\left[\left(\sum_{t=1}^{T}\sigma_{t}\,w_{t}(\sigma_{<t})\otimes
v_{t}(\sigma_{<t})\right)\left(\sum_{t=1}^{T}\sigma_{t}\,v_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right)\right]\\\
&=\operatorname{\mathbb{E}}\left[\sum_{t,r}\sigma_{t}\,\sigma_{r}\left\langle
v_{t}(\sigma_{<t}),v_{r}(\sigma_{<r})\right\rangle w_{t}(\sigma_{<t})\otimes
w_{r}(\sigma_{<r})\right]\\\
&=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert
v_{t}(\sigma_{<t})\right\rVert^{2}w_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right]+\operatorname{\mathbb{E}}\left[\sum_{t\neq
r}\sigma_{t}\sigma_{r}\left\langle
v_{t}(\sigma_{<t}),v_{r}(\sigma_{<r})\right\rangle w_{t}(\sigma_{<t})\otimes
w_{r}(\sigma_{<r})\right]\\\
&=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert
v_{t}(\sigma_{<t})\right\rVert^{2}w_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right].\end{split}$

To see why the second term above is $0$, consider the case $t<r$. We have

$\begin{split}\operatorname{\mathbb{E}}\left[\sigma_{t}\sigma_{r}\left\langle
v_{t}(\sigma_{<t}),v_{r}(\sigma_{<r})\right\rangle w_{t}(\sigma_{<t})\otimes
w_{r}(\sigma_{<r})\right]&=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{E}}\left[\sigma_{t}\sigma_{r}\left\langle
v_{t}(\sigma_{<t}),v_{r}(\sigma_{<r})\right\rangle w_{t}(\sigma_{<t})\otimes
w_{r}(\sigma_{<r})\mid\sigma_{<r}\right]\right]\\\
&=\operatorname{\mathbb{E}}\left[\sigma_{t}\left\langle
v_{t}(\sigma_{<t}),v_{r}(\sigma_{<r})\right\rangle w_{t}(\sigma_{<t})\otimes
w_{r}(\sigma_{<r})\,\operatorname{\mathbb{E}}\left[\sigma_{r}\mid\sigma_{<r}\right]\right]\\\
&=0.\end{split}$

The last equality follows because $\sigma_{r}$ is independent of $\sigma_{<r}$
and thus
$\operatorname{\mathbb{E}}\left[\sigma_{r}\mid\sigma_{<r}\right]=\operatorname{\mathbb{E}}[\sigma_{r}]=0$.
The case where $t>r$ is symmetric. Putting everything together, we have

$\begin{split}\operatorname{tr}\left(\operatorname{\mathbb{E}}[F^{\star}F]\right)&=\operatorname{tr}\left(\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert
v_{t}(\sigma_{<t})\right\rVert^{2}w_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right]\right)\\\
&=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert
v_{t}(\sigma_{<t})\right\rVert^{2}\operatorname{tr}\left(w_{t}(\sigma_{<t})\otimes
w_{t}(\sigma_{<t})\right)\right]\\\
&=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\left\lVert
v_{t}(\sigma_{<t})\right\rVert^{2}\left\lVert
w_{t}(\sigma_{<t})\right\rVert^{2}\right]\\\
&\leq\sum_{t=1}^{T}c_{1}^{2}c_{2}^{2}=(c_{1}c_{2})^{2}\,T,\end{split}$

which implies that $\operatorname{\mathbb{E}}[\,\left\lVert
F\right\rVert_{2}]\leq\sqrt{\operatorname{tr}\left(\operatorname{\mathbb{E}}\left[F^{\star}F\right]\right)}\leq\sqrt{(c_{1}c_{2})^{2}T}=c_{1}\,c_{2}\,T^{\frac{1}{2}}$.
This completes our proof.

###  A.2 Proof of Theorem 1

Define the normalized loss class $\\{(u,v)\mapsto\frac{1}{4c^{2}}\left\lVert
f(u)-v\right\rVert^{2}\,:f\in\mathcal{F}_{p}\\}$ such that every function in
this class maps to $[0,1]$. Applying [Rakhlin et al., 2015b, Theorem 2] to
this normalized loss class, we obtain that the expected regret of
$\mathcal{A}$ is $\leq 8c^{2}\,\text{Rad}_{T}(\overline{\mathcal{F}}_{p})$,
where $\overline{\mathcal{F}}_{p}=\\{\frac{1}{4c^{2}}f\mid
f\in\mathcal{F}_{p}\\}$ is the normalized operator class. Since
$\text{Rad}_{T}(\overline{\mathcal{F}}_{p})=\frac{1}{4c^{2}}\,\text{Rad}_{T}(\mathcal{F}_{p})$,
the expected regret of $\mathcal{A}$ is $\leq
2\,\text{Rad}_{T}(\mathcal{F}_{p})$. This completes the proof of the first
inequality. We now focus on proving the second inequality here. By definition,
we have

$\begin{split}&\text{Rad}_{T}(\mathcal{F}_{p})=\sup_{x,y}\,\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}\sigma_{t}\left\lVert
f(x_{t}(\sigma_{<t}))-y_{t}(\sigma_{<t})\right\rVert^{2}\right]\\\
&\leq\sup_{x,y}\left(\,\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}\sigma_{t}\left\lVert
f(x_{t}(\sigma_{<t}))\right\rVert^{2}\right]+2\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}-\sigma_{t}\left\langle
f(x_{t}(\sigma_{<t})),y_{t}(\sigma_{<t})\right\rangle\right]\right.\\\
&\quad\left.+\operatorname{\mathbb{E}}\left[\,\sum_{t=1}^{T}\sigma_{t}\left\lVert
y_{t}(\sigma_{<t}))\right\rVert^{2}\right]\right)\\\
&=\sup_{x,y}\left(\,\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}\sigma_{t}\left\lVert
f(x_{t}(\sigma_{<t}))\right\rVert^{2}\right]+2\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}\sigma_{t}\left\langle
f(x_{t}(\sigma_{<t})),y_{t}(\sigma_{<t})\right\rangle\right]\right).\end{split}$

To handle the second term above, recall that Lemma 9 implies $\left\langle
f(x_{t}(\sigma_{<t})),y_{t}(\sigma_{<t})\right\rangle=\operatorname{tr}(f\circ\,(x_{t}(\sigma_{<t})\otimes
y_{t}(\sigma_{<t})))$. Using the linearity of the trace operator, we obtain

$\begin{split}\sum_{t=1}^{T}\sigma_{t}\left\langle
f(x_{t}(\sigma_{<t})),y_{t}(\sigma_{<t})\right\rangle=\operatorname{tr}\left(f\circ\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
y_{t}(\sigma_{<t})\right)\leq\left\lVert
f\right\rVert_{p}\,\,\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
y_{t}(\sigma_{<t})\right\rVert_{q},\end{split}$

where $q=1-\frac{1}{p}$ is the Hölder conjugate of $p$ [Reed and Simon, 1975,
Page 41]. This implies the bound

$\begin{split}\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}\sigma_{t}\left\langle
f(x_{t}(\sigma_{<t})),y_{t}(\sigma_{<t})\right\rangle\right]&\leq\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\left\lVert
f\right\rVert_{p}\,\,\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
y_{t}(\sigma_{<t})\right\rVert_{q}\right]\\\ &\leq
c\,\operatorname{\mathbb{E}}\left[\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
y_{t}(\sigma_{<t})\right\rVert_{q}\right],\end{split}$

where the last inequality follows from the definition of $\mathcal{F}_{p}$.

To handle the first term in the bound of $\text{Rad}_{T}(\mathcal{F}_{p})$
above, note that

$\left\lVert f(x_{t}(\sigma_{<t}))\right\rVert^{2}=\left\langle
f(x_{t}(\sigma_{<t})),f(x_{t}(\sigma_{<t}))\right\rangle=\left\langle
f^{\star}f(x_{t}(\sigma_{<t})),x_{t}(\sigma_{<t})\right\rangle=\operatorname{tr}(f^{\star}f\circ(x_{t}(\sigma_{<t})\otimes
x_{t}(\sigma_{<t}))),$

where the final equality follows from Lemma 9. Using linearity of trace, and
the generalized Hölder’s inequality for Schatten norms [Reed and Simon, 1975,
Page 41], we obtain

$\begin{split}\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\sum_{t=1}^{T}\sigma_{t}\left\lVert
f(x_{t}(\sigma_{<t}))\right\rVert^{2}\right]&\leq\operatorname{\mathbb{E}}\left[\sup_{f\in\mathcal{F}_{p}}\,\left\lVert
f^{\star}f\right\rVert_{p}\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
x_{t}(\sigma_{<t})\right\rVert_{q}\right]\\\ &\leq
c^{2}\operatorname{\mathbb{E}}\left[\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
x_{t}(\sigma_{<t})\right\rVert_{q}\right],\end{split}$

where the last inequality uses the fact that $\left\lVert
f^{\star}f\right\rVert_{p}\leq\left\lVert f\right\rVert_{p}^{2}$. Combining
everything, we obtain

$\begin{split}\text{Rad}_{T}(\mathcal{F}_{p})\leq
c^{2}\operatorname{\mathbb{E}}\left[\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
x_{t}(\sigma_{<t})\right\rVert_{q}\right]+2c\,\operatorname{\mathbb{E}}\left[\left\lVert\sum_{t=1}^{T}\sigma_{t}\,x_{t}(\sigma_{<t})\otimes
y_{t}(\sigma_{<t})\right\rVert_{q}\right]\leq
3c^{2}\,T^{\max\left\\{\frac{1}{2},\frac{1}{q}\right\\}},\end{split}$

where the final inequality follows from using Lemma 2 twice. Recalling that
$\frac{1}{q}=1-\frac{1}{p}$ completes our proof of second inequality.

##  Appendix B Lower Bound Proofs for Online Setting

###  B.1 Proof of Theorem 4

Let $\zeta$ denote the Riemann-Zeta function,
$\zeta(r)=\sum_{n=1}^{\infty}\frac{1}{n^{r}}$ for $r>1$. Then, pick a sequence
$\gamma=\\{\gamma_{n}\\}_{n\in\mathbb{N}}$ such that

$\gamma_{n}=\frac{1}{\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,n^{\frac{1}{p}+\varepsilon}},$

for some $0<\varepsilon<\frac{1}{p}$. Clearly, $0\leq\gamma_{n}\leq 1$. Define
$\mathcal{G}^{\gamma}$ according to the Equation (1), and consider an operator
$g^{\gamma}\in\mathcal{G}^{\gamma}$. There must exist a $n\in\mathbb{N}$ and
$\sigma\in\\{-1,1\\}^{n}$ such that
$g^{\gamma}=\sum_{i=1}^{n}\sigma_{i}\,\gamma_{i}\,\psi_{i}\otimes e_{i}.$ Note
that this is a singular value decomposition of $g^{\gamma}$ with singular
values $\\{\sigma_{i}\gamma_{i}\\}_{i=1}^{n}$. Since $f^{\gamma}$ is a finite-
rank operator, it must be compact. Thus, we have

$\left\lVert
g^{\gamma}\right\rVert_{p}\leq\left(\sum_{i=1}^{n}|\sigma_{i}\,\gamma_{i}|^{p}\right)^{\frac{1}{p}}=\frac{1}{\zeta^{\frac{1}{p}}(1+\varepsilon
p)}\,\left(\sum_{i=1}^{n}\frac{1}{n^{1+\varepsilon
p}}\right)^{\frac{1}{p}}\leq\frac{1}{\zeta^{\frac{1}{p}}(1+\varepsilon
p)}\,\left(\sum_{i=1}^{\infty}\frac{1}{n^{1+\varepsilon
p}}\right)^{\frac{1}{p}}=1.$

Therefore, $g^{\gamma}\in\mathcal{F}_{p}$. As $g^{\gamma}$ is arbitrary, we
must have $\mathcal{G}^{\gamma}\subseteq\mathcal{F}_{p}$. Since any lower
bound for learning $\mathcal{G}^{\gamma}$ is also a lower bound for learning
$\mathcal{F}_{p}$, Lemma 3 implies that the regret of any algorithm
$\mathcal{A}$ for $\mathcal{F}_{p}$ is $\geq\sum_{t=1}^{T}\gamma_{t}$, which
is

$\begin{split}\frac{1}{\zeta^{\frac{1}{p}}(1+\varepsilon\,p)}\,\sum_{t=1}^{T}\frac{1}{t^{\frac{1}{p}+\varepsilon}}\geq\frac{1}{\zeta^{\frac{1}{p}}(1+\varepsilon\,p)}\int_{1}^{T}\frac{1}{t^{\frac{1}{p}+\varepsilon}}\,dt&=\frac{1}{\zeta^{\frac{1}{p}}(1+\varepsilon\,p)}\,\frac{T^{1-\frac{1}{p}-\varepsilon}}{1-\frac{1}{p}-\varepsilon}\,=\Omega(T^{1-\frac{1}{p}-\varepsilon}).\end{split}$

This completes the proof.

###  B.2 Proof of Theorem 5

Define $\mathcal{G}^{\gamma}$ according to Equation (1) for a sequence
$\gamma$ such that $\gamma_{n}=1$ for all $n\in\mathbb{N}$. Consider an
operator $g^{\gamma}\in\mathcal{G}^{\gamma}$. There must exist a
$n\in\mathbb{N}$ and $\sigma\in\\{-1,1\\}^{n}$ such that
$g^{\gamma}=\sum_{i=1}^{n}\sigma_{i}\,\psi_{i}\otimes e_{i}.$ Since this is a
singular value decomposition with singular values
$\\{\sigma_{i}\\}_{i=1}^{n}$, we must have $\left\lVert
g^{\gamma}\right\rVert_{\infty}=\sup_{i\geq 1}|\sigma_{i}|=1$. Therefore,
$g^{\gamma}\in\mathcal{F}_{\infty}$. As $g^{\gamma}$ is arbitrary, we must
have $\mathcal{G}^{\gamma}\subseteq\mathcal{F}_{\infty}$. Since any lower
bound for learning $\mathcal{G}^{\gamma}$ is also the lower bound for learning
$\mathcal{F}_{\infty}$, Lemma 3 implies that the regret of any algorithm
$\mathcal{A}$ for $\mathcal{F}_{\infty}$ is
$\geq\sum_{t=1}^{T}\gamma_{t}=\sum_{t=1}^{T}1=T$. This completes the proof.

##  Appendix C Proofs for Agnostic PAC Setting

We first provide the formal definition of agnostic PAC learnability here.

######  Definition 3 (Agnostic PAC Learnability [Shalev-Shwartz and Ben-David,
2014]).

A linear operator class
$\mathcal{F}\subseteq\mathcal{L}(\mathcal{V},\mathcal{W})$ is agnostic
learnable , if there exists a function $\mathcal{M}:(0,1)^{2}\to\mathbb{N}$
and a learning algorithm
$\mathcal{P}:(\mathcal{X}\times\mathcal{Y})^{\star}\to\mathcal{Y}^{\mathcal{X}}$
with the following property: for every $\epsilon,\delta\in(0,1)$ and for every
distribution $\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$, running
algorithm $\mathcal{P}$ on $n\geq\mathcal{M}(\epsilon,\delta)$ i.i.d. samples
from $\mathcal{D}$ outputs a predictor $\mathcal{P}_{S}$ such that with
probability at least $1-\delta$ over $S\sim\mathcal{D}^{n}$,

$\operatorname{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\left\lVert\mathcal{P}_{S}(x)-y\right\rVert^{2}\right]\leq\inf_{f\in\mathcal{F}}\operatorname{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[\left\lVert
f(x)-y\right\rVert^{2}]+\epsilon.$

Next, following our roadmap of the online model, we establish the lower bound
for $\mathcal{G}^{\gamma}$, which subsequently implies the lower bounds for
$S_{p}(\mathcal{V},\mathcal{W})$ for various choices of $\gamma$ as a function
of $p\in[1,\infty)$.

######  Lemma 10 (Agnostic PAC Lower Bounds of $\mathcal{G}^{\gamma}$).

Let $\mathcal{V}$ and $\mathcal{W}$ be Hilbert spaces with orthonormal basis
$\\{e_{i}\\}_{i\in\mathbb{N}}$ and $\\{\psi_{i}\\}_{i\in\mathbb{N}}$
respectively. Let $\mathcal{X}=\\{v\in\mathcal{V}\mid\left\lVert
v\right\rVert\leq 1\\}$ denote the instance space and
$\mathcal{Y}=\\{w\in\mathcal{W}\mid\left\lVert w\right\rVert\leq 1\\}$ denote
the target space. For a sequence $\gamma=\\{\gamma_{n}\\}_{n\in\mathbb{N}}$
such that $\gamma_{n}\in[0,1]$, define the function class
$\mathcal{G}^{\gamma}$ as in Equation (1). Fix $m,n\in\mathbb{N}$ such that
$m\geq 2$. Then, for any agnostic PAC learning algorithm $\mathcal{P}$, there
exists a distribution $\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$ such
that with probability at least $\frac{1}{8}$, the excess risk of $\mathcal{P}$
trained on $n$ i.i.d. samples from the source distribution $\mathcal{D}$ is at
least

$\frac{1}{2mn}\sum_{i=1}^{mn}\gamma_{i}-\frac{1}{2m}.$

###### Proof.

Fix $n,m\in\mathbb{N}$. Let $\mathcal{D}$ be an arbitrary joint distribution
on $\mathcal{X}\times\mathcal{Y}$, and let $U$ denote the uniform distribution
on $\\{e_{1},\ldots,e_{mn}\\}$. For each $\sigma\in\\{-1,1\\}^{mn}$, define
$f_{\sigma}=\sum_{i=1}^{mn}\sigma_{i}\,\psi_{i}\otimes e_{i}$. The expected
minimax excess risk of any algorithm $\mathcal{P}$ trained on $n$ i.i.d.
samples from the source distribution $\mathcal{D}$ is

$\begin{split}&\inf_{\mathcal{P}}\sup_{\mathcal{D}}\operatorname{\mathbb{E}}_{S\sim\mathcal{D}^{n}}\left[\operatorname{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\left\lVert\mathcal{P}_{S}(x)-y\right\rVert^{2}\right]-\inf_{g\in\mathcal{G}^{\gamma}}\operatorname{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\left\lVert
g(x)-y\right\rVert^{2}\right]\right]\\\
&\geq\inf_{\mathcal{P}}\operatorname{\mathbb{E}}_{\sigma\sim\\{\pm
1\\}^{mn}}\left[\operatorname{\mathbb{E}}_{S\sim(U\times
f_{\sigma})^{n}}\left[\operatorname{\mathbb{E}}_{x\sim
U}\left[\left\lVert\mathcal{P}_{S}(x)-f_{\sigma}(x)\right\rVert^{2}\right]-\inf_{g\in\mathcal{G}^{\gamma}}\operatorname{\mathbb{E}}_{x\sim
U}\left[\left\lVert
g(x)-f_{\sigma}(x)\right\rVert^{2}\right]\right]\right]\end{split}$

where the first inequality follows upon replacing supremum over
$\mathcal{D},\sigma$ with $U$ and expectation over $\sigma$. Let $S_{x}$
denote the instances from labeled samples $S$. Let us first lower bound the
expected risk of the learner $\mathcal{P}$. Then, we will upper bound the
expected risk of the optimal function in $\mathcal{G}^{\gamma}$. Exchanging
the order of the first two expectations, the lower bound of the expected risk
of the learner $\mathcal{P}$ is

$\begin{split}&\inf_{\mathcal{P}}\operatorname{\mathbb{E}}_{S_{x}\sim
U^{n}}\left[\operatorname{\mathbb{E}}_{\sigma\sim\\{\pm
1\\}^{mn}}\left[\operatorname{\mathbb{E}}_{x\sim
U}\left[\left\lVert\mathcal{P}_{S}(x)-f_{\sigma}(x)\right\rVert^{2}\right]\right]\right]\\\
&=\inf_{\mathcal{P}}\operatorname{\mathbb{E}}_{S_{x}\sim
U^{n}}\left[\operatorname{\mathbb{E}}_{\sigma\sim\\{\pm
1\\}^{mn}}\left[\frac{1}{mn}\sum_{i=1}^{mn}\left\lVert\mathcal{P}_{S}(e_{i})-f_{\sigma}(e_{i})\right\rVert^{2}\right]\right]\\\
&\geq\inf_{\mathcal{P}}\operatorname{\mathbb{E}}_{N\sim\text{Unif}(\\{1,,\ldots,mn\\})^{n}}\left[\operatorname{\mathbb{E}}_{\sigma\sim\\{\pm
1\\}^{mn}}\left[\frac{1}{mn}\sum_{i\notin
N}\left\lVert\mathcal{P}_{S}(e_{i})-\sigma_{i}\psi_{i}\right\rVert^{2}\right]\right]\\\
&\geq\inf_{\mathcal{P}}\operatorname{\mathbb{E}}_{N\sim\text{Unif}(\\{1,,\ldots,mn\\})^{n}}\left[\frac{1}{mn}\sum_{i\notin
N}\left(\operatorname{\mathbb{E}}_{\sigma\sim\\{\pm
1\\}^{mn}}\left[\left\lVert\mathcal{P}_{S}(e_{i})-\sigma_{i}\psi_{i}\right\rVert\right]\right)^{2}\right].\end{split}$

In order to get the second to the last inequality, we reinterpret sampling $x$
uniformly from $\\{e_{1},\ldots,e_{mn}\\}$ as sampling index $i$ uniformly
from $\\{1,\ldots,mn\\}$ and drawing $e_{i}$. The final inequality follows
upon exchanging the sum and expectation and applying Jensen’s. Note that

$\begin{split}&\operatorname{\mathbb{E}}_{\sigma\sim\\{\pm
1\\}^{mn}}\left[\left\lVert\mathcal{P}_{S}(e_{i})-\sigma_{i}\psi_{i}\right\rVert\right]=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{E}}_{\sigma_{i}}\left[\left\lVert\mathcal{P}_{S}(e_{i})-\sigma_{i}\psi_{i}\right\rVert\right]\mid\\{\sigma_{j}\\}_{j\neq
i}\right]\\\
&=\operatorname{\mathbb{E}}\left[\frac{1}{2}\left(\left\lVert\mathcal{P}_{S}(e_{i})-\psi_{i}\right\rVert+\left\lVert\mathcal{P}_{S}(e_{i})+\psi_{i}\right\rVert\right)\mid\\{\sigma_{j}\\}_{j\neq
i}\right]\\\ &\geq\frac{1}{2}\left\lVert\psi_{i}+\psi_{i}\right\rVert\\\
&=1,\end{split}$

where we use the fact $\mathcal{P}_{S}$ is independent of $\sigma_{i}$ as
$i\notin N$ and reverse triangle inequality. Thus, combining everything, our
lower bound is

$\geq\inf_{\mathcal{P}}\operatorname{\mathbb{E}}_{N\sim\text{Unif}(\\{1,,\ldots,mn\\})^{n}}\left[\frac{1}{mn}\sum_{i\notin
N}1\right]=\frac{1}{mn}\operatorname{\mathbb{E}}_{N\sim\text{Unif}(\\{1,,\ldots,mn\\})^{n}}(mn-|N|)\geq\frac{mn-n}{mn}=\frac{m-1}{m},$

where we use the fact that $|N|\leq n$.

Next, we upperbound optimal expected risk amongst functions in
$\mathcal{G}^{\gamma}$. Consider
$g_{\sigma}^{\gamma}=\sum_{i=1}^{2n}\sigma_{i}\,\gamma_{i}\,\psi_{i}\otimes
e_{i}$. Note that $g_{\sigma}^{\gamma}\in\mathcal{G}^{\gamma}$. Then, we have

$\begin{split}\inf_{g\in\mathcal{G}^{\gamma}}\operatorname{\mathbb{E}}_{x\sim
U}\left[\left\lVert
g(x)-f_{\sigma}(x)\right\rVert^{2}\right]\leq\operatorname{\mathbb{E}}_{x\sim
U}\left[\left\lVert
g_{\sigma}^{\gamma}(x)-f_{\sigma}(x)\right\rVert^{2}\right]&=\frac{1}{mn}\sum_{i=1}^{mn}\left\lVert
g_{\sigma}^{\gamma}(e_{i})-f_{\sigma}(e_{i})\right\rVert^{2}\\\
&=\frac{1}{mn}\sum_{i=1}^{mn}\left\lVert\sigma_{i}\,\gamma_{i}\psi_{i}-\sigma_{i}\psi_{i}\right\rVert^{2}\\\
&=\frac{1}{mn}\sum_{i=1}^{mn}(\gamma_{i}-1)^{2}\\\
&\leq\frac{-1}{mn}\sum_{i=1}^{mn}\gamma_{i}+1,\end{split}$

using the fact that $\gamma_{i}^{2}\leq\gamma_{i}$. Thus, putting everything
together, the minimax expected excess risk is at least

$\frac{m-1}{m}+\frac{1}{mn}\sum_{i=1}^{mn}\gamma_{i}-1=\frac{1}{mn}\sum_{i=1}^{mn}\gamma_{i}-\frac{1}{m}.$

Using standard arguments [Shalev-Shwartz and Ben-David, 2014, Lemma B.1], one
can show that the excess risk is at least

$\frac{1}{2}\left(\frac{1}{mn}\sum_{i=1}^{mn}\gamma_{i}-\frac{1}{m}\right)$

with probability at least $\frac{1}{8}$. This completes our proof. ∎

###  C.1 Proof of Theorem 6

Picking
$\gamma_{n}=\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,n^{\frac{1}{p}+\varepsilon}\right)^{-1}$,
we can show that $\mathcal{G}^{\gamma}\subseteq\mathcal{F}_{p}:=\\{f\in
S_{p}(\mathcal{V},\mathcal{W})\mid\left\lVert f\right\rVert_{p}\leq 1\\}$.
Thus, using Lemma 10, for any PAC learning algorithm $\mathcal{P}$ for
$\mathcal{F}_{p}$, there exists a distribution $\mathcal{D}$ on
$\mathcal{X}\times\mathcal{Y}$ such that with probability at least
$\frac{1}{8}$, the excess risk of $\mathcal{P}$ trained on $n$ i.i.d. samples
from the source distribution $\mathcal{D}$ is

$\begin{split}\frac{1}{2mn}\sum_{i=1}^{mn}\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,i^{\frac{1}{p}+\varepsilon}\right)^{-1}-\frac{1}{2m}&\geq\frac{\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,\right)^{-1}}{2mn}\int_{1}^{mn}\frac{1}{i^{\frac{1}{p}+\varepsilon}}\,di\,-\frac{1}{2m}\\\
&=\frac{\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,\right)^{-1}}{2mn}\,\frac{(mn)^{1-\frac{1}{p}-\varepsilon}-1}{1-\frac{1}{p}-\varepsilon}-\frac{1}{2m}\\\
&\geq\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,\right)^{-1}\,\frac{(mn)^{1-\frac{1}{p}-\varepsilon}-1}{2mn}-\frac{1}{2m}\\\
&\geq\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,\right)^{-1}\,\frac{(mn)^{1-\frac{1}{p}-\varepsilon}}{4mn}-\frac{1}{2m}\\\
&=\frac{1}{2}\left(\zeta^{\frac{1}{p}}(1+\varepsilon\,p)\,\,\right)^{-1}\,\frac{(mn)^{1-\frac{1}{p}-\varepsilon}}{4mn}\end{split}$

if we choose
$m^{1-\frac{1}{p}-\varepsilon}=4\,\zeta^{\frac{1}{p}}(1+\varepsilon
p)\,n^{\frac{1}{p}+\varepsilon}$ so that first term is double of the second
term in the second to last expression above. For this choice of $m$, the lower
bound is
$\frac{1}{2m}=\Omega(n^{\frac{-1-p\varepsilon}{p-1-p\varepsilon}})=\Omega(n^{-\frac{1}{p}-\varepsilon}).$
This completes our proof.

###  C.2 Proof of Theorem 7

Picking $\gamma_{n}=1$ for all $n\in\mathbb{N}$, we showed above that
$\mathcal{G}^{\gamma}\subseteq\mathcal{F}_{\infty}:=\\{f\in
S_{\infty}(\mathcal{V},\mathcal{W})\mid\left\lVert f\right\rVert_{\infty}\leq
1\\}$. Thus, using Lemma 10, for any PAC learning algorithm $\mathcal{P}$ for
$\mathcal{F}_{\infty}$, there exists a distribution $\mathcal{D}$ on
$\mathcal{X}\times\mathcal{Y}$ such that with probability at least
$\frac{1}{8}$, the excess risk of $\mathcal{P}$ trained on $n$ i.i.d. samples
from the source distribution $\mathcal{D}$ is
$\geq\frac{1}{2}(1-\frac{1}{m})\geq\frac{1}{4}$ for all $m\geq 2$. Therefore,
the class the class $\mathcal{F}_{\infty}$ is not PAC learnable either.