# Unrestricted Douglas-Rachford algorithms for solving convex feasibility
problems in Hilbert space

Kay Barshada, Aviv Gibalib and Simeon Reichc CONTACT
K. Barshad<EMAIL_ADDRESS><EMAIL_ADDRESS>
A. Gibali<EMAIL_ADDRESS>
S. Reich<EMAIL_ADDRESS>a,cDepartment of Mathematics, The Technion –
Israel Institute of Technology, 32000 Haifa, Israel;
bDepartment of Mathematics, Braude College, 2161002 Karmiel, Israel

###### Abstract

In this work we focus on the convex feasibility problem (CFP) in Hilbert
space. A specific method in this area that has gained a lot of interest in
recent years is the Douglas-Rachford (DR) algorithm. This algorithm was
originally introduced in 1956 for solving stationary and non-stationary heat
equations. Then in 1979, Lions and Mercier adjusted and extended the algorithm
with the aim of solving CFPs and even more general problems, such as finding
zeros of the sum of two maximally monotone operators. Many developments which
implement various concepts concerning this algorithm have occurred during the
last decade. We introduce an unrestricted DR algorithm, which provides a
general framework for such concepts. Using unrestricted products of a finite
number of strongly nonexpansive operators, we apply this framework to provide
new iterative methods, where, inter alia, such operators may be interlaced
between the operators used in the scheme of our unrestricted DR algorithm.

###### keywords:

Convex feasibility problem; common fixed point problem; Douglas-Rachford
algorithm; iterative method; strongly nonexpansive operator; unrestricted
product.

##  1 Preliminaries

Suppose that $\mathcal{H}$ is a real Hilbert space with inner product
$\langle\cdot,\cdot\rangle$ and let $\|\cdot\|$ be the norm induced by
$\langle\cdot,\cdot\rangle$. We denote by
$Id:\mathcal{H}\rightarrow\mathcal{H}$ the identity operator on $\mathcal{H}$,
that is, for all $x\in\mathcal{H}$, $Idx=x$. For an operator
$T:\mathcal{H}\rightarrow\mathcal{H}$, the fixed points set of $T$ is defined
as $\mathrm{Fix(\mathit{T})}:=\left\\{x\in\mathcal{H}\mid Tx=x\right\\}$. For
each nonempty and convex set $C\subseteq\mathcal{H}$, we denote by $P_{C}$ the
(unique) metric projection onto $C$, the existence of which is guaranteed if
$C$ is, in addition, closed. The expressions $x_{n}\rightharpoonup x$ and
$x_{n}\rightarrow x$ denote, respectively, the weak and strong convergence to
$x$ of a sequence $\left\\{x_{n}\right\\}_{n=0}^{\infty}$ in
$\mathscr{\left(\mathcal{H},\mathscr{\|\cdot\|}\right)}$. Throughout this
paper, $\mathbb{N}$ denotes the set of natural numbers starting from $0$, and
for any two integers $m$ and $n$, with $m\leq n$, we denote by
$\left\\{m,\dots,n\right\\}$ the set of all integers between $m$ and $n$
(including $m$ and $n)$.

Now we recall the following types of algorithmic operators. For more
information on such operators, see, for example, [9].

######  Definition 1.1.

Let $T:\mathcal{H}\rightarrow\mathscr{\mathcal{H}}$ be an operator and let
$\lambda\in\left[0,2\right]$. The operator
$T_{\lambda}:\mathcal{H}\rightarrow\mathscr{\mathcal{H}}$ defined by
$T_{\lambda}:=\left(1-\lambda\right)\mathrm{Id}+\lambda T$ is called a
$\lambda$-$relaxation$ of the operator $T$. The operator $T_{2}$ is called the
reflection of the operator $T$.

######  Remark 1.

Clearly, $\mathrm{Fix}(T)=\mathrm{Fix}(T_{\lambda})$ for every operator
$T:\mathcal{H}\rightarrow\mathcal{H}$ and every $\lambda\in\left(0,2\right]$.

######  Definition 1.2.

An operator $T:\mathcal{H}\rightarrow\mathcal{H}$ is said to be nonexpansive
if

$\left\|Tx-Ty\right\|\leq\left\|x-y\right\|\;\forall x,y\in\mathcal{H}.$

For $\lambda\in\left[0,2\right]$, an operator
$T:\mathcal{H}\rightarrow\mathcal{H}$ is said to be $\lambda$-relaxed
nonexpansive if $T$ is a $\lambda$-relaxation of a nonexpansive operator $U$,
that is, $T=U_{\lambda}$.

######  Remark 2.

Clearly, a composition of nonexpansive operators is nonexpansive.

######  Definition 1.3.

An operator $T:\mathcal{H}\rightarrow\mathcal{H}$ is said to be quasi-
nonexpansive if $\mathrm{Fix}\left(T\right)\not=\emptyset$ and

$\left\|Tx-z\right\|\leq\left\|x-z\right\|\;\forall(x,z)\in\mathcal{H}\times\mathrm{Fix}\left(T\right).$

######  Remark 3.

It is clear that a nonexpansive operator with a fixed point is, in particular,
quasi-nonexpansive.

######  Definition 1.4.

An operator $T:\mathcal{H}\rightarrow\mathcal{H}$ is called firmly
nonexpansive if

$\left\langle Tx-Ty,x-y\right\rangle\geq\left\|Tx-Ty\right\|^{2}\;\forall
x,y\in\mathcal{H}.$

For $\lambda\in\left[0,2\right]$, an operator
$T:\mathcal{H}\rightarrow\mathcal{H}$ is called $\lambda$-relaxed firmly
nonexpansive if $T$ is a $\lambda$-relaxation of a firmly nonexpansive
operator $U$, that is, $T=U_{\lambda}$.

######  Theorem 1.5.

Let $T:\mathcal{H}\rightarrow\mathcal{H}$ be an operator. The following
conditions are equivalent.

  1. i.

$T$ is firmly nonexpansive.

  2. ii.

$T_{\lambda}$ is nonexpansive for each $\lambda\in\left[0,2\right]$.

  3. iii.

There exists a nonexpansive operator $N:\mathcal{H\rightarrow\mathcal{H}}$
such that $T=2^{-1}\left(Id+N\right)$.

###### Proof.

See Theorem 2.2.10 in [9]. ∎

######  Definition 1.6.

For $\lambda\in\left(0,1\right)$, we say that an operator
$T:\mathcal{H}\rightarrow\mathcal{H}$ is $\lambda$-averaged if it is a
$\lambda$-relaxed nonexpansive operator. We say that an operator
$T:\mathcal{H}\rightarrow\mathcal{H}$ is averaged if it is $\lambda$-averaged
for some $\lambda\in\left(0,1\right)$.

######  Corollary 1.7.

Let $\lambda\in\left(0,2\right)$. An operator
$T:\mathcal{H}\rightarrow\mathcal{H}$ is $\lambda$-relaxed firmly nonexpansive
if and only if it is $(2^{-1}\lambda)$-averaged.

###### Proof.

See Corollary 2.2.17 in [9]. ∎

######  Theorem 1.8.

Let $n$ be a positive integer. For each $i=1,\dots,n$, let
$\lambda_{i}\in\left(0,2\right)$ and let
$T_{i}:\mathcal{H}\rightarrow\mathcal{H}$ be $\lambda_{i}$-relaxed firmly
nonexpansive. Then $T:=T_{n}T_{n-1}\cdots T_{1}$ is a $\lambda$-relaxed firmly
nonexpansive operator for some $\lambda\in\left(0,2\right)$. In addition, if
$\cap_{i=1}^{n}\mathrm{Fix}(T_{i})\not=\emptyset$, then
$\mathrm{Fix}(T)=\cap_{i=1}^{n}\mathrm{Fix}(T_{i})$.

###### Proof.

See Theorem 2.2.42 and Theorem 2.1.26 in [9]. ∎

The following corollary is an immediate consequence of Theorem 1.8 and
Corollary 1.7.

######  Corollary 1.9.

Let $n$ be a positive integer. For each $i=1,\dots,n$, let
$\lambda_{i}\in\left(0,1\right)$ and let
$T_{i}:\mathcal{H}\rightarrow\mathcal{H}$ be $\lambda_{i}$-averaged. Then
$T:=T_{n}T_{n-1}\cdots T_{1}$ is a $\lambda$-averaged operator for some
$\lambda\in\left(0,1\right)$. In addition, if
$\cap_{i=1}^{n}\mathrm{Fix}(T_{i})\not=\emptyset$, then
$\mathrm{Fix}(T)=\cap_{i=1}^{n}\mathrm{Fix}(T_{i})$.

######  Example 1.10.

Let $C\subset\mathcal{H}$ be a nonempty, closed and convex set, and let
$P_{C}:\mathscr{\mathcal{H}\rightarrow\mathcal{H}}$ be the metric projection
onto $C$. Then the operator $P_{C}$ is firmly nonexpansive and hence averaged.
For the proof, see Theorem 2.2.21 in [9].

######  Definition 1.11.

We write that an operator $T:\mathcal{H}\rightarrow\mathcal{H}$ satisfies
Condition $\left(S\right)$ if for each pair of sequences
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ and
$\left\\{y_{n}\right\\}_{n=0}^{\infty}$ in $\mathcal{H}$,

$\left.\begin{array}[]{l}\left\\{x_{n}-y_{n}\right\\}_{n=0}^{\infty}\,\,\mathrm{is}\,\mathrm{\,bounded}\\\
\left\|x_{n}-y_{n}\right\|-\left\|Tx_{n}-Ty_{n}\right\|\rightarrow
0\end{array}\right\\}\Longrightarrow
x_{n}-y_{n}-\left(Tx_{n}-Ty_{n}\right)\rightarrow 0.$

The operator $T$ is called strongly nonexpansive if it is nonexpansive and
satisfies Condition $\left(S\right)$.

######  Theorem 1.12.

Let $T:\mathcal{H}\rightarrow\mathcal{H}$ be a firmly nonexpansive operator
and let $\lambda\in\left(0,2\right)$. Then the $\lambda$-relaxation
$T_{\lambda}$ of $T$ is strongly nonexpansive.

###### Proof.

See Theorem 2.3.4 in [9]. ∎

The following corollary is an immediate consequence of Theorem 1.12 and
Corollary 1.7.

######  Corollary 1.13.

Let $T:\mathcal{H}\rightarrow\mathcal{H}$ be an averaged operator. Then $T$ is
strongly nonexpansive.

######  Definition 1.14.

An operator $T:\mathcal{H}\rightarrow\mathcal{H}$ is asymptotically regular if
for each $x\in\mathcal{H}$, we have

$\left\|T^{n+1}x-T^{n}x\right\|\rightarrow 0.$

######  Lemma 1.15.

Let $T:\mathcal{H}\rightarrow\mathcal{H}$ be a strongly nonexpansive operator
such that $\mathrm{Fix}\left(T\right)\not=\emptyset$. Then $T$ is
asymptotically regular.

###### Proof.

See Lemma 3.4.9 in [9]. ∎

######  Definition 1.16.

Let $C$ be nonempty, closed and convex subset of $\mathcal{H}$. An operator
$T:C\rightarrow\mathcal{H}$ is weakly regular (satisfies Opial’s demi-
closedness principle, $T-Id$ is demiclosed at $0$) if for any sequence
$\left\\{x_{n}\right\\}_{n=0}^{\infty}\subset\mathcal{H}$ and any
$x\in\mathcal{H}$, the following implication holds:

$\left.\begin{array}[]{l}x_{n}\rightharpoonup x\\\ Tx_{n}-x_{n}\rightarrow
0\end{array}\right\\}\Longrightarrow x\in\mathrm{Fix}(T).$

######  Lemma 1.17.

Let $T:\mathcal{H}\rightarrow\mathcal{H}$ be a nonexpansive operator. Then $T$
is weakly regular.

###### Proof.

See Lemma 3.2.5 in [9]. ∎

Next, we recall the following generalization of Opial’s Theorem, which we will
use in the sequel.

######  Theorem 1.18.

Let $C\subset\mathcal{H}$ be a nonempty, closed and convex set, and let
$S:C\rightarrow\mathcal{H}$ be a weakly regular operator such that
$\mathrm{Fix}\left(S\right)\not=\emptyset$. Assume that $x_{0}\in C$ is
arbitrary and $\left\\{T_{n}\right\\}_{n=0}^{\infty}$ is a sequence of quasi-
nonexpansive operators $T_{n}:C\rightarrow C$ such that
$\mathrm{Fix}\left(S\right)\subset\cap_{n=0}^{\infty}\mathrm{Fix}(T_{n})$. If
the sequence $\left\\{x_{n}\right\\}_{n=0}^{\infty}$ generated by the
recurrence $x_{n}=T_{n-1}\left(x_{n-1}\right)$ satisfies

$\left\|Sx_{n}-x_{n}\right\|\rightarrow 0,$

then it converges weakly to a point $x_{*}\in\mathrm{Fix}\left(S\right)$.

###### Proof.

See Theorem 3.6.2 along with Remark 3.6.4 in [9]. ∎

The following theorem is an immediate consequence of Theorem 1.18. It is a
well-known theorem established by Opial in [16].

######  Theorem 1.19.

Let $C\subset\mathcal{H}$ be a nonempty, closed and convex set. If
$T:C\rightarrow C$ is a nonexpansive and asymptotically regular operator with
$\mathrm{Fix}\left(T\right)\not=\emptyset$, then for any $x_{0}\in C$, the
sequence $\left\\{x_{n}\right\\}_{n=0}^{\infty}$ generated by the recurrence
$x_{n}=T\left(x_{n-1}\right)$ converges weakly to a point
$x_{*}\in\mathrm{Fix}\left(T\right)$.

##  2 Introduction

The Convex Feasibility Problem (CFP) in $\mathcal{H}$ is the problem of
finding a point $x_{*}\in\cap_{\alpha\in I}C_{\alpha}$, where
$\left\\{C_{\alpha}\right\\}_{\alpha\in I}$ is a family of nonempty, closed
and convex subsets of $\mathcal{H}$. There are numerous iterative methods for
solving this problem in the literature (see, for example, [4, 5, 9] and
references therein). The Douglas-Rachford (DR) algorithm for a finite family
of sets, originally introduced by Douglas and Rachford in [12] for solving the
heat equation, is one such method. It has attracted considerable interest in
the last few years. Many investigations of this algorithm have recently been
undertaken in diverse directions, as one can observe, for example, in [8, 14,
1, 6, 11] and references therein. Borwein and Tam presented in [7] a cyclic-DR
algorithm for CFPs in which the number of sets is allowed to be greater than
$2$. In this DR algorithm the original one is applied over subsequent pairs of
sets. Artacho et al. provided in [2] a more general framework for the cyclic
DR algorithm, where the proper employment of certain sets and operators in
this algorithm is studied. In the present paper we offer a further extension
of these ideas by introducing an unrestricted DR algorithm, where the sets are
chosen (almost) unrestrictedly, that is, our DR-algorithm is (almost)
unrestricted in the sense of the choice of sets which are used to obtain its
outcome. We begin by recalling the notion of an $r$-set Douglas-Rachford
($r$-set DR) operator, which was defined in [11] in the following way.

######  Definition 2.1.

Given a finite family $\left\\{C_{i}\right\\}_{i=1}^{r}$ of nonempty, closed
and convex subsets of $\mathcal{H}$, the composite reflection operator
$\mathcal{V}_{\left\\{C_{i}\right\\}_{i=1}^{r}}:\mathcal{H}\rightarrow\mathcal{H}$
is defined by

$\mathcal{V}_{\left\\{C_{i}\right\\}_{i=1}^{r}}:=\mathcal{R}_{C_{r}}\dots\mathcal{R}_{C_{1}},$
(1)

where $\mathcal{R}_{C_{i}}=2P_{C_{i}}-Id$ is the reflection with respect to
the corresponding $C_{i}$ for each $i=1,\dots,r$. The $r$-set DR  operator
$\mathcal{T}_{\left\\{C_{i}\right\\}_{i=1}^{r}}:\mathcal{H}\rightarrow\mathcal{H}$
is defined by

$\mathcal{T}_{\left\\{C_{i}\right\\}_{i=1}^{r}}:=2^{-1}\left(Id+\mathcal{V}_{\left\\{C_{i}\right\\}_{i=1}^{r}}\right).$
(2)

We recall the following property of the $r$-set DR operator established in
[11].

######  Lemma 2.2.

