# Full Duplex Massive MIMO Architectures: Recent Advances, Applications, and
Future Directions

George C. Alexandropoulos, Md Atiqul Islam,
and Besma Smida G. C. Alexandropoulos is with the Department of Informatics
and Telecommunications, National and Kapodistrian University of Athens,
Panepistimiopolis Ilissia, 15784 Athens, Greece (e-mail:
alexandg@di.uoa.gr).M. A. Islam and B. Smida are with the Department of
Electrical and Computer Engineering, University of Illinois at Chicago, USA
(e-mails: {mislam23,smida}@uic.edu).

###### Abstract

The increasingly demanding objectives for next generation wireless
communications have spurred recent research activities on multi-antenna
transceiver hardware architectures and relevant intelligent communication
schemes. Among them belong the Full Duplex (FD) Multiple-Input Multiple-Output
(MIMO) architectures, which offer the potential for simultaneous uplink and
downlink operations in the entire frequency band. However, as the number of
antenna elements increases, the interference signal leaking from the
transmitter of the FD radio to its receiver becomes more severe. In this
article, we present a unified FD massive MIMO architecture comprising analog
and digital transmit and receive BeamForming (BF), as well as analog and
digital SI cancellation, which can be jointly optimized for various
performance objectives and complexity requirements. Performance evaluation
results for applications of the proposed architecture to fully digital and
hybrid analog and digital BF operations using recent algorithmic designs, as
well as simultaneous communication of data and control signals are presented.
It is shown that the proposed architecture, for both small and large numbers
of antennas, enables improved spectral efficiency FD communications with fewer
analog cancellation elements compared to various benchmark schemes. The
article is concluded with a list of open challenges and research directions
for future FD massive MIMO communication systems and their promising
applications.

##  I Introduction

Future wireless networks are converging towards a unified communication,
sensing, and computing platform that enables various vertical applications
[1]. The ubiquity, ultra-high speed, and low latency needed by this
omnipresent platform will require, among other factors, more efficient
frequency spectrum usage as well as optimized co-design of the control and
data planes. In-band Full Duplex (FD) communication [2] is lately receiving
increasing attention as a candidate technology for 6-th Generation (6G)
wireless systems [1], due to its inherent capability to enable simultaneous
UpLink (UL) and DownLink (DL) wireless operations within the entire frequency
band. This unique feature has the potential to improve spectral efficiency and
system operation flexibility compared to the current Half Duplex (HD) systems
but also reduce the communication latency enabling Simultaneous Communication
of Data and Control (SCDC) signals.

A large body of research contributions has recently appeared in the literature
on the design of FD hardware architectures and their performance analysis [2].
The core bottleneck for FD operation is Self-Interference (SI), which refers
to the transmitted signal from the Transmitter (TX) of the FD radio that leaks
to the FD radio’s Receiver (RX). At this RX side, the power of the SI signal
can be many times stronger than the power of the received signal of interest,
which is usually transmitted from another radio. Consequently, SI can severely
degrade the reception of the desired signal, and thus its mitigation is
required in order to maximize the potential gain of FD operation. Propagation
domain isolation, analog domain suppression, digital SI cancellation, and
their combinations have been adopted in practice to suppress the strong SI
signal below the RX noise floor.

Current wireless systems, and visions for 6G, adopt the Multiple-Input
Multiple-Output (MIMO) and massive MIMO technologies [1], which rely on
multiple TX and RX antennas and beamforming techniques to offer highly
reliable and high throughput communication links. Naturally, if SI can be
suppressed below the RX noise floor, combining FD with MIMO communication will
further boost the spectral efficiency of FD operation compared to the case of
FD single-input single-output systems. However, as the number of TX and/or RX
antennas increases, mitigating SI becomes more challenging, since more
antennas result in more interference components. Therefore, efficient FD MIMO
approaches are required to maximize the profit from FD operation with the
lowest possible hardware and computational complexities.

Motivated by the potential of FD MIMO radios for enabling flexible utilization
of the available spectrum, and consequently, diverse simultaneous UL and DL
operations, we focus in this article on the latest advances in the FD MIMO
transceiver hardware designs and their applications. In Section II, we present
a unified FD massive MIMO transceiver architecture comprising Analog and
Digital (A/D) TX/RX BeamForming (BF) as well as A/D SI cancellation, which are
jointly optimized for various performance objectives and complexity
requirements. Representative applications of the proposed architecture to
massive MIMO with fully digital and hybrid A/D BF, as well as to SCDC schemes
are discussed in Section III. Section IV includes a list of open challenges
and research directions for future FD MIMO radios, and the article is
concluded in Section V.

Figure 1: Unified FD MIMO architecture with $N$ Transmit (TX) and $M$ Receive
(RX) antenna elements. The architecture incorporates analog and digital TX/RX
BeamForming (BF), analog cancellation comprising $K$ lines intended for
suppressing the Self-Interference (SI) signal, and digital SI cancellation.
The outputs of the $N_{\rm T}$ TX Radio Frequency (RF) chains are fed to the
input of the analog SI canceller, while its outputs are connected to the
$M_{\rm R}$ RX RF chains. The $N$ TX antenna elements are connected to the
$N_{\rm T}$ TX RF chains via phase shifters, the same holds for the
interconnection between the $M$ RX antenna elements and the $M_{\rm R}$ RX RF
chains. The designs of the analog and digital TX/RX beamformers, as well as of
the analog and digital SI cancellers, are jointly optimized.

##  II Unified FD MIMO Architecture

We consider the unified FD MIMO transceiver architecture of Fig. 1 for the
case of $N$ TX and $M$ RX antennas, where any of the $N$ and $M$ can be
arbitrarily large. All TX antenna elements are attached to $N_{\rm T}\leq N$
TX Radio Frequency (RF) chains; similarly holds for the RX antenna elements
whose outputs are connected to $M_{\rm R}\leq M$ RX RF chains. A TX RF chain
consists of a digital-to-analog converter, a mixer which upconverts the signal
from baseband to RF, and a power amplifier. An RX RF chain consists of a low
noise amplifier, a mixer which downconverts the signal from RF to baseband,
and an analog-to-digital converter. We next discuss the A/D TX/RX BF and SI
cancellation components of the presented architecture, as well as their joint
design for diverse operations.

Table I: Summary of Existing FD MIMO Approaches with Hybrid A/D BF in Comparison with the proposed unified scheme. | [3] | [4] | [5] | [6] | Proposed
---|---|---|---|---|---
Analog BF Architecture | Fully Connected | Fully Connected | Fully Connected | Fully Connected | Fully or Partially Connected
Resolution of Phase Shifters | Infinite | Infinite | Finite | Finite | Finite
Total Number of Phase Shifters | $NN_{\rm T}+MM_{\rm R}$ | $NN_{\rm T}+MM_{\rm R}$ | $NN_{\rm T}+MM_{\rm R}$ | $NN_{\rm T}+MM_{\rm R}$ |  $N+M$ (Partially Connected)
Consideration of TX Impairments | No | No | No | No | Yes
Number of Analog Taps | $NM$ | $NM$ | $0$ | $0$ | $\leq N_{\rm T}M_{\rm R}$

###  II-A Analog and Digital TX Beamforming

At the TX side of Fig. 1, the information symbols (i.e., the modulated
information bits) are firstly processed in baseband by the digital BF module,
whose $N_{\rm T}$ outputs are individually upsampled and pulse shaped before
being fed to the $N_{\rm T}$ inputs of the TX RF chains. The TX RF chains
upconvert the beamformed information signal to the carrier frequency and
attach it to the analog TX BF component. Analog BF is usually realized via a
network of phase shifters, where each phase shifter has constant amplitude but
an adjustable phase component. In the fully connected analog BF architecture,
each TX RF chain is connected with all TX antennas via a distinct phase
shifter. On the other hand, when the partially connected (or sub-array) analog
BF architecture is considered, distinct subsets of antennas are connected to
different RF chains, again via phase shifters. In the sequel, we focus on the
latter more cost-efficient sub-array architecture, where each sub-array is
connected to $N/N_{\rm T}$ (assumed integer) distinct antennas. According to
this architecture, each sub-array is capable of realizing a predefined
codebook of analog beams.

###  II-B Analog and Digital RX Beamforming

The RX side of the unified FD MIMO transceiver architecture is composed of
analog RX BF connecting the $M$ RX antennas with the inputs of the $M_{\rm R}$
RX RF chains, and digital RX BF that processes the outputs of the RX RF chains
in baseband before symbol decoding. Similar to the TX side, each of the RX RF
chains is connected to a sub-array of $M/M_{\rm R}$ (again, assumed integer-
valued) antenna elements via constant-magnitude phase shifters. The complex-
valued analog RX BF vectors belong in a predefined RX beam codebook, similar
to the analog TX BF ones. The signals at the outputs of the RX RF chains are
being downconverted and fed to the digital RX beamformer to derive the
estimated information symbols.

###  II-C Analog SI Cancellation

The conventional FD MIMO architectures [7] deploy fully connected analog SI
cancellation, which interconnects all inputs to the TX antennas to all outputs
of the RX antennas in order to suppress all possible SI signals. This
cancellation approach requires $K=NM$ SI attenuation lines. In the recent
architecture of [8], the analog SI canceller connects all outputs of the TX RF
chains with all inputs to the RX RF chains, which results in $K=N_{\rm
T}M_{\rm R}$ attenuation lines. Clearly, when $N>N_{\rm T}$ or $M>M_{\rm R}$,
the architecture of [8] has the lowest complexity analog SI cancellation.
However, an algorithmic design for the parameters of the attenuation lines as
well as for TX/RX BF to justify improved performance with the fully connected
architectures of [7] was not presented in [8].

As shown in the proposed unified FD MIMO architecture in Fig. 1, $K\leq N_{\rm
T}M_{\rm R}$ SI attenuation lines appear in the analog canceller, which also
includes two selection networks. The role of these networks is to decide which
SI signals will be mitigated from which inputs to the RX RF chains. In [9],
the selection network which feeds the inputs to the SI attenuation lines was
implemented with $K$ MUltipleXers (MUXs) of $N_{\rm T}$-to-$1$, while $K$
DEMUltipleXers (DEMUXs) of $1$-to-$M_{\rm R}$ were considered for implementing
the selection network at the outputs of the attenuation lines. Each
attenuation line was realized via a fixed delay, a variable phase shifter, and
a variable attenuator, termed compactly as an analog tap. The adders appearing
before the RX RF chains in Fig. 1 can be implemented via power combiners or
directional couplers.

###  II-D Digital SI Cancellation

In practical FD MIMO radios, the TX RF chains induce impairments to the
transmitted signals due to the nonlinearities of the power amplifiers and the
In-Phase Quadrature (IQ) mixer imbalances. These impairments result in SI
signals that incommode the simultaneous reception of the signal of interest.
To deal with this problem, digital SI cancellation can be applied in baseband
to suppress the residual SI signal after analog SI cancellation. In baseband,
a reciprocal version of the residual SI is modeled and added to the inputs of
the digital RX BF for SI suppression. In the performance results that follow,
we model the effect of the power amplifier nonlinearities using the memoryless
nonlinear model, which gives rise to the power amplifier 3-order-Intercept-
Point (IIP3). The impact of the IQ imbalance is modeled as an image component
expressed by the TX Image-Rejection-Ratio (IRR) [10].

###  II-E Joint A/D SI Cancellation and TX/RX Beamforming Design

The objective of SI cancellation in FD radios is to suppress the SI signal
below the RX noise floor. In practical wireless communication systems, each RX
RF chain is characterized by a maximum input signal power level, above which
saturation happens. This means that when the SI signal is larger than the
chain’s maximum allowable power level, this RX RF chain gets saturated. The
role of the analog SI canceller is to suppress the SI signal power level below
the latter threshold in order to avoid saturation. Our proposed unified FD
MIMO architecture includes a module for jointly designing the parameters of
the A/D SI canceller and A/D TX/RX BF according to any desired operation
objective (e.g., SI suppression together with DL plus UL rate maximization).

