# Shaping Next-Generation RAN Topologies to Meet Future Traffic Demands: A
Peak Throughput Study

Paolo Fiore∗, Ilario Filippini∗ and Danilo De Donno§
∗ANTLab - Advanced Network Technologies Laboratory, Politecnico di Milano,
Milan, Italy
§Milan Research Center, Huawei Technologies Italia S.r.l, Milan, Italy
Email: $\\{$paolo.fiore<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Millimeter-Wave (mm-Wave) Radio Access Networks (RANs) are a promising
solution to tackle the overcrowding of the sub-6 GHz spectrum, offering wider
and underutilized bands. However, they are characterized by inherent technical
challenges, such as a limited propagation range and blockage losses caused by
obstacles. Integrated Access and Backhaul (IAB) and Reconfigurable Intelligent
Surfaces (RIS) are two technologies devised to face these challenges. This
work analyzes the optimal network layout of RANs equipped with IAB and RIS in
real urban scenarios using MILP formulations to derive practical design
guidelines. In particular, it shows how optimizing the peak user throughput of
such networks improves the achievable peak throughput, compared to the
traditional mean-throughput maximization approaches, without actually
sacrificing mean throughputs. In addition, it indicates star-like topologies
as the best network layout to achieve the highest peak throughputs.

##  I Introduction

Since its introduction in 3GPP Release 15, the millimeter-Wave (mm-Wave) radio
spectrum has been sought over as a launchpad to reach previously unachievable
transmission rates for end users. With the prospect of bandwidths orders of
magnitude larger than the ones possible in LTE and 5G sub-6 GHz, combined with
a sparsely used spectrum, this frequency range has become very attractive to
operators, vendors, and researchers to answer the pressing issue of spectrum
overcrowding in sub-6 GHz and to give traction to innovation and development
in mobile radio communications [1, 2].
Moreover, the need for a more suitable frequency range for high-speed/low-
latency use cases spawns from numerous forecasts, which consistently predict
an ever-increasing volume of traffic consumed by mobile devices. As reported
in [3], it is expected that, by 2028, the total mobile traffic will increase
three-fold compared to 2023, and all of the data traffic growth will come from
5G New Radio (NR) connections, leaving far behind the usage of previous
generations of mobile Radio Access Networks (RAN), such as GSM (2G), UMTS
(3G), and LTE (4G).

The public expectation on mm-Wave frequencies must face the inherent
challenges of transmitting with limited propagation range due to severe path
loss and blockage loss caused by obstacles at such a high frequency [4].
Suppose an obstacle interrupts a mm-Wave radio link. In that case, the high
reflectivity of materials found in urban areas causes the wave to be deflected
in unwanted directions, reducing the probability of being detected by the
designated receiver [1].
One way to partially solve the propagation shortcomings of mm-Wave frequencies
consists in densifying the Radio Access Network (RAN) by installing a greater
number of base stations in the considered area. This solution comes with
increased installation costs proportional to the desired level of
densification. Integrated Access and Backhaul (IAB), a paradigm standardized
yet in Release 16, can mitigate the limitations of this approach. Backhaul
links between base stations are relocated from the more expensive underground
fiber cabling to the radio spectrum. In this way, all radio links can be
shortened by deploying simpler and cheaper devices than full-fledged base
stations. This process effectively reduces path loss and, at the same time,
can be less taxing on the capital expenditure (CAPEX), saving up to 85$\%$ of
installation costs as there is no need for wired connections and trenching [5,
6, 7, 8]. Nevertheless, massive RAN densification still represents a
challenging topic spawning the search for other alternative solutions.

The recent topic of metasurfaces, particularly Reconfigurable Intelligent
Surfaces (RIS), is gaining momentum in the mm-Wave research and industry
community [9] to boost throughput [10] and resilience to obstacle outages [11,
12]. RIS are planar surfaces made of small radiating elements and have been
proven cheaply mass-producible. RIS can steer the impinging waves to any
direction in their Field of View (FoV) in a quasi-passive way (also addressing
power consumption concerns), and can exploit alternative radio paths that, as
previously mentioned, are mostly unavailable, managing to turn around static
obstacles (e.g., buildings) and limiting the impact of sudden obstacles (e.g.,
vehicles and pedestrians).
The technologies above are promising enough to have been an object of study in
recent publications [13, 14], and a detailed analysis is warranted to evaluate
their impact on the connectivity service from a networking perspective. This
has produced Mixed-Integer Linear Programming (MILP) models, whose solutions
mathematically describe how and where each device should be installed to
deploy a RAN that maximizes a preselected indicator. This allows to
unequivocally measure the network performance and assess the contribution of
these new technologies. Traditionally, the mean user throughput has been
employed as the main parameter for network optimization [15].

However, in [16, 17], it has been recently stated that mobile data traffic of
type video has increased from $53.72$ (2021) [16] to $67.60\%$ (2022) [17] of
the total mobile traffic and is set to keep increasing in the following years.
Therefore, it is time to evaluate different video traffic-friendly metrics as
the focus of optimization, even more so considering the different propagation
conditions of mm-Waves compared to commonly used lower frequencies.
With such an abundance of bandwidth available in the mm-Wave spectrum, ultra-
high throughput transmissions will transfer large data volumes in very-short
time periods, which will be then consumed in the idle period before the next
large-volume burst. A shorter occupation of the RAN resources leads more users
to transmit and receive at the maximum rate available. Thus, peak user
throughput becomes a potentially crucial optimization parameter. In addition,
speed tests are now an extremely common tool to evaluate the quality of a
mobile operator; hence, maximizing the peak user throughput will be very
effective.

This work, to the best of our knowledge, is the first to analyze how an urban
RAN topology that is planned by optimizing the peak user throughput compares
against a more traditional mean throughput approach. Under the optimality
guarantees of MILP models, we show that deploying a peak-throughput optimal
topology yields mean-throughput results similar to traditional methods while
significantly enhancing the maximum achievable throughput, all at an equal
installation cost.
The remainder of this paper is structured as follows: Section 1 focuses on the
detailed description of the components of the considered network scenario, and
Section III describes the MILP network planning models used; Section IV
compares the results obtained by the conventional approach and our proposal;
final remarks in Section V conclude the paper.

##  II System Model

Figure 1: RAN scenario with different types of obstacles.

In this section, we provide a description of a RIS-empowered mm-Wave IAB Radio
Access Network, shown in Figure 1. We describe in detail the main elements of
such networks, their behavior, and how they relate to each other in the system
model.

An IAB network consists of: User Equipments (UE) that must be served; a single
IAB Donor, a full-fledged Base Station (BS) and the only node in the RAN
cabled to the rest of the network, and IAB Nodes, simple BS capable of giving
access to UEs and wireless relaying data from/to other IAB Nodes. Backhaul
links between IAB Nodes and access links serving the UEs operate at the same
frequency range (in-band backhauling). An IAB network assumes a tree topology,
as in 3GPP specifications [18], enabling end-to-end connections between the
Donor and the UEs in a multi-hop fashion. Due to space limitations, only
downlink traffic flow has been considered in this work. Nevertheless, simple
amendments can be added to straightforwardly extend it to consider uplink
traffic.

All links in the RAN use advanced beamforming to improve propagation at the
mm-Wave range: thus, given the narrow nature of the beams, in concert with a
half-duplex operation mode of every device and a continuous Time Division
Multiplexing (TDM) approach111We considered the timesharing resources to be
allocated in a continuous temporal frame instead of a real-scenario discrete
resource block, the impact of mutual interference is typically minimal.
Therefore, we consider interference between different links negligible [19,
20].

The use of RISs in an IAB Network is mainly motivated by their ability to
impact EM propagation in order to improve channel conditions in case of
obstacles. RISs operate as passive beamformers, capable of redirecting an
incident radio signal toward a desired direction. UEs can be served by a
single direct link from an IAB Node or by a Smart Radio Connection (SRC), a
triplet involving a UE and both an IAB Node and a RIS. IAB Nodes are expected
to dynamically command and change SRC configurations [9] to activate the
reflection through the RIS, within their FoV, to improve throughput during
obstacle obstruction, and thus resilience to obstacle blockage.

We adopt the mm-Wave channel model provided in [21], which includes the effect
of RISs, as well as the physical characterization of the involved devices in
the RAN (IAB Donor, IAB Node, RIS, and UE). We consider nomadic obstacles
modeled as in [21], where the blockage probability and blockage loss are
calculated from Monte-Carlo simulations and then fitted to derive a
probability distribution. We also consider the self-blockage zone, modeled as
in 3GPP specifications, which consists of a circular sector centered in the UE
position where the signal attenuation is increased to model the effect of
users’ body [22].

We consider static and nomadic obstacles. Static obstacles (i.e., buildings)
can be avoided during the network planning phase so that IAB Nodes can be
connected only if in Line-of-Sight (LoS) conditions. Vice versa, the heights
of nomadic obstacles are typically smaller than those of IAB Nodes’ and RIS’
installation sites, therefore their presence will affect only access links
from the access nodes (IAB Nodes and RISs) to the UEs. For these reasons, we
assume all backhaul links are always in Line-of-Sight (LoS) conditions, and
their capacity (in Mb/s) is constant. On the other hand, access links can be
interrupted by nomadic obstacles, the user’s body, or both; therefore, their
average capacity is weighted by the probability of being in every possible
blockage state (including both direct link and SRC links). Moreover, when an
SRC is available, only the best link between the direct IAB-UE and the
reflected RIS-UE is selected as the access link.

##  III MILP Models

We now detail two different MILP formulations to provide optimal IAB network
topology: the Mean-Throughput Formulation, a baseline formulation in which the
objective function maximizes the mean user throughput, and the Peak-Throughput
Formulation, an extension of the baseline, in which the peak user throughput
becomes the objective of the maximization. Both formulations share a common
notation, defined as follows.

Adopting the standard approach used in the literature[23], we define a set
$\mathcal{C}$ of Candidate Sites (CS) where a network device (the IAB Donor,
an IAB Node, or a RIS) can be installed over an urban area planned to be
covered by a mm-Wave network. Inside $\mathcal{C}$, two CSs $\hat{c}$ and
$\tilde{c}$ are selected for the installation of two fixed special devices:
$\hat{c}$ is always reserved for the IAB Donor. In contrast, $\tilde{c}$ is a
placeholder CS for a ”fake” RIS. This method lets the solver decide whether to
assign a real SRC (a BS, a UE, and a RIS) or a ”fake” SRC (a BS, a UE, and the
”fake” RIS), thus a direct connection, to each UE, without the need to
introduce additional variables to characterize the two different kinds of
access connections. Test Points (TP), centroids of traffic mimicking the
geographical distribution of UEs in the area, are represented by set
$\mathcal{T}$.

All physical characteristics of an SRC, such as SNR and blockage loss, are
encapsulated in the binary activation parameters $\Delta$ and the achievable
rate parameters $C\in\mathbb{R^{+}}$. Parameter $\Delta_{t,c,r}^{SRC}$ equals
1 when an SRC can be established between TP $t\in\mathcal{T}$, an IAB device
installed in $c\in\mathcal{C}$, and a RIS in CS $r\in\mathcal{C}$. Similarly,
parameter $\Delta_{c,d}^{BH}$ indicates the availability of the inband-
backhaul link between IAB nodes $c,d\in\mathcal{C}$. When an SRC can be
established, $C_{t,c,r}^{SRC}$ is the weighted average of capacities
calculated in various states of blockage, while
$C_{t,c,r}^{RIS}\in\mathbb{R^{+}}$ is the achievable rate of SRC ($t,c,r$)
when only the reflected path through the RIS is available. Finally,
$C_{c,d}^{BH}\in\mathbb{R^{+}}$ defines the capacity of a backhaul link
between two nodes $c,d\in\mathcal{C}$. A minimum amount of demand $D$,
measured in Mb/s, must be served to each TP.

Every RIS has an associated azimuthal angle $F$, representing its Field of
View (FoV), where both an IAB Node and a TP must lie in to be able to use the
RIS222The elevation angle of the FoV of the RIS is managed in pre-processing
given the fixed height of the involved devices in the planning scenario.. To
evaluate if two devices fall within the FoV of the RIS, parameters
$\Phi_{r,t}^{\text{A}},\Phi_{r,c}^{\text{B}}\in\left[0,2\pi\right]$ must be
defined: the former represents the angle between RIS $r\in\mathcal{C}$ and TP
$t\in\mathcal{T}$, and the latter the angle between RIS $r$ and BS $c$, with
$r,c\in\mathcal{C}$.

Finally, the selection of network devices to deploy is constrained by budget
$B$, and $P^{\text{IAB}}$ and $P^{\text{RIS}}$ are the prices for IAB Nodes
and RISs, respectively.

TABLE I: Decision variables for MTF and PTF Variable | Description
---|---
$y_{c}^{\text{DON}}\in\\{0,1\\}$ | Installation of IAB Donor in CS $c\in\mathcal{C}$.
$y_{c}^{\text{IAB}}\in\\{0,1\\}$ | Installation of IAB Node in CS $c\in\mathcal{C}$.
$y_{c}^{\text{RIS}}\in\\{0,1\\}$ | Installation of RIS in CS $c\in\mathcal{C}$.
$x_{t,c,r}\in\\{0,1\\}$ | Activation of SRC ($t,c,r$), $t\in\mathcal{T},c,r\in\mathcal{C}$.
$z_{c,d}\in\\{0,1\\}$ | Activation of backhaul link ($c,d$), $c,d\in\mathcal{C}$.
$f_{c,d}\in\mathbb{R^{+}}$ | Traffic on backhaul link ($c,d$), $c,d\in\mathcal{C}$.
$g_{t,c,r}\in\mathbb{R^{+}}$ | Traffic on SRC ($t,c,r$), $t\in\mathcal{T},c,r\in\mathcal{C}$.
$w_{c}\in\mathbb{R^{+}}$ | Total traffic to the IAB Donor, $c\in\mathcal{C}$.
$t_{c}^{\text{TX}}\in\left[0,1\right]$ | Transmission time ratio of BS installed in CS $c\in\mathcal{C}$.
$t_{c}^{\text{RX}}\in\left[0,1\right]$ | Reception time ratio of BS installed in CS $c\in\mathcal{C}$.
$\phi_{c}\in\left[0,2\pi\right]$ | Azimuthal orientation of RIS installed in CS $c\in\mathcal{C}$.
PTF flow variables
$f_{t,c,d}^{\text{X}}\in\mathbb{R^{+}}$ | Extra traffic on backhaul link ($c,d$), $c,d\in\mathcal{C}$.
$g_{t,c,r}^{\text{X}}\in\mathbb{R^{+}}$ | Extra traffic on SRC ($t,c,r$), $t\in\mathcal{T},c,r\in\mathcal{C}$.
$w_{t,c}^{\text{X}}\in\mathbb{R^{+}}$ | Total extra traffic to the IAB Donor, $c\in\mathcal{C}$.

The network planning model’s solution consists in assigning a value to the
decision variables in Table I, as per the goal stated by the selected
objective function. Said variables determine which devices will be installed
and where ($y_{c}^{\text{DON}},y_{c}^{\text{IAB}},y_{c}^{\text{RIS}}$), how
they will be connected to each other ($x_{t,c,r},z_{c,d}$), how much traffic
will flow through each link ($f_{c,d},g_{t,c,r},w_{c}$), how the time
resources of each BS are employed ($t_{c}^{\text{TX}},t_{c}^{\text{RX}}$), and
how the RIS will be oriented ($\phi_{c}$).

###  III-A Mean-Throughput Formulation (MTF)

The MTF is defined by the following objective and constraints:

$\max\sum_{t\in\mathcal{T},c,r\in\mathcal{C}}g_{t,c,r}\\\ $ (1a) s.t.:
$\displaystyle y_{c}^{\text{IAB}}+y_{c}^{\text{RIS}}\leq 1,$
$\displaystyle\forall c\in\mathcal{C},$ (1b) $\displaystyle
y_{c}^{\text{DON}}\leq y_{c}^{\text{IAB}},$ $\displaystyle\forall
c\in\mathcal{C},$ (1c)
$\displaystyle\sum_{c\in\mathcal{C}}y_{c}^{\text{DON}}\leq 1,$ (1d)
$\displaystyle y_{\tilde{c}}^{\text{RIS}}\geq 1,$ (1e) $\displaystyle
y_{\hat{c}}^{\text{DON}}\geq 1,$ (1f) $\displaystyle
z_{c,d}\leq\Delta^{\text{BH}}_{c,d}\left(y_{c}^{\text{IAB}}+y_{d}^{\text{IAB}}\right)/2,$
$\displaystyle\forall c,d\in\mathcal{C},$ (1g) $\displaystyle
x_{t,c,r}\leq\Delta^{\text{SRC}}_{t,c,r}\left(y_{c}^{\text{IAB}}+y_{r}^{\text{RIS}}\right)/2,$
$\displaystyle\forall t\in\mathcal{T},c,r\in\mathcal{C},$ (1h)
$\displaystyle\sum_{c,r\in C}x_{t,c,r}=1,$ $\displaystyle\forall
t\in\mathcal{T},$ (1i) $\displaystyle\sum_{d\in\mathcal{C}}z_{d,c}\leq
1-y_{c}^{\text{DON}},$ $\displaystyle\forall c\in\mathcal{C},$ (1j)
$\displaystyle\sum_{c\in\mathcal{C}\setminus\\{\hat{c},\tilde{c}\\}}\left(P^{\text{IAB}}y_{c}^{\text{IAB}}+P^{\text{RIS}}y_{c}^{\text{RIS}}\right)\leq
B,$ (1k) $\displaystyle
w_{c}+\sum_{d\in\mathcal{C}}\left(f_{d,c}-f_{c,d}\right)-\sum_{\begin{subarray}{c}t\in\mathcal{T}\\\
r\in\mathcal{C}\end{subarray}}g_{t,c,r}=0,$ $\displaystyle\forall
c\in\mathcal{C},$ (1l) $\displaystyle f_{c,d}\leq C_{c,d}^{\text{BH}}z_{c,d},$
$\displaystyle\forall c,d\in\mathcal{C},$ (1m) $\displaystyle Dx_{t,c,r}\leq
g_{t,c,r}\leq C_{t,c,r}^{\text{SRC}}x_{t,c,r},$ $\displaystyle\forall
t\in\mathcal{T},c,r\in\mathcal{C},$ (1n) $\displaystyle w_{c}\leq
M^{\text{MAX}}y_{c}^{\text{DON}},$ $\displaystyle\forall c\in\mathcal{C},$
(1o) $\displaystyle
t_{c}^{\text{TX}}=\sum_{d\in\mathcal{C}}\frac{f_{c,d}}{C_{c,d}^{\text{BH}}}+\sum_{\begin{subarray}{c}t\in\mathcal{T}\\\
r\in\mathcal{C}\end{subarray}}\frac{g_{t,c,r}}{C_{t,c,r}^{\text{SRC}}},$
$\displaystyle\forall c\in\mathcal{C},$ (1p) $\displaystyle
t_{c}^{\text{RX}}=\sum_{d\in\mathcal{C}}\frac{f_{d,c}}{C_{d,c}^{\text{BH}}},$
$\displaystyle\forall c\in\mathcal{C},$ (1q) $\displaystyle
t_{c}^{\text{TX}}+t_{c}^{\text{RX}}\leq y_{c}^{\text{IAB}},$
$\displaystyle\forall c\in\mathcal{C},$ (1r)
$\displaystyle\sum_{\begin{subarray}{c}t\in\mathcal{T}\\\
c\in\mathcal{C}\end{subarray}}\frac{g_{t,c,r}}{C_{t,c,r}^{\text{RIS}}}\leq
y_{r}^{\text{RIS}},$ $\displaystyle\forall
r\in\mathcal{C}\setminus{\tilde{c}},$ (1s)
$\displaystyle\phi_{r}\geq\Phi^{\text{A}}_{r,t}-F/2-2\pi(1-x_{t,c,r}),$
$\displaystyle\forall t\in\mathcal{T},c,r\in\mathcal{C}\setminus{\tilde{c}},$
(1t) $\displaystyle\phi_{r}\leq\Phi^{\text{A}}_{r,t}+F/2+2\pi(1-x_{t,c,r}),$
$\displaystyle\forall t\in\mathcal{T},c,r\in\mathcal{C}\setminus{\tilde{c}},$
(1u) $\displaystyle\phi_{r}\geq\Phi^{\text{B}}_{r,c}-F/2-2\pi(1-x_{t,c,r}),$
$\displaystyle\forall t\in\mathcal{T},c,r\in\mathcal{C}\setminus{\tilde{c}},$
(1v) $\displaystyle\phi_{r}\leq\Phi^{\text{B}}_{r,c}+F/2+2\pi(1-x_{t,c,r}),$
$\displaystyle\forall t\in\mathcal{T},c,r\in\mathcal{C}\setminus{\tilde{c}}.$
(1w)

The MTF objective function (1a) maximizes the sum-throughput of all UEs333The
value of the objective function is divided by $|\mathcal{T}|$ in post-
processing to obtain the mean user throughput..

Deployment constraints (1b-1f): Constr. (1b) guarantees mutual exclusivity
between IAB Nodes and RISs in a specific CS $c\in\mathcal{C}$, constr. (1c)
enables the possibility of an IAB Node to be promoted to a Donor, constr. (1d)
guarantees at most a single Donor, while constr. (1e) and constr. (1f) install
the ”fake” RIS and the Donor in $\tilde{c},\hat{c}\in\mathcal{C}$,
respectively.

Link-Activation constraints (1g-1j): Constr. (1g) activates a backhaul link
between two CSs $c,d\in\mathcal{C}$ if both of them have an IAB Node installed
and the physical characteristics of the potential link are favorable
($\Delta_{c,d}^{BH}=1$). In the same way, in (1h), an SRC is activated if a BS
is installed in $c$ and a RIS in $r$, and binary parameter
$\Delta_{t,c,r}^{SRC}$ is equal to 1, $c,r\in\mathcal{C}$. (1i) forces each TP
to be served by a single SRC, and (1j) guarantees the deployment of a tree
topology.

Budget constraint: Constr. (1k) limits the acquisition of devices to the
budget $B$444This constraint makes sure not to consider in the budget the IAB
Donor (which is a fixed cost and thus not included in the variable budget) and
the ”fake” RIS (which is not an actual device but rather a way to keep the
formulation compact and easy to manage)..

Flow constraints (1l-1o): Const. (1l) guarantees flow balance at any BS in the
tree, const. (1m) upper bounds backhaul link flows to link capacities, const.
(1n) imposes both the minimum demand $D$ and the limit of maximum SRC
capacity. Finally, constr. (1o) limit the traffic entering the RAN from the
Core Network, under the assumption that this quantity cannot be more than the
capacity of the best-performing link coming out of the Donor, indicated by
$M^{\text{MAX}}$. Note that, although not strictly necessary, these types of
constraints help reduce the solution time by tightly shaping the solution
space.

Resource-sharing constraints (1p-1s): Constr. (1p) defines the timeshare
(assuming $1$ to be $100$% of the available time) dedicated to transmission
for any BS (in both the access and backhaul phases). Similarly, constr. (1q)
defines the reception timeshare. Constr. (1r) enforces half-duplex operation
mode considering both transmission and reception timeshares, while constr.
(1s) manages the timeshare of a RIS installed in CS $r\in\mathcal{C}$ among
different SRCs $\\{(t_{1},c_{1},r),\cdots,(t_{n},c_{n},r)\\},t_{1}\cdots
t_{n}\in\mathcal{T},c_{1}\cdots c_{n},r\in\mathcal{C}$.

RIS-orientation constr. (1t-1w): These constraints set the value of the
orientation variable $\phi_{c}$ dependent according to the angles between the
involved devices and force angles of reflection links to lie within the FoV of
the RIS, if any.555These constraints do not affect the status of the ”fake”
RIS, since it is not an actual device and does not need an orientation.

###  III-B Peak-Throughput Formulation (PTF)

The Peak-Throughput Formulation extends the Mean-Throughput formulation by
adding some variables and constraints. The other parts of the model are
inherited from the previous formulation.

As mentioned in Section I, when users manage to establish a peak-throughput
connection, the event is akin to a traffic burst, characterized by short
duration and no correlation with other users’ traffic. For this reason, the
allocation of the extra traffic enabled by the peak-throughput is
fundamentally different from the average traffic demand $g_{t,c,r}$, and must
be modeled with a distinct approach. While being routed on different links
from the IAB Donor to the final UE, the average demand $g_{t,c,r}$ for SRC
($t,c,r$) shares the same time resources with all the other SRCs in its path.
The extra traffic $g_{t,c,r}^{\text{X}}$, on the other hand, does not share
the resources with the other SRCs, but is allocated as if any considered UE is
the only one in the network and can reserve all the capacity that is not used
by the guaranteed traffic $g_{t,c,r}$.

The extra traffic of an SRC ($t,c,r$) is defined by the spare capacities of
the links in its route from the IAB Donor to the UE; its value is the one of
the BS with the least resources available (bottleneck BS). The timeshares
which are already reserved for the mean-throughput traffic of all UEs are
still guaranteed by constraints (1p-1s) and thus remain untouched.

Therefore, we add further flow variables to capture peak-throughput traffic.
They are listed in Table I. This model does not need to maximize the mean user
throughput; all instances of variable $g_{t,c,r}$ in MTF (in constraints
1l,1n,1p, and 1s) can be replaced with $Dx_{t,c,r}$, resulting in a leaner
formulation.
Objective function and constraints characterizing PTF are:

$\max\sum_{t\in\mathcal{T},c,r\in\mathcal{C}}g_{t,c,r}^{\text{X}}\\\ $ (2a)
s.t.: $\displaystyle
w_{t,c}^{\text{X}}+\sum_{d\in\mathcal{C}}\left(f_{t,d,c}^{\text{X}}-f_{t,c,d}^{\text{X}}\right)-\sum_{\
r\in\mathcal{C}}g_{t,c,r}^{\text{X}}=0,$ $\displaystyle\forall
t\in\mathcal{T},c\in\mathcal{C},$ (2b) $\displaystyle f_{t,c,d}^{\text{X}}\leq
C_{c,d}^{\text{BH}}z_{c,d},$ $\displaystyle\forall
t\in\mathcal{T},c,d\in\mathcal{C},$ (2c) $\displaystyle
g_{t,c,r}^{\text{X}}\leq C_{t,c,r}^{\text{SRC}}x_{t,c,r},$
$\displaystyle\forall t\in\mathcal{T},c,r\in\mathcal{C},$ (2d) $\displaystyle
w_{t,c}^{\text{X}}\leq M^{\text{MAX}}y_{c}^{\text{DON}},$
$\displaystyle\forall t\in\mathcal{T},c\in\mathcal{C},$ (2e)
$\displaystyle\sum_{r\in\mathcal{C}}\frac{g_{t,c,r}^{\text{X}}}{C_{t,c,r}^{\text{SRC}}}+\sum_{d\in\mathcal{C}}\frac{f_{t,d,c}^{\text{X}}}{C_{d,c}^{\text{BH}}}\leq
y_{c}^{\text{IAB}}-t_{c}^{\text{TX}}-t_{c}^{\text{RX}},$ $\displaystyle\forall
c\in\mathcal{C},t\in\mathcal{T},$ (2f)
$\displaystyle\sum_{d\in\mathcal{C}}(\frac{f_{t,d,c}^{\text{X}}}{C_{d,c}^{\text{BH}}}+\frac{f_{t,c,d}^{\text{X}}}{C_{c,d}^{\text{BH}}})\leq
y_{c}^{\text{IAB}}-t_{c}^{\text{TX}}-t_{c}^{\text{RX}},$ $\displaystyle\forall
c\in\mathcal{C},t\in\mathcal{T},$ (2g)
$\displaystyle\sum_{c\in\mathcal{C}}\frac{g_{t,c,r}^{\text{X}}}{C_{t,c,r}^{\text{RIS}}}\leq
y_{r}^{\text{RIS}}-\sum_{\begin{subarray}{c}\tau\in\mathcal{T}\\\
c\in\mathcal{C}\end{subarray}}\frac{Dx_{\tau,c,r}}{C_{\tau,c,r}^{\text{RIS}}},$
$\displaystyle\forall r\in\mathcal{C}\setminus{\tilde{c}},t\in\mathcal{T}.$
(2h)

The objective function (2a) maximizes the sum of the users’ peak throughputs
instead of the mean throughput of the previous formulation. Constr. (2b),
similar to constr. (1l), imposes the flow balance of the extra traffic routing
through the tree; constr. (2c-2e) are the counterparts of capacity-related
constr. (1m-1o), but involving the peak-throughput traffic. Finally, constr.
(2f-2h) respectively model the BS’ timeshare assigned to peak-throughput
traffic for a BS involved in an SRC (2f), for a BS only involved in peak-
throughput traffic backhauling (2g), and for a RIS (2h).

###  III-C Peak-Throughput Heuristics

The additional complexity introduced by peak-throughput traffic resulted in a
formulation that was too hard to be solved in a reasonable amount of time
(e.g., a single instance reached an unsatisfactory optimality gap of $30\%$ in
one hour); therefore, we have developed a heuristic approach to speed up
solving time while keeping a high level of quality of solutions. The technique
consists in reducing the $M^{\text{MAX}}$ parameter, representing the highest-
capacity backhaul link of the IAB Donor, to a fraction of its actual value, a
sort of forced bottleneck approach. This adjustment significantly reduces the
solution space, speeding up the branch-and-cut phase of the solution search.

This heuristic approach has been validated by comparing its results to those
of the exact formulation in a set of smaller scenarios. Due to space
limitations, we do not report the complete performance analysis. Nevertheless,
the two approaches produced very similar performance trends; the heuristic
approach reduces the solution time to an average of 6 seconds within a gap
smaller than $5\%$.

##  IV Results

In this section, we will compare the performances of the network scenarios
optimized according to the mean-throughput formulation (MTF) against the ones
obtained by applying the peak-throughput formulation (PTF), solved using the
heuristic approach in Section III-C. We first investigate mean and peak
throughputs achieved by both formulations, then we compare topological aspects
to obtain a comprehensive performance analysis of the strengths and weaknesses
of each model. The solutions are also iterated over progressively increasing
values of the available budget to observe how much CAPEX will impact the
quality of the solutions found.

The instances subject to network planning optimization are defined by a $150m$
radius hexagonal cell deployment area centered around a randomly chosen point
within a full 3D representation of the metropolitan area of Milan [24], which
includes buildings as opaque static obstacles of an actual urban scenario. The
installation of the IAB Donor is fixed to the leftmost vertex of the hexagon;
25 CSs and 15 TPs are then randomly placed in the area according to
surrounding buildings. The IAB Donor and the IAB Nodes are composed of three
$120^{\circ}$ sectors with $16x12$ element panel arrays ($12x8$ for the IAB
Node) and a $58dBm$ EIRP ($51dBm$ for the IAB Node), a carrier frequency of
$28GHz$ and a bandwidth of $200MHz$. The UEs are modeled as a $2$x$2$ antenna
array. RISs are made of $100$x$100$ passive elements in a rectangular array,
with a FoV of $120^{\circ}$. All devices have $\frac{\lambda}{2}$ spacing in
both directions between elements. The IAB Donor is set at a $25m$ height, the
IAB Nodes at $6m$, the RISs at $3m$, and the UEs at $1.5m$. The price of IAB
Nodes is normalized at $1$ unit of cost, while the expected inexpensive
production process of RISs compared to IAB Nodes is encapsulated in a price
ten times smaller at $0.1$. The total available budget spans from $6$ to $20$
units, with steps of $0.2$. Minimum UE demand is fixed at $150Mbps$. All the
link capacities are computed according to Shannon’s capacity. All the results
are averaged over $80$ random deployment instances generated through MATLAB
and solved with IBM ILOG CPLEX. The maximum optimality gap between the
feasible solutions found and their respective continuous relaxation upper
bound is fixed at $5\%$.

(a) Average installed devices

(b) Average throughputs per user

Figure 2: Device installation and throughput sensitivity to budget variation.

###  IV-A Performance Comparison

Figure 2a shows how RIS usage is more prominent in the MTF planning (dashed
blue curve), where, on average, four RIS are installed in each cell; in PTF
(dashed yellow curve), instead, RIS reduces to about 2 per scenario,
indicating that they are not suitable devices to increase peak throughput. As
for IAB Nodes, the two models perform in the same way up to around 10 units of
budget. Beyond that point, MTF (solid blue curve) tends to buy more IAB Nodes
compared to PTF (solid yellow curve). In Figure 2b, the metrics driving the
whole optimization are shown: the solid lines represent the mean throughput
achievable in cells planned with MTF (blue) and PTF (yellow), while the dashed
lines indicate the related peak throughput. It is clear from these results
that even if PTF’s results derive from a heuristic approach, peak throughputs
in PTF-planned layouts gain more than $150Mbps$ compared to those of the same
scenarios planned with MTF, while at the same time obtaining a similar mean
throughput. Remarkable is the fact that there is no need to increase the
available budget significantly above 12 units since the mean throughput is
almost constant throughout the plot, and the peak throughput does not show
meaningful improvement, further increasing the budget.
These results show that the PTF-planned networks obtain a quasi-optimal mean
throughput (i.e., like MTF planning) while notably improving the peak
throughput for the users, so they can fully exploit the entire capacity of the
RAN.

###  IV-B Topology Features

(a) Average number of hops per user

(b) Average degree of IAB Donor

Figure 3: Multi-hop and Donor degree sensitivity to budget variation.

In this subsection, we investigate how the different throughput performance
reflects in a different network topology generated by the two formulations.
Since the IAB network is intrinsically connected to the concept of multi-hop
forwarding, it is important to check the average path depth of the tree from
the IAB Donor to a generic UE, measured in number of hops. Together with the
depth, another relevant aspect of a tree topology is its degree, that is, how
many subtrees spawn from each node. In particular, the degree of the root node
(the IAB Donor) can be used as a metric to evaluate how close to a star
topology the RAN is. In Figure 3a, PTF obtains a consistently smaller average
number of hops per user than MTF, indicating that its trees must be shallower
than those generated by MTF. The degree of the Donor is shown in Figure 3b.
PTF not only assigns the Donor more incident links than MTF, but the two
curves have opposite trends as the available budget increases: PTF gets closer
to a star topology, while MTF departs from it. As a proof of concept, we
report in Figure 4 an instance with a significant difference between the peak
throughput obtained by the two models; it is evident how PTF (Figure 4b)
selects star-like topologies compared to MTF (Figure 4a). For completeness, we
include the same instance, shown from a three-dimensional isometric view in
Figure 5.

(a) MTF topology example, top view.

(b) PTF topology example, top view.

Figure 4: Topology comparison of the two formulations from the top.

(a) MTF topology example, isometric view.

(b) PTF topology example, isometric view.

Figure 5: Topology comparison of the two formulations from an isometric view.

##  V Conclusion

In this paper, we analyzed the potential of mm-Wave IAB RANs equipped with
RISs to provide peak and mean throughput traffic. Our analysis has
demonstrated that optimizing the network layout of mm-Wave RANs integrated
with IAB and RIS considering the peak user throughput can significantly
improve the achievable peak throughput in realistic urban scenarios compared
to the traditional mean-throughput approach. In addition, these layouts can
guarantee a mean throughput comparable with the one achievable via traditional
planning approaches.
Network layouts must move towards shallow star-like topology to pursue peak
throughput maximization. This has important practical implications for
developing and deploying next-generation networks, particularly in urban
environments, where the demand for ultra-high-speed connectivity is rapidly
increasing.

## Acknowledgment

The research in this paper has been carried out in the framework of Huawei-
Politecnico di Milano Joint Research Lab. The Authors acknowledge Huawei Milan
research center for the collaboration.

## References

  * [1] S. Rangan, T. S. Rappaport, and E. Erkip, “Millimeter-wave cellular wireless networks: Potentials and challenges,” _Proceedings of the IEEE_ , vol. 102, no. 3, pp. 366–385, 2014.
  * [2] M. R. Akdeniz, Y. Liu, M. K. Samimi, S. Sun, S. Rangan, T. S. Rappaport, and E. Erkip, “Millimeter wave channel modeling and cellular capacity evaluation,” _IEEE Jrn. on Sel. Areas in Comm._ , vol. 32, no. 6, pp. 1164–1179, 2014.
  * [3] Ericsson. (2022) ”ericsson mobility report: November 2022”. [Online]. Available: https://www.ericsson.com/en/reports-and-papers/mobility-report/reports/november-2022
  * [4] G. R. MacCartney, T. S. Rappaport, and S. Rangan, “Rapid fading due to human blockage in pedestrian crowds at 5g millimeter-wave frequencies,” in _GLOBECOM 2017 - 2017 IEEE Global Communications Conference_ , 2017, pp. 1–7.
  * [5] Y. Zhang, M. A. Kishk, and M.-S. Alouini, “A survey on integrated access and backhaul networks,” _Frontiers in Communications and Networks_ , vol. 2, 2021\. [Online]. Available: https://www.frontiersin.org/articles/10.3389/frcmn.2021.647284
  * [6] H. Willebrand and B. Ghuman, “Fiber optics without fiber,” _IEEE Spectrum_ , vol. 38, no. 8, pp. 40–45, 2001.
  * [7] M. Polese, M. Giordani, A. Roy, S. Goyal, D. Castor, and M. Zorzi, “End-to-end simulation of integrated access and backhaul at mmwaves,” in _2018 IEEE 23rd International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)_ , 2018, pp. 1–7.
  * [8] M. Polese, M. Giordani, T. Zugno, A. Roy, S. Goyal, D. Castor, and M. Zorzi, “Integrated access and backhaul in 5g mmwave networks: Potential and challenges,” _IEEE Communications Magazine_ , vol. 58, no. 3, pp. 62–68, 2020.
  * [9] R. Flamini, D. De Donno, J. Gambini, F. Giuppi, C. Mazzucco, A. Milani, and L. Resteghini, “Toward a heterogeneous smart electromagnetic environment for millimeter-wave communications: An industrial viewpoint,” _IEEE Transactions on Antennas and Propagation_ , vol. 70, no. 10, pp. 8898–8910, 2022\.
  * [10] E. Moro, I. Filippini, A. Capone, and D. De Donno, “Planning Mm-Wave access networks with reconfigurable intelligent surfaces,” in _2021 IEEE 32nd Annual Int. Sym. on Personal, Indoor and Mobile Radio Comm. (PIMRC)_ , Helsinki, Finland, Sep. 2021.
  * [11] P. Fiore, E. Moro, I. Filippini, A. Capone, and D. D. Donno, “Boosting 5g mm-wave iab reliability with reconfigurable intelligent surfaces,” in _2022 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2022, pp. 758–763.
  * [12] G. Leone, E. Moro, I. Filippini, A. Capone, and D. D. Donno, “Towards reliable mmwave 6g ran: Reconfigurable surfaces, smart repeaters, or both?” in _2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)_ , 2022, pp. 81–88.
  * [13] O. Tsilipakos, A. C. Tasolamprou, A. Pitilakis, F. Liu, X. Wang, M. S. Mirmoosa, D. C. Tzarouchis, S. Abadal, H. Taghvaee, C. Liaskos _et al._ , “Toward intelligent metasurfaces: The progress from globally tunable metasurfaces to software-defined metasurfaces with an embedded network of controllers,” _Advanced Optical Materials_ , vol. 8, no. 17, p. 2000783, 2020\.
  * [14] M. Di Renzo, M. Debbah, D.-T. Phan-Huy, A. Zappone, M.-S. Alouini, C. Yuen, V. Sciancalepore, G. C. Alexandropoulos, J. Hoydis, H. Gacanin _et al._ , “Smart radio environments empowered by reconfigurable ai meta-surfaces: An idea whose time has come,” _EURASIP Journal on Wireless Communications and Networking_ , vol. 2019, no. 1, pp. 1–20, 2019.
  * [15] H. Ju and R. Zhang, “Throughput maximization in wireless powered communication networks,” _IEEE Transactions on Wireless Communications_ , vol. 13, no. 1, pp. 418–428, 2014.
  * [16] Sandvine. (2022) ”2022 global internet phenomena report”. [Online]. Available: https://www.sandvine.com/global-internet-phenomena-report-2022
  * [17] ——. (2023) ”2023 global internet phenomena report”. [Online]. Available: https://www.sandvine.com/global-internet-phenomena-report-2023
  * [18] 3GPP, “3rd generation partnership project; technical specification group radio access network; nr; study on integrated access and backhaul; (release 16),” 3GPP, Tech. Rep., 2018.
  * [19] F. Devoti and I. Filippini, “Planning mm-wave access networks under obstacle blockages: A reliability-aware approach,” _IEEE/ACM Trans. on Networking_ , vol. 28, no. 5, pp. 2203–2214, 2020.
  * [20] S. Kutty and D. Sen, “Beamforming for millimeter wave communications: An inclusive survey,” _IEEE Communications Surveys & Tutorials_, vol. 18, no. 2, pp. 949–973, 2016.
  * [21] R. A. Ayoubi, M. Mizmizi, D. Tagliaferri, D. De Donno, and U. Spagnolini, “Network-controlled repeaters vs. reconfigurable intelligent surfaces for 6g mmw coverage extension,” 2022. [Online]. Available: https://arxiv.org/abs/2211.08033
  * [22] G. R. A. N. W. Group, “Study on channel model for frequencies from 0.5 to 100 ghz (release 15),” 3GPP, Tech. Rep., 2020.
  * [23] A. Capone, I. Filippini, S. Gualandi, and D. Yuan, _Resource Optimization in Multiradio Multichannel Wireless Mesh Networks_. John Wiley & Sons, Ltd, 2013, ch. 7, pp. 239–274. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/9781118511305.ch7
  * [24] (2012) ”milano geoportale - open data”. Comune di Milano. [Online]. Available: https://geoportale.comune.milano.it/sit/open-data/


