# Lipschitz Interpolation: Non-parametric Convergence under Bounded Stochastic
Noise

Julien Walden Huang<EMAIL_ADDRESS>
University of Oxford Stephen Roberts<EMAIL_ADDRESS>
University of Oxford Jan-Peter Calliess<EMAIL_ADDRESS>
University of Oxford

###### Abstract

This paper examines the asymptotic convergence properties of Lipschitz
interpolation methods within the context of bounded stochastic noise. In the
first part of the paper, we establish probabilistic consistency guarantees of
the classical approach in a general setting and derive upper bounds on the
uniform convergence rates. These bounds align with well-established optimal
rates of non-parametric regression obtained in related settings and provide
new precise upper bounds on the non-parametric regression problem under
bounded noise assumptions. Practically, they can serve as a theoretical tool
for comparing Lipschitz interpolation to alternative non-parametric regression
methods, providing a condition on the behaviour of the noise at the boundary
of its support which indicates when Lipschitz interpolation should be expected
to asymptotically outperform or underperform other approaches. In the second
part, we expand upon these results to include asymptotic guarantees for online
learning of dynamics in discrete-time stochastic systems and illustrate their
utility in deriving closed-loop stability guarantees of a simple controller.
We also explore applications where the main assumption of prior knowledge of
the Lipschitz constant is removed by adopting the LACKI framework (Calliess et
al. (2020)) and deriving general asymptotic consistency.

Keywords: Non-parametrics, System Identification, Lipschitz Interpolation,
Non-linear systems, Convergence Rates, Asymptotics

##  1 Introduction

Non-parametric regression methods are a flexible class of machine learning
algorithms that often enjoy strong estimation success even when little is
known about the underlying target function or data-generating distribution.
Generally, theoretical guarantees on their convergence have been well-
researched with classical optimal convergence rates obtained in seminal work
by Stone (1982) in the case where the noise is assumed to be essentially
Gaussian; although various extensions relax this assumption, and a variety of
general consistency results can be derived (Györfi et al. (2002)). In this
paper, we will extend the literature on the non-parametric estimation problem
by considering the setting of bounded stochastic noise and a non-parametric
regression framework known as Lipschitz interpolation111Also referred to as
non-linear set membership (Milanese and Novara (2004)) or kinky inference
(Calliess et al. (2020)) (Beliakov (2006). This theoretical context is of
particular interest to the field of control where Lipschitz interpolation has
been used in various predictive control applications and bounded noise
assumptions are commonly made.

More generally, the popularity of data-driven adaptive control frameworks has
increased significantly in both industry and academia over the past two
decades. These frameworks assume that the underlying system dynamics are
partially or completely unknown and need to be identified through
computational machine learning-based approaches. Traditionally, linear
parametric regression methods have been extensively studied and utilized for
this purpose (Ljung (2010)). However, with recent advancements, the research
focus has expanded to encompass non-linear approaches, reflecting the growing
interest in more expressive modelling techniques (Schoukens and Ljung (2019)).
Non-linear non-parametric regression methods such as the Nadaraya-Watson
estimator (Nadaraya (1964)), Polynomial Spline Interpolation (Stone (1994)),
general Lipschitz Interpolation or Gaussian process regression (Williams and
Rasmussen (2006)) which offer flexible predictors capable of modelling complex
dynamics with minimal hyperparameter tuning have emerged as natural tools in
this context. In particular, Gaussian process regression and Lipschitz
interpolation frameworks have been increasingly studied due to their inherent
ability to provide uncertainty quantification and worst-case error guarantees
which enable the design of robust controllers that ensure system safety and
meet desired performance criterias (e.g. see Hewing et al. (2019), Canale et
al. (2007)).

In contrast to the probabilistic nature of the uncertainty characterisation
provided by Gaussian processes, Lipschitz interpolation-based techniques offer
deterministic guarantees in the form of feasible systems sets (Milanese and
Novara (2004)) and worst-case error bounds (Calliess et al. (2020)). This has
been particularly useful in the context of safety-critical model predictive
control (MPC) where a number of associated non-linear controllers have been
designed and are being researched (see Canale et al. (2014), Manzano et al.
(2020), Manzano et al. (2021) for a selection). At the same time, this
popularity has led to several recent extensions of the original Lipschitz
interpolation framework: (Calliess et al. (2020)) relaxes the assumption of
prior knowledge of the Lipschitz constant in favour of a fully data-driven
approach by incorporating a Lipschitz constant estimation procedure,
(Maddalena and Jones (2020)) proposes an equivalent smooth formulation which
is more suited for controllers that rely on gradient computations, (Blaas et
al. (2019)) extends the framework by incorporating localised Lipschitz
constants and (Manzano et al. (2022)) proposes a computationally more
efficient approach that retains key properties of the original Lipschitz
interpolation framework.

Given the growing use of Lipschitz interpolation frameworks in control,
obtaining a strong theoretical understanding of this method is essential.
While several finite sample guarantees and worst-case error bounds already
exist (see in particular Milanese and Novara (2004), Calliess et al. (2020)),
few consistency results have been derived, to the best of our knowledge, none
under stochastic noise. By contrast, numerous asymptotic guarantees and
convergence rates have been obtained for other popular non-parametric methods.
In particular, for alternative safe-learning frameworks based on Gaussian
processes, both the pointwise convergence of the posterior mean function
(Seeger et al. (2008), Yang et al. (2017), Wynne et al. (2021)) and the
contraction rate of the posterior distribution, which provide a measure of
uncertainty quantification (van der Vaart and van Zanten (2008), Van Der Vaart
and Van Zanten (2011)), of the fitted Gaussian processes have been derived.

These types of asymptotic properties are crucial for adaptive control
applications as they guarantee that the learned dynamics and error bounds
accurately converge to the true underlying system dynamics while also
providing a characterisation of the long-run performance of the regression
method. This in turn ensures that the controllers built on these data-driven
frameworks become increasingly more successful the longer the interaction with
the underlying plant progresses. Considering the computational advantages of
Lipschitz interpolation over Gaussian process regression (Calliess et al.
(2020)), deriving analogous asymptotic guarantees for Lipschitz interpolation
is therefore strongly desirable and constitutes the main motivation of this
paper. Specifically, the following contributions to the literature are made:

  * •

(Main Result) In the case of independent input sampling, general consistency
and upper bounds on the asymptotic convergence rates are obtained for both the
prediction function (Theorem 7) and the worst-case error bounds (Corollary 8)
of the general Lipschitz constant interpolation framework. While convergence
lower bounds do not exist for the exact setting considered in this paper
signifying that the optimality of our bounds is not (yet) established, the
obtained rates are consistent with the optimal convergence rates for non-
parametric regression in related settings; e.g. with the classical convergence
rate results derived by (Stone (1982)).

  * •

In the case of discrete-time non-linear and noisy dynamical systems, we show
that the Lipschitz interpolation framework and worst-case bounds converge
point-wise in moments (Corollary 9 and ensuing discussion) and that, under an
additional sampling assumption, the convergence rates match the ones derived
in the first part of the paper. The first result can be directly applied in
the context of the existing non-linear controllers discussed above (e.g.
Canale et al. (2014), Manzano et al. (2020)) and we provide a simple
illustration in the context of online learning-based trajectory tracking
control (see Section 6).

  * •

In a general sampling setting, probabilistic consistency is shown (Theorem 15)
for the fully data-driven LACKI (Lazily Adapted Constant Kinky Inference)
estimator (Calliess et al. (2020)) that extends the general Lipschitz
interpolation framework by removing the key assumption of prior knowledge of
the Lipschitz constant. This result generalises on Theorem 16 of (Calliess et
al. (2020)) which derives the consistency of the LACKI estimator in the noise-
free setting.

We note that with the goal of obtaining a precise characterisation of the
convergence rates of Lipschitz interpolation methods, we make a non-standard
noise assumption (Assumption 2) utilising the concept of ”non-regular” noise
(Ibragimov and Has’ Minskii (2013)) which describes the behaviour of the tails
of the noise distribution in proximity of assumed noise bounds. This type of
assumption has been used in recent research on non-parametric boundary
regression (see Hall and Van Keilegom (2009), Jirak et al. (2014) and ensuing
works) and allows for a better comparison between the convergence rates of
Lipschitz interpolation derived in this paper and the ones known for Gaussian
process regression and other kernel methods. In fact, the convergence rate
bounds obtained in this paper provide an explicit condition on the tail
behaviour of the noise that indicates when the Lipschitz interpolation should
be expected to asymptotically outperform or underperform other non-parametric
regression paradigms.

##  2 Lipschitz Interpolation: Set-up & Assumptions

Given an input space $\mathcal{X}\subset\mathbb{R}^{d}$ endowed with a metric
$\,\mathfrak{d}:\mathcal{X}^{2}\to\mathbb{R}_{\geq 0}$ and an output
space222Here, it would be possible to extend the analysis done in this paper
to a vector-valued output space, i.e. $\mathcal{Y}\subset\mathbb{R}^{m}$ for
$m\in\mathbb{N}$, by applying the obtained results in a component-wise
fashion. $\mathcal{Y}\subset\mathbb{R}$ endowed with a metric
$\,\mathfrak{d}_{\mathcal{Y}}:\mathcal{Y}^{2}\to\mathbb{R}_{\geq 0}$, the goal
of non-parametric regression is to learn an unknown target function
$f:\mathcal{X}\to\mathcal{Y}$. In this paper, we will assume that $f$ belongs
to the class of $L$-Lipschitz (continuous) functions (with respect to
$\,\mathfrak{d}_{\mathcal{X}}$, $\,\mathfrak{d}_{\mathcal{Y}}$ and some
$L\in\mathbb{R}_{+}$) which we formally define as:

$Lip(L,\,\mathfrak{d}):=\\{h:\mathcal{X}\to\mathcal{Y}|\,\mathfrak{d}_{\mathcal{Y}}(h(x),h(x^{\prime}))\leq
L\,\mathfrak{d}(x,x^{\prime}),\forall x,x^{\prime}\in\mathcal{X}\\}.$

The smallest non-negative number $L^{*}$ for which $f$ is $L^{*}$-Lipschitz is
called the _best_ Lipschitz constant of $f$, i.e.
$L^{*}=\min\\{L\in\mathbb{R}_{\geq 0}|f\in Lip(L,\,\mathfrak{d})\\}$. The
functional assumption that the target function $f$ is $L$-Lipschitz continuous
for some $L\in\mathbb{R}_{+}$ is essential for the application of Lipschitz
interpolation frameworks and is standard in the relevant literature (Milanese
and Novara (2004), Beliakov (2006), Calliess et al. (2020)).

In order to learn $f$, we assume that a sequence of sample sets
$(\mathcal{D}_{n})_{n\in\mathbb{N}}:=(G^{\mathcal{X}}_{n},G^{\mathcal{Y}}_{n})_{n\in\mathbb{N}}$
defined such that $\mathcal{D}_{n}\subset\mathcal{D}_{n+1}$ for
$n\in\mathbb{N}$ is available, where
$G_{n}^{\mathcal{X}}:=\\{s_{i}|i=1,...,N_{n}\\}\subset\mathcal{X}$ represents
a set of sample inputs that can be either deterministically or randomly
generated and
$G^{\mathcal{Y}}_{n}:=\\{\tilde{f}_{i}|i=1,...,N_{n}\\}\subset\mathcal{Y}$
denotes the set of noise-corrupted values of the target function $f$
associated with the inputs in $G_{n}^{\mathcal{X}}$. Unless stated otherwise,
we will also assume that elements of $G^{\mathcal{Y}}_{n}$ are of the form
$\tilde{f}_{k}=f(s_{k})+e_{k}$ where $(e_{k})_{k\in\mathbb{N}}$ is a
collection of random variables denoting the additive observational noise.

In this paper, we will make the following assumption on the noise:

###### Assumption 1

(General noise assumptions) The noise variables $(e_{k})_{k\in\mathbb{N}}$ are
assumed to be independent and identically333The identically distributed
assumption is made to alleviate notation and is not technically needed in our
derivations. distributed random variables with compact support:
$\exists\bar{\mathfrak{e}}>0$ such that $\forall k\in\mathbb{N}:$
$\mathbb{P}\left(e_{k}\in[-\bar{\mathfrak{e}},\bar{\mathfrak{e}}]\right)=1$.
Furthermore, we assume that the bounds of the support are tight in the
following sense:
There exists $\bar{\epsilon}>0$, $\forall
k\in\mathbb{N},\epsilon\in(0,\bar{\epsilon})$:

$\mathbb{P}(e_{k}>\bar{\mathfrak{e}}-\epsilon)>0\quad\text{ and
}\quad\mathbb{P}(e_{k}<-\bar{\mathfrak{e}}+\epsilon)>0$

In order to derive precise upper bounds on the convergence rates, we will
sometimes make an additional noise assumption which describes the behaviour of
the noise at the boundary of its support. This assumption is given formally as
follows:

###### Assumption 2

(Assumptions on the boundary behaviour of the noise) Assume that Assumption 2
holds. We assume that the behaviour of the noise near the bounds of the
support can be characterised in the following sense: There exists
$\bar{\epsilon},\gamma,\eta>0,\forall
k\in\mathbb{N},\epsilon\in(0,\bar{\epsilon})$:

$\mathbb{P}(e_{k}>\bar{\mathfrak{e}}-\epsilon)>\gamma\epsilon^{\eta}\quad\text{
and
}\quad\mathbb{P}(e_{k}<-\bar{\mathfrak{e}}+\epsilon)>\gamma\epsilon^{\eta}.$

(a) $\eta=0.5$

(b) $\eta=1$

(c) $\eta=2$

(d) $\eta=3$

Figure 1:  Illustration of Assumption 2 for various $\eta$. The target
function is given by $f(x)=-\sin(3x)x^{2}+5$ and the noise distribution is
defined as a mixture of two truncated Weibull distributions. The solid lines
define the error bounds of the observed data, i.e. (with abuse of notation)
$f\pm\bar{\mathfrak{e}}$.

###### Example 1

(Noise distributions) For $\eta=1$, commonly used noise distributions with
bounded support such as the uniform or the truncated Gaussian distributions
satisfy Assumption 2. More generally, any noise distribution for which the
density can be bounded away from zero on a bounded symmetric support satisfies
the assumption with $\eta=1$.

The assumption of boundedness of the support of the noise distribution given
in Assumption 1 is standard in the Lipschitz interpolation literature (e.g.
see Milanese and Novara (2004), Calliess et al. (2020)) as it ensures that the
functions $\mathfrak{u}_{n},\mathfrak{l}_{n}$ defined in Definition 1 are
generally well-behaved. By contrast, as noted in the introduction of this
paper, the assumption on the tail of the noise distribution stated in
Assumption 2 is non-standard444But as shown in Example 1, many standard noise
distributions arise as special cases. in the literature. While this assumption
will be not needed to ensure the asymptotic consistency of Lipschitz
interpolation frameworks, the precise characterisation of the bounded tail of
the noise distribution as a function of $\gamma$ and $\eta$ given in
Assumption 2 makes it possible to derive a more refined convergence rate
result that depends on $\eta$.

The general Lipschitz interpolation framework considered in this paper is
defined as follows:

###### Definition 1

(Lipschitz interpolation) Using the set-up defined above, we define the
sequence of predictors $(\hat{f}_{n})_{n\in\mathbb{N}}$,
$\hat{f}_{n}:\mathcal{X}\to\mathcal{Y}$ associated to
$(\mathcal{D}_{n})_{n\in\mathbb{N}}$, as

$\,\mathfrak{\hat{f}_{n}}\bigl{(}x):=\frac{1}{2}\mathfrak{u}_{n}(x)+\frac{1}{2}\mathfrak{l}_{n}(x),$
(1)

where $\mathfrak{u}_{n},\mathfrak{l}_{n}:\mathcal{X}\to\mathcal{Y}$ are
defined as

$\displaystyle\mathfrak{u}_{n}(x)=\min_{i=1,...,N_{n}}\tilde{f}_{i}+L\,\mathfrak{d}(x,s_{i})$
$\displaystyle\mathfrak{l}_{n}(x)=\max_{i=1,...,N_{n}}\tilde{f}_{i}-L\,\mathfrak{d}(x,s_{i})$

and $L\in\mathbb{R}_{\geq 0}$ is a selected hyper-parameter.

Ideally, the hyper-parameter $L\in\mathbb{R}_{\geq 0}$ can be set to be larger
than the best Lipschitz constant $L^{*}$ of the unknown target function. In
this case, existing finite sample and worst-case guarantees can be utilised.

###### Remark 2

(Alternative Formulation) In some works (see in particular Milanese and Novara
(2004), Calliess et al. (2020)) an alternative formulation is given for the
Lispchitz interpolation predictors. In this case, the bounds
($\bar{\mathfrak{e}}$) on the noise distribution are assumed known and are
explicitly used in the formulation of
$\tilde{}\mathfrak{u}_{n},\tilde{}\mathfrak{l}_{n}:\mathcal{X}\to\mathcal{Y}$:

$\displaystyle\tilde{}\mathfrak{u}_{n}(x)=\min_{i=1,...,N_{n}}\tilde{f}_{i}+L\,\mathfrak{d}(x,s_{i})+\bar{\mathfrak{e}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}$
$\displaystyle\tilde{}\mathfrak{l}_{n}(x)=\max_{i=1,...,N_{n}}\tilde{f}_{i}-L\,\mathfrak{d}(x,s_{i})-\bar{\mathfrak{e}}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
This formulation is useful for computing tight worst-case upper and lower
bound guarantees in practice and can be used in the context of this paper to
weaken Assumption 1 by considering asymmetric noise bounds, i.e.
$e\in[\bar{\mathfrak{e}}_{1},\bar{\mathfrak{e}}_{2}]$ with probability $1$
where $\bar{\mathfrak{e}}_{1}<0<\bar{\mathfrak{e}}_{2}\in\mathbb{R}$. All
results derived in this paper can be shown to hold for the alternative
Lipschitz interpolation formulation.

Figure 2:  Illustration of of the consistency of Lipschitz interpolation for
the target function: $f(x)=\sqrt{x}\sin(2x^{2})+0.5x$ on the input space
$\mathcal{X}=[0,2]$, with uniform sampling on $\mathcal{X}$ and with
independent uniform noise: $U([-0.5,0.5])$ on the observations ($\eta=1$). The
Lipschitz interpolation plotted in the lefthand figure utilised 100 samples
and assumed that a bound of ($\bar{\mathfrak{e}}^{\prime}=0.7$) on the noise
bound ($\bar{\mathfrak{e}}=0.5$) was known in order to compute the lower and
upper bounds (the LI predictors can be constructed without knowledge of
$\bar{\mathfrak{e}}^{\prime}$). The convergence rate and standard deviation
plotted on the righthand figure were obtained by running the experiment
independently 20 times. Both plots assumed that access to a bound on the best
Lipschitz constant was known in order to apply the Lipschitz interpolation
framework.

As the description of the input and output metrics has been general so far, we
make the following simplifying assumption on the output metric in order to
obtain our theoretical results.

###### Assumption 3

(Assumption on $\,\mathfrak{d}_{\mathcal{Y}}$). In this paper we will restrict
ourselves to the case,
$\,\mathfrak{d}_{\mathcal{Y}}(y,y^{\prime})=\left\|y-y^{\prime}\right\|_{\mathcal{Y}}$,
$\forall y,y^{\prime}\in\mathcal{Y}$ where $\left\|.\right\|_{\mathcal{Y}}$ is
a norm on $\mathcal{Y}$. It will therefore be sufficient to derive our
asymptotic results for the case: $\left\|.\right\|_{\mathcal{Y}}=|.|$ as
discussed below.

As the norms on $\mathcal{Y}\subset\mathbb{R}$ are of the form
$\left\|y-y^{\prime}\right\|=c|y-y^{\prime}|$ $\forall
y,y^{\prime}\in\mathcal{Y}$ for some $c>0$, it is sufficient to consider the
case $\left\|y-y^{\prime}\right\|_{\mathcal{Y}}=|y-y^{\prime}|$, $\forall
y,y^{\prime}\in\mathcal{Y}$ in order to achieve our theoretical results.
Assumption 3 is necessary in order to ensure that for arbitrary
$x,x^{\prime}\in\mathcal{X}$, the relations: $f(x)\leq
f(x^{\prime})+\frac{L}{c}\,\mathfrak{d}(x,x^{\prime})$ and
$f(x)-\frac{L}{c}\,\mathfrak{d}(x,x^{\prime})\leq f(x^{\prime})$ hold. In
particular, for any sub-linear metric $\,\mathfrak{d}_{\mathcal{Y}}$, these
inequalities no longer hold. We note however that no restrictions are made on
the input metric $\,\mathfrak{d}$.

##  3 Asymptotic Consistency and Convergence Rates

In order for our consistency results to hold for both random and deterministic
sampling approaches, we recall Definition 8: ”Becoming dense, rates,
$\stackrel{{\scriptstyle r}}{{\longrightarrow}},\stackrel{{\scriptstyle
r}}{{\leadsto}},\stackrel{{\scriptstyle r}}{{\twoheadrightarrow}}$” of
(Calliess et al. (2020)) to define general sampling conditions for
$(G_{n})_{n\in\mathbb{N}}$.

###### Definition 3

(Uniformly dense sampling) We say that the sequence of sets of sample inputs
$(G_{n})_{n\in\mathbb{N}}$ becomes uniformly dense relative to $\mathcal{X}$
at a rate $r$ (denoted by $(G_{n})\stackrel{{\scriptstyle
r}}{{\twoheadrightarrow}}\mathcal{X}$) if $\exists
r:\mathbb{N}\to\mathbb{R}_{+}$ such that $\lim_{n\to\infty}r(n)=0$ and
$\forall n\in\mathbb{N}$, $\sup_{x\in\mathcal{X}}\inf_{s_{n}\in
G_{n}}\,\mathfrak{d}(s_{n},x)\leq r(n)$.

Using this definition, we can provide the following asymptotic guarantee for
the general Lipschitz interpolation method.

###### Theorem 4

Suppose Assumptions 1 and 3 hold, $\mathcal{X}$ is bounded and the target
function $f\in Lip(L^{*},\,\mathfrak{d})$555unless specified otherwise,
Lipschitz continuity will be assumed to be w.r.t. the metrics
$\,\mathfrak{d}$,$\,\mathfrak{d}_{\mathcal{Y}}$ on the spaces
$\mathcal{X},\mathcal{Y}$. with best Lipschitz constant
$L^{*}\in\mathbb{R}_{+}$. If the sampling set sequence
$(\mathcal{D}_{n})_{n\in\mathbb{N}}$ has sample inputs
$(G_{n}^{\mathcal{X}})_{n\in\mathbb{N}}$ such that $\exists r\in
o(1):(G_{n}^{\mathcal{X}})\stackrel{{\scriptstyle
r}}{{\twoheadrightarrow}}\mathcal{X}$ and the sequence of predictors
$(\hat{f}_{n})_{n\in\mathbb{N}}$ are computed by a general Lipschitz
interpolation framework with a hyperparameter $L\in\mathbb{R}_{\geq 0}$ set
such that $L\geq L^{*}$ then we have:

$\forall\epsilon>0\text{,
}\lim_{n\to\infty}\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))>\epsilon\right)=0.$

