# MU-Massive MIMO with Multiple RISs: SINR Maximization and Asymptotic
Analysis

Somayeh Aghashahi, Zolfa Zeinalpour-Yazdi, Aliakbar Tadaion, Mahdi Boloursaz
Mashhadi, and Ahmed Elzanaty, This work is based upon research funded by Iran
National Science Foundation (INSF) under project No.4013201.S. Aghashahi, Z.
Zeinalpour-Yazdi and A. Tadaion are with the Department of Electrical
Engineering, Yazd University, Yazd, Iran (e-mail<EMAIL_ADDRESS>and
{zeinalpour, tadaion}@yazd.ac.ir).M. B. Mashhadi and A. Elzanaty are with 5GIC
& 6GIC, Institute for Communication Systems (ICS), University of Surrey,
Guildford, GU2 7XH, United Kingdom (e-mail: {m.boloursazmashhadi,
a.elzanaty}@surrey.ac.uk).

###### Abstract

In this letter, we investigate the signal-to-interference-plus-noise-ratio
(SINR) maximization problem in a multi-user massive multiple-input-multiple-
output (massive MIMO) system enabled with multiple reconfigurable intelligent
surfaces (RISs). We examine two zero-forcing (ZF) beamforming approaches for
interference management namely BS-UE-ZF and BS-RIS-ZF that enforce the
interference to zero at the users (UEs) and the RISs, respectively. Then, for
each case, we resolve the SINR maximization problem to find the optimal phase
shifts of the elements of the RISs. Also, we evaluate the asymptotic
expressions for the optimal phase shifts and the maximum SINRs when the number
of the base station (BS) antennas tends to infinity. We show that if the
channels of the RIS elements are independent and the number of the BS antennas
tends to infinity, random phase shifts achieve the maximum SINR using the BS-
UE-ZF beamforming approach. The simulation results illustrate that by
employing the BS-RIS-ZF beamforming approach, the asymptotic expressions of
the phase shifts and maximum SINRs achieve the rate obtained by the optimal
phase shifts even for a small number of the BS antennas.

###### Index Terms:

RIS-assisted communication, Multi-RIS, MIMO, Zero-Forcing.

##  I Introduction

Reconfigurable intelligent surface (RIS) is a new physical layer technology
introduced to overcome the drawbacks of wireless communications such as
fading, blockage, and interference [1]. An RIS is a planner array of passive
reflecting elements which can change the phase of the reflected signals of
which the phase shifts can be continuously adjusted [2]. Thus, based on the
scenario, the behavior of the wireless environment can be improved by
deploying the RISs in appropriate places and optimizing the phase shifts of
their elements. For instance, exploiting an RIS in a cell with one user can
solve the blockage problem or increase the SNR of the user equipment (UE) [3].
However, in multi-user scenarios with a multiple input multiple output (MIMO)
base station (BS), interference management by joint design of beamforming
vectors of the BS and phase shifts of the RIS elements is a challenge.

Several studies have been conducted on solving the challenges of beamforming
and phase shift design in an RIS-aided multi-user MIMO scenario with different
objectives [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] such as maximization of the
sum rate [4, 5], spectral efficiency [6] and energy efficiency [7, 8] or
minimization of the transmission power [9], max-min SINR problem [10, 11], and
the exposure to electromagnetic fields [12, 13]. However, the proposed
solutions involve intricate algorithms and straightforward designs are not
presented in the literature. Moreover, the analysis of the results for a
massive number of BS antennas is not investigated.

Regarding the above considerations, in this letter, we investigate the SINR
maximization problem in the downlink transmission of a multi-user massive MIMO
system assisted with multiple RISs. In this scenario, we assume that some of
the UEs are directly served by the BS, while others have no direct channel to
the BS and are served through the RISs. Each RIS serves several UEs in a
specific geographic area, forming a cluster. We use two zero-forcing (ZF)
approaches for the beamforming of the BS. The advantage of ZF beamforming is
that it completely cancels the interference and this gets us a degree of
freedom for asymptotic analysis and phase shift design. Moreover, the ZF
beamforming in massive MIMO systems achieves a near-optimal performance[15].
The main contributions of this letter can be summarized as follows: (i) We
employ a ZF beamforming approach named BS-UE-ZF that nulls the interference at
the UEs, and obtain the optimal phase shifts of the RISs that maximize the
SINR of the UEs. Then, for the case that one UE is connected to each RIS, we
derive asymptotic expressions for the optimal phase shifts as the number of
the BS antennas tends to infinity. (ii) We prove that if the RISs experience
i.i.d. normal channels, random phase shifts achieve the maximum SINR when the
number of the BS antennas tends to infinity. (iii) For the case that one UE is
connected to each RIS, we propose another ZF beamforming approach named BS-
RIS-ZF that nulls the interference at the RISs. This approach leads to closed-
form expressions for the RIS phase shifts that maximize the SINRs at UEs. (iv)
We evaluate asymptotic expressions for the optimal phase shifts and the
maximum SINRs for the BS-RIS-ZF.

Figure 1:  The system model

##  II System Model

We consider downlink transmission in a multi-RIS multi-user massive MIMO
system. We assume that $U_{d}$ of the UEs (named direct UEs) are directly
connected to the BS, and $U_{b}$ of them (named blocked UEs) have no direct
connection with the BS and $K$ RISs are deployed to assist the communication
between the BS and these UEs. For $k\in\mathcal{K}\triangleq\\{1,\dots,K\\}$,
$L_{k}$ of the blocked UEs are served through the $k^{\rm th}$ RIS which are
selected by algorithm 1. Moreover, the channels between this RIS and the other
UEs are blocked as considered in [16]. Let, $M$ be the number of the BS
antennas and $N$ be the number of the elements at each of the RISs. Also,
$\mathbf{H}_{k}\in\mathbb{C}^{M\times N}$,
$\mathbf{h}_{k,\ell}\in\mathbb{C}^{N\times 1}$, and
$\mathbf{h}_{d,u}\in\mathbb{C}^{M\times 1}$ denote the channel matrix between
the BS and the $k^{\rm th}$ RIS, the channel vector between the $k^{\rm th}$
RIS and the $\ell^{\rm th}$ blocked UE connected to this RIS, and the channel
between the BS and the $u^{\rm th}$ direct UE, respectively. We assume that
each of the channel coefficients has a complex normal distribution. The
channel between the BS and each IRS is correlated such that
$\mathbb{E}\\{\mathbf{H}_{{k}}^{H}\mathbf{H}_{k}\\}=\mathbf{R}_{k}$, while the
channels between the BS and different RISs are independent, i.e.,
$\mathbb{E}\\{\mathbf{H}_{{k}}^{H}\mathbf{H}_{k^{\prime}}\\}=\mathbf{0}$ for
$k\neq k^{\prime}$. The diagonal reflected matrix for the $k^{\rm th}$ RIS is
$\mbox{\boldmath{$\Phi$}}_{k}\triangleq\mathrm{diag}(e^{j\phi_{k,1}},\dots,e^{j\phi_{k,N}})$,
where for $i\in\mathcal{N}\triangleq\\{1,\dots,N\\}$, $\phi_{k,i}$ is the
phase shift of the $i^{\rm th}$ element of the RIS. Thus, the received signal
at the $\ell^{\rm th}$ blocked UE connected to the $k^{\rm th}$ RIS is given
by

$\displaystyle
y_{{}_{b,k,\ell}}=\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{b,k,\ell}x_{{}_{b,k,\ell}}+\sum_{\begin{subarray}{c}m=1\vspace*{-0.25mm}\\\
m\neq
k\end{subarray}}^{K}\sum_{\begin{subarray}{c}i=1\end{subarray}}^{L_{m}}\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{b,m,i}x_{{}_{b,m,i}}$
$\displaystyle+\sum_{\begin{subarray}{c}i=1\vspace*{-0.1mm}\\\
i\neq\ell\end{subarray}}^{L_{k}}\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{b,k,i}x_{{}_{b,k,i}}+\sum_{n=1}^{U_{d}}\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{d,n}x_{{}_{d,n}}+z_{{}_{b,k,\ell}},$
(1)

and the received signal at the $u^{\rm th}$ direct UE is

$\displaystyle
y_{{}_{d,u}}=\mathbf{h}_{d,u}^{H}\mathbf{w}_{d,u}x_{{}_{d,u}}+\sum_{\begin{subarray}{c}n=1\vspace*{-0.25mm}\\\
n\neq
u\end{subarray}}^{U_{d}}\mathbf{h}_{d,u}^{H}\mathbf{w}_{d,n}x_{{}_{d,n}}+\sum_{m=1}^{K}\sum_{\ell=1}^{L_{m}}\mathbf{h}_{d,u}^{H}\mathbf{w}_{b,m,\ell}x_{{}_{b,m,\ell}}$
$\displaystyle+z_{{}_{d,u}},$ (2)