###  II-F State-of-the-Art in FD MIMO with Hybrid A/D Beamforming

Table I summarizes the state-of-the-art in FD MIMO approaches with hybrid A/D
BF [3, 4, 5, 6] in comparison with our unified scheme. As shown, the existing
works adopt fully-connected analog TX/RX BF, which results in large numbers of
phase shifters, as compared to the partially-connected architecture that will
be considered for the proposed scheme. In addition, our scheme will be
investigated for practical TX impairments, in contrary to ideal transmissions
studied in [3, 4, 5, 6]. The architectures in [3, 4] include analog SI
cancellers with $K=NM$ taps, i.e., the canceller’s hardware scales with the
product of the TX and RX antennas. This complexity is prohibitive for FD
massive MIMO systems. In [5] and [6], passive SI suppression is used instead
of analog cancellers. However, as it will be shown in our simulation results,
only digital TX/RX BF falls short in efficiently handling nonlinear SI
resulting from TX impairments. The proposed scheme deploys a novel analog
canceller with $K\leq N_{\rm T}M_{\rm R}$ taps (i.e., its complexity does not
scale with the number of TX/RX antennas, hence, suitable for massive MIMO),
which is jointly designed with the A/D TX/RF beamformers.

##  III Applications of the Proposed FD Architecture

In this section, four representative applications of the proposed FD MIMO
transceiver architecture and design optimization framework are presented. In
our simulations, we have considered a small-cell Base Station (BS) of the
typical value ${-}110$dBm for the noise floor, which deploys the proposed FD
MIMO radio, as well as both HD and FD User Equipment (UE) with noise floor at
${-}90$dBm. To emulate practical nonidealities at the BS, we have assumed that
its TX RF chains induce nonlinearities due to imperfect power amplification
[10], as well as image components due to IQ imbalance. The power amplifier
IIP3 and IRR values were set to $20$dBm and $30$dB, respectively. Unless
otherwise indicated, the UL and DL were simulated as Rayleigh fading channels,
while the SI channel was modeled as Rician faded with $\kappa$-factor equal to
$30$dB.

Figure 2: Average sum rate versus the DL transmit power in dBm for a $4\times
4$ FD MIMO BS with $K$ analog taps, communicating with two $4$-antenna HD UEs:
one served in the DL with up to $4$ parallel streams and the other
transmitting a single-stream in the UL with power equal to the DL
transmission.

###  III-A FD MIMO with Digital Beamforming

The achievable ergodic sum-rate performance, defined as the summation of the
UL and DL rates, of the proposed unified FD MIMO architecture with A/D SI
cancellation and only digital beamforming is demonstrated in Fig. 2 with
respect to the DL transmit power in dBm, which has been set equal to the UL
power. Estimation of all involved channels with the Minimum Mean Squared Error
(MMSE) approach using $40$ pilot symbols was performed. We have considered a
$4\times 4$ BS node (i.e., $N=N_{\rm T}=M=M_{\rm R}=4$) with $K=12$ taps
(i.e., $K=0.75NM$) for the special case where every TX/RX RF chain is
connected to a single antenna. This node is serving an HD receiving UE with
$4$ antennas in the DL direction, while an HD $4$-antenna UE transmits a
single-stream signal through the UL channel. For the BS, the joint analog
cancellation and digital BF design of [9] has been adopted for the ideal TX
case, whereas the design of [10], that also includes digital SI cancellation,
was simulated for the case of TX impairments. In Fig. 2, the sum rate with the
FD MIMO scheme of [7] that adopts null space SI suppression with full-tap time
domain analog SI cancellation (i.e., $K=NM=16$), as well as the sum rate for
the case where all involved nodes are HD ones is also illustrated for
comparison purposes. As depicted, the proposed design with $K=12<NM$
outperforms the scheme of [7] for moderate-to-high transmit powers and ideal
transmissions. When practical TX impairments are considered, the scheme of [7]
suffers from substantial rate degradation due to its inability to mitigate the
nonlinear SI components with only digital RX BF. However, the scheme of [10]
is capable of handling the nonlinearities via its digital SI canceller,
outperforming both the benchmark FD scheme and HD MIMO communication.

###  III-B FD Massive MIMO with Analog and Digital Beamforming

Figure 3: Average sum rate versus the DL transmit power in dBm for a $64\times
32$ FD MIMO BS with Hybrid A/D BF (HBF) and $K$ analog taps, communicating
with a $4$-antenna and a $2$-antenna HD UEs, the former served in the DL with
up to $4$ parallel streams and the latter is transmitting in UL up to $2$ data
streams with power equal to the DL transmission.

The proposed BS for the case of massive MIMO with $N=64$ and $M=32$ and the
partially connected hybrid A/D BF architecture is investigated in terms of the
achievable sum rate in Fig. 3, when deployed for realizing concurrent DL and
UL communications with a $4$-antenna and a $2$-antenna, respectively, HD UEs.
The former was served with up to $4$ data streams, and the latter transmitted
up to $2$ streams with power equal to the DL transmission. We have considered
$N_{\rm T}=4$ TX and $M_{\rm R}=2$ RX RF chains at the BS, where each of them
is connected with a distinct $16$-element Uniform Linear Array (ULA). Each
antenna is connected to its sole RF chain via a phase shifter having unit
amplitude and $3$-bit phase resolution. This setup enables analog TX/RX BF,
which was realized via a common codebook based on the discrete Fourier
transform for all ULAs. In the figure, we have considered a millimeter wave
channel comprising $7$ equal-power paths and adopted the joint A/D SI
cancellation and BF design of [11] for the BS with $K=4$ taps (i.e.,
$K=0.5N_{\rm T}M_{\rm R}\ll NM$). We have also sketched the performance for
the case where both nodes are HD and for the scheme [5] that adopts only BF to
suppress the SI signal and enable data communication. Evidently, the design
[11] for the proposed scheme outperforms both that of [5] and HD hybrid A/D
BF. This behavior witnesses that the considered $4$-tap analog cancellation
results in increasing rate improvement as the DL and UL transmit powers
increase. Interestingly, for non-ideal transmissions with more than $32.5$dBm
power, [5] fails to provide any gain over the HD scheme.

###  III-C Simultaneous Multi-User MIMO and Channel Estimation

Figure 4: Average DL rate versus the DL transmit power in dBm for an $8\times
8$ FD MIMO BS with $K$ analog SI cancellation taps, which is linked with $4$
single-antenna FD UEs via reciprocal UL and DL channels using the SCDC
paradigm. The UL transmit power was set to $10$dBm and TX impairments were
considered.

Suppose an FD MIMO BS wishes to serve multiple FD multi-antenna UEs in the DL
via TX beamforming while they concurrently transmit training symbols in the UL
[12]. Those symbols are intended for UL channel estimation at the BS (thus, DL
channel estimation due to reciprocity for ideal antenna calibration), given
sufficient SI suppression below the BS noise floor. This estimation is then
used by the BS to realize DL data communication via rate-maximizing digital
BF. Compared with conventional MIMO communication in time division duplexing
systems where UL channel estimation and DL data communication take place in a
time orthogonal manner, the considered SCDC scheme results in improved
achievable rate, as will be demonstrated.

In Fig. 4, we consider an FD BS for the case of fully digital $8\times 8$ MIMO
(i.e., $N=N_{\rm T}=M=M_{\rm R}=8$) with $K=64$ taps (full-tap analog
cancellation) and K=32 (i.e., $50\%$ reduction in the number of taps), when
linked with $4$ single-antenna FD UEs via SCDC. The achievable DL rate is
demonstrated as a function of the BS transmit power in dBm, considering a
$10$dBm UE transmit power for the training symbols in the UL. We have assumed
communications on a slot-by-slot basis for the proposed SCDC scheme, where one
DL and one UL packet are simultaneously communicated per time slot.
Specifically, the whole UL packet includes the equal-numbered orthogonal
pilots of all UEs, which are used for the estimation of the respective $4$ DL
channels. The latter estimates for each slot are used in its next one for
digital Zero-Forcing (ZF) BF of the $4$ parallel data streams in the DL, one
per UE. To capture possible Channel State Information (CSI) delay, we have
adopted the Gauss-Markov delay model with $50$Hz Doppler spread for $1$ms
packet duration. For comparison purposes, we have evaluated the DL rate of the
proposed scheme with ideal CSI estimation and full-tap analog SI cancellation,
as well as the performance for the case where all involved nodes are HD ones.
In the latter case, a sole packet is communicated per time slot; a portion of
it is dedicated for UL channel estimation and the rest for DL data
communication. For the results in Fig. 4, we have considered $400$ symbols per
UL and DL packet. In the considered HD MIMO case, only $90\%$ of each DL
packet (i.e., $360$ symbols) is used for data transmission, since its first
$10\%$ remains idle to enable reception of the training symbols of the $4$ UEs
in the UL. For the proposed SCDC scheme, all $400$ symbols of each UL packet
are used for channel estimation (enabling better accuracy than the HD case),
which is then used for the ZF beamforming of data in the next slot’s DL
packet. We have also simulated the multi-user FD MIMO scheme of [13] that
requires full-tap analog cancellation (i.e., $K=64$). According to this
scheme, channel estimation is acquired in the UL via a time-division multiple-
access manner similar to HD MIMO. Following a sequential mode of operation,
the reception of UL pilots from a UE takes place concurrently with beamformed
DL data communication for the UEs whose channels have been previously
estimated. The performance curves in Fig. 4 witness that all considered SCDC
variations exhibit comparable performance for DL transmit powers up to
$20$dBm. However, for higher power values, the performance of all approaches
with realistic CSI estimation degrades compared to the ideal CSI case as a
consequence of estimation errors. It is also shown that for moderate-to-high
transmit powers, the proposed SCDC scheme with the unified architecture for
$K=32$ outperforms [13] for $K=64$ as well as conventional HD MIMO
communications.

###  III-D Simultaneous Beam Selection and Direction Estimation

Figure 5: Average DL rate versus the DL transmit power in dBm for a $64\times
2$ FD MIMO BS with hybrid A/D BF and $K$ analog taps, communicating with a
single-antenna FD UE. In the UL, training symbols are transmitted with power
$10$dBm for DOA estimation, which is used in the DL for selecting the best
analog TX beams.

In Fig. 5, we numerically evaluate the performance of a novel SCDC scheme
enabled by the proposed FD architecture. In particular, we consider a
$64\times 2$ FD massive MIMO BS with $N_{\rm T}=2$ TX and $M_{\rm R}=2$ RX RF
chains, where each TX RF chain is connected to a distinct $32$-element ULA via
unit-amplitude and $3$-bit resolution phase shifters, while each RX antenna is
attached to a dedicated RX RF chain. The BS intends to serve a single-antenna
FD UE node in the DL direction via A/D TX BF. The analog BF is realized with
discrete Fourier transform beams at each ULA. In the UL, the UE transmits
training symbols with power $10$dBm to enable Direction-Of-Arrival (DOA)
estimation at the BS side. Similar to the previous SCDC scheme, we assume
simultaneous communication of one DL and one UL packet per time slot, and that
the DOA estimation from the UL packet in each time slot is used by the BS in
the successive time slot for the beam selections needed for the analog TX BF.
Figure 5 illustrates the achievable DL rate of this SCDC scheme with $K=2$
analog taps along with full-tap analog cancellation with $K=4$, under a Rician
channel with $\kappa=20$dB. For comparison purposes, we have evaluated the DL
rate of our scheme with ideal CSI estimation and $K=4$, as well as the case
where both nodes are HD. We have considered $400$ symbols per UL and DL
packet, while similar to Sec. III-C, only $90\%$ of each DL packet was used
for data transmission in the HD scheme, with the remaining $10\%$ being idle
to enable UL training reception for DOA estimation. In contrast, all $400$ UL
symbols in the proposed SCDC scheme were used for DOA estimation. As depicted
in the figure, our scheme with $K=2$ provides comparable performance to HD for
low-to-moderate transmit powers. Additionally, this reduced-complexity case is
close to the DL rate achieved with $K=4$. For example, for the transmit power
$40$dBm, the performance gap is only $1$bps/Hz, while there exists a $50\%$
reduction in the number of analog taps. It is also shown that, as the transmit
power increases, the DL rate resulting from DOA estimation saturates, as
compared to the ideal CSI case; this is the consequence of the increasing
estimation error. For moderate-to-high transmit powers, the proposed SCDC
scheme with $K=2$ clearly outperforms the conventional HD approach.