Before providing the proof of Theorem 4, we recall the notion of
$\epsilon$-covering that will be used in multiple proofs of this paper.

###### Definition 5

($\epsilon$-Cover) Let $d\in\mathbb{N}$, $\epsilon>0$ and consider a set
$\mathcal{X}\subset\mathbb{R}^{d}$ and a metric $\,\mathfrak{d}$ on
$\mathbb{R}^{d}$. Denoting $B_{\epsilon}(x)$ the ball of radius $\epsilon$
centred in $x\in\mathcal{X}$ with respect to $\,\mathfrak{d}$, we define an
$\epsilon$-cover of $\mathcal{X}$ as a subset
$Cov(\epsilon)\subset\mathbb{R}^{d}$ such that
$\mathcal{X}\subset\bigcup_{x\in Cov(\epsilon)}B_{\epsilon}(x)$ and the
associated set of balls as $\mathcal{B}:=\\{B_{\epsilon}(x)|x\in
Cov(\epsilon)\\}$. We say furthermore that $Cov(\epsilon)$ is a
$\epsilon$-minimal cover of $\mathcal{X}$ if
$|Cov(\epsilon)|=min\\{n:\exists\epsilon\text{-covering over $\mathcal{X}$of
size n}\\}.$

Proof  We begin by establishing a general bound on
$\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))$, $\forall n\in\mathbb{N}$,
$\forall x\in\mathcal{X}$. For any $x\in\mathcal{X}$ we have:

$\displaystyle\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))=|\hat{f}_{n}(x)-f(x)|$
$\displaystyle=\left|\frac{1}{2}\min_{i=1,...,N_{n}}\\{\tilde{f}_{i}+L\,\mathfrak{d}(x,s_{i})\\}+\frac{1}{2}\max_{i=1,...,N_{n}}\\{\tilde{f}_{i}-L\,\mathfrak{d}(x,s_{i})\\}-f(x)\right|$
$\displaystyle=\left|\frac{1}{2}\min_{i=1,...,N_{n}}\\{\tilde{f}_{i}-f(x)+L\,\mathfrak{d}(x,s_{i})\\}+\frac{1}{2}\max_{i=1,...,N_{n}}\\{\tilde{f}_{i}-f(x)-L\,\mathfrak{d}(x,s_{i})\\}\right|.$

Using the Lipschitz continuity of $f$ , we obtain the following set of
inequality relations for the two terms stated above:

$\displaystyle(1)\min_{i=1,...,N_{n}}\\{e_{i}\\}\leq\min_{i=1,...,N_{n}}\left\\{\tilde{f}_{i}-f(x)+L\,\mathfrak{d}(x,s_{i})\right\\}\leq\min_{i=1,...,N_{n}}\\{e_{i}+(L^{*}+L)\,\mathfrak{d}(x,s_{i})\\}.$
$\displaystyle(2)\max_{i=1,...,N_{n}}\left\\{e_{i}-(L^{*}+L)\,\mathfrak{d}(x,s_{i})\right\\}\leq\max_{i=1,...,N_{n}}\left\\{\tilde{f}_{i}-f(x)-L\,\mathfrak{d}(x,s_{i})\right\\}\leq\max_{i=1,...,N_{n}}\\{e_{i}\\}.$

In combination, we see that

$\displaystyle|\hat{f}_{n}(x)-f(x)|$
$\displaystyle\leq\frac{1}{2}\max\Big{\\{}\underbrace{\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{i=1,...,N_{n}}\left\\{e_{i}+(L^{*}+L)\,\mathfrak{d}(x,s_{i})\right\\}}_{(I)},$
$\displaystyle\underbrace{-\min_{i=1,...,N_{n}}\\{e_{i}\\}-\max\limits_{i=1,...,N_{n}}\left\\{e_{i}-(L^{*}+L)\,\mathfrak{d}(x,s_{i})\right\\}}_{(II)}\Big{\\}}.$

$(I),(II)$ can then be bounded using the assumption of uniform convergence of
the grid (see Definition 3). Define $R:=\frac{\epsilon}{4(L^{*}+L)}$ and
consider the minimal covering of $\mathcal{X}$ of radius $R$ with respect to
$\,\mathfrak{d}$ that we denote $Cov(R)$ and the associated set of hyperballs
$\mathcal{B}$. By uniform convergence of the sample inputs, there exists
$M\in\mathbb{N}$ such that $\forall n>M$: $\forall B\in\mathcal{B}$, $|B\cap
G_{n}^{\mathcal{X}}|>0$. Then, the following upper bound holds for $(I)$ with
$n>M$ ($(II)$ can be bounded in a similar way):

$\displaystyle\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{i=1,...,N_{n}}\\{e_{i}+(L^{*}+L)\,\mathfrak{d}(x,s_{i})\\}$
$\displaystyle\leq$
$\displaystyle\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in B^{x}\cap
G_{n}^{\mathcal{X}}}\\{e(s_{i})+(L^{*}+L)\,\mathfrak{d}(x,s_{i})\\}$
$\displaystyle\leq$
$\displaystyle\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in B^{x}\cap
G_{n}^{\mathcal{X}}}\left\\{e(s_{i})+2(L^{*}+L)R\right\\}$

where with abuse of notation, $e(s_{i})$ denotes the noise term associated
with the input $s_{i}$ and $B^{x}$ denotes a hyperball $B\in\mathcal{B}$ such
that $x\in B$. Similarly for $(II)$, we obtain

$(II)\leq\max_{i=1,...,N_{n}}\\{-e_{i}\\}+\min_{s_{i}\in B^{x}\cap
G_{n}^{\mathcal{X}}}\\{-e(s_{i})+2(L^{*}+L)R\\}.$

Let $\epsilon>0$. Utilising these bounds, $\forall n>M$, we obtain

$\displaystyle\mathbb{P}(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))>\epsilon)$
$\displaystyle\leq\mathbb{P}\Big{(}2(L^{*}+L)R+\frac{1}{2}\sup_{x\in\mathcal{X}}\max\Big{\\{}\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in
B^{x}\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\},$
$\displaystyle-\min_{i=1,...,N_{n}}\\{e_{i}\\}-\max_{s_{i}\in B^{x}\cap
G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}\Big{\\}}>\epsilon\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\frac{1}{2}\max_{B\in\mathcal{B}}\max\Big{\\{}\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\},$
$\displaystyle-\min_{i=1,...,N_{n}}\\{e_{i}\\}-\max_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}\Big{\\}}>\epsilon-2(L^{*}+L)R\Big{)}$
$\displaystyle\leq\mathbb{P}\left(\max_{B\in\mathcal{B}}\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}>\frac{\epsilon}{2}\right)$
$\displaystyle+\mathbb{P}\left(\max_{B\in\mathcal{B}}\max_{i=1,...,N_{n}}\\{-e_{i}\\}+\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}\\{-e(s_{i})\\}\\}>\frac{\epsilon}{2}\right)$

where the last inequality follows by definition of $R$. Both probability terms
stated above can be shown to converge to $0$ as follows:

$\mathbb{P}\left(\max_{B\in\mathcal{B}}\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}>\frac{\epsilon}{2}\right)$
$=1-\mathbb{P}\left(\max_{B\in\mathcal{B}}\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}\leq\frac{\epsilon}{2}\right)$
$=1-\mathbb{P}\left(\forall
B\in\mathcal{B},\max_{i=1,...,N_{n}}\\{e_{i}\\}+\min_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}\leq\frac{\epsilon}{2}\right)$ $\leq
1-\mathbb{P}\left(\forall B\in\mathcal{B}:\max_{i=1,...,N_{n}}\\{e_{i}\\}\in
I_{1},\min_{s_{i}\in B\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}\in
I_{2}\right).$

Here $I_{1}:=[\bar{\mathfrak{e}}-\frac{\epsilon}{4},\bar{\mathfrak{e}}]$ and
$I_{2}:=[-\bar{\mathfrak{e}},-\bar{\mathfrak{e}}+\frac{\epsilon}{4}]$.
Applying a similar argument to the one given in $(\star\star)$ in the proof of
Theorem 7, we have that the last term is upper bounded by

$1-\prod_{B\in\mathcal{B}}\mathbb{P}\left(\max_{i=1,...,N_{n}}\\{e_{i}\\}\in
I_{1},\min_{s_{i}\in B\cap G_{n}^{\mathcal{X}}}\\{e(s_{i})\\}\in I_{2}\right)$
$\leq 1-\mathbb{P}\left(\max_{i=1,...,N_{n}}\\{e_{i}\\}\in
I_{1},\min_{i=1,...,L_{n}}\\{e_{i}\\}\in I_{2}\right)^{|\mathcal{B}|}$

where $L_{n}:=\min_{B\in\mathcal{B}}|B\cap G_{n}^{\mathcal{X}}|$ and $|.|$ is
used to denote the cardinality operator for finite sets. By the uniformity of
the convergence of the sample inputs, we have that
$\lim_{n\to\infty}L_{n}=\lim_{n\to\infty}N_{n}=+\infty$. Using basic
identities of probability theory and applying Assumption 1, we have that

$\lim_{n\to\infty}\mathbb{P}\left(\max_{i=1,...,N_{n}}\\{e_{i}\\}\in
I_{1},\min_{i=1,...,L_{n}}\\{e_{i}\\}\in I_{2}\right)=1$

which implies that

$\lim_{n\to\infty}\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))>\epsilon\right)=0$

and concludes the proof.

Theorem 4 ensures that the classical Lipschitz interpolation method is
asymptotically consistent for a general selection of input metrics.
Furthermore, a similar result for Lipschitz interpolation with a multi-
dimensional output setting $\mathcal{Y}\subset R^{m}$ for $m\in\mathbb{N}$
follows naturally by applying Theorem 4 to each output component function (the
noise assumption would need to be modified in this case; e.g. see Assumption
7).

In general, we are mostly interested in simple metric choices for
$\,\mathfrak{d}$. In this case with additional assumptions on $\mathcal{X}$
and $\mathcal{Y}$, we can extend the result obtained in Theorem 4 by deriving
asymptotic rates of convergence for the general Lipschitz interpolation
method. More precisely, we have the following definition (Györfi et al.
(2002)):

###### Definition 6

Consider a sequence of non-parametric predictors
$(\hat{f}_{n})_{n\in\mathbb{N}}$ and a class of functions $\mathcal{C}$
endowed with a norm $\left\|.\right\|$. Let $(a_{n})_{n\in\mathbb{N}}$ be a
sequence of positive constants in $\mathbb{R}$. We define
$(a_{n})_{n\in\mathbb{N}}$ as the rate of convergence of
$(\hat{f}_{n})_{n\in\mathbb{N}}$ on $\mathcal{C}$ with respect to
$\left\|.\right\|$ if there exists $c>0$ such that

$\limsup_{n\to\infty}\sup_{f\in\mathcal{C}}\mathbb{E}\left[a_{n}^{-1}\left\|\hat{f}_{n}-f\right\|\right]=c<\infty.$

In order to avoid extreme cases of compact spaces, the following general
assumption provides a light geometric assumption on $\mathcal{X}$.

###### Assumption 4

(Geometric Assumption on $\mathcal{X}$) Let $\mathcal{X}\subset\mathbb{R}^{d}$
be compact and convex. There exist two constants $r_{0}>0,\theta\in(0,1]$ such
that $\forall x\in\mathcal{X}$, $r\in\left(0,r_{0}\right):\newline
\operatorname{vol}\left(B_{r}(x)\cap\mathcal{X}\right)\geq\theta\operatorname{vol}\left(B_{r}(x)\right)$.

Assumption 4 has been used in the learning theory literature (e.g. see Hu et
al. (2020) Bachoc et al. (2021)) and ensures that for all $x\in\mathcal{X}$, a
constant fraction of ball with a sufficiently small radius and centred in $x$
is contained in $\mathcal{X}$. For example, if $\mathcal{X}$ is a the unit
hypercube then Assumption 4 holds with $r_{0}=1,\theta=2^{-d}$.

The additional assumptions on the sampling of the sample inputs
$(D_{n})_{n\in\mathbb{N}}$ and metric of the input space $\,\mathfrak{d}$ are
relatively standard and are given as follows:

###### Assumption 5

(Assumption on Sampling) $(G_{n}^{\mathcal{X}})_{n\in\mathbb{N}}$ is a
randomly sampled sequence on $\mathcal{X}$ with a sampling distribution
density that is bounded away from zero on $\mathcal{X}$.

###### Assumption 6

(Hölder Condition) We restrict the input space metrics under consideration to
be of the form $\,\mathfrak{d}(x,y)=\left\|x-y\right\|_{p}^{\alpha}$ where
$\alpha\in(0,1]$ and $\left\|.\right\|_{p}$ denotes the usual $p$-norm on
$\mathbb{R}^{d}$ with $p\in\mathbb{N}\cup\\{+\infty\\}$.

###### Theorem 7

Consider an input space $\mathcal{X}\subset\mathbb{R}^{d}$ that satisfies
Assumption 4, an output space $\mathcal{Y}\subset\mathbb{R}$ and the function
space $\mathcal{C}=Lip(L^{*},\,\mathfrak{d})$ with $L^{*}\in\mathbb{R}_{\geq
0}$ endowed with the supremum-norm:
$\left\|h\right\|_{\infty}=\sup_{x\in\mathcal{X}}\left\|h(x)\right\|_{\mathcal{Y}}$.
Assume that Assumptions 1, 2, 5, 6 with $\alpha\in(0,1]$, $p\in\mathbb{N}$
hold. Then, any sequence of predictors $(\hat{f}_{n})_{n\in\mathbb{N}}$
generated by the general Lipschitz interpolation framework set with a
hyperparameter $L\geq L^{*}$ achieves a rate of convergence of at least
$(a_{n})_{n\in\mathbb{N}}:=\left((n^{-1}log(n))^{\frac{\alpha}{d+\eta\alpha}}\right)_{n\in\mathbb{N}}$
with respect to $\left\|.\right\|_{\infty}$, i.e.

$\limsup_{n\to\infty}\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}\mathbb{E}\left[a_{n}^{-1}\left\|\hat{f}_{n}-f\right\|_{\infty}\right]<\infty.$

Proof  See appendix B.

