# Massive Access in Extra Large-Scale MIMO with Mixed-ADC over Near-Field
Channels

Yikun Mei, Zhen Gao, De Mi, , Mingyu Zhou, Dezhi Zheng, Michail Matthaiou, ,
Pei Xiao, , and Robert Schober This work was supported in part by the Natural
Science Foundation of China (NSFC) under Grant 62071044 and Grant U2001210; in
part by the Shandong Province Natural Science Foundation under Grant
ZR2022YQ62; in part by the Beijing Nova Program. _(Corresponding authors: Zhen
Gao; Mingyu Zhou.)_ Y. Mei is with the School of Information and Electronics,
Beijing Institute of Technology, Beijing 100081, China. Z. Gao and D. Zheng
are with the MIIT Key Laboratory of Complex-Field Intelligent Sensing, Beijing
Institute of Technology, Beijing 100081, China, also with the Yangtze Delta
Region Academy, Beijing Institute of Technology (Jiaxing), Jiaxing 314019,
China, and also with the Advanced Technology Research Institute, Beijing
Institute of Technology, Jinan 250307, China. D. M and P. Xiao are with
University of Surrey, Guildford GU2 7XH, U.K. M. Zhou is with Baicells
Technologies Co. Ltd., Beijing 100089, China. M. Matthaiou is with Queen’s
University Belfast, Belfast BT3 9DT, U.K. R. Schober is with Friedrich-
Alexander Universität Erlangen-Nürnberg, 91054 Erlangen, Germany. (e-mails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Massive connectivity for extra large-scale multi-input multi-output (XL-MIMO)
systems is a challenging issue due to the near-field access channels and the
prohibitive cost. In this paper, we propose an uplink grant-free massive
access scheme for XL-MIMO systems, in which a mixed-analog-to-digital
converters (ADC) architecture is adopted to strike the right balance between
access performance and power consumption. By exploiting the spatial-domain
structured sparsity and the piecewise angular-domain cluster sparsity of
massive access channels, a compressive sensing (CS)-based two-stage orthogonal
approximate message passing algorithm is proposed to efficiently solve the
joint activity detection and channel estimation problem. Particularly, high-
precision quantized measurements are leveraged to perform accurate hyper-
parameter estimation, thereby facilitating the activity detection. Moreover,
we adopt a subarray-wise estimation strategy to overcome the severe angular-
domain energy dispersion problem which is caused by the near-field effect in
XL-MIMO channels. Simulation results verify the superiority of our proposed
algorithm over state-of-the-art CS algorithms for massive access based on XL-
MIMO with mixed-ADC architectures.

###### Index Terms:

Compressive sensing, massive access, mixed-ADC, orthogonal approximate message
passing, XL-MIMO system.

##  I Introduction

Massive machine-type communication (mMTC) has long been identified as a major
enabler of the Internet-of-Everything that will seamlessly connect a vast
number of devices in future wireless networks[1, 3, 2]. To achieve the low
latency, high efficiency, and reliability required for mMTC, uplink grant-free
massive access schemes leveraging non-orthogonal radio resources have been
widely investigated in recent years [3, 5, 6, 7, 4, 8]. Due to the inherent
sporadic traffic of mMTC, compressive sensing (CS)-based solutions have been
proposed for joint activity detection and channel estimation (JADCE) yielding
good performance [5, 6, 7, 4]. In [5], an approximate message passing
(AMP)-based detection algorithm was proposed to solve the JADCE problem by
leveraging the virtual angular domain sparsity of massive multi-input multi-
output (MIMO) channels. Furthermore, the authors of [6] explored cooperation-
based massive access for cell-free massive MIMO systems to avoid inter-cell
interference. In the context of millimeter-wave/terahertz massive MIMO
systems, the authors of [7] proposed two multi-rank aware JADCE algorithms to
exploit the simultaneously sparse and low-rank structure of the delay-angular
domain channels.

However, it is believed that massive MIMO-based 5G networks will gradually
reach their limits. To accommodate denser connections with higher data rates
in 6G networks, deploying extra large-scale MIMO (XL-MIMO) at the base station
(BS) with extremely large array aperture has recently been proposed as a
promising 6G candidate technology [9, 10]. Compared with massive MIMO, the
emerging XL-MIMO substantially increases the near-field region, causing the
access devices to fall into the near-field electromagnetic propagation
environment. In this case, the near-field channels should be carefully modeled
using spherical wavefronts, rather than the conventional far-field plane-wave
assumption, requiring dedicated signal processing methods. To this end, near-
field channel estimation has been investigated for XL-MIMO systems in [9, 11,
10] by considering grant-based multiple access while supporting a relatively
small number of users. State-of-the-art JADCE solutions for massive access are
based on the far-field plane-wave assumption, and their performance will
degrade in near-field MIMO channels. Additionally, it is unrealistic to deploy
high-resolution analog-to-digital converters (ADC) across all the antennas of
XL-MIMO systems. To reduce cost and power consumption, MIMO receivers with
low-resolution ADCs have been proposed in [12, 13]. However, the quantization
noise caused by low-resolution ADCs significantly reduces the accuracy of the
received signals, limiting detection performance. To improve performance,
mixed-ADC architectures utilizing a large number of low-resolution ADCs with a
small number of high-resolution ADCs were investigated in [14, 15], and the
optimal ADC bit allocation for massive MIMO systems was analyzed in [16].

In this paper, we design a CS-based grant-free random access scheme for
massive connectivity based on XL-MIMO employing the mixed-ADC architecture,
where a two-stage orthogonal approximate message passing (TS-OAMP) algorithm
is proposed to solve the JADCE problem. Specifically, the common support
structure of the spatial-domain channel and the cluster sparsity of the
piecewise angular-domain channel are exploited to enhance the performance of
activity detection and channel estimation, respectively. Moreover, a small
number of high-resolution ADCs can ensure accurate hyper-parameter estimation
by using the expectation-maximization (EM) algorithm, and the adopted
subarray-wise estimation is capable of mitigating the angular-domain energy
dispersion of near-field MIMO channels. Simulation results demonstrate that
the proposed algorithm outperforms the state-of-the-art JADCE schemes for
massive access in XL-MIMO systems.

_Notations:_ Column vectors and matrices are denoted by boldface lower and
upper-case symbols, respectively; $(\cdot)^{\rm T}$, $(\cdot)^{\rm H}$ and
$(\cdot)^{-1}$ denote the transpose, conjugate transpose, and inverse of a
matrix, respectively; $\|\cdot\|_{p}$ is the $\ell_{p}$ norm of the argument;
${\bf A}_{:,n}$ denotes the $n$-th column vector of matrix $\bf A$;
$\Re\\{\cdot\\}$ and $\Im\\{\cdot\\}$ denote the real and imaginary parts of
the argument, respectively; $\text{diag}(\bf a)$ and $\text{diag}(\bf A)$
denote a diagonal matrix with $\bf a$ as the main diagonal and the diagonal
vector of matrix $\bf A$, respectively; $\text{Bdiag}(\cdot)$ denotes a block
diagonal matrix created from input matrices; ${\cal C}{\cal
N}({\bm{\mu}},{\bf\Sigma})$ denotes the complex Gaussian distribution with
mean vector $\bm{\mu}$ and covariance matrix ${\bf\Sigma}$; $\Phi(\cdot)$ and
$\phi(\cdot)$ are the cumulative distribution function and probability
distribution function of a standard Gaussian random variable, respectively;
${\rm sign}(\cdot)$ and $\delta(\cdot)$ denote the signum function and the
Dirac function, respectively; $|\cdot|_{c}$ denotes the the cardinality of a
set.

##  II System Model

We consider uplink grant-free massive Internet-of-Things (IoT) access based on
XL-MIMO systems. The BS deploys an extra large-scale uniform linear array
(ULA) comprising $N_{r}$ antenna elements, where the distance between two
adjacent antenna elements is half a wavelength. There are $K$ single-antenna
IoT devices in the coverage area of the BS. Due to the inherent sporadic
traffic in mMTC, though $K$ can be very large, the number of simultaneously
active devices $K_{a}$ can be small $(K_{a}\ll K)$. During the training phase,
the $k$-th active device transmits the unique pilot sequence
${{\bf{s}}_{k}}{\in\mathbb{C}^{M}}$ to the BS, and the received signal
${{\bf{Y}}}{\in\mathbb{C}^{M\times N_{r}}}$ can be expressed as

${{\bf{Y}}}=\sum\limits_{k=1}^{K}{{\alpha_{k}}}{\sqrt{P_{k}}}{{\bf{s}}_{k}}{{\bf{h}}^{\rm
T}_{k}}+{{\bf{W}}}={\bf{S}}{{\bf{H}}}+{{\bf{W}}},\vspace{-1mm}$ (1)

where ${{\alpha_{k}}}$ is the binary activity indicator that equals one when
the $k$-th device is active and zero otherwise,
${\bf{h}}_{k}{\in\mathbb{C}^{N_{r}}}$ is the channel vector between the $k$-th
device and the extra large array at the BS, $P_{k}$ is the $k$-th device’s
transmit power, ${{\bf{W}}}$ is the additive white Gaussian noise, each column
of which follows ${\cal CN}{\left({\bf 0},\sigma^{2}{\bf I}_{M}\right)}$,
${\bf{S}}=\left[{{\bf{s}}_{1}},\ldots,{{\bf{s}}_{K}}\right]{\in\mathbb{C}^{M\times
K}}$, and
${{\bf{H}}}=\left[{{\alpha_{1}}}{\sqrt{P_{1}}}{{\bf{h}}_{1}},\ldots,{{\alpha_{K}}}{\sqrt{P_{K}}}{{\bf{h}}_{K}}\right]^{\rm
T}{\in\mathbb{C}^{K\times N_{r}}}$. The pilot matrix $\bf S$ is generated by
randomly selecting $M$ rows from a $K$-dimensional discrete Fourier transform
(DFT) matrix and satisfies ${\bf S}{\bf S}^{\rm H}={\bf{I}}_{M}$.

The extra-large array aperture of the BS effectively increases the Rayleigh
distance, which determines the boundary between the far and near fields. For
instance, assuming $N_{r}=512$ and a carrier wavelength of $\lambda=0.05$ m,
the theoretical Rayleigh distance is around $6.5$ km [10]. Thus, the near-
field region is large and will cover most IoT devices around the BS. This
illustrates that XL-MIMO systems significantly increase the extent of the
near-field region. Thus, in typical XL-MIMO systems, most IoT devices are
located within the near-field coverage, and the channels should be modeled
based on spherical wavefronts instead of the conventional planar wavefronts.
In this case, the narrowband channel between the $n$-th antenna and the $k$-th
device can be expressed as ${{{h}}_{k,n}}=\beta_{k,n}{{{\tilde{h}}}_{k,n}}$,
where $\beta_{k,n}$ and ${{{\tilde{h}}}_{k,n}}$ are the large-scale fading and
the small-scale fading coefficients, respectively. Moreover,
${{{\tilde{h}}}_{k,n}}$ can be modeled as

${{{\tilde{h}}}_{k,n}}=\sqrt{\frac{\kappa_{k}}{\kappa_{k}+1}}e^{j\frac{2\pi}{\lambda}d^{\rm
LoS}_{k,n}}+\sqrt{\frac{1}{\kappa_{k}+1}}\sum\limits_{l=1}^{L_{p}}e^{j\frac{2\pi}{\lambda}d^{\rm
NLoS}_{k,n,l}},\vspace{-1mm}$ (2)

where $\kappa_{k}$ is the Rician factor for the $k$-th device, $\lambda$ is
the wavelength, $d^{\rm LoS}_{k,n}$ and $d^{\rm NLoS}_{k,n,l}$ are the
distances of the line of sight (LoS) component and the $l$-th non-LoS (NLoS)
component between the $n$-th antenna and the $k$-th device, respectively, and
$L_{p}$ is the number of NLoS components.

Note that conventional far-field channels can be modeled based on the 3GPP
spatial channel model (SCM) [18], which assumes that for each multipath
component, all receive antennas at the BS share the same angle-of-arrival
(AoA). However, in XL-MIMO systems, this assumption may not hold, since the
distance between the receive antennas and the devices can vary dramatically
for different receive antennas. This near-field effect in XL-MIMO channels
destroys the Fourier transform relationship between the spatial-domain channel
and the angular-domain channel that exists for far-field propagation, leading
to significant energy dispersion, as shown in Fig. 1. Correspondingly, the
traditional far-field massive MIMO channel estimation methods exploiting
angular-domain sparsity are not applicable in near-field XL-MIMO systems. As a
consequence, it is necessary to develop dedicated massive access approaches
for near-field XL-MIMO systems.

Figure 1: Comparison between the near-field and far-field angular-domain
channels, where $\theta$ represents the AoA, the distance of the LoS component
in the near-field and far-field environments is $48$ m and $1000$ m,
respectively, $N_{r}=512$, and $L_{p}=3$.

##  III Proposed CS-Based JADCE Algorithm

During one frame, the active devices send their pilot sequence to the BS in
the training phase. Once the identity information and the channel state
information of the active devices are obtained, the BS can recover the data
transmitted by these active devices through existing techniques [19].
Consequently, we focus on how to efficiently solve the JADCE problem.

In view of the high cost of configuring high-resolution ADCs for all antennas,
we consider a mixed-ADC architecture. Before the quantization, a variable gain
amplifier (VGA) with automatic gain control (AGC) is applied to scale the
analog signal to the appropriate range. Then, the quantized received signal
${\widetilde{\bf Y}}$ can be expressed as

${\widetilde{\bf
Y}}_{:,n}=g\left({\bf{Y}}_{:,n}\right)=\begin{cases}{\bf{Y}}_{:,n},&n\in{\cal
H}\\\ {\cal Q}_{B}\left({{\bf{Y}}}_{:,n}\right),&n\in{\cal L}\end{cases},\ \ \
\forall n,\vspace{-1mm}$ (3)

where ${{\cal Q}_{B}}(\cdot)$ is the complex $B$-bit quantizer, ${\cal H}$ and
${\cal L}$ are the index sets of the RF chains employing high-resolution and
low-resolution ADCs, respectively. In practice, the quantizer is applied to
the received signals element-wise, with the real and imaginary parts quantized
separately. For simplicity, here we consider uniform quantization. Define a
set of thresholds $r_{0}<r_{1}<r_{2}<\cdots<r_{2^{B}}$, where
$r_{0}=-\infty,r_{2^{B}}=\infty,r_{b}=-1+2^{1-B}b,b=1,2,\cdots,2^{B}-1$. For
any input element $Y\in(r_{b-1},r_{b}]$, ${\widetilde{Y}}=-1+2^{-B}(2b-1)$ is
the output after quantization.

To leverage the sparsity of the angular-domain channel, the quantized signals
${\widetilde{\bf Y}}$ need to be multiplied by the dictionary matrix. However,
directly processing ${\widetilde{\bf Y}}$ using the conventional JADCE
approaches [6, 5, 7] would not harness the gains of high-resolution quantized
measurements, since the proportion of high-precision quantized measurements is
small. On the other hand, it has been demonstrated that the common sparsity of
the spatial-domain channel on different antennas can be exploited to enhance
activity detection performance [5]. Inspired by these considerations, we
propose a TS-OAMP algorithm to solve the JADCE problem with the generalized
linear model (GLM) in (3). As shown in Fig. 2, the proposed algorithm can be
divided into two stages as follows:

$\bullet$ Stage 1: This stage identifies the active devices based on the
problem formulation of the spatial-domain channel with common support
sparsity. Moreover, the noise variance is estimated through the EM algorithm
using high-resolution quantized signals.

$\bullet$ Stage 2: By leveraging the intermediate results in Stage 1, this
stage aims to estimate the piecewise angular-domain channel with cluster
sparsity. To avoid the significant energy spread caused by the near-field
effect, we decompose the whole array into several subarrays, and each subarray
is individually processed based on a conventional far-field analysis.

###  III-1 Stage 1

Figure 2: Block diagram of the proposed TS-OAMP algorithm.

A similar problem for the GLM caused by the limited quantization has been
solved in [6, 13, 15]. Inspired by these works, we define two modules: a non-
linear module and a standard linear model (SLM) module. For simplicity, we
first define ${\bf{Z}}={\bf{SH}}$, so that the quantized received signal is
given by ${\widetilde{\bf Y}}=g\left({\bf{Z}}+{{\bf{W}}}\right)$.

The non-linear module performs de-quantization based on the minimum mean
square error (MMSE) estimator and outputs the extrinsic messages as the input
to the SLM module. Since the quantization function is non-linear, the element-
wise MMSE estimator is employed to obtain the posterior mean $\hat{\bf Z}$ and
variance ${\bm{\nu}}$, reducing the strong quantization noise. After that, by
denoting the extrinsic message of the non-linear module as ${\bf{Z}}_{\rm
ext}$ and ${{\bm{\nu}}_{\rm ext}}$, the equivalent SLM problem can be written
as

${\bf{Z}}_{\rm ext}={\bf{S}}{{\bf{H}}}+{{\bf{W}_{\rm ext}}},\vspace{-1mm}$ (4)

where the $n$-th column of the equivalent noise ${\bf{W}_{\rm ext}}$ is
characterized by ${\cal CN}{\left({\bf 0},\nu_{{\rm ext},n}{\bf
I}_{M}\right)}$. Note that ${{\bf{H}}}$ is the spatial-domain channel and
exhibits the common sparsity structure, namely

${\rm supp}\\{{\bf{h}}_{n}\\}={\rm supp}\\{{\bf{h}}_{n^{\prime}}\\},\ \
\forall n,n^{\prime}\in{\cal H},n\neq n^{\prime},\vspace{-1mm}$ (5)

where ${{\bf{h}}}_{n}={{\bf{H}}}_{:,n}$ and ${\rm supp}\\{\cdot\\}$ denotes
the set of non-zero elements of a vector.

To solve the typical multiple measurement vector (MMV) CS problem in (4), we
adopt the OAMP-MMV algorithm in [8]. Generally, the OAMP algorithm proposed in
[20] is more robust than the traditional AMP algorithm and has fewer
requirements on the sensing matrix. Specifically, the OAMP algorithm consists
of a de-correlated linear estimator and a divergence-free estimator, and the
final output is the MMSE estimate when the algorithm converges. Furthermore,
the OAMP-MMV algorithm was developed in [8] to solve the MMV CS problem with a
common sparsity structure. Based on this Bayesian framework, we assume that
the a priori distribution of $h_{k,n}$ is

$p\left({{h_{k,n}}}\right)=\left({1-{\lambda_{k,n}}}\right)\delta\left({{h_{k,n}}}\right)+{{{\lambda_{k,n}}}}{\cal
CN}{\left(0,\psi_{n}\right)},\vspace{-1mm}$ (6)

where the a priori sparsity ratio $\lambda_{k,n}$ denotes the non-zero
probability of $h_{k,n}$. Then, the posterior mean and variance are obtained
with the MMSE estimator of the OAMP-MMV algorithm111Due to space constraints,
we omit the details of the derivation of the OAMP-MMV algorithm and refer
interested readers to [8] for more information.. Subsequently, the SLM module
passes extrinsic messages to the input of the non-linear module.

The steps of Stage 1 are summarized in lines 1-24 of Algorithm 1, where
$T_{1}$ is the maximum number of iterations for this stage. The non-linear
module comprises lines 4-11 for de-quantization, where ${\bf\hat{Z}}$ and
${\bm{\nu}}$ are calculated in lines 4-10 with some abuse of notation, since
they are applied to the real and imaginary parts, respectively. The extrinsic
message is given in line 11, where high-resolution and low-resolution
quantized signals are handled differently. This is intuitive because the
signals with high-resolution quantization are accurate. Lines 12-22 describe
the OAMP-MMV algorithm, which constitutes the SLM module. The posterior
sparsity ratio ${\pi}_{k,n}$ is given in line 15, which represents the
posterior non-zero probability of $h_{k,n}$. Lines 19-21 are the EM steps to
update the unknown parameters. In line 20, the common sparsity structure is
exploited to update the sparsity ratio ${\lambda}_{k,n}$ by averaging, and
${\cal M}$ is defined as

${\cal
M}=\begin{cases}\left\\{1,2,...,N_{r}\right\\},&(\sigma^{2})^{t-1}\geq(\sigma^{2})_{\text{Th}},\\\
{\cal H},&\text{otherwise},\end{cases}\vspace{-1.5mm}$ (7)

where the threshold $(\sigma^{2})_{\text{Th}}=\frac{1}{|{\cal
H}|_{c}}\sum\limits_{n\in{\cal H}}\frac{\|\tilde{\bf
Y}_{:,n}\|_{2}^{2}}{(\text{SNR}_{\text{Th}}+1)M}$ to distinguish low signal-
to-noise ratio (SNR) levels and high SNR levels is obtained according to a
coarse estimate of the noise variance in Eq. (35) of [5], and
$\text{SNR}_{\text{Th}}$ is set to $10$ based on our computer experiments. In
(7), a small number of high-resolution signals are insufficient to perform
accurate activity detection at low SNR levels. Thus, low-resolution signals
are exploited to enhance the common sparsity structure. However, they should
be removed from activity detection when the SNR is high, avoiding the
interference caused by quantization noise. Moreover, the channel variance
$\psi_{n}$ and noise variance $\sigma^{2}$ are updated as lines 19 and 21,
respectively, where we also use the high-resolution signals to update the
noise variance. On the contrary, previous works either assume that the noise

Algorithm 1 Proposed TS-OAMP Algorithm

0: ${\widetilde{\bf Y}}$, ${\bf{S}}$, and ${\bf{D}}_{\mathrm{sub}}$.

0: ${\hat{{\bf{X}}}}$ and $\hat{\bm{\alpha}}$.

1: %Stage 1:

2: Initialize ${\tilde{\bf{u}}_{n}^{0}=\bm{0},{\bf{u}}_{n}^{0}=\bm{0}}$, and
${{{\tilde{v}}_{n}^{0}}}=1$. $({\sigma^{2}})^{0}$, $\psi_{n}^{0}$, and
${{\lambda^{0}_{k,n}}}$ are initialized as Eqs. (35)-(37) of [5];

3: for $t=1$ to $T_{1}$ do

4:
$\mathring{y}_{m,n}=\Re\\{{\tilde{y}}_{m,n}\\}\in(r_{b-1},r_{b}],\mathring{u}^{t-1}_{m,n}=\Re\\{{\tilde{u}}^{t-1}_{m,n}\\}$;

5: $\eta^{t}_{m,n}=\frac{{\rm
sign}(\mathring{y}_{m,n})\mathring{u}^{t-1}_{m,n}-{\rm
min}\\{|r_{b-1}|,|r_{b}|\\}}{\sqrt{[(\sigma^{2})^{t-1}+{\tilde{v}}^{t-1}_{n}]/2}}$;

6: $\xi^{t}_{m,n}=\frac{{\rm
sign}(\mathring{y}_{m,n})\mathring{u}^{t-1}_{m,n}-{\rm
max}\\{|r_{b-1}|,|r_{b}|\\}}{\sqrt{[(\sigma^{2})^{t-1}+{\tilde{v}}^{t-1}_{n}]/2}}$;

7: ${\hat{z}}_{m,n,\Re}^{t}=\mathring{u}^{t-1}_{m,n}+\frac{{\rm
sign}(\mathring{y}_{m,n}){\tilde{v}}_{n}^{t-1}}{\sqrt{2[{(\sigma^{2})^{t-1}}+{\tilde{v}}_{n}^{t-1}]}}$$\left[\frac{\phi(\eta^{t}_{m,n})-\phi(\xi^{t}_{m,n})}{\Phi(\eta^{t}_{m,n})-\Phi(\xi^{t}_{m,n})}\right]$;

8:
${\nu}_{n,\Re}^{t}=\frac{{\tilde{v}}^{t-1}_{n}}{2}-\frac{({\tilde{v}}_{n}^{t-1})^{2}}{2[(\sigma^{2})^{t-1}+{\tilde{v}}^{t-1}_{n}]}\times\frac{1}{M}\sum\limits_{m=1}^{M}$
$\left[\frac{\eta^{t}_{m,n}\phi(\eta^{t}_{m,n})-\xi^{t}_{m,n}\phi(\xi^{t}_{m,n})}{\Phi(\eta^{t}_{m,n})-\Phi(\xi^{t}_{m,n})}+\left(\frac{\phi(\eta^{t}_{m,n})-\phi(\xi^{t}_{m,n})}{\Phi(\eta^{t}_{m,n})-\Phi(\xi^{t}_{m,n})}\right)^{2}\right]$;

9: Set
$\mathring{y}_{m,n}=\Im\\{{\tilde{y}}_{m,n}\\},\mathring{u}^{t-1}_{m,n}=\Im\\{{\tilde{u}}^{t-1}_{m,n}\\}$,
then calculate ${\hat{z}}_{m,n,\Im}^{t}$ and ${\nu}_{n,\Im}^{t}$ by repeating
lines 5-8;

10: ${\hat{\bf z}}_{n}^{t}={\hat{\bf z}}_{n,\Re}^{t}+j{\hat{\bf
z}}_{n,\Im}^{t}$, ${\nu}_{n}^{t}={\nu}_{n,\Re}^{t}+{\nu}_{n,\Im}^{t}$;

11: $n\in{\cal L}:{\bf z}_{{\rm ext},n}^{t}=\nu_{{\rm
ext},n}^{t}\left(\frac{{\hat{\bf z}}_{n}^{t}}{{\nu}_{n}^{t}}-\frac{{\tilde{\bf
u}}_{n}^{t}}{{\tilde{v}}_{n}^{t}}\right),\frac{1}{\nu_{{\rm
ext},n}^{t}}=\frac{1}{{\nu}^{t}_{n}}-\frac{1}{{\tilde{v}}_{n}^{t}}$;
$n\in{\cal H}:{\bf z}_{{\rm ext},n}^{t}={\tilde{\bf y}}_{n},\nu_{{\rm
ext},n}^{t}=(\sigma^{2})^{t}$;

12:
$v_{n}^{t}=\frac{1}{M}\|{\bf{z}}^{t}_{\mathrm{ext},n}-{\bf{S}}{{\bf{u}}_{n}^{t-1}}\|^{2}_{2}-{\nu_{{\rm
ext},n}^{t}}$;

13:
${{\bf{r}}_{n}^{t}}={{\bf{u}}_{n}^{t-1}}+\frac{K}{M}{{\bf{S}}^{\rm{H}}}\left({{\bf{z}}^{t}_{\mathrm{ext},n}-{\bf{S}}{{\bf{u}}_{n}^{t-1}}}\right)$;

14: ${\tau}_{n}^{t}=\frac{K-M}{M}{v}_{n}^{t}+\frac{K}{M}{\nu^{t}_{{\rm
ext},n}}$;

15:
$({\pi^{t}_{k,n}})^{-1}=1+\frac{(1-\lambda^{t-1}_{k,n})(\tau^{t}_{n}+\psi^{t-1}_{n})}{\lambda^{t-1}_{k,n}\tau^{t}_{n}}\exp{(-\frac{\psi^{t-1}_{n}|r^{t}_{k,n}|^{2}}{\tau^{t}_{n}(\tau^{t}_{n}+\psi^{t-1}_{n})})}$;

16:
${\mu}^{t}_{k,n}={\pi}^{t}_{k,n}\frac{{\psi^{t-1}_{n}}}{{\tau^{t}_{n}}+{\psi^{t-1}_{n}}}{r}^{t}_{k,n}$;

17:
${\gamma}^{t}_{n}=\frac{1}{K}\sum\limits_{k=1}^{K}\left[{\pi}^{t}_{k,n}\frac{\tau^{t}_{n}\psi^{t-1}_{n}}{\tau^{t}_{n}+\psi^{t-1}_{n}}+(1-\pi^{t}_{k,n})|{\mu}^{t}_{k,n}|^{2}\right]$;

18:
$u_{k,n}^{t}=\frac{\tau_{n}^{t}{{\gamma}^{t}_{n}}}{\tau_{n}^{t}-{{\gamma}^{t}_{n}}}\left(\frac{\mu^{t}_{k,n}}{{\gamma}^{t}_{n}}-\frac{r_{k,n}^{t}}{\tau_{n}^{t}}\right)$;

19:
${\psi}_{n}^{t}={\sum\limits_{k=1}^{K}\left[\frac{\tau_{n}^{t-1}\psi_{n}^{t}}{\tau_{n}^{t}+\psi_{n}^{t-1}}+\left(\frac{\pi_{k,n}^{t}r_{k,n}^{t}}{\tau_{n}^{t}+\psi_{n}^{t-1}}\right)^{2}\right]}/{\sum\limits_{k=1}^{K}\pi_{k,n}^{t}}$;

20:
${\lambda}_{k,1}^{t}={\lambda}_{k,2}^{t}=\cdots={\lambda}_{k,N_{r}}^{t}=\frac{1}{|{\cal
M}|_{c}}\sum\limits_{n^{\prime}\in{\cal M}}{\pi}_{k,n^{\prime}}^{t}$;

21: $(\sigma^{2})^{t}=\frac{1}{|{\cal H}|_{c}}\sum\limits_{n\in{\cal
H}}(\frac{1}{M}{{\|{\tilde{\bf
Y}}_{:,n}-{\bf{S}}{\bm{\mu}_{n}^{t}}\|}_{2}^{2}}+{{\gamma}^{t}_{n}})$;

22: ${\tilde{\bf u}}^{t}_{n}={\bf S}{\bf
u}^{t}_{n},({{\tilde{v}}_{n}^{t}})^{-1}=({{{\gamma}^{t}_{n}}})^{-1}-({\tau_{n}^{t}})^{-1}$;

23: end for

24: Obtain ${\hat{\alpha}_{k}}$ according to (8) ;

25:

26: %Stage 2:

27: Initialize ${\bf Z}_{\mathrm{ext}}^{T_{1}+1}={\bf Z}_{\rm ext}^{T_{1}}{\bf
D}_{\mathrm{sub}}$, ${\bf U}^{T_{1}}={\bf U}^{T_{1}}{\bf D}_{\mathrm{sub}}$,
${\bm{\nu}}_{{\rm ext}}^{T_{1}+1}=\text{diag}({\bf
D}^{\mathrm{H}}_{\mathrm{sub}}{\text{diag}({\bm{\nu}}_{{\rm
ext}}^{T_{1}})}{\bf D}_{\mathrm{sub}})$,
$\lambda^{T_{1}+1}_{k,n}=\lambda^{0}_{k,n}$, and
${\bm{\psi}}^{T_{1}+1}=\text{diag}({\bf
D}^{\mathrm{H}}_{\mathrm{sub}}{\text{diag}({\bm{\psi}}^{T_{1}})}{\bf
D}_{\mathrm{sub}})$;

28: for $t=T_{1}+1$ to $T_{1}+T_{2}$ do

29:
$v_{n}^{t}=\frac{1}{M}\|{\bf{z}}^{T_{1}+1}_{\mathrm{ext},n}-{\bf{S}}{{\bf{u}}_{n}^{t-1}}\|^{2}_{2}-\nu_{{\rm
ext},n}^{T_{1}+1}$;

30: Repeat lines 13-15 and let
${\pi^{t}_{k,n}}={\pi^{t}_{k,n}}{\hat{\alpha}_{k}}$, then repeat lines 16-19;

31: ${\lambda}_{k,n}^{t}=\frac{1}{|{\cal
N}_{n}|_{c}}\sum\limits_{n^{\prime}\in{\cal N}_{n}}{\pi}_{k,n^{\prime}}^{t}$;

32: end for

33: $\hat{\bf
X}=\left[{\bm{\mu}}_{1}^{T_{1}+T_{2}},{\bm{\mu}}_{2}^{T_{1}+T_{2}},\cdots,{\bm{\mu}}_{N_{r}}^{T_{1}+T_{2}}\right]$.

variance is known [13, 15] or estimate it by neglecting the quantization noise
[6], where the former is impractical and the latter is ineffective for low-bit
quantized measurements.

When the iterative process terminates, the final posterior sparsity ratio is
used to detect activity. The Bayesian activity detector is defined as follows:

${\hat{\alpha}}_{k}=\begin{cases}1,&{\lambda}_{k,N_{r}}^{T_{1}}\geq 0.5,\\\
0,&\text{otherwise},\end{cases}\ \ \ \forall k.\vspace{-1mm}$ (8)

If ${\hat{\alpha}}_{k}=1$, the $k$-th device is considered to be active,
otherwise it is inactive.

###  III-2 Stage 2

In this stage, our goal is to estimate the angular-domain channel from the
intermediate results of Stage 1\. To mitigate the severe energy dispersion
effect in near-field MIMO channels as illustrated in Fig. 1, we divide the
whole XL-MIMO array into $N_{\rm sub}$ subarrays; then, the piecewise angular-
domain channel can be represented as follows

${{\bf{X}}}={{\bf{H}}}{{\bf{D}}_{\mathrm{sub}}},\vspace{-1mm}$ (9)

where
${{\bf{D}}}_{\mathrm{sub}}=\text{Bdiag}({{\bf{D}}},\cdots,{{\bf{D}}})\in{\mathbb{C}}^{N_{r}\times
G_{r}}$ consists of $N_{\mathrm{sub}}$ traditional dictionary matrices
${\bf{D}}\in{\mathbb{C}}^{N_{r}/N_{\mathrm{sub}}\times
G_{r}/N_{\mathrm{sub}}}$, and $G_{r}$ denotes the dimension of the dictionary.
The $(m,n)$-th element of $\bf D$ is given by

${\bf{D}}_{m,n}=\frac{1}{\sqrt{G_{r}/N_{\mathrm{sub}}}}e^{j(m-1)\pi\frac{2(n-1)-G_{r}/N_{\mathrm{sub}}}{G_{r}/N_{\mathrm{sub}}}}.\vspace{-1mm}$
(10)

Accordingly, the equivalent SLM problem in (4) becomes

${\bf{Z}}_{\rm ext}{{\bf{D}}}_{\mathrm{sub}}={\bf{S}}{{\bf{X}}}+{{\bf{W}_{\rm
ext}}}{{\bf{D}}}_{\mathrm{sub}},\vspace{-1.5mm}$ (11)

and we can adopt a similar approach as in Stage 1 to estimate X. It is worth
mentioning that the activity pattern detected in Stage 1 can be exploited as a
priori information to enhance the estimation performance.

The whole process of Stage 2 is represented by lines 26-33 of Algorithm 1,
where $T_{2}$ is the maximum number of iterations for this stage. Line 27
specifies the necessary transformation from the spatial-domain expression to
the angular-domain expression. Lines 29-30 repeat the OAMP-MMV algorithm from
Stage 1, where the detected activity information is utilized to constrain
$\pi^{t}_{k,n}$. The clustered sparsity structure of the angular-domain
channel is adaptively learned in line 31, where ${\cal N}_{n}=\\{n-1,n+1\\}$
denotes the neighbor indices of $x_{n}$ in a subarray.

Similar to [21], the _damping_ technique is adopted to effectively prevent the
proposed TS-OAMP algorithm from divergence. Specifically, for line 18 of
Algorithm 1, we have
${u}^{t}_{k,n}=(1-\epsilon){u}^{t}_{k,n}+\epsilon{u}^{t-1}_{k,n}$, where the
damping factor is chosen as $\epsilon=0.4$. Likewise, ${\tilde{v}}^{t}_{n}$ is
damped in the same way.

In Table I, we compare the computational complexity of Algorithm 1 with that
of several baseline algorithms, including the structured sparsity-based
generalized approximated message passing (SS-GAMP) algorithm [6], the OAMP-MMV
algorithm [8], and the simultaneous weighted orthogonal matching pursuit
(SWOMP) algorithm [5]. Here, we focus on the number of complex-valued
multiplications and assume that the complexity of one real-valued
multiplication equals one-quarter of the complexity of one complex-valued
multiplication. Since the cubic term $N_{r}KM$ (or $G_{r}KM$) is the main
contributor to the computational complexity, the number of complex-valued
multiplications required for these algorithms is similar. Furthermore, the de-
quantization processing of low-quantized signals inevitably causes additional
computational complexity in the SS-GAMP, the OAMP-MMV, and the TS-OAMP
algorithms.

TABLE I: Complexity Analysis

Algorithm | Number of complex-valued multiplications
---|---
SS-GAMP | $(T_{1}+T_{2})\left(4N_{r}KM+20N_{r}K+16N_{r}M+3KM\right)+T_{\text{tur}}N_{r}M(K+1)$
OAMP-MMV | $(T_{1}+T_{2})\left(\frac{37}{4}N_{r}K+4G_{r}KM+G_{r}M+10G_{r}K+\frac{7}{4}G_{r}\right)$
SWOMP | $(T_{1}+T_{2})\left[N_{r}M(K+N_{r})+(T_{1}+T_{2}+1)\left(N_{r}M+M\frac{2(T_{1}+T_{2})+1}{3}+\frac{(T_{1}+T_{2})(T_{1}+T_{2}+1)}{4}\right)\right]$
TS-OAMP | $T_{1}\left[N_{r}(4KM+\frac{77}{4}K+M+\frac{3}{2})+|{\cal H}|_{c}M(K+2)\right]+T_{2}G_{r}\left(3KM+11K+M+\frac{3}{4}\right)$
|

Note: $T_{\text{tur}}$ denotes the iteration number of the SS-GAMP algorithm
[6].

##  IV Simulation Results

In this section, we evaluate the detection performance of the proposed TS-OAMP
algorithm for near-field grant-free massive access. Unless further specified,
the main simulation parameters are set as follows: $N_{r}=512$, $K=500$,
$K_{a}=50$, $\lambda=0.05$ m, $L_{p}=5$, $B=2$, $G_{r}/N_{r}=2$,
$N_{\mathrm{sub}}=2$, $d^{\mathrm{LoS}}_{k,n}\in[10,100]$ m,
$d^{\mathrm{NLoS}}_{k,n,l}\in(10,300)$ m, and $\kappa_{k}=(13-0.03d^{\rm
LoS}_{k,N_{r}/2})$ dB222In this setup, the array length is around $12.8$ m,
which is acceptable according to previous researches on XL-MIMO systems [22,
23].${}^{\text{,}}$333For $2$-bit quantization, we set $r_{0}=-2.22$ and
$r_{2^{B}}=2.22$ in our experiments for computational simplicity and
stability, avoiding the case that infinity times zero. In addition, $d^{\rm
LoS}_{k,N_{r}/2}$ denotes the distance between the $k$-th device and the
$\frac{N_{r}}{2}$-th antenna element at the BS. Since the distance between the
device and the BS can vary dramatically for different antenna elements, we
choose the middle position of the ULA as the representative for power
control.. The large-scale fading is modeled as $\beta_{k,n}=({\lambda}/{4\pi
d^{\rm LoS}_{k,n}})^{2}$, and adaptive power control is assumed at the
devices, i.e., $P_{k}=P_{t}({d^{\rm LoS}_{k,N_{r}/2}}/{100})^{2}$, where
$P_{t}$ is the reference transmit power used by all devices for power control.
Besides, the high-resolution ADCs are uniformly distributed in the extra-large
array with an interval of $\Delta_{\cal H}=32$, i.e., ${\cal
H}=\\{16,48,80,\cdots\\}$. The bandwidth is set to $1$ MHz and the power
spectral density of the background noise is set to $-174$ dBm/Hz. The maximum
numbers of iterations of the proposed algorithm are set to $T_{1}=30$ and
$T_{2}=20$. We adopt the activity error rate (AER) and normalized mean square
error (NMSE) as evaluation metrics

${{\rm
AER}}=\dfrac{1}{K}{{\sum\limits_{k=1}^{K}{\left|{{{\hat{\alpha}}_{k}}-{\alpha_{k}}}\right|}}},\
{\mathrm{NMSE}}={\mathbb{E}}\left[\frac{{\|{\bf H}-{\hat{\bf
H}}\|}^{2}}{{\|{\bf H}\|}^{2}}\right],\vspace{-1mm}$ (12)

where ${\mathbb{E}}[\cdot]$ denotes the expectation operator, and $\hat{\bf
H}$ is the estimated spatial-domain channel. For the proposed algorithm,
$\hat{\bf H}$ can be obtained based on $\hat{\bf X}$ and (9). Additionally, we
compare with the following baseline algorithms:

$\bullet$ SS-GAMP: The SS-GAMP algorithm [6] exploits the common support
structure to directly estimate the spatial-domain channel.

$\bullet$ OAMP-MMV: The OAMP-MMV algorithm [8] utilizes the clustered sparsity
structure and estimates the angular-domain channel, where the de-quantization
module is added.

$\bullet$ SWOMP: The SWOMP algorithm [5] is a variant of the classic OMP
algorithm. It also estimates the spatial-domain channel by exploiting the
common support structure.

Fig. 3 shows the activity detection performance of different JADCE algorithms.
Although mixed-precision quantized signals are adopted for these detection
algorithms, the proposed TS-OAMP algorithm achieves a high activity detection
performance and outperforms the other algorithms due to the more efficient
exploitation of the mixed-ADC architecture.

Figure 3: AER of different JADCE algorithms versus: (a) the length of pilot
sequence $M$ for $P_{t}=5$ dBm; (b) the transmit power $P_{t}$ for $M=56$.

Figure 4: NMSE of different JADCE algorithms versus: (a) the length of pilot
sequence $M$ for $P_{t}=5$ dBm; (b) the transmit power $P_{t}$ for $M=200$.

Figure 5: (a) Gains of the proposed algorithm for the mixed-ADC architecture
and subarray-wise estimation versus $M$; (b) Gains of the proposed algorithm
with subarray-wise estimation versus $N_{r}$.

In Fig. 4, we compare the NMSE performance of different JADCE algorithms. As
can be seen, the OAMP-MMV algorithm and the TS-OAMP algorithm perform better
since they exploit the sparsity of the angular-domain channel. However, the
proposed algorithm significantly outperforms the OAMP-MMV algorithm thanks to
the subarray-wise processing and more efficient utilization of the mixed-ADC
architecture.

Figure 6: NMSE performance of the proposed algorithm versus the distance
between the BS and the devices, $d$, for $M=100$ and $P_{t}=10$ dBm.

Figure 7: Detection performance of the TS-OAMP algorithm versus the number of
high-resolution ADCs $|{\cal H}|_{c}$: (a) AER; (b) NMSE.

Fig. 5 verifies the gain of the proposed algorithm for the mixed-ADC
architecture and for subarray-wise estimation. Without the assistance of high-
resolution ADCs, the detection performance of the TS-OAMP algorithm suffers
even if the two-stage structure and subarray-wise estimation are employed, as
can be observed in Fig. 5(a). Besides, we can observe the benefits of
subarray-wise processing, demonstrating its effectiveness in suppressing the
near-field effects.

The impact of distance on the NMSE performance of the proposed algorithm is
studied in Fig. 6, where the devices are distributed in the range
$d^{\mathrm{LoS}}_{k,n}\in(d-5,d+5)$ m. As can be seen, the benefit of
subarray-wise processing decreases with distance, since the near-field effect
is more pronounced when the devices are closer to the BS. As the distance
increases, the detection performance of both the TS-OAMP algorithm and the TS-
OAMP algorithm without subarray-processing improves due to the weakening of
the near-field effect.

In Fig. 7, we investigate the detection performance of the TS-OAMP algorithm
as a function of the number of high-resolution ADCs $|{\cal H}|_{c}$ in the
mixed-ADC architecture. Generally, the detection performance of the TS-OAMP
algorithm improves as $|{\cal H}|_{c}$ increases, and the TS-OAMP algorithm
employing only high-resolution ADCs and only low-resolution ADCs has the best
and worst detection performance, respectively. Moreover, Fig. 7 shows that a
small number of high-resolution ADCs can significantly enhance the detection
performance compared to the case with only low-resolution ADCs, which verifies
the effectiveness of the mixed-ADC architecture in our proposed scheme.

##  V Conclusions

In this paper, we proposed a TS-OAMP algorithm to solve the JADCE problem for
massive connectivity based on mixed-ADC XL-MIMO over near-field channels. In
the first stage, the activity detection relied on the common support structure
of spatial-domain channels and the accurate hyper-parameter estimation from
high-precision measurements. Next, the sparse angular-domain channel was
estimated based on the intermediate results of the previous stage, where the
near-field effect of the XL-MIMO channels was mitigated by subarray-wise
processing. Numerical results verified that our proposed algorithm performs
remarkably well facilitating near-field massive access in XL-MIMO systems. In
future work, the proposed schemes can be extended to multi-carrier systems to
enhance the range of possible applications.

## References

  * [1] N. H. Mahmood, et al., “White paper on critical and massive machine type communication towards 6G,” [Online]. Available:arXiv:2004.14146, 2020.
  * [2] J. Zhao, J. Liu, L. Yang, B. Ai, and S. Ni, “Future 5G-oriented system for urban rail transit: Opportunities and challenges,” China Commun., vol. 18, no. 2, pp. 1-12, Feb. 2021.
  * [3] X. Chen, D. W. K. Ng, W. Yu, E. G. Larsson, N. Al-Dhahir, and R. Schober, “Massive access for 5G and beyond,” IEEE J. Sel. Areas Commun., vol. 39, no. 3, pp. 615-637, Mar. 2021.
  * [4] H. Xiao, et al., “A grant-free method for massive machine-type communication with backward activity level estimation,” IEEE Trans. Signal Process., vol. 68, pp. 6665-6680, Nov. 2020.
  * [5] M. Ke, et al., “Compressive sensing-based adaptive active user detection and channel estimation: Massive access meets massive MIMO,” IEEE Trans. Signal Process., vol. 68, pp. 764-779, Jan. 2020.
  * [6] M. Ke, et al., “Massive access in cell-free massive MIMO-based internet of things: Cloud computing and edge computing paradigms,” IEEE J. Sel. Areas Commun., vol. 39, no. 3, pp. 756-772, Mar. 2021.
  * [7] X. Shao, X. Chen, C. Zhong, and Z. Zhang, “Exploiting simultaneous low-rank and sparsity in delay-angular domain for millimeter-wave/terahertz wideband massive access,” IEEE Trans. Wireless Commun., vol. 21, no. 4, pp. 2336-2351, Apr. 2022.
  * [8] Y. Mei, et al., “Compressive sensing based joint activity and data detection for grant-free massive IoT access,” IEEE Trans. Wireless Commun., vol. 21, no. 3, pp. 1851-1869, Mar. 2022.
  * [9] X. Wei and L. Dai, “Channel estimation for extremely large-scale massive MIMO: Far-field, near-field, or hybrid-field?” IEEE Commun. Lett., vol. 26, no. 1, pp. 177-181, Jan. 2022.
  * [10] M. Cui and L. Dai, “Channel estimation for extremely large-scale MIMO: Far-field or near-field?” IEEE Trans. Commun., vol. 70, no. 4, pp. 2663-2677, Apr. 2022.
  * [11] Y. Han, S. Jin, C. Wen, and X. Ma, “Channel estimation for extremely large-scale massive MIMO systems,” IEEE Wireless Commun. Lett., vol. 9, no. 5, pp. 633-637, Jan. 2020.
  * [12] J. Mo, P. Schniter, and R. W. Heath, “Channel estimation in broadband millimeter wave MIMO systems with few-bit ADCs,” IEEE Trans. Signal Process., vol. 66, no. 5, pp. 1141-1154, Mar. 2018.
  * [13] Y. Han, S. Jin, C. Wen, and X. Ma, “Bayes-optimal joint channel-and-data estimation for massive MIMO with low-precision ADCs,” IEEE Trans. Signal Process., vol. 64, no. 10, pp. 2541-2556, May 2016.
  * [14] N. Liang and W. Zhang, “Mixed-ADC massive MIMO,” IEEE J. Sel. Areas Commun., vol. 34, no. 4, pp. 983-997, Apr. 2016.
  * [15] T. Liu, S. Jin, C. Wen, M. Matthaiou, and X. You, “Generalized channel estimation and user detection for massive connectivity with mixed-ADC massive MIMO,” IEEE Trans. Wireless Commun., vol. 18, no. 6, pp. 3236-3250, June 2019.
  * [16] D. Verenzuela, E. Björnson, and M. Matthaiou, “Optimal per-antenna ADC bit allocation in correlated and cell-free massive MIMO,” IEEE Trans. Commun., vol. 69, no. 7, pp. 4767-4780, July 2021.
  * [17] Z. Gao, C. Zhang, and Z. Wang, “Robust preamble design for synchronization, signaling transmission, and channel estimation,” IEEE Trans. Broadcast. vol. 61, no. 1, pp. 98-104, Mar. 2015.
  * [18] 3GPP TS 38.901 V16.1.0, “Study on channel model for frequencies from 0.5 to 100 GHz,” Dec. 2019.
  * [19] H. He, et al., “Bayesian optimal data detector for hybrid mmWave MIMO-OFDM systems with low-resolution ADCs,” IEEE J. Sel. Top. Signal Process., vol. 12, no. 3, pp. 469-483, June 2018.
  * [20] J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020-2033, 2017.
  * [21] S. Rangan, P. Schniter, A. K. Fletcher, and S. Sarkar, “On the convergence of approximate message passing with arbitrary matrices,” IEEE Trans. Inf. Theory, vol. 65, no. 9, pp. 5339-5351, Sept. 2019.
  * [22] Z. H. Shaik, E. Björnson, and E. G. Larsson, “MMSE-optimal sequential processing for cell-free massive MIMO with radio stripes,” IEEE Trans. Commun., vol. 69, no. 11, pp. 7775-7789, Nov. 2021.
  * [23] Z. Dong and Y. Zeng, “Near-field spatial correlation for extremely large-scale array communications,” IEEE Commun. Lett., vol. 26, no. 7, pp. 1534-1538, July 2022.


was large, capped at 1 once, and reach the advice value once. Hence, Algorithm
7 has $O(n\log s\log\frac{c^{T}x}{\alpha(1)})$ iterations. ∎

##  4 Empirical Evaluations

We demonstrate the applicability of our algorithmic framework on a synthetic
dataset as well as a real world case study on internet router graphs. Our
focus will be on evaluating our online covering algorithms, Algorithms 1 and
2, with possibly fractional hints and fractional entries. We focus on this
setting since it’s the simplest of our algorithms and already captures our
overall algorithm framework. Note that prior work in [BMS20] has already
demonstrated the empirical advantage of learning-based methods for online
covering with integral hints and constraints, albeit on synthetic datasets.

##### Datasets.

Our synthetic dataset is constructed as follows. The constraint matrix $A$
represents a $n\times n$ matrix where each entry is uniformly in $\\{0,1\\}$.
We set $n=500$. The objective function $c$ is a scaled vector with entries
uniform in $[0,1]$. The vector we are covering is the all ones vector, i.e.,
we are solving $Ax\geq\mathbf{1}$, and the rows of $A$ arrive online. Our
graph dataset is constructed as follows. We have a sequence of nine
(unweighted) graphs which represents an internet router network sampled across
time [LK14, LKF05]444Graphs can be accessed in
https://snap.stanford.edu/data/Oregon-1.html. The graphs have approximately
$n\sim 10^{4}$ nodes and $m\sim 2.2\cdot 10^{4}$ edges. We note that the nodes
of the graphs are labeled and the labeling is consistent throughout the
different time stamps. Each graph defines an instance of the set cover problem
derived from vertex cover as follows. The edges of the graphs are labeled and
the $n$ vertex neighborhoods define $n$ sets. The edges of the graph (the
universe elements) appear online and we must cover these edges by choosing
vertices (the sets) which are incident on them. The objective function $c$
will be the same as the synthetic case so our problem represents an instance
of weighted vertex cover.

##### Predictions.

We instantiate predictions in a variety of ways, drawing inspiration from many
prior works[BMS20, DIL+21, CSVZ22]. First we describe our predictions for the
synthetic datasets. We consider two types of predictions. In one case, we
first find the optimal offline solution $x$ by solving the full linear
program. We then noisy corrupt the entries of $x$ by setting the entries to be
$0$ independently with some probability $p$. This is the same type of
predictions in [BMS20] which they refer to as the ‘replacement rate’ strategy.

The second type of predictions are informed by the following motivating
setting of learning-augmented algorithms: we are solving many different, but
related, problem instances. To mimic this situation, we have matrices
$A_{0},A_{1},\ldots$ where each index represents a new problem instance.
$A_{0}$ is our synthetic matrix and $A_{i+1}$ updates $A_{i}$ by flipping $n$
entries at random. We fix $c$ to be the same throughout. The predictions for
all instances $i\geq 1$ are given by the optimal offline solution generated
from the first instance $A_{0}$. This “batch” experimental design naturally
models the scenario where the current problem instance is similar to past
instances and so one can hope to utilize past learned information to improve
current algorithmic performance. A similar style of predictions, although not
in an online context, has been employed in [CEI+22, EFS+22, DIL+21, CSVZ22].
Furthermore, this mimics the setting for proving PAC learning bounds.

For our graph dataset, we first solve the set cover instance on the first
graph in the family using an offline linear program solver. We then use the
solution from the first graph as the hint for all subsequent graphs. We also
noisy alter this hint for one of our experiments using the replacement rate
strategy. Note that the set of vertices might vary across graphs since new
vertices can appear in the network while older vertices may be removed. In
this case, we set the corresponding entry in the hint vector to be $0$.

The type of dataset and predictions used will always be stated explicitly in
our experimental results below.

##### Results.

Our results are shown in Figures 2 and 3. Figure 2 shows the results on the
synthetic dataset while Figure 3 refers to our graph dataset. Description of
each figure follows.

In Figure 2(a), we consider a single online instance of the synthetic dataset.
Our prediction is the offline optimal solution. The figure shows a smooth
trade-off in the competitive ratio as the parameter $\lambda$ ranges from $0$
(full trust in the predictions) to $1$ (standard online algorithm with no
hints), as predicted by our theoretical bounds. Since the instance is random,
we plot the average of $20$ trials for each setting of $\lambda$ and also
shade in one standard deviation. The plot validates the consistency of our
algorithms as the competitive ratio is a factor of two lower with accurate
predictions.

In Figure 2(b), we again consider a single synthetic instance. This time, we
consider the “replacement rate” strategy and randomly zero out the entries of
the prediction (which is again the offline optimum) independently. The
expected fraction of entries in the hint vector being set to zero is denoted
as the corruption rate and is shown in the $x$-axis. We see that for a fixed
setting of $\lambda$, such as $\lambda=0.1$, our algorithm performs much
better than not utilizing any hints when the corruption factor is low. This
intuitively makes sense and is exactly what Figure 2(a) shows. However, as we
increase the corruption factor, the performance of the algorithm degrades.
Crucially, the performance _does not_ degrade arbitrarily worse compared to
$\lambda=1$ (no hints) performance, which empirically validates the robustness
of our algorithm. Indeed, our algorithm with hints is able to outperform the
baseline even up to a high corruption factor. Lastly, if we utilize hints in a
naive way where we only scale the hint variables to satisfy the constraints,
then the competitive ratio is at least four orders of magnitude larger than
the values in Figure 2(b). Thus, post-processing the hints, such as what our
algorithm does, is crucial.

In Figure 2(c), we consider a “batch” experimental design for our synthetic
dataset with $20$ time steps. The green curve shows the competitive ratio
without using any hints, i.e., $\lambda$ is set to $1$ (the baseline). The
orange curve shows the competitive ratio across the varying instances when we
use a batch prediction. Precisely, this means we use the optimal offline
solution of the _first_ instance and this hint is fixed for all future
instances which noisily drift away from the first instance. The blue curve
showcases more powerful predictions where the offline optimal of time step
$t-1$ is used as the hint for time step $t$. We display the average values
across $20$ instances. We see that as the time step increases, the orange
curve drifts upwards, which is intuitive as the problem instances are
increasingly different. Nevertheless, the hint stays valid for many time steps
as the orange curve is still below the green baseline even after many time
steps. As expected, the blue curve consistently has the lowest competitive
ratio as the hints are also updated. We do not shade in the standard deviation
to increase the clarity of the figure but the variance of the curves similar
to Figure 2(a).

(a)

(b)

(c)

Figure 2: Figures for our synthetic dataset.

(a)

(b)

Figure 3: Figures for our time-varying graph dataset.

We now describe the experimental results on our graph dataset. In Figure 3(a),
the green curve represents not using any hints (baseline) while the orange
curve shows the competitive ratio as we vary the graph instance while using
the hint derived from graph $\\#1$ ($\lambda$ is set to $0.1$). It is shown
that the hints help outperform the baseline and in addition, the hints stay
accurate even if the structure of graph $\\#9$ has drifted away from that of
graph $\\#1$. The online predictions, shown in blue, does marginally better
than the batch version.

Figure 3(b) shows a similar plot as Figure 2(b). We consider a replacement
rate strategy where we zero out coordinates of the hint vector independently
with varying probabilities. The curve shows the average of $5$ trials and
$\lambda=0.1$ again. The same qualitative message as Figure 2(b) holds: while
the corruption rate is small, we achieve a similar competitive ratio as in
Figure 3(a) and as the corruption rate increases, there is a smooth increase
in the competitive ratio.

In addition to extending and complementing the experimental results of
[BMS20], we summarize our experimental results in the following points: (a)
Our theory is predictive of experimental performance and qualitatively
validates our robustness and consistency trade offs. (b) Our algorithm
framework which underlies all of our algorithm contributions is efficient to
carry out and execute in practice. (c) Learning-augmented online algorithms
can be applied to real world datasets varying over time such as in the
analysis of graphs derived from a dynamic network.

##  5 Conclusion

We present the first framework for the learning-augmented online covering LP
and SDP problem. As shown in table 1, for the problems without box
constraints, our algorithms are $O(1/(1-\lambda)))$-consistent and
$O(\log(\kappa n/\lambda))$-robust; for the problems with box constraints, our
algorithms are $O(1/(1-\lambda)))$-consistent and $O(\log(s/\lambda))$-robust.
Our algorithms not only support fractional advice but also update the
variables efficiently. Our work raises several open questions.