Let $\left\\{C_{i}\right\\}_{i=1}^{r}$ be a finite family of nonempty, closed
and convex subsets of $\mathcal{H}$ such that
$\mathrm{int}\cap_{i=1}^{r}C_{i}\not=\emptyset$. Then

$\mathrm{Fix}\left(\mathcal{T}_{\left\\{C_{i}\right\\}_{i=1}^{r}}\right)=\cap_{i=1}^{r}C_{i}.$

###### Proof.

See Corollary 23 in [11]. ∎

Given a finite family $\left\\{C_{i}\right\\}_{i=1}^{m}$ of nonempty, closed
and convex subsets of $\mathcal{H}$, a mapping $f$ from $\mathbb{N}$ onto
$\left\\{1,\dots,m\right\\}$ and an integer $r>1$, set
$\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}$ to be the
finite family of subsets of $\mathcal{H}$ defined by

$C_{m,r}\left(n\right)\left(j\right):=C_{f\left(\left(r-1\right)n+j-1\right)}$
(3)

for each $j=1,\dots,r$ and each natural number $n$. Define a sequence of
unrestricted $r$-set DR operators $\left\\{S_{n}\right\\}_{n=0}^{\infty}$ by

$S_{n}:=\mathcal{T}_{\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}}$
(4)

for each $n\in\mathbb{N}$. For an arbitrary point $x_{0}\in\mathcal{H}$, we
intend to analyze the convergence of the sequence
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ generated by the following recurrence:

$\displaystyle\color[rgb]{0,0,0}x_{n}:=S_{n-1}\left(x_{n-1}\right).\color[rgb]{0,0,0}$
(5)

The sequence $\left\\{x_{n}\right\\}_{n=0}^{\infty}$ is the outcome of our
unrestricted DR algorithm.

In the setting above, let $j_{f}$ be a natural number such that

$f\left(\left\\{1,\dots,j_{f}\right\\}\right)=\left\\{1,\dots,m\right\\}.$ (6)

We define a composite unrestricted DR operator
$Q:\mathcal{H}\rightarrow\mathcal{H}$ by

$Q:=S_{j_{f}}\dots S_{0}$ (7)

and study the convergence properties of the sequence
$\left\\{y_{n}\right\\}_{n=0}^{\infty}$ generated by the following recurrence,
for an arbitrary point $y_{0}\in\mathcal{H}$:

$\displaystyle y_{n}:=Q\left(y_{n-1}\right)$ (8)

This sequence is the outcome of an alternative unrestricted DR algorithm.

For a finite (possibly empty) family of operators
$\left\\{T_{i}\right\\}_{i=p}^{q}$ defined on $\mathcal{H}$, where $p$ and $q$
are integers, recall that for each integer $q^{\prime}\leq q$, the product
(composition) of $\left\\{T_{i}\right\\}_{i=p}^{q^{\prime}}$, which we denote
by $T_{q}\cdots T_{p}$ (it is sometimes denoted in the literature also by
$\prod_{i=p}^{q}T_{i}$) is defined by the following recurrence:

$T_{q^{\prime}}\cdots T_{p}:=\begin{cases}Id&\mathrm{if}\,q^{\prime}<p\\\
T_{q^{\prime}}\circ\left(T_{q^{\prime}-1}\cdots
T_{p}\right)&\mathrm{if}\,q^{\prime}\geq p\end{cases}.$

Recall also that the unrestricted product of a family
$\left\\{T_{\alpha}\right\\}_{i\in I}$ of operators determined by a mapping
$h:\mathbb{N}\rightarrow I$ is the sequence of operators
$\left\\{P_{n}\right\\}_{n=0}^{\infty}$ defined by
$P_{n}:=T_{h\left(n\right)}\dots T_{h\left(0\right)}$ for each
$n\in\mathbb{N}$. For more information and applications concerning
unrestricted products, we refer the reader to, for example, [10] and [13].

The following theorem concerning the convergence of an unrestricted product of
two strongly nonexpansive operators was established in [13]. It provides a
powerful tool for finding a common fixed point of two such operators.

######  Theorem 2.3.

Let $T_{1}$ and $T_{2}$ be two strongly nonexpansive operators such that
$\mathrm{Fix}(T_{1})\cap\mathrm{Fix}(T_{2})\not=\emptyset$. Assume
$h:\mathbb{N\rightarrow}\left\\{1,2\right\\}$ is a mapping such that
$h^{-1}\left(\left\\{i\right\\}\right)$ is an infinite set for each $i=1,2$.
Then for each $x\in\mathcal{H}$, the sequence
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$, where
$\left\\{P_{n}\right\\}_{n=0}^{\infty}$ is the unrestricted product of
$\left\\{T_{i}\right\\}_{i=1}^{2}$ determined by the mapping $h$, converges
weakly to a common fixed point of $T_{1}$ and $T_{2}$.

###### Proof.

See Theorem 1 in [13]. ∎

It is still an open question, whether this result can be extended to more than
two operators in the most general case. But from the optimization theory point
of view, we can actually choose how often each operator belonging to a given
family of operators should appear in the concrete method which we apply in
order to find a common fixed point of the operators in this family. It turns
out that in the case where each operator of a given finite family appears in
the product sufficiently frequently, Theorem 2.3 can be extended to an
arbitrary finite number of given operators, as is implied by Theorem 2.5
below. Before formulating it, we present the following notion of quasi-
periodicity, which was used in [13]. In similar settings, it is sometimes
called intermittency (see, for example, [3] and [15]).

######  Definition 2.4.

Assume that $M$ is a positive integer and that $h$ is a mapping defined on
$\mathbb{N}$. We say that $h$ is $M$-quasi-periodic if for each
$n\in\mathbb{N}$, we have

$h\left(\left\\{n,\dots,n+M-1\right\\}\right)=h\left(\mathbb{N}\right).$

Given a finite family $\left\\{T_{i}\right\\}_{i=1}^{m}$ of strongly
nonexpansive operators, a positive integer $M$ and an $M$-quasi-periodic
mapping $h$ which is onto $\left\\{1,\dots,m\right\\}$, the following theorem,
which was first proved in [13], establishes the convergence of the sequence
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$, where
$\left\\{P_{n}\right\\}_{n=0}^{\infty}$ is the unrestricted product of the
family $\left\\{T_{i}\right\\}_{i=1}^{m}$ determined by $h$ and
$x\in\mathcal{H}$ is arbitrary. Due to the high importance of this theorem and
for the convenience of the reader, we provide a detailed proof of it in
Section 4.

######  Theorem 2.5.

Assume that $\left\\{T_{i}\right\\}_{i=1}^{m}$ is a finite family of strongly
nonexpansive operators satisfying
$\cap_{i=1}^{m}\mathrm{Fix}(T_{i})\not=\emptyset$, $M$ is a positive integer
and $h$ is an $M$-quasi-periodic mapping onto $\left\\{1,\dots,m\right\\}$.
Then for each $x\in\mathcal{H}$, the sequence
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ converges weakly to a common fixed
point of the operators $\left\\{T_{i}\right\\}_{i=1}^{m}$, where
$\left\\{P_{n}\right\\}_{n=0}^{\infty}$ is the unrestricted product of
$\left\\{T_{i}\right\\}_{i=1}^{m}$ determined by $h$.

In order to prove the above theorem we need the following two technical
lemmata.

######  Lemma 2.6.

Let $T:\mathcal{H}\rightarrow\mathcal{H}$ be a nonexpansive mapping and
$\left\\{v_{n}\right\\}_{n=0}^{\infty}$ be a sequence in $\mathcal{H}$.
Suppose $\left\\{v_{n}\right\\}_{n=0}^{\infty}$ and
$\left\\{Tv_{n}\right\\}_{n=0}^{\infty}$ both converge weakly to some
$v\in\mathcal{H}$ and that
$\left\|v_{n}\right\|-\left\|Tv_{n}\right\|\rightarrow 0$. Then
$v\in\mathrm{Fix}(T)$.

###### Proof.

See Lemma 1 in [13]. ∎

######  Lemma 2.7.

Let $\left\\{T_{\alpha}\right\\}_{\alpha\in I}$ be a family of nonexpansive
operators and $h:\mathbb{N}\rightarrow I$ be a mapping. Assume that
$\left\\{P_{n_{k}}\right\\}_{k=0}^{\infty}$ and
$\left\\{P_{n_{k}^{\prime}}\right\\}_{k=0}^{\infty}$ are two subsequences of
the unrestricted product $\left\\{P_{n}\right\\}_{n=0}^{\infty}$ of
$\left\\{T_{\alpha}\right\\}_{\alpha\in I}$ determined by $h$ and let
$x\in\mathcal{H}$. If $x_{1}$and $x_{2}$ are common fixed points of the family
$\left\\{T_{\alpha}\right\\}_{\alpha\in I}$ above such that
$P_{n_{k}}x\rightharpoonup x_{1}$ and $P_{n_{k}^{\prime}}x\rightharpoonup
x_{2}$, then $x_{1}=x_{2}$.

###### Proof.

See Lemma 3 in [13]. ∎

The rest of the paper is organized as follows. In Section 3 we formulate our
main results, as well as discuss a few remarks and examples. Section 4 is
devoted to several auxiliary results. Finally, the proofs of our main results
are presented in Section 5.

##  3 Main results

Below we state our three main theorems. We establish them in Section 5.

######  Theorem 3.1.

Assume that $\left\\{C_{i}\right\\}_{i=1}^{m}$ is a finite family of nonempty,
closed and convex subsets of $\mathcal{H}$, $r>1$ is an integer and $f$ is a
mapping from $\mathbb{N}$ onto $\left\\{1,\dots,m\right\\}$. Suppose that the
sequences $\left\\{S_{n}\right\\}_{n=0}^{\infty}$ and
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ are defined, respectively, by (4) and
(5), $j_{f}$ is defined by (6), $Q$ is defined by (7) and
$\left\\{y_{n}\right\\}_{n=0}^{\infty}$ is defined by (8). Then the following
assertions hold:

  1. i.

If there exists $S:\mathcal{H}\rightarrow\mathcal{H}$, which is a weakly
regular operator with a fixed point such that
$\mathrm{Fix}(S)\subset\cap_{i=1}^{m}C_{i}$, and the sequence
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ satisfies

$\left\|Sx_{n}-x_{n}\right\|\rightarrow 0,$

then $\left\\{x_{n}\right\\}_{n=0}^{\infty}$ converges weakly to a point
$x_{*}\in\cap_{i=1}^{m}C_{i}$.

  2. ii.

If $\cap_{i=1}^{m}C_{i}$ has an interior point, then the sequence
$\left\\{y_{n}\right\\}_{n=0}^{\infty}$ converges weakly to a point
$y_{*}\in\cap_{i=1}^{m}C_{i}$.

Note that part (ii) of Theorem 3.1 above generalizes Theorem 3.7 in [2] (see
also Remark 4 (c) below). Since it is often difficult to verify the existence
of an operator $S$ as in part (i), we introduce a so-called $M$-quasi-periodic
unrestricted DR algorithm in our next result, where we make a modest
assumption concerning the frequency of the sets defined by (3). This algorithm
converges weakly if $\cap_{i=1}^{n}C_{i}\not=\emptyset$ and if, in addition,
$\cap_{i=1}^{n}C_{i}$ has an interior point, then its weak limit is a solution
of the CFP defined by the family $\left\\{C_{i}\right\\}_{i=1}^{m}$.

######  Theorem 3.2.

Assume that $\left\\{C_{i}\right\\}_{i=1}^{m}$ is a finite family of nonempty,
closed and convex subsets of $\mathcal{H}$, $r>1$ and $M$ are positive
integers. Let $f$ be a mapping from $\mathbb{N}$ onto
$\left\\{1,\dots,m\right\\}$. For each natural number $n$, let
$\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}$ be the finite
family of subsets of $\mathcal{H}$ defined by (3) so that the sequence of
families
$\left\\{\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}\right\\}_{n=0}^{\infty}$
is $M$-quasi-periodic (as a mapping defined on $\mathbb{N}$). Suppose that the
sequences $\left\\{S_{n}\right\\}_{n=0}^{\infty}$ and
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ are defined, respectively, by (4) and
(5). Then the following assertions hold:

  1. i.

If $\cap_{i=1}^{n}C_{i}\not=\emptyset$, then
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ converges weakly to a common fixed
point of the operators $\left\\{S_{n}\right\\}_{n=0}^{\infty}$.

  2. ii.

If $\mathrm{int}\cap_{i=1}^{n}C_{i}\not=\emptyset$, then
$\left\\{x_{n}\right\\}_{n=0}^{\infty}$ converges weakly to a point
$x_{*}\in\cap_{i=1}^{m}C_{i}$.

######  Theorem 3.3.

Assume that $\left\\{C_{i}\right\\}_{i=1}^{m}$ is a finite family of nonempty,
closed and convex subsets of $\mathcal{H}$ such that $\cap_{i=1}^{m}C_{i}$ has
an interior point, and that $r>1$ and $M$ are positive integers. Suppose
further that $f$ is a mapping from $\mathbb{N}$ onto
$\left\\{1,\dots,m\right\\}$, the sequence
$\left\\{S_{n}\right\\}_{n=0}^{\infty}$ is defined by (4), $j_{f}$ is defined
by (6) and $Q$ is defined by (7). Let $\left\\{T_{j}\right\\}_{j=1}^{k}$ be a
family of strongly nonexpansive operators with a common fixed point, let $h$
be an $M$-quasi-periodic mapping onto $\left\\{1,\dots,k\right\\}$, let
$x\in\mathcal{H}$ and let $\left\\{P_{n}\right\\}_{n=0}^{\infty}$ be the
unrestricted product of the family $\left\\{T_{j}\right\\}_{j=0}^{k}$
determined by $h$. Then the following assertions hold:

  1. i.

If for each $n\in\left\\{1,\dots,j_{f}\right\\}$, the operator $S_{n}$ is an
element of $\left\\{T_{j}\right\\}_{j=1}^{k}$, then
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ converges weakly to a point
$x_{*}\in\cap_{i=1}^{m}C_{i}$.

  2. ii.

If $Q$ is an element of $\left\\{T_{j}\right\\}_{j=1}^{k}$, then
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ converges weakly to a point
$x_{*}\in\cap_{i=1}^{m}C_{i}$.

######  Remark 4.

  1. a.

If $\mathcal{H}$ is a finite dimensional space, then the convergence in our
results is strong.

  2. b.

In particular, due to Lemma 1.17, Theorem 3.1(i) can be applied to the case
where the operator $S$ is a nonexpansive operator.

  3. c.

The cyclic DR algorithm, first introduced in [2], is obtained by choosing in
Theorem 3.2 $f:\mathbb{N}\rightarrow\left\\{1,\dots,m\right\\}$ to be defined
by $f\left(n\right):=n\,\,\mathrm{mod\,}\,m+1$ for each $n\in\mathbb{N}$ and
$M=m$. Here we obtain, in addition, that it always converges to a solution of
the CFP defined by the family $\left\\{C_{i}\right\\}_{i=1}^{m}$ under the
assumption that $\cap_{i=1}^{n}C_{i}$ has an interior point.

  4. d.

By Theorem 1.12, Corollary 1.13 and Example 1.10, Theorem 3.3 can be applied
to the family of strongly nonexpansive operators
$\left\\{T_{i}\right\\}_{i=1}^{k}$, which contains, in particular,
$\lambda$-relaxed firmly nonexpansive operators with the relaxation parameter
lying in the interval $\left(0,2\right)$, averaged operators and metric
projections.

##  4 Auxiliary results

In this section, we present several technical lemmata, which will be used in
the proofs of our main results.

######  Lemma 4.1.

For each family $\left\\{C_{i}\right\\}_{i=1}^{r}$ of nonempty, closed and
convex subsets of $\mathcal{H}$, the unrestricted $r$-sets-DR operator
$\mathcal{T}_{\left\\{C_{i}\right\\}_{i=1}^{r}}$ is averaged and hence
strongly nonexpansive. In particular, if the family
$\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}$ is defined by
(3), where $\left\\{C_{i}\right\\}_{i=1}^{m}$ is a given family of nonempty,
closed and convex subsets of $\mathcal{H}$, $r>1$ is an integer and $f$ is a
mapping from $N$ onto $\left\\{1,\dots,m\right\\}$, then for each
$n\in\mathbb{N}$, the operator $S_{n}$ defined by (4) is averaged and hence
strongly nonexpansive. As a result, the composite unrestricted DR operator $Q$
defined by (7) is averaged and hence strongly nonexpansive.

###### Proof.