Convergence lower bounds do not exist for the exact setting considered in this
paper signifying that we cannot directly compare the rates stated in Theorem 7
to a theoretically optimal convergence rate. Instead, we can note that the
convergence rate of Lipschitz interpolation is in line with several known
optimal rates in related settings (see Table 1), i.e. non-parametric
regression on the Lipschitz continuous function space endowed with an $L_{2}$
or $L_{\infty}$ norm. In particular, we note that the exponent of the
convergence rate derived for Lipschitz interpolation exactly matches the
exponent of the convergence rate derived in Tsybakov (2004) in the case where
the noise distribution is assumed to be uniform (i.e. $\eta=1$). Our
convergence rate is however larger by a log-factor due to a difference in
norm.

Furthermore, by varying $\eta$ in Assumption 2, we can compare our rate of
convergence:
O$\left((n^{-1}log(n)\right)^{\frac{\alpha}{d+\eta\alpha}})_{n\in\mathbb{N}}$
to classical non-parametric convergence rates. More precisely, we observe the
following:

  * •

For $\eta<2$: the derived convergence rates for Lipschitz interpolation are
better than the known optimal convergence rates obtained under a Gaussian tail
noise assumption on the noise distribution:
$(n^{-1}log(n))^{\frac{\alpha}{2\alpha+d}}$ (Stone (1982)) which are
attained666Note that these methods can be shown to converge at this rate under
the simple assumption of bounded variance (Györfi et al. (2002)). by Gaussian
process regression (Yang et al. (2017)) and other kernel-based non-parametric
methods such as local polynomial regression (Stone (1982)) or the Nadaraja-
Watson estimator (Tsybakov (2004), Müller and Wefelmeyer (2010)).

  * •

For $\eta>2$: the opposite becomes true and these alternative non-parametric
methods can be expected to converge quicker asymptotically than the Lipschitz
interpolation framework.

Algorithm/Type | Convergence Rate | Noise Assumption | Norm
---|---|---|---
LI (Upper Bound) | O$\left(n^{-1}log(n)\right)^{\frac{\alpha}{d+\eta\alpha}}$ | Bounded |  $L_{\infty}$.
Optimal (Tsybakov (2004)) | $\Theta\left(n^{-1}\right)^{\frac{\alpha}{d+\alpha}}$ | Uniform ($\eta=1$) | $L_{2}$
Optimal (Stone (1982)) | $\Theta\left(n^{-1}log(n)\right)^{\frac{\alpha}{d+2\alpha}}$ | Gaussian 444Various generalisations of this noise assumption exist, see Stone (1982). | $L_{\infty}$
Optimal (Stone (1982)) | $\Theta\left(n^{-1}\right)^{\frac{\alpha}{d+2\alpha}}$ | Gaussian44footnotemark: 4 | $L_{2}$
Optimal (Jirak et al. (2014)) |  $\Theta\left(n^{-1}\right)^{\frac{\alpha}{1+\eta\alpha}}$ (d=1) | Boundary Regr. | $L_{2}$
Upper Bound (Selk et al. (2022)) | O$\left(n^{-1}log(n)\right)^{\frac{\alpha}{d+\eta\alpha}}$ | Boundary Regr. | $L_{\infty}$
Table 1: Comparison of the convergence rate derived in Theorem 7 with optimal
rates of convergence rates in similar settings and discussion given in this
section.

This ”$\eta$-condition” provides a theoretical tool for comparing the expected
long-run performance of Lipschitz interpolation relative to alternative non-
parametric methods and can help guide the choice of the system identification
approach if information on the non-regularity of the noise distribution is
obtainable. We note that the convergence rates of the kernel-based non-
parametric methods stated in Table 1 hold under general noise assumptions (see
footnotes 4 and 6 below) and that, aside from the Nadaraja-Watson estimator,
no formal derivation of improved convergence rates in the bounded noise
setting considered in this paper currently exists777To the extent of our
knowledge. for these methods. As these kernel-based non-parametric frameworks
generally rely on local averaging of the noise in order to prove convergence,
it is expected that their convergence rates do not improve with respect to
their classical convergence rates (stated in Table 1) under Assumption 1 and
Assumption 2. This has been formally shown to be true for the Nadaraja-Watson
estimator by Müller and Wefelmeyer (2010) and a more general discussion on the
topic can be found in Meister and Reiß (2013).

Figure 3:  Illustration of the behaviour of the convergence rates derived in
Theorem 7 for various values of $(d,\alpha,\eta)$.

As discussed above, the convergence rates obtained in Theorem 7 under the
bounded noise assumptions are better than the classical optimal convergence
rates derived by Stone (1982). This is possible as the lower bounds of these
optimal convergence rates are generally derived under the condition that the
noise has a positive density with respect to the Lebesgue measure on
$\mathbb{R}$ which does not hold for the noise assumptions of this paper. As a
consequence, $O\left(n^{-1}log(n)\right)^{\frac{\alpha}{d+\eta\alpha}}$
provides a new general upper bound on the non-parametric regression problem in
the bounded noise setting and future work can be done on deriving lower bounds
to match these results. We expect the lower bounds to be tight given recent
results by Jirak et al. (2014) on the optimal convergence rates of the related
non-parametric boundary regression problem (see below for a more detailed
discussion).

The optimality results of Theorem 2 of Milanese and Novara (2004) show that
$(\tilde{}\mathfrak{u}_{n})_{n\in\mathbb{N}}$,
$(\tilde{}\mathfrak{l}_{n})_{n\in\mathbb{N}}$ are exactly equal to the upper
and lower bounds of the feasible systems set, i.e. the set of all data-
consistent Lipschitz continuous systems and therefore provide worst-case error
prediction bounds. With little modification to the proof of Theorem 7, both
error bounds can be shown to converge to $f$ at the same rate as
$(\hat{f}_{n})_{n\in\mathbb{N}}$ as stated in the following Corollary.

###### Corollary 8

Assume that the setting and assumptions of Theorem 7 holds. The worst-case
prediction guarantees $(\tilde{}\mathfrak{u}_{n})_{n\in\mathbb{N}}$,
$(\tilde{}\mathfrak{l}_{n})_{n\in\mathbb{N}}$ defined in Remark 2 with second
hyperparameter: $\bar{\mathfrak{e}}^{\prime}=\bar{\mathfrak{e}}$, converge
uniformly to any target function $f\in Lip(L^{*},\,\mathfrak{d})$ at a rate of
at least $((n^{-1}log(n))^{\frac{\alpha}{d+\eta\alpha}})_{n\in\mathbb{N}}$.

Proof  Follows from the proof of Theorem 7.

A connection between our convergence results and succeeding work on non-
parametric boundary regression (see Hall and Van Keilegom (2009) and ensuing
works) can be made. More precisely, consider the predictive functions
$(\tilde{}\mathfrak{u}_{n}^{\prime})_{n\in\mathbb{N}}$,
$(\tilde{}\mathfrak{l}_{n}^{\prime})_{n\in\mathbb{N}}$ defined for all
$n\in\mathbb{N}$ as
$\tilde{}\mathfrak{u}_{n}^{\prime}:\mathcal{X}\to\mathcal{Y}$,
$x\mapsto\mathfrak{u}_{n}(x)+\bar{\mathfrak{e}}_{1}+\bar{\mathfrak{e}}_{2}$
and $\tilde{}\mathfrak{l}_{n}^{\prime}:\mathcal{X}\to\mathcal{Y}$,
$x\mapsto\mathfrak{l}_{n}(x)-\bar{\mathfrak{e}}_{1}-\bar{\mathfrak{e}}_{2}$
where $\bar{\mathfrak{e}}_{1},\bar{\mathfrak{e}}_{2}$ are tight asymmetric
bounds on the noise. $(\tilde{}\mathfrak{u}_{n}^{\prime})_{n\in\mathbb{N}}$,
$(\tilde{}\mathfrak{l}_{n}^{\prime})_{n\in\mathbb{N}}$ can be interpreted as
conservative non-parametric boundary regression methods. Therefore, in the
context of bounded noise, the two problems are equivalent and we can again
slightly modify the proof of Theorem 7 to obtain the same uniform asymptotic
convergence rates of $O(n^{-1}log(n))^{\frac{\alpha}{\eta d+\alpha}})$ as
$(\hat{f}_{n})_{n\in\mathbb{N}}$. These rates exactly match the recently
derived best convergence rates in the multivariate boundary regression problem
(Selk et al. (2022)) and have the same exponent888They differ by a log-factor
which is usual when considering the $L_{\infty}$ norm instead of the $L_{2}$
norm. as the optimal rates derived with respect to the $L_{2}$ norm (Jirak et
al. (2014)). In order to properly define
$(\tilde{}\mathfrak{u}_{n}^{\prime})_{n\in\mathbb{N}}$,
$(\tilde{}\mathfrak{l}_{n}^{\prime})_{n\in\mathbb{N}}$, prior knowledge of an
upper bound on the Lipschitz constant ($L\geq L^{*}$) as well as the Hölder
exponent ($\alpha$) and of tight bounds of the noise
($\bar{\mathfrak{e}}_{1},\bar{\mathfrak{e}}_{2}$) are needed. However in
contrast to the proposed ”best” non-parametric estimators that attain the
optimal rates, we do not require prior knowledge of the degree of ”non-
regularity” of the noise ($\eta$, defined in Assumption 2) which is usually
required in order to define an optimal bandwidth hyperparameter (Drees et al.
(2019), Selk et al. (2022)). In the bounded noise setting, our assumption is
therefore arguably more natural and simpler to verify in practice as ($\eta$)
is generally hard to determine precisely.

##  4 Online Learning: Asymptotics

A set-up not yet explicitly considered in this paper but relevant to control
applications is when the output variables can be used as input variables. More
specifically, we consider the case where $f$ models the dynamics of a non-
linear autoregressive stochastic system with exogenous control variables:

$y_{n}=f(x_{n})+e_{n}$

where $x_{n}=(y_{n-d_{y}},...,y_{n-1},u_{n-d_{u}},...,u_{n})$ with
$y_{i}\in\mathcal{Y}\subset\mathbb{R}$ and
$u_{i}\in\mathcal{U}\subset\mathbb{R}^{s}$ for $d_{y},d_{u},s\in\mathbb{N}$
and $e_{n}\in\mathbb{R}$ is a noise variable that satisfies Assumption 1.
Here, $y_{i}$ denotes the autoregressive inputs and the $u_{i}$ denote vectors
of past and current control inputs. In this setting, we will therefore
consider
$\mathcal{X}=\mathbb{R}^{d_{y}}\times\mathcal{U}^{d_{u}+1}\subset\mathbb{R}^{d_{y}+(d_{u}+1)(s)},\mathcal{Y}=\mathbb{R}$.
If the dynamics and control inputs are such that the underlying dynamical
system is ergodic then Theorem 4 can be applied and a weaker version of
Theorem 7 can be derived. However, in general, this cannot be guaranteed and
the following result on the asymptotic point-wise convergence of the general
Lipschitz interpolation framework is needed.

###### Corollary 9

Consider
$\mathcal{X},\mathcal{Y},(x_{n})_{n\in\mathbb{N}},(u_{n})_{n\in\mathbb{N}},(y_{n})_{n\in\mathbb{N}}$
as defined above, $L^{*}\geq 0$ and $(\hat{f}_{n})_{n\in\mathbb{N}}$ as
defined in Definition 1 with $L\geq L^{*}$ and
$(\mathcal{D}_{n})_{n\in\mathbb{N}}=(x_{n},y_{n})_{n\in\mathbb{N}}$. Suppose
that Assumptions 1, 3 hold. Assume furthermore that
$\mathcal{U}\subset\mathbb{R}^{s}$ is bounded. Then $\forall p\in\mathbb{N}$,
$M^{*}\in\mathbb{R}^{+}$

$\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{E}\left[\left\|f(x_{n+1})-\hat{f}_{n}(x_{n+1})\right\|_{\mathcal{Y}}^{p}\right]\to
0$

where $\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$ denotes the set containing
all functions in $Lip(L^{*},\,\mathfrak{d})$ that are bounded by $M^{*}$, i.e.
$\left\|f\right\|_{\infty}\leq M^{*}$.

Proof  As in the proof of Theorem 7, we have that for all $n\geq 1$ and any
sampling procedure $\mathcal{D}_{n}$,
$\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\left\|\hat{f}_{n}-f\right\|_{\infty}$
is uniformly bounded with probability $1$. This follows from (1) the existence
of a bounded set $\tilde{}\mathcal{X}\subset\mathcal{X}$ such that
$(x_{n})_{n\in\mathbb{N}}\subset\tilde{}\mathcal{X}$ (with probability 1)
which is due to the boundedness of
$\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$, the compactness of $\mathcal{U}$
and Assumption 1 (which implies that the noise is bounded), (2) $f\in
Lip(L^{*},\,\mathfrak{d})$ and (3) by construction of the Lipschitz
interpolation framework. More precisely, we have $\forall n\in\mathbb{N}$,
$\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\left\|\hat{f}_{n}-f\right\|_{\infty}\leq
2\bar{\mathfrak{e}}+2L\delta_{\,\mathfrak{d}}(\tilde{}\mathcal{X})$ where
$\delta_{\,\mathfrak{d}}(\tilde{}\mathcal{X}):=\sup_{x,y\in\tilde{}\mathcal{X}}\,\mathfrak{d}(x,y)$.
Using Lemma 25, it is therefore sufficient to show convergence in probability,
i.e.

$\forall\epsilon>0:\text{
}\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{P}(|\hat{f}_{n}(x_{n+1})-f(x_{n+1})|>\epsilon)=0$

which can be done through a modified proof of Theorem 4 as follows. Fix
$\epsilon>0$ and consider the minimal covering of $\bar{}\mathcal{X}$ by balls
of radius $r<\frac{\epsilon}{4(L^{*}+L)}$ which we denote $cov(r)$ and the
associated set of hyperballs $\mathcal{B}$ (the existence of a finite covering
is guaranteed by the boundedness of $\tilde{}\mathcal{X}$). There exists
$N_{1}\in\mathbb{N}$ such that for all $B\in\mathcal{B}$; $(x_{n})_{n\geq
N_{1}}\cap B\in\\{0,+\infty\\}$. Denoting by
$\mathcal{\tilde{B}}\subset\mathcal{B}$ the subset of $\mathcal{B}$ consisting
of hyperballs that contain an infinite number of elements of $(x_{n})_{n\geq
N_{1}}$, we can proceed as in the proof of Theorem 4.

Let $f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$ be arbitrary. For
$n>N_{1}$ sufficiently large (such that there is at least one sample input in
each hyperball of $\mathcal{\tilde{B}}$), applying the same arguments as in
the proof of Theorem 4:

$\mathbb{P}\left(\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x_{n+1}),f(x_{n+1}))>\epsilon\right)$
$\leq\mathbb{P}\left(\max_{B\in\mathcal{\tilde{B}}}\left|\max_{i=1,...,n}\\{e_{i}\\}+\min_{x_{i}\in
B}\\{e(x_{i})\\}\right|>\frac{\epsilon}{2}\right)+\mathbb{P}\left(\max_{B\in\mathcal{\tilde{B}}}\left|\min_{i=1,...,n}\\{e_{i}\\}+\max_{x_{i}\in
B}\\{e(x_{i})\\}\right|>\frac{\epsilon}{2}\right).$

As the choice of $f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$ was
arbitrary and the upper bound expressed above does not depend on $f$, we have
that both terms of this upper bound can be treated with the same approach as
the one used to conclude the proof of Theorem 4. This implies

$\displaystyle\quad\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{P}\left(|\hat{f}_{n}(x_{n+1})-f(x_{n+1})|>\epsilon\right)$
$\displaystyle\leq\lim_{n\to\infty}\mathbb{P}\left(\max_{B\in\mathcal{\tilde{B}}}|\max_{i=1,...,n}\\{e_{i}\\}+\min_{x_{i}\in
B}\\{e(x_{i})\\}|>\frac{\epsilon}{2}\right)$
$\displaystyle+\lim_{n\to\infty}\mathbb{P}\left(\max_{B\in\mathcal{\tilde{B}}}|\min_{i=1,...,n}\\{e_{i}\\}+\max_{x_{i}\in
B}\\{e(x_{i})\\}|>\frac{\epsilon}{2}\right)$ $\displaystyle=0$

which concludes the proof.

The setting considered in Corollary 9 is the same as the one considered in
Milanese and Novara (2004) and in ensuing applications of the Lipschitz
interpolation framework in the context of MPC (see Canale et al. (2014),
Manzano et al. (2020)). As in Corollary 8, the worst-case prediction
guarantees $(\tilde{}\mathfrak{u}_{n})_{n\in\mathbb{N}}$,
$(\tilde{}\mathfrak{l}_{n})_{n\in\mathbb{N}}$ can be shown to provide similar
guarantees to the one proposed Corollary 9 which provides a theoretical
guarantee that even conservative adaptive controllers relying on worst-case
bounds of Lipschitz interpolation methods will consider the true underlying
dynamics in the long run. In Section 6, a slight modification of Corollary 18
that considers dynamics with multidimensional outputs
$(y_{n})_{n\in\mathbb{N}}$ is given. This extension is then applied in the
context of tracking control in order to obtain closed-loop stability
guarantees for a simple online-learning based controller

To conclude this section, we remark that if an additional assumption is made
on the sequence of inputs $(x_{n})_{n\in\mathbb{N}}$, then the convergence
rate derived in Theorem 7 holds in the online learning setting. This
assumption is given using the following definition on the ”regularity of the
sampling” of $(x_{n})_{n\in\mathbb{N}}$.

###### Definition 10

(Regularity Assumption for $(x_{n})_{n\in\mathbb{N}}$) We say that
$(x_{n})_{n\in\mathbb{N}}$ is regularly sampled on a set
$\bar{}\mathcal{X}\subset\mathcal{X}$ if $\exists N\in\mathbb{N}$,
$(x_{n})_{n\in\mathbb{N}_{\geq N}}\subset\bar{}\mathcal{X}$ and $\exists
M\in\mathbb{N}$ such that $\forall n>N$ and $\forall
A\subset\bar{}\mathcal{X}$ ,

$\mathbb{P}(x_{n+M}\in A|x_{n})>C\mu(A)$

where $\mu(A)$ denotes the Lebesgue measure of $A$ and $C>0$ is an arbitrary
constant.

In essence, Definition 1 states that $(x_{n})_{n\in\mathbb{N}}$ is regularly
sampled on a given set $\bar{}\mathcal{X}\subset\mathcal{X}$ if
$(x_{n})_{n\in\mathbb{N}}$ will eventually be contained in $\bar{}\mathcal{X}$
and will continue to visit all of $\bar{}\mathcal{X}$ with non-zero
probability. The existence of such a set depends implicitly on the target
function and the defined control inputs.

###### Corollary 11

Assume that the setting and assumptions of Corollary 9 hold and consider
$f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$. If Assumption 2 holds and
the stochastic control law $u_{n+1}:=u(x_{n},\hat{f}_{n},\mathcal{D}_{n})$ is
defined such that $(x_{n})_{n\in\mathbb{N}}$ is regularly sampled on a bounded
set $\bar{}\mathcal{X}\subset\mathcal{X}$ that satisfies Assumption 4, then