##  IV Open Challenges and Future Directions

The performance of the FD MIMO transceiver design presented in Fig. 1 has been
investigated for ideal selection networks in the analog SI canceller (i.e.,
ideal MUXs/DEMUXs of arbitrary $K$) and for narrowband communications.
Additionally, the investigated algorithms for diverse wireless operations are
suboptimal, requiring an offline investigation for the adequate value $K$ of
the number of the SI attenuation lines. Therefore, further studies are needed
considering wideband FD operation with relevant modulation schemes (e.g.,
Orthogonal frequency-division multiplexing), selection networks with practical
losses, feasible $K$ numbers for the MUXs/DEMUXs sizes, and realistic
correlated channels for planar antenna arrays. Furthermore, optimized
algorithms with low computational complexity for multi-user and/or multi-cell
simultaneous UL and DL operations need to be derived. To this end, the FD
operation, which inevitably contributes to the overall network interference,
needs to be efficiently incorporated and handled into the next generation Non-
Orthogonal Multiple Access (NOMA) techniques. The design of A/D TX/RX beam
codebooks for SI mitigation is another important research topic towards the
practical deployment of FD MIMO transceivers. We next discuss in more detail
some of the most promising future directions for FD massive MIMO
communications.

High-Frequency Communications: Given the limited spectral resources at
frequencies below 6GHz, the Fifth Generation ($5$G) New Radio has adopted
millimeter Wave (mmWave) frequencies to accommodate high data rate
communications, and $6$G is expected to support wireless links at THz (i.e.,
$0.1-10$ THz) [1]. To compensate for the high pathloss at those high frequency
bands, highly directive A/D BF is necessary. Hence, combining FD MIMO radios
with mmWave and THz technologies is a promising approach to reach higher
spectral efficiencies. Interestingly, the SCDC features of the presented FD
massive MIMO framework can be used for low latency analog beam tracking,
paving the way for beyond $5$G standalone mmWave and THz communications. For
example, the beam refinement for multiple UEs can take place in the UL
simultaneously with their DL data communication from the FD massive MIMO BS.
However, the nonlinearities of the power amplifiers become the bottleneck of
SI cancellation in mmWave and THz frequencies. The RF imperfections will not
be sufficiently suppressed in the analog domain with reduced hardware
complexity and sophisticated, yet of reasonable computation complexity,
digital SI cancellation will be needed, possibly with the aid of digital RX
BF.

Integrated Communications and Sensing: The presented SCDC schemes in this
article constitute only a portion of the potential of the FD MIMO technology
for simultaneous transmit-and-receive applications. In fact, the FD operation
can enable joint communication and radar [14], offering reusability of the
available resources and integration of advanced sensing capabilities in future
wireless systems. To this end, the presented FD massive MIMO architecture can
be exploited for realizing highly flexible multiple beams for both
communications and radar, trading off the complexity of SI cancellation with
the sensing resolution.

Channel Estimation Schemes: Most FD MIMO techniques rely on the idealized
simplifying assumption of the availability of perfect CSI; however, this
assumption is unrealistic. Indeed, the CSI acquired at the FD nodes is
imperfect due to estimation errors induced by i) nonlinear hardware
components; ii) phase noise from the device’s oscillators; and iii) channel
aging caused by the mobility of the UEs. Those CSI errors will be exacerbated
at the FD node when massive numbers of TX and RX antennas are used. In
addition, as shown in Section III, it is very hard to completely cancel the SI
signal in the practical case of imperfect CSI. Hence, CSI estimation is a
particularly critical issue in FD MIMO systems. The same holds for channel
aging, which requires sophisticated channel tracking algorithms. To maximize
the ergodic mutual information, which is a nonconvex function of the power
allocation, efficient techniques for optimizing the power/pilot-overhead
allocation vectors need to be developed.

Machine-Learning-Based Configurations: Artificial Neural Networks (ANNs) are
lately gaining substantial attention in wireless communications as an
efficient means to deal with hardware nonlinearities and to tame wireless
channel dynamics. It is appealing to consider efficient hardware
implementations of ANNs to handle the nonlinearities of the multiple power
amplifiers in the FD massive MIMO architecture, especially when considered for
high-frequency communications. This will enable more efficient analog SI
cancelers, thus, increasing the flexibility of A/D TX/RX BF. In addition,
supervised and reinforcement learning techniques can be deployed for traffic
predictions in order to enable dynamic scheduling of UL and DL users in
multiple interfering FD massive MIMO connections. With such approaches, the
large overhead of multiple pilot-assisted massive MIMO channel estimates will
be avoided.

Massive Metasurface Antennas: Incorporating reconfigurable metasurfaces in
wireless networks has been recently advocated as a revolutionary means to
transform any naturally passive wireless propagation environment into a
dynamically programmable one. This can be accomplished by deploying cost-
effective and easy to coat metasurfaces to the environment’s objects, thus,
offering increased environmental intelligence for the scope of diverse
wireless networking objectives. Metasurfaces are artificial planar structures
of multiple reconfigurable radiating metamaterial elements that can be
programmed to reflect an incoming electromagnetic field in a tunable way
(passive metasurfaces) or can be used as TX or RX antenna arrays (active
metasurfaces) [15]. Interesting directions of research are the investigation
of FD massive MIMO operation in networks empowered by passive metasurfaces,
and the design of FD MIMO architectures with massive numbers of metasurface-
based antennas. In the former direction, efficient NOMA techniques to manage
FD-based reflections need to be devised, whereas, in the latter, hybrid A/D
TX/RX BF schemes will be required.

##  V Conclusion

In this article, a unified FD massive MIMO transceiver architecture was
presented that includes most of the latest FD MIMO designs as special cases.
The presented architecture includes A/D TX/RX BF as well as A/D SI
cancellation of adjustable hardware complexity, which can be jointly optimized
for various performance objectives and complexity requirements. It was shown
in the performance evaluation results, for the FD rate maximization and two
example SCDC schemes, that the complexity of the analog SI canceller is
independent of the number of transceiver antennas, and scales only up to a
portion of the product of the numbers of TX and RX RF chains. We discussed
open challenges with the proposed FD MIMO transceivers and presented some
future research directions for FD functionality in next generation extreme
massive MIMO systems.

## References

  * [1] “The next hyper-Connected experience for all,” White Paper, Samsung 6G Vision, Jun. 2020.
  * [2] H. Alves, T. Riihonen, and H. A. Suraweera, _Full-Duplex Communications for Future Wireless Networks_. Singapore: Springer, 2020.
  * [3] Z. Xiao, P. Xia, and X.-G. Xia, “Full-duplex millimeter-wave communication,” _IEEE Wireless Commun._ , vol. 24, no. 6, pp. 136–143, Dec. 2017.
  * [4] K. Satyanarayana, M. El-Hajjar, P.-H. Kuo, A. Mourad, and L. Hanzo, “Hybrid beamforming design for full-duplex millimeter wave communication,” _IEEE Trans. Veh. Technol._ , vol. 68, no. 2, pp. 1394–1404, Dec. 2018.
  * [5] I. P. Roberts and S. Vishwanath, “Beamforming cancellation design for millimeter-wave full-duplex,” in _Proc. IEEE GLOBECOM_ , Waikoloa, USA, 9-13 Dec. 2019, pp. 1–6.
  * [6] J. M. B. Da Silva, A. Sabharwal, G. Fodor, and C. Fischione, “1-bit phase shifters for large-antenna full-duplex mmwave communications,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 10, pp. 6916–6931, Jul. 2020.
  * [7] E. Everett, C. Shepard, L. Zhong, and A. Sabharwal, “SoftNull: Many-antenna full-duplex wireless via digital beamforming,” _IEEE Trans. Wireless Commun._ , vol. 12, no. 15, pp. 8077–8092, Dec. 2016.
  * [8] I. P. Roberts, H. B. Jain, and S. Vishwanath, “Equipping millimeter-wave full-duplex with analog self-interference cancellation,” in _Proc. IEEE ICC_ , Dublin, Ireland, Jun. 2020, pp. 1–6.
  * [9] G. C. Alexandropoulos and M. Duarte, “Joint design of multi-tap analog cancellation and digital beamforming for reduced complexity full duplex MIMO systems,” in _Proc. IEEE ICC_ , Paris, France, May 2017.
  * [10] M. A. Islam, G. C. Alexandropoulos, and B. Smida, “A unified beamforming and A/D self-interference cancellation design for full duplex MIMO radios,” in _Proc. IEEE PIMRC_ , Istanbul, Turkey, Sep. 2019.
  * [11] G. C. Alexandropoulos, M. A. Islam, and B. Smida, “Full duplex hybrid A/D beamforming with reduced complexity multi-tap analog cancellation,” in _Proc. IEEE SPAWC_ , Atlanta, USA, May 2020, pp. 1–6.
  * [12] M. A. Islam, G. C. Alexandropoulos, and B. Smida, “Simultaneous downlink data transmission and uplink channel estimation with reduced complexity full duplex MIMO radios,” in _Proc. IEEE ICC_ , Dublin, Ireland, Jun. 2020, pp. 1–6.
  * [13] J. Mirza, G. Zheng, K.-K. Wong, S. Lambotharan, and L. Hanzo, “On the performance of multiuser MIMO systems relying on full-duplex CSI acquisition,” _IEEE Trans. Wireless Commun._ , vol. 66, no. 10, pp. 4563–4577, May 2018.
  * [14] C. B. Barneto, S. D. Liyanaarachchi, M. Heino, T. Riihonen, and M. Valkama, “Full duplex radio/radar technology: The enabler for advanced joint communication and sensing,” _IEEE Wireless Commun._ , vol. 28, no. 1, pp. 82–88, Feb. 2021.
  * [15] N. Shlezinger, G. C. Alexandropoulos, M. F. Imani, Y. C. Eldar, and D. R. Smith, “Dynamic metasurface antennas for 6G extreme massive MIMO communications,” _IEEE Wireless Commun._ , vol. 28, no. 2, pp. 106–113, Apr. 2021.


# Deep neural network approximation of analytic functions

###### Abstract

We provide an entropy bound for the spaces of neural networks with piecewise
linear activation functions, such as the ReLU and the absolute value
functions. This bound generalizes the known entropy bound for the space of
linear functions on $\mathbb{R}^{d}$ and it depends on the value at the point
$(1,1,...,1)$ of the networks obtained by taking the absolute values of all
parameters of original networks. Keeping this value together with the depth,
width and the parameters of the networks to have logarithmic dependence on
$1/\varepsilon$, we $\varepsilon$-approximate functions that are analytic on
certain regions of $\mathbb{C}^{d}$. As a statistical application we derive an
oracle inequality for the expected error of the considered penalized deep
neural network estimators.

Keywords: entropy estimation, neural networks, approximation theory, analytic
functions, prediction guarantees

Aleksandr Beknazaryan<EMAIL_ADDRESS>
University of Twente

##  1 Introduction