4pt

# Adapting to Covariate Shift in Real-time
by Encoding Trees with Motion Equations

Tham Yik Foong, Heng Zhang, Mao Po Yuan,and Danilo Vasconcellos Vargas Danilo
Vasconcellos Vargas are with the Department of Information Science and
Technology at Kyushu University, Japan, and The University of Tokyo, Tokyo,
Japan.Tham Yik Foong, Heng Zhang, and Mao Po Yuan are with the Department of
Information Science and Technology at Kyushu University, Japan.This work was
supported by JST, ACT-I Grant Number JP-50243 and JSPS KAKENHI Grant Number
JP20241216. Tham Yik Foong and Heng Zhang are supported by JST SPRING, Grant
Number JPMJSP2136.

###### Abstract

Input distribution shift presents a significant problem in many real-world
systems. Here we present Xenovert, an adaptive algorithm that can dynamically
adapt to changes in input distribution. It is a perfect binary tree that
adaptively divides a continuous input space into several intervals of uniform
density while receiving a continuous stream of input. This process indirectly
maps the source distribution to the shifted target distribution, preserving
the data’s relationship with the downstream decoder/operation, even after the
shift occurs. In this paper, we demonstrated how a neural network integrated
with Xenovert achieved better results in 4 out of 5 shifted datasets, saving
the hurdle of retraining a machine learning model. We anticipate that Xenovert
can be applied to many more applications that require adaptation to unforeseen
input distribution shifts, even when the distribution shift is drastic.