$\limsup_{n\to\infty}\mathbb{E}[a_{n}^{-1}\left\|f(x_{n+1})-\hat{f}_{n}(x_{n+1})\right\|_{\mathcal{Y}}]<\infty.$

where
$(a_{n})_{n\in\mathbb{N}}:=((n^{-1}log(n))^{\frac{\alpha}{d+\eta\alpha}})_{n\in\mathbb{N}}$.

###### Remark 12

From the proof of Corollary 9, we have that if $\mathcal{U}$ is bounded and
$f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$, then there exists a bounded
$\tilde{}\mathcal{X}\subset\mathcal{X}$ that contains
$(x_{n})_{n\in\mathbb{N}}$ with probability $1$. Therefore, only the second
part of Definition 10 and the geometric shape of $\bar{}\mathcal{X}$ need to
be checked in order for Corollary 11 to hold.

Proof  The proof of Corollary 11 follows from Theorem 7. More precisely:

By assumption, we have that there exists $M,N\in\mathbb{N}$ and a bounded set
$\bar{}\mathcal{X}\subset\mathcal{X}$ such that Definition 10 and Assumption 4
hold. Consider the sequence $(x_{n})_{n\in\mathbb{N}{\geq
N}}\subset\bar{}\mathcal{X}$ and the subsequence
$(\tilde{x}_{n})_{n\in\mathbb{N}}\subset(x_{n})_{n\in\mathbb{N}_{\geq N}}$
defined such that $\tilde{x}_{n}=x_{Mn+N}$ for all $n\in\mathbb{N}$. From
Definition 10, we have that for all $n\in\mathbb{N}$, $\tilde{x}_{n}$ is
sampled on $\bar{}\mathcal{X}$ with a probability distribution whose density
is bounded away from zero on all of $\bar{}\mathcal{X}$.

Then, defining $(\hat{f}_{n}^{M})_{n\in\mathbb{N}}$ as the predictors of the
Lipschitz interpolation framework with hyperparameter $L$ and sample inputs
$(\tilde{x}_{n})_{n\in\mathbb{N}}$, we can apply Theorem 7 to
$(\hat{f}_{n}^{M})_{n\in\mathbb{N}}$. This implies that
$(\hat{f}_{n}^{M})_{n\in\mathbb{N}}$ converges uniformly on
$\bar{}\mathcal{X}$ to $f$ at a rate that is upper bounded by
$(a_{\left\lfloor\frac{n}{M}\right\rfloor})_{n\in\mathbb{N}}=\tilde{c}(a_{n})_{n\in\mathbb{N}}$
for some $\tilde{c}>$ that depends on $M$ and where $n\in\mathbb{N}$ denotes
the index of the original sequence: $(x_{n})_{n\in\mathbb{N}}$. As the
asymptotic convergence rate of $(\hat{f}_{n})_{n\in\mathbb{N}}$ is at least as
fast as the convergence rate of $(\hat{f}_{n}^{M})_{n\in\mathbb{N}}$ due to
the fact that the input samples utilised by
$(\hat{f}_{n}^{M})_{n\in\mathbb{N}}$ are also utilised by
$(\hat{f}_{n})_{n\in\mathbb{N}}$, we have that
$(\hat{f}_{n})_{n\in\mathbb{N}}$ achieves the same uniform convergence rate on
$\bar{}\mathcal{X}$. Finally, as $(x_{n})_{n\in\mathbb{N}_{\geq
N}}\subset\bar{}\mathcal{X}$, the same converge rate holds for the pointwise
asymptotic convergence of $(x_{n})_{n\in\mathbb{N}}$, i.e.

$\limsup_{n\to\infty}\mathbb{E}[a_{n}^{-1}\left\|f(x_{n+1})-\hat{f}_{n}(x_{n+1})\right\|_{\mathcal{Y}}]$

with
$(a_{n})_{n\in\mathbb{N}}:=((n^{-1}log(n))^{\frac{\alpha}{d+\eta\alpha}})_{n\in\mathbb{N}}$.

While Corollary 11 provides an interesting extension to Theorem 7, the
characterisation of the regularly sampling set $\bar{X}$ and the necessity of
ensuring that Assumption 4 holds for $\bar{}\mathcal{X}$ can be difficult to
do in practice. Therefore, in comparison to Corollary 9 which can be directly
utilised in various control applications, Corollary 11 is essentially a
theoretical result.

##  5 Removing the Lipschitz Constant Assumption

The main difficulty of the Lipschitz interpolation framework is obtaining a
suitable hyper-parameter that properly estimates the Lipschitz constant of the
unknown target function. In cases where prior knowledge of the Lipschitz
constant of $f$ is not obtainable, an additional step is therefore needed.
While one solution would be to compute this estimate offline beforehand, this
approach is problematic when considering a stream of data. Instead, one can
consider the approach developed by Novara et al. (2013) and applied in the
context of Lipschitz interpolation by Calliess et al. (2020) which utilises a
modified version of Strongin’s Lipschitz constant estimator (Strongin (1973))
to $(\mathcal{D}_{n})_{n\in\mathbb{N}}$ to obtain a sequence
$(L(n))_{n\in\mathbb{N}}$ of approximations of $L^{*}$. These estimates can be
continuously updated with the arrival of new data and are defined formally in
the following definition.

###### Definition 13

(LACKI rule) The Lazily Adapted Lipschitz Constant Kinky Inference (LACKI)
rule computes a Lipschitz interpolation predictor $\,\mathfrak{\hat{f}_{n}}$
as per Definition 1, but where L depends on
$(\mathcal{D}_{n})_{n\in\mathbb{N}}$ and is computed as follows:

$L(n):=\max\Bigl{\\{}0,\max_{(s,s^{\prime})\in
U_{n}}\frac{\,\mathfrak{d}_{\mathcal{Y}}(\tilde{f}(s),\tilde{f}(s^{\prime}))-\lambda}{\,\mathfrak{d}(s,s^{\prime})}\Bigr{\\}},$
(2)

where $U_{n}=\\{(g_{1},g_{2})\in G_{n}^{\mathcal{X}}\times
G_{n}^{\mathcal{X}}|\,\mathfrak{d}(g_{1},g_{2})>0\\}$ and $\lambda$ is a
hyperparameter.

The noise bounds can be correctly estimated if the $\lambda$ hyper-parameter
of the LACKI rule is set to $2\bar{\mathfrak{e}}$. Calliess et al. (2020)
provides worst-case prediction bounds even when the noise bounds are not
correctly estimated. In this paper, we focus on the case where the noise
bounds are known and $\lambda$ can be correctly specified. We note that the
Lipschitz estimator $L(n)$ given by LACKI is the smallest Lipschitz constant
that is consistent with the data. In other words, it reduces the hypothesis
space of Lipschitz continuous functions $Lip(L(n),\,\mathfrak{d})$ that the
target function f could belong to.

We start by showing that the LACKI rule proposed in Definition 13 converges
asymptotically to the best Lipschitz constant of the unknown target function.

###### Lemma 14

If the assumptions of Theorem 4 hold, then :

$\forall\epsilon>0,\lim_{n\to\infty}\mathbb{P}(|L(n)-L^{*}|>\epsilon)=0$

Proof  Fix an arbitrary $\epsilon>0$. We start by defining an auxiliary
function F:

$\displaystyle F:Dom(F):=\mathcal{X}\times\mathcal{X}-\\{(x$
$\displaystyle,x)|x\in\mathcal{X}\\}\longrightarrow\mathbb{R}_{\leq 0}$
$\displaystyle(x,y)$
$\displaystyle\longmapsto\frac{\,\mathfrak{d}_{\mathcal{Y}}{(f(x),f(y))}}{\,\mathfrak{d}(x,y)}$

By construction, $L^{*}=\sup_{(x,y)\in Dom(F)}F(x,y)$ and there exists
$(x_{1},x_{2})\in Dom(F)$ such that $L^{*}-\frac{\epsilon}{2}\leq
F(x_{1},x_{2})\leq L^{*}$. Hence,

$\mathbb{P}\left(|L(n)-L^{*}|>\epsilon\right)$
$\leq\mathbb{P}\left(|L(n)-F(x_{1},x_{2})|+|F(x_{1},x_{2})-L^{*}|>\epsilon\right)$
$=\mathbb{P}\left(|F(x_{1},x_{2})-L(n)|>\frac{\epsilon}{2}\right)=\mathbb{P}\left(F(x_{1},x_{2})-L(n)>\frac{\epsilon}{2}\right).$

Since F is continuous on its domain, we have that $\exists\delta_{1}>0$ such
that $\forall(x,y)\in B_{\delta_{1}}((x_{1},x_{2}))$999Here,
$B_{\delta}((x_{1},x_{2}))$ denotes the ball centered in $(x_{1},x_{2})$ of
radius $\delta_{1}$ with respect to
$\,\mathfrak{d}_{\mathcal{X}\times\mathcal{X}}$ defined such that
$\,\mathfrak{d}_{\mathcal{X}\times\mathcal{X}}((x_{1},x_{2}),(x_{1}^{\prime},x_{2}^{\prime}))=\,\mathfrak{d}(x_{1},x_{1}^{\prime})+\,\mathfrak{d}(x_{2},x_{2}^{\prime})$
$\cap$ $Dom(F)$, $|F(x_{1},x_{2})-F(x,y)|<\frac{\epsilon}{2}$. Defining
$0<\delta_{2}<\min\\{\frac{\delta_{1}}{2},\frac{\,\mathfrak{d}(x_{1},x_{2})}{2}\\}$,
we consider the two hyperballs $B_{1}:=B_{\delta_{2}}(x_{1})$,
$B_{2}:=B_{\delta_{2}}(x_{1})$. Then

$\displaystyle F(x_{1},x_{2})$ $\displaystyle-L(n)$
$\displaystyle=F(x_{1},x_{2})$ $\displaystyle-\max_{(s,s^{\prime})\in
U_{n}}\frac{|\tilde{f}(s)-\tilde{f}(s^{\prime})|-\lambda}{\,\mathfrak{d}(s,s^{\prime})}$
$\displaystyle\leq F(x_{1},x_{2})$ $\displaystyle-\max_{s_{i}\in
B_{1},s_{j}\in
B_{2}}\frac{|\tilde{f}(s_{1})-\tilde{f}(s_{j})|-\lambda}{\,\mathfrak{d}(s_{i},s_{j})}$
$\displaystyle\leq F(x_{1},x_{2})$
$\displaystyle-\max_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{|f(s_{i})-f(s_{j})|+|e(s_{i})-e(s_{j})|-\lambda}{\,\mathfrak{d}(s_{i},s_{j})}$
$\displaystyle\leq F(x_{1},x_{2})$
$\displaystyle-\min_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{|f(s_{i})-f(s_{j})|}{\,\mathfrak{d}(s_{i},s_{j})}$
$\displaystyle-\max_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{|e(s_{i})-e(s_{j})|-\lambda}{\,\mathfrak{d}(s_{i},s_{j})}.$

where
$cond(x,y):=\left\\{sgn\left(f(s_{i})-f(s_{j})\right)=sgn\left(e(s_{i})-e(s_{j})\right)\right\\}$
and with abuse of notation, $\tilde{f}(s_{i})$ $e(s_{i})$ denote the noise
term associated with the input $s_{i}$. By definition of $B_{1}$, $B_{2}$, we
have

$\displaystyle F(x_{1},x_{2})-\min_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in
B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{|f(s_{i})-f(s_{j})|}{\,\mathfrak{d}(s_{i},s_{j})}$
$\displaystyle=F(x_{1},x_{2})-\min_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in
B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}F(s_{i},s_{j})\leq\frac{\epsilon}{4}.$

Substituting this value into the initial expression, we can obtain the upper
bound

$\displaystyle\frac{\epsilon}{4}-\max_{\begin{subarray}{c}s_{i}\in
B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{|e(s_{i})-e(s_{j})|-\lambda}{\,\mathfrak{d}(s_{i},s_{j})}$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{4}+\min_{\begin{subarray}{c}s_{i}\in
B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{\lambda-|e(s_{i})-e(s_{j})|}{\,\mathfrak{d}(s_{i},s_{j})}$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon}{4}+\min_{\begin{subarray}{c}s_{i}\in
B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{\lambda-|e(s_{i})-e(s_{j})|}{\,\mathfrak{d}(x_{1},x_{2})-2\delta_{2}}.$

By the assumption of uniformly dense sampling, there exists $M\in\mathbb{N}$
such that $r(M)<{\delta_{2}}$. Therefore, for $n>M$,

$\mathbb{P}\left(F(x_{1},x_{2})-L(n)>\frac{\epsilon}{2}\right)$
$\leq\mathbb{P}\left(\min_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\frac{\lambda-|e(s_{i})-e(s_{j})|}{\,\mathfrak{d}(x_{1},x_{2})-2\delta_{2}}>\frac{\epsilon}{4}\right)$
$\leq\mathbb{P}\left(\min_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}\left\\{\lambda-|e(s_{i})-e(s_{j})|\right\\}>\frac{\epsilon}{4}(\,\mathfrak{d}(x_{1},x_{2})-2\delta_{2})\right)$
$=\mathbb{P}\left(\max_{\begin{subarray}{c}s_{i}\in B_{1},s_{j}\in B_{2}\\\
cond(s_{i},s_{j})\end{subarray}}|e(s_{i})-e(s_{j})|<\lambda-\frac{\epsilon}{4}(\,\mathfrak{d}(x_{1},x_{2})-2\delta_{2})\right).$

As $\lambda=2\bar{\mathfrak{e}}$ and
$\,\mathfrak{d}(x_{1},x_{2})>2\delta_{2}$, the last expression can be shown to
converge to 0 as $n$ goes to $\infty$ by a similar argument to the one used in
the proof of Theorem 4.

Lemma 14 proves that the modified version of Strongin’s estimate defined in
Definition 13 is a consistent Lipschitz constant estimator under bounded
noise. It is therefore of interest for applications outside the one considered
in this paper, e.g. see in particular global optimisation methods that depend
explicitly on the Lipschitz constant (see for example Malherbe and Vayatis
(2017)). One main drawback however is that none of the finite sample estimates
generated by the LACKI rule upper bound the true Lipschitz constant. This is
discussed in more detail after Theorem 15.

Using Theorem 4 and Lemma 14, we can now show that the sequence of LACKI
predictors $(\hat{f}_{n})_{n\in\mathbb{N}}$ converges uniformly and in
probability to the target function $f$.

###### Theorem 15

If the assumptions of Theorem 4 hold, then the sequence of LACKI predictors
$(\hat{f}_{n})_{n\in\mathbb{N}}$ with $\lambda=2\bar{\mathfrak{e}}$ converges
to f uniformly and in probability:

$\forall\epsilon>0,\lim_{n\to\infty}\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))>\epsilon\right)=0$

Proof  The proof of Theorem 15 follows from Theorem 4 and Lemma 14. Fix an
arbitrary $\epsilon>0$, we have

$\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),f(x))>\epsilon\right)$
$\leq\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}(x),\hat{f}_{n}^{*}(x))>\frac{\epsilon}{2}\right)+\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}^{*}(x),f(x))>\frac{\epsilon}{2}\right)$

where $(\hat{f}_{n}^{*})_{n\in\mathbb{N}}$ denotes the general Lipschitz
interpolation framework with a hyperparameter equal to the best Lipschitz
constant $L^{*}$ of $f$. The second term of the upper bound given above
converges to 0 as $n\to\infty$ by Theorem 4. For the first term, we have

$\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}_{\mathcal{Y}}(\hat{f}_{n}^{*}(x),\hat{f}_{n}(x))>\frac{\epsilon}{2}\right)$
$\leq\mathbb{P}\left(\sup_{x\in\mathcal{X}}\frac{1}{2}|\min_{i=1,...,N_{n}}\\{\tilde{f}_{i}+L(n)\,\mathfrak{d}(x,s_{i})\\}-\min_{i=1,...,N_{n}}\\{\tilde{f}_{i}+L^{*}\,\mathfrak{d}(x,s_{i})\\}|>\frac{\epsilon}{4}\right)$
$+\mathbb{P}\left(\sup_{x\in\mathcal{X}}\frac{1}{2}|\max_{i=1,...,N_{n}}\\{\tilde{f}_{i}-L(n)\,\mathfrak{d}(x,s_{i})\\}-\max_{i=1,...,N_{n}}\\{\tilde{f}_{i}-L^{*}\,\mathfrak{d}(x,s_{i})\\}|>\frac{\epsilon}{4}\right)$
$\leq\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}(x,s^{*}_{i})|L^{*}-L(n)|>\frac{\epsilon}{4}\right)+\mathbb{P}\left(\sup_{x\in\mathcal{X}}\,\mathfrak{d}(x,s^{*}_{k})|L^{*}-L(n)|>\frac{\epsilon}{4}\right)$
$\leq
2\mathbb{P}\left(\delta_{\,\mathfrak{d}}(\mathcal{X})|L^{*}-L(n)|>\frac{\epsilon}{4}\right)$
(3)

where
$s^{*}_{i}:=\text{argmin}_{i=1,...,N_{n}}\\{\tilde{f}_{i}+L(n)\,\mathfrak{d}(x,s_{i})\\}$
and
$s^{*}_{k}:=\text{argmax}_{i=1,...,N_{n}}\\{\tilde{f}_{i}-L(n)\,\mathfrak{d}(x,s_{i})\\}$.
As $\delta_{\,\mathfrak{d}}(\mathcal{X})$ is finite by assumption, Lemma 14
can be applied to show that
$\mathbb{P}(\delta_{\,\mathfrak{d}}(\mathcal{X})|L^{*}-L(n)|>\frac{\epsilon}{4})$
converges to 0.

In general, it suffices for the sequence of Lipschitz constant estimates to
converge to a value that is bigger than the best Lipschitz constant in order
for the consistency guarantees given in Theorem 15 to hold. This follows from
the fact that Lemma 14 holds for any Lipschitz interpolation framework with
$L\geq L^{*}$. Furthermore, if the Lipschitz constant estimate can be
guaranteed to be feasible101010i.e. $\hat{L}(n)\geq L^{*}$. in a finite number
of queries and is asymptotically bounded, then the rate of convergence of the
adaptive Lipschitz interpolation method matches the one derived in Theorem 7.
Unfortunately, as remarked above, the LACKI rule proposed in Definition 13 is
not feasible for any finite number of sample points but converges only
asymptotically to the true best Lipschitz constant. One approach to remedying
this problem would be to include a multiplicative factor $\kappa\geq 1$
(similar to the original approach proposed by Strongin (1973) in the noiseless
sampling setting) in the LACKI rule. However, developing a principled approach
to setting $\kappa$ is non-trivial and depends on second order partial
derivatives of the unknown target function.