where $\mathbf{w}_{b,k,\ell}$ and $\mathbf{w}_{d,u}$ are the beamforming
vectors, $x_{{}_{b,k,\ell}}$ and $x_{{}_{d,u}}$ are the transmit signals and
$z_{{}_{b,k,\ell}}$ and $z_{{}_{d,u}}$ are the AWGN corresponding to the
$\ell^{\rm th}$ blocked UE connected to the $k^{\rm th}$ RIS and the $u^{\rm
th}$ direct UE, respectively. The first terms in (1) and (2) are the desired
signals for the $\ell^{\rm th}$ blocked and $u^{\rm th}$ direct UEs,
respectively, while the second and third terms are the interference. Thus, the
SINR of the $\ell^{\rm th}$ blocked UE connected to the $k^{\rm th}$ RIS can
be written as

$\displaystyle\mathrm{SINR}_{b,k,\ell}={\dfrac{|\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{b,k,\ell}|^{2}}{\mathcal{I}_{b,k,\ell}+\sigma^{2}_{k,\ell}},}$
(3) where
$\displaystyle\mathcal{I}_{b,k,\ell}=\sum_{\begin{subarray}{c}m=1\vspace*{-0.25mm}\\\
m\neq
k\end{subarray}}^{K}\sum_{\begin{subarray}{c}i=1\end{subarray}}^{L_{m}}|\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{b,m,i}|^{2}+$
$\displaystyle+\sum_{\begin{subarray}{c}i=1\vspace*{-0.1mm}\\\
i\neq\ell\end{subarray}}^{L_{k}}|\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{b,k,i}|^{2}+\sum_{n=1}^{U_{d}}|\mathbf{h}_{k,\ell}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{H}_{k}^{H}\mathbf{w}_{d,n}|^{2},$

while the SINR of the $u^{\rm th}$direct UE is

$\mathrm{SINR}_{d,u}=\dfrac{|\mathbf{h}_{d,u}^{H}\mathbf{w}_{d,u}|^{2}}{\sum\limits_{\begin{subarray}{c}n=1\vspace*{-0.25mm}\\\
n\neq
u\end{subarray}}^{U_{d}}|\mathbf{h}_{d,u}^{H}\mathbf{w}_{d,n}|^{2}+\sum\limits_{\begin{subarray}{c}m=1\end{subarray}}^{K}\sum\limits_{\begin{subarray}{c}\ell=1\end{subarray}}^{L_{m}}|\mathbf{h}_{d,u}^{H}\mathbf{w}_{b,m,\ell}|^{2}+\sigma^{2}_{u}}.$
(4)

Algorithm 1

1: Input: The allowed number of UEs to be scheduled, $U_{\max}$. The minimum
value of required receive power, $p_{\rm min}$.

2: Output: Scheduled UEs and assigned RISs.

3: Turn off the RISs and broadcast the signal.

4: Save the receive power of the UEs.

5: for $k=1$ to $K$ do

6: Turn on the $k^{\rm th}$ RIS and broadcast the signal.

7: Save the receive power of the UEs.

8: Turn off the $k^{\rm th}$ RIS.

9: end for

10: Schedule up to $U_{\max}$ number of the UEs, whose maximum receive power
is more than $p_{\rm min}$ and assign the RISs 111The UEs with the highest
receive powers can be scheduled and each UE can be assigned to the RIS that
maximizes its received power..

##  III SINR Maximization Problem

In this section, first, we employ the BS-UE-ZF beamforming approach in which
we cancel the interference at the UEs. Then, for the special case when one UE
is related to each of the RISs, we design the BS-RIS-ZF beamforming approach
in which we cancel the interference at the RISs. For each of the beamforming
methods, we design the phase shifts of the RISs to maximize the SINR of the
blocked UEs and obtain asymptotic results when the number of BS antennas tends
to infinity, i.e., $M\longrightarrow\infty$.

###  III-A BS-UE-ZF Beamforming

In the BS-UE-ZF beamforming, we design the beamforming vectors in such a way
that they enforce the interference at the UEs to zero. Actually, considering
$\mathbf{g}_{{}_{k,\ell}}=\mathbf{H}_{k}\mbox{\boldmath{$\Phi$}}_{k}^{H}\mathbf{h}_{k,\ell}$
as the channel vector between the BS and the $\ell^{\rm th}$ blocked UE
connected to $k^{\rm th}$ RIS and defining
$\mathbf{Q}_{1}=\begin{bmatrix}\mathbf{g}_{{}_{1,1}}\dots\mathbf{g}_{{}_{1,L_{1}}}\dots\mathbf{g}_{{}_{K,1}}\dots\mathbf{g}_{{}_{K,L_{K}}}\
\mathbf{h}_{d,1}\dots\mathbf{h}_{d,U_{d}}\end{bmatrix}^{H},$ the ZF
beamforming matrix is given as

$\mathbf{W}_{\mathrm{ZF}}=\mathbf{Q}_{1}^{H}(\mathbf{Q}_{1}\mathbf{Q}_{1}^{H})^{-1},$
(5)

which under the condition $M\geq(U_{b}+U_{d})$, eliminates the inter-user
interference [17]. Therefore, the SINR of the $\ell^{\rm th}$ blocked UE
connected to the $k^{\rm th}$ RIS becomes

$\displaystyle\mathrm{SINR}_{b,k,\ell}$
$\displaystyle=\dfrac{|\mathbf{g}_{k,\ell}^{H}\mathbf{Q}_{1}^{H}(\mathbf{Q}_{1}\mathbf{Q}_{1}^{H})^{-1}\mathbf{e}_{k}|^{2}}{\sigma^{2}_{k,\ell}}=\dfrac{|\mathbf{v}_{k}^{H}\mathbf{q}_{k,\ell}|^{2}}{\sigma^{2}_{k,\ell}},$
(6)

where $\mathbf{q}_{k,\ell}={\rm
diag}(\mathbf{h}_{k,\ell}^{H})\mathbf{H}_{k}^{H}\mathbf{Q}_{1}^{H}(\mathbf{Q}_{1}\mathbf{Q}_{1}^{H})^{-1}\mathbf{e}_{k}$,
$\mathbf{e}_{k}$ is the unit-base vector with non-zero value at the $k^{\rm
th}$ component, $\mathbf{v}_{k}={\rm Vec}(\mbox{\boldmath{$\Phi$}}_{k}^{H})$
and operator ${\rm Vec}(.)$ returns the vector of the diagonal components of
the diagonal matrix.

In order to jointly maximize the SINR of the blocked UEs, as a suboptimal
solution, for $k\in\mathcal{K}$ we maximize the sum of the SINRs of the UEs
connected to the $k^{\rm th}$ RIS, i.e.,

$\displaystyle\max_{\mathbf{v}_{k}}\sum_{\ell=1}^{L_{k}}|\mathbf{v}_{k}^{H}\mathbf{q}_{k,\ell}|^{2}\equiv\max_{\mathbf{v}_{k}}\mathbf{v}_{k}^{H}\left(\sum_{\ell=1}^{L_{k}}\mathbf{q}_{k,\ell}\mathbf{q}_{k,\ell}^{H}\right)\mathbf{v}_{k}$
(7) $\displaystyle\,\,\mathrm{s.t.}\,|\mathbf{v}_{k}|^{2}\leq
1\quad\quad\quad\quad\mathrm{s.t.}\,|\mathbf{v}_{k}|^{2}\leq 1,$

The optimum value of $\mathbf{v}_{k}$ in (7) is equal to the eigenvector of
matrix $\sum_{\ell=1}^{L_{k}}\mathbf{q}_{k,\ell}\mathbf{q}_{k,\ell}^{H}$
corresponding to its maximum eigenvalue. Thus, for $L_{k}=1$, the optimum
value of $\phi_{k,i}$ is

$\displaystyle\phi_{k,i}=-\sphericalangle(h^{*}_{k,1,i}[\mathbf{H}_{k}^{H}\mathbf{Q}_{1}^{H}(\mathbf{Q}_{1}\mathbf{Q}_{1}^{H})^{-1}\mathbf{e}_{k}]_{{}_{i}}),k\in\mathcal{K},i\in\mathcal{N}.$
(8)

In the following proposition, we obtain the asymptotic form of (8) as
$M\longrightarrow\infty$.

######  Proposition 1.

Considering the BS-UE-ZF beamforming in (5) and the asymptotic regime where
$M\longrightarrow\infty$, when one UE is connected to the $k^{\rm th}$ RIS the
phase shifts of the RIS elements that maximize the SINR of the UEs can be
found by solving the following equation system:

$\phi_{k,i}=-\sphericalangle(h_{k,1,i}^{*}\sum_{\ell=1}^{N}R_{i,\ell}e^{-j\phi_{k,\ell}}h_{k,1,\ell})\
i\in\mathcal{N},$ (9)