Let $\left\\{C_{i}\right\\}_{i=1}^{r}$ be a family of nonempty, closed and
convex subsets of $\mathcal{H}$. For each $i=1,\dots,r$, the reflection
$\mathcal{R}_{C_{i}}=2P_{C_{i}}-Id$ is nonexpansive by Example 1.10 and
Theorem 1.5 (i) and (ii). Hence the composite reflection operator
$\mathcal{V}_{\left\\{C_{i}\right\\}_{i=1}^{r}}$ is nonexpansive by Remark 2.
By (2) and Theorem 1.5 (iii) and (i),
$\mathcal{T}_{\left\\{C_{i}\right\\}_{i=1}^{r}}$ is firmly nonexpansive and by
Corollary 1.7, it is averaged and hence strongly nonexpansive by Corollary
1.13. The rest of the statement of the lemma follows from (4), (7), Corollary
1.9, and Corollary 1.13. ∎

######  Lemma 4.2.

Assume that $\left\\{C_{i}\right\\}_{i=1}^{m}$ is a family of nonempty, closed
and convex subsets of $\mathcal{H}$, $r>1$ is an integer and $f$ is a mapping
from $N$ onto $\left\\{1,\dots,m\right\\}$. Then

$\cap_{i=1}^{m}C_{i}\subset\cap_{n=0}^{\infty}\mathrm{Fix}(S_{n})\subset\cap_{n=0}^{j_{f}}\mathrm{Fix}(S_{n}),$

where $\left\\{S_{n}\right\\}_{n=0}^{\infty}$ and $j_{f}$ are defined by,
respectively, (4) and (6). If, in addition,
$\mathrm{int}\cap_{i=1}^{m}C_{i}\not=\emptyset$, then

$\cap_{i=1}^{m}C_{i}=\cap_{n=0}^{\infty}\mathrm{Fix}(S_{n})=\cap_{n=0}^{j_{f}}\mathrm{Fix}(S_{n}).$

###### Proof.

Clearly, by (4), Remark 1 and (1), for each $n\in\mathbb{N},$

$\mathrm{Fix}(S_{n})=\mathrm{Fix}\left(\mathcal{T}_{\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}}\right)=\mathrm{Fix}\left(\mathcal{V}_{\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}}\right)\supset\cap_{i=1}^{m}C_{i}.$

Hence

$\cap_{i=1}^{m}C_{i}\subset\cap_{n=0}^{\infty}\mathrm{Fix}(S_{n})\subset\cap_{n=0}^{j_{f}}\mathrm{Fix}(S_{n}).$

Assume that $\mathrm{int}\cap_{i=1}^{m}C_{i}\not=\emptyset$. Let
$z\in\cap_{n=0}^{j_{f}}\mathrm{Fix}(S_{n})$ and
$p\in\left\\{1,\dots,m\right\\}$ be arbitrary. There exist $j\in\mathbb{N}$
and unique $N,k\in\mathbb{N}$ such that $f\left(j\right)=p$, $j\leq j_{f}$,
$k<r-1$ and $j=\left(r-1\right)N+k$. Since $N\leq j\leq j_{f}$ and $k+1\leq
r-1$, by (4), Lemma 2.2 and (3), we have

$z\in\mathrm{Fix}(S_{N})=\mathrm{Fix}\left(\mathcal{T}_{\left\\{C_{m,r}\left(N\right)\left(j\right)\right\\}_{j=1}^{r}}\right)=\cap_{j=1}^{r}C_{f\left(\left(r-1\right)N+j-1\right)}\subset
C_{f\left(\left(r-1\right)N+k\right)}=C_{p}.$

Hence

$\cap_{n=0}^{\infty}\mathrm{Fix}(S_{n})\subset\cap_{n=0}^{j_{f}}\mathrm{Fix}(S_{n})\subset\cap_{i=1}^{m}C_{i}$

and the result follows. ∎

The rest of this section is devoted to the proof of Theorem 2.5.

######  Lemma 4.3.

Assume that $\left\\{T_{i}\right\\}_{i=1}^{m}$ is a finite family of
operators, $M$ is a positive integer and $h$ is an $M$-quasi-periodic mapping
onto $\left\\{1,\dots,m\right\\}$. Then for each strictly increasing sequence
$\left\\{n_{k}\right\\}_{k=0}^{\infty}$ of natural numbers such that
$n_{k}\geq n_{k-1}+M$ for each positive integer $k$, there exist a strictly
increasing sequence $\left\\{n_{k}^{\prime}\right\\}_{k=0}^{\infty}$ of
natural numbers and a finite sequence $\left\\{l_{i}\right\\}_{i=1}^{M}$ so
that the set of values of $\left\\{l_{i}\right\\}_{i=1}^{M}$ is
$\left\\{1,\dots,m\right\\}$ and $h\left(j\right)=l_{j-n_{n_{k}^{\prime}}}$
for each $k\in\mathbb{N}$ and each
$j\in\left\\{n_{n_{k}^{\prime}}+1,\dots,n_{n_{k}^{\prime}}+M\right\\}$. As a
result,

$P_{n_{n_{k+1}^{\prime}}}=T_{h\left(n_{n_{k+1}^{\prime}}\right)}\cdots
T_{h\left(n_{n_{k}^{\prime}}+M+1\right)}T_{l_{M}}\cdots
T_{l_{1}}P_{n_{n_{k}^{\prime}}},$

where $\left\\{P_{n}\right\\}_{n=0}^{\infty}$ is the unrestricted product of
$\left\\{T_{i}\right\\}_{i=1}^{m}$ determined by $h$.

###### Proof.

Let $\left\\{n_{k}\right\\}_{k=0}^{\infty}$ be a strictly increasing sequence
of natural numbers such that $n_{k}\geq n_{k-1}+M$ for each positive integer
$k$. Let $k\in\mathbb{N}$. Since $h$ is an $M$-quasi-periodic mapping onto
$\left\\{1,\dots,m\right\\}$, we have
$\left\\{1,\dots,m\right\\}=h\left(\left\\{n_{k}+1,\dots,n_{k}+M\right\\}\right)$
for each natural number $k$.

Since the number of mappings
$s:\left\\{1,\dots,M\right\\}\rightarrow\left\\{1,\dots,m\right\\}$ is finite,
it follows that there exists a strictly increasing sequence
$\left\\{n_{k}^{\prime}\right\\}_{k=0}^{\infty}$ of natural numbers and a
finite sequence $\left\\{l_{i}\right\\}_{i=1}^{M}$ with all the asserted
properties. ∎

######  Lemma 4.4.

Assume that $\left\\{v_{n}\right\\}_{n=0}^{\infty}$ is a bounded sequence in
$\mathcal{H}$, $\left\\{T_{i}\right\\}_{i=1}^{m}$ is a finite family of
strongly nonexpansive operators such that the origin is their common fixed
point and $v\in\mathcal{H}$ is such that

$v_{n}\rightharpoonup v\,\,\mathrm{and}\,\,\left\|T_{i-1}\cdots
T_{1}v_{n}\right\|-\left\|T_{i}\cdots T_{1}v_{n}\right\|\rightarrow 0$ (9)

for each $i=1,\dots,m$. Then the sequence $\left\\{T_{m}\cdots
T_{1}v_{n}\right\\}_{n=1}^{\infty}$ converges weakly to $v$, which is also a
common fixed point of the family $\left\\{T_{i}\right\\}_{i=1}^{m}$.

###### Proof.

The proof is by induction on $m$. For $m=0$ the statement is clear. Assume
that $m>0$. By the induction hypothesis $\left\\{T_{m-1}\cdots
T_{1}v_{n}\right\\}_{n=0}^{\infty}$ converges weakly to $v$, which is a common
fixed point of the family $\left\\{T_{i}\right\\}_{i=1}^{m-1}$. Since each
$T_{i}$ is nonexpansive, since the origin is a common fixed point of the
family $\left\\{T_{i}\right\\}_{i=1}^{m}$ and since the sequence
$\left\\{v_{n}\right\\}_{n=0}^{\infty}$ is bounded, we see that the sequence
$\left\\{T_{m-1}\cdots T_{1}v_{n}\right\\}_{n=0}^{\infty}$ is also bounded.
Define a sequence $\left\\{w_{n}\right\\}_{n=1}^{\infty}\subset\mathcal{H}$ by
$w_{n}:=0$ for all $n\in\mathbb{N}$. Since $T_{m}$ satisfies Condition
$\left(S\right)$ and

$\left\|T_{m-1}\cdots T_{1}v_{n}-w_{n}\right\|-\left\|T_{m}T_{m-1}\cdots
T_{1}v_{n}-T_{m}w_{n}\right\|\rightarrow 0,$

it follows that

$T_{m-1}\cdots T_{1}v_{n}-T_{m}\dots T_{1}v_{n}\rightharpoonup 0.$

As a result, $T_{m}\cdots T_{1}v_{n}$ converges weakly to $v$. Combining this
with the induction hypothesis, (9) and Lemma 2.6 applied to the sequence
$\left\\{T_{m-1}\cdots T_{1}v_{n}\right\\}_{n=0}^{\infty}$ and the operator
$T_{m}$, we obtain the desired result. ∎

######  Lemma 4.5.

Assume that $\left\\{T_{i}\right\\}_{i=1}^{m}$ is a finite family of strongly
nonexpansive operators such that the origin is their common fixed point, $M$
is a positive integer and $h$ is an $M$-quasi-periodic mapping onto
$\left\\{1,\dots,m\right\\}$. Assume that $x\in\mathcal{H}$ and that $v$ is a
weak cluster point of the sequence $\left\\{P_{n}x\right\\}_{n=0}^{\infty}$,
where $\left\\{P_{n}\right\\}_{n=0}^{\infty}$ is the unrestricted product of
$\left\\{T_{i}\right\\}_{i=1}^{m}$ determined by $h$. Then $v$ is also a
common fixed point of the family $\left\\{T_{i}\right\\}_{i=1}^{m}$.

###### Proof.

Clearly, there exists a strictly increasing sequence
$\left\\{n_{k}\right\\}_{k=0}^{\infty}$ such that $P_{n_{k}}x\rightharpoonup
v$. Without any loss of generality, we may assume that $n_{k}\geq n_{k-1}+M$
for each positive integer $k$. By Lemma 4.3, we may also assume that there
exists a finite sequence $\left\\{l_{i}\right\\}_{i=1}^{M}$ so that the set of
values of $\left\\{l_{i}\right\\}_{i=1}^{M}$ is $\left\\{1,\dots,m\right\\}$
and $h\left(j\right)=l_{j-n_{k}}$ for each $k\in\mathbb{N}$ and each
$j\in\left\\{n_{k}+1,\dots,n_{k}+M\right\\}$. As a result,

$P_{n_{k+1}}=T_{h\left(n_{k+1}\right)}\cdots
T_{h\left(n_{k+1}+M+1\right)}T_{l_{M}}\cdots T_{l_{1}}P_{n_{k}}.$ (10)

Since the origin is a common fixed point of the family
$\left\\{T_{i}\right\\}_{i=1}^{m}$ and since each $T_{i}$ is nonexpansive, it
follows that $\lim_{n\rightarrow\infty}\left\|P_{n}x\right\|$ exists. Hence
the sequence $\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ is bounded and by (10)

$\left\|T_{l_{i-1}}\cdots T_{l_{1}}P_{n_{k}}x\right\|-\left\|T_{l_{i}}\cdots
T_{l_{1}}P_{n_{k}}x\right\|\rightarrow 0$

for each $i=1,\dots,M$ as $k\rightarrow\infty$. Now we apply Lemma 4.4 to the
sequence $\left\\{P_{n_{k}}x\right\\}_{k=0}^{\infty}$ and the family
$\left\\{T_{l_{i}}\right\\}_{i=1}^{M}$ to obtain that the sequence
$\left\\{T_{l_{M}}\cdots T_{l_{1}}P_{n_{k}}x\right\\}_{k=0}^{\infty}$
converges weakly to $v$, which is a common fixed point of the family
$\left\\{T_{l_{i}}\right\\}_{i=1}^{M}$ and hence is a common fixed point of
the family $\left\\{T_{i}\right\\}_{i=1}^{m}$, because the set of values of
$\left\\{l_{i}\right\\}_{i=1}^{M}$ is $\left\\{1,\dots,m\right\\}$. ∎

  * Proof of Theorem 2.5.

Without any loss of generality, we may assume that the origin is a common
fixed point of the family $\left\\{T_{i}\right\\}_{i=1}^{m}$. Assume that the
point $x\in\mathcal{H}$. Since the sequence
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ is bounded, it has a weak cluster
point $v$. Let $v_{1},v_{2}\in\mathcal{H}$ be two weak cluster points of
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$. By Lemma 4.5, they are common fixed
points of the family $\left\\{T_{i}\right\\}_{i=1}^{m}$. By Lemma 2.7, we have
$v_{1}=v_{2}$. As a result, the sequence
$\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ converges weakly to $v$, which is a
common fixed point of the family $\left\\{T_{i}\right\\}_{i=1}^{m}$. ∎

##  5 Proofs of the main results

  * Proof of Theorem 3.1.

(i) By Lemma 4.2, we have

$\cap_{i=1}^{m}C_{i}\subset\cap_{n=0}^{\infty}\mathrm{Fix}(S_{n}).$ (11)

Let $n\in\mathbb{N}$. By Lemma 4.1, $S_{n}$ is strongly nonexpansive and hence
nonexpansive. Since $\mathrm{Fix}(S)\subset\cap_{i=1}^{m}C_{i}$, it follows
that $\cap_{i=1}^{m}C_{i}\not=\emptyset$. Relation (11) and Remark 3 imply
that $S_{n}$ is quasi-nonexpansive. Applying Theorem 1.18, we arrive at the
result.
(ii) By Lemma 4.2, Lemma 4.1 and Corollary 1.9,

$\mathrm{Fix}(Q)=\cap_{i=1}^{m}C_{i}\not=\emptyset.$ (12)

By Lemma 4.1, $Q$ is strongly nonexpansive and therefore nonexpansive. By
Lemma 1.15, it is asymptotically regular. The desired result now follows from
(12) and Theorem 1.19. ∎

######  Remark 5.

In light of Lemma 4.2, part (ii) of Theorem 3.1 can also be proved by using
Theorem 2.5 (without using Theorem 1.19): define a quasi-periodic mapping $h$
from $\mathbb{N}$ onto $\left\\{1,\dots,j_{f}+1\right\\}$ by
$h\left(n\right):=n\,\,\mathrm{mod\,}\,\left(j_{f}+1\right)+1$ for each
$n\in\mathbb{N}$ and a sequence of operators
$\left\\{T_{i}\right\\}_{i=1}^{j_{f}+1}$ by $T_{i}:=S_{i-1}$ for each
$i\in\left\\{1,\dots,j_{f}+1\right\\}$.

  * Proof of Theorem 3.2.

Let $F:=\left\\{S_{n}\mid\,n\in\left\\{0,\dots,M-1\right\\}\right\\}$. Since
the sequence
$\left\\{\left\\{C_{m,r}\left(n\right)\left(j\right)\right\\}_{j=1}^{r}\right\\}_{n=0}^{\infty}$
is $M$-quasi-periodic, it is clear that $F$ contains all possible operators
$S_{n}$ (for all $n\in\mathbb{N}$). Set
$T:\left\\{1,\dots,p\right\\}\rightarrow F$ to be the bijection, where $p$ is
the cardinality of the set $F$. Define
$h:\mathbb{N}\rightarrow\left\\{1,\dots,p\right\\}$ by
$h\left(n\right)=T^{-1}\left(S_{n}\right)$. Clearly, $h$ is a quasi-periodic
mapping onto $\left\\{1,\dots,p\right\\}$. Then $S_{n}=T_{h\left(n\right)}$
for each natural number $n$. Now (i) follows from Lemma 4.1 and Theorem 2.5,
while (ii) follows from (i) and Lemma 4.2. ∎

  * Proof of Theorem 3.3.

Since $\cap_{j=1}^{k}\mathrm{Fix}(T_{j})\not=\emptyset$, by Theorem 2.5, the
sequence $\left\\{P_{n}x\right\\}_{n=0}^{\infty}$ converges weakly to a point
$x_{*}\in\cap_{j=1}^{k}\mathrm{Fix}(T_{j})$. Since $\cap_{i=1}^{m}C_{i}$ has
an interior point, by Lemma 4.2,
$\cap_{n=1}^{j_{f}}\mathrm{Fix}(S_{n})=\cap_{i=1}^{m}C_{i}\not=\emptyset$. By
Lemma 4.1 and Corollary 1.9,
$\mathrm{Fix}(Q)=\cap_{n=1}^{j_{f}}\mathrm{Fix}(S_{n})$. As a result, in both
cases (i) and (ii)