It has recently been shown that deep neural networks with appropriate $l_{p}$
parameter regularizations can effectively estimate unknown regression
functions. Parameter regularization is needed to bound the complexity of
approximant networks and, thus, to achieve favorable convergence rates. The
most popular types of such constraints are the $l_{0}$ (sparsity) and the
$l_{1}$ regularizations (see, respectively, [9] and [10] and references
therein). Although for theoretical justifications the $l_{0}$ regularization
is more convenient, as it allows to apply combinatorial arguments to bound the
complexity (entropy) of the space of approximant networks, for practical
implementations the $l_{1}$ regularizations are more feasible. The natural
approach is therefore to first impose an $l_{1}$ constraint on the network
parameters and then use the sparsity induced from it to bound the entropy of
considered networks. This can be done (i) by taking the small parameters to be
0; (ii) by applying Maurey’s sparsification lemma given in [8]. In [10] the
first technique is applied to derive an entropy bound of order
$O((2/L)^{2L-1}/\varepsilon^{2})$ for spaces of deep neural networks with
Lipschitz continuous activation functions and with $l_{1}$ parameter norm
bounded by $1.$ This bound then leads to the guarantee for the prediction
error of corresponding regularized regression estimator that decreases at rate
$n^{-1/2}$ (up to a logarithmic factor) with the number of samples $n$. Using
Maurey’s sparsification lemma, for the spaces of linear functions, which can
be considered as neural networks with no hidden layers, entropy bounds of
order $O(1/\varepsilon^{2})$ depending on the $l_{\infty}$-regularization of
the input vectors and on the $l_{1}$-regularization of the acting vectors have
been derived in [2] and [15]. In this work we first generalize those bounds
for the spaces of deep neural networks with piecewise linear activation
functions, including the ReLU activation function $\sigma(x)=0\lor x$ and the
absolute value activation function $a(x)=|x|$ (although considered activation
functions may be even discontinuous). Our bound is given in terms of the
$l_{1}$ norm of the vector obtained by taking absolute values of all
parameters and multiplying the matrices that constitute the network. For a
given network $f$ we denote this quantity by $\|f\|_{\times}$. Clearly, if $f$
is a network with non-negative nodes and with ReLU, absolute value or identity
acitvation function, then $\|f\|_{\times}=f(\textbf{1}),$ where
$\textbf{1}=(1,1,...,1)$. Also, if $\ell$ is a linear function, then
$\|\ell\|_{\times}=\|\textbf{w}\|_{1}$, where w is the acting vector. Note
that network characteristics similar to $\|\cdot\|_{\times}$ are also
considered in the works [1] and [6], where they are called, respectively, the
variation and the path norm of a network and in terms of those concepts the
complexities and statistical features of classes of networks are described.
The objective of the present paper is the construction of concrete networks
that approximate functions from considered classes and for which the quantity
$\|\cdot\|_{\times}$ is small. It turns out that networks with absolute value
activation function may suit this goal better than the networks with ReLU
activation function. More precisely, we show that analytic functions can be
$\varepsilon$-approximated by networks $f_{\varepsilon}$ with absolute value
activation function $a(x)$ and with $\|f_{\varepsilon}\|_{\times}$ depending
logarithmically on $1/\varepsilon$. The depth, width as well as the parameters
of those networks also have logarithmic dependence on $1/\varepsilon$. Such
approximation holds (i) on any subset $(0,1-\delta]^{d}\subset(0,1)^{d}$ for
analytic functions on $(0,1)^{d}$ with absolutely convergent power series;
(ii) on the whole hypercube $[0,1]^{d}$ for functions that can be analytically
continued to certian subsets of $\mathbb{C}^{d}$. Note that for case (i) an
exponential convergence rate of deep ReLU networks has also been derived in
[13]. In this work we show that with the absolute value activation function,
the quantity $\|\cdot\|_{\times}$ for the approximating deep networks is also
of logarithmic dependence on $1/\varepsilon$. Finally, we provide an oracle
inequality for regression estimation with $\|\cdot\|_{\times}-$regularized
deep neural networks. In case the unknown regression function satisfies the
above assumption given in (ii), we get a guarantee for the prediction error of
order $n^{-1/2}$ up to a logarithmic factor.

Notation: For a matrix $W\in\mathbb{R}^{d_{1}\times d_{2}}$ we denote by
$|W|\in\mathbb{R}^{d_{1}\times d_{2}}$ the matrix obtained by taking the
absolute values of the entries of $W$: $|W|_{ij}=|W_{ij}|$. For brevity of
presentation we will say that the matrix $|W|$ is the absolute value of the
matrix $W$ (note that in the literature there are also other definitions of
the notion of an absolute value of a matrix). For
$\textbf{x}=(x_{1},...,x_{d})\in\mathbb{R}^{d}$ and
$\textbf{k}=(k_{1},...,k_{d})\in\mathbb{N}_{0}^{d},$ the degree of the
monomial $\textbf{x}^{\textbf{k}}=x_{1}^{k_{1}}\cdot...\cdot x_{d}^{k_{d}}$ is
defined to be $\|\textbf{k}\|_{1}=\sum_{i=1}^{d}k_{i}.$ Also, as the vectors
will be considered as matrices with one of the dimensions equal to $1$, we
will in some cases use spaces rather than commas to separate their
coordinates.

##  2 Main results

Entropy bound. Let $\mathcal{F}$ be a set of functions from some subset
$\mathcal{R}\subset\mathbb{R}^{d}$ to $\mathbb{R}$ and let
$\textbf{z}_{1}^{n}:=\\{\textbf{z}_{1},...,\textbf{z}_{n}\\}$ be a fixed set
of $n$ vectors in $\mathcal{R}$. For a given $\varepsilon>0$ let
$\mathcal{N}_{2}(\varepsilon,\mathcal{F},\textbf{z}_{1}^{n})$ be the minimal
number $N\in\mathbb{N},$ such that there exist $N$ functions $g_{1},...,g_{N}$
from $\mathcal{R}$ to $\mathbb{R}$ with the property that for every
$g\in\mathcal{F}$ there is some $k\in[N]$ such that

$\|g-g_{k}\|_{n}:=\bigg{\\{}\frac{1}{n}\sum_{i=1}^{n}(g(\textbf{z}_{i})-g_{k}(\textbf{z}_{i}))^{2}\bigg{\\}}^{1/2}<\varepsilon.$

The number
$\log_{2}\mathcal{N}_{2}(\varepsilon,\mathcal{F},\textbf{z}_{1}^{n})$ is
called the entropy of the space $\mathcal{F}$. Our goal in this part is to
estimate the entropy of the space of neural networks

$\mathcal{F}_{\alpha,r}(L,\textbf{p})=\\{f:[-r,r]^{d}\to\mathbb{R}\;|\;\;f(\textbf{x})=W_{L}\circ\alpha\circ
W_{L-1}\circ\alpha\circ...\circ\alpha\circ W_{0}\textbf{x}\\},$

where $W_{i}\in\mathbb{R}^{p_{i}\times p_{i+1}}$, $i=0,...,L,$ $p_{0}=d,$
$p_{L+1}=1$ and $\textbf{p}=(p_{0},p_{1},...,p_{L+1})$ is the width vector.
The number of hidden layers $L$ determines the depth of networks from
$\mathcal{F}_{\alpha,r}(L,\textbf{p})$ and in each layer the activation
function $\alpha:\mathbb{R}\to\mathbb{R}$ acts element-wise on the input
vector. We will consider activation functions of the form

$\alpha(x)=\begin{cases}x,&x\in I_{1},\\\ -x,&x\in I_{2},\\\ 0,&x\in
I_{3},\end{cases}$ (1)

where $I_{1},I_{2}$ and $I_{3}$ are (possibly empty) disjoint subsets of
$\mathbb{R}$ and $I_{1}\cup I_{2}\cup I_{3}=\mathbb{R}$. Note that the case
$I_{1}=\mathbb{R},I_{2}=I_{3}=\varnothing$ corresponds to the identity
activation function $i(x)=x$, the case $I_{1}=[0,\infty)$, $I_{2}=\varnothing$
and $I_{3}=(-\infty,0)$ corresponds to the ReLU activation function
$\sigma(x)=0\lor x$ and the case $I_{1}=[0,\infty)$, $I_{2}=(-\infty,0)$ and
$I_{3}=\varnothing$ corresponds to the absolute value activation function
$a(x)=|x|$. In case $\alpha(x)=i(x)=x,$ we get that
$\mathcal{F}_{i,r}(L,\textbf{p})$ is a space of linear functions

$\mathcal{L}_{r}=\\{\ell:[-r,r]^{d}\to\mathbb{R}\;|\;\;\ell(\textbf{x})=\textbf{w}\cdot\textbf{x};\;\textbf{w}\in\mathbb{R}^{d}\\}.$

For $b>0$ denote

$\mathcal{L}_{b,r}=\\{\ell:[-r,r]^{d}\to\mathbb{R}\;|\;\;\ell(\textbf{x})=\textbf{w}\cdot\textbf{x};\;\textbf{w}\in\mathbb{R}^{d},\|\textbf{w}\|_{1}\leq
b\\}.$ (2)

It is shown in [2] (see also [15]) that

$\log_{2}\mathcal{N}_{2}(\varepsilon,\mathcal{L}_{b,r},\textbf{z}_{1}^{n})\leq\bigg{\lceil}\frac{b^{2}r^{2}}{\varepsilon^{2}}\bigg{\rceil}\log_{2}(2d+1).$
(3)

Note that as the above bound has logarithmic dependence on $d$, it is
especially useful for the cases when the input dimension is large. Using this,
in the Lemma 2.1 below we obtain an entropy bound for the space
$\mathcal{F}_{\alpha,r}(L,\textbf{p}),$ where $\alpha$ is any activation
function of the form (1). The $l_{1}$ constraint imposed in (2) is replaced by
the $l_{1}$ constraint imposed on the product of absolute values of matrices
that constitute the networks from $\mathcal{F}_{\alpha,r}(L,\textbf{p}).$ More
precisely, for $f\in\mathcal{F}_{\alpha,r}(L,\textbf{p})$ given by

$f(\textbf{x})=W_{L}\circ\alpha\circ
W_{L-1}\circ\alpha\circ...\circ\alpha\circ W_{0}\textbf{x},$ (4)

denote

$\|f\|_{\times}=\bigg{\|}\prod_{i=0}^{L}|W_{i}|\bigg{\|}_{1},$ (5)

where $\|\cdot\|_{1}$ denotes the $l_{1}$ norm of the $p_{0}(=d)$ dimensional
vector $\prod_{i=0}^{L}|W_{i}|$. Let

$\mathcal{F}_{\alpha,r}(L,\textbf{p},B)=\\{f\in\mathcal{F}_{\alpha,r}(L,\textbf{p}),\|f\|_{\times}\leq
B\\}.$

We have the following

######  Lemma 2.1.

Assume that the activation function $\alpha$ is of the form (1). Then

$\log_{2}\mathcal{N}_{2}(\varepsilon,\mathcal{F}_{\alpha,r}(L,\textbf{p},B),z_{1}^{n})\leq\sum_{i=1}^{L}p_{i}\log_{2}(3n)+\bigg{\lceil}\frac{B^{2}r^{2}}{\varepsilon^{2}}\bigg{\rceil}\log_{2}(2Pd+1),$
(6)

where $P=\prod_{i=1}^{L}p_{i}.$

Note that in case $L=0,$ we get the same bound as in (3) (it is assumed that
$P=\prod_{i=1}^{0}p_{i}=1$).

Let us also compare the bound in (6) with the entropy bound for
$l_{1}$-regularized networks obtained in [10]. It is shown in [10] that the
entropy of neural networks with the $l_{1}$ norm of all parameters bounded by
$1$ and with activation function being Lipschitz continuous with Lipschitz
constant $1$ (such as $\sigma(x)$ and $a(x)$) is bounded by

$C\frac{L(2/L)^{2L}}{\varepsilon^{2}},$

where the constant $C$ only depends on the magnitude $r$ of input vectors. Let
us show that for those networks the factor $B^{2}$ in (2.1) is at most
$(1/(L+1))^{2(L+1)}$. As $W_{L}\in\mathbb{R}^{1\times p_{L}}$ and
$W_{L-1}\in\mathbb{R}^{p_{L}\times p_{L-1}}$, then

$\displaystyle\bigg{\|}|W_{L}|\times|W_{L-1}|\bigg{\|}_{1}=|W_{L}|\cdot\bigg{(}\sum\limits_{j=1}^{p_{L-1}}|W^{j}_{L-1}|\bigg{)}\leq\|W_{L}\|_{2}\bigg{\|}\sum\limits_{j=1}^{p_{L-1}}|W^{j}_{L-1}|\bigg{\|}_{2}\leq\|W_{L}\|_{1}\|W_{L-1}\|_{1},$