where $R_{k,i,\ell}$ is the element $(i,\ell)$ of the correlation matrix
$\mathbf{R}_{k}=\mathbb{E}\\{\mathbf{H}_{k}^{H}\mathbf{H}_{k}\\}$.

###### Proof.

Considering
$\mathbf{Q}_{1}=\begin{bmatrix}\mathbf{g}_{{}_{1,1}}\dots\mathbf{g}_{{}_{K,1}}\
\mathbf{h}_{d,1}\dots\mathbf{h}_{d,U_{d}}\end{bmatrix}^{H},$ for
$k\in\mathcal{K}$ we have

$\displaystyle\mathbf{H}_{k}^{H}\mathbf{Q}_{1}^{H}(\mathbf{Q}_{1}\mathbf{Q}_{1}^{H})^{-1}\mathbf{e}_{k}=$
$\displaystyle\mathbf{H}_{k}^{H}\begin{bmatrix}\mathbf{H}_{1}\mbox{\boldmath{$\Phi$}}^{H}_{1}\mathbf{h}_{1,1}\dots\mathbf{H}_{K}\mbox{\boldmath{$\Phi$}}^{H}_{K}\mathbf{h}_{K,1}\
\ \mathbf{h}_{d,1}\dots\mathbf{h}_{d,U_{d}}\end{bmatrix}$ (10)
$\displaystyle\times\scriptsize{\begin{bmatrix}\mathbf{g}_{{}_{1,1}}^{H}\mathbf{g}_{{}_{1,1}}&\dots&\mathbf{g}_{{}_{1,1}}^{H}\mathbf{g}_{{}_{K,1}}&\mathbf{g}_{{}_{1,1}}^{H}\mathbf{h}_{d,1}&\dots&\mathbf{g}_{{}_{1,1}}^{H}\mathbf{h}_{d,U_{d}}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
\mathbf{g}_{{}_{K,1}}^{H}\mathbf{g}_{{}_{1,1}}&\dots&\mathbf{g}_{{}_{K,1}}^{H}\mathbf{g}_{{}_{K,1}}&\mathbf{g}_{{}_{K,1}}^{H}\mathbf{h}_{d,1}&\dots&\mathbf{g}_{{}_{K,1}}^{H}\mathbf{h}_{d,U_{d}}\\\
\\\
\mathbf{h}_{d,1}^{H}\mathbf{g}_{{}_{1,1}}&\dots&\mathbf{h}_{d,1}^{H}\mathbf{g}_{{}_{K,1}}&\mathbf{h}_{d,1}^{H}\mathbf{h}_{d,1}&\dots&\mathbf{h}_{d,1}^{H}\mathbf{h}_{d,U_{d}}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
\mathbf{h}_{d,U_{d}}^{H}\mathbf{g}_{{}_{1,1}}&\dots&\mathbf{h}_{d,U_{d}}^{H}\mathbf{g}_{{}_{K,1}}&\mathbf{h}_{d,U_{d}}^{H}\mathbf{h}_{d,1}&\dots&\mathbf{h}_{d,U_{d}}^{H}\mathbf{h}_{d,U_{d}}\end{bmatrix}^{-1}}\mathbf{e}_{k}.$

Also, if
$\mathbf{H}_{k}=\begin{bmatrix}\mathbf{h}^{\prime}_{k,1}&\dots&\mathbf{h}^{\prime}_{k,N}\end{bmatrix}$,
as $M\longrightarrow\infty$, we get $\mathbf{h}^{\prime
H}_{k,\ell}\mathbf{h}^{\prime}_{n,m}\longrightarrow\mathbb{E}\\{\mathbf{h}^{\prime
H}_{k,\ell}\mathbf{h}^{\prime}_{n,m}\\}$ [18], and thus

$\mathbf{H}_{k}^{H}\mathbf{H}_{n}\longrightarrow\begin{cases}\mathbf{R}_{k}&n=k\\\
\mathbf{0}_{N\times N}&n\neq k\end{cases}.$ (11)

where $\mathbf{R}_{k}=\mathbb{E}\\{\mathbf{H}_{k}^{H}\mathbf{H}_{k}\\}$ and
$\mathbf{0}_{N\times N}$ is an $N\times N$ zero matrix. Therefore, as
$M\longrightarrow\infty$ we have

$\displaystyle\mathbf{H}_{k}^{H}\mathbf{Q}_{1}^{H}(\mathbf{Q}_{1}\mathbf{Q}_{1}^{H})^{-1}\mathbf{e}_{k}=\begin{bmatrix}\mathbf{0}\dots\mathbf{R}_{k}\mbox{\boldmath{$\Phi$}}_{k}^{H}\mathbf{h}_{k,1}\dots\mathbf{0}\end{bmatrix}$
$\displaystyle\times\mathrm{diag}\Big{(}{\small\frac{1}{\mathbf{h}_{1,1}^{H}\mbox{\boldmath{$\Phi$}}_{1}\mathbf{R}_{1}\mbox{\boldmath{$\Phi$}}_{1}^{H}\mathbf{h}_{1,1}},\dots,\frac{1}{\mathbf{h}_{K,1}^{H}\mbox{\boldmath{$\Phi$}}_{K}\mathbf{R}_{K}\mbox{\boldmath{$\Phi$}}_{K}^{H}\mathbf{h}_{K,1}}},$
$\displaystyle{\small\frac{1}{\mathbf{h}_{d,1}^{H}\mathbf{h}_{d,1}},\dots,\frac{1}{\mathbf{h}_{d,U_{d}}^{H}\mathbf{h}_{d,U_{d}}}}\Big{)}\mathbf{e}_{k}=\frac{\mathbf{R}_{k}\mbox{\boldmath{$\Phi$}}_{k}^{H}\mathbf{h}_{k,1}}{\mathbf{h}_{k,1}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{R}_{k}\mbox{\boldmath{$\Phi$}}_{k}^{H}\mathbf{h}_{k}}$
(12)

and thus (8) would be equal to

$\displaystyle\phi_{k,i}$
$\displaystyle=-\sphericalangle(\frac{1}{\mathbf{h}_{k,1}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{R}_{k}\mbox{\boldmath{$\Phi$}}_{k}^{H}\mathbf{h}_{k,1}}h_{k,1,i}^{*}\sum_{\ell=1}^{N}R_{i,\ell}e^{-j\phi_{k,\ell}}h_{k,1,\ell})$
$\displaystyle=-\sphericalangle(h_{k,1,i}^{*}\sum_{\ell=1}^{N}R_{i,\ell}e^{-j\phi_{k,\ell}}h_{k,1,\ell}),\
\ k\in\mathcal{K},i\in\mathcal{N},$ (13)

where (III-A) is resulted from the fact that
$\mathbf{h}_{k,1}^{H}\mbox{\boldmath{$\Phi$}}_{k}\mathbf{R}_{k}\mbox{\boldmath{$\Phi$}}_{k}^{H}\mathbf{h}_{k,1}$
is a real and positive number. ∎

######  Corollary 1.

For the special case that the channel vectors between the BS and each of the
elements of the $k^{\rm th}$ RIS are independent, i.e., $\
\mathbf{R}_{k}=\mathbf{I}$, employing the BS-UE-ZF approach, the SINR of the
blocked UE connected to the $k^{\rm th}$ RIS is maximized by considering
random phase shifts for the RIS elements, as $M\longrightarrow\infty$.

###### Proof.

By substituting $\mathbf{R}_{k}$ with $\mathbf{I}$ in (9), we get
$\phi_{k,i}=\phi_{k,i}\ \forall k,i$, meaning that $\phi_{k,i}$ can be
randomly chosen. ∎

###  III-B BS-RIS-ZF Beamforming

In this section, we consider the case that one UE is related to each RIS. We
design a novel approach, i.e., BS-RIS-ZF, in which the beamforming vectors are
derived to enforce the interference at the RISs and direct UEs to zero222Note
that the BS-RIS-ZF beamforming approach can also be implemented for the
general scenario; But, in this case, it needs to design the phase shifts of
the RISs to cancel the interference which is out of scope of this letter..
Thus, the beamforming vectors should satisfy the following conditions for
$k\in\mathcal{K}$ and $u\in\\{1,\dots,U_{d}\\}$:

$\displaystyle\mathbf{H}_{k}^{H}\mathbf{w}_{b,k,1}=\mathbf{1},\
\mathbf{H}_{m}^{H}\mathbf{w}_{b,k,1}=\mathbf{0}\ \forall m\neq k,\
\mathbf{h}_{d,u}^{H}\mathbf{w}_{b,k,1}=0,$
$\displaystyle{\mathbf{h}_{d,u}^{H}\mathbf{w}_{d,u}=1,\
\mathbf{H}_{k}^{H}\mathbf{w}_{d,u}=\mathbf{0},\
\mathbf{h}_{d,n}^{H}\mathbf{w}_{d,u}=0}\ \forall n\neq u.$ (14)