$x_{*}\in\cap_{j=1}^{k}\mathrm{Fix}(T_{j})\subset\mathrm{Fix}(Q)=\cap_{n=1}^{j_{f}}\mathrm{Fix}(S_{n})=\cap_{i=1}^{m}C_{i}.$

∎

## Funding

Simeon Reich was partially supported by the Israel Science Foundation (Grant
820/17), the Fund for the Promotion of Research at the Technion and by the
Technion General Research Fund.

## Acknowledgments

This work is accepted for publication in the journal Optimization Methods and
Software, November 2022.

## References

  * [1] F. J. Aragón Artacho, J. M. Borwein and M. K. Tam, _Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem_ , J. Global Optim. 65 (2016), pp. 309–327.
  * [2] F. J. Aragón Artacho, Y. Censor and A. Gibali, _The cyclic Douglas-Rachford algorithm with r-sets-Douglas-Rachford operators_ , Optim Methods Softw. 34 (2019), pp. 875–889.
  * [3] K. Barshad, S. Reich and R. Zalas, _Strong coherence and its applications to iterative methods_ , J. Nonlinear Convex Anal. 20 (2019), pp. 1507–1523.
  * [4] H. H. Bauschke and J. M. Borwein, _On projection algorithms for solving convex feasibility problems_ , SIAM Rev. 38 (1996), pp. 367–426.
  * [5] H. H. Bauschke and P. L. Combettes, _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_ , 2nd ed., Springer New York, 2017.
  * [6] H. H Bauschke and W. M. Moursi, _On the Douglas-Rachford algorithm_ , Math. Program. Ser. A 164 (2017), pp. 263–284.
  * [7] J. M. Borwein M. K. Tam, _A cyclic Douglas-Rachford iteration scheme_ , J. Optim Theory Appl. 160 (2014), pp. 1–29.
  * [8] R. I. Boţ, E. R. Csetnek and D. Meier, _Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces_ , Optim Methods Softw. 34 (2019), pp. 489–514.
  * [9] A. Cegielski, _Iterative Methods for Fixed Point Problems in Hilbert Spaces_ , Springer, Berlin, 2012.
  * [10] Y. Censor, A. Gibali and S. Reich, _A von Neumann alternating method for finding common solutions to variational inequalities_ , Nonlinear Anal. 75 (2012), pp. 4596–4603.
  * [11] Y. Censor and R. Mansour, _New Douglas-Rachford algorithmic structures and their convergence analyses_ , SIAM J. Optim. 26 (2016), pp. 474–487.
  * [12] J. Douglas and H. H Rachford, _On the numerical solution of heat conduction problems in two and three space variables_ , Trans. Amer. Math. Soc. 82 (1956), pp. 421–439.
  * [13] J. M. Dye and S. Reich, _Unrestricted iterations of nonexpansive mappings in Hilbert space_ , Nonlinear Anal. 18 (1992), pp. 199–597.
  * [14] O. S. Iyiola, C. D. Enyi and Y. Shehu, _Reflected three-operator splitting method for monotone inclusion problem_ , Optim Methods Softw. (2021) , DOI: 10.1080/10556788.2021.1924715
  * [15] V. I. Kolobov, S. Reich and R. Zalas, _Finitely convergent deterministic and stochastic iterative methods for solving convex feasibility problems_ , Mathematical Programming, accepted for publication.
  * [16] Z. Opial, _Weak convergence of the sequence of successive approximations for nonexpansive mappings_ , Bull. Am. Math. Soc. 73 (1967), pp. 591–597.


=~& \sum_{j}\theta_j^* \sum_{k}{\pi_k} \E\left[ \exp\left\{s \nu \left((P-P_n) \left(\ell_{e_k}(Z) - \ell_{e_j}(Z)\right) - \frac{\mu}{\nu\, C_b^2} P(\ell_{e_k}(Z) - \ell_{e_j}(Z))^2\right)\right\}\right]
\end{align}

Invoking Lemma <ref> with:

\begin{align}
V_i =~& \ell_{e_j}(Z_i) - \ell_{e_k}(Z_i)\\
c_0 =~& \frac{\mu}{\nu C_b^2}\\
\lambda = \frac{s \nu}{n}\\
c=~& 2b C_b
\end{align}

Hence we need:

\begin{align}
\lambda := \frac{s\nu}{n} \leq \frac{2c_0}{1 + 2c_0c} =: \frac{2 \mu}{\nu C_b^2 (1+ 2 \frac{\mu}{\nu C_b^2} 2 b C_b)} = \frac{2 \mu}{(\nu C_b^2+ 4 \mu b C_b )} \implies s \leq \frac{2 \mu n}{\nu C_b (\nu C_b+ 4 \mu b)}
\end{align}

§.§ Putting it all together

With the choice of $\beta$ and $\mu$ as described in the theorem statement, we can invoke the above Lemmas. Letting $C_b(\hat{g})$ the Lipschitz constant associated with an estimate $\hat{g}$, we have that w.p. $1-\delta$:

\begin{align}
R(\hat{\theta}) \leq \min_{j}\left( R(e_j)  +\frac{\beta}{n}\log(1/\pi_j)\right) + O\left(  \frac{\log(1/\delta) \max\{\frac{1}{\mu} C_b(\hat{g})^2, b\, C_b(\hat{g}) \}}{n}\right) + \frac{2}{\mu} \error(\hat{g})^2
\end{align}

§.§ Basic concentration proofs

For any random variable $Z$, if $\E\left[\exp\left\{ Z\right\} \right] \leq 1$, then $\Pr(Z \geq \log(1/\delta)) \leq \delta$.

Suppose that one shows that:

\begin{align}
\E\left[\exp\left\{ Z\right\} \right] \leq 1
\end{align}

Then by Markov's inequality:

\begin{align}
\Pr(Z \geq x) = \Pr(\exp(Z) \geq \exp(x)) \leq \frac{\E[\exp(Z)]}{\exp(x)}\leq \frac{1}{\exp(x)} = \exp(-x)
\end{align}

\begin{align}
\Pr(Z\geq \log(1/\delta)) \leq \delta
\end{align}

Suppose $\epsilon_1, \ldots, \epsilon_n$ are independent Rademacher random variables drawn equiprobably in $\{-1, 1\}$ and that $a_1,\ldots, a_n$ are real numbers. Then:

\begin{align}
\E_{\epsilon_{1:n}}\left[\exp\left\{\frac{1}{n} \sum_i \epsilon_i a_i \right\}\right] \leq \exp\left\{\frac{1}{2n^2} \sum_i a_i^2 \right\}
\end{align}

First note that for by the derivation in Example 2.2 of <https://www.stat.berkeley.edu/ mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf>, we have that:

\begin{align}
\E[\exp(\epsilon_i a_i/n)] \leq \exp(a_i^2/2n^2)
\end{align}

Invoking now independence of the $\epsilon_i$ we have:

\begin{align}
\E_{\epsilon_{1:n}}\left[\exp\left\{\frac{1}{n}\sum_i \epsilon_i a_i \right\}\right] =~& \E_{\epsilon_{1:n}}\left[\prod_{i=1}^n \exp\left\{\epsilon_i a_i/n \right\}\right]\\
=~& \prod_{i=1}^n \E_{\epsilon_{1:n}}\left[ \exp\left\{\epsilon_i a_i/n \right\}\right] \tag{independence}\\
\leq~& \prod_{i=1}^n \exp\left(\frac{a_i^2}{2n^2}\right) = \exp\left\{\frac{1}{2n^2} \sum_i a_i^2 \right\}
\end{align}

The following proposition can also be proven as an application of Bernstein's inequality.

Let $V_1,\ldots, V_n$ be i.i.d. random variables, such that $|V_i|\leq c$ a.s.. Let $c_0>0$, then for any $0< \lambda < \frac{2c_0}{1+ 2c_0 c}$:

\begin{align}
\E\left[\exp\left\{n\lambda \left( \frac{1}{n}\sum_i (V_i - \E[V_i] - c_0 \E[V_i^2]\right)\right\}\right] \leq 1
\end{align}

§.§ Auxiliary Lemmas

let $\mathcal{F}$ be a function class, $A_f, f \in \mathcal{F}$ be a given function on $\mathcal{F}$ and $\Phi$ be a convex non-decreasing function then

\mathbb{E} \Phi\left(\sup _{f \in \mathcal{F}}\left[\mathbb{E}[f(Z)]-\frac{1}{n}\sum_{i=1}^{n} f(Z_i)-A_f\right]\right) \leq \mathbb{E} \Phi\left(2 \sup _{f \in \mathcal{F}}\left[\frac{1}{n}\sum_{i=1}^{n} \varepsilon_i f(Z_i)-A_f\right]\right)

Let $F: \mathbb{R}_{+} \rightarrow \mathbb{R}_{+}$be convex and increasing. Let further $\varphi_i: \mathbb{R} \rightarrow \mathbb{R}, i \leq N$, be such that $|\varphi_i(s) - \varphi_i(t)|\leq |s-t|$ and $\varphi_i(0)=0$. Then, for any bounded subset $T$ in $\mathbb{R}^N$

\mathbb{E} F\left(\frac{1}{2}\left\|\sum_{i=1}^N \varepsilon_i \varphi_i\left(t_i\right)\right\|_T\right) \leq \mathbb{E} F\left(\left\|\sum_{i=1}^N \varepsilon_i t_i\right\|_T\right)

§ PROOF OF COROLLARIES FOR SQUARE LOSSES

Note that if we assume that $\hat{Y}(\hat{g})$ is uniformly bounded for any $\hat{g}\in G$ with $d(\hat{g},g_0)\leq \epsilon$ for some constant $\epsilon$ and since for $n$ larger than the designated constant, we have that w.p. $1-\delta$, $\hat{Y}(\hat{g})$ is absolutely and uniformly bounded by $U$. Moreover, $f_j(X)$ is absolutely and uniformly bounded by $U$. Note that by an exact first order Taylor expansion:

\begin{align}
|\ell(Z; f(X), g) - \ell(Z; f_*(X), g)|=~&\left|\int_{0}^1 2 (\hat{Y}(g) - (1-\tau)f(X) - \tau f_*(X)) (f(X) - f_*(X))d\tau\right|\\
~&\leq 2\left(\sup_{f\in F} |f(X)| + |\hat{Y}(g)|\right) |f(X) - f_*(X)|\\
~&\leq 2\,U\,|f(X) - f_*(X)|
\end{align}

Thus the loss function is $C_b=2U$ lipschitz and absolutely bounded by $4U^2$. Moreover, we have that the loss function $\ell(Z; f(X), g_0)$ is $2$-strongly convex in $f$ in expectation. Thus, we can take $\sigma=2$ in Theorem <ref>. Thus we can apply the main theorem with $\nu=1/2$, $\mu=1/14$ and $\beta=\max\{112\,U^2, 56 U^3\}$.

Finally, we analyze the quantity ${\cal E}(\hat{g})$. We first note that for any $\theta, g$, we have:

\begin{align}
\ell_{\theta,g}(Z) - \ell_{\theta^*, g}(Z) ~&= (\hat{Y}(g) - f_{\theta}(X))^2 - (\hat{Y}(g) - f_{\theta^*}(X))^2\\
=~& f_{\theta}(X)^2 - f_{\theta^*}(X)^2 + 2 \hat{Y}(g)\, (f_{\theta^*}(X) - f_{\theta}(X))
\end{align}

Moreover, for any $\theta \in \Theta$:

\begin{align}
\sum_{j} \theta_j \ell_{e_j,g}(Z) =~& \sum_{j} \theta_j (\hat{Y}(g) - f_{j}(X))^2 \\
=~& \hat{Y}(g)^2 \sum_{j} \theta_j + \sum_{j}\theta_j f_{j}(X)^2 - 2\sum_j \theta_j \hat{Y}(g) f_j(X)\\
=~& \hat{Y}(g)^2 + \sum_{j}\theta_j f_{j}(X)^2 - 2\sum_j \theta_j \hat{Y}(g) f_j(X) \tag{$\sum_{j} \theta_j=1$}\\
=~& \hat{Y}(g)^2 + \sum_{j}\theta_j f_{j}(X)^2 - 2 \hat{Y}(g) f_\theta \tag{$f_\theta = \sum_{j} \theta_j f_j$}
\end{align}

Thus we have that:

\begin{align}
\sum_{j} \theta_j \ell_{e_j,g}(Z) - \sum_{j} \theta_j^* \ell_{e_j,g}(Z) = \sum_{j}(\theta_j-\theta_j^*) f_{j}(X)^2 + 2 \hat{Y}(g) (f_{\theta^*}(X) - f_\theta(X))
\end{align}

Then by the definition of $\tilde{\ell}_{\theta, g}$, we have:

\begin{align}
\ell_{\theta,g}(Z) - \ell_{\theta^*, g}(Z) = (1- \nu) (f_{\theta}(X)^2 - f_{\theta^*}(X)^2) + \nu \sum_{j}(\theta_j-\theta_j^*) f_{j}(X)^2 + 2\hat{Y}(g) (f_{\theta^*}(X) - f_\theta(X))
\end{align}

Only the last part depends on the parameter $g$. Thus we get:

\begin{align}
{\cal E}(\hat{g}) =~& 2 \E[(\hat{Y}(g_0) - \hat{Y}(\hat{g}))(f_{\theta^*}(X) - f_{\hat{\theta}}(X))]
=~ 2 \E\left[\E\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]\, (f_{\theta^*}(X) - f_{\hat{\theta}}(X))\right]
\end{align}

Applying a Cauchy-Schwarz inequality, we have:

\begin{align}
{\cal E}(\hat{g}) =~&  2 \sqrt{\E\left[\E\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]^2\right]}\, \|f_{\theta^*}-f_{\hat{\theta}}\|_{L^2}
\end{align}

and we can take:

\begin{align}
\error(\hat{g}) = 2\sqrt{\E\left[\E\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]^2\right]}
\end{align}

in Theorem <ref>. Finally, note that since $\E[\hat{Y}(g_0)\mid X] = \tau_0(X)$, the excess risk evaluated at the true parameters satisfies that:

\begin{align}
R(\theta, g_0) - R(\theta', g_0) =~& \E\left[f_{\theta}(X)^2 - f_{\theta'}(X)^2 + 2\hat{Y}(g_0)(f_{\theta}(X) -f_{\theta'}(X))\right]\\
=~& \E\left[f_{\theta}(X)^2 - f_{\theta'}(X)^2 + 2\tau_0(X)\, (f_{\theta}(X) -f_{\theta'}(X))\right]\\
=~& \E\left[(f_{\theta}(X) - \tau_0(X))^2 - (f_{\theta'}(X) - \tau_0(X))^2\right]\\
=~& \|f_\theta -\tau_0\|^2 - \|f_{\theta'} - \tau_0\|^2
\end{align}

Thus we have that:

\begin{align}
R(\hat{\theta}, g_0) - \min_{j} R(e_j, g_0) = \|f_{\hat{\theta}} - \tau_0\|^2 - \min_{j} \|f_j - \tau_0\|^2
\end{align}

The proof is identical to Corollary <ref>, but we simply replace the application of the Cauchy-Schwarz inequality with the inequality:

\begin{align}
2 \E\left[\E\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]\, (f_{\theta^*}(X) - f_{\hat{\theta}}(X))\right] \leq~& 2 \E\left[\left|\E\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]\right|\right]\, \|f_{\theta_*} - f_{\hat{\theta}}\|_{L^{\infty}}\\
\leq~& 2\, C\, \E\left[\left|\E\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]\right|\right]\, \|f_{\theta_*} - f_{\hat{\theta}}\|_{L^{2}}^\gamma
\end{align}

§.§ Relaxed Nuisance Guarantees Under Eigenvalue Condition

Let $F$ be the random column vector defined as $F := (f_{1}(X), \cdots, f_{M}(X))$. Suppose that $\E[FF']\succeq c I$ and $\left\|\|F\|_{\infty}\right\|_{L^{\infty}} \leq U$. Then we can take $\gamma=1$ and $C = 2\, U \sqrt{\frac{M}{c}}$ in Corollary <ref>.

Here, the number of models $M$ and not the logarithm of them appears. However, assuming that the nuisance error term decays faster than $n^{-1/2}$, this linear in $M$ term will only appear in the lower-order terms.

Let $F$ be the random column vector defined as $F := (f_{1}(X), \cdots, f_{M}(X))$ and assume that $\left\|\|F\|_{\infty}\right\|_{L^{\infty}} \leq U$. Noting that:

\begin{align}
f_{\theta*}(X)-f_{\hat{\theta}}(X) = F'(\theta^* - \hat{\theta}).
\end{align}

we have:

\begin{align}
\|f_{\theta*}(X)-f_{\hat{\theta}}(X)\|_{L^\infty}~&\leq \left\|\|F\|_{\infty}\right\|_{L^{\infty}} \|\theta^* - \hat{\theta}\|_1 \\
~&\leq U\, \|\theta^* - \hat{\theta}\|_1 \leq U \sqrt{M} \|\theta^* - \hat{\theta}\|_2
\end{align}

Then we if we further assume that $\E[FF']\succeq c I$, i.e. the CATE models all contain independent signal components and are not colinear. Then we can write:

\begin{align}
\|f_{\theta*}(X)-~&f_{\hat{\theta}}(X)\|_{L^\infty} \leq U \sqrt{M} \sqrt{\|\theta^* - \hat{\theta}\|_2^2}\\
\leq~& U \sqrt{M} \sqrt{\frac{1}{c} (\theta^* - \hat{\theta})\E[FF'](\theta^* - \hat{\theta})}\\
=~& U \sqrt{M} \sqrt{\frac{1}{c} \E[(F'(\theta^* - \hat{\theta}))^2]}\\
=~& U \sqrt{M} \frac{1}{\sqrt{c}} \|f_{\theta^*} - f_{\hat{\theta}}\|_{L^2}
\end{align}

Thus under these further assumptions, we can set:

\begin{align}
C = 2\, U \sqrt{\frac{M}{c}}
\end{align}

in Corollary <ref>.

§ PROOF OF MAIN THEOREM WITHOUT SAMPLE SPLITTING

We will solely change the statement and proof of Lemma <ref> and subsequently Lemma <ref> and Lemma <ref> will be invoked at $g_0$ and not $\hat{g}$. The rest of the Lemmas do not depend on whether $\hat{g}$ was trained on the same samples or not as the ones that were used to construct $\hat{\theta}$.

Define the centered and offset empirical processes:

\begin{align}
Z_{n,1} =~& (1-\nu)(P-P_n) (\ell_{\hat{\theta}, g_0}(Z) - \ell_{\theta^*, g_0}(Z)) - \mu \sum_{j} \hat{\theta}_j \|f_j - f_{\theta^*}\|^2 -\frac{1}{s}K(\hat{\theta})\\
Z_{n,2} =~& \nu(P-P_n) \sum_{j} (\hat{\theta}_j-\theta_j^*)\ell_{e_j, g_0}(Z) - \mu \hat{\theta}^\top H \theta^* -\frac{1}{s}K(\hat{\theta})& H_{ij} = \|f_i - f_j\|^2 \\
Z_{n,3} =~& \max_{j}\left[ (P-P_n) (f_{j}(X) - f_{\theta^*}(X))^2 - \mu\|f_j - f_{\theta^*}\|^2 + \frac{1}{s}\log(\pi_j)\right]\\
Z_{n,4} =~& (P-P_n) (\hat{Y}(\hat{g}) - \hat{Y}(g_0))^2
\end{align}

Assume that:

\begin{align}
{\cal E}(\hat{g}) := P(\tilde{\ell}_{\hat{\theta},g_0}(Z) - \tilde{\ell}_{\theta^*,g_0}(Z)) - P(\tilde{\ell}_{\hat{\theta},\hat{g}}(Z) - \tilde{\ell}_{\theta^*,\hat{g}}(Z)) \leq \error(\hat{g})\, \|f_\theta - f_{\theta^*}\|
\end{align}

and $\ell(f, g_0)$ is $1$-strongly convex in expectation with respect to $f$ since we consider square losses. For any $\mu \leq \min\{\nu, 1-\nu\} \frac{1}{14}$:

\begin{align}
R(\hat{\theta}) \leq \min_{j} R(e_j) + 2\, (Z_{n,1} + Z_{n,2} + Z_{n,3} + Z_{n,4}) + \frac{1}{\mu}\error(\hat{g})^2
\end{align}

\begin{align}
\tilde{R}(\hat{\theta}, g_0) - \tilde{R}(\theta^*, g_0) =~&
P(\tilde{\ell}_{\hat{\theta},g_0}(Z) - \tilde{\ell}_{\theta^*,g_0}(Z))\\
P(\tilde{\ell}_{\hat{\theta},\hat{g}}(Z) - \tilde{\ell}_{\theta^*,\hat{g}}(Z)) + {\cal E}(\hat{g})\\
\leq~&
(P - P_n)(\tilde{\ell}_{\hat{\theta}, \hat{g}}(Z) - \tilde{\ell}_{\theta^*, \hat{g}}(Z)) - \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + {\cal E}(\hat{g})
\tag{By optimality of $\hat{\theta}$, $P_n(\tilde{\ell}_{\hat{\theta}, \hat{g}}(Z) - \tilde{\ell}_{\theta^*, \hat{g}}(Z)) {+ \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*))}\leq 0$}\\
=~& (P - P_n)(\tilde{\ell}_{\hat{\theta}, g_0}(Z) - \tilde{\ell}_{\theta^*, g_0}(Z)) + \Delta(\hat{g}, \hat{\theta}) - \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + {\cal E}(\hat{g})\\
=~& \mu\sum_j \hat{\theta}_j \|f_j - f_{\theta^*}\|^2 + \mu \hat{\theta}^\top H\theta^*+ Z_{n,1} + Z_{n,2}\\
~& +\frac{2}{s}K(\hat{\theta}) - \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + \Delta(\hat{g}, \hat{\theta}) + {\cal E}(\hat{g}) \tag{definition of $Z_{n,1}, Z_{n,2}$}
\end{align}

\begin{align}
\Delta(\hat{g}, \hat{\theta}) = (P - P_n)\left\{\tilde{\ell}_{\hat{\theta}, \hat{g}}(Z) - \tilde{\ell}_{\theta^*, \hat{g}}(Z) - \left(\tilde{\ell}_{\hat{\theta}, g_0}(Z) - \tilde{\ell}_{\theta^*, g_0}(Z)\right)\right\}
\end{align}

For the case of square losses, the above difference in differences simplifies to:

\begin{align}
\Delta(\hat{g}, \hat{\theta}) =~& (P - P_n)\left\{2 (\hat{Y}(\hat{g}) - \hat{Y}(g_0))\, (f_{\hat{\theta}}(X) - f_{\theta^*}(X))\right\}\\
=~& \sum_{j} \hat{\theta}_j \left[(P - P_n)\left\{2 (\hat{Y}(\hat{g}) - \hat{Y}(g_0))\, (f_j(X) - f_{\theta^*}(X))\right\} - \frac{1}{s}\log(\frac{1}{\pi_j})\right] + \frac{1}{s}K(\hat{\theta}) \\
=~& \mu \sum_{j} \hat{\theta}_j \|f_j - f_{\hat{\theta}^*}\|^2 +\frac{1}{s}K(\hat{\theta})\\
~&+ \sum_{j} \hat{\theta}_j \left[(P - P_n)\left\{2 (\hat{Y}(\hat{g}) - \hat{Y}(g_0))\, (f_j(X) - f_{\theta^*}(X))\right\} - \mu \|f_j - f_{\theta^*}\|^2+\frac{1}{s}\log(\pi_j)\right]\\
=~& \mu \sum_{j} \hat{\theta}_j \|f_j - f_{\hat{\theta}^*}\|^2 +\frac{1}{s}K(\hat{\theta}) \\
~& + \max_{\theta\in \Theta} \sum_{j} \theta_j \left[(P - P_n)\left\{2 (\hat{Y}(\hat{g}) - \hat{Y}(g_0))\, (f_j(X) - f_{\theta^*}(X))\right\} - \mu \|f_j - f_{\theta^*}\|^2 + \frac{1}{s}\log(\pi_j)\right]
\end{align}

Since the last term is linear in $\hat{\theta}$ and $\Theta$ is the simplex, it is maximized at a corner, which yields:

\begin{align}
\Delta(\hat{g}, \hat{\theta}) \leq~& \mu \sum_{j} \hat{\theta}_j \|f_j - f_{\hat{\theta}^*}\|^2 +\frac{1}{s}K(\hat{\theta})\\
~&+ \max_{j} \left[(P - P_n)\left\{2 (\hat{Y}(\hat{g}) - \hat{Y}(g_0))\, (f_j(X) - f_{\theta^*}(X))\right\} - \mu \|f_j - f_{\theta^*}\|^2+ \frac{1}{s}\log(\pi_j)\right]\\
\leq~& \mu \sum_{j} \hat{\theta}_j \|f_j - f_{\hat{\theta}^*}\|^2 +\frac{1}{s}K(\hat{\theta}) + (P - P_n)(\hat{Y}(\hat{g}) - \hat{Y}(g_0))^2 \\
~& +\max_{j} \left[(P - P_n)(f_j(X) - f_{\theta^*}(X))^2 - \mu \|f_j - f_{\theta^*}\|^2 + \frac{1}{s}\log(\pi_j)\right]\\
\leq~& \mu \sum_{j} \hat{\theta}_j \|f_j - f_{\hat{\theta}^*}\|^2 + Z_{n,3} + Z_{n,4} + \frac{1}{s}K(\hat{\theta})
\end{align}

By simple algebraic manipulations note that for any $\theta\in \Theta$:

\begin{align}
\sum_j \hat{\theta}_j \|f_j - f_{\theta^*}\|^2 = V(\hat{\theta}) + \|f_{\hat{\theta}} - f_{\theta^*}\|^2 \\
\hat{\theta}^\top H \theta^* = V(\hat{\theta}) + V(\theta^*) + \|f_{\hat{\theta}} - f_{\theta^*}\|^2
\end{align}

Letting $Z_n=Z_{n,1} + Z_{n,2} + Z_{n,3} + Z_{n,4}$, we have:

\begin{align}
\tilde{R}(\hat{\theta}, g_0) - \tilde{R}(\theta^*, g_0) \leq~& 3\mu V(\hat{\theta}) + \mu V(\theta^*) + 3\mu \|f_{\hat{\theta}} - f_{\theta^*}\|^2 + Z_n +\frac{3}{s}K(\hat{\theta}) - \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + {\cal E}(\hat{g})\\
\leq~& 3\mu V(\hat{\theta}) + \mu V(\theta^*) + 3\mu \|f_{\hat{\theta}} - f_{\theta^*}\|^2 + Z_n\\
~& +\frac{3}{s}K(\hat{\theta}) - \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + \error(\hat{g})\, \|f_{\hat{\theta}} - f_{\theta^*}\|\\
\leq~& 3\mu V(\hat{\theta}) + \mu V(\theta^*) + 4\mu \|f_{\hat{\theta}} - f_{\theta^*}\|^2 + Z_n \\
~& +\frac{3}{s}K(\hat{\theta}) -\frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + \frac{1}{\mu}\error(\hat{g})^2  \label{eqn:first-upper-no-split}
\end{align}

where the last inequality follows by an application of the AM-GM inequality. By Lemma <ref>, we have:

\begin{align}
\tilde{R}(\hat{\theta}, g_0) - \tilde{R}(\theta^*, g_0) \geq~& \mu (V(\theta^*) - V(\hat{\theta})) - \frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) + \left(\frac{(1-\nu)\sigma}{2} - \mu\right)\|f_{\hat{\theta}} - f_{\theta^*}\|^2\\
\geq~& \mu (V(\theta^*) - V(\hat{\theta})) -\frac{\beta}{n}(K(\hat{\theta})-K(\theta^*))+ 8\mu  \|f_{\hat{\theta}} - f_{\theta^*}\|^2  \tag{Since: $\sigma=2$ and $\mu \leq \frac{(1-\nu)}{18}\implies \frac{(1-\nu)\sigma}{2} \geq 9\mu$}
\end{align}

Combining the latter upper and lower bound on $\tilde{R}(\hat{\theta}, g_0) - \tilde{R}(\theta^*, g_0)$, we have:

\begin{align}
4\mu \|f_{\hat{\theta}} - f_{\theta^*}\|^2 \leq 4\mu V(\hat{\theta}) + Z_n + \frac{3}{s}K(\hat{\theta})+ \frac{1}{\mu} \error(\hat{g})^2
\end{align}

Plugging the bound on $4\mu\|f_{\hat{\theta}} - f_{\theta^*}\|^2$ back into Equation (<ref>) we have:

\begin{align}
\tilde{R}(\hat{\theta}, g_0) - \tilde{R}(\theta^*, g_0) \leq 7\mu V(\hat{\theta}) + \mu V(\theta^*) + 2\, Z_n -\frac{\beta}{n}(K(\hat{\theta})-K(\theta^*)) +\frac{6}{s}K(\hat{\theta}) + \frac{2}{\mu} \error(\hat{g})^2
\end{align}

By Lemma <ref>, we have:

\begin{align}
R(\hat{\theta}, g_0) \leq~& \tilde{R}(\theta^*, g_0) + \mu V(\theta^*)+ \left(7\mu - \frac{\nu \sigma}{2}\right) V(\hat{\theta}) + 2 Z_n + \frac{2}{\mu} \error(\hat{g})^2 \\
~& + \left(\frac{6}{s}-\frac{\beta}{n}\right)K(\hat{\theta}) + \frac{\beta}{n}K(\theta^*)\\
\leq~& \tilde{R}(\theta^*, g_0) + \mu V(\theta^*)+ \frac{\beta}{n}K(\theta^*) +2 Z_n + \frac{2}{\mu} \error(\hat{g})^2   \tag{since, $\sigma=2$, $\mu\leq \frac{\nu}{14}$ and $V(\hat{\theta})>0$ and $\beta\geq \frac{6n}{s}$ and $K(\hat{\theta})\geq0$}\\
=~& \min_{\theta\in \Theta} \left[\tilde{R}(\theta, g_0) + \mu V(\theta) + \frac{\beta}{n}K(\theta^*)\right] + 2 Z_n + \frac{2}{\mu} \error(\hat{g})^2 \tag{Since $\theta_*$ minimizes $H(\theta, g_0)$}\\
\leq~& \min_{j} \left[\tilde{R}(e_j, g_0) + \mu V(e_{j}) + \frac{\beta}{n}\log(\frac{1}{\pi_j})\right]+ 2 Z_n + \frac{2}{\mu} \error(\hat{g})^2 \\
=~& \min_{j} \left[R(e_j, g_0) + \frac{\beta}{n}\log(\frac{1}{\pi_j})\right]+ 2 Z_n + \frac{2}{\mu} \error(\hat{g})^2 \tag{Since $\tilde{R}(e_j, g_0)=R(e_j, g_0)$ and $V(e_j)=0$ for all $e_j$}
\end{align}

Assuming that $f\in F$ are uniformly and absolutely and bounded in $[-b,b]$, for any
$s\leq \frac{n \mu}{2b^2 (1+\mu)}$:

\begin{align}
{\Pr\left(Z_{n,3} \geq \frac{\log(1/\delta)}{s}\right) \leq \delta}
\end{align}

It suffices to show that:

\begin{align}
I := \E\left[\exp s Z_{n,3} \right] \leq 1
\end{align}

Note first that:

\begin{align}
\E\left[\exp s Z_{n,3} \right] =~& \E\left[\exp\left\{s
\max_{j} \left[(P-P_n) (f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu P (f_j(Z) - f_{\theta^*}(Z))^2 + \frac{1}{s}\log(\pi_j)\right]\right\}\right]\\
\leq~& \E\left[\max_j \exp\left\{s \left( (P-P_n) (f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu P (f_j(Z) - f_{\theta^*}(Z))^2+ \frac{1}{s}\log(\pi_j)\right)\right\}\right]\\
\leq~&\sum_j \pi_j \E\left[\exp\left\{s \left( (P-P_n) (f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu P (f_j(Z) - f_{\theta^*}(Z))^2\right)\right\}\right]\\
\leq~& \max_j \E\left[\exp\left\{s \left( (P-P_n) (f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu P (f_j(Z) - f_{\theta^*}(Z))^2\right)\right\}\right]
\end{align}

Since $f_j(Z)\in [-b, b]$, we have that $f_j(Z) - f_{\theta^*}(Z)\in [-2b, 2b]$. Thus:

\begin{align}
(f_j(Z)-f_{\theta^*}(Z))^2\geq \frac{(f_j(Z)-f_{\theta^*}(Z))^2}{4b^2} (f_j(Z)-f_{\theta^*}(Z))^2 = \frac{1}{4b^2} (f_j(Z)-f_{\theta^*}(Z))^4.
\end{align}

\begin{align}
I \leq~& \max_j \E_{Z_{1:n}}\left[ \exp\left\{s \left(\left(P_n - P\right)(f_{j}(Z) - f_{\theta^*}(Z))^2 - \frac{\mu}{4b^2} P (f_{j}(X) - f_{\theta^*}(X))^4 \right)\right\}\right]
\end{align}

It suffices to show that each term $j$ is upper bounded by $1$.

Applying Lemma <ref> with:

\begin{align}
V_i =~& (f_j(Z_i) - f_{\theta^*}(Z_i))^2\\
c =~& 4b^2\\
\lambda =~& s\\
c_0 =~& \frac{\mu}{4b^2}
\end{align}

we have that as long as:

\begin{align}
\lambda := \frac{s}{n} \leq \frac{2c_0}{1+2c_0 c} =: \frac{2\cdot \mu/4b^2}{1 + \mu} = \frac{\mu}{2b^2(1+\mu)}
\end{align}

\begin{align}
\E_{Z_{1:n}}\left[ \exp\left\{s \left(\left(P_n - P\right)(f_{j}(Z) - f_{\theta^*}(Z))^2 - \frac{\mu}{4b^2} P (f_{j}(X) - f_{\theta^*}(X))^4 \right)\right\}\right]\leq 1
\end{align}

Thus we need that:

\begin{align}
s \leq \frac{n \mu}{2b^2 (1+\mu)}
\end{align}

which is satisfied by our assumptions on $s$.

To bound $Z_{n,4}$ we will use the following concentration inequality of based on critical radius (e.g. [45]). See [12] for a proof of this theorem:

For any $h\in \Hcal := \prod_{i=1}^d \Hcal_i$ be a multi-valued outcome function, that is almost surely absolutely bounded by a constant. Let $\ell(Z; h(W))\in \R$ be a loss function that is $L$-Lipschitz in $h(W)$, with respect to the $\ell_2$ norm. Fix any $h_*\in \Hcal$ and let $\delta_n=\Omega\left(\sqrt{\frac{d\,\log\log(n) + \log(1/\zeta)}{n}}\right)$ be an upper bound on the critical radius of $\shull(\Hcal_i-h_{i,*})$ for $i\in [d]$. Then w.p. $1-\zeta$:

\begin{align}
\forall h\in \Hcal: \left|(P_n - P)\left[\ell(Z; h(W)) - \ell(Z; h_*(W))\right]\right| = 18\,L\,\left(d\, \delta_n \sum_{i=1}^d \|h_i - h_{i,*}\|_{L_2} + d\,\delta_n^2\right)
\end{align}

If the loss is linear in $h(W)$, i.e. $\ell(Z; h(W) + h'(W)) = \ell(Z; h(W)) + \ell(Z; h'(W))$ and $\ell(Z;\alpha h(W)) = \alpha \ell(Z;h(W))$ for any scalar $\alpha$, then it suffices that we take $\delta_n=\Omega\left(\sqrt{\frac{\log(1/\zeta)}{n}}\right)$ that upper bounds the critical radius of $\shull(\Hcal_i-h_{i,*})$ for $i\in [d]$.

Let $r_n$ denote the critical radius of the function space $\operatorname{star}(Y_G)$ where $Y_G := \{ (\hat{Y}(g) - \hat{Y}(g_0))^2 | g \in G\}$ and assume that $\hat{Y}(g)$ is uniformly bounded by $U$ for all $g \in G$.
Then for $\delta_n \geq \max\left\{r_n,\Omega\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)\right\}$, w.p. $1-\delta$

\begin{align}
Z_{n,4} \leq~& 18\,\left(\delta_n \sqrt{\E\left[(\hat{Y}(g) - \hat{Y}(g_0))^4\right]} + \delta_n^2\right) \label{eqn:lemma19}
\end{align}

We can apply Lemma <ref> with:

\begin{align}
h_g(W) :=~& (\hat{Y}(g) - \hat{Y}(g_0))^2, g\in G &
h_*(W) :=~& 0 &
\ell(Z;h(W)) :=~& h(W)
\end{align}

where $W$ is assumed to contain all the random variables that go into the calculation of the proxy labels $\hat{Y}(g)$.
Note that the loss function is $1$-Lipschitz in $h$ and we have a scalar-valued function $h$, i.e. $d=1$ and the loss function is linear in $h$. Thus we get that if $\delta_n = \Omega\left(\sqrt{\frac{\log(1/\zeta)}{n}}\right)$ upper bounds the critical radius $r_n$ of $\shull(Y_G)$, then w.p. $1-\zeta$:

\begin{align}
\left|(P_n - P) h_{\hat{g}}(W)\right| = 18\,\left(\delta_n \|h_{\hat{g}}\|_{L_2} + \delta_n^2\right) \leq 18\,\left(\delta_n \sqrt{\E\left[(\hat{Y}(g) - \hat{Y}(g_0))^4\right]} + \delta_n^2\right)
\end{align}

§.§ Putting it all together

Applying the AM-GM inequality to Equation (<ref>), we get:

\begin{align}
Z_{n,4} \leq~& \E[(\hat{Y}(\hat{g}) - \hat{Y}(g_0))^4] + 23\delta_n^2
= \E[(\hat{Y}(\hat{g}) - \hat{Y}(g_0))^4] + O\left(r_n^2+\frac{\log(1/\delta)}{n}\right)
\end{align}

Assuming $\hat{Y}(g)$ be uniformly bounded by $U$ and $f_j(X)$ is absolutely and uniformly bounded by $U$, the square loss is $4U$-Lipschitz. Choosing $\nu=1/2$ and combining all the above Lemmas, we have that w.p. $1-\delta$:

\begin{align}
R(\hat{\theta}) \leq~& \min_{j}\left( R(e_j)  +\frac{\beta}{n}\log(1/\pi_j)\right) + O\left(  r_n^2 + \frac{\log(\log(n))+ \log(1/\delta) \max\{\frac{1}{\mu} U^2, b\,U \}}{n}\right)
+ \frac{2}{\mu} \error(\hat{g})^2
\end{align}

§ PROOF OF EXPECTED REGRET THEOREM

Assuming sample-splitting, (i.e. $\hat{g}$ was trained on a sample that was independent of the sample that was used to determine the $M$ models $\{f_1,\ldots, f_M\}$), we can apply the results of  Lemma <ref>. Taking expectation on both sides of Equation (<ref>), we have:

\begin{align}
\E_{\hat{\theta},\hat{g},X} \left[R(\hat{\theta}) - \min_{j} [R(e_j, g_0){+ \frac{\beta}{n} \log(1/\pi_j)}]\right] \leq~& \E_{\hat{\theta},\hat{g},X} \left\{ 2\, (Z_{n,1} + Z_{n,2}) + \frac{1}{\mu}\error(\hat{g})^2 \right\}\\
\E_{\hat{\theta},\hat{g}} \left[R(\hat{\theta}) - \min_{j} [R(e_j, g_0){+ \frac{\beta}{n} \log(1/\pi_j)}]\right] \leq~& \E_{\hat{\theta},\hat{g}}\left[ \E_X [2\, (Z_{n,1} + Z_{n,2})] \right]+\frac{1}{\mu}\E_{\hat{\theta},\hat{g},X} \left[\error(\hat{g})^2 \right]
\end{align}

Recall from Lemma <ref> and Lemma <ref> that:$\E[\exp\{sZ _{n,1}\}] \leq 1 \text{ and } \E[\exp\{s Z_{n,2}\}] \leq 1$. For $i = \{1,2\}$, by Jensen's Inequality, we have:

\begin{align}
\E[sZ_{n,i}] \leq \log \left( \E[\exp\{sZ _{n,1}\}] \right)\leq \log(1) = 0
\end{align}

Since $s$ is positive, $ \E[Z_{n,i}] \leq 0 $. Thus,

\begin{align}
\E_{\hat{\theta},\hat{g}} \left[R(\hat{\theta}) - \min_{j} [R(e_j, g_0)+ \frac{\beta}{n} \log(1/\pi_j)]\right] \leq~& \frac{1}{\mu}\E_{\hat{\theta},\hat{g},X} \left[\error(\hat{g})^2 \right]
\end{align}

Let us denote with:

\begin{align}
\bias(X;\hat{g}) := \E\left[\hat{Y}(\hat{g}) - \hat{Y}(g_0)\mid X\right]
\end{align}

the bias of the labels due to the error in the nuisance functions.
For square losses, the error is:

\begin{align}
\error(\hat{g}) = 2\sqrt{\E_X\left[\E_{\hat{g}}\left[\hat{Y}(g_0) - \hat{Y}(\hat{g})\mid X\right]^2\right]} = 2\sqrt{\E_X\left[\E_{\hat{g}}\left[\bias(X;\hat{g})\right]^2\right]}
\end{align}

and we obtain the following bound on the expected regret:

\begin{align}
\E_{\hat{\theta}, \hat{g}}\left[\|f_{\hat{\theta}} - \tau_0\|^2 - \min_{j}\left( \|f_j - \tau_0\|^2 +\frac{\beta}{n} \log(1/\pi_j) \right)\right]\leq O\left(\frac{1}{\mu}\,  \E_X\left[\E_{\hat{g}}\left[\bias(X;\hat{g})\right]^2\right]\right)
\end{align}

§ GREEDY Q-AGGREGATION FOR SQUARE LOSSES

In this section, we show that we can get comparable theoretical guarantees when using a k-step greedy approximation of the Q-aggregation algorithm.

§.§ Preliminaries

Consider the following k-step greedy algorithm to find an approximate minimizer of a functional $Q(\theta)$, proposed in [7]:
Greedy model averaging GMA-0$_{+}$

Let $\theta^{(0)}=0$, $f_{\theta^{(0)}} = 0$
$k = 1, 2, \cdots$
Set $a_k = \frac{2}{k+1}$
$J^{(k)} = \argmin_{j}Q((1-a_{k})\theta^{(k-1)} +a_{k} e_{j})$
$\theta^{(k)} = \argmin_{\theta \in \Theta}Q(\theta)$ s.t. $\theta_{j} = 0$ for $j \not\in \{J^{(1)}, \cdots, J^{(k)}\}$

Suppose that $\ell_{\theta,\hat{g}}(Z)$ is of the form $(Y - f_\theta(X))^2$ for some label $Y\equiv \hat{Y}(\hat{g})$. Denote with:

\begin{align}
Q(\theta) :=~& P_n \tilde{\ell}_{\theta, \hat{g}}(Z) + \frac{\beta}{n}K(\theta) &
V_n(\theta) :=~&\sum_{j=1}^M \theta_j P_n (f_j(X) - f_\theta(X))^2
\end{align}

Then the estimator $f_{\theta^{(k)}}$, where $\theta^{(k)}$ is the output of GMA-$0_{+}$ after k steps satisfies:

\begin{align}
Q(\theta^{(k)}) \leq \min_{\theta \in \Theta}\{Q(\theta)+ C_Q V_{n}(\theta)\}
\end{align}
where $C_Q=\frac{4(1-\nu)}{k+3}$.

We first introduce some short-hand notation that will be convenient for the proof. Let $x_\theta = (f_\theta(X_1), \ldots, f_\theta(X_n))\in \R^n$, denote the vector of values of the function $f_\theta$ on the $n$ samples and $y=(Y_1, \ldots, Y_n)\in \R^n$ denote the vector of samples.
For any vectors $x_{\theta},x_{\bar{\theta}} \in \mathbb{R}^n$ define the empirical norm and associated inner product

\begin{align}
\|x_{\theta}-x_{\bar{\theta}}\|_n^2 :=~& \frac{1}{n} \sum_{i=1}^{n} (x_{\theta_{i}}-x_{\bar{\theta}_{i}})^2 &
\langle x_{\theta}, x_{\bar{\theta}} \rangle_{n} :=~& \frac{1}{n}\sum_{i=1}^{n}x_{\theta_{i}} x_{\bar{\theta}_{i}}
\end{align}

Then note that:

\begin{align}
V_n(\theta) =~&\sum_{j=1}^M \theta_j \|x_j - x_\theta\|_n^2 &
Q(\theta) =~& (1-\nu)\|x_\theta - y\|_n^2 + \nu\,\sum_{j=1}^M \theta_j \|x_j - y\|_n^2 + \frac{\beta}{n}K(\theta)
\end{align}

From Taylor expansion on the Q-functional, we have for any $x_\theta, x_{\theta'} \in \mathbb{R}^n$:

\begin{align}
Q(\theta) = Q(\theta') + \langle \nabla_{x}Q({\theta'}), x_{\theta}-x_{\theta'} \rangle_{n} + (1-\nu)
\|x_{\theta}-x_{\theta'}\|_{n}^2
\end{align}

Observe that for any $j \in \{1,\cdots, M\}$:

\begin{align}
Q(\theta^{(k)}+a_{k+1}(e_{J^{(k+1)}})-\theta^{(k)}) \leq Q(\theta^{(k)}+a_{k+1}(e_{j}-\theta^{(k)}))
\end{align}

Multiplying by $\theta_{j}$ and summing over all $\theta$ we get that for any $\theta \in \Theta$:

\begin{align}
& \sum_{j=1}^{M}\theta_{j}Q(\theta^{(k)}+a_{k+1}(e_{J^{(k+1)}})-\theta^{(k)}) \leq \sum_{j=1}^{M}\theta_{j}Q(\theta^{(k)}+a_{k+1}(e_{j}-\theta^{(k)})) \\
\iff & Q(\theta^{(k)}+a_{k+1}(e_{J^{(k+1)}})-\theta^{(k)}) \leq \sum_{j=1}^{M}\theta_{j}Q(\theta^{(k)}+a_{k+1}(e_{j}-\theta^{(k)})) \\
\implies & Q(\theta^{(k+1)}) \leq \sum_{j=1}^{M}\theta_{j}Q(\theta^{(k)}+a_{k+1}(e_{j}-\theta^{(k)}))
\end{align}

Using the Taylor expansion formula with $\theta = \theta^{(k)}+a_{k+1}(e_{j}-\theta^{(k)})$ and $\theta'=\theta^{(k)}$ on the RHS:

\begin{align}
Q(\theta^{(k+1)}) \leq~& \sum_{j=1}^M \theta_{j} \left[ Q(\theta^{(k+1)}) +\left[a_{k+1}(e_{j}-\theta^{(k)})\right]^T \nabla Q(\theta^{(k)}) +(1-\nu)\norm{\sum_{j=1}^{M}a_{k+1}(e_{j}-\theta^{(k)})x_{j}}_{n}^2\right] \\
\leq~& Q(\theta^{(k)}) + a_{k+1}\sum_{j=1}^M \theta_{j} \langle e_{j}, \nabla Q(\theta^{(k)}) \rangle_{n} -a_{k+1}\langle \theta^{(k)}, \nabla Q(\theta^{(k)}) \rangle_{n} + (1-\nu)a_{k+1}^{2} \sum_{j=1}^{M}\theta_{j}  \norm{x_{j}-x_{\theta^{(k)}}}_{n}^2  \\
\leq~& Q(\theta^{(k)}) + a_{k+1} \langle \theta - \theta^{(k)} , \nabla Q(\theta^{(k)}) \rangle_{n} + (1-\nu)a_{k+1}^{2} \sum_{j=1}^{M}\theta_{j}  \norm{x_{j}-x_{\theta^{(k)}}}_{n}^2
\\\leq~& Q(\theta^{(k)})+ a_{k+1}[Q(\theta)-Q(\theta^{(k)})] -(1-\nu) a_{k+1} \|x_{\theta^{(k)}}-x_{\theta}\|_{n}^2 + (1-\nu)a_{k+1}^{2}\sum_{j=1}^{M}\theta_{j}  \norm{x_{j}-x_{\theta^{(k)}}}_{n}^2
\\ \leq~& Q(\theta^{(k)})+ a_{k+1}[Q(\theta)-Q(\theta^{(k)})]-(1-\nu)a_{k+1}\|x_{\theta^{(k)}}-x_{\theta}\|_{n}^2
\\ & + (1-\nu)a_{k+1}^{2}\left(\sum_{j=1}^{M}\theta_{j}  \norm{x_{j}-x_{\theta}}_{n}^2 +\norm{x_{\theta^{(k)}}-x_{\theta}}_{n}^2 \right)\\
\leq~& Q(\theta^{(k)})+ a_{k+1}[Q(\theta)-Q(\theta^{(k)})] + (1-\nu)a_{k+1}^{2}\sum_{j=1}^{M}\theta_{j}  \norm{x_{j}-x_{\theta}}_{n}^2
\end{align}

\begin{align}
Q(\theta^{(k+1)})-Q(\theta) \leq~& (1-a_{k+1})[Q(\theta^{(k)})-Q(\theta)] +(1-\nu)a_{k+1}^2V(\theta)
\end{align}

For simplicity, denote $\delta_{k}=Q(\theta^{(k)})-Q(\theta)$ and $B=(1-\nu)\sum_{j=1}^{M}\theta_{j}\|x_{j}-x_{\theta}\|_{n}^2$

Using an induction on k, it is straightforward to prove the following:

\begin{align}
\delta_{k}\leq \frac{4B}{k+3}
\end{align}

§.§ Excess Risk Guarantees for the k-step Greedy Q-aggregation Estimator

Assume that for some function $\error(\hat{g})$:

\begin{align}
P(\tilde{\ell}_{\theta,g_0}(Z) - \tilde{\ell}_{\theta',g_0}(Z)) - P(\tilde{\ell}_{\theta,\hat{g}}(Z) - \tilde{\ell}_{\theta',\hat{g}}(Z))
\leq \error(\hat{g})\, \|f_{\theta} - f_{\theta'}\|^{\gamma}
\end{align}

for some $\gamma\in [0, 1]$ and square loss $\ell_{f,g}$. Assume that $\hat{Y}(\hat{g})$ and all functions $f_j$ are absolutely uniformly bounded by $U$. Let $\theta^k$ be the k-step greedy approximate of $\hat{\theta}$. For any $k\geq 2$, $\nu\geq 1/2$ and $\mu \leq \frac{1}{60} (1 - \nu)$

and $\beta \geq \max\{\frac{64 U^2(1-\nu)^2}{\mu}, \frac{16\nu U^2(\nu + 8 \mu U)}{\mu}\}$, w.p. $1-\delta$:

\begin{align}
R(\theta^k, g_0) \leq~& \min_{j=1}^M\left( R(e_j, g_0)  +\frac{3\beta}{2n}\log(1/\pi_j)\right) + O\left( \frac{\log(1/\delta) \frac{1}{\mu}U^2}{n}\right) + \left(\frac{1}{\mu}\right)^{\frac{\gamma}{2-\gamma}} \error(\hat{g})^{\frac{2}{2-\gamma}}
\end{align}

Here, we prove an analogue of  Lemma <ref> for the K-step greedy approximate of $\hat{\theta}$.

Let $\theta^*=\argmin_{\theta \in \Theta} \tilde{R}(\theta, g_0) + C_V V(\theta) + C_K K(\theta)$ and let $\theta^k$ be the k-step greedy approximate of $\hat{\theta}$.

Define the centered and offset empirical processes:

\begin{align}
Z_{n,1} =~& (1-\nu)(P-P_n) (\ell_{\theta^k, \hat{g}}(Z) - \ell_{\theta^*, \hat{g}}(Z)) - \mu \sum_{j} \theta^k_j \|f_j - f_{\theta^*}\|^2 {-\frac{1}{s}K(\theta^k)}\\
Z_{n,2} =~& \nu(P-P_n) \sum_{j} (\theta^k_j-\theta_j^*)\ell_{e_j, \hat{g}}(Z) - \mu (\theta^k)^\top H \theta^*{-\frac{1}{s}K(\theta^k)} & H_{ij} = \|f_i - f_j\|^2 \\
{ Z_{n,5} =}~& {C_Q(V_n(\theta^*) - V(\theta^*)) - \mu V(\theta^*) - \frac{1}{s}K(\theta^*)}\\
\end{align}

where $s$ is a positive number.

Assume that:

\begin{align}
{\cal E}(\hat{g}) := P(\tilde{\ell}_{\theta^k,g_0}(Z) - \tilde{\ell}_{\theta^*,g_0}(Z)) - P(\tilde{\ell}_{\theta^k,\hat{g}}(Z) - \tilde{\ell}_{\theta^*,\hat{g}}(Z)) \leq \error(\hat{g})\, \|f_{\theta^k} - f_{\theta^*}\|
\end{align}

and $\ell_{f, g} = (\hat(Y)(g) - f)$ where $\hat{Y}(\hat{g})$ and all functions $f_j$ are absolutely uniformly bounded by $U$.

Choose $\beta \geq \frac{8n}{s}$, $C_K = \frac{3\beta}{2n}$, and $C_V< \min\{1-\nu,\nu\}$. Furthermore, choose $k$ such that $C_Q<C_V$. Then, assuming $\mu \leq \min\left\{\frac{1}{6}\left(1-\nu - C_V \right), {\frac{1}{4} (\nu - C_V)}, \frac{1}{2}(C_V -C_Q)\right\}$, we get:

\begin{align}
R(\theta^k) \leq \min_{j} [R(e_j, g_0){+ \frac{3\beta}{2n} \log(1/\pi_j)}] + 2\, (Z_{n,1} + Z_{n,2} + Z_{n,5}) + \frac{1}{\mu}\error(\hat{g})^2 \label{eqn:lemma9-greedy}
\end{align}

For k-step greedy approximate, Theorem <ref> implies that:

\begin{align}
P_n \tilde{\ell}_{\theta^k, \hat{g}}(Z) + \frac{\beta}{n}K(\theta^k) \leq~& \min_{\theta \in \Theta} \{ P_n \tilde{\ell}_{\theta, \hat{g}}(Z) + \frac{\beta}{n}K(\theta)+ \frac{4(1-\nu)}{k+3}V_n(\theta)\}  \\
\leq~&P_n \tilde{\ell}_{\theta^*, \hat{g}}(Z) + \frac{4(1-\nu)}{k+3}V_n(\theta^*) + \frac{\beta}{n}K(\theta^*) \label{eqn:greedy_opt}
\end{align}

\begin{align}
\tilde{R}(\theta^k, g_0) - \tilde{R}(\theta^*, g_0) =~&
P(\tilde{\ell}_{\theta^k,g_0}(Z) - \tilde{\ell}_{\theta^*,g_0}(Z))\\
P(\tilde{\ell}_{\theta^k,\hat{g}}(Z) - \tilde{\ell}_{\theta^*,\hat{g}}(Z)) + {\cal E}(\hat{g})\\
\leq~&
(P - P_n)(\tilde{\ell}_{\theta^k, \hat{g}}(Z) - \tilde{\ell}_{\theta^*, \hat{g}}(Z)) + {\cal E}(\hat{g})
{-\frac{\beta}{n}(K(\theta^k)-K(\theta^*))} {+ C_Q V_n(\theta^*)}
\tag{By Eqn \ref{eqn:greedy_opt}}\\
=~& \mu\sum_j \theta^k_j \|f_j - f_{\theta^*}\|^2 + \mu (\theta^k)^\top H\theta^*+ Z_{n,1} + Z_{n,2} {+Z_{n,5}} + {\cal E}(\hat{g})\\
~& {-\frac{\beta}{n}(K(\theta^k)-K(\theta^*)) + \frac{2}{s}K(\theta^k)} {+ (C_Q+\mu) V(\theta^*) + \frac{1}{s}K(\theta^*)}
\tag{definition of $Z_{n,1}, Z_{n,2}, Z_{n,5}$}
\end{align}

By simple algebraic manipulations note that for any $\theta, \theta' \in \Theta$:

\begin{align}
\sum_j \theta_j \|f_j - f_{\theta'}\|^2 = V(\theta) + \|f_{\theta} - f_{\theta'}\|^2 \label{eqn:v}\\
\theta^\top H \theta'= V(\theta) + V(\theta') + \|f_{\theta} - f_{\theta'}\|^2
\end{align}

Letting $Z_n=Z_{n,1} + Z_{n,2} {+Z_{n,5}}$, we have:

\begin{align}
\tilde{R}(\theta^k, g_0) - \tilde{R}(\theta^*_k, g_0) \leq~& 2\mu V(\theta^k) + ({2\mu+C_Q}) V(\theta^*) + 2\mu \|f_{\theta^k} - f_{\theta^*}\|^2 + Z_n + {\cal E}(\hat{g})\\
~& -\frac{\beta}{n}(K(\theta^k)-K(\theta^*)) + \frac{2}{s}K(\theta^k) {+\frac{1}{s}K(\theta^*)}\\
\leq~& 2\mu V(\theta^k) + ( {2\mu+C_Q}) V(\theta^*) + 2\mu \|f_{\theta^k} - f_{\theta^*}\|^2 + Z_n + \error(\hat{g})\, \|f_{\theta^k} - f_{\theta^*}\|^{\gamma}\\
~& {-\frac{\beta}{n}(K(\theta^k)-K(\theta^*)) + \frac{2}{s}K(\theta^k)}  {+\frac{1}{s}K(\theta^*)} \label{eqn:}
\end{align}

By Young's inequality, for any $a\geq 0$ and $b\geq 0$, we have $a\,b\leq \frac{a^p}{p} + \frac{b^q}{q}$, such that $\frac{1}{p}+\frac{1}{q}=1$. Taking $a= \left(\frac{\gamma}{2\mu}\right)^{\gamma/2} \error(\hat{g})$ and $b=\left(\frac{2\mu}{\gamma}\right)^{\gamma/2}\|f_{\theta^k}-f_{\theta^*}\|^\gamma$ and $q=2/\gamma$ and $p=\frac{1}{1-1/q}=\frac{1}{1-\gamma/2}=\frac{2}{2-\gamma}$

\begin{align}
\error(\hat{g})\, \|f_{\theta^k} - f_{\theta^*}\|^{\gamma} \leq \underbrace{\frac{2}{2-\gamma}\left(\frac{\gamma}{2\mu}\right)^{\frac{\gamma}{2-\gamma}} \error(\hat{g})^{\frac{2}{2-\gamma}}}_{{\cal A}(\hat{g})}+ \mu \|f_{\theta^k} - f_{\theta^*}\|^2
\end{align}

Thus we can derive:

\begin{align}
\tilde{R}(\theta^k, g_0) - \tilde{R}(\theta^*, g_0) \leq~& 2\mu V(\theta^k) + ({2\mu+C_Q}) V(\theta^*) + 3\mu \|f_{\theta^k} - f_{\theta^*}\|^2 + Z_n + {\cal A}(\hat{g}) \\
~& {-\frac{\beta}{n}(K(\theta^k)-K(\theta^*)) + \frac{2}{s}K(\theta^k)} {+\frac{1}{s} K(\theta^*)}\label{eqn:greedy_first_upper}
\end{align}

To obtain a lower bound:

\begin{align}
\tilde{R}(\theta^k, g_0) - \tilde{R}(\theta^*, g_0) =~&
H(\theta_k, g_0) - H(\theta^*,g_0) + C_V (V(\theta^*) - V(\theta^k)) +C_K (K(\theta^*)-K(\theta^k))\\
\geq~& \left(1-\nu - C_V\right)\|f_{\theta^k} - f_{\theta^*}\|^2 + C_V (V(\theta^*) - V(\theta^k)) +C_K (K(\theta^*)-K(\theta^k)) \tag{By Lemma \ref{lem:strong-conv-tilde}}\\
\end{align}

Combining the latter upper and lower bound on $\tilde{R}(\theta^k, g_0) - \tilde{R}(\theta^*, g_0)$, we have:

\begin{align}
\left(1-\nu - C_V - 3\mu \right)  \|f_{\theta^k} - f_{\theta^*}\|^2 \leq~& (2\mu + C_V)V(\theta^k) + Z_n {
+ {\cal A}(\hat{g})} +  (2\mu + C_Q - C_V)V(\theta^*)\\
-~& \left(\frac{\beta}{n} - C_K\right)(K(\theta^k) - K(\theta^*)) + \frac{2}{s}K(\theta^k) + \frac{1}{s}K(\theta^*)\\
\end{align}

\begin{align}
\left(1-\nu - C_V - 3\mu \right) \geq 3\mu ~~~~~\Leftrightarrow~~~~~
\frac{1}{6}\left(1-\nu - C_V \right) \geq \mu
\end{align}

We get that:

\begin{align}
3\mu \|f_{\theta^k} - f_{\theta^*}\|^2 \leq~& {
+ {\cal A}(\hat{g})} + (2\mu + C_V)V(\theta^k) +  (2\mu + C_Q - C_V)V(\theta^*)\\
-~& \left(\frac{\beta}{n} - C_K\right)(K(\theta^k) - K(\theta^*)) + \frac{2}{s}K(\theta^k) + \frac{1}{s}K(\theta^*)\\
\end{align}

Plugging the bound on $\|f_{\theta^k} - f_{\theta^*}\|^2$ back into Equation (<ref>) we have:

\begin{align}
\tilde{R}(\theta^k, g_0) - \tilde{R}(\theta^*, g_0) \leq ~& (4\mu + C_V) V(\theta^k) + (4\mu + 2C_Q - C_V) V(\theta^*) + 2\, Z_n + 2\,{\cal A}(\hat{g}) \\
~& - \left(\frac{2\beta}{n} - C_K\right)(K(\theta^k)-K(\theta^*)) + \frac{4}{s}K(\theta^k) + \frac{2}{s}K(\theta^*)\\
\end{align}

By Lemma <ref>, we have:

\begin{align}
R(\theta^k, g_0) \leq~& \tilde{R}(\theta^*, g_0) + (4\mu + 2C_Q - C_V) V(\theta^*)+ \left(4\mu + C_V - {\nu}\right) V(\theta^k) + 2 Z_n + 2{\cal A}(\hat{g}) \\
~& {+\left(\frac{2\beta}{n}-C_K+\frac{2}{s}\right)K(\theta^*) + \left(\frac{4}{s} - \frac{2\beta}{n} + C_K\right)K(\theta^k)}\\
\leq~& \tilde{R}(\theta^*, g_0) + (4\mu + 2C_Q - C_V) V(\theta^*) + 2 Z_n + 2{\cal A}(\hat{g}) \tag{Since $\mu \leq \frac{1}{4}(\nu - C_V)$}\\
~& {+(\frac{2\beta}{n}-C_K+\frac{2}{s})K(\theta^*) + \left(\frac{4}{s} - \frac{2\beta}{n} + C_K\right)K(\theta^k)}\\
\end{align}

Let $C_K = \frac{3\beta}{2n}$

\begin{align}
\frac{1}{s} \leq~& \frac{\beta}{8n}\\
C_V \geq~& C_Q\\
\mu \leq~& \frac{1}{2}(C_V - C_Q)
\end{align}

We get that:

\begin{align}
4\mu + 2C_Q - C_V \leq C_V\\
\frac{2\beta}{n} - C_K +\frac{2}{s} \leq~& C_K\\
\frac{4}{s} - \frac{2\beta}{n} + C_K \leq~&0\\
\end{align}

Thus we get:

\begin{align}
R(\theta^k, g_0)\leq~& \tilde{R}(\theta^*, g_0) + C_V V(\theta^*) + C_K K(\theta^*) + 2 Z_n + 2{\cal A}(\hat{g})\\
\leq~& \min_{j} [\tilde{R}(e_j, g_0) + C_V V(e_{j}) {+  C_K\log(1/\pi_j)}]+ 2 Z_n + 2{\cal A}(\hat{g})\\
=~& \min_{j} [R(e_j, g_0){+  \frac{3\beta}{2n} \log(1/\pi_j)}] + 2 Z_n +2{\cal A}(\hat{g}) \tag{Since $\tilde{R}(e_j, g_0)=R(e_j, g_0)$ and $V(e_j)=0$ for all $e_j$}
\end{align}

Assuming that $f\in F$ are uniformly and absolutely and bounded in $[-U,U]$, for any positive
$s\leq \frac{n \mu}{2 C_Q^2 U^2 (1+\mu)}$:

\begin{align}
{\Pr\left(Z_{n,5} \geq \frac{\log(1/\delta)}{s}\right) \leq \delta}
\end{align}

It suffices to show that:

\begin{align}
I := \E\left[\exp s Z_{n,5} \right] \leq 1
\end{align}

Note first that:

\begin{align}
Z_{n,5} =~& {C_Q(V_n(\theta^*) - V(\theta^*)) - \mu V(\theta^*) - \frac{1}{s}K(\theta^*)}\\
\leq~& \max_j \left[ C_Q(P_n - P)(f_{j}(Z) - f_{\theta^*}(Z))^2 - \mu P(f_{j}(Z) - f_{\theta^*}(Z))^2 + \frac{1}{s}\log(\pi_j)\right]
\end{align}

\begin{align}
\E\left[\exp s Z_{n,5} \right] \leq ~& \E\left[\exp\left\{s
\max_{j} \left[C_Q(P_n - P)(f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu P (f_{j}(Z) - f_{\theta^*}(Z))^2 + \frac{1}{s}\log(\pi_j)\right]\right\}\right]\\
\leq~& \E\left[\max_j \exp\left\{s \left( C_Q(P_n - P)(f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu  P (f_{j}(Z) - f_{\theta^*}(Z))^2+ \frac{1}{s}\log(\pi_j)\right)\right\}\right]\\
\leq~&\sum_j \pi_j \E\left[\exp\left\{s \left( C_Q(P_n - P)(f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu  P(f_{j}(Z) - f_{\theta^*}(Z))^2\right)\right\}\right]\\
\leq~& \max_j \E\left[\exp\left\{s \left( C_Q(P_n - P)(f_{j}(Z) - f_{\theta^*}(Z))^2 -
\mu P(f_{j}(Z) - f_{\theta^*}(Z))^2\right)\right\}\right]
\end{align}

Since $f_j(Z)\in [U, U]$, we have that $f_j(Z) - f_{\theta^*}(Z)\in [-2U, 2U]$. Thus:

\begin{align}
(f_j(Z)-f_{\theta^*}(Z))^2\geq \frac{(f_j(Z)-f_{\theta^*}(Z))^2}{4U^2} (f_j(Z)-f_{\theta^*}(Z))^2 = \frac{1}{4U^2} (f_j(Z)-f_{\theta^*}(Z))^4.
\end{align}

\begin{align}
I \leq~& \max_j \E_{Z_{1:n}}\left[ \exp\left\{s \left(C_Q\left(P_n - P\right)(f_{j}(Z) - f_{\theta^*}(Z))^2 - \frac{\mu}{4 C_Q^2 U^2} P C_Q^2(f_{j}(Z) - f_{\theta^*}(Z))^4 \right)\right\}\right]
\end{align}

It suffices to show that each term $j$ is upper bounded by $1$.

Applying Lemma <ref> with:

\begin{align}
V_i =~& C_Q (f_j(Z_i) - f_{\theta^*}(Z_i))^2\\
c =~& 4 C_Q^2 U^2\\
\lambda =~& s\\
c_0 =~& \frac{\mu}{4C_Q^2U^2}
\end{align}

we have that as long as:

\begin{align}
\lambda := \frac{s}{n} \leq \frac{2c_0}{1+2c_0 c} =: \frac{2\cdot \mu/4 C_Q^2 U^2}{1 + \mu} = \frac{\mu}{2 C_Q^2 U^2(1+\mu)}
\end{align}

\begin{align}
\E_{Z_{1:n}}\left[ \exp\left\{s \left(C_Q\left(P_n - P\right)(f_{j}(Z) - f_{\theta^*}(Z))^2 - \frac{\mu}{4 C_Q^2 U^2} P C_Q^2(f_{j}(X) - f_{\theta^*}(X))^4 \right)\right\}\right]\leq 1
\end{align}

Thus we need that:

\begin{align}
s \leq \frac{n \mu}{2 C_Q^2 U^2 (1+\mu)}
\end{align}

which is satisfied by our assumptions on $s$.

Putting it All Together
Choose $\nu\geq 1/2$, such that $1-\nu \leq \nu$. Note that for any $k\geq 2$, we have $C_Q = \frac{4}{k+3}(1-\nu)\leq \frac{4}{5}(1-\nu)$. Choosing $C_V = \frac{5}{6} (1-\nu) \leq \frac{5}{6} \nu$, then we have that for $k\geq 2$, we have $C_Q < C_V$ and we can take $\mu \leq \frac{1}{60}(1-\nu)$ in Lemma <ref>.

Combining all the above Lemmas, we have that w.p. $1-\delta$, the k-step greedy Q-aggregation estimator $\theta_k$ achieves:

\begin{align}
R(\theta_k) \leq \min_{j}\left( R(e_j)  +\frac{3\beta}{2n}\log(1/\pi_j)\right) + O\left(  \frac{\log(1/\delta) \frac{1}{\mu}U^2}{n}\right) + \frac{2}{\mu} \error(\hat{g})^2
\end{align}

§ PROOF OF ORTHOGONAL STATISTICAL LEARNING THEOREM

§.§ Fast Rates

The proof follows the proof of Theorem 1 in [12] after replacing $f_*$ by $f$, and we recover the original theorem by assuming $F' = F$.

By a second order Taylor expansion around $f'$, there exist $\bar{f}\in\text{Star}(F',f')$ such that:

\begin{align}
( P\ell_{\hat{f},\hat{g}} - P\ell_{f',\hat{g}}) - D_{f}P\ell(f',\hat{g})[\hat{f}-f'] =~& \frac{1}{2}D_{f}^2P\ell_{\bar{f},\hat{g}}[\hat{f} - f',\hat{f}-f']\\
\geq~& \frac{\lambda}{2}\|\hat{f}-f'\|^2 - \frac{\kappa}{2} d(\hat{g},g_0)^{\frac{4}{1+r}} \tag{By Assumption \ref{assum:4}}
\end{align}

Rearranging, we get:

\begin{align}
\frac{\lambda}{2}\|\hat{f}-f'\|^2 \leq~& (P\ell_{\hat{f},\hat{g}} - P\ell_{f',\hat{g}})-D_{f}P\ell(f',\hat{g})[\hat{f}-f'] + \frac{\kappa}{2} d(\hat{g},g_0)^{\frac{4}{1+r}}\\
\end{align}

Applying a second-order Taylor expansion, we get:

\begin{align}
-D_{f}P\ell(f',\hat{g})[\hat{f}-f'] =~& -D_{f}P\ell(f',g_0)[\hat{f}-f'] - D_{g}D_{f}P\ell_{f',g_0}[\hat{f} - f',\hat{g}-g_0] \\
-~& \frac{1}{2}D_{g}^{2}D_{f}P\ell_{f,\bar{g}}[\hat{f} - f',\hat{g}-g_0, \hat{g}-g_0]\\
=~& - D_{f}P\ell(f',g_0)[\hat{f}-f']- \frac{1}{2}D_{g}^{2}D_{f}P\ell_{f,\bar{g}}[\hat{f} - f',\hat{g}-g_0, \hat{g}-g_0] \tag{By Assumption \ref{assum:1}}\\
\leq ~& - D_{f}P\ell(f',g_0)[\hat{f}-f'] + \beta_2\|\hat{f}-f'\|^{1-r}d(\hat{g},g_0)^2 \tag{By Assumption \ref{assum:3}(b)}\\
\end{align}

Alternatively, we can get the above result directly by <ref> instead of Assumptions <ref> and <ref>.

Invoking Young's inequality and using $r\in [0,1)$, we have that for any $\eta>0$:

\begin{align}
-D_{f}P\ell(f',\hat{g})[\hat{f}-f'] \leq - D_{f}P\ell(f',g_0)[\hat{f}-f']+\frac{\beta_2\eta}{4}\|\hat{f}-f'\|^2 + \frac{\beta_2}{2\eta^{(1-r)/(1+r)}}d(\hat{g},g_0)^{\frac{4}{1+r}}
\end{align}

Choosing $\eta = \frac{\lambda}{\beta_2}$, we get that:

\begin{align}
\|\hat{f}-f'\|^2 \leq - \frac{4}{\lambda}D_{f}P\ell(f',g_0)[\hat{f}-f']+ (P\ell_{\hat{f},\hat{g}} - P\ell_{f',\hat{g}}) +O\left( d(\hat{g},g_0)^{\frac{4}{1+r}} \right) \label{eqn:norm_f}
\end{align}

Taking Taylor expansion at $f'$, we have that there exist $\bar{f}\in\text{Star}(F',f')$ such that:

\begin{align}
P\ell_{\hat{f},g_0} -  P\ell_{f',g_0} = ~& D_{f}P\ell_{f',g_0}[\hat{f}-f'] + \frac{1}{2}D_{f}^2P\ell_{\bar{f},g_0}[\hat{f}-f',\hat{f}-f']\\
\leq~& D_{f}P\ell_{f',g_0}[\hat{f}-f'] + \frac{\beta_1}{2}\|\hat{f}-f'\|^2 \tag{By Assumption \ref{assum:3}(a)}\\
\leq~& -(\frac{2\beta_1}{\lambda}-1)  D_{f}P\ell_{f',g_0}[\hat{f}-f']+  O\left((P\ell_{\hat{f},\hat{g}} - P\ell_{f',\hat{g}}) + d(\hat{g},g_0)^{\frac{4}{1+r}}\right)
\end{align}

Since $\beta_1$ is the upper bound, we may assume $\frac{2\beta_1}{\lambda}>1$. Thus, we get:

\begin{align}
P\ell_{\hat{f},g_0} -  P\ell_{f',g_0} \leq O\left((P\ell_{\hat{f},\hat{g}} - P\ell_{f',\hat{g}}) + d(\hat{g},g_0)^{\frac{4}{1+r}}\right)\label{eqn:fast_rate}
\end{align}

Moreover, if

\begin{align}
P\ell_{\hat{f},\hat{g}}(Z) - P\ell_{f',\hat{g}}(Z) \leq \epsilon_n(\delta) \| \hat{f} - f'\| + \alpha_n(\delta)
\end{align}

Plugging this into Equation <ref> yields:

\begin{align}
\|\hat{f}-f'\|^2 \leq~& - \frac{4}{\lambda}D_{f}P\ell(f',g_0)[\hat{f}-f']+ \epsilon_n(\delta) \| \hat{f} - f'\| + \alpha_n(\delta) +O\left( d(\hat{g},g_0)^{\frac{4}{1+r}} \right)\\
\leq~& - \frac{4}{\lambda}D_{f}P\ell(f',g_0)[\hat{f}-f']+ \frac{1}{2}\| \hat{f} - f'\|^2 +O\left(\epsilon_n(\delta)^2 + \alpha_n(\delta)+ d(\hat{g},g_0)^{\frac{4}{1+r}} \right)
\end{align}

Thus, we get:

\begin{align}
\|\hat{f}-f'\|^2 \leq-\frac{8}{\lambda}D_{f}P\ell(f',g_0)[\hat{f}-f'] +O\left(\epsilon_n(\delta)^2 + \alpha_n(\delta)+ d(\hat{g},g_0)^{\frac{4}{1+r}} \right)
\end{align}

Plugging this into the Taylor expansion at $f'$, we get:

\begin{align}
P\ell_{\hat{f},g_0} -  P\ell_{f',g_0} = ~& D_{f}P\ell_{f',g_0}[\hat{f}-f'] + \frac{1}{2}D_{f}^2P\ell_{\bar{f},g_0}[\hat{f}-f',\hat{f}-f']\\
\leq~& D_{f}P\ell_{f',g_0}[\hat{f}-f'] + \frac{\beta_1}{2}\|\hat{f}-f'\|^2 \tag{By Assumption \ref{assum:3}(a)}\\
\leq~& -(\frac{4\beta_1}{\lambda}-1)  D_{f}P\ell_{f',g_0}[\hat{f}-f']+  O\left(\epsilon_n(\delta)^2 + \alpha_n(\delta)+ d(\hat{g},g_0)^{\frac{4}{1+r}}\right)
\end{align}

Again, we may assume $\frac{4\beta_1}{\lambda}>1$. Finally, we get:

\begin{align}
P\ell_{\hat{f},g_0} -  P\ell_{f',g_0} \leq O\left(\epsilon_n(\delta)^2 + \alpha_n(\delta)+ d(\hat{g},g_0)^{\frac{4}{1+r}}\right)
\end{align}

§.§ Slow Rates

§.§.§ With Universal Orthogonality

The proof follows the proof of Theorem 2 in [12], we reproduce it here for completeness.

\begin{align}
P\ell_{\hat{f},g_0}-P\ell_{f',g_0} =~& (P\ell_{\hat{f},g_0}-P\ell_{\hat{f},\hat{g}}) +(P\ell_{f',\hat{g}}-P\ell_{f',g_0}) + (P\ell_{\hat{f},\hat{g}}-P\ell_{f',\hat{g}})\\
\end{align}

Taking a second order Taylor expansion yields that there exist $g,\bar{g} \in \text{Star}(G,g_0)$ such that:

\begin{align}
(P\ell_{\hat{f},g_0}-P\ell_{\hat{f},\hat{g}}) +(P\ell_{f',\hat{g}}-P\ell_{f',g_0}) =~& -D_{g}P\ell_{\hat{f},g_0}[\hat{g} - g_0] - \frac{1}{2}D_{g}^{2}P\ell_{\hat{f},g_0}[\hat{g}-g-0,\hat{g}-g_0]\\
+~& D_{g}P\ell_{f',g_0}[\hat{g} - g_0] + \frac{1}{2}D_{g}^{2}P\ell_{f',g_0}[\hat{g}-g-0,\hat{g}-g_0]\\
\leq~& -D_{g}P\ell_{\hat{f},g_0}[\hat{g} - g_0] + D_{g}P\ell_{f',g_0}[\hat{g} - g_0] + \beta d(\hat{g},g_0)^2 \tag{By Assumption \ref{assum:6}}
\end{align}

Next, we take another second-order Taylor expansion on the derivative terms:

\begin{align}
D_{g}P\ell_{\hat{f},g_0}[\hat{g} - g_0] - D_{g}P\ell_{f',g_0}[\hat{g} - g_0] =~& D_{f}D_{g}P\ell_{f',g_0}[\hat{g}-g_0,\hat{f}-f'] + \frac{1}{2}D_{f}^{2}D_{g}P\ell_{\bar{f},g_0}[\hat{g}-g_0,\hat{f}-f',\hat{f}-f'] \\
=~& \frac{1}{2}D_{f}^{2}D_{g}P\ell_{\bar{f},g_0}[\hat{g}-g_0,\hat{f}-f',\hat{f}-f'] \tag{By Assumption \ref{assum:5}}
\end{align}
for some $\bar{f}\in\text{Star}(F,f')$.
Furthermore, we can rewrite:

\begin{align}
D_{f}^{2}~&D_{g}P\ell_{\bar{f},g_0}[\hat{g}-g_0,\hat{f}-f',\hat{f}-f'] \\=~& \lim_{t \rightarrow0}\frac{D_{f}D_{g}P\ell_{\bar{f}+t(\hat{f}-f'),g_0}[\hat{g}-g_0,\hat{f}-f'] - D_{f}D_{g}P\ell_{\bar{f},g_0}[\hat{g}-g_0,\hat{f}-f']}{t}
\end{align}

Since $\bar{f}+t(\hat{f}-f') \in \text{Star}(F,f') + \text{Star}(F-f',0)$ for all $t\in [0,1]$, Assumption <ref> implies that both terms in the numerator are zero. Thus, we get:

\begin{align}
D_{g}P\ell_{\hat{f},g_0}[\hat{g} - g_0] = D_{g}P\ell_{f',g_0}[\hat{g} - g_0]
\end{align}

Combining, we arrive at the desired result:

\begin{align}
P\ell_{\hat{f},g_0}(Z) - P\ell_{f',g_0}(Z) \leq O\left(  P\ell_{\hat{f},\hat{g}}(Z) - P\ell_{f',\hat{g}}(Z) + d(g, g_0)^2\right)
\end{align}

§.§.§ Without Universal Orthogonality

\begin{align}
P\ell_{\hat{f},g_0}-P\ell_{f',g_0} =~& (P\ell_{\hat{f},g_0}-P\ell_{f',g_0}) - (P\ell_{\hat{f},\hat{g}}-P\ell_{f',\hat{g}}) + (P\ell_{\hat{f},\hat{g}}-P\ell_{f',\hat{g}})\\
=~& D_f P\ell(\bar{f}, g_0)[\hat{f}-f'] - D_f P\ell(\bar{f}, \hat{g})[\hat{f}-f'] + P\ell_{\hat{f},\hat{g}}-P\ell_{f',\hat{g}})\tag{By first order Taylor expansion}\\
\leq~& \beta_4 d(\hat{g},g_0)^2 + (P\ell_{\hat{f},\hat{g}}-P\ell_{f',\hat{g}}) \tag{By Assumption \ref{assum:for_square_loss_slow}}\\
=~& O\left(P\ell_{\hat{f},\hat{g}}-P\ell_{f',\hat{g}} + d(\hat{g},g_0)^2\right)
\end{align}