First, for the problem without box constraints, is it possible to remove the
dependency on the condition number $\kappa$ in the robustness ratio? The
competitive ratio of the optimal online algorithms for covering LPs [BN09a]
and SDPs [EKN16] is $O(\log n)$. For the learning-augmented set cover problem
where the entries in the constraint matrix are zeros and ones, the robustness
ratio is $O(\log(d/\lambda))$, where the worst case for $d$ is $d=n$. It seems
that the condition number arises due to additive term $D_{j}$ used for the
growth rate. Another direction is to discover the trader-off lower bounds
between the robustness and consistency ratio for the online covering and SDP
covering problem as in [WZ20] for the ski rental and the non-clairvoyant
scheduling problem.

Next, our technique can potentially be used on other online covering problems
[ABC+16, SN20, GN14] for the learning-augmented extension. It would be
exciting to see if the primal-dual continuous augmentation approach with well-
selected growth rates can be employed for these problems.

As stated in [BMS20], another natural future direction is to design PDLA
algorithms for packing LPs. For general online packing LPs, an
$O(1/\log\kappa)$-competitive online solution can be obtained only if a
condition number $\kappa$ is known offline [BN09b], implying impossibility
results without assumptions. The hope here is to study structured packing
problems, e.g., load balancing [BN09a] and ad-auction revenue maximization
[BJN07].