###### Index Terms:

Distribution Shift, Covariate Shift, Adaptive Learning, Machine Learning,
Continual Learning

##  I Introduction

Changes are inevitable in nature; a system that is built around the assumption
that the environment is static often fails when the input distribution shifts.
For instance, a phenomenon called covariate shift happens when the input data
used to train a model differs from the input data encountered in testing [1,
2, 3, 4]. Research examining covariate shift has shown linear trends between
performance on shifted and unshifted test distributions, which degrade the
performance of the application [5, 6]. The earliest solutions proposed to
combat covariate shift involved adjusting the importance of training instances
to reduce the discrepancy between training and testing distributions [7, 8, 9,
10]. Subsequent methods involved finding the differences in densities between
two functions and then utilizing importance-weighted learning methods to
determine the parameters for training the models [11, 12]. Additionally, more
effective shift detection methods have also been developed to enable
counteractions [13].

Currently, machine learning approaches still fall short in terms of
adaptability when handling the problem of covariate shift in an online fashion
[3]. Most of the methods proposed are limited by the assumption that the
training and testing distributions should overlap to some extent [14]. Often,
the common workaround during the event of a covariate shift is to retrain the
model on the shifted dataset [15, 13]. This leads to a significant increase in
the cost of maintaining a machine learning model (i.e., the cost is directly
proportional to the scale of the dataset and the frequency of the shifting
events). Despite being a common phenomenon that is ubiquitous in many
scenarios, these issues are not properly addressed by an adaptive algorithm.