Furthermore, in contrast to the general Lipschitz interpolation approach, the
LACKI estimator is also not necessarily asymptotically consistent in the
setting of a non-linear discrete-time dynamic system. This is due to the fact
that dependent on the sampling sequence, the LACKI rule may never become large
enough to ensure that the relations (1) and (2) derived in the proof of Lemma
14 hold. This issue could potentially be fixed by including a ”memory hyper-
parameter” that limits the number of past observations considered in the
$\mathfrak{u}_{n}$, $\mathfrak{l}_{n}$ functions. This extension will be
investigated in future work.

In essence, while the general Lipschitz interpolation framework can be shown
to perform well as a non-parametric estimation method, the additional
difficulty of Lipschitz constant estimation implies that many of the desirable
asymptotic properties become difficult to obtain for a fully adaptive version
of the framework. A detailed discussion on this issue can be found in Huang et
al. (2023) where optimal convergence rates are given for the Lipschitz
constant estimation problem and a feasible asymptotically consistent
estimation method is developed.

##  6 Connections to Online Learning and Control

We conclude this paper by providing a simple illustration of the potential
applicability of our results to learning-based control. More precisely, we
slightly modify the online consistency results of the general Lipschitz
interpolation stated in Section 4 in order to obtain closed-loop stability of
a class of online learning-based trajectory tracking controllers discussed in
Sanner and Slotine (1991), Åström and Wittenmark (2013), Chowdhary et al.
(2013), Calliess et al. (2020).

We briefly recall the setting of the trajectory tracking control problem
considered by Calliess et al. (2020). The goal is to ensure that a sequence of
states $(y_{n})_{n\in\mathbb{N}}$ follows a given reference trajectory
$(\xi_{n})_{n\in\mathbb{N}}$. In order to do so, it is assumed that the states
$(y_{n})_{n\in\mathbb{N}}$ satisfy a multivariate recurrence relation
described as follows:

$y_{n}=f(x_{n})$

where $x_{n}=(y_{n-d_{y}},...,y_{n-1},u_{n-d_{u}},...,u_{n})$ with
$y_{i}\in\mathcal{Y}\subset\mathbb{R}^{l}$ denoting the past autoregressive
inputs, $u_{i}\in\mathcal{U}\subset\mathbb{R}^{s}$ denoting a vector of past
or current control inputs for $d_{y},d_{u},s,l\in\mathbb{N}$. In this setting,
we will therefore consider
$\mathcal{X}=\mathbb{R}^{(l)(d_{y})}\times\mathcal{U}^{d_{u}+1}\subset\mathbb{R}^{(l)(d_{y})+(s)(d_{u}+1)}$,
$\mathcal{Y}=\mathbb{R}^{l}$. Note that in contrast to the setting considered
in Section 4 the noise does not impact the state and will only be assumed to
be observational: we assume that the Lipschitz interpolation framework has
access to noisy samples of function values $f(x_{i})$ at each time step $i<n$:
$\mathcal{D}_{n}=\\{(x_{i},\tilde{f}_{i})|i<n\\}$.

Under this assumption on the system dynamics, the problem becomes equivalent
to defining a control law that ensures that the tracking error
$(\zeta_{n})_{n\in\mathbb{N}}$, $\zeta_{n}=\xi_{n}-y_{n}$ becomes stable:
obtaining, in an ideal scenario, a closed-loop recurrence relation

$\zeta_{n+1}=\phi(\zeta_{n})$

where $\phi$ is a contraction with a desirable fixed point $\zeta_{*}$,
typically $\zeta_{*}=0$.

This type of stability is well-known to be achievable when the dynamics of the
states $(y_{n})_{n\in\mathbb{N}}$ are known and sufficiently well-behaved
(Åström and Wittenmark (2013)) or when $f$ is assumed unknown but well
approximated by linear learning-based methods (Limanond and Tsakllis (2000)).
Obtaining such guarantees in the setting where $f$ is assumed both unknown and
non-linear is less straightforward although significant research has been
conducted with the use of non-parametric regression methods (Sanner and
Slotine (1991), Chowdhary et al. (2013), Calliess et al. (2020)).

Under a general assumption on the control law, the online-learning guarantees
of the Lipschitz interpolation method (Corollary 9 and Lemma 18) derived in
this paper can be shown to directly imply the convergence of the tracking
error to a fixed point, therefore ensuring the asymptotic stability of the
controller.

To do so, we begin by formally extending the online guarantees of the
Lipschitz interpolation stated in Corollary 9 to the multi-dimensional online
setting described above. In this case, the Lipschitz interpolation framework
is applied component-wise as follows:

###### Definition 16

(Multi-dimensional Lipschitz interpolation) Let $L\in\mathbb{R}_{\geq 0}$ be a
selected hyper-parameter. Using the set-up defined above, we define the
sequence of predictors $(\hat{f}_{n})_{n\in\mathbb{N}}$,
$\hat{f}_{n}:\mathcal{X}\to\mathcal{Y}$ associated to
$(\mathcal{D}_{n})_{n\in\mathbb{N}}$, as

$\forall
j\in\\{1,...,l\\},\quad\,\mathfrak{\hat{f}_{n}}^{i}\bigl{(}x):=\frac{1}{2}\mathfrak{u}_{n}^{j}(x)+\frac{1}{2}\mathfrak{l}_{n}^{j}(x),$

where $\mathfrak{u}_{n}^{j},\mathfrak{l}_{n}^{j}:\mathcal{X}\to\mathbb{R}$ are
defined as

$\displaystyle\mathfrak{u}_{n}^{j}(x)=\min_{i=1,...,N_{n}}{\tilde{f}_{n,i}^{j}}+L\,\mathfrak{d}(x,s_{i})$
$\displaystyle\mathfrak{l}_{n}^{j}(x)=\max_{i=1,...,N_{n}}{\tilde{f}_{n,i}^{j}}-L\,\mathfrak{d}(x,s_{i})$

for all $j\in\\{1,...,l\\}$.

We note that under Assumption 8 provided below, it is relatively
straightforward to observe that each component of the target function is also
Lipschitz continuous with the same Lipschitz constant. This implies that the
properties utilised in the previous sections hold component-wise for the
multi-dimensional Lipschitz interpolation framework.

In order to derive the desired online guarantee for the Lipschitz
interpolation framework described in Definition 16, we first extend the
assumptions of the previous sections to the multi-dimensional output setting.

###### Assumption 7

(Assumption on multi-dimensional noise) The noise variables
$(e_{k})_{k\in\mathbb{N}}$, $e_{k}\in\mathbb{R}^{d}$ are assumed to be
independent and identically111111The identically distributed assumption is
made to alleviate notation and is not technically needed in our derivations.
distributed random variables such that
$\exists\bar{\mathfrak{e}}\in\mathbb{R}_{+}^{d}$, such that $\forall
k\in\mathbb{N}$ $j\in\\{1,...,d\\}$,
$e_{k}^{j}\in[-\bar{\mathfrak{e}}^{j},\bar{\mathfrak{e}}^{j}]$ with
probability $1$. We assume further that the bounds of the support are tight,
i.e. $\forall\epsilon>0$, $\forall j\in\\{1,...,d\\}$,

$\mathbb{P}(e_{k}^{j}\in[-\bar{\mathfrak{e}}^{j}+\epsilon,\bar{\mathfrak{e}}^{j}]),\mathbb{P}(e_{k}^{j}\in[-\bar{\mathfrak{e}}^{j},\bar{\mathfrak{e}}^{j}-\epsilon])>0.$

###### Assumption 8

(Assumption on $\,\mathfrak{d}_{\mathcal{Y}}$). In this section, we will
restrict ourselves to the case,
$\,\mathfrak{d}_{\mathcal{Y}}(y,y^{\prime})=\left\|y-y^{\prime}\right\|_{1}$,
$\forall y,y^{\prime}\in\mathcal{Y}$ where $\left\|.\right\|_{1}$ denotes the
usual 1-norm.

###### Remark 17

By the strong equivalence of norms on $\mathbb{R}^{l}$, it is sufficient to
show the results of this section for
$\left\|.\right\|_{\mathcal{Y}}=\left\|.\right\|_{1}$. Additionally, we note
that if a Lipschitz constant of the target function is known for a given norm
on $\mathbb{R}^{l}$, then it is straightforward to compute a feasible
Lipschitz constant for any other norm on $\mathbb{R}^{l}$.

###### Corollary 18

(Multidimensional Online Learning) Consider the multidimensional setting
described above121212With the same arguments, one can show that the same
result holds for the multidimensional version of the dynamical system
described in Section 4., $L^{*},M^{*}\in\mathbb{R}^{+}$ and
$(\hat{f}_{n})_{n\in\mathbb{N}}$ as defined in Definition 16 with $L\geq
L^{*}$ and
$(\mathcal{D}_{n})_{n\in\mathbb{N}}=(x_{n},y_{n})_{n\in\mathbb{N}}$. Assume
that Assumptions 7 and 8 hold. Assume furthermore that $\mathcal{U}$ is
compact. Then

$\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{E}[\left\|f(x_{n+1})-\hat{f}_{n}(x_{n+1})\right\|_{\mathcal{Y}}]\to
0$

where we recall that $\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$ denotes the
set containing all functions in $Lip(L^{*},\,\mathfrak{d})$ that are bounded
by $M^{*}$, i.e. $\left\|f(x)\right\|_{\mathcal{Y}}\leq M^{*}$.

Proof  By the strong equivalence of norms on $\mathbb{R}^{l}$, it is
sufficient to show Lemma 18 for
$\left\|.\right\|_{\mathcal{Y}}=\left\|.\right\|_{1}$:

$\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{E}[\left\|f(x_{n+1})-\hat{f}_{n}(x_{n+1})\right\|_{1}]\to
0.$

This is implied if $\forall j\in\\{1,...,l\\}$:

$\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{E}[|f^{j}(x_{n+1})-\hat{f}^{j}_{n}(x_{n+1})|]\to
0$

where $f^{j}_{n},\hat{f}^{j}_{n}$ denote the j-th component functions of
$f_{n},\hat{f}_{n}$. This statement can be derived using the same arguments as
the ones given in the proof of Corollary 9 as, under Assumption 8, $f$ is
component-wise Lipschitz continuous with Lipschitz constant $L^{*}$ and by
construction, the multi-dimensional Lipschitz interpolation framework can be
considered component-wise.
Utilising Lemma 18, we can now state the closed-loop guarantees of an online
controller based on the Lipschitz interpolation framework.

###### Theorem 19

Assume the settings described above. Assume that reference trajectory
$(\xi_{n})_{n\in\mathbb{N}}$ is bounded and that the recursive plant dynamics
satisfy: $f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$ for some
$L^{*},M^{*}>0$. Let $(\hat{f}_{n})_{n\in\mathbb{N}}$ be the predictors
generated by the Lipschitz interpolation framework with hyperparameter $L\geq
L^{*}$ and
$(\mathcal{D}_{n})_{n\in\mathbb{N}}=(x_{n},\tilde{f}_{i})_{n\in\mathbb{N}}$.
If there exists a bounded control law
$u_{n+1}:=u(x_{n},\hat{f}_{n},\mathcal{D}_{n})$ such that the closed loop
dynamics are given by:

$\zeta_{n+1}=\phi(\zeta_{n})+d_{n}$

where $d_{n}:=f(x_{n})-\hat{f}(x_{n})$ is the one-step prediction error and
$\phi$ is a contraction with a fixed point $\zeta_{*}\in\mathcal{X}$ and
Lipschitz constant $\lambda_{\phi}\in[0,1)$, then we have

$\lim_{n\to\infty}\mathbb{E}[\left\|\zeta_{n}-\zeta_{*}\right\|_{\mathcal{Y}}]=0.$

Proof  The proof follows a modified version of the proof Theorem 17 of
Calliess et al. (2020) and an application of Corollary 19.

Define the _nominal reference error_ $(\bar{\zeta}_{n})_{n\in\mathbb{N}}$,
$\bar{\zeta}_{0}=\zeta_{0}$, $\bar{\zeta}_{n+1}=\phi(\bar{\zeta}_{n})$ for
$n\in\mathbb{N}$. Fix an arbitrary $\epsilon>0$. The proof of Theorem 19
follows from the following sequence of steps.

By the Banach fixed point Theorem, $\exists n_{0}\in\mathbb{N}$ such that
$\forall n\geq n_{0}$,
$\left\|\bar{\zeta}_{n}-\zeta_{*}\right\|_{\mathcal{Y}}<\frac{\epsilon}{3}$.

Inductively, one can show that $\forall n,k\in\mathbb{N}$,

$\mathbb{E}[\left\|\zeta_{k}-\bar{\zeta}_{k}\right\|_{\mathcal{Y}}]$
$\leq\lambda_{\phi}^{n}\mathbb{E}[\left\|\zeta_{k}-\bar{\zeta}_{k}\right\|_{\mathcal{Y}}]+\sum^{n-1}_{i=0}\lambda_{\phi}^{n-1-i}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}]$
$\leq\lambda_{\phi}^{n}\mathbb{E}[\left\|\zeta_{k}-\bar{\zeta}_{k}\right\|_{\mathcal{Y}}]+\frac{1}{1-\lambda_{\phi}}\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}].$

By Lemma 18, we have that $\mathbb{E}[\left\|d_{n}\right\|_{\mathcal{Y}}]$
converges to 0 as n goes to infinity. Therefore, $\exists k_{0}\in\mathbb{N}$
such that $\forall k\geq k_{0}$,

$\frac{1}{1-\lambda_{\phi}}\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}]\leq\frac{\epsilon}{3}.$

Let $m_{0}:=\max\\{n_{0},k_{0}\\}$. Since $\lambda_{\phi}^{q_{0}}<1$, there
exists $q_{0}\in\mathbb{N}$ such that:

$\lambda_{\phi}^{q_{0}}\mathbb{E}[\left\|\zeta_{m_{0}}-\bar{\zeta}_{m_{0}}\right\|_{\mathcal{Y}}]<\frac{\epsilon}{3}.$

Let $M:=m_{0}+q_{0}$. Combining the above steps, we have for any $m>M$ there
exists $n\geq q_{0}$ such that $m=m_{0}+n$. This implies

$\mathbb{E}[\left\|\zeta_{m}-\zeta_{*}\right\|_{\mathcal{Y}}]\leq\left\|\zeta_{*}-\bar{\zeta}_{m}\right\|_{\mathcal{Y}}+\mathbb{E}[\left\|\zeta_{m}-\bar{\zeta}_{m}\right\|_{\mathcal{Y}}]$
$\leq\frac{\epsilon}{3}+\lambda_{\phi}^{q_{0}}\mathbb{E}[\left\|\zeta_{m_{0}}-\bar{\zeta}_{m_{0}}\right\|_{\mathcal{Y}}]+\frac{1}{1-\lambda_{\phi}}\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{m_{0}+i}\right\|_{\mathcal{Y}}]$
$\leq\frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{\epsilon}{3}=\epsilon.$

As the choice of $\epsilon$ was arbitrary, this concludes the proof.

Theorem 19 provides a theoretical result on the global stability in
expectation of a general class of control problems where both the system
dynamics and the error dynamics are assumed to be both unknown and non-linear.
An extension of Theorem 19 which states that the convergence rates of the
Lipschitz constant estimator derived in Corollary 11 hold for the tracking
error $(\zeta_{n})_{n\in\mathbb{N}}$ can also be obtained. However, this
result would be contingent on the difficult-to-verify ”regularity of the
sampling” assumption of $(x_{n})_{n\in\mathbb{N}}$ (as defined in Definition
10) and is therefore of limited interest. We provide it in the appendix for
completeness.

Unfortunately, for numerous applications, the contraction assumption on
dynamics of the tracking error $\phi$ is too stringent to be achieved in
practice. To alleviate this issue, Theorem 19 can be extended to consider the
more general assumption that $\phi$ is an eventually contracting function if
$\phi$ is also assumed to be a linear. More formally, we define an eventually
contracting function as follows.

###### Definition 20

(Eventually Contracting Function) Let $l\in\mathbb{N}$. A continuous function
$h:\mathbb{R}^{l}\to\mathbb{R}^{l}$ is said to be eventually contracting if
there exists $N\in\mathbb{N}$ and $\lambda\in[0,1)$ such that $\forall
x,y\in\mathbb{R}^{l}$:

$\,\mathfrak{d}(h^{N}(x),h^{N}(y))\leq\lambda\,\mathfrak{d}(x,y).$

As with the contracting functions considered above, eventually contracting
functions can be shown to admit a unique fixed point $\xi^{*}$. Additionally,
it is well-known that a linear function $h:\mathbb{R}^{l}\to\mathbb{R}^{l}$
defined as $h(x)=Mx$ for some matrix $M\in\mathbb{R}^{l\times l}$ is
eventually contracting if and only if the spectral radius of $M$ is strictly
smaller than 1: $\rho(M)<1$.

The assumption of the existence of a control law
$u_{n+1}:=u(x_{n},\hat{f}_{n},\mathcal{D}_{n})$ such that the closed loop
dynamics are given by: $\zeta_{n+1}=\phi(\zeta_{n})+d_{n}$and $\phi$ is
eventually contracting can be observed in applications such as the removal of
wing rock during the landing of modern fighter aircraft (Monahemi and Krstic
(1996), Chowdhary et al. (2013)). Therefore, if Theorem 19 can be extended to
hold under these assumptions, then, conditional on the existence of feasible
Lipschitz constant estimate, the online learning-based reference tracking
controllers utilising a Lipschitz interpolation can be ensured to be globally
asymptotically stable in expectation in these settings. This alternative
result is stated in the following corollary.

###### Corollary 21

Assume the setting and initial assumptions of Theorem 19. If there exists a
bounded control law $u_{n+1}:=u(x_{n},\hat{f}_{n},\mathcal{D}_{n})$ such that
the closed loop dynamics are given by:

$\zeta_{n+1}=\phi(\zeta_{n})+d_{n}$

where $d_{n}:=f(x_{n})-\hat{f}(x_{n})$ is the one-step prediction error and
$\phi:\mathbb{R}^{l}\to\mathbb{R}^{l}$, $\phi(\zeta)=M\zeta$ for a matrix
$M\in\mathbb{R}^{l\times l}$ that is a stable, i.e. $\rho(M)<1$. Then

$\lim_{n\to\infty}\mathbb{E}[\left\|\zeta_{n}\right\|_{\mathcal{Y}}]=0.$

Proof  The proof of Corollary 21 is similar to the on given for Theorem 19.

Define the nominal reference error $(\bar{\zeta}_{n})_{n\in\mathbb{N}}$,
$\bar{\zeta}_{0}=\zeta_{0}$, $\bar{\zeta}_{n+1}=\phi(\bar{\zeta}_{n})$ for
$n\in\mathbb{N}$. Fix an arbitrary $\epsilon>0$.