## Acknowledgment

We thank Roie Levin for bringing to our attention the significantly simpler
algorithm described in Appendix B.

## References

  * [AAA+06] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor.  A general approach to online network optimization problems.  ACM Transactions on Algorithms (TALG), 2(4):640–660, 2006.
  * [AAA+09] Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor.  The online set cover problem.  SIAM Journal on Computing, 39(2):361–370, 2009.
  * [AB99] Martin Anthony and Peter L. Bartlett.  Neural Network Learning: Theoretical Foundations.  Cambridge University Press, 1999.
  * [ABC+16] Yossi Azar, Niv Buchbinder, TH Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, et al.  Online algorithms for covering and packing problems with convex objectives.  In 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 148–157, 2016.
  * [ABFP13] Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi.  Online mixed packing and covering.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 85–100, 2013.
  * [ACE+20] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In International Conference on Machine Learning, pages 345–355. PMLR, 2020.
  * [AGKK20] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  Advances in Neural Information Processing Systems, 33:7933–7944, 2020.
  * [AGKP22] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi.  Online algorithms with multiple predictions, 2022.
  * [APT22] Yossi Azar, Debmalya Panigrahi, and Noam Touitou.  Online graph algorithms with predictions.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35–66. SIAM, 2022.
  * [AW02] Rudolf Ahlswede and Andreas Winter.  Strong converse for identification via quantum channels.  IEEE Transactions on Information Theory, 48(3):569–579, 2002.
  * [BBN12] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  A primal-dual randomized algorithm for weighted paging.  Journal of the ACM (JACM), 59(4):1–24, 2012.
  * [BJN07] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor.  Online primal-dual algorithms for maximizing ad-auctions revenue.  In European Symposium on Algorithms, pages 253–264. Springer, 2007\.
  * [BMRS20] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson.  Learning augmented energy minimization via speed scaling.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
  * [BMS20] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
  * [BN09a] Niv Buchbinder and Joseph Naor.  The design of competitive online algorithms via a primal-dual approach.  Found. Trends Theor. Comput. Sci., 3(2-3):93–263, 2009.
  * [BN09b] Niv Buchbinder and Joseph Naor.  Online primal-dual algorithms for covering and packing.  Mathematics of Operations Research, 34(2):270–286, 2009.
  * [CEI+22] Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang.  Triangle and four cycle counting with predictions in graph streams.  In The Tenth International Conference on Learning Representations, ICLR, 2022.
  * [CSVZ22] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang.  Faster fundamental graph algorithms via learned predictions.  In International Conference on Machine Learning, ICML, pages 3583–3602, 2022.
  * [DIL+21] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Faster matchings via learned duals.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pages 10393–10406, 2021.
  * [DIRW20] Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, and Tal Wagner.  Learning space partitions for nearest neighbor search.  In 8th International Conference on Learning Representations, ICLR, 2020, 2020.
  * [DKT+21] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis.  Learning online algorithms with distributional advice.  In Proceedings of the 38th International Conference on Machine Learning, ICML, pages 2687–2696, 2021.
  * [EFS+22] Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou.  Learning-augmented $k$-means clustering.  In The Tenth International Conference on Learning Representations, ICLR, 2022.
  * [EIN+21] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner.  Learning-based support estimation in sublinear time.  In 9th International Conference on Learning Representations, ICLR, 2021.
  * [EKN16] Noa Elad, Satyen Kale, and Joseph (Seffi) Naor.  Online semidefinite programming.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, pages 40:1–40:13, 2016.
  * [FMMM09] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan.  Online stochastic matching: Beating 1-1/e.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117–126. IEEE, 2009.
  * [GKR00] Naveen Garg, Goran Konjevod, and Ramamoorthi Ravi.  A polylogarithmic approximation algorithm for the group steiner tree problem.  Journal of Algorithms, 37(1):66–84, 2000.
  * [GL20] Anupam Gupta and Roie Levin.  The online submodular cover problem.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1525–1537. SIAM, 2020.
  * [GLQ21] Elena Grigorescu, Young-San Lin, and Kent Quanrud.  Online directed spanners and steiner forests.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), 2021.
  * [GN14] Anupam Gupta and Viswanath Nagarajan.  Approximating sparse covering integer programs online.  Mathematics of Operations Research, 39(4):998–1011, 2014.
  * [GP19] Sreenivas Gollapudi and Debmalya Panigrahi.  Online algorithms for rent-or-buy with expert advice.  In Proceedings of the 36th International Conference on Machine Learning, ICML, pages 2319–2327, 2019.
  * [GW95] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  J. ACM, 42(6):1115–1145, 1995.
  * [HIKV19] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian.  Learning-based frequency estimation algorithms.  In 7th International Conference on Learning Representations, ICLR, 2019.
  * [ISZ21] Zachary Izzo, Sandeep Silwal, and Samson Zhou.  Dimensionality reduction for wasserstein barycenter.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS, pages 15582–15594, 2021.
  * [JLL+20] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff.  Learning-augmented data stream algorithms.  In 8th International Conference on Learning Representations, ICLR, 2020.
  * [KDZ+17] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs.  Advances in neural information processing systems, 30, 2017.
  * [KMMO94] Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan S. Owicki.  Competitive randomized algorithms for non-uniform problems.  Algorithmica, 11(6):542–571, 1994.
  * [LFKF18] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman.  Training gaussian mixture models at scale via coresets.  Journal of Machine Learning Research, 18(160):1–25, 2018.
  * [LK14] Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * [LKF05] Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos.  Graphs over time: densification laws, shrinking diameters and possible explanations.  In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 177–187, 2005.
  * [LLMV20] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1859–1877, 2020.
  * [LV18] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  In Proceedings of the 35th International Conference on Machine Learning, ICML, pages 3302–3311, 2018.
  * [Mit18] Michael Mitzenmacher.  A model for learned bloom filters and optimizing by sandwiching.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, pages 462–471, 2018.
  * [MNS12] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi.  Online optimization with uncertain information.  ACM Transactions on Algorithms (TALG), 8(1):1–29, 2012.
  * [ND21] Kim Thang Nguyen and Christoph Dürr.  Online primal-dual algorithms with predictions for packing problems.  CoRR, abs/2110.00391, 2021.
  * [PSK18] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ML predictions.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, pages 9684–9693, 2018.
  * [Roh20] Dhruv Rohatgi.  Near-optimal bounds for online caching with machine learned advice.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1834–1845, 2020.
  * [SN20] Xiangkun Shen and Viswanath Nagarajan.  Online covering with $l_{q}$-norm objectives and applications to network design.  Mathematical Programming, 184, 2020.
  * [SZS+14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In 2nd International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2014.
  * [VB96] Lieven Vandenberghe and Stephen P. Boyd.  Semidefinite programming.  SIAM Rev., 38(1):49–95, 1996.
  * [WX06] Avi Wigderson and David Xiao.  Derandomizing the aw matrix-valued chernoff bound using pessimistic estimators and applications.  ECCC TR06-105, 2006.
  * [WZ20] Alexander Wei and Fred Zhang.  Optimal robustness-consistency trade-offs for learning-augmented online algorithms.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS, 2020.

##  Appendix A Learnability of Predictor

In this section, we present formal learning bounds for learning a good
predictor for the covering formulation of online semidefinite programming,
which includes learning a good predictor for online fractional linear
programming. Specifically, we prove that a good predictor can be efficiently
learned if the problem instances are drawn from a particular distribution, in
the style of the probably approximately correct (PAC) learning framework for
data-driven algorithm design. Similar ideas were used by [EFS+22, ISZ21,
CEI+22, CSVZ22] to show efficient learners for predictors for $k$-means
clustering and triangle counting. Thus while the results of this section use
ideas of prior papers, they are still meaningful as it provides an “end-to-
end” recipe for designing learning-augmented online algorithms. The prior part
of this paper designs online algorithms which leverage predictions and thus,
the natural follow up questions are how efficiently one can learn these hint
from data. Therefore this learnability section precisely addresses these
questions and makes our results complete.

Suppose there exists an underlying distribution $\mathcal{D}$ that generates
independent covering semidefinite programming or covering linear program
instances, capturing the case where similar problem instances are being
solved. Note that this setting also mirrors some of our experiments,
specifically in the case of our online covering datasets which are derived
from an underlying dataset (an internet router graph), sampled across time. We
would like to efficiently learn a good predictor $f$ from a family of
functions $\mathcal{F}$, where the input to $f$ is an covering SDP
$\mathcal{S}$ and the output is a weight vector. Each covering SDP instance
can be written in terms of $d:=O(nm^{2})$ variables, so we assume that each
input instance $\mathcal{S}$ is encoded as a vector in $\mathbb{R}^{d}$. The
output of $f$ is then an $n$-dimensional vector, so that each coordinate
$i\in[n]$ represents the associated weight of the matrix $A_{i}$ selected in
the covering SDP.

To quantify the quality of each function $f$, we consider a loss function
$L:f\times\mathcal{S}\rightarrow\mathbb{R}$ that outputs the cost of
corresponding SDP cover. For example, $f$ can output a set of matrix weights
given an instance $\mathcal{S}$. If the matrix weights are not feasible, then
the loss function may output $\infty$. Otherwise if the matrix weights are
feasible, then the loss function may output the corresponding cost, defined by
the cost vector that is also given in $\mathcal{S}$.

We would like to learn the best function $f\in\mathcal{F}$ that minimizes the
objective:

$\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[L(f,\mathcal{S})].$ (21)

Let $f^{*}$ denote the minimizer of the above objective, i.e., the optimal
function in $\mathcal{F}$, so that

$f^{*}=\operatorname{argmin}\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[L(f,\mathcal{S})].$

We assume that for each SDP instance $\mathcal{S}$ and each $f\in\mathcal{F}$
that $f(\mathcal{S})$ and $L(f,\mathcal{S})$ can be computed in time that is a
(small) polynomial in $n$ and $d$, which we denote by $T(n,d)$.

We show that there exists an efficient algorithm that outputs a function
$\hat{f}\in\mathcal{F}$ whose loss is within an additive $\varepsilon$ of the
loss of the optimal function $f^{*}$.

######  Theorem A.1.

There exists an algorithm that uses
$\operatorname{poly}\left(T(n,d),\frac{1}{\varepsilon}\right)$ samples and
outputs a function $\hat{f}$ that satisfies with probability at least
$\frac{9}{10}$,

$\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[L(\hat{f},\mathcal{S})]\leq\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[L(f^{*},\mathcal{S})]+\varepsilon,$

where
$f^{*}=\operatorname{argmin}\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[L(f,\mathcal{S})]$.

Theorem A.1 shows that only a small number of samples are needed to have a
good probability of learning an approximately-optimal function $\hat{f}$, in a
typical PAC-style bound. Specifically, the algorithm to compute $\hat{f}$ is
simply the empirical risk minimizer, i.e., the algorithm minimizes the
empirical loss after an appropriate number of samples are drawn. To prove
correctness of Theorem A.1, we first define the notion of pseudo-dimension for
a function class, which generalizes the more familiar VC dimension to real
functions, e.g., Definition $9$ in [LFKF18].

######  Definition A.2 (Pseudo-Dimension).

Let $\mathcal{X}$ be a ground set and $\mathcal{F}$ be a set of functions from
$\mathcal{X}$ to the interval $[0,1]$. Let
$U=\\{x_{1},\cdots,x_{n}\\}\subset\mathcal{X}$ be a fixed set,
$R=\\{r_{1},\cdots,r_{n}\\}$ be a fixed set of real numbers with
$r_{i}\in[0,1]$ for all $i\in[n]$, and $f\in\mathcal{F}$ be a fixed function.
The set $U_{f}=\\{x_{i}\in U\mid f(x_{i})\geq r_{i}\\}$ is called the induced
subset of $U$ formed by $f$ and $R$. The set $U$ with associated values $R$ is
shattered by $\mathcal{F}$ if $|\\{U_{f}\mid f\in\mathcal{F}\\}|=2^{n}$. The
_pseudo-dimension_ of $\mathcal{F}$ is the cardinality of the largest
shattered subset of $\mathcal{X}$ (or $\infty$).

Let $\mathcal{G}$ be the class of functions in $\mathcal{F}$ composed with
$L$, so that

$\mathcal{G}:=\\{L\circ f:f\in\mathcal{F}\\}.$

Without loss of generality, we normalize the range of the loss function $L$ to
$[0,1]$. Then the performance of the empirical risk minimization and the
number of necessary samples can be related to the pseudo-dimension using
standard bounds as follows:

######  Theorem A.3.

[AB99] Let $\mathcal{D}$ be a distribution over problem instances
$\mathcal{S}$ and $\mathcal{G}$ be a class of functions
$g:\mathcal{S}\rightarrow[0,1]$ with pseudo-dimension $d_{\mathcal{G}}$.
Consider $t$ i.i.d. samples
$\mathcal{S}_{1},\mathcal{S}_{2},\ldots,\mathcal{S}_{t}$ from $\mathcal{D}$.
There exists a universal constant $C$, such that for any $\varepsilon>0$, if
$t\geq\frac{C\cdot d_{\mathcal{G}}}{\varepsilon^{2}}$, then with probability
at least $\frac{9}{10}$,

$\left|\frac{1}{t}\sum_{i=1}^{t}g\left(\mathcal{S}_{i}\right)-\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}\,g(\mathcal{S})\right|\leq\varepsilon$