By defining
$\mathbf{Q}_{2}\triangleq\begin{bmatrix}\mathbf{H}_{1}\dots\mathbf{H}_{K}\ \
\mathbf{h}_{d,1}\dots\mathbf{h}_{d,U_{d}}\end{bmatrix}^{H}$, the BS-RIS-ZF
beamforming matrix can be written as

$\mathbf{W}_{\rm
ZF}^{\prime}=\mathbf{Q}_{2}^{H}(\mathbf{Q}_{2}\mathbf{Q}_{2}^{H})^{-1}\mbox{\boldmath{$\Gamma$}},$
(15)

where $\mbox{\boldmath{$\Gamma$}}=$

$\scriptsize{\begin{bmatrix}1&\dots&1&0&&&\dots&&0&\\\
0&\dots&0&1&\dots&1&0&\dots&0&\\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots&\mathbf{0}_{K\times
U_{d}}\\\ 0&&&\ldots&&0&1&\ldots&1&\\\ &&&&{\mathbf{0}_{U_{d}\times
NK}}&&&&&\mathbf{I}_{U_{d}}\end{bmatrix}}^{T}$. Thus, the SINR of the blocked
UE connected to $k^{\rm th}$ RIS is

$\mathrm{SINR}_{b,k,1}=\dfrac{|\sum\limits_{i=1}^{N}e^{j\phi_{i,k}}h_{k,1,i}^{*}[\mathbf{H}_{k}^{H}\mathbf{Q}_{2}^{H}(\mathbf{Q}_{2}\mathbf{Q}_{2}^{H})^{-1}\mbox{\boldmath{$\Gamma$}}\mathbf{e}_{k}]_{{}_{i}}|^{2}}{\sigma^{2}_{k}}.$
(16)

Similar to the previous subsection, the optimal phase shifts of the RIS
elements make the phases of the summation terms in the numerator of the SINR
ratio equal to zero; thus,

$\phi_{k,i}=-\sphericalangle(h_{k,1,i}^{*}[\mathbf{H}_{k}^{H}\mathbf{Q}_{2}^{H}(\mathbf{Q}_{2}\mathbf{Q}_{2}^{H})^{-1}\mbox{\boldmath{$\Gamma$}}\mathbf{e}_{k}]_{{}_{i}})\hskip
2.84526ptk\in\mathcal{K},i\in\mathcal{N}$ (17)

The major benefit of the BS-RIS-ZF beamforming is the availability of the
closed-form equations for the RIS phase shifts. However, we must note that in
the BS-RIS-ZF approach we need to satisfy $M>NK+U_{d}$ to completely remove
the interference, while increasing the number of the BS antennas increases the
complexity of the channel estimation [19]. Therefore, there exists a trade-off
between the complexity of the phase shift design and channel estimation.

Now, in the following, we evaluate the asymptotic expressions for the optimal
phase shifts and maximum $\mathrm{SINR}_{b,k,1}$ as $M\longrightarrow\infty$.

######  Proposition 2.

Considering the proposed BS-RIS-ZF beamforming, as $M\longrightarrow\infty$,
the RIS phase shifts that maximize the SINR of the blocked UE connected to the
$k^{\rm th}$ RIS are

$\phi_{k,i}=-\sphericalangle(h_{k,i}^{*}f_{k,i}),\ i\in\mathcal{N}$ (18)

and the maximum value of $\mathrm{SINR}_{b,k,1}$ is

$\mathrm{SINR}_{b,k,1}^{*}=\frac{1}{\sigma^{2}_{k}}(\sum_{i=1}^{N}|f_{k,i}||h_{k,i}|)^{2},$
(19)

where $f_{k,i}$ is the $i^{\rm th}$ element of the vector

$\mathbf{f}_{k}=\begin{bmatrix}\mathbf{0}_{N\times(k-1)N}\ \mathbf{R}_{k}\
\mathbf{0}_{N\times((K-k)N+U_{d})}\end{bmatrix}$
$\times{\mathrm{blkdiag}}(\mathbf{R}_{1}^{-1},\dots,\mathbf{R}_{K}^{-1},\mathbf{I}_{U_{d}})\mbox{\boldmath{$\Gamma$}}\,\mathbf{e}_{k},$

and $\mathrm{blkdiag}(.)$ returns a block diagonal matrix constructed by the
arguments.

###### Proof.

As $M\longrightarrow\infty$, employing (11), we have

$(\mathbf{Q}_{2}\mathbf{Q}_{2}^{H})^{-1}={\mathrm{blkdiag}}(\mathbf{R}_{1}^{-1},\dots,\mathbf{R}_{K}^{-1},\mathbf{I}_{U_{d}}),$
(20)

and

$\mathbf{H}_{k}^{H}\mathbf{Q}_{2}^{H}=\begin{bmatrix}\mathbf{0}_{N\times(k-1)N}&\mathbf{R}_{k}&\mathbf{0}_{N\times((K-k)N+U_{d})}\end{bmatrix}.$
(21)

Thus, substituting (20) and (21) in (17), the asymptotic expressions for the
optimal phase shifts are as in (18). Then, substituting the phase shifts
obtained by (18), (20), and (21) in (16), the asymptotic value of maximum
$\mathrm{SINR}_{k}$ would be obtained as in (19). ∎

Analysis of the rank of matrix $\mathbf{Q}_{2}$: Regarding that the
performance of the BS-RIS-ZF approach can be affected by the rank of matrix
$\mathbf{Q}_{2}$, we analyze the rank of this matrix in this section. Assuming
that $\mathbf{H}_{k}=\mathbf{F}_{k}\mathbf{D}_{k}$, where $\mathbf{F}_{k}$ is
an $M\times N$ matrix with i.i.d. normal random variable elements and
$\mathbf{D}_{k}=\mathbf{R}_{k}^{1/2}$, the matrix $\mathbf{Q}_{2}$ can be
rewritten as
$\begin{bmatrix}\mathbf{F}_{1}\mathbf{D}_{1}\dots\mathbf{F}_{K}\mathbf{D}_{K}\
\ \mathbf{H}_{d}\end{bmatrix}^{H},$ where
$\mathbf{H}_{d}=[\mathbf{h}_{d,1}\dots\mathbf{h}_{d,U_{d}}]$. Considering the
fact that the elements of the random matrices $\mathbf{F}_{k}$, $\
k\in\mathcal{K}$, and $\mathbf{H}_{d}$ are independent of each other, we
conclude that the rank of matrix $\mathbf{Q}_{2}$ is equal to
$\sum_{k=1}^{K}\mathrm{rank}(\mathbf{D}_{k}^{H}\mathbf{F}_{k}^{H})+\mathrm{rank}(\mathbf{H}_{d})$.
Also, from [20], we have

$\mathrm{rank}(\mathbf{D}_{k}^{H}\mathbf{F}_{k}^{H})\leqslant\min\\{\mathrm{rank}(\mathbf{D}_{k}^{H}),\mathrm{rank}(\mathbf{F}_{k}^{H})\\},$

and $\mathrm{rank}(\mathbf{F}_{k}^{H})\leqslant\min\\{M,N\\}$. Hence, assuming
that $N\leqslant M$, we get
$\mathrm{rank}(\mathbf{D}_{k}^{H}\mathbf{F}_{k}^{H})\leqslant\mathrm{rank}(\mathbf{D}_{k}^{H})$
and thus,
$\mathrm{rank}(\mathbf{Q}_{2})\leqslant\sum_{k=1}^{K}\mathrm{rank}(\mathbf{D}_{k}^{H})+\mathrm{rank}(\mathbf{H}_{d}).$
Moreover, the elements of $\mathbf{H}_{d}$ are independently distributed and
thus, $\mathrm{rank}(\mathbf{H}_{d})=\min\\{M,U_{d}\\}$. Therefore, assuming
that $U_{d}<M$ we have
$\mathrm{rank}(\mathbf{Q}_{2})\leqslant\sum_{k=1}^{K}\mathrm{rank}(\mathbf{D}_{k}^{H})+U_{d}$.
Consequently, we can conclude that the correlation of the BS to RIS channels
can restrict the rank of matrix $\mathbf{Q}_{2}$.

###  III-C Computational Complexity.

The number of multiplications required to compute the beamforming vectors and
the RIS phase shifts in the BS-UE-ZF approach is equal to
$U_{b}((U_{b}+U_{d})^{3}+2M(U_{b}+U_{d})^{2}+MN(U_{b}+U_{d})+MN^{2}+MN+1)$,
while for the BS-RIS-ZF method, it is equal to
$U_{b}((NU_{b}+U_{d})^{3}+(2M+U_{b}+K+d)(NU_{b}+U_{d})^{2}+MN(NU_{b}+U_{d})+1)$.
We observe that the complexity of both of the approaches with respect to $M$
is of the order of $\mathcal{O}(M)$. Also, their complexities with respect to
$N$ are of the order of $\mathcal{O}(N)$ and $\mathcal{O}(N^{3})$,
respectively. Therefore, the complexity of the BS-RIS-ZF approach is more
sensitive to $N$.