where $\times$ denotes matrix product, $\cdot$ denotes dot product of vectors
and superscripts indicate the corresponding columns of a matrix. Similarly, as
$\sum\limits_{i=0}^{L}\|W_{i}\|_{1}\leq 1,$ then

$\|f\|_{\times}=\bigg{\|}\prod_{i=0}^{L}|W_{i}|\bigg{\|}_{1}\leq\prod_{i=0}^{L}\|W_{i}\|_{1}\leq\Bigg{(}\sum\limits_{i=0}^{L}\|W_{i}\|_{1}/(L+1)\Bigg{)}^{L+1}\leq\frac{1}{(L+1)^{L+1}},$

and the desired implication follows.

Function approximation with $\mathcal{F}(L,\textbf{p},B)$. In this part we
show that analytic functions can be $\varepsilon$-approximated by networks
from $\mathcal{F}_{a,1}(L,\textbf{p},B)$ with parameters
$L,\|\textbf{p}\|_{\infty}$ and $B$ having logarithmic dependence on
$1/\varepsilon$. As all networks will have the same activation function
$a(x)=|x|$, in the following the subscripts $(a,1)$ will be omitted.

Neural network approximation algorithm of smooth functions presented in [14]
is based on the approximation of a function $h(x)=x^{2}$ which then leads to
an approximation of the product $xy=(h(x+y)-h(x)-h(y))/2$. The latter then
allows to construct local approximations of Taylor polynomials of a given
function. In order to approximate the function $h(x)=x^{2}$ it is noted that
for the triangle wave

$g_{s}(x)=\smash{\underbrace{g\circ g\circ...\circ g}_{s\
\text{times}}}\vphantom{1}(x),$

where $g:[0,1]\to[0,1]$ is defined by

$g(x)=\begin{cases}2x,&x<1/2,\\\ 2(1-x),&x\geq 1/2,\\\ \end{cases}$

we have that the function

$f_{m}(x)=x-\sum_{s=1}^{m}\frac{g_{s}(x)}{2^{2s}}$ (7)

approximates $x^{2}$ with the error $2^{-2m-2}$. The approximation of $x^{2}$
by the networks with ReLU activation function $\sigma$ then follows from the
representation

$g(x)=2\sigma(x)-4\sigma(x-1/2)+2\sigma(x-1).$

Thus, in this case we will get matrices containing entries 2 and 4 which will
make the quantity $\|\cdot\|_{\times}$ defined by (5) big. We would therefore
like to represent the function $g(x)$ by linear combination of activation
functions with fewer terms and smaller coefficients. This is possible if
instead of $\sigma(x)$ we use the absolute value activation function $a(x)$.
Indeed, in this case we have that $g(x)$ can be represented on $[0,1]$ as

$g(x)=1-2a(x-1/2).$ (8)

In the following lemma we use the above representation to construct a network
with activation function $a(x)$, that for the given $\gamma,m\in\mathbb{N}$
simultaneously approximates all $d$-dimensional monomials of degree less than
$\gamma$ up to an error $\gamma^{2}4^{-m}$. The depth of this network has
order $m\log_{2}\gamma$ and its width is of order $m\gamma^{d+1}$. Moreover,
the entries of the product of the absolute values of matrices of the network
have order at most $\gamma^{5}$ (note the independence of $m$). Also, as in
the constructions of neural networks we omit the shift vectors, we will add a
coordinate $1$ to the input vector x and will consider the networks as
functions of a vector $(1\;\textbf{x})$.

For $\gamma>0$ let $C_{d,\gamma}$ denote the number of $d$-dimensional
monomials $\textbf{x}^{\textbf{k}}$ with degree $\|\textbf{k}\|_{1}<\gamma$.
Note that $C_{d,\gamma}<(\gamma+1)^{d}$.

######  Lemma 2.2.

There exists a network _Mon_ ${}_{m,\gamma}^{d}\in\mathcal{F}(L,\emph{{p}})$
with $L\leq\lceil\log_{2}\gamma\rceil(2m+5)+2$ and
$\|\emph{{p}}\|_{\infty}\leq 6\gamma(m+2)C_{d,\gamma}$ such that

$\bigg{\|}\emph{Mon}_{m,\gamma}^{d}(1\;\emph{{x}})-(\emph{{x}}^{\emph{{k}}})_{\|\emph{{k}}\|_{1}<\gamma}\bigg{\|}_{\infty}\leq\gamma^{2}4^{-m},\quad\emph{{x}}\in[0,1]^{d}.$

Moreover, the entries of the $C_{d,\gamma}\times(d+1)$ \- dimensional matrix
obtained by multiplying the absolute values of matrices presented in
$\emph{Mon}_{m,\gamma}^{d}$ are all bounded by $144(\gamma+1)^{5}$.

Taking in the above lemma
$\gamma,m=\lceil\log_{2}\frac{1}{\varepsilon}\rceil,$ we get a network from
$\mathcal{F}(L,\textbf{p})$ with $L$ and $\|\textbf{p}\|_{\infty}$ having
logarithmic dependence on $1/\varepsilon$, that simultaneously approximates
the monomials of degree at most $\gamma$ with error $\varepsilon$ (up to a
logarithmic factor). Moreover, the entries of the product of absolute values
of matrices of this network will also have logarithmic dependence on
$1/\varepsilon$. Below we use this property to construct neural network
approximation of analytic and analytically continuable functions with
approximation error $\varepsilon$ and with network parameters having
logarithmic order.

######  Theorem 2.1.

Let
$f(\textbf{{{x}}})=\sum_{\textbf{k}\in\mathbb{N}^{d}_{0}}a_{\textbf{k}}\textbf{x}^{\textbf{k}}$
be an analytic function on $(0,1)^{d}$ with
$\sum_{\textbf{k}\in\mathbb{N}^{d}_{0}}|a_{\textbf{k}}|\leq F$. Then, for any
$\varepsilon,\delta\in(0,1)$ there is a network
$F_{\varepsilon}\in\mathcal{F}(L,\emph{{p}},B)$ with
$L=(\log_{2}\frac{1}{\delta})O(\log_{2}\frac{1}{\varepsilon})^{2},$
$\|\emph{{p}}\|_{\infty}=(\frac{1}{\delta})^{d+1}O(\log_{2}\frac{1}{\varepsilon})^{d+2}$
and $B=F(d+1)(\frac{1}{\delta})^{5}O(\log_{2}\frac{1}{\varepsilon})^{5},$ such
that

$|F_{\varepsilon}(1\;\textbf{x})-f(\textbf{x})|\leq\frac{2F\varepsilon}{\delta^{2}},\quad\textit{for
all }\;\textbf{x}\in(0,1-\delta]^{d}.$

Note that an exponential convergence rate of deep ReLU network approximants on
subintervals $(0,1-\delta]^{d}$ is also given in [13]. In our case, however,
not only the depth and the width but also the quantity
$\|F_{\varepsilon}\|_{\times}$ of the constructed network $F_{\varepsilon}$
have logarithmic dependence on $1/\varepsilon$. Note that in the above
theorem, as $\delta$ approaches to $0,$ both $\|{\textbf{p}}\|_{\infty}$ and
$B,$ as well as the approximation error, grow polynomially on $1/\delta.$ In
the next theorem we use the properties of Chebyshev series to derive an
exponential convergence rate on the whole hypercube $[0,1]^{d}$.

Recall that the Chebyshev polynomials are defined as $T_{0}(x)=1,$
$T_{1}(x)=x$ and

$T_{n+1}(x)=2xT_{n}(x)-T_{n-1}(x).$

Chebyshev polynomials play an important role in the approximation theory, and,
in particular, it is known ([11], Theorem 3.1) that if $f$ is Lipschitz
continuous on $[-1,1]$ then it has a unique representation as an absolutely
and uniformly convergent Chebyshev series

$f(x)=\sum_{k=0}^{\infty}a_{k}T_{k}(x).$

Moreover, in case $f$ can be analytically continued to an ellipse
$E_{\rho}\subset\mathbb{C}$ with foci $-1$ and $1$ and with the sum of
semimajor and semiminor axes equal to $\rho>1,$ then the partial sums of the
above Chebyshev series converge to $f$ with geometric rate and the coeffients
$a_{k}$ also decay with geometric rate. This result has been first derived by
Bernstein in [3] and its extension to the multivariate case has been given in
[12]. Note that the condition $z\in E_{\rho}$ implies that $z^{2}\in
N_{1,h^{2}},$ where $h=(\rho-\rho^{-1})/2$ and for $d,a>0,$
$N_{d,a}\subset\mathbb{C}$ denotes an open ellipse with foci $0$ and $d$ and
the leftmost point $-a$. For $F>0,$ $\rho>1$ and $h=(\rho-\rho^{-1})/2$ let
$\mathcal{A}^{d}(\rho,F)$ be the space of functions $f:[0,1]^{d}\to\mathbb{R}$
that can be analytically continued to the region
$\\{\textbf{z}\in\mathbb{C}^{d}:z_{1}^{2}+...+z_{d}^{2}\in N_{d,h^{2}}\\}$ and
are bounded there by $F$. Using the extension of Bernstein’s theorem to the
multivariate case we get

######  Lemma 2.3.

Let $\rho\geq 2^{\sqrt{d}}$. For $f\in\mathcal{A}^{d}(\rho,F)$ there is a
constant $C=C(d,\rho,F)$ and a polynomial

$p(\textbf{{{x}}})=\sum_{\|\textbf{k}\|_{1}\leq\gamma}b_{\textbf{k}}\textbf{x}^{\textbf{k}},\quad\textbf{x}\in[0,1]^{d},$

with

$|b_{\textbf{k}}|\leq C(\gamma+1)^{d}$ (9)

and

$|f(\textbf{x})-p(\textbf{x})|\leq C\rho^{-\gamma/\sqrt{d}},\quad\textit{for
all \;}\textbf{x}\in[0,1]^{d}.$

Combining Lemma 2.2 and Lemma 2.3 we get the following

######  Theorem 2.2.

Let $\varepsilon\in(0,1)$ and let $\rho\geq 2^{\sqrt{d}}$. For
$f\in\mathcal{A}^{d}(\rho,F)$ there is a network
$F_{\varepsilon}\in\mathcal{F}(L,\emph{{p}},B)$ with
$L=O(\log_{2}\frac{1}{\varepsilon})^{2},$
$\|\emph{{p}}\|_{\infty}=O(\log_{2}\frac{1}{\varepsilon})^{d+2}$ and
$B=O(\log_{2}\frac{1}{\varepsilon})^{2d+5}$ and a constant $C=C(d,\rho,F)$
such that

$|F_{\varepsilon}(1\;\textbf{x})-f(\textbf{x})|\leq
C\varepsilon,\quad\textit{for all \;}\textbf{x}\in[0,1]^{d}.$

We conclude this part by estimating the $l_{1}$ parameter regularization of
networks constructed in Theorem 2.2. First, the total number of parameters in
those networks is bounded by
$(L+1)\|\textbf{p}\|_{\infty}^{2}=O(\log_{2}\frac{1}{\varepsilon})^{2d+6}.$
From (8) it follows that all parameters of network
$\textrm{Mon}_{m,\gamma}^{d}$ from Lemma 2.2 are in $[-2,2]$. In Theorem 2.2
the network $F_{\varepsilon}$ is obtained by adding to a network
$\textrm{Mon}_{m,\gamma}^{d},$ with
$\gamma=m=O(\log_{2}\frac{1}{\varepsilon}),$ a layer with coefficients of
partial sums of power series of approximated function. Thus, using (9), we get
that the $l_{1}$ norm of the parameters of network $F_{\varepsilon}$
constructed in Theorem 2.2 has order
$O(\log_{2}\frac{1}{\varepsilon})^{4d+6}$.

Application to nonparametric regression. Consider a nonparametric regression
model

$Y=f_{0}(\textbf{X})+\epsilon,$