for all $g\in\mathcal{G}$.

From the triangle inequality, we then have the following corollary.

######  Corollary A.4.

Let $t\geq\frac{C\cdot d_{\mathcal{G}}}{\varepsilon^{2}}$, where $C$ is the
universal constant from Theorem A.3. Consider a set of $t$ independent samples
$\mathcal{S}_{1},\ldots,\mathcal{S}_{t}$ from $\mathcal{D}$ and let $\hat{g}$
be a function in $\mathcal{G}$ that minimizes
$\frac{1}{t}\sum_{i=1}^{t}g(\mathcal{S}_{i})$. Then with probability at least
$\frac{9}{10}$,

$\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[\hat{g}(\mathcal{S})]\leq\mathbb{E}_{\mathcal{S}\sim\mathcal{D}}[g^{*}(\mathcal{S})]+2\varepsilon.$

Hence, the main question is whether we can bound the pseudo-dimension of the
given function class $\mathcal{G}$. To that end, we first observe that the
pseudo-dimension can be related to the VC dimension of a related class of
threshold functions. In particular, this relationship has been instrumental in
showing a number of existing learning bounds, e.g., [LFKF18, ISZ21, EFS+22,
CEI+22, CSVZ22].

######  Lemma A.5 (Pseudo-dimension to VC dimension, Lemma $10$ in [LFKF18]).