Figure 1: Xenovert’s adaptation from source distribution (red) to target
distribution (blue). The histogram displays the frequency of interval
activation, indicating that all intervals have nearly identical input
frequencies. Thus, this shows that the quasi-quantiles can divide the input
distribution uniformly.

To mitigate these issues, we introduce a parametric algorithm named Xenovert.
It uses a perfect binary tree to dynamically partition a continuous input
space into multiple intervals, each quantized to represent different degrees
of value. It achieves adaptation by adjusting the sizes of these intervals
while processing input sequentially to avoid imbalances among them. This
process maps the source distribution to a shifted target distribution via an
intermediate representation, which is a set of intervals (see Fig. 1). Our
experimental analysis of distribution shifts has demonstrated the novelty of
our method for continuously adapting to drastic distribution shifts.
Furthermore, we integrate the Xenovert with neural network to address
covariate shift, demonstrating its practical application on shifted datasets.
Without any retraining required, inputs processed by the Xenovert can retain
the mapping from the original training input to the shifted input, essentially
allowing the downstream neural network to adapt to the shifted input
distribution. The algorithm has been validated under three specific shifting
conditions: instant, gradual, and recurring, using different types of
probability distributions.

To summarize, this paper makes the following contributions:

  * •

We have developed an adaptive algorithm capable of managing drastic shifts in
the input distribution, even in cases where there is no overlap between the
source and target distributions, a topic yet to be extensively explored in the
field of machine learning.

  * •