As $\rho(M)<1$, we have that $\lim_{n\to\infty}\bar{\zeta}_{n}=0$ (Hasselblatt
and Katok (2003)). This implies that $\exists n_{0}\in\mathbb{N}$ such that
$\forall n\geq n_{0}$,
$\left\|\bar{\zeta}_{n}\right\|_{\mathcal{Y}}<\frac{\epsilon}{3}$.

Inductively, one can show that $\forall n,k\in\mathbb{N}$,

$\mathbb{E}[\left\|\zeta_{n+k}-\bar{\zeta}_{n+k}\right\|_{\mathcal{Y}}]$
$\leq\left\|M^{n}\right\|_{\mathcal{Y}}\mathbb{E}\left[\left\|(\zeta_{k}-\bar{\zeta}_{k})\right\|_{\mathcal{Y}}\right]+\sum^{n-1}_{i=0}\left\|M^{n-1-i}\right\|_{\mathcal{Y}}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}].$

By Gelfand’s formula we have
$\lim_{n\to\infty}\left\|M^{k}\right\|^{\frac{1}{k}}=\rho(M)<1$ for any matrix
norm $\left\|.\right\|$. This implies that there exists $n_{1}$ such that for
all $n\geq n_{1}$:
$\left\|M^{n}\right\|_{\mathcal{Y}}\leq\left\|M^{n}\right\|_{\mathcal{Y}}^{\frac{1}{n}}<\lambda_{\phi}<1$
for some $\lambda_{\phi}\in(0,1)$. Utilising this relation and matrix-vector
inequalities, we obtain the following inequalities: let $n\geq n_{1}$, there
exists $n_{2}\in\mathbb{N}\cup\\{0\\}$ such that
$n=n_{1}\left\lfloor\frac{n}{n_{1}}\right\rfloor+n_{2}$:

$\left\|M^{n}\right\|_{\mathcal{Y}}=\left\|M^{n_{1}(\left\lfloor\frac{n}{n_{1}}\right\rfloor-1)}M^{n_{1}+n_{2}}\right\|_{\mathcal{Y}}\leq\left\|M^{n_{1}}\right\|_{\mathcal{Y}}^{(\left\lfloor\frac{n}{n_{1}}\right\rfloor-1)}\left\|M^{n_{1}+n_{2}}\right\|_{\mathcal{Y}}\leq\lambda_{\phi}^{(\left\lfloor\frac{n}{n_{1}}\right\rfloor-1)}\lambda_{\phi}=\lambda_{\phi}^{\left\lfloor\frac{n}{n_{1}}\right\rfloor}.$

Substituting this inequality into the bound given above, we obtain:

$\left\|M^{n}\right\|_{\mathcal{Y}}\mathbb{E}\left[\left\|(\zeta_{k}-\bar{\zeta}_{k})\right\|_{\mathcal{Y}}\right]+\sum^{n-1}_{i=0}\left\|M^{n-1-i}\right\|_{\mathcal{Y}}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}]$
$\leq\lambda_{\phi}^{\left\lfloor\frac{n}{n_{1}}\right\rfloor}\mathbb{E}[\left\|(\zeta_{k}-\bar{\zeta}_{k})\right\|_{\mathcal{Y}}]+\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}]\left(K_{n_{1}}+\sum^{\left\lceil\frac{n-1}{n_{1}}\right\rceil}_{i=1}n_{1}\lambda_{\phi}^{i}\right)$
$\leq\lambda_{\phi}^{\left\lfloor\frac{n}{n_{1}}\right\rfloor}\mathbb{E}[\left\|(\zeta_{k}-\bar{\zeta}_{k})\right\|_{\mathcal{Y}}]+\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}]\left(K_{n_{1}}+\frac{n_{1}}{1-\lambda_{\phi}}\right)$

where $K_{n_{1}}:=\sum^{n_{1}-1}_{i=0}\left\|M^{i}\right\|_{\mathcal{Y}}$ By
Lemma 18, we have that $\mathbb{E}[\left\|d_{n}\right\|_{\mathcal{Y}}]$
converges to 0 as n goes to infinity. Therefore, $\exists k_{0}\in\mathbb{N}$
such that $\forall k\geq k_{0}$,

$\left(K_{n_{1}}+\frac{n_{1}}{1-\lambda_{\phi}}\right)\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{k+i}\right\|_{\mathcal{Y}}]\leq\frac{\epsilon}{3}.$

Let $m_{0}:=\max\\{n_{0},k_{0}\\}$. There exists $q_{0}\in\mathbb{N}$ such
that

$\lambda_{\phi}^{\left\lfloor\frac{q_{0}}{n_{1}}\right\rfloor}\mathbb{E}[\left\|\zeta_{m_{0}}-\bar{\zeta}_{m_{0}}\right\|_{\mathcal{Y}}]<\frac{\epsilon}{3}.$

Let $M:=m_{0}+q_{0}$. Combining the above steps, we have that for all $m>M$,
there exists $n\geq q_{0}$ such that $m=m_{0}+n$. This implies

$\mathbb{E}[\left\|\zeta_{m}\right\|_{\mathcal{Y}}]\leq\left\|\bar{\zeta}_{m}\right\|_{\mathcal{Y}}+\mathbb{E}[\left\|\zeta_{m}-\bar{\zeta}_{m}\right\|_{\mathcal{Y}}]$
$\leq\frac{\epsilon}{3}+\lambda_{\phi}^{\left\lfloor\frac{q_{0}}{n_{1}}\right\rfloor}\mathbb{E}[\left\|\zeta_{m_{0}}-\bar{\zeta}_{m_{0}}\right\|_{\mathcal{Y}}]+\left(K_{n_{1}}+\frac{n_{1}}{1-\lambda_{\phi}}\right)\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{m_{0}+i}\right\|_{\mathcal{Y}}]$
$\leq\frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{\epsilon}{3}=\epsilon.$

As the choice of $\epsilon$ was arbitrary, this concludes the proof.

###  6.1 Example - model-reference adaptive control of a single pendulum

As a simple illustration, we replicate a modification of the model-reference
adaptive control example in Calliess et al. (2020). Here, we control an Euler
discretisation of a torque-actuated single pendulum in set-point control mode:

We consider a torque controlled pendulum where forces $u$ can be applied to
the joint of the pendulum. The angle of the pendulum is called $q$. We define
a state $x=[q\dot{q}]$. In continuous-time, it’s dynamics are given by the ODE
$\ddot{q}=f(x)+u$ where $f(x)=-\sin(q)-\dot{q}$ may be uncertain a priori and
hence, needs to be learned online while we control.

Figure 4:  Illustration of the pendulum control example. A single run is
depicted in the leftmost figure showing how the controller learns to drive the
state to the set-point in spite of the noise and initially uncertain dynamics.
Note, “Time” is simulation time $t=\Delta n$ [sec.] for discrete time steps
$n=0,1,...$. The second figure shows how the mean trajectories, averaged over
30 repetitions (each with new draws from the noise distribution), converge to
the set-point. An illustration of our theory, predicting vanishing tracking
errors in the mean, is depicted in the rightmost figure: For each repetition
of the experiment, the colored lines show the error trajectories
$(\left\|\xi({\Delta n})-x(\Delta n)\right\|)_{n=0,1,2,\dots}$ as well as
their empirical mean (black dashed line).

As explained in Section 4 of Calliess et al. (2020), using online learning of
noisy measurements of angular accelerations (but assuming full state
observability) we can use Lipschitz interpolation to learn a model
$\hat{f}_{n}$ at time step $n$ define a control law
$u(x)=-\hat{f}_{n}(x)-K_{1}x_{1}-K_{2}x_{2}$ with gains $K_{1},K_{2}>0$ such
that the closed-loop error dynamics becomes:

$\displaystyle\zeta_{n+1}$ $\displaystyle=\phi(\zeta_{n})+\Delta d_{n}$ (4)
$\displaystyle=\underbrace{M\zeta_{n}}_{=:\phi(\zeta_{n})}+\Delta d_{n}$ (5)

where $\Delta=0.1$ is a sampling period for the time discretisation,
$d_{n}=f(x_{n})-\hat{f}_{n}(x_{n})$ is the tracking error and
$M=\left(\begin{array}[h]{cc}1&\,\Delta\\\ -\Delta K_{1}&1-\Delta
K_{2}\end{array}\right)$ is a matrix, where the gain parameters
$K_{1},K_{2}=1$ were chosen to render $M$ stable (i.e. such that its spectral
radius $\rho(M)<1$). This renders the closed-loop tracking error dynamics
consistent with the one considered in Corollary 21 and as previously
discussed, implies that the error dynamics are an eventual contraction.

For this experiment, we chose Lipschitz interpolation with a fixed Lipschitz
constant $L=11$ which is a Lipschitz constant of the true dynamics. To learn
$f$ the Lipschitz interpolator had access to acceleration corrupted by
uniformly distributed noise drawn i.i.d. from the interval [-2,2] given a
performance example in a relatively low signal-to-noise ration setting.
Starting in initial state $x_{0}=[-2.,-1.]$, the controller was given a set-
point reference $\xi_{n}=[2\pi,0],\forall n\in\mathbb{N}$. An example run of
the controller as well as empirical measurements of the tracking dynamics
across 30 trials of the experiments for different noise realisations are given
in Figure 4. Note, consistent with our theory, the plots show how the tracking
error appears to vanish in the mean (and in fact for all realisations).

Before we conclude, we will need to point out some limitations to the online
control application given in this section:

###### Remark 22

Firstly, our example assumed knowledge of the Lipschitz constant. While not an
uncommon assumption, we recognise that having to know the true Lipschitz
constant is a practical limitation. Therefore methods such as LACKI (Calliess
et al. (2020)) or POKI (Calliess (2017)) could also be employed to incorporate
full black-box learning. Our example however, merely serves as a simple
illustration of our currently developed theory. Secondly, we assumed that
states were observable but that only accelerations were noisy.

Extending our results to learning-based control settings that involve
Lipschitz constant parameter estimation and extending the theory to realistic
settings of noisy state observations would, in our opinion, be an interesting
direction to investigate in future work.

##  7 Conclusion

In conclusion, this paper has provided a comprehensive investigation into the
asymptotic convergence properties of general Lipschitz interpolation methods
in the presence of bounded stochastic noise. Through our analysis, we have
established probabilistic consistency guarantees for the classical approach
within a broad context. Furthermore, by deriving upper bounds on the uniform
convergence rates, we have aligned these bounds with the well-established
optimal rates of non-parametric regression observed in similar settings. These
rates provide a precise characterisation of the impact of the behaviour of the
noise at the boundary of its support on the non-parametric uniform convergence
rates and are, as far as the authors of this paper are aware, novel to the
literature.

These established bounds can also serve as useful tools for the comparative
asymptotic assessment of Lipschitz interpolation against alternative non-
parametric regression techniques determining the circumstances under which
Lipschitz interpolation frameworks can be anticipated to be asymptotically
better or worse. In particular, an explicit condition on the noise’s behaviour
at the boundary of its support can be utilised to predict this out-or under-
performance.

Extending our work, we have expanded our asymptotic results to consider online
learning in discrete-time stochastic systems. The additional consistency
guarantees we provide in this context carry practical significance, as we show
how they can be utilised to establish closed-loop stability assurances for a
simple online learning-based controller in the setting of model reference
adaptive control. We note that these asymptotic results also hold for the
worst-case upper and lower bounds provided by the ceiling and floor predictors
of the Lipschitz interpolation framework. This implies that even the most
conservative adaptive controllers relying on worst-case bounds of Lipschitz
interpolation methods will consider the true underlying dynamics in the long
run.

Finally, we have provided a brief theoretical study of the fully data-driven
LACKI framework (Calliess et al. (2020)) which extends classical Lipschitz
interpolation by incorporating a Lipschitz constant estimation mechanism into
the algorithm. We show asymptotic consistency of both the Lipschiz constant
estimation method and the extended framework which can serve to further
theoretically motivate the use of the LACKI in practice.

Two research avenues are of interest with respect to the theoretical results
derived in this paper. The first would be the derivation of lower bounds on
the non-parametric convergence rates under the same settings and assumptions
as the ones utilised in Theorem 7. These would, ideally but not unexpectedly,
given existing results on the optimal convergence rates of non-parametric
boundary regression by Jirak et al. (2014), demonstrate the optimality of the
upper bounds on the non-parametric convergence rates developed in this paper.
The second potential research direction would be to extend the convergence
rate upper bounds stated in Theorem 7 such that they hold for the practical
and fully data-driven extensions of Lipschitz interpolation such as LACKI
(Calliess et al. (2020)) or POKI Calliess (2017).

## References

  * Åström and Wittenmark (2013) Karl J Åström and Björn Wittenmark.  _Adaptive control_.  Courier Corporation, 2013.
  * Bachoc et al. (2021) François Bachoc, Tom Cesari, and Sébastien Gerchinovitz.  Instance-dependent bounds for zeroth-order Lipschitz optimization with error certificates.  _Advances in Neural Information Processing Systems_ , 34:24180–24192, 2021.
  * Beliakov (2006) Gleb Beliakov.  Interpolation of Lipschitz functions.  _Journal of computational and applied mathematics_ , 196(1):20–44, 2006.
  * Blaas et al. (2019) Arno Blaas, Jose Maria Manzano, Daniel Limon, and Jan Calliess.  Localised kinky inference.  In _2019 18th European Control Conference (ECC)_ , pages 985–992. IEEE, 2019.
  * Calliess (2017) Jan-Peter Calliess.  Lipschitz optimisation for Lipschitz interpolation.  In _2017 American Control Conference (ACC)_ , pages 3141–3146. IEEE, 2017.
  * Calliess et al. (2020) Jan-Peter Calliess, Stephen J Roberts, Carl Edward Rasmussen, and Jan Maciejowski.  Lazily adapted constant kinky inference for nonparametric regression and model-reference adaptive control.  _Automatica_ , 122:109216, 2020.
  * Canale et al. (2014) M Canale, L Fagiano, and MC Signorile.  Nonlinear model predictive control from data: a set membership approach.  _International Journal of Robust and Nonlinear Control_ , 24(1):123–139, 2014.
  * Canale et al. (2007) Massimo Canale, Lorenzo Fagiano, and Mario Milanese.  Power kites for wind energy generation [applications of control].  _IEEE Control Systems Magazine_ , 27(6):25–38, 2007.
  * Chowdhary et al. (2013) Girish Chowdhary, Hassan A Kingravi, Jonathan P How, and Patricio A Vela.  A Bayesian nonparametric approach to adaptive control using Gaussian processes.  In _52nd IEEE Conference on Decision and Control_ , pages 874–879. IEEE, 2013.
  * Drees et al. (2019) Holger Drees, Natalie Neumeyer, and Leonie Selk.  Estimation and hypotheses testing in boundary regression models.  _Bernoulli_ , 25(1):424 – 463, 2019.  doi: 10.3150/17-BEJ992.
  * Györfi et al. (2002) László Györfi, Michael Köhler, Adam Krzyżak, and Harro Walk.  _A distribution-free theory of nonparametric regression_ , volume 1.  Springer, 2002.
  * Hall and Van Keilegom (2009) Peter Hall and Ingrid Van Keilegom.  Nonparametric “regression” when errors are positioned at end-points.  _Bernoulli_ , 15(3):614–633, 2009.
  * Hasselblatt and Katok (2003) Boris Hasselblatt and Anatole Katok.  _A first course in dynamics: with a panorama of recent developments_.  Cambridge University Press, 2003.
  * Hewing et al. (2019) Lukas Hewing, Juraj Kabzan, and Melanie N Zeilinger.  Cautious model predictive control using Gaussian process regression.  _IEEE Transactions on Control Systems Technology_ , 28(6):2736–2743, 2019.
  * Hu et al. (2020) Yichun Hu, Nathan Kallus, and Xiaojie Mao.  Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes.  In _Conference on Learning Theory_ , pages 2007–2010. PMLR, 2020\.
  * Huang et al. (2023) Julien Walden Huang, Stephen J. Roberts, and Jan-Peter Calliess.  On the sample complexity of Lipschitz constant estimation.  _Transactions on Machine Learning Research_ , 2023.  ISSN 2835-8856.  URL https://openreview.net/forum?id=UIalYAHdBH.  Featured Certification.
  * Ibragimov and Has’ Minskii (2013) Ildar Abdulovich Ibragimov and Rafail Zalmanovich Has’ Minskii.  _Statistical estimation: asymptotic theory_ , volume 16.  Springer Science & Business Media, 2013.
  * Jirak et al. (2014) Moritz Jirak, Alexander Meister, and Markus Reiss.  Adaptive function estimation in nonparametric regression with one-sided errors.  _The Annals of Statistics_ , pages 1970–2002, 2014.
  * Limanond and Tsakllis (2000) S. Limanond and K.S. Tsakllis.  Model reference adaptive and nonadaptive control of linear time-varying plants.  _IEEE Transactions on Automatic Control_ , 45(7):1290–1300, 2000.  doi: 10.1109/9.867022.
  * Ljung (2010) Lennart Ljung.  Perspectives on system identification.  _Annual Reviews in Control_ , 34(1):1–12, 2010\.
  * Maddalena and Jones (2020) Emilio T Maddalena and Colin N Jones.  Learning non-parametric models with guarantees: A smooth Lipschitz regression approach.  _IFAC-PapersOnLine_ , 53(2):965–970, 2020.
  * Malherbe and Vayatis (2017) Cédric Malherbe and Nicolas Vayatis.  Global optimization of Lipschitz functions.  In _International Conference on Machine Learning_ , pages 2314–2323. PMLR, 2017.
  * Manzano et al. (2020) José María Manzano, Daniel Limon, David Muñoz de la Peña, and Jan-Peter Calliess.  Robust learning-based MPC for nonlinear constrained systems.  _Automatica_ , 117:108948, 2020.
  * Manzano et al. (2021) José María Manzano, David Munoz de la Pena, Jan-Peter Calliess, and Daniel Limon.  Componentwise Hölder inference for robust learning-based MPC.  _IEEE Transactions on Automatic Control_ , 66(11):5577–5583, 2021.
  * Manzano et al. (2022) Jose Maria Manzano, David Muñoz de la Peña, and Daniel Limon.  Input-to-state stable predictive control based on continuous projected kinky inference.  _International Journal of Robust and Nonlinear Control_ , 2022.
  * Meister and Reiß (2013) Alexander Meister and Markus Reiß.  Asymptotic equivalence for nonparametric regression with non-regular errors.  _Probability Theory and Related Fields_ , 155:201–229, 2013\.
  * Milanese and Novara (2004) Mario Milanese and Carlo Novara.  Set membership identification of nonlinear systems.  _Automatica_ , 40(6):957–975, 2004.
  * Monahemi and Krstic (1996) Mogen M Monahemi and Miroslav Krstic.  Control of wing rock motion using adaptive feedback linearization.  _Journal of guidance, control, and dynamics_ , 19(4):905–912, 1996.
  * Müller and Wefelmeyer (2010) Ursula U Müller and Wolfgang Wefelmeyer.  Estimation in nonparametric regression with non-regular errors.  _Communications in Statistics—Theory and Methods_ , 39(8-9):1619–1629, 2010.
  * Nadaraya (1964) Elizbar A Nadaraya.  On estimating regression.  _Theory of Probability & Its Applications_, 9(1):141–142, 1964.
  * Novara et al. (2013) Carlo Novara, Lorenzo Fagiano, and Mario Milanese.  Direct feedback control design for nonlinear systems.  _Automatica_ , 49(4):849–860, 2013.
  * Sanner and Slotine (1991) Robert M Sanner and Jean-Jacques E Slotine.  Gaussian networks for direct adaptive control.  In _1991 American control conference_ , pages 2153–2159. IEEE, 1991\.
  * Schoukens and Ljung (2019) Johan Schoukens and Lennart Ljung.  Nonlinear system identification: A user-oriented road map.  _IEEE Control Systems Magazine_ , 39(6):28–99, 2019.
  * Seeger et al. (2008) Matthias W Seeger, Sham M Kakade, and Dean P Foster.  Information consistency of nonparametric Gaussian process methods.  _IEEE Transactions on Information Theory_ , 54(5):2376–2382, 2008.
  * Selk et al. (2022) Leonie Selk, Charles Tillier, and Orlando Marigliano.  Multivariate boundary regression models.  _Scandinavian Journal of Statistics_ , 49(1):400–426, 2022.
  * Stone (1982) Charles J Stone.  Optimal global rates of convergence for nonparametric regression.  _The annals of statistics_ , pages 1040–1053, 1982.
  * Stone (1994) Charles J Stone.  The use of polynomial splines and their tensor products in multivariate function estimation.  _The annals of statistics_ , 22(1):118–171, 1994\.
  * Strongin (1973) RG Strongin.  On the convergence of an algorithm for finding a global extremum.  _Engineering Cybernetics_ , 11(4):549–555, 1973\.
  * Tsybakov (2004) Alexandre B Tsybakov.  Introduction to nonparametric estimation, 2009.  _URL https://doi. org/10.1007/b13794. Revised and extended from the_ , 9(10), 2004.
  * Van Der Vaart and Van Zanten (2011) Aad Van Der Vaart and Harry Van Zanten.  Information rates of nonparametric Gaussian process methods.  _Journal of Machine Learning Research_ , 12(6), 2011.
  * van der Vaart and van Zanten (2008) AW van der Vaart and JH van Zanten.  Rates of contraction of posterior distributions based on Gaussian process priors.  _Annals of Statistics_ , 36(3):1435–1463, 2008\.
  * Williams and Rasmussen (2006) Christopher KI Williams and Carl Edward Rasmussen.  _Gaussian processes for machine learning_ , volume 2.  MIT press Cambridge, MA, 2006.
  * Wu (2017) Yihong Wu.  Lecture notes on information-theoretic methods for high-dimensional statistics.  _Lecture Notes for ECE598YW (UIUC)_ , 16, 2017.
  * Wynne et al. (2021) George Wynne, François-Xavier Briol, and Mark Girolami.  Convergence guarantees for Gaussian process means with misspecified likelihoods and smoothness.  _The Journal of Machine Learning Research_ , 22(1):5468–5507, 2021.
  * Yang et al. (2017) Yun Yang, Anirban Bhattacharya, and Debdeep Pati.  Frequentist coverage and sup-norm convergence rate in Gaussian process regression.  _arXiv preprint arXiv:1708.04753_ , 2017.