##  IV Simulation Results

In this section, we conduct simulations to verify the performance of the
proposed beamforming and phase shift design approaches. In this regard, we use
the channel estimation approach proposed in [19] and compare the results with
the case of perfect channel estimation. The RIS elements correlation model is
adopted from [21]. The minimum distance between the elements of each of the
RISs is equal to $d=\lambda$ and $d=\lambda/4$ for the cases of the i.i.d. and
correlated channels, respectively, where $\lambda$ is the wavelength. Also,
the area of each RIS element is equal to $A=d^{2}$ and $\mu\lambda^{2}=-75$dB
where $\mu$ is the average intensity attenuation [21]. Moreover, the carrier
frequency is $f=1800$ MHz and the power spectral density of the AWGN at the
UEs is equal to $-174~{}\rm{dBm}/\rm{Hz}$.

(a)

(b)

Figure 2:  Average sum rate exploiting the BS-UE-ZF approach vs. the number of
the BS antennas ($M$), $K=4$, $U_{d}=2$ (a): i.i.d. (b): Correlated channels.

In Fig. 2, we illustrate the average sum rate versus the number of the BS
antennas, for various phase shift design approaches and the number of RIS
elements in the BS-UE-ZF beamforming scenario, considering both the i.i.d. and
correlated channels. It can be noticed that in both cases increasing the
number of the elements in the RISs improves the average sum rate, and $N=1$
leads to the lowest average sum rate. In Fig.2(a), we observe that for the
i.i.d. channels, by increasing the number of the BS antennas the average sum
rate of random phase shifts tends to the average sum rate of the optimal ones
(see Corollary 1). In Fig. 2(b), we observe that in the case of the correlated
channels, by increasing the number of the BS antennas, the average sum rate of
the asymptotic phase shifts converges to the average sum rate of the optimal
phase shifts. Moreover, both of these phase shift design approaches achieve a
much more average sum rate compared to random phase shifts.

In Fig. 3, we plot the average sum rate versus the number of the BS antennas
for the various phase shift design approaches in the BS-RIS-ZF beamforming
scenario, and also depict the asymptotic average sum rate obtained by the
asymptotic SINRs. We observe that for both the i.i.d. and correlated channels,
the rates of the asymptotic phase shifts and the asymptotic SINRs accurately
track the optimal phase shifts rate. Moreover, it can be observed that in the
case of the i.i.d. channels when the condition $M\geqslant KN+U_{d}$ is
satisfied, the average sum rates start to increase, and the correlated
channels do not have a restrictive impact on the start point of rate arising.

Furthermore, in Fig. 2 and Fig. 3, we illustrate the curves corresponding to
the case that we have channel estimation error (the channel estimation
approach in [19] is used). We observe that in both of the i.i.d. and
correlated channels there is not a significant reduction in the sum rate of
the BS-UE-ZF and BS-RIS-ZF approaches when we have some error in the channel
estimation.

(a)

(b)

Figure 3:  Average sum rate exploiting the BS-RIS-ZF approach vs. the number
of the BS antennas ($M$), $K=4$, $U_{d}=2$ (a): i.i.d. (b): Correlated
channels.

##  V Conclusion

In this letter, we considered a multi-RIS, multi-user massive MIMO system and
investigated the SINR maximization problem for the asymptotic scenario where
the number of the BS antennas tends to infinity. We examined two ZF
beamforming approaches, i.e., BS-UE-ZF and BS-RIS-ZF which null the
interference at the UEs and the RISs, respectively. For each of the proposed
methods, we obtained the optimal phase shifts of the elements of the RISs that
maximize the SINR of the UEs. Considering the BS-UE-ZF beamforming approach,
we showed that when the channels of the RIS elements are independent, random
phase shifts can achieve the maximum SINR for an asymptotic large number of BS
antennas. For the BS-UE-ZF beamforming method, the simulation results showed
that the asymptotic expressions of the RIS phase shifts achieve the rate of
the optimal phase shifts, even for a small number of the BS antennas.

## References

  * [1] Q. Wu and R. Zhang, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless network,” _IEEE Commun. Mag._ , vol. 58, no. 1, pp. 106–112, 2019.
  * [2] S. Gong _et al._ , “Toward smart wireless communications via intelligent reflecting surfaces: A contemporary survey,” _IEEE Commun. Surveys Tutorials_ , vol. 22, no. 4, pp. 2283–2314, 2020.
  * [3] E. Björnson _et al._ , “Reconfigurable intelligent surfaces: A signal processing perspective with wireless applications,” _IEEE Signal Processing Mag._ , vol. 39, no. 2, pp. 135–158, 2022.
  * [4] Y. Liu _et al._ , “Dynamic-controlled RIS assisted multi-user MISO downlink system: Joint beamforming design,” _IEEE Trans. on Green Commun. and Networking_ , 2021.
  * [5] H. Guo, Y.-C. Liang, J. Chen, and E. G. Larsson, “Weighted sum-rate maximization for reconfigurable intelligent surface aided wireless networks,” _IEEE Trans. on Wireless Commun._ , vol. 19, no. 5, pp. 3064–3076, 2020.
  * [6] J. Wang, H. Wang, Y. Han, S. Jin, and X. Li, “Joint transmit beamforming and phase shift design for reconfigurable intelligent surface assisted MIMO systems,” _IEEE Trans. on Cognitive Commun. and Networking_ , vol. 7, no. 2, pp. 354–368, 2021.
  * [7] Z. Yang _et al._ , “Energy-efficient wireless communications with distributed reconfigurable intelligent surfaces,” _IEEE Trans. on Wireless Commun._ , 2022.
  * [8] C. Huang, A. Zappone, G. C. Alexandropoulos, M. Debbah, and C. Yuen, “Reconfigurable intelligent surfaces for energy efficiency in wireless communication,” _IEEE Trans. on Wireless Commun._ , vol. 18, no. 8, pp. 4157–4170, 2019.
  * [9] Z. Yang, W. Xu, C. Huang, J. Shi, and M. Shikh-Bahaei, “Beamforming design for multiuser transmission through reconfigurable intelligent surface,” _IEEE Trans. on Commun._ , vol. 69, no. 1, pp. 589–601, 2020.
  * [10] A. Kammoun, A. Chaaban, M. Debbah, M.-S. Alouini _et al._ , “Asymptotic max-min SINR analysis of reconfigurable intelligent surface assisted MISO systems,” _IEEE Trans. on Wireless Commun._ , vol. 19, no. 12, pp. 7748–7764, 2020.
  * [11] A. Subhash _et al._ , “Optimal phase shift design for fair allocation in RIS aided uplink network using statistical CSI,” _arXiv preprint arXiv:2209.08983_ , 2022.
  * [12] H. Ibraiwish, A. Elzanaty, Y. H. Al-Badarneh, and M.-S. Alouini, “EMF-aware cellular networks in RIS-assisted environments,” _IEEE Commun. Letters_ , vol. 26, no. 1, pp. 123–127, 2021.
  * [13] A. Subhash _et al._ , “Max-min data rate optimization for RIS-aided uplink communications with green constraints,” _arXiv preprint arXiv:2208.00182_ , 2022.
  * [14] A. Kafizov, A. Elzanaty, L. R. Varshney, and M.-S. Alouini, “Wireless network coding with intelligent reflecting surfaces,” _IEEE Commun. Letters_ , 2021\.
  * [15] E. G. Larsson, O. Edfors, F. Tufvesson, and T. L. Marzetta, “Massive MIMO for next generation wireless systems,” _IEEE Commun. Mag._ , vol. 52, no. 2, pp. 186–195, 2014.
  * [16] Z. Ding and H. Vincent Poor, “A simple design of IRS-NOMA transmission,” _IEEE Commun. Letters_ , vol. 24, no. 5, pp. 1119–1123, 2020.
  * [17] Q. H. Spencer, C. B. Peel, A. L. Swindlehurst, and M. Haardt, “An introduction to the multi-user MIMO downlink,” _IEEE Commun. Mag._ , vol. 42, no. 10, pp. 60–67, 2004.
  * [18] R. Couillet and M. Debbah, _Random matrix methods for wireless communications_. Cambridge University Press, 2011.
  * [19] L. Wei _et al._ , “Channel estimation for RIS-empowered multi-user MISO wireless communications,” _IEEE Trans. on Commun._ , vol. 69, no. 6, pp. 4144–4157, 2021.
  * [20] G. Strang, _Linear algebra and its applications_. Belmont, CA: Thomson, Brooks/Cole, 2006.
  * [21] E. Björnson and L. Sanguinetti, “Rayleigh fading modeling and channel hardening for reconfigurable intelligent surfaces,” _IEEE Wireless Commun. Letters_ , vol. 10, no. 4, pp. 830–834, 2020.