For any $g\in\mathcal{G}$, let $B_{g}(x,y)=\text{sgn}(g(x)-y)$, i.e., the
indicator function of the region on or below the graph of $g$. Then the
pseudo-dimension of $\mathcal{G}$ is equivalent to the VC dimension of the
subgraph class $B_{\mathcal{G}}=\\{B_{g}\mid g\in\mathcal{G}\\}$.

We can also relate the VC dimension of a given function class to the
computational complexity of the function class, i.e., the time complexity of
computing a function in the class.

######  Lemma A.6 (Theorem 8.14 in [AB99]).

Let $h:\mathbb{R}^{a}\times\mathbb{R}^{b}\rightarrow\\{0,1\\}$ define the
class

$\mathcal{H}=\\{x\rightarrow h(\theta,x):\theta\in\mathbb{R}^{a}\\}.$

Suppose that $h$ can be computed by an algorithm that takes as input the pair
$(\theta,x)\in\mathbb{R}^{a}\times\mathbb{R}^{b}$ and returns $h(\theta,x)$
after no more than $t$ of the following operations:

  * •

arithmetic operations $+,-,\times,$ and $/$ on real numbers,

  * •

jumps conditioned on $>,\geq,<,\leq,=,$ and $=$ comparisons of real numbers,
and

  * •