where $f_{0}:[0,1]^{d}\to\mathbb{R}$ is the unknown regression function to be
recovered from $n$ observed iid pairs $(\textbf{X}_{i},Y_{i})$, $i=1,...,n$.
The input variable X follows distribution $P_{\textbf{X}}$ on $[0,1]^{d}$ and
the noise variable $\epsilon$ is assumed to be independent of X. It is also
assumed that $\|f_{0}\|_{\infty}\leq F$ and $\epsilon$ is sub-Gaussian with
$\operatorname{\mathbb{E}}(e^{a\epsilon^{2}})<\infty$.

Let $\mathcal{F}_{n}:=\mathcal{F}(L_{n},\textbf{p}_{n},B_{n})$ be a space of
neural networks with architecture depending on $n$ and to be specified later,
and let

$\hat{f}_{n}\in\operatorname*{arg\,min}\limits_{f\in\mathcal{F}_{n}}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}(Y_{i}-f(\textbf{X}_{i}))^{2}+J_{n}(f)\bigg{]}$
(10)

be a penalized empirical risk minimizer over $\mathcal{F}_{n}$ with penalty
function

$J_{n}(f)=\lambda_{n}\|f\|_{\times}.$

The following theorem estimates the expected prediction error

$\operatorname{\mathbb{E}}\bigg{[}\|\hat{f}_{n}-f_{0}\|^{2}_{2,P_{\textbf{X}}}\bigg{]},$

where the expectation is taken over the training data.

######  Theorem 2.3.

Let
$\lambda_{n}\sim\frac{\log_{2}^{3}n(\sum_{i=1}^{L_{n}}\log_{2}p_{i})^{1/2}}{\sqrt{n}}.$
Then for the estimator $\hat{f}_{n}$ defined by (10) we have that

$\operatorname{\mathbb{E}}\bigg{[}\|\hat{f}_{n}-f_{0}\|^{2}_{2,P_{\textbf{X}}}\bigg{]}\leq
2\inf\limits_{f\in\mathcal{F}_{n}}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\|f-f_{0}\|^{2}_{2,P_{\textbf{X}}}+J_{n}(f)\bigg{]}+C\frac{\sum_{i=1}^{L_{n}}p_{i}\log_{2}^{3}n}{n}$
(11)

for some constant $C>0$.

Taking in Theorem 2.2 $\varepsilon=\frac{1}{n},$ for a function
$f_{0}\in\mathcal{A}^{d}(\rho,F)$ we get an existence of a network
$f_{n}\in\mathcal{F}_{n}=\mathcal{F}(L_{n},\textbf{p}_{n},B_{n}),$ with
$L_{n}=O(\log_{2}n)^{2},$ $\|\textbf{p}\|_{\infty}=O(\log_{2}n)^{d+2},$
$B_{n}=O(\log_{2}n)^{2d+5}$ and a constant $C=C(d,\rho,F),$ such that

$|f_{n}(1\;\textbf{x})-f_{0}(\textbf{x})|\leq C\frac{1}{n},\quad\textit{for
all \;}\textbf{x}\in[0,1]^{d}.$

Thus, for the estimator $\hat{f}_{n}$ defined by (10) we get a convergence
rate of order $\frac{(\log_{2}n)^{2d+10}}{\sqrt{n}}$ in (11), which agrees, up
to logarithmic factors, with the rate obtained for the $l_{1}$-regularized
neural network estimators in [10].

##  3 Proofs

Proof of Lemma 2.1 As the activation function $\alpha$ is of the form (1),
then for a given vector $\textbf{z}\in[-r,r]^{d}$ and a given neural network
$f(\textbf{x})=W_{L}\circ\alpha\circ
W_{L-1}\circ\alpha\circ...\circ\alpha\circ W_{0}\textbf{x},$ there exist
matrices $V_{i}\in\mathbb{R}^{p_{i}\times p_{i}},i=1,...,L,$ such that each
$V_{i}$ is a diagonal matrix with all entries on the main diagonal being
either $-1$, $0$ or $1$ and

$f(\textbf{z})=W_{L}\circ V_{L}\circ W_{L-1}\circ V_{L-1}\circ...\circ\
V_{1}\circ W_{0}\textbf{z}.$

The vector z splits $\mathbb{R}^{p_{0}}=\mathbb{R}^{d}$ into 3 subsets: the
dot product of the vectors from the first subset with z is in $I_{1}$, the dot
product of the vectors from the second subset with z is in $I_{2}$ and the dot
product of the vectors from the third subset with z belongs to $I_{3}$. Then
the $i$-th diagonal entry $V_{1}^{ii}$ of the matrix $V_{1}$ is equal to 1 if
the $i$-th row $W_{0}^{i}$ of the matrix $W_{0}$ belongs to the first subset,
$V_{1}^{ii}=-1$ if $W_{0}^{i}$ is from the second subset and $V_{1}^{ii}=0$ if
$W_{0}^{i}$ belongs to the third subset described above, $i=1,...,p_{1}$. We
can thus divide $\mathcal{F}_{\alpha,r}(L,\textbf{p})$ into $3^{p_{1}}$
subclasses, such that the neural networks from each of those subclasses
applied to the vector z share the same matrix $V_{1}$. Continuing this way, we
obtain a splitting of $\mathcal{F}_{\alpha,r}(L,\textbf{p})$ into
$3^{\sum_{i=1}^{L}p_{i}}$ subclasses such that the networks from each of those
subclasses applied to the vector z share the same matrices $V_{1},...,V_{L}$.

Now suppose that we are given $n$ vectors
$\textbf{z}_{1},...,\textbf{z}_{n}\in[-r,r]^{d}$. Those $n$ vectors split the
space $\mathcal{F}_{\alpha,r}(L,\textbf{p})$ into $(3n)^{\sum_{i=1}^{L}p_{i}}$
subclasses such that the networks from each of those subclasses applied to the
vector $\textbf{z}_{k}$ share the same diagonal matrices
$V_{1}^{k},...,V_{L}^{k},$ $k=1,...,n$. More precisely, for each subclass,
there exist fixed diagonal matrices $V_{1}^{k},...,V_{L}^{k},$ with entries on
the main diagonal being either $-1,0$ or $1,$ such that

$f(\textbf{z}_{k})=W_{L}\circ V^{k}_{L}\circ W_{L-1}\circ
V^{k}_{L-1}\circ...\circ\ V^{k}_{1}\circ W_{0}\textbf{z}_{k},\quad k=1,...,n,$
(12)

(note that for $j\neq k$ the matrices $V_{i}^{j}$ and $V_{i}^{k}$ may be
different). Let us now cover one of those subclasses (given by (12)). Let
$E_{i}^{j}\in\mathbb{R}^{p_{i}\times p_{i}}$ be a matrix with
$E_{i}^{j}(j,j)=1$ and all other entries equal to $0$, $i=1,...,L,$
$j=1,...,p_{i}.$ Denote $P=\prod_{i=1}^{L}p_{i}$ and let
$M_{1},M_{2},...,M_{P}$ be the vectors from $\mathbb{R}^{1\times d}$ having
the form

$W_{L}\circ E_{L}^{j_{L}}\circ W_{L-1}\circ E_{L-1}^{j_{L-1}}\circ...\circ\
E_{1}^{j_{1}}\circ W_{0},$

$j_{i}=1,...,p_{i},$ $i=1,...,L$. As each matrix $V^{k}_{i}$ can be written as
a sum of some (at most $p_{i}$) of the matrices $E_{i}^{j}$ and $-E_{i}^{j},$
$i=1,...,L,$ $j=1,...,p_{i},$ then from (12) it follows that for each
$k=1,...,n,$ there exists $\delta^{k}\in\\{-1,0,1\\}^{P}$ such that

$f(\textbf{z}_{k})=\sum_{i=1}^{P}\delta_{i}^{k}M_{i}\textbf{z}_{k},$ (13)

where $\delta_{i}^{k}$ is the $i$-th coordinate of $\delta^{k}$. Let
$M\in\mathbb{R}^{P\times d}$ be a matrix whose $i$-th row is $M_{i}$,
$i=1,...,P,$ and let $W=(M^{1},...,M^{d})\in\mathbb{R}^{1\times Pd}$ be a
vector obtained by concatenating the (transposed) columns $M^{1},...,M^{d}$ of
$M$. Then there is a matrix $\Delta_{k}\in\\{-1,0,1\\}^{Pd\times d}$ that only
depends on $\delta^{k},$ such that for
$\textbf{x}_{k}=\Delta^{k}\textbf{z}_{k}$ we have that (13) can be rewritten
as

$f(\textbf{z}_{k})=W\textbf{x}_{k},\quad k=1,...,n.$

Note that for each $k$ the vector $\textbf{x}_{k}$ only depends on
$\textbf{z}_{k}$ and on the matrices $V_{i}^{k}$ and the latter are fixed for
the networks that we are currently considering. Moreover, for each
$k=1,...,n,$ we have that
$\|\textbf{x}_{k}\|_{\infty}=\|\textbf{z}_{k}\|_{\infty}$. Noting that
$\|W\|_{1}\leq\|f\|_{\times}\leq B,$ we get from (3) that the entropy of the
subclass that we are currently considering is bounded by
$\lceil\frac{B^{2}r^{2}}{\varepsilon^{2}}\rceil\log_{2}(2Pd+1)$. As
$\mathcal{F}_{\alpha,r}(L,\textbf{p},B)$ is a union of
$(3n)^{\sum_{i=1}^{L}p_{i}}$ such subclasses, then

$\log_{2}\mathcal{N}_{2}(\varepsilon,\mathcal{F}_{\alpha,r}(L,\textbf{p},B),z_{1}^{n})\leq\sum_{i=1}^{L}p_{i}\log_{2}(3n)+\bigg{\lceil}\frac{B^{2}r^{2}}{\varepsilon^{2}}\bigg{\rceil}\log_{2}(2Pd+1).$

$\square$

In the following proofs $I_{k}$ denotes identity matrix of size $k\times k$
and all the networks have activation $a(x)=|x|$. The proof of Lemma 2.2 is
based on the following 2 lemmas.

######  Lemma 3.1.

For any positive integer $m$, there exists a network _Mult_
${}_{m}\in\mathcal{F}(2m+3,\emph{{p}})$, with $p_{0}=3,$ $p_{L+1}=1$ and
$\|\emph{{p}}\|_{\infty}=3m+2,$ such that

$|\textrm{Mult}_{m}(1\;x\;y)^{\intercal}-xy|\leq 3\cdot
2^{-2m-3},\quad\textrm{for all}\;x,y\in[0,1],$ (14)

and the product of absolute values of the matrices presented in _Mult_ m is
equal to

$\bigg{(}3\sum_{k=1}^{m}\frac{2^{k}-1}{2^{2k}},2-2^{-m},2-2^{-m}\bigg{)}.$

###### Proof.

For $k\geq 2$ let $R_{k}$ denote a row of length $k$ with first entry equal to
$-1/2$, last entry equal to $1$ and all other entries equal to $0$. Let
$A_{k}$ be a matrix of size $(k+1)\times k$ obtained by adding the $(k+1)$-th
row $R_{k}$ to the indentity matrix $I_{k}$. That is,

$A_{k}=\left(\begin{array}[]{@{} c c @{}}\begin{matrix}\text{$I_{k}$}\quad\\\
-\frac{1}{2}\quad 0\quad 0\quad...\quad 0\quad
1\end{matrix}\end{array}\right).$

Let also $B_{k}$ denote a matrix of size $k\times k$ given by

$B_{k}=\begin{pmatrix}\text{$\;\;I_{k-1}$}&\begin{matrix}\;\;\;\;0\\\
\;\;\;\;0\\\ \;\;\;\;\vdots\\\ \;\;\;\;0\\\ \;\;\;\;0\end{matrix}\\\
\begin{matrix}1&0&0&...&0&0\end{matrix}&-2\end{pmatrix}.$

It then follows from (8) that

$B_{m+2}\circ a\circ A_{m+1}\circ...\circ B_{3}\circ a\circ
A_{2}\binom{1}{x}=\begin{pmatrix}1\\\ x\\\ g_{1}(x)\\\ g_{2}(x)\\\ \cdot\\\
\cdot\\\ \cdot\\\ g_{m}(x)\end{pmatrix}.$