$\displaystyle=\mathbb{E}[f(X)^{2}-f^{\phi}_{0}(X)^{2}-2Y\\{f(X)-f^{\phi}_{0}(X)\\}]$
$\displaystyle=\mathbb{E}[(f(X)-f^{\phi}_{0}(X))\\{f(X)+f^{\phi}_{0}(X)-2\mathbb{E}(Y\mid
X)\\}]$
$\displaystyle=\mathbb{E}[(f(X)-f^{\phi}_{0}(X))(f(X)+f^{\phi}_{0}(X)-2f^{\phi}_{0}(X))]$
$\displaystyle=\mathbb{E}|f(X)-f^{\phi}_{0}(X)|^{2}.$

Ans we have

$\displaystyle\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$
$\displaystyle=\inf_{f\in\mathcal{F}_{CNN}}\mathbb{E}|f(X)-f^{\phi}_{0}(X)|^{2}.$

Besides, note that for least squares $f^{\phi}_{0}=2\eta-1$ and
$\|f^{\phi}_{0}\|_{\infty}=1$, thus taking $T=1$ in (13) is sufficient for the
error control analysis. Let $\mathcal{F}_{CNN}$ be a class of CNNs defined in
(11) bounded by $\mathcal{B}\geq 1+\lambda d^{\alpha/2}$. By Theorem 7, there
exists a function $f$ implemented by CNN with its depth no more than
$L=12M+14$ and its width no more than $\mathcal{W}=\max\\{4d\lfloor
N^{\frac{1}{d}}\rfloor+3d,12N+8\\}$ such that

$\mathbb{E}\|f(X)-f^{\phi}_{0}(X)\|^{2}_{2}\leq
18^{2}{d}\\{\omega_{f^{\phi}_{0}}(N^{-2/d}M^{-2/d})\\}^{2},$

and based on Theorem 6, the empirical $\phi$-risk minimizer
$\hat{f}^{\phi}_{n}$ defined in (12) satisfies, for any $\delta>0$, with
probability at least $1-\delta$,

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f^{\phi}_{0})\leq\frac{16\sqrt{2}B_{\phi}\mathcal{B}\mathcal{S}^{1/2}L^{1/4}}{\sqrt{n}}+2B_{\phi}\mathcal{B}\sqrt{\frac{2\log(1/\delta)}{n}}+2\times
18^{2}\lambda{d}N^{-4\alpha/d}M^{-4\alpha/d},.$

Let $M=\lfloor n^{d/2(d+2\alpha)}\rfloor$, $N=1$, size (number of parameters)
$\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times\\{\lfloor
n^{d/2(d+2\alpha)}\rfloor+14\\}$ and
$\delta=\exp\\{-n^{(d-2\alpha)/(d+2\alpha)}\\}$. By plunging in
$B_{\phi}=2\mathcal{B}$ and above values, we have with probability at least
$1-\exp\\{-n^{(d-2\alpha)/(d+2\alpha)}\\}$,

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}(32\sqrt{2}c+4\sqrt{2})\mathcal{B}^{2}+4\cdot
18^{2}\lambda^{2}d(\max\\{7d,20\\})^{-\frac{4\alpha}{d}}\Big{\\}}n^{-\frac{2\alpha}{(d+2\alpha)}},$

where $c=O(d)$ is a constant independent of $n,\mathcal{B},\alpha$ and
$\lambda$.

The excess risk bound under the approximate low-dimensional manifold
assumption can be obtained in a similar way.

###  B.8 Proof of the logistic loss example

Proof  For the modified logistic loss function
$\phi(a)=\max\\{\log\\{1+\exp(-a)\\},\tau\\}$ with
$\tau=\log\\{1+\exp(-T)\\}$, the corresponding measurable minimizer defined in
(6) is $f^{\phi}_{0,T}$, the truncated version of the minimizer $f_{0}^{\phi}$
under the original logistic loss; see Table 2. As a consequence, under the
modified logistic loss, $\Delta_{\phi}(T)=0$ by definition since the infimum
of the modified logistic loss can be achieved within $[-T,T]$. Let
$\mathcal{F}_{CNN}$ be the class of CNNs defined in (11) with
$\min(|\log[\eta(\textbf{0})/\\{1-\eta(\textbf{0})\\}]|,T\\}+\omega_{f^{\phi}_{0,T}}(\sqrt{d})\leq\mathcal{B}$,
the number of layers $L\leq 12\lfloor n^{2d/(3d+8\alpha)}\rfloor+14$, width
$\mathcal{W}\leq\max\\{7d,20\\}$ and size
$\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times(\lfloor
n^{2d/(3d+8\alpha)}\rfloor+14)$. Then by Theorem 8, let
$\delta=\exp\\{-n^{d/(d+8\alpha/3)}\\}$, we have with probability at least
$1-\exp\\{-n^{d/(d+8\alpha/3)}\\}$, the excess $\phi$-risk of the ERM
$\hat{f}^{\phi}_{n}$ defined in (12) satisfies

$\displaystyle R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}(16\sqrt{2}c+2\sqrt{2})\mathcal{B}+72\lambda\exp(T)\sqrt{d}(\max\\{7d,20\\})^{-\frac{2\alpha}{d}}\Big{\\}}n^{-\frac{\alpha}{0.75d+2\alpha}},$

where $c$ is a constant independent of $n,\mathcal{B},\alpha,\lambda$, and $c$
is independent of $d$ if $d\leq 2$ otherwise $c=O(d)$. Alternatively, (18) can
be simply written as

$R^{\phi}(\hat{f}^{\phi}_{n})-R^{\phi}(f_{0}^{\phi})\leq
C(T,d)n^{-\frac{\alpha}{0.75d+2\alpha}},$

where $C(T,d)=O(d(1+4\lambda d^{\alpha/2})\exp(T))$ is a constant independent
of $n,\mathcal{B}$. Here the prefactor $C(T,d)$ depends on the dimension $d$
at a rate no more than $O(d^{\alpha/2+1})$.

The excess risk bound under the approximate low-dimensional manifold
assumption can be obtained in a similar way.

###  B.9 Proof of the exponential loss example

Proof  The proof is similar to that of the logistic loss example. We omitted
the proof here.

###  B.10 Proof of the SVM example

Proof  Based on Theorem 6, our proof focus on controlling the approximation
error $\inf_{f\in\mathcal{F}_{CNN}}R^{\phi}(f)-R^{\phi}(f^{\phi}_{0})$. Recall
that $f_{0}^{\phi}(x)={\rm sign}(2\eta(x)-1)$, we would firstly approximate
Hölder continuous function $\eta$ by CNNs. Similar to the proof in Theorem 8,
for any $M,N\in\mathbb{N}^{+}$, there exists a function
$\eta^{*}\in\mathcal{F}_{MLP}$ with bound $\mathcal{B}\geq 1$, depth
$L=12M+14$ and width $\mathcal{W}=\max\\{4d\lfloor
N^{\frac{1}{d}}\rfloor+3d,12N+8\\}$ such that
$\|\eta^{*}\|_{\infty}\leq|\eta(0)|+\omega_{\eta}(\sqrt{d})$ and

$|\eta^{*}(x)-\eta(x)|\leq 18\sqrt{d}\omega_{\eta}(N^{-2/d}M^{-2/d}),$

for any $x\in[0,1]^{d}\backslash\Omega$ where $\Omega$ is a set with
arbitrarily small Lebesgue measure. Let
$\varepsilon_{n}=18\sqrt{d}\omega_{\eta}(N^{-2/d}M^{-2/d})$.

We construct the neural network $f_{MLP}$ by adding one layer to $\eta^{*}$ as

$f_{MLP}(x)=2\sigma\Big{[}\frac{1}{\varepsilon_{n}}\\{\eta^{*}(x)-\frac{1}{2}\\}\Big{]}-2\sigma\Big{[}\frac{1}{\varepsilon_{n}}\\{\eta^{*}(x)-\frac{1}{2}\\}-1\Big{]}-1,$