output $0,1$.

Then the VC dimension of $\mathcal{H}$ is at most $O(a^{2}t^{2}+t^{2}a\log
a)$.

We can now prove Theorem A.1 by roughly instantiating Lemma A.6 using the
computational complexity of any function in the function class $\mathcal{G}$.

###### Proof of Theorem A.1.

The proof essentially follows from the proofs of similar theorems in the
sample complexity bound sections of the papers [LFKF18, ISZ21, EFS+22, CEI+22,
CSVZ22] but we nonetheless repeat it here for completeness. By Theorem A.3 and
Corollary A.4, we observe that it suffices to bound the pseudo-dimension of
the class $\mathcal{G}=L\circ\mathcal{F}$. By Lemma A.5, the pseudo-dimension
of $\mathcal{G}$ is equivalent to the VC dimension of threshold functions
defined by $\mathcal{G}$. Moreover by Lemma A.6, the VC dimension of the
threshold functions defined by $\mathcal{G}$ is polynomial in the complexity
of computing a member of the function class.

Hence, Lemma A.6 implies that the VC dimension of $B_{\mathcal{G}}$ defined in
Lemma A.5 is polynomial in the number of arithmetic operations needed to
compute the threshold function associated to some $g\in\mathcal{G}$, which is
polynomial in $T(n,d)$ by our definition. Therefore, the pseudo-dimension of
$\mathcal{G}$ is also polynomial in $T(n,d)$ and the desired claim follows. ∎