Thus, if $S_{m+2}$ is a row of length $m+2$ defined as

$S_{m+2}=\bigg{(}0\;\;1\;\;-\frac{1}{2^{2\cdot 1}}\;\;-\frac{1}{2^{2\cdot
2}}\;\;...\;\;-\frac{1}{2^{2\cdot m}}\bigg{)},$

then

$S_{m+2}\circ a\circ B_{m+2}\circ a\circ A_{m+1}\circ...\circ a\circ
B_{3}\circ a\circ A_{2}\binom{1}{x}=f_{m}(x),$

where $f_{m}$ is defined by (7). We have that

$|S_{m+2}|\cdot|B_{m+2}|\cdot|A_{m+1}|\cdot...\cdot|B_{3}|\cdot|A_{2}|=\bigg{(}\sum_{k=1}^{m}\frac{2^{k+1}-2}{2^{2k}},2-2^{-m}\bigg{)}.$

As $xy=\frac{1}{2}\big{(}(x+y)^{2}-x^{2}-y^{2}\big{)},$ then in the first
layer of $\textrm{Mult}_{m}$ we will obtain a vector

$\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 1&0&0\\\ 0&0&1\\\ 1&0&0\\\
0&1&1\end{pmatrix}\begin{pmatrix}1\\\ x\\\
y\par\end{pmatrix}:=C\begin{pmatrix}1\\\ x\\\
y\par\end{pmatrix}=\begin{pmatrix}1\\\ x\\\ 1\\\ y\\\ 1\\\ x+y\\\
\end{pmatrix}$

and will then paralelly apply the network from the first part of the proof to
each of the pairs $(1\;x)$, $(1\;y)$ and $(1\;(x+y)).$ More precisely, for a
given matrix $M$ of size $p\times q$ let $\tilde{M}$ be a matrix of size
$3p\times 3q$ defined as

$\tilde{M}=\begin{pmatrix}M&\mbox{\Large 0}&\mbox{\Large 0}\\\ \mbox{\Large
0}&M&\mbox{\Large 0}\\\ \mbox{\Large 0}&\mbox{\Large 0}&M\end{pmatrix}.$

We then have that

$\bigg{(}-\frac{1}{2}\;\;\ -\frac{1}{2}\;\;\ \frac{1}{2}\bigg{)}\circ
a\circ\tilde{S}_{m+2}\circ a\circ\tilde{B}_{m+2}\circ
a\circ\tilde{A}_{m+1}\circ...\circ\tilde{B}_{3}\circ a\circ\tilde{A}_{2}\circ
a\circ C\begin{pmatrix}1\\\ x\\\
y\par\end{pmatrix}=\frac{1}{2}(f_{m}(x+y)-f_{m}(x)-f_{m}(y)),$

which together with $|f_{m}(x)-x^{2}|<2^{-2m-2}$ and the triangle inequality
implies (14). It remains to note that

$\bigg{(}\frac{1}{2}\;\;\ \frac{1}{2}\;\;\
\frac{1}{2}\bigg{)}\cdot|\tilde{S}_{m+2}|\cdot|\tilde{B}_{m+2}|\cdot|\tilde{A}_{m+1}|\cdot...\cdot|\tilde{B}_{3}|\cdot|\tilde{A}_{2}|\cdot|C|=\bigg{(}3\sum_{k=1}^{m}\frac{2^{k}-1}{2^{2k}},2-2^{-m},2-2^{-m}\bigg{)}.$

$\square$

######  Lemma 3.2.

For any positive integer $m$, there exists a network _Mult
${}^{r}_{m}\in\mathcal{F}(L,\textbf{p})$_, with
$L=(2m+5)\lceil\log_{2}r\rceil+1,$ $p_{0}=r+1,$ $p_{L+1}=1$ and
$\|\emph{{p}}\|_{\infty}\leq 6r(m+2)+1,$ such that

$|\emph{Mult}^{r}_{m}(1\;\emph{{x}})^{\intercal}-\prod_{i=1}^{r}x_{i}|\leq
r^{2}4^{-m},\quad\textit{for
all}\;\emph{{x}}=(x_{1}\;...\;x_{r})\in[0,1]^{r},$

and for the $(r+1)$-dimensional vector $J_{m}^{r}$ obtained by multiplication
of absolute values of matrices presented in $\emph{Mult}^{r}_{m}$ we have that
$\|J_{m}^{r}\|_{\infty}\leq 144r^{4}$.

###### Proof.

First, for a given $k\in\mathbb{N}$, we construct a network
$N^{k}_{m}\in\mathcal{F}(L,\textbf{p})$ with $L=2m+4,$ $p_{0}=2k+1$ and
$p_{L+1}=k+1,$ such that

$N^{k}_{m}\cdot(1\quad x_{1}\quad x_{2}\quad...\quad x_{2k-1}\quad
x_{2k})=(1\quad\textrm{Mult}_{m}(1\;x_{1}\;x_{2})\quad...\quad\textrm{Mult}_{m}(1\;x_{2k-1}\;x_{2k})).$

In the first layer we obtain a vector for which the first coordinate is $1$
followed by triples $(1\quad x_{2l-1}\quad x_{2l})$ $l=1,...,k,$ that is, the
vector $(1\quad 1\quad x_{1}\quad x_{2}\quad 1\quad x_{3}\quad
x_{4}\quad...\quad 1\quad x_{2k-1}\quad x_{2k})$. $N_{m}^{k}$ is then obtained
by applying parallelly the network $\textrm{Mult}_{m}$ to each triple $(1\quad
x_{2l-1}\quad x_{2l})$ while keeping the first coordinate equal to 1. The
product of absolute values of the matrices presented in this construction is a
matrix of size $(k+1)\times(2k+1)$ having a form

$\begin{pmatrix}1&0&0&0&0&0&...&0&0&0\\\ a_{m}&b_{m}&b_{m}&0&0&0&...&0&0&0\\\
a_{m}&0&0&b_{m}&b_{m}&0&...&0&0&0\\\
\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
a_{m}&0&0&0&0&0&...&0&b_{m}&b_{m}\end{pmatrix},$

where $a_{m}=3\sum_{k=1}^{m}\frac{2^{k}-1}{2^{2k}}$ and $b_{m}=2-2^{-m}$ are
the coordinates obtained in the previous lemma. Let us now construct the
network $\textrm{Mult}_{m}^{r}$. The first hidden layer of
$\textrm{Mult}_{m}^{r}$ computes

$(1\quad x_{1}\quad x_{2}\quad...\quad x_{r})\mapsto(1\quad x_{1}\quad
x_{2}\quad...\quad x_{r}\quad\smash{\underbrace{1\quad 1\quad...\quad
1}_{2^{q}-r}}\vphantom{1}),$

where $q=\lceil\log_{2}r\rceil$. We then subsequently apply the networks
$N_{m}^{2^{q}},N_{m}^{2^{q-1}},...,N_{m}^{2}$ and in the last layer we mutiply
the outcome by $(0\quad 1)$. From Lemma 3.1 and triangle inequality we have
that $|\textrm{Mult}_{m}(1\;x\;y)^{\intercal}-tz|\leq 3\cdot
2^{-2m-3}+|x-t|+|y-z|,$ for $x,y,t,z\in[0,1]$. Hence, by induction on $q$ we
get that
$|\textrm{Mult}^{r}_{m}(1\;{\textbf{x}})^{\intercal}-\prod_{i=1}^{r}x_{i}|\leq
3^{q}2^{-2m-3}\leq 3r^{2}2^{-2m-3}\leq r^{2}4^{-m}$.

Note that the product of absolute values of matrices in each network
$N^{k}_{m}$ has the above form, that is, in each row it has at most 3 nonzero
values each of which is less than 2. As the matrices given in the first and
the last layer of $\textrm{Mult}_{m}^{r}$ also satisfy this property, then
each entry of the product of absolute values of all matrices of
$\textrm{Mult}_{m}^{r}$ will not exceed $12^{q+2}\leq 144r^{4}$.

$\square$

Proof of Lemma 2.2. We have that if $\|\textbf{k}\|_{1}=0$ then
$\textbf{x}^{\textbf{k}}=1$ and if $\|\textbf{k}\|_{1}=1$ then k has only one
non-zero coordinate, say, $k_{j},$ which is equal to $1$ and
$\textbf{x}^{\textbf{k}}=x_{j}$. Denote $N=C_{d,\gamma}-d-1$ and let
$\textbf{k}^{1},...,\textbf{k}^{N}$ be the multi-indices satisfying
$1<\|\textbf{k}^{i}\|_{1}<\gamma,$ $i=1,...,N$. For
$\textbf{k}=(k_{1},...,k_{d})$ with $\|\textbf{k}\|_{1}>1$, denote by
$\textbf{x}_{\textbf{k}}$ the $(\|\textbf{k}\|_{1}+1)$-dimesional vector of
the form

$\textbf{x}_{\textbf{k}}=(1,\smash{\underbrace{x_{1},...,x_{1}}_{k_{1}}}\vphantom{1},...,\smash{\underbrace{x_{d},...,x_{d}}_{k_{d}}}\vphantom{1}).$

The first layer of $\textrm{Mon}_{m,\gamma}^{d}$ computes the
$\bigg{(}d+1+\sum_{i=1}^{N}(\|\textbf{k}^{i}\|_{1}+1)\bigg{)}$-dimensional
vector

$(1,\textbf{x},\textbf{x}_{\textbf{k}^{1}},...,\textbf{x}_{\textbf{k}^{N}})^{\intercal}$

by multiplying the input vector by matrix $\Gamma$ of size
$\bigg{(}d+1+\sum_{i=1}^{N}(\|\textbf{k}^{i}\|_{1}+1)\bigg{)}\times(r+1)$. In
the following layers we do not change the first $d+1$ coordinates (by
multiplying them by $I_{d+1}$) and to each $\textbf{x}_{\textbf{k}^{i}}$ we
apply in parallel the network $\textrm{Mult}^{\|\textbf{k}^{i}\|_{1}}_{m}$.
Recall that in Lemma 3.2 $J_{m}^{r}$ denotes the $(r+1)$-dimensional vector
obtained from the product of absolute values of matrices of
$\textrm{Mult}^{r}_{m}$. We then have that the product of absolute values of
matrices of $\textrm{Mon}_{m,\gamma}^{d}$ has the form

$M=\left(\begin{array}[]{ccccc}\text{$I_{k}$}\\\
&\text{$J_{m}^{\|\textbf{k}^{1}\|_{1}}$}&&\textbf{\Huge 0}\\\
&&\text{$J_{m}^{\|\textbf{k}^{2}\|_{1}}$}\\\ &\textbf{\Huge 0}&&\ddots\\\
&&&&\text{$J_{m}^{\|\textbf{k}^{N}\|_{1}}$}\end{array}\right)\cdot\Gamma.$

As the matrix $\Gamma$ only contains entries $0$ and $1$ then applying Lemma
3.2 we get that the entries of $M$ are bounded by

$\max\limits_{1\leq i\leq
N}\bigg{|}\bigg{|}J_{m}^{\|\textbf{k}^{i}\|_{1}}\bigg{|}\bigg{|}_{1}\leq
144(\gamma+1)^{5}.$

$\square$

Proof of Theorem 2.1 Let
$\gamma=\lceil\frac{1}{\delta}\ln\frac{1}{\varepsilon}\rceil.$ Then, for
$\textbf{x}\in(0,1-\delta]^{d}$ we have that

$\bigg{|}f(\textbf{{{x}}})-\sum_{\|\textbf{k}\|_{1}\leq\gamma}a_{\textbf{k}}\textbf{x}^{\textbf{k}}\bigg{|}=\bigg{|}\sum_{\|\textbf{k}\|_{1}>\gamma}a_{\textbf{k}}\textbf{x}^{\textbf{k}}\bigg{|}\leq(1-\delta)^{\gamma}F\leq\varepsilon
F.$