where $\sigma$ is the ReLU activation function. Then we can see that
$\|f_{MLP}\|_{\infty}\leq 1$ and $f_{MLP}(x)=1$ if
$\eta^{*}(x)\geq\varepsilon_{n}+1/2$,
$f_{MLP}(x)=2(\eta^{*}(x)-1/2)/\varepsilon_{n}-1$ if
$1/2+\varepsilon_{n}>\eta^{*}(x)\geq 1/2$ and $f_{MLP}(x)=-1$ if
$\eta^{*}(x)<1/2.$ Let
$\Omega_{\eta,\varepsilon}=\\{x\in[0,1]^{d}:|2\eta(x)-1|>\varepsilon\\}$ for
$\epsilon>0$. Then for $x\in\Omega_{\eta,4\varepsilon_{n}}$, we have
$|f_{MLP}(x)-f^{\phi}_{0}(x)|=0$, since
$\eta^{*}(x)-1/2=(\eta(x)-1/2)-(\eta^{*}(x)-\eta(x))>\varepsilon_{n}$ when
$\eta(x)-1/2>2\varepsilon_{n}$ and $\eta^{*}(x)-1/2<-\varepsilon_{n}$ when
$\eta(x)-1/2<-2\varepsilon_{n}$. Then

$\displaystyle R^{\phi}(f_{MLP})-R^{\phi}(f^{\phi}_{0})=$
$\displaystyle\mathbb{E}\Big{[}\phi(Yf_{MLP}(X))-\phi(Yf_{0}^{\phi}(X))\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}|f_{MLP}(X)-f_{0}^{\phi}(X)||2\eta(X)-1|\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{X\in\Omega_{\eta,4\varepsilon_{n}}}\Big{[}|f_{MLP}(X)-f_{0}^{\phi}(X)||2\eta(X)-1|\Big{]}$
$\displaystyle\leq$ $\displaystyle 8\varepsilon_{n}P(|2\eta(X)-1|\leq
4\varepsilon_{n})$ $\displaystyle\leq$ $\displaystyle 8\times 4^{q}\times
c_{noise}\times\varepsilon_{n}^{q+1}.$

Setting the parameters in $\eta^{*}$ by $N=1$ and $M=12\lfloor
n^{2d/\\{3d+8\alpha(q+1)\\}}\rfloor+14$ and
$\mathcal{S}\leq\mathcal{W}^{2}L\leq\max\\{49d^{2},400\\}\times(\lfloor
n^{2d/(3d+8\alpha(q+1))}\rfloor+14)$, and let $\delta$ be
$\exp(-n^{3d/(3d+8\alpha(q+1))})$, then by Theorem 6, with probability at
least $1-\exp(-n^{3d/(3d+8\alpha(q+1))})$,

$\displaystyle R^{\phi}(\hat{f}_{n}^{\phi})-R^{\phi}(f_{0}^{\phi})\leq$
$\displaystyle\Big{\\{}16\sqrt{2}c+2\sqrt{2}+144\times 4^{q}\lambda
c_{noise}\sqrt{d}(\max\\{7d,20\\})^{-2\alpha/d}\Big{\\}}$ $\displaystyle\hskip
113.81102pt\times n^{-4\alpha(q+1)/\\{3d+8\alpha(q+1)\\}},$

where $c$ is a constant independent with $n,\mathcal{B},\alpha,\lambda$ and
$c$ is independent with $d$ if $d\leq 2$ otherwise $c=O(d)$.

The excess risk bound under the approximate low-dimensional manifold
assumption can be obtained in a similar way.