##  Appendix B A Simple Learning-Augmented Online Algorithm

In this section, we revisit a simple and possibly folklore learning-augmented
online algorithm for online covering LPs. Its robustness ratio is
asymptotically as good as the state-of-the-art online algorithm and its
consistency ratio is also asymptotically as good as the advice if the advice
is feasible. We recall that a similar approach also applies to a wide range of
learning-augmented online minimization problems, including online SDPs, online
LPs and SDPs with box constraints, online submodular cover [GL20], and online
covering with $\ell_{q}$-norm objectives [SN20].

The idea of the algorithm is to maintain two candidate solutions, the advice
$x^{\prime}$ and the solution obtained by a state-of-the-art online algorithm
[GN14]. Let $\mathcal{O}$ be a state-of-the-art online algorithm and let
$x^{(i)}$ be its solution obtained at round $i$. In the beginning, $x^{(0)}$
is initialized according to the online algorithm $\mathcal{O}$. We follow the
online algorithm $\mathcal{O}$ until its objective $c^{T}x^{(i)}$ is larger
than the objective of the advice $c^{T}x^{\prime}$. Once the advice is
infeasible, we ignore the advice and use the online algorithm. Transitioning
either from the online algorithm to the advice or from the advice to the
online algorithm pays only a constant factor. Once we transition, to maintain
monotonicity of the online solution, we pick the coordinate-wise maximum
between the advice and the solution by $\mathcal{O}$. The algorithm works as
follows.