In order to approximate the partial sum
$\sum_{\|\textbf{k}\|_{1}\leq\gamma}a_{\textbf{k}}\textbf{x}^{\textbf{k}},$ we
add one last layer with the coefficients of that partial sum to the network
$\textrm{Mon}_{m,\gamma+1}^{d}$ obtained in Lemma 2.2 with
$m=\log_{2}\lceil\frac{1}{\varepsilon}\rceil$. For the obtained network
$F_{\varepsilon}$ we have that

$\|F_{\varepsilon}\|_{\times}\leq 144(d+1)F(\gamma+2)^{5}.$

$\square$

Let us now present the result from [12] that will be used to derive Lemma 2.3.
First, if $f\in\mathcal{A}^{d}(\rho,F)$, then ([5], Theorem 4.1) $f$ has a
unique representation as an absolutely and uniformly convergent multivariate
Chebyshev series

$f(\textbf{x})=\sum_{k_{1}=0}^{\infty}...\sum_{k_{d}=0}^{\infty}a_{k_{1},...,k_{d}}T_{k_{1}}(x_{1})...T_{k_{d}}(x_{d}),\quad\textbf{x}\in[0,1]^{d}.$

Note that for $\mathbf{k}:=(k_{1},...,k_{d})$, the degree of a $d$-dimesional
polynomial $T_{k_{1}}(x_{1})...T_{k_{d}}(x_{d})$ is
$\|\textbf{k}\|_{1}=k_{1}+...+k_{d}$. Then, for any non-negative integers
$n_{1},...,n_{d},$ the partial sum

$p(\textbf{x})=\sum_{k_{1}=0}^{n_{1}}...\sum_{k_{d}=0}^{n_{d}}a_{\textbf{k}}T_{k_{1}}(x_{1})...T_{k_{d}}(x_{d})$
(15)

is a polynomial truncation of the multivariate Chebyshev series of $f$ of
degree $d(p)=n_{1}+...+n_{d}$. It is shown in [12] that

######  Theorem 3.1.

For $f\in\mathcal{A}^{d}(\rho,F)$ there is a constant $C=C(d,\rho,F)$ such
that the multivariate Chebyshev coefficients of $f$ satisfy

$|a_{\textbf{k}}|\leq C\rho^{-\|\textbf{k}\|_{2}}$ (16)

and for the polynomial truncations $p$ of the multivariate Chebyshev series of
$f$ we have that

$\inf_{d(p)\leq\gamma}\|f(\textbf{x})-p(\textbf{x})\|_{[0,1]^{d}}\leq
C\rho^{-\gamma/\sqrt{d}}.$

Proof of Lemma 2.3 Note that from the recursive definition of the Chebyshev
polynomials it follows that for any $k\geq 0$ the coefficients of the
Chebyshev polynomial $T_{k}(x)$ are all bounded by $2^{k}$. Let now $p$ be a
polynomial given by (15) with degree $d(p)\leq\gamma$. As the number of
summands in the right-hand side of (15) is bounded by $(\gamma+1)^{d},$ then,
using (16), we get that $p$ can be rewritten as

$p(\textbf{x})=\sum_{\|\textbf{k}\|_{1}\leq\gamma}b_{\textbf{k}}\textbf{x}^{\textbf{k}},$

with

$|b_{\textbf{k}}|\leq
C(\gamma+1)^{d}2^{\|\textbf{k}\|_{1}}\rho^{-\|\textbf{k}\|_{2}}\leq
C(\gamma+1)^{d}2^{\sqrt{d}\|\textbf{k}\|_{2}}\rho^{-\|\textbf{k}\|_{2}}\leq
C(\gamma+1)^{d},$

where the last inequality follows from the condition $\rho\geq 2^{\sqrt{d}}$.
$\square$

Proof of Theorem 2.2 The proof follows from Lemma 2.2 and Lemma 2.3 by taking
$\gamma=m=\lceil\log_{2}\frac{1}{\varepsilon}\rceil$ and adding to the network
$\textrm{Mon}_{m,\gamma+1}^{d}$ the last layer with the coefficients of the
polynomial $p(\textbf{x})$ from Lemma 2.3. For the obtained network
$F_{\varepsilon}$ we have that

$\|F_{\varepsilon}\|_{\times}\leq
144C(d+1)C_{d,\gamma+1}(\gamma+2)^{d}(\gamma+2)^{5}\leq
144C(d+1)(\gamma+2)^{2d+5},$

where $C$ is the constant from Lemma 2.3.

Proof of Theorem 2.3. Let $\mathcal{F}(L_{n},\textbf{p}_{n})$ be a class of
neural networks with depth $L_{n}$ and width vector $\textbf{p}_{n}$ depending
on $n$ and let

$\hat{f}_{n}\in\operatorname*{arg\,min}\limits_{f\in\mathcal{F}_{n}}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}(Y_{i}-f(\textbf{X}_{i}))^{2}+J_{n}(f)\bigg{]}$

be the penalized empirical risk minimizer over
$\mathcal{F}(L_{n},\textbf{p}_{n})$ with some non-negative penalty function
$J_{n}(f)$. For $t>0$ and $j\in\mathbb{N}_{0}$ define

$\mathcal{F}_{j,n,t}:=\\{f\in\mathcal{F}_{n}:J_{n}(f)\leq 2^{j}t\\}.$

Using Theorem 19.3 from [4] it is shown in [7] that if $t_{n}$ is such that
for any $t\geq t_{n}$ and any $\delta\geq 2^{j}t/8$

$\int_{\delta/(2^{11}K_{n}^{2})}^{\sqrt{\delta}}\log^{1/2}\mathcal{N}_{2}\bigg{(}\frac{u}{4K_{n}},\mathcal{F}_{j,n,t},z_{1}^{n}\bigg{)}du\leq\frac{c\delta\sqrt{n}}{\log_{2}n}$

holds for $K_{n}:=(\sqrt{8/a}\log^{1/2}n)\lor F$ and some constant $c>0$, then

$\operatorname{\mathbb{E}}\bigg{[}\|\hat{f}_{n}-f_{0}\|^{2}_{2,P_{\textbf{X}}}\bigg{]}\leq
2\inf\limits_{f\in\mathcal{F}_{n}}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\|f-f_{0}\|^{2}_{2,P_{\textbf{X}}}+J_{n}(f)\bigg{]}+C\bigg{(}t_{n}+\frac{\log^{2}_{2}n}{n}\bigg{)}.$

As in our case $J_{n}(f)=\lambda_{n}\|f\|_{\times}$, then
$\mathcal{F}_{j,n,t}=\mathcal{F}(L_{n},\textbf{p}_{n},2^{j}t/\lambda_{n})$.
Take $t_{n}=32\sum_{i=1}^{L_{n}}p_{i}\log_{2}^{3}(2n)/n.$ Then, applying Lemma
6, we get that for any $t\geq 32\sum_{i=1}^{L_{n}}p_{i}\log_{2}^{3}(2n)/n$ and
any $\delta\geq 2^{j}t/8\geq 4\sum_{i=1}^{L_{n}}p_{i}\log_{2}^{3}(2n)/n$

$\displaystyle\int_{\delta/(2^{11}K_{n}^{2})}^{\sqrt{\delta}}\log^{1/2}\mathcal{N}_{2}\bigg{(}\frac{u}{4K_{n}},\mathcal{F}_{j,n,t},z_{1}^{n}\bigg{)}du=\int_{\delta/(2^{11}K_{n}^{2})}^{\sqrt{\delta}}\log^{1/2}\mathcal{N}_{2}\bigg{(}\frac{u}{4K_{n}},\mathcal{F}(L_{n},\textbf{p}_{n},2^{j}t/\lambda_{n}),z_{1}^{n}\bigg{)}du$
$\displaystyle\leq\bigg{(}\delta\sum_{i=1}^{L_{n}}p_{i}\log_{2}(2n)\bigg{)}^{1/2}+\int_{\delta/(2^{11}K_{n}^{2})}^{\sqrt{\delta}}\frac{(2^{j}t/\lambda_{n})}{(u/4K_{n})}\log_{2}^{1/2}(2Pd+1)du$
$\displaystyle\leq\frac{\delta\sqrt{n}}{2\log_{2}n}+(8\delta/\lambda_{n})4K_{n}\log_{2}^{1/2}(2Pd+1)\int_{\delta/(2^{11}K_{n}^{2})}^{\sqrt{\delta}}du/u$
$\displaystyle=\frac{\delta\sqrt{n}}{2\log_{2}n}+\frac{32\delta
K_{n}}{\lambda_{n}}\log_{2}^{1/2}(2Pd+1)\ln\frac{2^{11}K_{n}^{2}}{\sqrt{\delta}}.$

Thus, we need to show that

$\frac{32\delta
K_{n}}{\lambda_{n}}\log_{2}^{1/2}(2Pd+1)\ln\frac{2^{11}K_{n}^{2}}{\sqrt{\delta}}\leq\frac{\delta\sqrt{n}}{2\log_{2}n},$

or, equivalently, that

$\frac{32K_{n}}{\lambda_{n}}\log_{2}^{1/2}(2Pd+1)\ln\frac{2^{11}K_{n}^{2}}{\sqrt{\delta}}\leq\frac{\sqrt{n}}{2\log_{2}n}.$

As $\delta\geq 4\sum_{i=1}^{L_{n}}p_{i}\log_{2}^{3}(2n)/n$,
$K_{n}\leq\log_{2}^{1/2}n$ and $P=\prod_{i=1}^{L_{n}}p_{i},$ then the above
inequality follows from the assumption on the $\lambda_{n}$ in the theorem.

## Acknowledgement

The author would like to thank Johannes Schmidt-Hieber for support and
valuable suggestions. The author has been supported by the NWO Vidi grant:
“Statistical foundation for multilayer neural networks”.

## References

  * [1] Barron, A., Klusowski, J., Approximation and estimation for high-dimensional deep learning networks. https://arxiv.org/pdf/1809.03090.pdf , 2018.
  * [2] Bartlett, P.L., The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525-536, 1998.
  * [3] Bernstein, S., Sur la meilleure approximation de |x| par des polynomes de degrés donnés, Acta Math., 37 (1), 1-57, 1914.
  * [4] Györfi, L., Kohler, M., Krzyzak, A., and Walk, H., A distribution-free theory of nonparametric regression. Springer Science & Business Media, 2006.
  * [5] Mason, J. C., Near-best multivariate approximation by Fourier series, Chebyshev series and Chebyshev interpolation, Journal of Approx. Theory, 28(4), 349-358, 1980.
  * [6] Neyshabur, B., Salakhutdinov, R. and Srebro, N., Path-SGD: Path-normalized optimization in deep neural networks. Advances in Neural Information Processing Systems, 2422-2430, 2015.
  * [7] Ohn, I., Kim, Y., Nonconvex sparse regularization for deep neural networks and its optimality, https://arxiv.org/pdf/2003.11769.pdf
  * [8] Pisier, G., Remarques sur un résultat non publié de B. Maurey. Séminaire Analyse fonctionnelle (dit), 1-12, 1980.
  * [9] Schmidt-Hieber, J., Nonparametric regression using deep neural networks with ReLU activation function. Annals of Statistics. 48 (4): 1875–1897, 2020.
  * [10] Taheri, M., Xie, F., and Lederer, J., Statistical Guarantees for Regularized Neural Networks, https://arxiv.org/pdf/2006.00294.pdf.
  * [11] Trefethen, L., N., Approximation Theory and Approximation Practice. SIAM, 2013.
  * [12] Trefethen, L. N., Multivariate polynomial approximation in the hypercube. Proc. Amer. Math. Soc., 145: 4837-4844, 2017.
  * [13] Weinan, E., Wang, Q., Exponential convergence of the deep neural network approximation for analytic functions. Science China Mathematics, 61(10): 1733-1740, 2018.
  * [14] Yarotsky, D. Error bounds for approximations with deep ReLU networks. Neural Networks, 94: 103-114, 2017.
  * [15] Zhang, T., Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2: 527-550, 2002.