## References

  * Alipanahi et al. (2015) Babak Alipanahi, Andrew Delong, Matthew T Weirauch, and Brendan J Frey.  Predicting the sequence specificities of dna-and rna-binding proteins by deep learning.  _Nature biotechnology_ , 33(8):831–838, 2015\.
  * Amemiya (1978) Takeshi Amemiya.  The estimation of a simultaneous equation generalized probit model.  _Econometrica: Journal of the Econometric Society_ , pages 1193–1205, 1978.
  * Arora et al. (2018) Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In _International Conference on Machine Learning_ , pages 254–263. PMLR, 2018.
  * Audibert et al. (2007) Jean-Yves Audibert, Alexandre B Tsybakov, et al.  Fast learning rates for plug-in classifiers.  _The Annals of statistics_ , 35(2):608–633, 2007\.
  * Bao et al. (2014) Chenglong Bao, Qianxiao Li, Zuowei Shen, Cheng Tai, Lei Wu, and Xueshuang Xiang.  Approximation analysis of convolutional neural networks.  2014\.  URL https://cpb-us-w2.wpmucdn.com/blog.nus.edu.sg/dist/d/11132/files/2019/07/paper_cnn_copy.pdf.
  * Baraniuk and Wakin (2009) Richard G. Baraniuk and Michael B. Wakin.  Random projections of smooth manifolds.  _Found. Comput. Math._ , 9(1):51–77, 2009.
  * Bartlett et al. (2017) Peter Bartlett, Dylan J Foster, and Matus Telgarsky.  Spectrally-normalized margin bounds for neural networks.  _arXiv preprint arXiv:1706.08498_ , 2017.
  * Bartlett and Mendelson (2006) Peter L Bartlett and Shahar Mendelson.  Empirical minimization.  _Probability theory and related fields_ , 135(3):311–334, 2006.
  * Bartlett et al. (2006) Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe.  Convexity, classification, and risk bounds.  _J. Amer. Statist. Assoc._ , 101(473):138–156, 2006.
  * Bartlett et al. (2021) Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint, 2021.
  * Bauer and Kohler (2019) Benedikt Bauer and Michael Kohler.  On deep learning as a remedy for the curse of dimensionality in nonparametric regression.  _Ann. Statist._ , 47(4):2261–2285, 2019.
  * Ben-David and Urner (2014) Shai Ben-David and Ruth Urner.  The sample complexity of agnostic learning under deterministic labels.  In _Conference on Learning Theory_ , pages 527–542. PMLR, 2014.
  * Ben-David et al. (2012) Shai Ben-David, David Loker, Nathan Srebro, and Karthik Sridharan.  Minimizing the misclassification error rate using a surrogate convex loss.  _arXiv preprint arXiv:1206.6442_ , 2012.
  * Blumer et al. (1989) Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  _Journal of the ACM (JACM)_ , 36(4):929–965, 1989\.
  * Boser et al. (1992) Bernhard E. Boser, Isabelle M. Guyon, and Vladimir N. Vapnik.  A training algorithm for optimal margin classifiers.  In _Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory_ , pages 144–152. ACM Press, 1992.
  * Boucheron et al. (2005) Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi.  Theory of classification: A survey of some recent advances.  _ESAIM: probability and statistics_ , 9:323–375, 2005.
  * Bousquet and Zhivotovskiy (2019) Olivier Bousquet and Nikita Zhivotovskiy.  Fast classification rates without standard margin assumptions.  _arXiv preprint arXiv:1910.12756_ , 2019.
  * Breiman et al. (1984) L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone.  _Classification and Regression Trees_.  Wadsworth and Brooks, Monterey, CA, 1984.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine learning_ , 45(1):5–32, 2001.
  * Chen et al. (2019a) Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao.  Nonparametric regression on low-dimensional manifolds using deep relu networks.  _arXiv preprint arXiv:1908.01842_ , 2019a.
  * Chen et al. (2019b) Minshuo Chen, Haoming Jiang, and Tuo Zhao.  Efficient approximation of deep relu networks for functions on low dimensional manifolds.  _Advances in Neural Information Processing Systems_ , 2019b.
  * Cortes and Vapnik (1995) Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  _Machine learning_ , 20(3):273–297, 1995.
  * Cox (1958) D. R. Cox.  The regression analysis of binary sequences.  _J. Roy. Statist. Soc. Ser. B_ , 20:215–242, 1958.
  * Cristianini and Shawe-Taylor (1999) Nello Cristianini and John Shawe-Taylor.  _An Introduction to Support Vector Machines: And Other Kernel-Based Learning Methods_.  Cambridge University Press, USA, 1999.
  * Fang et al. (2020) Zhiying Fang, Han Feng, Shuo Huang, and Ding-Xuan Zhou.  Theory of deep convolutional neural networks ii: Spherical analysis.  _Neural Networks_ , 131:154–162, 2020.
  * Farrell et al. (2021) Max H. Farrell, Tengyuan Liang, and Sanjog Misra.  Deep neural networks for estimation and inference.  _Econometrica_ , 89(1):181–213, 2021.
  * Freund et al. (1996) Yoav Freund, Robert E Schapire, et al.  Experiments with a new boosting algorithm.  In _icml_ , volume 96, pages 148–156. Citeseer, 1996.
  * Friedman et al. (2000) Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  Additive logistic regression: a statistical view of boosting.  _Ann. Statist._ , 28(2):337–407, 2000.
  * Golowich et al. (2020) Noah Golowich, Alexander Rakhlin, and Ohad Shamir.  Size-independent sample complexity of neural networks.  volume 9, pages 473–504, 2020.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, Cambridge, MA, 2016.
  * Hastie et al. (2001) Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  _The Elements of Statistical Learning_.  Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001.
  * Jiao et al. (2021) Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang.  Deep nonparametric regression on approximately low-dimensional manifolds, 2021.
  * Kääriäinen (2006) Matti Kääriäinen.  Active learning in the non-realizable case.  In _International Conference on Algorithmic Learning Theory_ , pages 63–77. Springer, 2006.
  * Kalai and Sastry (2009) Adam Tauman Kalai and Ravi Sastry.  The isotron algorithm: High-dimensional isotonic regression.  In _COLT_. Citeseer, 2009.
  * Kalai et al. (2008) Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio.  Agnostically learning halfspaces.  _SIAM J. Comput._ , 37(6):1777–1805, 2008.
  * Kim et al. (2021) Yongdai Kim, Ilsang Ohn, and Dongha Kim.  Fast convergence rates of deep neural networks for classification.  _Neural Networks_ , 138:179–197, 2021.
  * Kleinbaum et al. (2002) David G Kleinbaum, K Dietz, M Gail, Mitchel Klein, and Mitchell Klein.  _Logistic regression_.  Springer, 2002.
  * Kohler et al. (2019) Michael Kohler, Adam Krzyzak, and Sophie Langer.  Estimation of a function of low local dimensionality by deep neural networks.  _arXiv preprint arXiv:1908.11140_ , 2019.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _Nature_ , 521(7553):436–444, 2015.
  * Li et al. (2018) Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao.  On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond.  _arXiv preprint arXiv:1806.05159_ , 2018.
  * Lin and Zhang (2019) Shan Lin and Jingwei Zhang.  Generalization bounds for convolutional neural networks.  _arXiv preprint arXiv:1910.01487_ , 2019.
  * Lin (2004) Yi Lin.  A note on margin-based loss functions in classification.  _Statistics & Probability Letters_, 68(1):73–82, 2004.
  * Liu and Shen (2006) Yufeng Liu and Xiaotong Shen.  Multicategory $\psi$-learning.  _Journal of the American Statistical Association_ , 101(474):500–509, 2006.
  * Lu et al. (2017) Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang.  The expressive power of neural networks: A view from the width.  _arXiv preprint arXiv:1709.02540_ , 2017.
  * Lugosi and Vayatis (2004) Gábor Lugosi and Nicolas Vayatis.  On the Bayes-risk consistency of regularized boosting methods.  _The Annals of Statistics_ , 32(1):30 – 55, 2004\.
  * Mammen and Tsybakov (1999) Enno Mammen and Alexandre B. Tsybakov.  Smooth discrimination analysis.  _Ann. Statist._ , 27(6):1808–1829, 1999.
  * Marron et al. (2007) J. S. Marron, Michael J. Todd, and Jeongyoun Ahn.  Distance-weighted discrimination.  _Journal of the American Statistical Association_ , 102(480):1267–1271, 2007.
  * Marron et al. (1983) James Stephen Marron et al.  Optimal rates of convergence to bayes risk in nonparametric discrimination.  _The Annals of Statistics_ , 11(4):1142–1155, 1983.
  * Masnadi-Shirazi and Vasconcelos (2009) Hamed Masnadi-Shirazi and Nuno Vasconcelos.  On the design of loss functions for classification: theory, robustness to outliers, and savageboost.  _Advances in Neural Information Processing Systems 21 2009._ , 21:1049–1056, 2009.
  * Masnadi-Shirazi and Vasconcelos (2015) Hamed Masnadi-Shirazi and Nuno Vasconcelos.  A view of margin losses as regularizers of probability estimates.  _J. Mach. Learn. Res._ , 16:2751–2795, 2015.
  * Massart and Élodie Nédélec (2006) Pascal Massart and Élodie Nédélec.  Risk bounds for statistical learning.  34(5):2326 – 2366, 2006.
  * Mohri et al. (2018) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of Machine Learning_.  MIT Press, Cambridge, MA, 2018.
  * Nakada and Imaizumi (2019) Ryumei Nakada and Masaaki Imaizumi.  Adaptive approximation and estimation of deep neural network with intrinsic dimensionality.  _arXiv preprint arXiv:1907.02177_ , 2019.
  * Nock and Nielsen (2008) Richard Nock and Frank Nielsen.  On the efficient minimization of classification calibrated surrogates.  _Advances in neural information processing systems_ , 21:1201–1208, 2008.
  * Oono and Suzuki (2019) Kenta Oono and Taiji Suzuki.  Approximation and non-parametric estimation of resnet-type convolutional neural networks.  In _International Conference on Machine Learning_ , pages 4922–4931. PMLR, 2019.
  * Raghu et al. (2017) Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In _International Conference on Machine Learning_ , pages 2847–2854. PMLR, 2017.
  * Safavian and Landgrebe (1991) S Rasoul Safavian and David Landgrebe.  A survey of decision tree classifier methodology.  _IEEE transactions on systems, man, and cybernetics_ , 21(3):660–674, 1991.
  * Schmidhuber (2015) Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  _Neural Networks_ , 61:85–117, 2015.
  * Schmidt-Hieber (2019) Johannes Schmidt-Hieber.  Deep relu network approximation of functions on a manifold.  _arXiv preprint arXiv:1908.00695_ , 2019.
  * Schmidt-Hieber (2020) Johannes Schmidt-Hieber.  Rejoinder: “Nonparametric regression using deep neural networks with ReLU activation function” [ MR4134775; MR4134776; MR4134777; 4134778; MR4134774].  _Ann. Statist._ , 48(4):1916–1921, 2020.
  * Scholkopf and Smola (2018) B. Scholkopf and A.J. Smola.  _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_.  MIT Press, 2018.
  * Shen et al. (2003) Xiaotong Shen, George C Tseng, Xuegong Zhang, and Wing Hung Wong.  On $\psi$-learning.  _Journal of the American Statistical Association_ , 98(463):724–734, 2003.
  * Shen et al. (2019) Zuowei Shen, Haizhao Yang, and Shijun Zhang.  Nonlinear approximation via compositions.  _Neural Networks_ , 119:74–84, 2019.
  * Shen et al. (2020) Zuowei Shen, Haizhao Yang, and Shijun Zhang.  Deep network approximation characterized by number of neurons.  _Commun. Comput. Phys._ , 28(5):1768–1811, 2020\.
  * Stone (1982) Charles J. Stone.  Optimal global rates of convergence for nonparametric regression.  _Ann. Statist._ , 10(4):1040–1053, 1982.
  * Talagrand (1994) Michel Talagrand.  Sharper bounds for gaussian and empirical processes.  _The Annals of Probability_ , pages 28–76, 1994.
  * Telgarsky et al. (2015) Matus Telgarsky, Miroslav Dudik, and Robert Schapire.  Convex risk minimization and conditional probability estimation.  In _Conference on Learning Theory_ , pages 1629–1682. PMLR, 2015\.
  * Tsybakov (2004) Alexandre B. Tsybakov.  Optimal aggregation of classifiers in statistical learning.  _Ann. Statist._ , 32(1):135–166, 2004.
  * Vapnik and Chervonenkis (1974) Vladimir Vapnik and Alexey Chervonenkis.  Theory of pattern recognition, 1974.
  * Wang and Zou (2016) Boxiang Wang and Hui Zou.  Sparse distance weighted discrimination.  _Journal of Computational and Graphical Statistics_ , 25(3):826–838, 2016.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_ , 2016.
  * Yang (1999) Yuhong Yang.  Minimax nonparametric classification. i. rates of convergence.  _IEEE Transactions on Information Theory_ , 45(7):2271–2284, 1999.
  * Yarotsky (2017) Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  _Neural Networks_ , 94:103–114, 2017.
  * Yarotsky (2018) Dmitry Yarotsky.  Optimal approximation of continuous functions by very deep relu networks.  In _Conference on Learning Theory_ , pages 639–649. PMLR, 2018.
  * Zhang (2004) Tong Zhang.  Statistical behavior and consistency of classification methods based on convex risk minimization.  _Ann. Statist._ , 32(1):56–85, 2004.
  * Zhivotovskiy and Hanneke (2018) Nikita Zhivotovskiy and Steve Hanneke.  Localization of vc classes: Beyond local rademacher complexities.  _Theoretical Computer Science_ , 742:27–49, 2018.
  * Zhou (2020a) Ding-Xuan Zhou.  Theory of deep convolutional neural networks: Downsampling.  _Neural Networks_ , 124:319–327, 2020a.
  * Zhou (2020b) Ding-Xuan Zhou.  Universality of deep convolutional neural networks.  _Appl. Comput. Harmon. Anal._ , 48(2):787–794, 2020b.
  * Zhou and Troyanskaya (2015) Jian Zhou and Olga G Troyanskaya.  Predicting effects of noncoding variants with deep learning–based sequence model.  _Nature methods_ , 12(10):931–934, 2015.
  * Zhou and Feng (2018) Pan Zhou and Jiashi Feng.  Understanding generalization and optimization performance of deep cnns.  In _International Conference on Machine Learning_ , pages 5960–5969. PMLR, 2018.