##  A Additional Results (Convergence rate of tracking error)

We provide the theoretical convergence rates obtained for the tracking error
in the application to online learning-based control. As noted in Section 6,
this result is not generally applicable as verification of the ”regular
sampling” condition defined in Definition 10 is difficult to do in practice.

###### Corollary 23

Assume that the setting and assumptions of Corollary 18 hold. Assume
furthermore that the stochastic control law
$u_{n+1}:=u(x_{n},\hat{f}_{n},\mathcal{D}_{n})$ is defined such that
$(x_{n})_{n\in\mathbb{N}}$ is regularly sampled on a set
$\bar{}\mathcal{X}\subset\mathcal{X}$ that satisfies Assumption 4 and that the
noise vectors $(\epsilon_{n})_{n\in\mathbb{N}}$ are component-wise
independent. Then,

$\limsup_{n\to\infty}\mathbb{E}[a_{n}^{-1}\left\|f(x_{n+1})-\hat{f}_{n}(x_{n+1})\right\|_{\mathcal{Y}}]<\infty.$

where
$(a_{n})_{n\in\mathbb{N}}:=((n^{-1}log(n))^{\frac{\alpha}{d+\eta\alpha}})_{n\in\mathbb{N}}$.

Proof (sketch) Applying the same arguments as in the proof of Lemma 18, it is
sufficient to consider: $\forall j\in\\{1,...,l\\}$

$\limsup_{n\to\infty}\mathbb{E}[a_{n}^{-1}|f^{j}(x_{n+1})-\hat{f}^{j}_{n}(x_{n+1})|].$

Since the noise is component-wise independent, we can apply the arguments
utilised in the proof of Corollary 11 for all $j\in\\{1,...,l\\}$ and conclude
the proof.

###### Theorem 24

Assume the settings and assumptions of Theorem 19 hold. If the stochastic
control law $u_{n+1}:=u(x_{n},\hat{f}_{n},\mathcal{D}_{n})$ is such that
$(x_{n})_{n\in\mathbb{N}}$ is regularly sampled on a set
$\bar{}\mathcal{X}\subset\mathcal{X}$ that satisfies Assumption 4 and the
noise vectors $(\epsilon_{n})_{n\in\mathbb{N}}$ are component-wise
independent. Then,

$\limsup_{n\to\infty}\mathbb{E}[a_{n}^{-1}\left\|e_{n}-e_{*}\right\|_{\mathcal{Y}}]<\infty$

where
$(a_{n})_{n\in\mathbb{N}}:=((n^{-1}log(n))^{\frac{\alpha}{d+\eta\alpha}})_{n\in\mathbb{N}}$.

Proof (sketch) Follows from applying the proof of Theorem 19 and noting that
the slowest converging term at the end of the proof is given by

$\frac{1}{1-\lambda_{\phi}}\max_{i=0,...,n-1}\mathbb{E}[\left\|d_{m_{0}+i}\right\|_{\mathcal{Y}}].$

This term can be upper bounded by applying Corollary 23 which therefore
provides the convergence rate and concludes the proof.

##  B Proof of Theorem 7

Proof  From the proof of Theorem 4, we have $\forall f\in
Lip(L^{*},\,\mathfrak{d})$, $x\in\mathcal{X}$,

$|\hat{f}_{n}(x)-f(x)|$
$\leq\max\Big{\\{}\min_{i=1,...,N_{n}}\\{\frac{e_{i}}{2}+\frac{L^{*}+L}{2}\,\mathfrak{d}(x,s_{i})\\}+\max_{i=1,...,N_{n}}\\{\frac{e_{i}}{2}\\},$
$-\min_{i=1,...,N_{n}}\\{\frac{e_{i}}{2}\\}-\max\limits_{i=1,...,N_{n}}\\{\frac{e_{i}}{2}-\frac{L^{*}+L}{2}\,\mathfrak{d}(x,s_{i})\\}\Big{\\}}.$

Consider the minimal covering of $\mathcal{X}$ of radius
$R_{n}:=a_{n}=\left(n^{-1}log(n)\right)^{\frac{\alpha}{d+\eta\alpha}}$ with
respect to $\,\mathfrak{d}$ denoted $Cov(R_{n})$ and the associated set of
hyperballs; $\mathcal{B}_{n}$. Assuming that $n$ is large enough such that
every hyperball in $\mathcal{B}_{n}$ contains at least one input of
$G_{n}^{\mathcal{X}}$, we have that the following upper bound holds:

$|\hat{f}_{n}(x)-f(x)|$ $\leq\max\left\\{\min_{s_{i}\in B^{x}\cap
G_{n}^{\mathcal{X}}}\\{\frac{e(s_{i})}{2}\\},\min_{s_{i}\in B^{x}\cap
G_{n}^{\mathcal{X}}}\\{-\frac{e(s_{i})}{2}\\}\right\\}+\frac{\bar{\mathfrak{e}}}{2}+(L^{*}+L)R_{n}$

where with abuse of notation, $e(s_{i})$ denotes the noise variable associated
with the input $s_{i}$ and $B^{x}\in\mathcal{B}_{n}$ such that $x\in B$. For
all $n\in\mathbb{N}$, we define the following random variable and event

$\displaystyle A_{n}$
$\displaystyle:=\max_{B\in\mathcal{B}_{n}}\max\left\\{\min_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}\\{\frac{e(s_{i})}{2}\\},-\max_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}\\{\frac{e(s_{i})}{2}\\}\right\\}+\frac{\bar{\mathfrak{e}}}{2}$
$\displaystyle E_{n}$ $\displaystyle:=\left\\{\forall
B\in\mathcal{B}_{n},|\\{i\in[n]\\},s_{i}\in B\\}|>0\right\\}.$

Then, from ($\star$) given at the end of the proof we have that it is
sufficient to consider

$\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}\mathbb{E}\left[a_{n}^{-1}\left\|\hat{f}_{n}-f\right\|_{\infty}\Big{|}E_{n}\right]\mathbb{P}(E_{n})$

in order for Theorem 7 to hold. For $n\in\mathbb{N}$ sufficiently large such
that $\mathbb{P}(E_{n})>0$ (see ($\star$)), we can apply the upper bound on
$|\hat{f}_{n}(x)-f(x)|$ derived above:

$\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}\mathbb{E}\left[a_{n}^{-1}\left\|\hat{f}_{n}-f\right\|_{\infty}\Big{|}E_{n}\right]=\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}\mathbb{E}\left[a_{n}^{-1}\sup_{x\in\mathcal{X}}|f_{n}(x)-f(x)|\Big{|}E_{n}\right]$
$\leq a_{n}^{-1}\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}\mathbb{E}\left[\sup_{x\in\mathcal{X}}\max\left\\{\min_{s_{i}\in
B^{x}\cap G_{n}^{\mathcal{X}}}\\{\frac{e(s_{i})}{2}\\},\min_{s_{i}\in
B^{x}\cap
G_{n}^{\mathcal{X}}}\\{-\frac{e(s_{i})}{2}\\}\right\\}+\frac{\bar{\mathfrak{e}}}{2}+(L^{*}+L)R_{n}\Big{|}E_{n}\right]$
$=a_{n}^{-1}(L^{*}+L)R_{n}+\mathbb{E}\left[a_{n}^{-1}\max_{B\in\mathcal{B}_{n}}\max\left\\{\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}\\{\frac{e(s_{i})}{2}\\},\min_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}\\{-\frac{e(s_{i})}{2}\\}\right\\}+\frac{\bar{\mathfrak{e}}}{2}\Big{|}E_{n}\right]$
$=(L^{*}+L)a_{n}^{-1}R_{n}+\mathbb{E}\left[a_{n}^{-1}A_{n}\Big{|}E_{n}\right].$

By definition of $R_{n}$, the first term: $(L^{*}+L)a_{n}^{-1}R_{n}=(L^{*}+L)$
is bounded for all $n\in\mathbb{N}$. We can therefore focus on upper bounding
the second term:

$\mathbb{E}\left[a_{n}^{-1}A_{n}\Big{|}E_{n}\right]\mathbb{P}(E_{n})=\mathbb{E}\left[a_{n}^{-1}A_{n}\right].$

Using $0\leq A_{n}\leq 2\bar{\mathfrak{e}}$ with probability 1, we have
$\forall C_{0}>0$,

$a_{n}^{-1}A_{n}\leq C_{0}1_{\\{a_{n}^{-1}A_{n}\leq
C_{0}\\}}+2\bar{\mathfrak{e}}a_{n}^{-1}1_{\\{a_{n}^{-1}A_{n}>C_{0}\\}}$

with probability $1$. This implies that

$\mathbb{E}[a_{n}^{-1}A_{n}]\leq
C_{0}+2\bar{\mathfrak{e}}a_{n}^{-1}\mathbb{P}(A_{n}>C_{0}a_{n}).$

It is therefore sufficient to show that $\exists C_{0}>0$ such that

$\limsup_{n\to\infty}\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}a_{n}^{-1}\mathbb{P}(A_{n}>C_{0}a_{n})<\infty.$

We have

$\mathbb{P}(A_{n}>C_{0}a_{n})=1-\mathbb{P}(\forall
B\in\mathcal{B}_{n}:\min_{s_{i}\in B\cap G_{n}^{\mathcal{X}}}e(s_{i})\in
I_{1},\max_{s_{i}\in B\cap G_{n}^{\mathcal{X}}}e(s_{i})\in I_{2})$
$\stackrel{{\scriptstyle(\star\star)}}{{\leq}}1-\prod_{B\in\mathcal{B}_{n}}\mathbb{P}\left(\min_{s_{i}\in
B\cap G_{n}^{\mathcal{X}}}e(s_{i})\in I_{1},\max_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e(s_{i})\in I_{2}\right)$ $\leq
1-\mathbb{P}\left(\min_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in
I_{1},\max_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in
I_{2}\right)^{|\mathcal{B}_{n}|}$

where $I_{1}:=[-\bar{\mathfrak{e}},-\bar{\mathfrak{e}}+2C_{0}a_{n})$,
$I_{2}:=(\bar{\mathfrak{e}}-2C_{0}a_{n},\bar{\mathfrak{e}}]$ and
$N_{\mathcal{B}_{n}}:=\min_{B\in\mathcal{B}_{n}}|B\cap G_{n}^{\mathcal{X}}|$.
The second to last inequality follows from arguments given in $(\star\star)$
provided at the end of the proof. For $n$ large enough such that
$2C_{0}a_{n}<\bar{\epsilon}$, we can apply Assumption 2 to simplify the left
hand expression as follows;

$\mathbb{P}\left(\min_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in
I_{1},\max_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in I_{2}\right)$
$\geq\mathbb{P}\left(\min_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in
I_{1}\right)\cdot\mathbb{P}\left(\max_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in
I_{2}|\min_{i\in 1,...,N_{\mathcal{B}_{n}}}e_{i}\in I_{1}\right)$
$\geq\left(1-\left(1-\gamma(2C_{0}a_{n})^{\eta}\right)^{N_{\mathcal{B}_{n}}}\right)\left(1-\left(1-\gamma(2C_{0}a_{n})^{\eta}\right)^{N_{\mathcal{B}_{n}}-1}\right)$
$\geq\left(1-2\left(1-\gamma(2C_{0}a_{n})^{\eta}\right)^{N_{\mathcal{B}_{n}}-1}\right)^{2}.$

Therefore, we have

$\sup_{f\in Lip(L^{*},\,\mathfrak{d})}a_{n}^{-1}\mathbb{P}(A_{n}>C_{0}a_{n})$
$\leq
a_{n}^{-1}\left(1-\left(1-2(1-\gamma(2C_{0}a_{n})^{\eta})^{N_{\mathcal{B}_{n}}-1}\right)^{2|\mathcal{B}_{n}|}\right).$
$\leq
a_{n}^{-1}\left(1-\left(1-2(1-\gamma(2C_{0}a_{n})^{\eta})^{N_{\mathcal{B}_{n}}-1}\right)^{\frac{C_{1}}{{a_{n}}^{\frac{d}{\alpha}}}}\right).$

where we used the fact that there exists a constant $C_{1}>0$ (that can depend
on $d$) such that
$2|\mathcal{B}_{n}|\leq\frac{C_{1}}{{R_{n}}^{\frac{d}{\alpha}}}=\frac{C_{1}}{{a_{n}}^{\frac{d}{\alpha}}}$
which is a modification of (Wu (2017), Theorem 14.2) that follows from the
assumed convexity of $\mathcal{X}$. By Lemma 26, in order for the above
expression to be bounded, it is sufficient that
$2(1-\gamma(2C_{0}a_{n})^{\eta})^{N_{\mathcal{B}_{n}}-1}$ behaves like
$C_{2}^{\prime}{a_{n}}^{({\frac{d}{\alpha}}+1)}$ for an arbitrary
$C_{2}^{\prime}>0$ as $n$ goes to infinity. More precisely, let
$C_{2}^{\prime}=1$, it is sufficient to have:

$2(1-\gamma(2C_{0}a_{n})^{\eta})^{N_{\mathcal{B}_{n}}-1}\leq{a_{n}}^{({\frac{d}{\alpha}}+1)}$
$\iff N_{\mathcal{B}_{n}}\geq
1+({\frac{d}{\alpha}}+1)\frac{\log\left(a_{n}\right)}{\log\left(1-\gamma(2C_{0}a_{n})^{\eta}\right)}$

as $n$ goes to infinity. The right-hand expression can be re-expressed as the
series expansion:

$\frac{d+\alpha}{\alpha\gamma(2C_{0})^{\eta}}\frac{1}{{a_{n}}^{\eta}}\log(\frac{1}{a_{n}})+O(\log(\frac{1}{a_{n}}))$

as $a_{n}$ goes to $0$. Therefore, for any
$C_{2}>\frac{d+\alpha}{\alpha\gamma(2C_{0})^{\eta}}$ and $n>0$ large enough,
we have
$1+({\frac{d}{\alpha}}+1)\frac{\log(a_{n})}{\log(1-\gamma(2C_{0}a_{n})^{\eta})}<C_{2}\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}$
and it suffices to have

$N_{\mathcal{B}_{n}}\geq C_{2}\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}$

as $n$ goes to infinity in order for $\lim_{n\to\infty}\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}a_{n}^{-1}\mathbb{P}(A_{n}>C_{0}a_{n})$ to be
bounded:
If $N_{\mathcal{B}_{n}}\geq
C_{2}\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}$,

$\limsup_{n\to\infty}\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}a_{n}^{-1}\mathbb{P}(A_{n}>C_{0}a_{n})\leq
a_{n}^{-1}\left(1-\left(1-{a_{n}}^{({\frac{d}{\alpha}}+1)}\right)^{\frac{C_{1}}{{a_{n}}^{\frac{d}{\alpha}}}}\right)\leq
2C_{1}$

where the last inequality follows from Lemma 26.

Therefore, the final step of the proof is to show that
$N_{\mathcal{B}_{n}}\geq C_{2}\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}$
occurs with a probability that converges to $1$ at a rate of $a_{n}$ as n goes
to infinity.

More precisely, let $n\in\mathbb{N}$ and fix an arbitrary constant
$C_{2}>\frac{d+\alpha}{\alpha\gamma(2C_{0})^{\eta}}$ based on the condition
given above (note that $C_{0}>0$ can be set arbitrarily large).