Algorithm 9 A Simple Algorithm for Learning-Augmented Online Covering LPs

1:$i_{a}\leftarrow\infty$. $\triangleright$ $i_{a}$ is the round that we
transition to the advice

2:for $i=1,2,...$ do $\triangleright$ each arriving row or constraint

3: Update $A$ by adding a new row $i$.

4: Run $\mathcal{O}$ for round $i$ and obtain $x^{(i)}$.

5: if $Ax^{\prime}\geq\mathbf{1}$ and $c^{T}x^{\prime}\geq c^{T}x^{(i)}$ then
$\triangleright$ use the online solution

6: $x\leftarrow x^{(i)}$.

7: if $Ax^{\prime}\geq\mathbf{1}$ and $c^{T}x^{\prime}<c^{T}x^{(i)}$ and
$i<i_{a}$ then $\triangleright$ transition to the advice

8: $i_{a}\leftarrow i$. $\triangleright$ (only once at round $i_{a}$)

9: for $j\in[n]$ do

10: $x_{j}\leftarrow\max\\{x^{\prime}_{j},x^{(i-1)}_{j}\\}$.

11: if $Ax^{\prime}\geq\mathbf{1}$ does not hold then $\triangleright$ use
only the online solution

12: if $i<i_{a}$ then $\triangleright$ no transition to advice

13: $x\leftarrow x^{(i)}$.

14: if $i\geq i_{a}$ then $\triangleright$ has transitioned to advice

15: for $j\in[n]$ do $\triangleright$ transition back to the online solution

16: $x_{j}\leftarrow\max\\{x^{\prime}_{j},x^{(i)}_{j}\\}$.

######  Theorem B.1.

For the learning-augmented online covering LP problem, there exists an online
algorithm that generates $x$ such that

$c^{T}x\leq\min\\{O(c^{T}x^{\prime}),O(\log k)\textsf{OPT}\\}$

when $x^{\prime}$ is feasible, and $c^{T}x\leq O(\log k)\textsf{OPT}$ when
$x^{\prime}$ is infeasible. Here, $k\leq n$ is the row sparsity of $A$, i.e.,
the maximum number of non-zero entries of each row.

###### Proof.

We use Algorithm 9 with the $O(\log k)$-competitive online algorithm for
$\mathcal{O}$.

######  Theorem B.2 ([GN14]).

There exists an $O(\log k)$-competitive algorithm for the online covering LP
problem.

Algorithm 9 considers four possible cases.

  1. 1.

The advice is feasible but $\mathcal{O}$ is better (line 5).

  2. 2.

The advice is feasible and it is better than $\mathcal{O}$ (line 7 or $x$ is
not updated).

  3. 3.

The advice is infeasible and never used (line 12).

  4. 4.

The advice is infeasible and was used when it was feasible (line 14).

Clearly, Algorithm 9 always returns a feasible solution $x$ and $x$ is updated
in a non-decreasing manner.

We first consider the case when $x^{\prime}$ is feasible. For the first case,
we never use the advice, so

$c^{T}x\leq O(\log k)\textsf{OPT}\leq\min\\{O(c^{T}x^{\prime}),O(\log
k)\textsf{OPT}\\}.$

For the second case, either the advice becomes better than the online solution
at round $i$ or $x$ is not updated because the advice becomes better than the
online solution at a previous round $i_{a}<i$. For the previous case, by the
design of Algorithm 9, we have that

$c^{T}x\leq c^{T}(x^{\prime}+x^{(i-1)})\leq
2c^{T}x^{\prime}\leq\min\\{O(c^{T}x^{\prime}),O(\log k)\textsf{OPT}\\}.$

For the later case, $x$ is not updated after round $i_{a}$ so the claim still
holds.

The remaining cases are when $x^{\prime}$ is infeasible. For the third case,
we never use the advice, so $c^{T}x\leq O(\log k)\textsf{OPT}$. For the last
case, let $\textsf{OPT}_{i}$ denote the value of OPT at round $i$. We know
that the advice was feasible at some previous round $i^{\prime}\geq i_{a}$ but
became infeasible at round $i^{\prime}+1\leq i$. Round $i^{\prime}$ belongs to
the second case, so at that round

$c^{T}x\leq 2c^{T}x^{\prime}.$

In round $i^{\prime}+1$, we transition back from the advice to the online
algorithm, so

$c^{T}x\leq 2c^{T}x^{\prime}+O(\log
k)\textsf{OPT}_{i^{\prime}+1}\leq\min\\{O(c^{T}x^{\prime}),O(\log
k)\textsf{OPT}_{i^{\prime}+1}\\}\leq O(\log k)\textsf{OPT}_{i^{\prime}+1}.$

In round $i$, $c^{T}x^{\prime}$ does not change but OPT changes. By the
property of the online algorithm $\mathcal{O}$, we always have

$c^{T}x\leq O(\log k)\textsf{OPT}_{i}.$

∎