We have integrated our algorithm with a neural network to enhance its
robustness against covariate shift and achieved better in 4 out of 5 shifted
datasets.

  * •

Through investigations of Xenovert with different types of probability
distributions and shifting types, we provide an extensive analysis of our
methods using simulation data.

##  II Related work

Numerous algorithms have been developed to either detect or adapt to
distribution shifts. Commonly, statistical hypothesis testing methods are
employed for detection purposes. For instance, the Kolmogorov-Smirnov Test
identifies when two distributions differ, yet it lacks the ability to provide
detailed quantification of the differences. Conversely, the shift function and
its variants, as in [16], are adept at detecting and quantifying the degree of
shifting between two distributions. To visualize and understand multivariate
distribution shifts, an algorithm called Relative Density Clouds based on
k-nearest neighbor density estimates was proposed. This method is particularly
useful for identifying and interpreting complex patterns of changes in
distribution characteristics, such as location, scale, and variation, which
aligns with the challenges of detecting shifts in multivariate distributions
[17].

Nevertheless, detecting a covariate shift alone is not sufficient. For models
to make accurate predictions, adapting to these shifts is essential. There are
algorithms that use moving-quantiles, akin to those in this work, to adapt to
recent changes in data streams. However, these methods rely typically on
predefined parameters, such as sliding windows, sketches (compact
representations in data stream processing), or frequency counters [18, 19, 20,
21]. A current benchmark for adapting to covariate shifts is the Dynamic
Importance Weighting (DIW) algorithm, which has demonstrated effectiveness in
handling these shifts in datasets [14]. However, DIW, which utilizes weight
estimation methods such as Kernel Mean Matching, Least-Squares Importance
Fitting, and Direct Importance Estimation, encounters limitations in handling
drastic shifts. This is primarily due to these methods’ heavy reliance on the
overlap between training and test distributions [22, 3, 14, 23, 24]. The
accuracy of weight estimations diminishes when distributions have minimal
overlap or when relationships between variables undergo substantial changes,
leading to reduced effectiveness under severe distribution shift conditions.
More recently, [25] addresses the challenge of continuous covariate shift by
using an online method for density ratio estimation under conditions of data
scarcity. Drastic shifts, however, are under-explored, as the method is aimed
at minimizing risk while training predictors over time, especially in
scenarios with continuously shifting test data distributions. Additionally,
the concept of online label shift has been explored in recent studies [26,
27].

##  III Methodology

###  III-A Xenovert

Figure 2: Illustration of indexing and level structure in Xenovert. Xenovert
divides the input using a tree structure with each node setting boundaries
into quasi-quantile, with leaf nodes indexing these quasi-quantiles. The index
of quasi-quantiles, $i=\\{0,1,\cdots,n\\}$ are sorted from left to right in
ascending order regardless of the hierarchy. The levels are sorted in
descending order in a top-down manner.

Figure 3: The illustration of Xenovert’s update function. Xenovert is a
perfect binary tree that uses its nodes to represent quasi-quantiles $q$,
which divide the input space into equal-sized intervals. In detail, when given
an input $x$ at time step $t$, the chosen quasi-quantiles approximate towards
the input with the update function $q_{i,t+1}=q_{i,t}+\alpha v_{i,t+1}s$;
Where $v$ is a velocity term, $alpha$ is the learning rate, $\theta$ is the
velocity decay, and $s=-1$ if $q-x>0$, otherwise, $s=1$. Starting from the
root quasi-quantiles $q_{r}$, we select the ‘left’ child node if $x<q_{r}$ (or
$x<q$, when it is not a root node); otherwise, select the ‘right’ child node.
The selected child node is marked in black. The gray shade is the interval
that the input falls into. If the input distribution remains constant, the
quasi-quantiles converge to an equilibrium state, eventually ensuring that all
intervals contain an equal concentration of inputs.

We propose the Xenovert, designed to adaptively segment a continuous input
space into multiple uniform intervals. The workflow of the Xenovert is
outlined as follows: First, we define the Xenovert as a perfect binary tree,
denoted as $T$, with a total $L$ level. Followed by that, each node in the
Xenovert is conceptualized as a quasi-quantile, represented by a scalar value
$q_{i}\in\mathbb{R}$, with the series ranging from $q_{0}$ to $q_{N}$, where
$N=2^{L}-1$. The root quasi-quantile, or root node, is represented as
$q_{r}=\frac{N+1}{2}$. The correspondence between the indexing of these quasi-
quantiles and the levels of the binary tree is illustrated in Figure 2. As the
level $L$ dictates the quasi-quantile count, it is chosen to optimize between
detailed input representation or adaptability, depending on the task
requirements.

The function for updating these quasi-quantiles is first conceptualized as a
Widrow-Hoff function for scalar value (quasi-quantile’s value). Therefore, we
can omit the cross-product with the input as the error already reflects the
input’s magnitude and direction:

$q_{i,t+1}=q_{i,t}+\alpha(q_{i,t}-x_{t})$ (1)

where $\alpha$ is the learning rate and $x_{t}$ is the current input, as well
as the expected value of $q_{i,t}$. The learning rule dictates that whenever
an input $x$ is introduced, the quasi-quantiles $q_{i,t+1}$ are updated to
gradually approach the value of this input. However, continuous input can
cause fluctuations around the expected value and fail to maintain stability.
To address this, we redefined the error term using a motion equation,
resulting in the final quasi-quantiles update function described by:

$s=\left\\{\begin{matrix}-1&,q-x>0\\\ 1&,otherwise\end{matrix}\right.$ (2)

$v_{i,t+1}=\theta v_{i,t}+|q_{i,t}-x_{t}|$ (3)

$f(q_{i})=q_{i,t+1}=q_{i,t}+\alpha v_{i,t+1}s$ (4)

where $v$ is a velocity term and $\theta$ is the velocity decay. We initialize
$\alpha$ to $1e-05$, $v$ to $0$ and $\theta$ to $0.99$. Over time, this motion
equation enables the quasi-quantiles to approximate the average of their
respective intervals. The velocity term $v$ serves as an damping or momentum
factor for each update, modulating the update rate of quasi-quantiles to
prevent excessive adjustments. In other words, small updates occur when the
selected quasi-quantile is close to the inputs, while larger updates occur if
the quasi-quantile is far from the subsequent inputs. The term $s$ in Eq. 2
determines the update direction.

The update occurs recursively from the root node to one of the leaf nodes.
Only the root node and the selected nodes will get updated, and the selection
criteria for the selected child node (quasi-quantiles) on each level are
defined by the selection function:

$f(q_{j})|\forall l<=L,j=\left\\{\begin{matrix}&i-2^{l-2},x<q_{i}\\\
&i+2^{l-2},x\geq q_{i}\end{matrix}\right.$ (5)

with $l$ being the current level in the binary tree, $i$ the index of the
current selected node (quasi-quantile), and $j$ the next selected node. At
each time step, the algorithm updates the selected quasi-quantiles on every
level ($L$ number of quasi-quantiles). Assuming the input distribution does
not change, these quasi-quantiles will uniformly distribute across the input
space over time. If a distribution shift occurs, the quasi-quantiles actively
adapt to this new distribution until it stabilizes. Figure 3A illustrates the
Xenovert’s update and selection functions.

To yield an output that is adapted to the distribution shift, Xenovert
converts input into quantized output $y$ by:

$C(q_{j}),j=\left\\{\begin{matrix}&i-2^{l-2},x<q_{i}\\\ &i+2^{l-2},x\geq
q_{i}\end{matrix}\right.,|\forall l<=L$ (6)

The convert function $C(q_{j})$ is a recursive function that iterates for $L$
times, and then returns the output value $y$, which equals $j$.

Figure 4: Simulation result of distributions with three types of shifting. (A)
The ridgeline plot shows the shifting from source distribution to target
distribution (bottom to top). The bottom row shows the degree of shifting in
source and target distribution. Based on the HI score learning curve, we
observed a general trend where the HI score drops when shifting starts to
occur and returns to a near-optimum score when Xenovert adapts to the new
distribution. (B) The adaptation of Xenovert is invariant to the degree of
shifting. Firstly, we experimented with Xenovert’s adaptation using inputs
drawn from a normal distribution, $\mathcal{N}(0,5)$ and $\mathcal{N}(50,5)$
as the source and target distributions, respectively. Followed by that, we
experimented with another set of distributions, $\mathcal{N}(0,5)$ and
$\mathcal{N}(250,5)$. The HI score learning curve, however, remains almost
identical in both experiments, proving its invariance to the degree of
shifting. (C) The higher the total level, the lesser the data compression and
information lost, but the lower the HI score. (D) The stability-adaptability
trade-off, where the higher the learning rate, the lower the stability but the
faster the adaptability.

##  IV Analyzing Xenovert on
Univariate Distribution Shift

###  IV-A Experiment setup

In this section, we evaluated the performance of Xenovert on various types of
distributions with three types of shifts. The type of shift indicates whether
the transition from source distribution to target distribution takes place
instantly or gradually over time. Besides, in the case of recurring shifts,
inputs are drawn seasonally or cyclically from the source distribution and
target distribution. Fig. 4 shows the experiment setup that evaluates Xenovert
on Uniform, Normal, Multimodal Normal, Chi-square, and Multivariate Normal
distribution with instant, gradual, and recurring shifting. In each
experiment, we generate a pair of source distributions and target
distributions. Both source and target distributions are defined with different
parameters. For instance, in Normal distribution tasks, the source
distribution is $\mathcal{N}(2,4)$ while the target distribution is
$\mathcal{N}(10,2)$. Inputs drawn from the source distribution are treated as
input before the distribution shift occurs, while inputs drawn from the target
distribution are treated as input after the distribution shift occurs.

The degree of shifting in this experiment is measured using a shift function.
The shift function quantifies how much two distributions differ; compare this
to a significant Kolmogorov–Smirnov test, where it only informs that the two
distributions differ, not how much. To verify whether the inputs drawn from
the target distribution are uniformly distributed by the quantiles, we use the
histogram intersection (HI) score to compare the prediction of Xenovert to a
uniform distribution. The HI score is a real value ranging from 0 to 1 that
indicates the similarity of two discretized probability distributions. When
the prediction of Xenovert is completely identical to a uniform distribution,
it will receive a maximum value of 1.

###  IV-B Result

The result in Table. I revealed that Xenovert can achieve close to the maximum
HI score consistently over the three types of distribution shifts with
noticeable adaptivity. This adaptivity is revealed by the HI score over time
shown in Fig. 4, in which the Xenovert can first adapt to the source
distribution and reach equilibrium. Once the shifting happens, the Xenovert
starts adapting spontaneously to fit the target distribution, given enough
input; this is indicated by the dropping and climbing of the HI score. With
the above-mentioned sufficient experiments and adequate results, we then
generalized the approach to other applications, as described in the following
sections.

Xenovert is further shown to be invariant to the degree of shifting. This is
verified by the recorded identical HI scores of two experiments, conducted
using (1) $\mathcal{N}(0,5)$ and $\mathcal{N}(50,5)$ as source distributions
and (2) $\mathcal{N}(250,5)$ as target distributions (Fig. 4A). Additionally,
we analyzed the total levels of the Xenovert on the HI score (i.e., the number
of quantized outputs). The higher the total level, the lesser the data
compression and information lost, as the number of quantized outputs
increased. The graph in Fig. 4B shows that the HI score decreases as the total
levels increase and data compression decreases. Other than that, we
investigated how the progression of the HI score was affected by different
values of learning rate. We observed that the higher the learning rate, the
lower the stability but faster the adaptability (Fig. 4C). This is referred to
as the stability-adaptability trade-off. Note that an extreme learning rate
(e.g., $0.01$) can cause large fluctuations, leading to a lower HI score.

TABLE I: HI scores for adapting to the shifting of Uniform, Normal, Multimodal
Normal, and Chi-squared distributions, with different types of shifts. Result
are mean ± SD.

Distribution | Instant shift | Gradual shift | Recurring shift
---|---|---|---
Uniform | $0.984\pm 0.000$ | $0.992\pm 0.001$ | $0.976\pm 0.001$
Normal | $0.972\pm 0.001$ | $0.990\pm 0.001$ | $0.975\pm 0.001$
Multimodal Normal | $0.982\pm 0.001$ | $0.984\pm 0.001$ | $0.989\pm 0.001$
Chi-Squared | $0.983\pm 0.000$ | $0.981\pm 0.001$ | $0.984\pm 0.001$

##  V Application on Covariate Shift Problem

###  V-A Experiment setup

Covariate shift refers to changes in the distribution of the input variables
$x$, even when the mapping to the label $y$ remains unchanged in $X\rightarrow
Y$ problems. In other words, it can be defined as the case where the
conditional distribution $P_{tr}(y|x)=P_{tst}(y|x)$ remains unchanged but
$P_{tr}(x)\neq P_{tst}(x)$. Covariate shift mainly occurs under the influence
of a non-stationary environment or sampling bias [3, 4, 28, 29]. For instance,
global climate change can be a driver of phenotypic changes in plants and
crops. Thus, the morphological shift can affect the measurement of their
features over time [30, 31]. This can potentially pose a problem for the
classifier that failed to incorporate such an event. Here, we investigate how
our method can be applied to mitigate covariate shifts in real-world data.

Figure 5: Diagram illustrating the integration of Xenoverts with a Neural
Network. The dataset consists of $p$ features, and each feature is
independently processed by one of the $p$ Xenoverts, resulting in a set of
quantized inputs. These inputs are then fed into the neural network. As the
Xenoverts adapt, the neural network is concurrently trained. Notably, after a
covariate shift, the neural network’s parameters can remain frozen, performing
inference as usual. However, the Xenoverts continue to adapt to the evolving
input distribution, ensuring the quantized inputs stay pertinent for the
neural network’s inference.

Figure 6: Feature distributions for three example datasets, illustrating the
original population distribution and the corresponding shifted distributions
for training and testing sets. The training set depicted is a subset, adjusted
to match the size of the testing set for visualization purposes. These
visualizations are referred from [24].

Figure 7: Adaptation of Xenovert to the input distribution before (left) and
after (right) covariate shift. (Top) The activation frequencies of the
intervals are kept approximately uniform online, achieved through Xenovert’s
reorganization of the values of its quasi-quantiles (dashed line).

This experiment compares neural networks trained under three conditions: with
Xenovert, without Xenovert, and with DIW. When integrated with Xenovert, the
neural network employs the Xenovert(s) to transform raw inputs into quantized
inputs based on the intervals they fall into (for the architecture of this
integration, refer to Figure 2). Every time an input is fed into the Xenovert,
it will reconfigure its quasi-quantiles corresponding to the input. A basic
two-layer Multilayer Perceptron (MLP) was employed as the neural network model
across all three conditions. This simple MLP configuration primarily aimed to
test the effects of Xenovert and DIW with minimal influence from the
complexity of the neural network itself.

We conducted our experiments on five shifted datasets, comprising two for
classification tasks and three for regression tasks. The models’ performances
were evaluated using accuracy for the classification tasks and Mean Squared
Error (MSE) for the regression tasks. Our study includes real-world datasets,
such as Diabetes [32], Abalone [33], Iowa House Prices [34], and the Mosquito
Indicator in Korea. These datasets were chosen for their inherent natural
shifts, including sampling bias and data rearranging before significant shifts
occurred. We also apply an artificial shift to the Iris dataset attributes to
simulate a drastic shift, simulating the adaptive changes in plant attributes
driven by global climate change, as mentioned earlier in this section.

The handling of each dataset, including the specific methods used for
introducing shifts and preparing the data for analysis, is detailed in
Appendix B-A. Figure 6 provides examples of selected features from the
datasets, illustrating their states before and after the shifts. We also
compared performance on unshifted datasets (original forms of Iris and
Abalone) versus their shifted versions to evaluate any potential information
loss caused by Xenovert. For each dataset, we trained the standard MLP and the
integrated models using the source distribution (pre-shift data) and evaluated
their performance using the target distribution (post-shift data), assessing
their ability to adapt to changes in data distribution.

###  V-B Result

The results summarized in Table II show that MLP integrated with Xenovert
achieved the best result in 4 out of 5 shifted datasets, especially one with
drastic shifts. This highlights Xenovert’s ability to adapt to covariate
shifts. In the Iris dataset, the standard MLP model exhibited a significant
accuracy reduction from $1.00\pm 0.00$ without shift to $0.36\pm 0.67$ with
shift. In contrast, MLP with Xenovert effectively maintained its high
accuracy, recording $0.99\pm 0.01$ both with and without shift. For the
Diabetes dataset, both the standard MLP and MLP with Xenovert showed a similar
trend in terms of accuracy, respectively, whereas MLP with DIW had a lower
accuracy.

In the shifted regression datasets, the standard MLP’s performance on the
Abalone dataset increased in MSE from $2.34\pm 0.14$ in the unshifted
condition to $7.038\pm 2.635$ in the shifted condition. MLP with Xenovert,
however, demonstrated a lower MSE of $3.953\pm 0.271$ under the shifted
condition. In the regression tasks across other tested datasets, MLP with
Xenovert consistently demonstrated a lower MSE compared to the standard MLP.
This hints at its stable performance despite the influence of the covariate
shift in regression tasks. Note that MLP with DIW is not applicable for the
regression tasks.

A separate analysis comparing performance on datasets with and without shifts
reveals a minor degradation in performance for MLP with Xenovert. This is
likely due to information loss during the quantization process. Despite this,
MLP with Xenovert demonstrated consistent resilience to shifts, maintaining
stable performance metrics in both shifted and unshifted conditions. In
contrast, the standard MLP model exhibited a significant decline in accuracy
and an increase in MSE under shifted conditions, indicating a vulnerability to
shifts in input, specifically those that are drastic.

TABLE II: Comparison of Neural Networks with Xenovert, without Xenovert, and
with DIW on Covariate Shift Dataset.

Dataset\Method | MLP | MLP+Xenovert | MLP+DIW
---|---|---|---
Classification (Accuracy $\uparrow$)
Iris (no shift) | $1.00\pm 0.00$ | $0.99\pm 0.01$ | $0.98\pm 0.01$
Iris | $0.36\pm 0.67$ | $0.99\pm 0.01$ | $0.34\pm 0.08$
Diabetes | $0.56\pm 0.07$ | $0.56\pm 0.05$ | $0.52\pm 0.09$
Regression (MSE $\downarrow$)
Abalone (no shift) | $2.34\pm 0.14$ | $2.41\pm 0.11$ | -
Abalone | $7.038\pm 2.635$ | $3.953\pm 0.271$ | -
Iowa House Prices | $76199.49\pm 3219.5$ | $61374.59\pm 1169.3$ | -
Mosquito Indicator in Korea | $15.24\pm 6.21$ | $13.99\pm 1.05$ | -

##  VI Computational Complexity Analysis

We analyze the computational complexity of the two primary operations in the
proposed Xenovert algorithm: the update function $f(x)$, which adapts quasi-
quantiles to accommodate shifts in each input, and the convert function
$C(x)$, which returns a quantized output. Both functions exhibit a complexity
of $O(N\cdot L)$, where $N$ is the number of inputs and $L$ is the depth of
the tree. The computational complexity of these functions is primarily due to
their recursive traversal from the root to a leaf node in the tree by the
depth $L$.

##  VII Discussion

In this study, we present an online method that adapts to distribution shifts,
a critical challenge in dynamic data environments. This is accomplished
through the adaptive algorithm proposed by adjusting the value of quasi-
quantiles to approximate the interval’s average.

In the univariate distribution shift experiment, the Xenovert demonstrated its
capability to adjust quasi-quantiles, guiding them towards the average within
their intervals. Consequently, it uniformly divided the input space, mapping
any type of distribution into a uniform distribution. Moreover, the results
showed that Xenovert is robust against instant, gradual, and recurring
distribution shifts. Nonetheless, the Xenovert’s output seldom produces a
perfect uniform distribution as the most recent inputs account for the
imperfection, since these types of adaptive algorithms are, arguably, more
sensitive to recent temporal input.

Particularly, increasing the number of quasi-quantiles can reduce the
information loss during compression when transforming intervals into quantized
output. However, this increase also heightens the sensitivity of each quasi-
quantile, leading them to adjust their values more frequently, which
consequently lowers the HI score. In addition, the stability-adaptability
trade-off hints that the learning rate should be tuned according to the
shifting rate of the input distribution. Heuristically, a problem with rapid
shifting might require sacrificing precision for faster adaptability.
Conversely, the issue of having a task that requires more precision but is
constrained by limited data can easily be mitigated by bootstrapping the data.

The experimental results show that integrating a neural network with the
Xenovert enables adaptation to data with covariate shifts. This can save the
hurdle of periodically detecting shifts and retraining a classifier,
especially for systems expected to be deployed in environments subject to
change. The key to achieving this is maintaining the mapping between the
training input and the shifted testing input through the use of configurable
quasi-quantiles. A notable limitation, however, is the potential information
loss inherent in compressing raw input into a set of quantized units.
Therefore, the total level of the Xenovert needs to be scaled accordingly to
balance information retention and quantization efficiency. Our algorithm is
not intended to supplant the current state-of-the-art methods for addressing
covariate shift. For example, methods like dynamic importance reweighting are
more adept at handling shifts caused by noise or outliers, but less so with
drastic shifts; Rather, we propose our algorithm as a simpler alternative for
this specific issue while also offering a potential solution for other similar
problems.

##  VIII Conclusion

In conclusion, we may characterize Xenovert as a general-purpose adaptive
algorithm that maintains an equal division of input distribution. Due to its
simplicity, we speculate the algorithm can be further applied to other
applications. Additionally, future work will focus on developing a more
generalized version of Xenovert, capable of handling high-dimensional inputs,
potentially an N-dimensional Xenovert.

##  Appendix A Xenovert

Algorithm 1 and Algorithm 2 displayed the pseudocode for the workflow of
quasi-quantiles and Xenovert. The source code of the models has been made
available to download in a DOI (doi.org/10.5281/zenodo.8127371).

Algorithm 1 Quasi-quantile

class QQ $\triangleright$ Quasi-quantile object

$leftChild:$ QQ

$rightChild:$ QQ

$l=0$ $\triangleright$ Current level

$\alpha=1e-05$ $\triangleright$ Learning rate

$v=0$ $\triangleright$ Velocity

$\theta=0.99$ $\triangleright$ Velocity decay

$q=0$ $\triangleright$ Quasi-quantile’s value

procedure Grow($\alpha$, $q$, $l$)

if $leftChild$ exist then

$leftChild.\textsc{Grow}(\alpha,q,l)$ $\triangleright$ Call Grow recursively

$rightChild.\textsc{Grow}(\alpha,q,l)$

else

Instantiate quasi-quantiles object as children

$leftChild:=$ QQ$(\alpha,q,l+1)$

$rightChild:=$ QQ$(\alpha,q,l+1)$

end if

end procedure

procedure Update($x$)

$v^{\prime}=\theta\times v+|q-x|$

$s=1$

if $q-x>0$ then

$s=-1$

end if

$q^{\prime}=q+\alpha\times v^{\prime}\times s$

if $leftChild$ exist then

if $x<q$ then

$leftChild$.Update($x$)

else

$rightChild$.Update($x$)

end if

end if

end procedure

Output a quantized output according to the selected interval

procedure Convert($x$, offset)

if $leftChild$ exist then

if $x<q$ then

$leftChild$.Convert($x$, offset)

else

$rightChild$.Convert($x$, $2^{l}+$offset)

end if

else

if $x<q$ then

return offset

else

return $2^{l}+$offset

end if

end if

end procedure

end class

Algorithm 2 Xenovert

class Xenovert $\triangleright$ Xenovert object

$\alpha=1e-05$ $\triangleright$ Learning rate

$q=0$ $\triangleright$ Root quasi-quantile’s value

$rootQuasiQuatile:=$ QQ($\alpha$, $q$) $\triangleright$ Root quasi-quantile

$X$ $\leftarrow$ Input distribution

Grow the binary tree $L$ times

$l=0$

for $L$ do

$rootQuasiQuatile.\textsc{Grow}(\alpha,q,l)$

end for

procedure Update($X$)

for $x\in X$ do

$rootQuasiQuatile.\textsc{Update}(x)$

end for

end procedure

Output a quantized output based on input $x$

procedure Output($x$)

return $rootQuasiQuatile.\textsc{Convert}(x)$

end procedure

end class

##  Appendix B Experiment details

###  B-A Covariate shift Problem

In our experiment, we prepared five shifted datasets, including synthetic
datasets and real-world datasets, to explore the impact of covariate shift on
machine learning model performance. Here we denote the training set as
$X_{tr}$ and shifted testing set as $X_{te}$, with each dataset split based on
the predefined criteria specified below. Note that we added Gaussian noise to
the input features if the attribute is an integer to prevent the true divide
issue. Xenovert can be iteratively updated with online data, but this can
introduce some bias to the most recent data if they are temporally correlated
over many samples. To mitigate this, we can implement shuffles on the data
distribution that is fed into Xenovert.

We compare two neural networks that learn with Xenovert and without Xenovert.
When working with Xenovert, each i.i.d feature in $X_{tr}$ will be fed into a
corresponding Xenovert for the adaptation process. For instance, in the case
of the Iris dataset, 4 features are paired with 4 Xenoverts. Following that,
each Xenovert performed adaptation and produced a quantized output
$O\in\\{0,M\\}\in\mathbb{Z}$. The quantized outputs are used as raw inputs to
train a Multi-layer perceptron network (MLP) for the downstream operation. The
architecture of the network is composed of two hidden layers; each layer
contains 200 neurons and a ReLU activation function. The input layer takes
four inputs, and the output layer outputs the cross entropy of three classes.
For the MLP training, we set the batch size to 200, the epoch to 2000, and a
learning rate of 0.01. After the network is trained, we feed $X_{te}$ to
Xenoverts for adaptation and to produce quantized outputs. The network takes
those quantized outputs and performs classification without retraining. On the
other hand, the neural network without Xenovert, which adopted the same
architecture, is trained with a training set and performs classification on
shifted testing sets without re-training. We then compare their accuracy to
determine the effectiveness of Xenovert in handling covariate shift.

####  B-A1 Iris [35]

The Iris dataset preprocessing introduced an artificial shift by increasing
petal length and width in $X_{te}$ by 5 units. The original dataset served as
the $X_{tr}$, creating a distinct morphological shift of the species.

####  B-A2 Diabetes [32]

We order the dataset by age and split it by patients younger than age 24 as
$X_{tr}$ and patients older and equal to age 24 as the $X_{te}$. We select
Glucose and BMI as features, determined by Pearson’s correlation to predict
whether a patient has diabetes.

####  B-A3 Abalone [33]

We apply sampling bias by segmenting based on the feature Whole weight of the
abalones, following the experiment setting from [24].

####  B-A4 Iowa House Prices [34]

We split the dataset by the feature YearBuilt, which indicates the year the
house was built. Data of houses that were built before or during the year 2000
will be included in $X_{tr}$. Data of houses that were built after the year
2000 will be included in $X_{tr}$. We selected GrLivArea and OverallQual as
features, determined by Pearson’s correlation to the label, house prices.

####  B-A5 Mosquito Indicator in Korea

We introduce sampling bias through temporal partitioning of the data,
designating records up until 2018 for $X_{tr}$ and those from 2019 forward for
$X_{te}$.

##  Appendix C Statistical analysis

The reported statistical test was analyzed using Python (SciPy). The data
shown in the covariate shift study were obtained from at least 30 independent
experiments. The results gathered in the univariate experiments were obtained
from at least 30 independent experiments. Values in different experimental
groups are expressed as the mean ± standard deviation. $p<0.05$ was considered
statistically significant.

## Acknowledgment

This work was supported by JST, ACT-I Grant Number JP-50243 and JSPS KAKENHI
Grant Number JP20241216. Tham Yik Foong and Heng Zhang are supported by JST
SPRING, Grant Number JPMJSP2136.

## References

  * [1] C. M. Bishop and N. M. Nasrabadi, _Pattern recognition and machine learning_. Springer, 2006, vol. 4, no. 4.
  * [2] A. E. Kelly and M. L. Goulden, “Rapid shifts in plant distribution with recent climate change,” _Proceedings of the National Academy of Sciences_ , vol. 105, no. 33, pp. 11 823–11 826, 2008.
  * [3] J. Quinonero-Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence, _Dataset shift in machine learning_. Mit Press, 2008.
  * [4] M. Sugiyama, S. Nakajima, H. Kashima, P. Buenau, and M. Kawanabe, “Direct importance estimation with model selection and its application to covariate shift adaptation,” _Advances in neural information processing systems_ , vol. 20, 2007.
  * [5] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga, R. L. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. Earnshaw, I. Haque, S. M. Beery, J. Leskovec, A. Kundaje, E. Pierson, S. Levine, C. Finn, and P. Liang, “Wilds: A benchmark of in-the-wild distribution shifts,” in _Proceedings of the 38th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, M. Meila and T. Zhang, Eds., vol. 139. PMLR, 18–24 Jul 2021, pp. 5637–5664. [Online]. Available: https://proceedings.mlr.press/v139/koh21a.html
  * [6] D. Hendrycks, S. Basart, N. Mu, S. Kadavath, F. Wang, E. Dorundo, R. Desai, T. Zhu, S. Parajuli, M. Guo _et al._ , “The many faces of robustness: A critical analysis of out-of-distribution generalization,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 8340–8349.
  * [7] A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf, “Covariate shift by kernel mean matching,” _Dataset shift in machine learning_ , vol. 3, no. 4, p. 5, 2009.
  * [8] J. Huang, A. Gretton, K. Borgwardt, B. Schölkopf, and A. Smola, “Correcting sample selection bias by unlabeled data,” _Advances in neural information processing systems_ , vol. 19, 2006.
  * [9] Y. Yu and C. Szepesvári, “Analysis of kernel mean matching under covariate shift,” _arXiv preprint arXiv:1206.4650_ , 2012.
  * [10] S. Bickel, M. Brückner, and T. Scheffer, “Discriminative learning under covariate shift.” _Journal of Machine Learning Research_ , vol. 10, no. 9, 2009.
  * [11] T. Mehmood, K. H. Liland, L. Snipen, and S. Sæbø, “A review of variable selection methods in partial least squares regression,” _Chemometrics and intelligent laboratory systems_ , vol. 118, pp. 62–69, 2012.
  * [12] M. Sugiyama, S. Nakajima, H. Kashima, M. Kawanabe _et al._ , “Kullback-leibler importance estimation procedure for covariate shift adaptation,” _JSAI Technical Report, Type 2 SIG_ , vol. 2007, no. DMSM-A702, p. 03, 2007.
  * [13] H. Raza, G. Prasad, and Y. Li, “Adaptive learning with covariate shift-detection for non-stationary environments,” 09 2014, pp. 1–8.
  * [14] T. Fang, N. Lu, G. Niu, and M. Sugiyama, “Rethinking importance weighting for deep learning under distribution shift,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 11 996–12 007, 2020.
  * [15] S. G. Finlayson, A. Subbaswamy, K. Singh, J. Bowers, A. Kupke, J. Zittrain, I. S. Kohane, and S. Saria, “The clinician and dataset shift in artificial intelligence,” _The New England journal of medicine_ , vol. 385, no. 3, p. 283, 2021.
  * [16] G. A. Rousselet, C. R. Pernet, and R. R. Wilcox, “Beyond differences in means: robust graphical methods to compare two groups in neuroscience,” _European Journal of Neuroscience_ , vol. 46, no. 2, pp. 1738–1748, 2017.
  * [17] M. Del Giudice, “Relative density clouds: Visualizing and exploring multivariate patterns of group differences,” _PloS one_ , vol. 18, no. 6, p. e0287784, 2023.
  * [18] A. Arasu and G. S. Manku, “Approximate counts and quantiles over sliding windows,” in _Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 2004, pp. 286–296.
  * [19] L. Wang, G. Luo, K. Yi, and G. Cormode, “Quantiles over data streams: an experimental study,” in _Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data_ , 2013, pp. 737–748.
  * [20] Z. Karnin, K. Lang, and E. Liberty, “Optimal quantile approximation in streams,” 2016.
  * [21] T. M. Martinetz, S. G. Berkovich, and K. J. Schulten, “’neural-gas’ network for vector quantization and its application to time-series prediction,” _IEEE transactions on neural networks_ , vol. 4, no. 4, pp. 558–569, 1993.
  * [22] M. Sugiyama, T. Suzuki, and T. Kanamori, _Density ratio estimation in machine learning_. Cambridge University Press, 2012.
  * [23] T. Zhang, I. Yamane, N. Lu, and M. Sugiyama, “A one-step approach to covariate shift adaptation,” 2021.
  * [24] M. Sugiyama and K.-R. Müller, “Input-dependent estimation of generalization error under covariate shift,” 2005.
  * [25] Y.-J. Zhang, Z.-Y. Zhang, P. Zhao, and M. Sugiyama, “Adapting to continuous covariate shift via online density ratio estimation,” _arXiv preprint arXiv:2302.02552_ , 2023.
  * [26] Y. Bai, Y.-J. Zhang, P. Zhao, M. Sugiyama, and Z.-H. Zhou, “Adapting to online label shift with provable guarantees,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 29 960–29 974, 2022.
  * [27] Y.-H. Yan, P. Zhao, and Z.-H. Zhou, “Online non-stochastic control with partial feedback,” _Journal of Machine Learning Research_ , vol. 24, no. 273, pp. 1–50, 2023.
  * [28] S. J. Pan and Q. Yang, “A survey on transfer learning,” _IEEE Transactions on knowledge and data engineering_ , vol. 22, no. 10, pp. 1345–1359, 2009.
  * [29] J. G. Moreno-Torres, T. Raeder, R. Alaiz-Rodríguez, N. V. Chawla, and F. Herrera, “A unifying view on dataset shift in classification,” _Pattern recognition_ , vol. 45, no. 1, pp. 521–530, 2012.
  * [30] A. S. Jump and J. Penuelas, “Running to stand still: adaptation and the response of plants to rapid climate change,” _Ecology letters_ , vol. 8, no. 9, pp. 1010–1020, 2005.
  * [31] G. R. Guerin, H. Wen, and A. J. Lowe, “Leaf morphology shift linked to climate change,” _Biology letters_ , vol. 8, no. 5, pp. 882–886, 2012.
  * [32] J. W. Smith, J. E. Everhart, W. Dickson, W. C. Knowler, and R. S. Johannes, “Using the adap learning algorithm to forecast the onset of diabetes mellitus,” in _Proceedings of the annual symposium on computer application in medical care_. American Medical Informatics Association, 1988, p. 261.
  * [33] W. Nash, T. Sellers, S. Talbot, A. Cawthorn, and W. Ford, “Abalone,” UCI Machine Learning Repository, 1995, DOI: https://doi.org/10.24432/C55C7W.
  * [34] D. De Cock, “Ames, iowa: Alternative to the boston housing data as an end of semester regression project,” _Journal of Statistics Education_ , vol. 19, no. 3, 2011.
  * [35] R. A. Fisher, “The use of multiple measurements in taxonomic problems,” _Annals of eugenics_ , vol. 7, no. 2, pp. 179–188, 1936.

|  Tham Yik Foong received a BSc (Hons) in Software Engineering with
Multimedia from Limkokwing University in 2017. He then received an MSc in
Machine Learning in Science at the University of Nottingham in 2020.
Currently, he is working towards his Ph.D. degree at Kyushu University, Japan,
since 2021, supported by the prestigious SPRING Scholarship from one of
Japan’s largest funding agencies. his research interests lie in adaptive
algorithms, reinforcement learning, and reservoir computing.
---|---
|  Heng Zhang received the B.Eng. degree from the Department of Electronic
Information Engineering, Shenzhen University, China, 2019, and the M.Sc.
degree from the Department of Electrical and Electronic Engineering, The
University of Manchester, 2020. He is currently pursuing the Ph.D. degree in
Kyushu University, Japan, since 2021. His current research interests include
bio-inspired machine learning, artificial intelligence, and robust and
adaptive learning algorithms. He has been receiving the SPRING Scholarship to
study at Kyushu University since 2021, which is supported by one of the
biggest Japanese funding agencies.
---|---
|  Mao Po Yuan received a BSc in Mechanical Engineering from National Chung
Hsing University in 2020. Currently, he is working towards his master’s degree
at Kyushu University, Japan, since 2022. His research interests lie in
generative model, computer vision, and robustness.
---|---
|  Danilo Vasconcellos Vargas is an associate professor at Kyushu University,
a visiting researcher at the University of Tokyo, and CEO/Founder of MiraiX.
His research interests include AI, evolutionary computation, and complex
adaptive systems. He has published numerous works in prestigious journals and
received several awards, including the IEEE Transactions on Evolutionary
Computation Outstanding 2022 Paper award. He has presented tutorials at
various conferences, co-organized and advised workshops, and leads the
Laboratory of Intelligent Systems focused on building robust and adaptive AI
funded by JST and JSPS.
---|---