$S_{n}:=\left\\{\forall B\in\mathcal{B}_{n}:\text{ }|\\{i\in[n]\\},s_{i}\in
B\\}|>C_{2}\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}\right\\}$

i.e. the event that there is more than
$C_{2}\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}$ queries in each hyperball
in $\mathcal{B}_{n}$. Utilising the asymptotic bound developed in the first
part of the proof, we have by the law of total probability:

$\limsup_{n\to\infty}\mathbb{E}[a_{n}^{-1}A_{n}]\leq
C_{0}+2\bar{\mathfrak{e}}\limsup_{n\to\infty}a_{n}^{-1}\mathbb{P}(A_{n}>C_{0}a_{n})$
$\leq
C_{0}+2\bar{\mathfrak{e}}\limsup_{n\to\infty}a_{n}^{-1}\left(\mathbb{P}(A_{n}>C_{0}a_{n}|S_{n})+\mathbb{P}(S_{n}^{c})\right)\leq
C_{0}+4\bar{\mathfrak{e}}C_{1}+\limsup_{n\to\infty}a_{n}^{-1}\mathbb{P}(S_{n}^{c})$

where the last inequality can be obtained by applying Lemma 26.

To conclude the proof, we need to show that
$\limsup_{n\to\infty}a_{n}^{-1}\mathbb{P}(S_{n}^{c})$ is bounded. We have
(denoting $b_{n}:=\log(\frac{1}{a_{n}})\frac{1}{{a_{n}}^{\eta}}$ to alleviate
notation):

$\mathbb{P}(S_{n})=\mathbb{P}\left(\forall
B\in\mathcal{B}_{n}:|\\{i\in[n]\\},s_{i}\in B\\}|>C_{2}b_{n}\right)$
$\geq\prod_{B\in\mathcal{B}_{n}}\mathbb{P}\left(|\\{i\in[\left\lfloor\frac{n}{2}\right\rfloor]\\},s_{i}\in
B\\}|>C_{2}b_{n}\right)$
$\geq\prod_{B\in\mathcal{B}_{n}}\left(1-\mathbb{P}\left(|\\{i\in[\left\lfloor\frac{n}{2}\right\rfloor]\\},s_{i}\in
B\\}|\leq C_{2}b_{n}\right)\right)$

where the first inequality stated above follows from $(\star\star\star)$
(shown at the end of the proof) for $n\in\mathbb{N}$ if $C_{2}$ satisfies the
condition: $C_{2}\leq\frac{d+\eta\alpha}{2C_{1}\alpha}$ where
$C_{1},d,\alpha,\eta$ are constants.

Then, Assumption 4 on $\mathcal{X}$ implies that there
$r_{0}>0,\theta\in(0,1]$ such that $\forall x\in\mathcal{X}$,
$r\in\left(0,r_{0}\right),\operatorname{vol}\left(B_{r}(x)\cap\mathcal{X}\right)\geq\theta\operatorname{vol}\left(B_{r}(x)\right)$.
Therefore, for all $n\in\mathbb{N}$ such that $R_{n}<r_{0}$, we have that
Assumption 4 can be applied to $B\in\mathcal{B}_{n}$. Using Assumption 5, we
have that the random variable defined by
$|\\{i\in[\left\lfloor\frac{n}{2}\right\rfloor]\\},s_{i}\in B\\}|$ follows a
binomial distribution with a success probability $p$ that can be lower bounded
by
$C_{3}^{\prime}\frac{vol(B)}{vol(\mathcal{X})}=C_{3}^{\prime\prime}a_{n}^{\frac{d}{\alpha}}$
for $C_{3}^{\prime},C_{3}^{\prime\prime}>0$ and with expectation:

$\mathbb{E}\left[|\\{i\in[\left\lfloor\frac{n}{2}\right\rfloor]\\},s_{i}\in
B\\}|\right]=\left\lfloor\frac{n}{2}\right\rfloor
p\geq\frac{C_{3}^{\prime\prime}}{3}n^{\frac{\eta\alpha}{\eta\alpha+d}}\log(n)^{\frac{d}{d+\eta\alpha}}=C_{3}n^{\frac{\eta\alpha}{\eta\alpha+d}}\log(n)^{\frac{d}{d+\eta\alpha}}$

where $C_{3}:=\frac{C_{3}^{\prime\prime}}{3}$. (Note: the ”$3$” denominator
was arbitrarily selected in order to remove the ceiling operator in the above
equation).

As the only condition on $C_{2}$ is given by the bound
$C_{2}>\frac{d+\alpha\xi}{\alpha\gamma(2C_{0})^{\eta}}$, $C_{2}$ can be set
arbitrarily small as $C_{0}$ can be set arbitrarily large. Therefore, there
exists $C_{0}>0$, $C_{2}>0$ such that
$C_{2}\leq\min\\{\frac{d+\eta\alpha}{2C_{1}\alpha},\frac{C_{3}(d+\eta\alpha)}{\alpha}\\}$
which implies that $(\star\star\star)$ holds and that:

$C_{2}b_{n}=C_{2}\left(\frac{\alpha}{d+\eta\alpha}\right)\log\left(\frac{n}{\log{(n)}}\right)\left(\frac{n}{\log(n)}\right)^{\frac{\eta\alpha}{\eta\alpha+d}}$
$\leq
C_{2}\left(\frac{\alpha}{d+\eta\alpha}\right)n^{\frac{\eta\alpha}{\eta\alpha+d}}\log(n)^{\frac{d}{d+\eta\alpha}}\leq
C_{3}n^{\frac{\eta\alpha}{\eta\alpha+d}}\log(n)^{\frac{d}{d+\eta\alpha}}\leq\frac{\mathbb{E}[|\\{i\in[n]\\},s_{i}\in
B\\}|]}{2}.$

This last relation implies that we can apply Lemma 1 of Stone (1982) to obtain
the upper bound:

$\mathbb{P}\left(|\\{i\in[n]\\},s_{i}\in B\\}|\leq
C_{2}b_{n}\right)\leq\mathbb{P}\left(|\\{i\in[n]\\},s_{i}\in
B\\}|\leq\frac{\mathbb{E}\left[|\\{i\in[n]\\},s_{i}\in
B\\}|\right]}{2}\right)$
$\leq\left(\frac{2}{e}\right)^{\frac{\mathbb{E}[|\\{i\in[n]\\},s_{i}\in
B\\}|]}{2}}$

which in turn implies

$\left(1-\mathbb{P}\left(|\\{i\in[n]\\},s_{i}\in B\\}|\leq
C_{2}b_{n}\right)\right)^{|\mathcal{B}_{n}|}\geq\left(1-\left(\frac{2}{e}\right)^{\frac{\mathbb{E}[|\\{i\in[n]\\},s_{i}\in
B\\}|]}{2}}\right)^{|\mathcal{B}_{n}|}.$

Plugging this expression back into
$\limsup_{n\to\infty}a_{n}^{-1}\mathbb{P}(S_{n}^{c})$, we obtain

$a_{n}^{-1}\mathbb{P}\left(S_{n}^{c}\right)\leq
a_{n}^{-1}\left(1-\left(1-(\frac{2}{e})^{\frac{\mathbb{E}[|\\{i\in[n]\\},s_{i}\in
B\\}|]}{2}}\right)^{|\mathcal{B}_{n}|}\right).$ $\leq
a_{n}^{-1}\left(1-\left(1-(\frac{2}{e})^{\frac{C_{3}}{2}n^{\frac{\eta\alpha}{\eta\alpha+d}}\log(n)^{\frac{d}{d+\eta\alpha}}}\right)^{C_{1}{a_{n}}^{\frac{d}{\alpha}}}\right)$

which converges to $0$ as $n$ goes infinity and concludes the proof (follows
from the exponential speed of convergence of
$(\frac{2}{e})^{\frac{C_{3}}{2}n^{\frac{\eta\alpha}{\eta\alpha+d}}\log(n)^{\frac{d}{d+\eta\alpha}}}$).

($\star$) For completeness we revisit the assumption made in the proof. Recall
for all $n\in\mathbb{N}$,

$E_{n}:=\left\\{\forall B\in\mathcal{B}_{n},|\\{i\in[n]\\},s_{i}\in
B\\}|>0\right\\}.$

Then, by law of total expectation, we have $\forall f\in
Lip(L^{*},\,\mathfrak{d})$, $n\in\mathbb{N}$ sufficiently large such that
$\mathbb{P}(E_{n})>0$ (which exists since
$\mathbb{P}(E_{n})>\mathbb{P}(S_{n})\overset{n\to\infty}{\rightarrow}1$ );

$\mathbb{E}[a_{n}^{-1}\left\|\hat{f}_{n}-f\right\|_{\infty}]$
$=a_{n}^{-1}(\mathbb{E}\left[\left\|\hat{f}_{n}-f\right\|_{\infty}\Big{|}E_{n}\right]\mathbb{P}(E_{n})+\mathbb{E}\left[\left\|\hat{f}_{n}-f\right\|_{\infty}\Big{|}E_{n}^{c}\right]\mathbb{P}(E_{n}^{c})).$

For all $n\geq 1$, $f\in Lip(L^{*},\,\mathfrak{d})$ and any sampling procedure
$\mathcal{D}_{n}$, $\left\|\hat{f}_{n}-f\right\|_{\infty}$ is uniformly
bounded with probability $1$. More precisely, we have $\sup_{f\in
Lip(L^{*},\,\mathfrak{d})}\left\|\hat{f}_{n}-f\right\|_{\infty}$ $\leq
2\bar{\mathfrak{e}}+2L\delta_{\,\mathfrak{d}}(\mathcal{X})$ where
$\delta_{\,\mathfrak{d}}(\mathcal{X}):=\sup_{x,x^{\prime}\in\mathcal{X}}\,\mathfrak{d}(x,x^{\prime})$
with probability $1$ which follows from $f\in Lip(L^{*},\,\mathfrak{d})$ and
by the design of the Lipschitz interpolation framework. This bound is finite
by the assumed compactness of $\mathcal{X}$. Therefore, denoting
$K:=2\bar{\mathfrak{e}}+2L\delta_{\,\mathfrak{d}}(\mathcal{X})$, we have that
the above statement is upper bounded by

$\mathbb{E}\left[a_{n}^{-1}\left\|\hat{f}_{n}-f\right\|_{\infty}\Big{|}E_{n}\right]\mathbb{P}(E_{n})+a_{n}^{-1}K\mathbb{P}(E_{n}^{c}).$

The first term is equal to the simplified expression assumed earlier in the
proof and the second term converges to 0 since
$\mathbb{P}(E_{n}^{c})\leq\mathbb{P}(S_{n}^{c})$ and
$\lim_{n\to\infty}a_{n}^{-1}\mathbb{P}(S_{n}^{c})=0$ as shown above.

($\star\star$) For all $B\in\mathcal{B}_{n}$, let $E(B)$ denote the event

$E(B):=\left\\{\min_{s_{i}\in B\cap G_{n}^{\mathcal{X}}}e_{i}\in
I_{1},\max_{s_{i}\in B\cap G_{n}^{\mathcal{X}}}e_{i}\in I_{2}\right\\}.$

Then, imposing an arbitrary ordering of the hyperballs in $\mathcal{B}_{n}$,
we have

$\mathbb{P}\left(\forall B\in\mathcal{B}_{n},\min_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e_{i}\in I_{1},\max_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e_{i}\in I_{2}\right)$
$=\mathbb{P}\left(E(B_{1})\right)\prod_{i=2}^{|\mathcal{B}_{n}|}\mathbb{P}\left(E(B_{i})|E(B_{i-1}),...,E(B_{1})\right).$

For all $i\in\\{1,...,|\mathcal{B}_{n}|\\}$, we observe that either there
exists $j\in\\{1,...,i-1\\}\text{ such that }B_{i}\cap B_{j}\cap
G_{n}^{\mathcal{X}}\neq 0$ in which case

$\mathbb{P}\left(E(B_{i})|E(B_{i-1}),...,E(B_{1})\right)>\mathbb{P}(E(B_{i}))$

or no such $j$ exists, in which case

$\mathbb{P}(E(B_{i})|E(B_{i-1}),...,E(B_{1}))=\mathbb{P}(E(B_{i})).$

Therefore, we have that

$\mathbb{P}(\forall B\in\mathcal{B}_{n},\min_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e_{i}\in I_{1},\max_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e_{i}\in I_{2})$
$\geq\prod_{B\in\mathcal{B}_{n}}\mathbb{P}(\min_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e_{i}\in I_{1},\max_{s_{i}\in B\cap
G_{n}^{\mathcal{X}}}e_{i}\in I_{2}).$

$(\star\star\star)$ In order to alleviate notation, for all
$B\in\mathcal{B}_{n}$, we define the following event:

$\mathcal{E}_{B}(n):=\left\\{|\\{i\in[n]\\},s_{i}\in
B\\}|>C_{2}b_{n}\right\\}.$

It is trivial to see that for all $B\in\mathcal{B}_{n}$, $\mathcal{E}_{B}(n)$
is increasing in $n$ (when $b_{n}$ is kept fixed). Utilising the arbitrary
numbering of $\mathcal{B}_{n}$ defined above in $(\star\star)$, we have

$\mathbb{P}(S_{n})=\mathbb{P}(\forall
B\in\mathcal{B}_{n}:\mathcal{E}_{B}(n))=\mathbb{P}\left(\mathcal{E}_{B_{2}}(n)\right)\prod_{i=1}^{|\mathcal{B}_{n}|}\mathbb{P}\left(\mathcal{E}_{B_{i}}(n)|\mathcal{E}_{B_{i-1}}(n),...,\mathcal{E}_{B_{1}}(n)\right)$
$\geq\prod_{i=1}^{|\mathcal{B}_{n}|}\mathbb{P}\left(\mathcal{E}_{B_{i}}(n-(i-1)C_{2}b_{n}\right)\geq\prod_{B\in\mathcal{B}_{n}}\mathbb{P}\left(\mathcal{E}_{B}(n-|\mathcal{B}_{n}|C_{2}b_{n}\right)$

where the second to last inequality holds due to the independence of the input
sampling. Computing $|\mathcal{B}_{n}|C_{2}b_{n}$, we obtain

$|\mathcal{B}_{n}|C_{2}b_{n}\leq
C_{2}\frac{C_{1}}{a_{n}^{\frac{d}{\alpha}}}\log(\frac{1}{a_{n}})\frac{1}{a_{n}^{\eta}}=C_{1}C_{2}\frac{\log(\frac{1}{a_{n}})}{a_{n}^{\frac{d+\eta\alpha}{\alpha}}}$
$=nC_{1}C_{2}\frac{\alpha}{d+\eta\alpha}(1-\frac{\log(\log(n))}{\log(n)})\leq
nC_{1}C_{2}\frac{\alpha}{d+\eta\alpha}.$

Therefore, setting the condition $C_{2}\leq\frac{d+\eta\alpha}{2C_{1}\alpha}$,
we have

$\mathbb{P}(S_{n})\geq\prod_{B\in\mathcal{B}_{n}}\mathbb{P}\left(\mathcal{E}_{B}\left(n(1-C_{1}C_{2}\frac{\alpha}{d+\eta\alpha})\right)\right)\geq\prod_{B\in\mathcal{B}_{n}}\mathbb{P}\left(\mathcal{E}_{B}(\frac{n}{2})\right).$

##  C Technical Lemmas

###### Lemma 25

Assume that the settings and assumptions of Theorem 7 hold. Let
$(g_{n})_{n\in\mathbb{N}}$ denote a sequence of non-parametric predictors and
$(b_{n})_{n\in\mathbb{N}}$ denote a convergence rate sequence (that converges
to 0). If $\exists K>0$ such that
$\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\left\|\hat{g}_{n}-f\right\|_{\infty}<K$
$\forall n\in\mathbb{N}$ with probability 1, then

$\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{E}[(f(x_{n+1})-\hat{g}_{n}(x_{n+1}))^{p}]\to
0$ (6)

if and only if $\forall\epsilon>0$

$\lim_{n\to\infty}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{P}(|f(x_{n+1})-\hat{g}_{n}(x_{n+1})|>\epsilon)=0$
(7)

where $\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$ is as defined in Corollary
9.

Proof  ”$\implies$” can be trivially obtained by applying Markov’s inequality.
We show the ”$\impliedby$” statement. Fix $\epsilon>0$ and consider an
arbitrary $f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})$. Define
$A_{n}:=|f(x_{n+1})-\hat{g}_{n}(x_{n+1})|>\epsilon$, we have

$(f(x_{n+1})-\hat{g}_{n}(x_{n+1}))^{p}\leq\epsilon^{p}1_{A_{n}^{c}}+K^{p}1_{A_{n}}$

with probability $1$. This implies that

$\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{E}[(f(x_{n+1})-\hat{g}_{n}(x_{n+1}))^{p}]$
$\leq\epsilon^{p}+K^{p}\sup_{f\in\overline{Lip}(L^{*},\,\mathfrak{d},M^{*})}\mathbb{P}(|f(x_{n+1})-\hat{g}_{n}(x_{n+1})|>\epsilon)$
$\stackrel{{\scriptstyle n\to 0}}{{\leq}}\epsilon^{p}.$

As the choice of $\epsilon$ was arbitrary, $(\ref{equ:conv moment})$ holds.

###### Lemma 26

$\forall p,c>0$, we have

$\limsup_{x\to\infty}x\left(1-(1-\frac{1}{x^{p+1}})^{cx^{p}}\right)\leq 2c$

Proof  Lemma 26 can be shown as follows.

$x\left(1-(1-\frac{1}{x^{p+1}})^{cx^{p}}\right)=x\left(1-e^{cx^{p}\log(1-\frac{1}{x^{p+1}})}\right).$

Expanding the exponent based on the power series expression of $\log(1+x)$, we
obtain

$cx^{p}\log(1-\frac{1}{x^{p+1}})=-cx^{p}\sum_{m=1}^{\infty}\frac{1}{mx^{m(p+1)}}=-\frac{cx^{p}}{x^{p+1}}\sum_{m=0}^{\infty}\frac{1}{(m+1)x^{m(p+1)}}$
$\geq-\frac{c}{x}\sum_{m=0}^{\infty}\frac{1}{x^{m(p+1)}}=-\frac{c}{x}\frac{x^{(p+1)}}{x^{(p+1)}-1}\geq-\frac{2c}{x}$

for sufficiently large $x$. Substituting this equation back into the initial
bound, we obtain:

$\limsup_{x\to\infty}x\left(1-e^{cx^{p}\log(1-\frac{1}{x^{p+1}})}\right)\leq\limsup_{x\to\infty}x\left(1-e^{-\frac{2c}{x}}\right)\stackrel{{\scriptstyle
x\to\infty}}{{\rightarrow}}2c.$