# The Cost of Informing Decision-Makers in Multi-Agent Maximum Coverage
Problems with Random Resource Values

Bryce L. Ferguson, Dario Paccagnan, and Jason R. Marden This research was
supported by ONR Grant #N00014-20-1-2359, and AFOSR Grants #FA95550-20-1-0054
and FA9550-21-1-0203B. L. Ferguson (corresponding author) and J. R. Marden are
with the Department of Electrical and Computer Engineering, University of
California, Santa Barbara, CA<EMAIL_ADDRESS>Paccagnan
is with the Department of Computing, Imperial College London,
<EMAIL_ADDRESS>
###### Abstract

The emergent behavior of a distributed system is conditioned by the
information available to the local decision-makers. Therefore, one may expect
that providing decision-makers with more information will improve system
performance; in this work, we find that this is not necessarily the case. In
multi-agent maximum coverage problems, we find that even when agents’
objectives are aligned with the global welfare, informing agents about the
realization of the resource’s random values can reduce equilibrium performance
by a factor of 1/2. This affirms an important aspect of designing distributed
systems: information need be shared carefully. We further this understanding
by providing lower and upper bounds on the ratio of system welfare when
information is (fully or partially) revealed and when it is not, termed the
value-of-informing. We then identify a trade-off that emerges when optimizing
the performance of the best-case and worst-case equilibrium.

##  I Introduction

In large-scale systems, the prospect of distributing decision-making to local
entities is becoming increasingly enticing as a method to reduce complexity
while maintaining some level of performance. This can take the form of swarm
control for robotic fleets [1], autonomous driving decisions in mobility
services [2], local task assignment decisions [3], and many more. Taking a
distributed approach entails assigning each agent a decision-making algorithm,
such as maximizing an assigned local objective function [4], then analyzing
the system’s equilibria [5]. As agents need not possess full knowledge of the
overall system; the local decisions (and, ultimately, global behavior) are
dependent on the information communicated with and between the agents [6, 7]
In this work, we address how available information affects system performance.

We focus on maximum coverage problems: a class of models in which each agent
selects a set of resources from a ground set, with the objective of maximizing
the value of covered resources. To solve this in a distributed fashion, each
agent is given a utility function to evaluate what set of resources to cover;
this forms a game played by the agents with their resource selection as their
action and the evaluation of their assigned utility function as their payoff.
Existing work has focused on how to design these utility rules and how well
the resulting equilibria of the emergent game approximate the optimal welfare
[8, 9, 10]. In this work, we generalize this model to consider the case where
agents have uncertainty about the resources’ values. In this setting, we ask
how revealing information to local decision-makers affects equilibrium
performance. Interestingly, we find that _revealing truthful information about
the system state can worsen system performance_. While this phenomenon has
been observed before in social systems [11], here we find that similar
conclusions hold even when the local decision-makers’ objectives are _aligned_
with the global welfare.

To study this, we consider a _Bayesian persuasion_ framework, in which a well-
informed system operator can strategically reveal information to agents using
messages (or signals) which contain partial information [12]. In this work, we
study how this information revealing affects equilibrium welfare. To this end,
we introduce a new performance metric termed the _value-of-informing_ , which
measures the ratio between the equilibrium welfare under an information-
revealing policy and when no information is revealed. This measures the gain
or loss in welfare from revealing information.

The framework of Bayesian persuasion has gained traction in the areas of
economics, operations research, and engineering, but typically for settings
concerned with the behavior and beliefs of human users (e.g., traffic routing
apps [13, 14, 15], pricing/investing decisions [16], hybrid work policies
[17], etc.). Results are typically restricted to a binary classification on
whether revealing full information helps or not [18, 12], or methods to
compute optimal information revealing policies in limited settings [19, 20,
15], often with no guarantee on the magnitude of improvement. Here, we adapt
the ideas of information provisioning to the setting of engineered systems,
where designed decision-making components can improve their estimate of the
system state by receiving relevant messages (e.g., a fleet of surveillance
drones receiving live map updates).

Revealing information to local decision-makers can obviously improve the
welfare of emergent system equilibria; however, in this work, we find that
this is not always the case. In fact, system performance may degrade by a
factor of 1/2 when revealing truthful information to local decision-makers.
The possible loss in system welfare from informing decision-makers comes from
two sources (1) the multiplicity of equilibria and (2) the local objective
assigned to each decision-maker. We study the aforementioned value-of-
informing when considering the best-case and worst-case equilibria for
different local objectives. Ultimately, we highlight a trade-off between the
possible loss from revealing information to best-case and worst-case
equilibrium guarantees when agents’ local objectives are designed.

##  II Problem Formulation

###  II-A Maximum Coverage Problem

Maximum coverage problems have been used to model resource allocation, sensor
coverage, job scheduling, and more [21]. Consider the multi-agent maximum
coverage problem, in which $\mathcal{R}=\\{1,\ldots,R\\}$ is a finite set of
resources. For each resource $r\in\mathcal{R}$, let $v_{r}\geq 0$ be the value
of that resource; further, let $v\in\mathbb{R}_{\geq 0}^{|\mathcal{R}|}$ be
the vector containing each resource value. Let $N=\\{1,\ldots,n\\}$ be a set
of agents, where each agent $i\in N$ can be assigned to cover a subset of
resources $a_{i}\subseteq\mathcal{R}$. The set of allowable assignments for
each agent is defined by $\mathcal{A}_{i}\subseteq 2^{\mathcal{R}}$. When each
agent is assigned, an allocation of agents is denoted
$a=(a_{1},\ldots,a_{n})\in\mathcal{A}=\mathcal{A}_{1}\times\ldots\times\mathcal{A}_{n}$.
Let $(G,v)$ define a maximum coverage problem where
$G=(N,\mathcal{R},\mathcal{A})$.

In an allocation $a$, the system welfare is equal to the total value of
resources covered by at least one agent, i.e., $W(a;v)=\sum_{r\in\cup_{i\in
N}a_{i}}v_{r}.$ However, finding an optimal allocation $a^{\rm
opt}\in\operatorname*{arg\,max}_{a\in\mathcal{A}}W(a;v)$ is NP-hard [9]. It is
for this reason, we consider a distributed solution technique to approximate
this optimal solution.

###  II-B Distributed Decision Making

Let each agent $i\in N$ possess a local objective function

$U_{i}(a;v)=\sum_{r\in a_{i}}v_{r}f(|a|_{r}),$

which depends on their own action and the actions of every other agent. This
local objective, or utility function, is parameterized by a local utility rule
$f:\mathbb{N}\rightarrow\mathbb{R}$ that takes as argument $|a|_{r}$, the
number of agents covering resource $r$ in allocation $a$. The system operator
can adopt a utility rule $f$ without exact knowledge of the problem instance
if needed.

When agents sequentially and repeatedly update their assignment to one that
currently maximizes their utility function, these best-response dynamics have
fixed points that are the Nash equilibria of the underlying game. The
convergence of best response dynamics in potential games to pure Nash
equilibria are addressed in [9, 5]. Nash equilibrium allocations can be
defined by

$U_{i}(a^{\rm NE};v)\geq U_{i}(a_{i}^{\prime},a^{\rm
NE}_{-i};v)\leavevmode\nobreak\ \forall
a_{i}^{\prime}\in\mathcal{A}_{i},\leavevmode\nobreak\ i\in N,$ (1)

where $a_{-i}$ denotes the allocation of all agents but player $i$. Let ${\rm
NE}(G,v,f)$ denote the set of states satisfying (1). These states represent
the possible solutions of the distributed dynamics, and we will consider their
welfare as an approximation of the maximum coverage problem.

Figure 1: Depiction of information signaling in maximum coverage problems. On
the left is the support of a random state variable $v$. At right is a maximum
coverage problem, to which we have assigned each agent a local objective. The
agents in the coverage problem possess the prior distribution of the unknown
state variable and receive some partial information $\pi_{k}$ about the
realization. The manner in which information is revealed will alter how agents
evaluate their objectives and change the emergent behavior.

###  II-C Uncertainty and Information Signaling

In this work, we consider how uncertainty and information can affect the
efficacy of distributed decision-making. We consider this uncertainty in the
form of randomness for the resources values. Let $v\in\mathbb{R}_{\geq
0}^{|\mathcal{R}|}$ (the vector containing the value of each resource
$r\in\mathcal{R}$) be a discrete random variable with prior distribution
$\mu_{0}$. A realization of $v$ determines each resource’s value
$[v_{1},\ldots,v_{|\mathcal{R}|}]=v$, i.e., the resource values may be
correlated. Let the support of $v$ be $\mathcal{V}:=\mathrm{supp}(v)$.

First, we consider the case where agents are uninformed about the system
state, i.e., they know the prior distribution $\mu_{0}$ but not the exact
realization of $v$. In this setting, the agents optimize their expected
utility, which we will denote
$\overline{U}_{i}(a;\mu_{0})=\mathbb{E}_{v\sim\mu_{0}}\left[\sum_{r\in
a_{i}}v_{r}f(|a|_{r})\right].$ Let ${\rm NE}(G,\mu_{0},f)={\rm
NE}(G,\mathbb{E}_{v\sim\mu_{0}}[v],f)$. Additionally, the objective of the
maximum coverage problem is to maximize the expected welfare, i.e.,
$\overline{W}(a;\mu_{0})=\mathbb{E}_{\mu_{0}}\left[\sum_{r\in\cup_{i\in
N}a_{i}}v_{r}\right].$

As a means to try and improve the performance of the distributed decision-
making agents, we may consider revealing information about the realization of
the system state. One option is to reveal full information (or let agents know
the realization exactly); however, either due to communication constraints or
by design choice, it is often meaningful to reveal only partial information as
well. In line with the broader Bayesian Persuasion framework, consider
revealing information with an information signaling policy
$\Pi=\\{\pi_{1},\ldots,\pi_{m}\\}$, where $\pi_{k}\subseteq\mathcal{V}$,
$\pi_{j}\cap\pi_{k}=\emptyset$, and $\bigcup_{k=1}^{m}\pi_{k}=\mathcal{V}$.
This signaling policy $\Pi$ forms a partition over the support of our random
state variable $v$. The signal $\pi\in\Pi$ is revealed to the agents when
$v\in\pi$.111In this work, we consider signaling policies that are
deterministic mappings from state to signal. In general, signal $\pi$ could be
drawn randomly based on state $v$. Many of the results easily generalize to
this setting, but for ease of exposition and relevance to our problem setting
of informing designed decision-makers, we present the results for
deterministic signaling by treating $\Pi$ as a partition of $\mathcal{V}$. The
new system operates as follows: A system operator adopts a signaling policy
$\Pi$ and utility rule $f$. A state $v$ is drawn from $\mu_{0}$, and all
agents are informed of which element of $\Pi$ the realization belongs to. The
corresponding signal $\pi$ is sent, and each player $i\in N$ computes the
posterior belief on the realization
$\mu_{\pi}(x)=\mathbb{P}[v=x|v\in\pi]=\mu_{0}(x)/\left(\sum_{v^{\prime}\in\pi}\mu_{0}(v^{\prime})\right)$
if $v\in\pi$ and zero otherwise. The agents then seek to maximize their
expected utility with the posterior belief.

Agents may now condition their action on the received signal. Let
$\alpha\in\mathcal{A}^{\Pi}$ denote a joint strategy, where an element
$\alpha_{i}(\pi)\in\mathcal{A}$ captures the action agent $i$ takes when they
receive signal $\pi$. In a strategy profile $\alpha$, agent $i$ has an
expected payoff of
$\overline{U}_{i}(\alpha;\mu_{0},\Pi)=\mathbb{E}_{v\sim\mu_{0}}\left[\sum_{r\in\alpha_{i}}v_{r}f(|\alpha|_{r})\right]$.
Note that $\alpha_{i}$ is implicitly a function of the received signal $\pi$,
which itself is determined by the state variable $v$; as such, each of
$\alpha_{i}$, $\pi$, and $v$ are random variables. The expected welfare
becomes
$\overline{W}(\alpha;\mu_{0},\Pi)=\mathbb{E}_{v\sim\mu_{0}}\left[\sum_{r\in\cup_{i\in
N}\alpha_{i}}v_{r}\right]$.

When agents follow best-response dynamics, the set of fixed points becomes the
set of Bayes-Nash equilibria, ${\rm BNE}(G,\mu_{0},\Pi,f)$. A strategy
$\alpha^{\rm BNE}$ in this set satisfies

$\overline{U}_{i}(\alpha^{\rm
BNE};\mu_{0},\Pi)\geq\overline{U}_{i}(\alpha_{i}^{\prime},\alpha^{\rm
BNE}_{-i};\mu_{0},\Pi)\leavevmode\nobreak\
\forall\alpha_{i}^{\prime}\in\mathcal{A}_{i}^{\Pi}.$ (2)

The signaling policy $\Pi$ will alter this equilibria set and thus the
guarantees of our distributed solution to the maximum coverage problem.

Our motivation for this work is understanding how giving agents information
can affect system welfare. Due to the multiplicity of equilibria, we consider
two perspectives: the optimistic perspective in which the system designer
cares about the best attainable system performance, and the pessimistic
perspective in which the system designer cares about the worst possible
performance. For the optimistic perspective, the system designer evaluates a
signaling policy $\Pi$ by its effect on the system welfare in the best-case
equilibrium; as such, let the optimistic value-of-informing with signaling
policy $\Pi$ be

$\mathrm{VoI}^{+}(G,\mu_{0},\Pi,f)=\frac{\max_{\alpha\in{\rm
BNE}(G,\mu_{0},\Pi,f)}W(\alpha;\mu_{0},\Pi)}{\max_{a\in{\rm
NE}(G,\mu_{0},f)}W(a;\mu_{0})},$

which measures the gain in optimistic welfare by using policy $\Pi$.
Similarly, for the pessimistic perspective, the system operator evaluates a
signaling policy $\Pi$ by its effect on the system welfare in the worst-case
equilibrium; let the pessimistic value-of-informing be

$\mathrm{VoI}^{-}(G,\mu_{0},\Pi,f)=\frac{\min_{\alpha\in{\rm
BNE}(G,\mu_{0},\Pi,f)}W(\alpha;\mu_{0},\Pi)}{\min_{a\in{\rm
NE}(G,\mu_{0},f)}W(a;\mu_{0})},$

which is the same ratio but now with the worst-case equilibrium strategy and
allocation. These values inform a system operator of how revealing information
will affect their equilibrium guarantees. They differ from the well-known
price-of-anarchy/stability measures in that they relate two equilibrium
performances rather than equilibrium to optimal.

##  III Main Results

The main contribution of this work is in lower and upper bounding the value-
of-informing for best- and worst-case equilibria. These bounds depend on
agents’ local decision-making process. In Section III-A, we focus on the case
where agents’ payoffs are aligned with the system objective and find that
revealing information improves the best-case equilibrium
($\mathrm{VoI}^{+}\geq 1$) but can worsen the worst-case equilibrium
($\mathrm{VoI}^{-}\leq 1$). In Section III-B, we generalize these bounds to
any local utility rule $f$. In Section III-C, we observe a trade-off in the
lower bounds on $\mathrm{VoI}^{+}$ and $\mathrm{VoI}^{-}$; Fig. 2
characterizes this trade-off and highlights the fact that altering the local
objectives of agents affects the efficacy of revealing information.

###  III-A Marginal Contribution

The first utility design we will consider is the marginal contribution, where
each agent makes decisions that maximize their contribution to the system
welfare, i.e., $U_{i}(a)=W(a)-W(a_{-i}).$ This can be expressed by the local
utility rule $f^{\rm mc}(x):={\mathds{1}}{[x=1]}.$ When agents follow this
utility rule, their preferences are aligned with global welfare. This utility
rule has the property that it maximizes the best-case equilibrium guarantee,
known as the price-of-stability ratio [10]. However, as of yet, the effect of
revealing information to decision-makers using this utility function has not
been addressed. In Theorem 1, we address this question by providing lower and
upper bounds on the value-of-informing for the best- and worst-case
equilibria.

######  Theorem 1.

In a Bayesian Maximum Coverage problem $(G,\mu_{0},\Pi)$, with utility rule
$f^{\rm mc}$, the value-of-informing for the best-case equilibrium satisfies

$1\leq\mathrm{VoI}^{+}(G,\mu_{0},\Pi,f^{\rm mc})\leq\lvert\Pi\rvert,$ (3a) and
for the worst-case equilibrium satisfies
$1/2\leq\mathrm{VoI}^{-}(G,\mu_{0},\Pi,f^{\rm mc})\leq 2\lvert\Pi\rvert.$ (3b)

All of these bounds are tight, but the upper bounds on $\mathrm{VoI}^{-}$.

Before proving the statement, we discuss the consequences of these results. We
first see that revealing more information (increasing the cardinality of
$\Pi$) provides significant opportunities for improvement in either
perspective222A more refined understanding of this improvement can be attained
by considering the difference between the realizations and the prior mean..
However, revealing information need not always have such a positive effect. In
the optimistic perspective, revealing information can only improve performance
($\mathrm{VoI}^{+}\geq 1$); however, doing so does not come without
consequence, as revealing information can reduce the quality of the worst-case
equilibrium by a factor of 1/2 ($\mathrm{VoI}^{-}=1/2$). This fact affirms an
important property of information in a multi-agent system: revealing
information must be done carefully. The proof relies on the following lemma
characterizing Bayes-Nash equilibria and the expected welfare.

######  Lemma 1.

A joint strategy $\alpha$ is a Bayes-Nash equilibrium if and only if
$(\alpha_{1}(\pi),\ldots,\alpha_{n}(\pi))\in{\rm
NE}(G,\mathbb{E}[v\mid\pi_{k}],f)$ for each $\pi\in\Pi$. Additionally, the
expected welfare of a joint strategy $\alpha$ is a weighted average of the
welfare of the joint actions $\alpha(\pi)$ in the respective deterministic
games, i.e.,

$\overline{W}(\alpha;\mu_{0},\Pi)=\sum_{k=1}^{m}p_{k}W\left(\alpha(\pi_{k});\mathbb{E}[v|\pi_{k}]\right),$

where $p_{k}=\sum_{v\in\pi_{k}}\mu_{0}(v)$.

###### Proof.

Let $\alpha\in\mathcal{A}^{\Pi}$ denote a joint strategy. We show the first
claim by observing the following transformation for any $\alpha$,

$\displaystyle\overline{U}_{i}(\alpha;\mu_{0},\Pi)$
$\displaystyle=\mathbb{E}\left[\sum_{r\in\mathcal{R}}\mathbb{E}[v_{r}|\pi]f(|\alpha(\pi)|_{r})\right]$
(4a)
$\displaystyle=\sum_{k=1}^{m}p_{k}U_{i}\left(\alpha(\pi_{k});\mathbb{E}[v|\pi_{k}]\right),$
(4b)

where (4a) holds from the law of total expectation. Because $\alpha$ can be
any $m$-tuple of joint actions, (2) is satisfied if and only if
$U_{i}\left(\alpha(\pi);\mathbb{E}[v|\pi]\right)\geq
U_{i}\left(a_{i}^{\prime},\alpha_{-i}(\pi);\mathbb{E}[v|\pi]\right),$ for all
$a^{\prime}_{i}\in\mathcal{A}_{i}$, $\pi\in\Pi$; or, that $\alpha(\pi)$ is a
Nash equilibrium for the deterministic game $G$ with values
$\mathbb{E}[v|\pi]$ for each $\pi\in\Pi$. The second claim follows (4) with
welfare in place of utility. ∎

Proof of Theorem 1: Best-case equilibrium \- We will make use of the function
$W^{\star}(v)$, which denotes the welfare of an optimal allocation in $G$ when
the values are $v$. We note that with the marginal contribution utility rule,
each optimal allocation $a^{\rm opt}$ is an equilibrium; thus, the welfare of
the best Nash equilibrium is the optimal welfare [10], or
$W^{\star}(v)=\max_{a\in\mathcal{A}}W(a;v)=\max_{a^{\rm NE}\in{\rm
NE}(G,v,f^{\rm mc})}W(a^{\rm NE})$. We first make several observations about
the function $W^{\star}$. Observe that
$W^{\star}(v)=\max_{a\in\mathcal{A}}\sum_{r\in\mathcal{R}}v_{r}{\mathds{1}}{[|a|_{r}>0]},$
is the point-wise maximum of a set of affine (and thus convex) functions of
$v$, which is itself convex. Further, $W^{\star}$ is positively homogeneous,
i.e., $W^{\star}(\lambda v)=\lambda W^{\star}(v)$ for all $\lambda\geq 0$ and
$v\geq 0$, and $W^{\star}$ is monotone in $v$, i.e., $v\succeq
v^{\prime}\Rightarrow W^{\star}(v)\geq W^{\star}(v^{\prime})$ where
“$\succeq$” denotes the element-wise inequality.

Using the properties of $W^{\star}$, we will prove the bounds on
$\mathrm{VoI}^{+}$. First, the lower bound. Consider the Bayesian covering
game $(G,\mu_{0},\Pi)$. Observe that

$\displaystyle\max_{a\in{\rm NE}(G,\mu_{0},f^{\rm mc})}$
$\displaystyle\overline{W}(a;\mu_{0})=W^{\star}\left(\sum_{k=1}^{m}p_{k}\mathbb{E}[v|\pi_{k}]\right)$
(5a) $\displaystyle\leq\sum_{k=1}^{m}p_{k}W^{\star}(\mathbb{E}[v|\pi_{k}])$
(5b) $\displaystyle=\max_{\alpha\in{\rm BNE}(G,\mu_{0},\Pi,f^{\rm
mc})}\overline{W}(\alpha;\mu_{0},\Pi),$ (5c)

where (5a) holds from the fact the maximum-welfare Nash equilibrium is a
system optimum and the second claim of Lemma 1, (5b) holds from $W^{\star}$
convex and Jensen’s inequality, and (5c) holds from the second claim of Lemma
1 and the first claim of Lemma 1 with the fact the maximum-Nash is a system
optimum. Rearranging terms gives the first inequality in (3a). It is tight
when $|\mathcal{V}|=1$.

Now, we consider the upper bound on $\mathrm{VoI}^{+}$.

$\displaystyle\max_{\alpha\in{\rm BNE}(G,\mu_{0},\Pi,f^{\rm
mc})}\overline{W}(\alpha;\mu_{0},\Pi)=\sum_{k=1}^{m}p_{k}W^{\star}(\mathbb{E}[v|\pi_{k}])$
(6a) $\displaystyle\hskip
20.0pt=\sum_{k=1}^{m}W^{\star}\left(p_{k}\mathbb{E}[v|\pi_{k}]\right)\leq\sum_{k=1}^{m}W^{\star}(\mathbb{E}_{\mu_{0}}[v])$
(6b) $\displaystyle\hskip 40.0pt=\lvert\Pi\rvert\left(\max_{a\in{\rm
NE}(G,\mu_{0},f^{\rm mc})}\overline{W}(a;\mu_{0})\right),$ (6c)

where (6a) holds from the fact a Bayes-Nash joint strategy $\alpha$ is an
$m$-tuple of Nash equilibria, the maximum-welfare Nash equilibrium is optimal
in $W(\cdot\leavevmode\nobreak\ ;v)$ and the second claim in Lemma 1. (6b)
holds from $W^{\star}$ positive homogeneous and the monotonicity of
$W^{\star}$; more specifically,

$\mathbb{E}_{\mu_{0}}[v_{r}]=\sum_{k\in[m]}p_{k}\mathbb{E}[v_{r}|\pi_{k}]\\\
=p_{k}\mathbb{E}[v_{r}|\pi_{k}]+\sum_{k^{\prime}\in[m]\setminus
k}p_{k^{\prime}}\mathbb{E}[v_{r}|\pi_{k^{\prime}}]\geq
p_{k}\mathbb{E}[v_{r}|\pi_{k}],$

holds $\forall$ $r\in\mathcal{R}$, $\pi_{k}\in\Pi$. (6c) holds from the
definition $W^{\star}$.

To see this is tight, consider a problem with $R$ resources and one agent who
can select a single one of them, i.e., $\mathcal{A}_{1}=\\{1,\ldots,R\\}$.
Each resource can take on one of two values: $0$ or $1$. The prior $\mu_{0}$
is that exactly one resource is ever of value 1 with equal probability; so the
support of $v$ has $R$ elements, each of which occurs with probability $1/R$.
When uninformed, the single agent is indifferent over their actions and cannot
attain a payoff greater than $1/R$. When informed, the single agent can always
select the resource of value 1. Thus ${\rm VoI}^{+}=R=|\mathcal{V}|=|\Pi|$.

Worst-case equilibrium \- To focus on equilibrium strategies, let $a^{\rm
NE}(v)$ denote a Nash equilibrium joint action in the game $G$ when the values
are $v$. The following steps will hold for any Nash equilibrium, and the proof
will be completed by considering $a^{\rm NE}(v)$ as the welfare minimizing
Nash equilibrium. Observe that the uninformed Nash welfare satisfies

$W(a^{\rm NE}(\mathbb{E}_{\mu_{0}}[v]);\mathbb{E}_{\mu_{0}}[v])\leq
W^{\star}(\mathbb{E}_{\mu_{0}}[v])\leq\\\
\sum_{k=1}^{m}p_{k}W^{\star}(\mathbb{E}[v|\pi_{k}])\leq\sum_{k=1}^{m}p_{k}2W(a^{\rm
NE}(\mathbb{E}[v|\pi_{k}]);\mathbb{E}[v|\pi_{k}]),$

where the first inequality holds from the definition of $W^{\star}$, the
second holds from properties of $W^{\star}$ shown in the first part of the
proof, and the third holds from the price-of-anarchy bound of 1/2 [22].
Letting $a^{\rm NE}(v)$ be the worst-case Nash equilibrium when the values are
$v$ in each occurrence, the rightmost expression is the worst-case welfare in
a Bayes-Nash joint strategy via Lemma 1. This gives the first inequality in
(3a).

To see that this bound is tight, consider a resource allocation game with
three resources, $\mathcal{R}=\\{1,2,3\\}$, and two players, $N=\\{1,2\\}$
with two actions each: $\mathcal{A}_{1}=\\{r_{1},r_{2}\\}$ and
$\mathcal{A}_{2}=\\{r_{2},r_{3}\\}$. Let resource $r_{1}$ have value $v_{1}=1$
and $r_{3}$ have value $v_{3}=0$. Let the value of resource $r_{2}$ be a
random variable, where $v_{2}=1-\varepsilon$ with probability $1-p$ and
$v_{2}=1+\varepsilon(1-p)$ with probability $p$. When the agents are not
informed of the realization of $v_{2}$, its expected value is
$\mathbb{E}[v_{2}]=1-\varepsilon(1-p)^{2}<1$ and there is a unique Nash
equilibrium of $a=(r_{1},r_{2})$, providing a welfare of
$W(a;\mu_{0})=2-\varepsilon(1-p)^{2}$. When the full revelation signaling
policy $\Pi=\\{\\{r_{1}\\},\\{r_{2}\\}\\}$ is used, then when
$v_{2}=1-\varepsilon$, there is a unique equilibrium of
$\alpha^{1}=(r_{1},r_{2})$, and when $v_{2}=1+\varepsilon(1-p)$ there are two
equilibria, the worse of which is $\alpha^{2}=(r_{2},r_{3})$. This gives an
expected welfare of
$W(\alpha;\mu_{0})=(1-p)(2-\varepsilon)+p(1+\varepsilon(1-p))$ and a gain of
informing agents of ${\rm VoI}^{-}(\Pi,f^{\rm
mc})=\frac{(1-p)(2-\varepsilon)+p(1+\varepsilon(1-p))}{2-\varepsilon(1-p)^{2}}.$
Letting $p\rightarrow 1$ and $\varepsilon\rightarrow 0$ we get ${\rm
VoI}^{-}(\Pi,f^{\rm mc})\rightarrow 1/2$.

Finally, we show the upper bound on $\mathrm{VoI}^{-}$. Observe that the
welfare of a Bayes-Nash strategy $\alpha=\\{a^{\rm
NE}(\mathbb{E}[v|\pi])\\}_{\pi\in\Pi}$ under the signaling policy $\Pi$
satisfies

$\sum_{k=1}^{m}p_{k}W(a^{\rm
NE}(\mathbb{E}[v|\pi_{k}]);\mathbb{E}[v|\pi_{k}])\leq\sum_{k=1}^{m}p_{k}W^{\star}(\mathbb{E}[v|\pi_{k}])\\\
\leq|\Pi|\cdot W^{\star}(\mathbb{E}_{\mu_{0}}[v])\leq 2|\Pi|\cdot W(a^{\rm
NE}(\mathbb{E}_{\mu_{0}}[v]);\mathbb{E}_{\mu_{0}}[v]),$

where the first term is the expected payoff of $\alpha$, and the first
inequality holds from $W^{\star}$ being the optimal welfare, the second holds
from the upper bound on $\mathrm{VoI}^{+}$, and the third holds from the
price-of-anarchy bound. ∎

Figure 2: Lower bounds on the value of revealing information for the best- and
worst-case equilibria. If the utility rule $f$ is designed to lessen the loss
to worst-case equilibria (increasing $\mathrm{VoI}^{-}$), then there is a
greater possible loss to the worst-case equilibrium (decreasing
$\mathrm{VoI}^{+}$). This trade-off matches the tight bounds from Theorem 1
and Proposition 1, which appear as the endpoints of this plot. The bounds are
generated by comparing the value-of-informing to the price-of-
anarchy/stability via Theorem 2 and the price of stability to the price-of-
anarchy via [10, Theorem 4.1].

###  III-B Utility Design & Informing Efficacy

In Section III-A, we considered the special case in which agents’ local
objectives were aligned with the global objective using the marginal cost
utility rule $f^{\rm mc}$. In this section, we generalize this result to any
utility rule by leveraging a connection to the price-of-stability and price-
of-anarchy.

In the deterministic setting, the price-of-stability/anarchy are used to
quantify how the best-case and worst-case equilibria approximate the system
optimal. These metrics can be generalized to the Bayesian setting but need not
be informative or insightful on the effects revealing information within a
single problem instance [23] (i.e., failing to capture the benefits and
consequences or comparing bounds derived from different problem instances).
Let $\mathrm{PoA}(G,v,f)=\frac{\min_{a^{\rm NE}\in{\rm NE}(G,v,f)}W(a^{\rm
NE};v)}{\max_{a^{\rm opt}\in\mathcal{A}}W(a^{\rm opt};v)}$ denote the price-
of-anarchy for a deterministic maximum coverage problem, and let
$\mathrm{PoS}(G,v,f)=\frac{\max_{a^{\rm NE}\in{\rm NE}(G,v,f)}W(a^{\rm
NE};v)}{\max_{a^{\rm opt}\in\mathcal{A}}W(a^{\rm opt};v)}$ denote the price-
of-stability.

Though not immediately apparent, we establish a connection between the price-
of-stability/anarchy in deterministic covering games and the value-of-
informing in Bayesian covering games. In Theorem 2, we leverage this
connection to generate bounds on $\mathrm{VoI}^{+}$ and $\mathrm{VoI}^{-}$ for
any utility design.

######  Theorem 2.

Let $\psi:=\inf_{v\in\mathrm{conv}(\mathcal{V})}\mathrm{PoS}(G,v,f)$ and
$\rho:=\inf_{v\in\mathrm{conv}(\mathcal{V})}\mathrm{PoA}(G,v,f)$, then the
value of informing for the best-case equilibrium satisfies

$\psi\leq\mathrm{VoI}^{+}(G,\mu_{0},\Pi,f)\leq\psi^{-1}|\Pi|,$ (7a) and for
the worst-case equilibrium satisfies
$\rho\leq\mathrm{VoI}^{-}(G,\mu_{0},\Pi,f)\leq\rho^{-1}|\Pi|.$ (7b)

Proof of Theorem 2: The proof will rely on the function
$W^{\star}(v)=\max_{a\in\mathcal{A}}W(a;v)$ and several of its properties
shown in the proof of Theorem 1. First, we prove the bounds on
$\mathrm{VoI}^{+}$. Let $a\in{\rm NE}(G,\mathbb{E}_{\mu_{0}}[v],f)$ be an
arbitrary Nash equilibrium in the deterministic game $G$ with values
$\mathbb{E}_{\mu_{0}}[v]$ and utility rule $f$, and let $\alpha\in{\rm
BNE}(G,\mu_{0},\Pi,f)$ be an arbitrary Bayes-Nash equilibrium in $G$ with
prior $\mu_{0}$ on $v$ and information signaling policy $\Pi$ and utility
function $f$. Observe that the expected welfare of $\alpha$ satisfies

$\displaystyle\overline{W}(\alpha;\mu_{0},\Pi)$
$\displaystyle=\sum_{k=1}^{m}p_{k}W(\alpha(\pi_{k});\mathbb{E}[v|\pi_{k}])$
(8a) $\displaystyle\leq\sum_{k=1}^{m}p_{k}W^{\star}(\mathbb{E}[v|\pi_{k}])$
(8b) $\displaystyle\leq|\Pi|W^{\star}(\mathbb{E}_{\mu_{0}}[v])$ (8c)
$\displaystyle\leq\rho^{-1}|\Pi|\overline{W}(a;\mathbb{E}_{\mu_{0}}[v]),$ (8d)

where (8a) holds from Lemma 1, (8b) holds from the definition of $W^{\star}$,
(8c) holds from the monotonicity and positive homogeneity of $W^{\star}$
(previously shown in (6b)-(6c)), and (8d) holds from the definition of $\rho$.

Similarly, we can show that the expected total welfare of the uninformed
equilibrium $a$ satisfies

$\displaystyle\overline{W}(a;\mu_{0})$ $\displaystyle\leq W^{\star}(v)$ (9a)
$\displaystyle\leq\sum_{k=1}^{m}p_{k}W^{\star}(\mathbb{E}[v|\pi_{k}])$ (9b)
$\displaystyle\leq\sum_{k=1}^{m}p_{k}\rho^{-1}W(\alpha(\pi);\mathbb{E}[v|\pi_{k}])$
(9c) $\displaystyle=\rho^{-1}W(\alpha;\mu_{0},\Pi),$ (9d)

where (9b) holds from the convexity of $W^{\star}$, (9c) holds from the
definition of $\rho$, and (9d) holds from Lemma 1. Because (8) and (9) hold
for any $a\in{\rm NE}(G,\mathbb{E}_{\mu_{0}}[v],f)$ and $\alpha\in{\rm
BNE}(G,\mu_{0},\Pi,f)$, it holds for each being the respective welfare
minimizing equilibria. If we consider only the case where $a$ and $\alpha$ are
the welfare maximizing equilibria, i.e.,
$a\in\operatorname*{arg\,max}_{a^{\prime}\in{\rm
NE}(G,\mathbb{E}_{\mu_{0}}[v],f)}W(a^{\prime};\mathbb{E}_{\mu_{0}}[v])$ and
$\alpha\in\operatorname*{arg\,max}_{\alpha^{\prime}\in{\rm
BNE}(G,\mu_{0},v,f)}\overline{W}(\alpha^{\prime};\mu_{0},\Pi)$ ∎

###  III-C Optimistic / Pessimistic Trade-Off

Theorem 2 highlighted the fact that altering the utility design will change
the impact of information revealing; however, the given bounds need not be
tight. It appears that using a utility design with a higher price-of-anarchy
in the deterministic setting will lead to an improved lower bound on
$\mathrm{VoI}^{-}$. As such, we will more closely consider the price-of-
anarchy maximizing rule

$f^{\rm
g}(x):=(x-1)!\frac{\frac{1}{(n-1)(n-1)!}+\sum_{i=x}^{n-1}\frac{1}{i!}}{\frac{1}{(n-1)(n-1)!}+\sum_{i=1}^{n-1}\frac{1}{i!}},$

when $x>0$, and $f^{\rm g}(0)=0$, proven optimal in [9]. In Proposition 1, we
show tight lower bounds on the value-of-informing while using $f^{g}$.
Interestingly, though the pessimistic guarantee has improved, the optimistic
guarantee has worsened.

######  Proposition 1.

While using the the price-of-anarchy maximizing rule $f^{\rm g}$, the value-
of-informing for the best-case equilibrium satisfies

$1-\frac{1}{e}\leq\mathrm{VoI}^{+}(G,\mu_{0},\Pi,f^{\rm g}),$ (10a) and for
the worst-case equilibrium satisfies
$1-\frac{1}{e}\leq\mathrm{VoI}^{-}(G,\mu_{0},\Pi,f^{\rm g}),$ (10b)

Further, each of these lower bounds is tight.

Proof of Proposition 1: Theorem 2 can be used to show that each of (10a) and
(10b) are valid lower bounds. To see these bounds are tight, consider a
maximum coverage problem with resource set
$\mathcal{R}=\\{r_{p_{i}}\\}_{i=1}^{n-1}\bigcup\\{r_{s_{j}}\\}_{j=1}^{z}$
where $z=\lceil 1/(f^{g}(n)-\varepsilon)\rceil$. The first $n-1$ players can
select a single resource from the public resources $\\{r_{s_{j}}\\}_{j=1}^{z}$
or their respective private resource $r_{p_{i}}$ for player $i$, i.e.,
$\mathcal{A}_{i}=\\{r_{s_{1}},\ldots,r_{s_{z}},r_{p_{i}}\\},\leavevmode\nobreak\
\forall i\in N\setminus\\{n\\}$. The final player has exactly one action to
use all the shared resources simultaneously
$\mathcal{A}_{n}=(r_{s_{1}},\ldots,r_{s_{z}})$. Each private resource
$r_{p_{i}}$ has value $v_{r_{p_{i}}}=f^{\rm g}(n)-\varepsilon$ with
probability one where $\varepsilon>0$. The value of the shared resources are
random; each takes on value 1 w.p. $1/z<f^{\rm g}(n)-\varepsilon$ and 0
otherwise, and follow distribution $\mu_{0}$ such that exactly one is ever the
high value. When uninformed, each of the first $n-1$ players strictly prefers
their private resource, giving a unique equilibrium welfare of $W(a^{\rm
NE};\mu_{0})=1+(n-1)(f^{\rm g}(n)-\varepsilon)$. Under the full information
reveal policy $\Pi$, each of the $n-1$ agents strictly prefer to use the one
shared resource of value 1, giving an expected welfare of
$\overline{W}(\alpha^{\rm BNE};\mu_{0},\Pi)=1$. Because each of the informed
and uninformed equilibria are unique, this gives
$\mathrm{VoI}^{+}(\mu_{0},\Pi)=\mathrm{VoI}^{-}(\mu_{0},\Pi)=\frac{1}{1+(n-1)(f^{\rm
g}(n)-\varepsilon)}\rightarrow 1-\frac{1}{e}$ as $\varepsilon\rightarrow 0$
and $n\rightarrow\infty$. ∎

Comparing the lower bounds of Theorem 1 and Proposition 1 highlights a trade-
off between the guarantees of revealing information with the optimistic and
pessimistic perspectives. We further examine this trade-off in Fig. 2. Using
Theorem 2 and recent results on the price-of-anarchy/stability [10], we can
characterize lower bounds on $\mathrm{VoI}^{+}$ and $\mathrm{VoI}^{-}$ for
different utility rules.

##  IV Conclusion and Future Work

We addressed the possible benefit and consequences of revealing information to
local decision-makers in a distributed system. By lower and upper bounding the
value-of-informing, this work (1) quantified the possible effects of
information revealing and (2) identified a trade-off between the guarantees of
revealing information in the optimistic and pessimistic perspective. Future
work will answer the design question and develop methods to solve for
information signaling policies that optimize expected system welfare.

## References

  * [1] G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” _The International Journal of Robotics Research_ , vol. 32, no. 12, pp. 1495–1512, 2013.
  * [2] S. Wollenstein-Betech, A. Houshmand, M. Salazar, M. Pavone, C. G. Cassandras, and I. C. Paschalidis, “Congestion-aware Routing and Rebalancing of Autonomous Mobility-on-Demand Systems in Mixed Traffic,” in _2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC)_ , 2020, pp. 1–7.
  * [3] N. Mathew, S. L. Smith, and S. L. Waslander, “Planning paths for package delivery in heterogeneous multirobot teams,” _IEEE Transactions on Automation Science and Engineering_ , vol. 12, no. 4, pp. 1298–1308, 2015.
  * [4] J. R. Marden and J. S. Shamma, “Game Theory and Distributed Control,” in _Handbook of Game Theory Vol. 4_ , H. P. Young and S. Zamir, Eds. Elsevier Science, 2014.
  * [5] B. Swenson, R. Murray, and S. Kar, “On best-response dynamics in potential games,” _SIAM Journal on Control and Optimization_ , vol. 56, no. 4, pp. 2734–2767, Jul. 2018.
  * [6] S. Rahili, J. Lu, W. Ren, and U. Al-Saggaf, “Distributed Coverage Control of Mobile Sensor Networks in Unknown Environment Using Game Theory: Algorithms and Experiments,” _IEEE Transactions on Mobile Computing_ , vol. 17, no. 6, pp. 1303–1313, 2018.
  * [7] B. L. Ferguson and J. R. Marden, “Robust Utility Design in Distributed Resource Allocation Problems with Defective Agents,” _Dynamic Games and Applications_ , pp. 1–23, Aug. 2022.
  * [8] D. Paccagnan, R. Chandan, and J. R. Marden, “Utility Design for Distributed Resource Allocation—Part I: Characterizing and Optimizing the Exact Price of Anarchy,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 11, pp. 4616–4631, Nov. 2020\.
  * [9] M. Gairing, “Covering games: Approximation through non-cooperation,” in _Internet and Economics_ , 2009, pp. 184–195.
  * [10] V. Ramaswamy, D. Paccagnan, and J. R. Marden, “Multiagent Maximum Coverage Problems: The Tradeoff Between Anarchy and Stability,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 4, pp. 1698–1712, Apr. 2022\.
  * [11] D. Acemoglu, A. Makhdoumi, A. Malekian, and A. Ozdaglar, “Informational Braess’ Paradox: The Effect of Information on Traffic Congestion,” _Operations Research_ , vol. 66, no. 4, 2018.
  * [12] E. Kamenica and M. Gentzkow, “Bayesian Persuasion,” _American Economic Review_ , vol. 101, no. 6, pp. 2590–2615, Oct. 2011.
  * [13] M. Castiglioni, A. Celli, A. Marchesi, and N. Gatti, “Signaling in Bayesian Network Congestion Games: The Subtle Power of Symmetry,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 6, pp. 5252–5259, May 2021.
  * [14] B. L. Ferguson, P. N. Brown, and J. R. Marden, “Avoiding Unintended Consequences: How Incentives Aid Information Provisioning in Bayesian Congestion Games,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_ , Dec. 2022, pp. 3781–3786.
  * [15] H. Tavafoghi and D. Teneketzis, “Informational incentives for congestion games,” in _55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017_ , vol. 2018-Janua. Institute of Electrical and Electronics Engineers Inc., Jan. 2018, pp. 1285–1292.
  * [16] Y. Chen and J. Zhang, “Signalling by Bayesian Persuasion and Pricing Strategy,” _The Economic Journal_ , vol. 130, no. 628, pp. 976–1007, May 2020.
  * [17] S. Shah, S. Amin, and P. Jaillet, “Optimal Information Provision for Strategic Hybrid Workers,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_ , Dec. 2022, pp. 3807–3814.
  * [18] F. Sezer, H. Khazaei, and C. Eksin, “Social Welfare Maximization and Conformism via Information Design in Linear-Quadratic-Gaussian Games,” _arXiv preprint arXiv:2102.13047_ , 2021.
  * [19] Y. Zhu and K. Savla, “Information Design in Nonatomic Routing Games With Partial Participation: Computation and Properties,” _IEEE Transactions on Control of Network Systems_ , vol. 9, no. 2, pp. 613–624, Jun. 2022.
  * [20] M. Wu and S. Amin, “Information design for regulating traffic flows under uncertain network state,” in _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2019, pp. 671–678.
  * [21] D. Paccagnan, R. Chandan, and J. R. Marden, “Utility and mechanism design in multi-agent systems: An overview,” _Annual Reviews in Control_ , vol. 53, pp. 315–328, Jan. 2022.
  * [22] A. Vetta, “Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions,” _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ , pp. 416–425, 2002.
  * [23] U. Bhaskar, Y. Cheng, Y. K. Ko, and C. Swamy, “Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games,” 2015.


# A 3D Beamforming Scheme Based on The Spatial Distribution of User Locations

Jalal Rachad$\leavevmode\nobreak\ {}^{*+}$, Ridha Nasri$\leavevmode\nobreak\
{}^{*}$, Laurent Decreusefond$\leavevmode\nobreak\ {}^{+}$
$\leavevmode\nobreak\ {}^{*}$Orange Labs: Direction of Green transformation,
Data knowledge, traffic and resources Modeling,
40-48 avenue de la Republique 92320 Chatillon, France
$\leavevmode\nobreak\ {}^{+}$LTCI, Telecom Paris, Institut Polytechnique de
Paris,
75013, Paris, France
<EMAIL_ADDRESS>$\leavevmode\nobreak\
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Multi-antenna technologies such as massive Multiple-Input Multiple-Output
(massive MIMO) and beamforming are key features to enhance performance, in
terms of capacity and coverage, by using a large number of antennas
intelligently. With the upcoming 5G New Radio (NR), FD-MIMO (Full Dimension
MIMO) will play a major key role. FD-MIMO consists in arranging a large number
of antennas in a 2D array, which enables to use 3D beamforming i.e.,
beamforming in both horizontal and vertical dimensions. The present paper
provides a 3D beamforming model where beam steering depends on the random
spatial distribution of users. We attempt to derive some analytical results
regarding the probability distribution of antenna beamforming radiation
pattern. Also, through system level simulations, we show how 3D beamforming
can reduce interference impact, compared to the traditional 2D beamforming,
and enhances system performance in terms of the coverage probability and users
throughput.

###### Index Terms:

MIMO, 3D Beamforming, Performance, Interference, Azimuth, Downtilt.

##  I Introduction

As the amount of wireless data traffic is increasing continuously, 5G networks
need to support this proliferation through upgrading features in order to
ensure a strong compatibility with the upcoming mobile network generation
services. Massive Multiple antenna technologies including 3D beamforming have
drawn recently the attention of telecommunication actors and research
community. Actually, Beamforming consists in forming a signal beam between the
transmitter and the receiver by using an array of antennas. It enhances the
signal strength at the receiver and minimize interference level so that high
average data rate and high spectral efficiency can be achieved. Most existing
base stations (BSs) are equipped with directional antennas that provides
radiation patterns in the horizontal dimension, considering only the azimuth
angle, and having a fixed vertical pattern and downtilt. Recently, there has
been a trend to consider also the impact of the elevation and investigate how
antennas downtilt influence performance. It has been shown that the
combination of the horizontal and the vertical dimensions can further improve
the signal strength at the receiver location, enhances data rates and minimize
interference in neighboring cells [1].

MIMO and beamforming have been extensively studied in literature. For instance
in [2], coverage and rate in mmWaves network have been analyzed in an outdoor
environment. Authors considered directional antennas, approximated by sectored
antenna model, to perform directional beamforming in BSs and user equipments
(UEs). In [3] authors investigated the impact of adapting the vertical pattern
of antennas to user locations through conducted lab and field trial
measurements. They showed that, either in outdoor or indoor environments with
Line Of Sight (LOS) and Non Line Of Sight (NLOS) conditions, adapting the
vertical pattern improves performance. Interference restraint using dynamic
vertical beam steering has been studied in [4]. In [5] authors have analyzed
the impact of antenna radiation pattern and the downtilt on the performance of
a Downlink (DL) cellular network in terms of the coverage probability and the
area spectral efficiency (ASE). For the analytical approach, they have used
tools from stochastic geometry to model the spatial distribution of nodes.
Also, they have shown that there exists an optimal antenna downtilt that
depends on the LOS and NLOS conditions. This optimal downtilt maximizes the
coverage probability and improves the ASE. Similarly in [6], the effect of
antenna downtilt in a MIMO system has been studied through system level
simulations. Authors used the 3rd Generation Partnership Project (3GPP)
antenna radiation pattern model to show that the maximal cell throughput
depends on the antenna downtilt. Additionally, the network geometry and the
spatial distribution of users are important factors to consider when looking
for system performance analysis. Most considered models that can be found in
literature are the hexagonal model [7] and [8], and random models based on
spatial point process [9] and [10]. Analytical formulas are always considered
hard to derive when BSs are considered equipped with sectorized antennas,
especially in the case of random models, since interference depends on the
antenna radiation pattern in each sector. In [7], an explicit expression of
Interference to Signal Ratio (ISR) has been derived in a regular hexagonal
tri-sectorized network considering the horizontal antenna radiation pattern.
In [10] authors have analyzed performance of sectorized random network in
terms of Signal to Interference plus Noise Ratio (SINR). They have shown that
the distribution of SINR is insensitive to the antenna azimuth’s distribution.

The main contribution of this paper is to propose a new analytical approach to
model 3D beamforming in a regular tri-sectorized hexagonal network. We
characterize at first the antenna beamforming radiation pattern, in both
horizontal and vertical dimensions, considering the random locations of users
in the cells. Also, we prove that $ISR$ is an almost sure convergent series of
independent random variables and we show how to derive the mathematical
expectation of $ISR$ in each location of a mobile in a typical serving cell.
This metric is useful for link budget tools in which the expression of the
average perceived interference is required in each position. Then through
system level simulations, we analyze performance in terms of the coverage
probability and users throughput. We compare the proposed 3D beamforming model
with 2D beamforming in terms of coverage probability enhancement and
interference reduction.

The rest of the paper is structured as follows. In section II, we present our
network model as well as the 3D beamforming model. Section III provides a
characterization of antennas radiation patterns under the assumptions of the
3D beamforming model. A brief characterization of interference is given in
section IV. Numerical results are provided in section V. Section VI concludes
the paper.

##  II System model and notations

###  II-A Network model

We consider a regular tri-sectorized hexagonal network denoted by $\Lambda$
with an infinite number of sites $\boldsymbol{s}$ having an inter-site
distance denoted by $\delta$. For each site $\boldsymbol{s}$ $\in$ $\Lambda$,
there exists a unique (u,v) $\in$ $\mathbb{Z}^{2}$ such that
$\boldsymbol{s}=\delta(u+ve^{i\frac{\pi}{3}})$, we denote by
$\boldsymbol{s}_{0}$ the name of the serving cell located at the origin of
$\mathbb{R}^{2}$. Unlike regular hexagonal network with omni-directional
antennas, BSs of sites are located at the corner of the hexagons. All BSs have
the same height $l_{b}$, transmit with the same power level $P$ and assumed to
have directional antennas covering each one a hexagonal sector identified by
$c\in\\{1,2,3\\}$. The azimuths of antennas $\vartheta_{c}$ in which the
radiation is at its maximum is taken relative to the real axis and it is given
by

$\vartheta_{c}=\frac{\pi}{3}(2c-1),$ (1)

so that the azimuth of the first sector of each site has an angle of
$\frac{\pi}{3}$ with the real axis relatively to the position
$\boldsymbol{s}$.

The location of a mobile served by the first sector ($c=1$) of
$\boldsymbol{s}_{0}$ is denoted by $m$ such that $m=re^{i\theta}$ where (r,
$\theta$) are the polar coordinates in the complex plane. We denote also by
$n_{\boldsymbol{s},c}$ the geographical location of a mobile served by a
sector $c$ of a site $\boldsymbol{s}$ $\in$ $\Lambda^{*}$ in the plane, where
$\Lambda^{*}$ is the lattice $\Lambda$ without the serving cell
$\boldsymbol{s}_{0}$. Locations $n_{\boldsymbol{s},c}$ are written in the
complex plane by
$n_{\boldsymbol{s},c}=\boldsymbol{s}+r_{\boldsymbol{s},c}e^{i\theta_{\boldsymbol{s},c}}$,
where $r_{\boldsymbol{s},c}$ and $\theta_{\boldsymbol{s},c}$ represent
respectively the distance and the angle (complex argument) between
$n_{\boldsymbol{s},c}$ and $\boldsymbol{s}$.

###  II-B Beamforming model

As we mentioned previously, BSs are equipped with directional antennas with
sectorized gain pattern. At each TTI (Time Transmit Interval), we assume that
there is at most one user served by a sector $c$ of site $\boldsymbol{s}$
using beamforming radiation pattern. This can be modeled by a Bernoulli RV
$\rho_{\boldsymbol{s},c}$ such that
$\mathbb{P}(\rho_{\boldsymbol{s},c}=1)=\eta$ and
$\mathbb{P}(\rho_{\boldsymbol{s},c}=0)=1-\eta$. $\eta$ represents the
percentage of the occupied resources or the average load over the interfering
sites $\boldsymbol{s}$.

Furthermore, we assume that each antenna has a directional radiation that can
be described by two planar patterns: the horizontal and the vertical one
denoted respectively by $H$ and $V$. We define the antenna radiation for each
pattern by a $2\pi$-periodic function $U$ such that its restriction on
$(-\pi,\pi]\rightarrow[0,1]$ has the following properties

$\bullet$

$U(\alpha)=U(-\alpha)$ for all $\alpha\in(-\pi,\pi]$,

$\bullet$

$U(\alpha)=0$ if $\frac{\pi}{2}\leq|\alpha|\leq\pi$,

$\bullet$

$U$ is decreasing on $[0,\frac{\pi}{2}]$ and increasing on
$[\frac{-\pi}{2},0]$.

Numerous antenna radiation pattern models can be found in literature such as
the 3GPP model, Mogensen model [11] and real antenna patterns provided by
constructors (Kathrein antennas…). For reasons of tractability, we adopt in
the reminder of this analysis Mogensen model to describe the antenna
horizontal and vertical radiation patterns in the linear scale as follows

$\displaystyle H(\alpha)=[\cos(\alpha)]^{-2w_{h}}$ (2) $\displaystyle
V(\phi)=[\cos(\phi)]^{-2w_{v}},$ (3)

with $w_{h}=\frac{ln(2)}{\ln(\cos(\frac{\theta_{h3dB}}{2})^{2})}$ and
$w_{v}=\frac{ln(2)}{\ln(\cos(\frac{\theta_{v3dB}}{2})^{2})}$. $\theta_{h3dB}$
and $\theta_{v3dB}$ are respectively the horizontal and the vertical half
power beam widths.

This model can be adapted to beamforming radiation pattern by varying the beam
widths ($\theta_{h3dB}$ and $\theta_{v3dB}$ ). Hence, the antenna radiation
pattern received in a mobile location $m$ from an interfering site
$\boldsymbol{s}$ is defined by

$G_{\boldsymbol{s}}(m)=\sum_{c=1}^{3}\rho_{\boldsymbol{s},c}H(\alpha_{\boldsymbol{s},c})V(\phi_{\boldsymbol{s},c}),$
(4)

with $\alpha_{\boldsymbol{s},c}$ is the angle between the mobile $m$
orientation and the beam axis directed to a mobile $n_{\boldsymbol{s},c}$ in
the horizontal plane and $\phi_{\boldsymbol{s},c}$ is the angle between the
beam direction in the vertical plane and the mobile $m$. The angle
$\alpha_{\boldsymbol{s},c}$ can be expressed, based on the complex geometry,
as

$\alpha_{\boldsymbol{s},c}=\psi(m,\boldsymbol{s})-\theta_{\boldsymbol{s},c},$
(5)

where $\psi(m,\boldsymbol{s})=arg(m-\boldsymbol{s})$ and
$\theta_{\boldsymbol{s},c}=\psi(n_{\boldsymbol{s},c},\boldsymbol{s})$ is the
complex argument of $n_{\boldsymbol{s},c}$ relatively to $\boldsymbol{s}$.
Each $\theta_{\boldsymbol{s},c}$ is assumed to be uniformly distributed in the
interval $[\vartheta_{c}-\frac{\pi}{3},\vartheta_{c}+\frac{\pi}{3}]$, thus
using a linear transformation of the RV $\theta_{\boldsymbol{s},c}$, we can
easily prove that the angle $\alpha_{\boldsymbol{s},c}$ is a RV uniformly
distributed in the interval
$[\psi(m,\boldsymbol{s})-\frac{2\pi}{3}c,\psi(m,\boldsymbol{s})+\frac{2\pi}{3}(1-c)]$.

Similarly for the vertical dimension, the angle $\phi_{\boldsymbol{s},c}$ can
be expressed as

$\phi_{\boldsymbol{s},c}=atan(\frac{l_{b}}{|m-\boldsymbol{s}|})-\tilde{\phi}_{\boldsymbol{s},c},$
(6)

with
$\tilde{\phi}_{\boldsymbol{s},c}=atan(\frac{l_{b}}{r_{\boldsymbol{s},c}})$
refers to the antenna downtilt, which is variable in our case.

The distance $r_{\boldsymbol{s},c}=|n_{\boldsymbol{s},c}-\boldsymbol{s}|$
between a mobile $n_{\boldsymbol{s},c}$ and $\boldsymbol{s}$ varies between
$0$, when $n_{\boldsymbol{s},c}$ is close to $\boldsymbol{s}$ location, and
$\frac{2\delta}{3}$ when $n_{\boldsymbol{s},c}$ is located at the edge of a
sector. This distance can be characterized using the antenna radiation pattern
covering a whole hexagonal sector of $\boldsymbol{s}$. Thus,
$r_{\boldsymbol{s},c}$ is varying between $0$ and
$\frac{2\delta}{3}U(\theta_{\boldsymbol{s},c}-\vartheta_{c})$, with
$U(\theta_{\boldsymbol{s},c}-\vartheta_{c})$ is the antenna radiation pattern
of a sector (i.e., the half power beam width is equal to 65 degrees). So the
mobile will be located at the far edge of a sector when the angle between
$n_{\boldsymbol{s},c}$ and $\boldsymbol{s}$ is equal to the antenna azimuth in
which the radiation is at its maximum. Moreover, since mobile locations
$n_{\boldsymbol{s},c}$ are assumed to be uniformly distributed, we consider in
the remainder that $r_{\boldsymbol{s},c}$ is a RV uniformly distributed on the
interval $[0,\frac{2\delta}{3}U(\theta_{\boldsymbol{s},c}-\vartheta_{c})]$.
Fig. 1 illustrates the 3D beamforming model.

###  II-C Propagation model

To model the wireless channel, we consider the standard power-law path loss
model based on the distance between a mobile $m$ and a BS $\boldsymbol{s}$
such that the path loss $L(\boldsymbol{s},m)$ is given by

$L(\boldsymbol{s},m)=a|\boldsymbol{s}-m|^{2b},$ (7)

with $2b$ is the path loss exponent and $a$ is a propagation factor that
depends on the type of the environment (Indoor, Outdoor…).

In addition to the path loss, the received power by a mobile served in
downlink depends on the random channel effects, especially shadowing and fast
fading. Shadowing refers to the attenuation of the received signal power
caused by obstacles obstructing the propagation between the transmitter and
receiver. In this paper, we model the shadowing effect between a mobile
location $m$ and an interfering site $\boldsymbol{s}$ by a log-normal RV
$\chi_{\boldsymbol{s}}(m)=10^{\frac{Y_{\boldsymbol{s}}(m)}{10}}$ with
$Y_{\boldsymbol{s}}(m)$ is a Normal RV with mean
$\mathbb{E}(Y_{\boldsymbol{s}}(m))=0$ and variance $\sigma^{2}$. The shadowing
effect between $m$ and the serving site $\boldsymbol{s}_{0}$ is denoted by
$\chi_{0}$. This sequence of RVs are assumed to be independent and identically
distributed for all $(\boldsymbol{s},m)$.

Figure 1: 3D beamforming illustration

On the other hand, fast fading random model is not considered in this paper.
Its effect can be compensated through link level performing that maps the
$SINR$ to the throughput ($Th$). Also, for an AWGN (Additive Gaussian Noise
Channel), Shannon’s formula provides the relation between $SINR$ and $Th$.
Hence, the fast fading effect can be compensated by using a modified Shannon’s
formula to have $Th=K_{1}log_{2}(1+K_{2}SINR)$, with $K_{1}$ and $K_{2}$ are
constants calibrated from practical systems [12].

Therefore, the received power from a BS $\boldsymbol{s}$, transmitting with a
power level $P$, in a mobile location $m$ is expressed by

$P_{r}(m,\boldsymbol{s})=\frac{PAG_{\boldsymbol{s}}(m)\chi_{\boldsymbol{s}}(m)}{L(\boldsymbol{s},m)},$
(8)

with $A$ is the antenna gain and $G_{\boldsymbol{s}}(m)$ is the antenna
radiation pattern from $\boldsymbol{s}$ received at the mobile location $m$.

##  III Characterization of antenna beamforming radiation pattern
$G_{\boldsymbol{s}}(m)$

It is obvious from (4) that $G_{\boldsymbol{s}}(m)$ is a RV that depends on
the three RVs: $\alpha_{\boldsymbol{s},c}$, $\phi_{\boldsymbol{s},c}$ and
$r_{\boldsymbol{s},c}$. Also, one can notice that $V(\phi_{\boldsymbol{s},c})$
is a RV that depends on the RV $H(\alpha_{\boldsymbol{s},c})$. Therefore, to
characterize $G_{\boldsymbol{s}}(m)$, we start first by deriving the
probability density function (PDF) of $H(\alpha_{\boldsymbol{s},c})$ and the
PDF of $V(\phi_{\boldsymbol{s},c})$ conditionally on
$H(\alpha_{\boldsymbol{s},c})$, denoted respectively by
$f_{H_{\boldsymbol{s},c}}(h)$ and
$f_{V_{\boldsymbol{s},c}|H_{\boldsymbol{s},c}}(v)$. To do so, we shall use the
following lemma that gives the PDF of a transformed RV by a bijective
function.

######  Lemma 1.

Let $X$ be a RV and $f_{X}$ its PDF defined on an interval [a,b]. Let $Y$ be a
RV such that $Y=g(X)$ with $g$ is a bijective function. The PDF of $Y$ $f_{Y}$
is given by

$f_{Y}(y)=f_{X}(g^{-1}(Y))\left|\frac{dg^{-1}(y)}{dy}\right|\mathds{1}_{[g(a)\wedge
g(b),g(a)\vee g(b)]}(y)$ (9)

where $g^{-1}$ is the inverse function of $g$, $g(a)\wedge
g(b)=min(g(a),g(b))$ and $g(a)\vee g(b)=max(g(a),g(b))$.

The proof of this lemma is not provided here. To obtain the result, one can
calculate the PDF by distinguishing between the case when $g$ is increasing
and the case when it is decreasing.

Using lemma 1, the PDF $f_{\alpha_{\boldsymbol{s},c}}$ of the RV
$\alpha_{\boldsymbol{s},c}$ is given by

$f_{\alpha_{\boldsymbol{s},c}}(\alpha)=\frac{3}{2\pi}\mathds{1}_{[\psi(m,\boldsymbol{s})-\frac{2\pi}{3}c,\psi(m,\boldsymbol{s})+\frac{2\pi}{3}(1-c)]}(\alpha).$
(10)

Similarly, from equation (6), we can see that $\phi_{\boldsymbol{s},c}$ is the
transformation of the uniform RV $r_{\boldsymbol{s},c}$ by the function
$g(x)=atan(\frac{l_{b}}{|m-\boldsymbol{s}|})-atan(\frac{l_{b}}{x})$. Also,
this RV depends on $\alpha_{\boldsymbol{s},c}$. One can easily verify that $g$
is strictly increasing on the interval
$[0,\frac{2\delta}{3}U(\theta_{\boldsymbol{s},c}-\vartheta_{c})]$ and its
inverse function $g^{-1}$ is given by

$g^{-1}(y)=\frac{l_{b}}{tan(atan(\frac{l_{b}}{|m-\boldsymbol{s}|})-y)}.$ (11)

Hence, the PDF of $\phi_{\boldsymbol{s},c}$ conditionally on
$\alpha_{\boldsymbol{s},c}$, denoted by
$f_{\phi_{\boldsymbol{s},c}|\alpha_{\boldsymbol{s},c}}(\phi)$, is given by

$\displaystyle f_{\phi_{\boldsymbol{s},c}|\alpha_{\boldsymbol{s},c}}(\phi)$
$\displaystyle=\frac{3}{2\delta
U(\theta_{\boldsymbol{s},c}-\vartheta_{c})}\Big{(}1+\frac{1}{\tan^{2}(\phi-
atan(\frac{l_{b}}{|m-\boldsymbol{s}|}))}\Big{)}$
$\displaystyle\mathds{1}_{[atan(\frac{-|m-\boldsymbol{s}|}{l_{b}}),atan(\frac{2\delta
l_{b}U(\theta_{\boldsymbol{s},c}-\vartheta_{c})-3l_{b}|m-\boldsymbol{s}|}{2\delta|m-\boldsymbol{s}|U(\theta_{\boldsymbol{s},c}-\vartheta_{c})+3l_{b}^{2}})]}(\phi)$
(12)

Now, to characterize $G_{\boldsymbol{s}}(m)$, we apply once again Lemma 1 to
$\alpha_{\boldsymbol{s},c}$ and $\phi_{\boldsymbol{s},c}$ transformed by the
function $g$ such that $g=H$ for $\alpha_{\boldsymbol{s},c}$ and $g=V$ for
$\phi_{\boldsymbol{s},c}$. Thence, using lemma 1 and equations (10) and (12)
we obtain

$\displaystyle f_{H_{\boldsymbol{s},c}}(h)$
$\displaystyle=\frac{-3h^{\frac{-1-2w_{h}}{2w_{h}}}}{4\pi
w_{h}\sqrt{1-h^{\frac{-1}{w_{h}}}}}\mathds{1}_{[h_{1}\wedge h_{2},h_{1}\vee
h_{2}]}(h),$ (13)

with $h_{1}=H(arg(m-\boldsymbol{s})-\frac{2\pi}{3}c)$ and
$h_{2}=H(arg(m-\boldsymbol{s})+\frac{2\pi}{3}(1-c))$. And

$\displaystyle f_{V_{\boldsymbol{s},c}|H_{\boldsymbol{s},c}}(v)$
$\displaystyle=\Big{(}1+\frac{1}{\tan^{2}(acos(v^{\frac{-1}{2w_{v}}})-atan(\frac{l_{b}}{|m-\boldsymbol{s}|}))}\Big{)}\times$
$\displaystyle\frac{-3v^{\frac{-1-2w_{v}}{2w_{v}}}}{4w_{v}\delta
U(\theta_{\boldsymbol{s},c}-\vartheta_{c})\sqrt{1-v^{\frac{-1}{w_{v}}}}}\mathds{1}_{[v_{1}\wedge
v_{2},v_{1}\vee v_{2}]}(v),$ (14)

with $v_{1}=V(atan(\frac{-|m-\boldsymbol{s}|}{l_{b}}))$ and
$v_{2}=V(atan(\frac{2\delta
l_{b}U(\theta_{\boldsymbol{s},c}-\vartheta_{c})-3l_{b}|m-\boldsymbol{s}|}{2\delta|m-\boldsymbol{s}|U(\theta_{\boldsymbol{s},c}-\vartheta_{c})+3l_{b}^{2}}))$.

Moreover, the joint PDF of $H(\alpha_{\boldsymbol{s},c})$ and
$V(\phi_{\boldsymbol{s},c})$ denoted by
$f_{H_{\boldsymbol{s},c},V_{\boldsymbol{s},c}}$ is given by

$f_{H_{\boldsymbol{s},c},V_{\boldsymbol{s},c}}(h,v)=f_{V_{\boldsymbol{s},c}|H_{\boldsymbol{s},c}}(v)f_{H_{\boldsymbol{s},c}}(h).$
(15)

To calculate the PDF of
$Z_{h,v}=H(\alpha_{\boldsymbol{s},c})V(\phi_{\boldsymbol{s},c})$, one can use
the Mellin transform of the distribution of $Z_{h,v}$, denoted by
$f_{Z_{h,v}}$, defined by

$\displaystyle\mathcal{M}f_{Z_{h,v}}(s)$
$\displaystyle=\mathbb{E}[Z_{h,v}^{s-1}]=\int\int
h^{s-1}v^{s-1}f_{H_{\boldsymbol{s},c},V_{\boldsymbol{s},c}}(h,v)dhdv$
$\displaystyle=\int h^{s-1}\big{(}\int
v^{s-1}f_{V_{\boldsymbol{s},c}|H_{\boldsymbol{s},c}}(v)dv\big{)}f_{H_{\boldsymbol{s},c}}(h)dh$
(16)

Then, the PDF of the product of the horizontal and the vertical patterns
$f_{Z_{h,v}}$ can be obtained by using the inverse Mellin transform as follows

$f_{Z_{h,v}}(z)=\frac{1}{2\pi i}\int z^{-s}\mathcal{M}f_{Z_{h,v}}(s)ds.$ (17)

Finally the distribution of $G_{\boldsymbol{s}}(m)$ can be obtained by the
convolution of $f_{Z_{h,v}}$ for $c\in\\{1,2,3\\}$.

The mathematical expectation of $G_{\boldsymbol{s}}(m)$ is defined by

$\mathbb{E}[Gs(m)]=\eta\sum_{c=1}^{3}\mathbb{E}[H(\alpha_{\boldsymbol{s},c})V(\phi_{\boldsymbol{s},c})],$
(18)

where $\mathbb{E}[H(\alpha_{\boldsymbol{s},c})V(\phi_{\boldsymbol{s},c})]$ is
calculated by taking $s=2$ in equation (16).

When the downtilt is taken constant, the vertical antenna radiation pattern is
no more a RV. Thus, the explicit expression of $\mathbb{E}[Gs(m)]$
conditionally on $m$ can be written as

$\displaystyle\mathbb{E}[Gs(m)]$ $\displaystyle=\frac{3\eta
V(\phi_{\boldsymbol{s},c})}{2\pi}\sum_{c=1}^{3}\int_{\upsilon_{c}-\frac{\pi}{3}}^{\upsilon_{c}+\frac{\pi}{3}}\cos^{-2w_{h}}(\theta-\psi(m,\boldsymbol{s}))d\theta$
$\displaystyle=\frac{3\eta
V(\phi_{\boldsymbol{s},c})}{\pi}\int_{0}^{\pi}\cos^{-2w_{h}}(\theta)d\theta.$
(19)

Equation (19) comes from the $2\pi-$periodicity of the function $\cos$ and
Chasles’s formula.

Finally, by using
$\int_{0}^{\frac{\pi}{2}}cos^{z}(x)=\frac{\sqrt{\pi}\Gamma(\frac{z+1}{2})}{2\Gamma(\frac{z}{2}+1)}$
for all complex number $z$ such that $\Re(z)>-1$, the explicit expression of
the mathematical expectation of $G_{\boldsymbol{s}}(m)$ is given by

$\mathbb{E}[Gs(m)]=\frac{3\eta
V(\phi_{\boldsymbol{s},c})\Gamma(\frac{1}{2}-w_{h})}{\sqrt{\pi}\Gamma(1-w_{h})}$
(20)

with $\Gamma(.)$ is the Euler Gamma function.

##  IV Interference characterization (1)

A mobile located at a position $m$ in the first sector ($c=1$) of the serving
site $\boldsymbol{s}_{0}$ receives interference from the co-sectors and also
from the other interfering sites in $\Lambda^{*}$. We define the individual
$ISR$, denoted by $\mathcal{I}_{\boldsymbol{s}}(m)$, as the received power
from an interfering site $\boldsymbol{s}$ divided by the useful power received
by $m$ from the serving cell. Its expression is given by

$\displaystyle\mathcal{I}_{\boldsymbol{s}}(m)$
$\displaystyle=\frac{P_{r}(m,\boldsymbol{s})}{P_{r}(m,\boldsymbol{s}_{0})}$
$\displaystyle=r^{2b}|\boldsymbol{s}-m|^{-2b}G_{\boldsymbol{s}}(m)\tilde{\chi_{\boldsymbol{s}}},$
(21)

where
$\tilde{\chi_{\boldsymbol{s}}}=10^{\frac{\tilde{Y}_{\boldsymbol{s}}}{10}}$ is
a log-normal RV representing the ratio of the shadowing effect from
interfering sites and the shadowing effect from the serving site (The ratio of
two log-normal RVs is a log-normal RV), with $\tilde{Y}_{\boldsymbol{s}}$ is a
Normal RV with mean 0 and variance $\tilde{\sigma}^{2}$. Also, we define the
cumulative $ISR$ from all the interfering sites including the two other
sectors of the serving site $\boldsymbol{s}_{0}$ as the sum over
$\boldsymbol{s}\in\Lambda$ of all the individual ISRs. It is expressed as

$\mathcal{I}(m)=-1+\sum_{\boldsymbol{s}\in\Lambda}r^{2b}|\boldsymbol{s}-m|^{-2b}G_{\boldsymbol{s}}(m)10^{\frac{\tilde{Y}_{\boldsymbol{s}}}{10}}.$
(22)

$\mathcal{I}(m)$ is an infinite sum of independent positive RVs not
identically distributed. Hence according to Theorem 9.2.a of [13],

$\mathbb{E}[\mathcal{I}(m)]=-1+\mathbb{E}[10^{\frac{\tilde{Y}_{\boldsymbol{s}}}{10}}]\sum_{\boldsymbol{s}\in\Lambda}r^{2b}|\boldsymbol{s}-m|^{-2b}\mathbb{E}[G_{\boldsymbol{s}}(m)].$

In [7], it has been shown that
$\sum_{\boldsymbol{s}\in\Lambda^{*}}r^{2b}|\boldsymbol{s}-m|^{-2b}$ is a
convergent series on $x=\frac{r}{\delta}$ that can be approximated as follows

$\sum_{\boldsymbol{s}\in\Lambda^{*}}r^{2b}|\boldsymbol{s}-m|^{-2b}\approx\frac{6x^{2b}}{\Gamma(b)^{2}}\sum_{h=0}^{+\infty}\frac{\Gamma(b+h)^{2}}{\Gamma(h+1)^{2}}\omega(b+h)x^{2h}$
(23) $\text{ where
}\omega(z)=3^{-z}\zeta(z)\left(\zeta(z,\frac{1}{3})-\zeta(z,\frac{2}{3})\right),$

with $\zeta(.)$ and $\zeta(.,.)$ are respectively the Riemann Zeta and Hurwitz
Riemann Zeta functions [14].

Since $G_{\boldsymbol{s}}(m)\leq 1$, we have
$\mathbb{E}(G_{\boldsymbol{s}}(m))<1$. By using (23), we can easily prove that
$\mathbb{E}[\mathcal{I}(m)]<\infty$. Hence, according to Theorem 9.2.b of
[13], $\mathcal{I}(m)$ converges almost surely.

Unfortunately, the central limit theorem (CLT) can not be applied in this
case. Also, the generalized CLT known as Lyapunov CLT and Lindeberg CLT
conditions are not verified here. Hence, $\mathcal{I}(m)$ can not be
approximated by a Gaussian RV.

Additionally, we define the DL coverage probability $\varPi$ as the
probability that a mobile user $m$ is able to achieve a threshold $SINR$ ,
denoted by $\gamma$, during the DL transmission

$\varPi(\gamma)=\mathbb{P}(\Theta(m)>\gamma),$ (24)

where $\Theta(m)$ is the $SINR$ of $m$ and it can be expressed in terms of the
cumulative $ISR$ $\mathcal{I}(m)$ as follows

$\Theta(m)=\frac{1}{\mathcal{I}(m)+y_{0}},$ (25)

with $y_{0}=\frac{aNr^{2b}}{AP\chi_{0}}$ and $N$ is the thermal noise power.

Finally, the throughput is calculated using the upper bound of the well known
Shannon’s formula for a MIMO system $Tx\times Rx$, with $Tx$ and $Rx$ are
respectively the number of transmit and receive antennas. Hence the throughput
$C(m)$ of a user located at a position $m$ can be written as

$C(m)=(Tx\wedge Rx)B_{w}log_{2}(1+\Theta(m)),$ (26)

with $B_{w}$ is the system bandwidth.

##  V Numerical results and discussion

For numerical purpose, we consider 5 rings of interfering sites with an inter
site distance $\delta=0.750km$. All BSs are assumed to have the same height
$l_{b}=30m$, transmit with a power level $P=40dBm$ and operate in a bandwidth
$B_{w}$ of $20MHz$. The antenna gain is set to be $A=17dBi$. Also, the
downlink thermal noise power is calculated for $B_{w}$ and set to $N=-93dBm$.
The path loss exponent is considered to be $2b=3.5$, the propagation factor of
an outdoor environment is $a=130dB$ and the standard deviation of the log-
normal shadowing is $\sigma=5.5dB$. Finally, we assume that we have $2Rx$
antennas in user’s terminals, the number of $Tx$ antennas depends on the
chosen half power beam width ($\theta_{h3dB}$ and $\theta_{v3dB}$). This
number with beamforming is greater than 2 and thus, the number of possible
transmission layers is at most 2.

We simulate the 3D beamforming model in MATLAB considering four values of
$\theta_{h3dB}$ ($30\degree$, $20\degree$, $14\degree$ and $8\degree$) and a
vertical half power beam width $\theta_{v3dB}=8\degree$. We compare it to a
simulated hexagonal tri-sectorized network without beamforming mechanisms with
$\theta_{h3dB}=65$, $\theta_{v3dB}=32$ and a fixed downtilt angle $8\degree$.

We plot in Fig. 2 the empirical coverage probability (CCDF of $SINR$) curves
obtained by using Monte Carlo simulations for $20000$ mobile locations $m$. As
we can see, 3D beamforming enhances significantly performance. For instance,
with an $SINR$ threshold of $10dB$, the coverage probability increases from
$66\%$ to $99\%$ when 3D beamforming is deployed with a horizontal beam width
of $\theta_{h3dB}=8\degree$. Moreover, it can be observed that the coverage
probability increases as the beam width decreases. Actually, the beam width is
related to the number of transmit antennas used by BSs. When this number
increases, the signal is focused on a specific zone of the cell. Hence,
interference coming from neighboring sites are reduced significantly as the
beam width decreases and the number of transmit antennas increases. This leads
to an enhancement of $SINR$ and thus an enhancement of the coverage
probability.

Figure 2: Coverage probability: 3D beamforming impact.

Similarly in Fig. 3, we plot the user throughput as a function of the average
load over interfering sites considering the 3D beamforming with two values of
$\theta_{h3dB}$ ($16\degree$ and $8\degree$) and $\theta_{v3dB}=8\degree$. We
compare results with the case of tri-sectorized hexagonal network without
beamforming. As we can observe, with a tri-sectorized hexagonal network
without 3D beamforming, the throughput is more sensitive to the average load
variations over interfering sites and it decreases by almost $30\%$ when the
average load increases from $1\%$ to $100\%$. With 3D beamforming, one can
notice that the throughput increases significantly compared to the case
without beamfroming. Also, it increases as the beam width decreases, which is
in agreement with results of Fig. 2. Additionally, we can see that the
sensitivity to the average load and interference decreases in the case of 3D
beamforming, especially with small half power beam widths i.e., when the
number of transmit antennas increases.

Fig. 4 shows a comparison between the coverage probability of a network
adopting the 3D beamforming according to our model and the one of a network
using a 2D beamforming where only a random horizontal radiation pattern is
considered. The vertical component is taken constant and included in the
antenna gain. Once again, we can notice that a small beam width leads to an
increase of the coverage probability for the both models. Moreover, it is
obvious that performance in terms of $SINR$ with 3D beamforming are better
than 2D beamforming. Actually, most BSs use a linearly arranged array of
antennas placed at the top of BSs. Unfortunately, the number of antennas can
not be increased because of size constraints. Hence the interest of FD-MIMO,
based on a 2D array of antennas, that offers the possibility to increase the
number of transmit antennas and gives extra degrees of freedom in order to
improve significantly the wireless system performance. Also, it provides the
capability to adapt dynamically beam patterns in the horizontal and vertical
dimensions.

Figure 3: Throughput variation with the average load over interfering sites:
comparison between 3D beamforming model and hexagonal tri-sectorized network.
Figure 4: Coverage probability comparison: 3D beamforming vs 2D beamforming.

Finally in Fig. 5, we plot the coverage probability with the 3D beamforming
model, presented in this paper, for 2 values of $\theta_{h3dB}$ ($8\degree$
and $14\degree$) and $\theta_{v3dB}=8\degree$. We compare it with the coverage
probability of the same network, but instead of taking the downtilt angle
$\tilde{\phi}_{\boldsymbol{s},c}$ as a function of the mobile location
$n_{\boldsymbol{s},c}$, we consider two values of this angle,
$\tilde{\phi}_{\boldsymbol{s},c}=4\degree$ and
$\tilde{\phi}_{\boldsymbol{s},c}=8\degree$, close to the values used in
practical systems. One can observe that when the horizontal beam width is set
to $14\degree$, the 3D beamforming model with variable downtilt angle has
better performance than the case of fixed downtilt for the two values of
$\tilde{\phi}_{\boldsymbol{s},c}$. However, with a horizontal beam width of
$8\degree$, we can notice that the coverage probability when
$\tilde{\phi}_{\boldsymbol{s},c}=8\degree$ is getting closer to the one of the
network with 3D beamforming. Hence, using a large number of transmit antennas
to concentrate the beam to a specific location, especially in the horizontal
dimension, leads to a significant enhancement of performances. Moreover, for
the vertical dimension, it has been shown in several papers that there exists
an optimal downtilt angle for which the performance are enhanced
significantly. In practical systems, we take always a downtilt close to
6$\degree$.

Figure 5: Downtilt $\tilde{\phi}_{\boldsymbol{s},c}$ impact: variable vs fixed
downtilt.

##  VI Conclusions

In this paper, we have proposed an analytical model for 3D beamforming where
antenna radiation patterns depend on the spatial distribution of users’
locations in the plane. We have shown, through system level simulations, that
the 3D beamforming reduces significantly interference and thus enhances the
$SINR$ and users throughput in downlink. A comparison between the proposed 3D
model and the traditional 2D beamforming, where only the azimuthal plane is
considered, shows better performance with 3D beamforming. Hence the importance
of FD-MIMO, where a large number of antennas are arranged in a 2D array, that
makes possible to adapt beamforming also in the vertical dimension. A further
extension of this work can include some analytical results regarding the
distribution of beamforming radiation and the derivation of an upper bound of
the coverage probability using concentration inequalities. Also, one can study
the imperfection of beam steering especially for indoor users by considering
the same assumptions as this work.

## References

  * [1] A. D. Gandhi, “Significant Gains in Coverage and Downlink Capacity From Optimal Antenna Downtilt for Closely-Spaced cells in wireless networks,” in _Wireless and Optical Communication Conference (WOCC), 2014 23rd_. IEEE, 2014, pp. 1–6.
  * [2] T. Bai and R. W. Heath, “Coverage and Rate Analysis for Millimeter-Wave Cellular Networks,” _IEEE Transactions on Wireless Communications_ , vol. 14, no. 2, pp. 1100–1114, 2015.
  * [3] J. Koppenborg, H. Halbauer, S. Saur, and C. Hoek, “3d Beamforming Trials With an Active Antenna Array,” in _Smart Antennas (WSA), 2012 International ITG Workshop on_. IEEE, 2012, pp. 110–114.
  * [4] H. Halbauer, S. Saur, J. Koppenborg, and C. Hoek, “Interference Avoidance With Dynamic Vertical Beamsteering in Real Deployments,” in _Wireless Communications and Networking Conference Workshops (WCNCW), 2012 IEEE_. IEEE, 2012, pp. 294–299.
  * [5] J. Yang, M. Ding, G. Mao, Z. Lin, D.-g. Zhang, and T. H. Luan, “Optimal Base Station Antenna Downtilt in Downlink Cellular Networks,” _arXiv preprint arXiv:1802.07479_ , 2018.
  * [6] N. Seifi, M. Coldrey, M. Matthaiou, and M. Viberg, “Impact of Base Station Antenna Tilt on The Performance of Network MIMO Systems,” in _IEEE 75th Vehicular Technology Conference, VTC Spring 2012, Yokohama, 6 May-9 June 2012_ , 2012.
  * [7] R. Nasri and A. Jaziri, “Analytical Tractability of Hexagonal Network Model With Random User Location,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 5, pp. 3768–3780, 2016.
  * [8] J. Rachad, R. Nasri, and L. Decreusefond, “Interference analysis in dynamic tdd system combined or not with cell clustering scheme,” in _2018 IEEE 87th Vehicular Technology Conference (VTC Spring)_. IEEE, 2018, pp. 1–5.
  * [9] J. G. Andrews, F. Baccelli, and R. K. Ganti, “A Tractable Approach to Coverage and Rate in Cellular Networks,” _IEEE Transactions on communications_ , vol. 59, no. 11, pp. 3122–3134, 2011.
  * [10] B. Błaszczyszyn and M. K. Karray, “Spatial Distribution of The SINR in Poisson Cellular Networks With Sector Antennas,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 1, pp. 581–593, 2016.
  * [11] P. E. Mogensen, K. I. Pedersen, P. Leth-Espensen, B. Fleury, F. Frederiksen, K. Olesen, and S. L. Larsen, “Preliminary measurement results from an adaptive antenna array testbed for gsm/umts,” in _1997 IEEE 47th Vehicular Technology Conference. Technology in Motion_ , vol. 3. IEEE, 1997, pp. 1592–1596.
  * [12] P. Mogensen, W. Na, I. Z. Kovács, F. Frederiksen, A. Pokhariyal, K. I. Pedersen, T. Kolding, K. Hugl, and M. Kuusela, “LTE Capacity Compared to The Shannon Bound,” in _Vehicular Technology Conference, 2007. VTC2007-Spring. IEEE 65th_. IEEE, 2007, pp. 1234–1238.
  * [13] J. Jacod and P. Protter, _Probability Essentials_. Springer Science & Business Media, 2012.
  * [14] M. Abramowitz and I. A. Stegun, _Handbook of Mathematical Functions: with formulas, graphs, and mathematical tables_. Courier Corporation, 1964, no. 55.


# A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squares

Coralia Cartis  Jaroslav Fowkes  Zhen Shao

###### Abstract

We propose a Randomised Subspace Gauss-Newton (R-SGN) algorithm for solving
nonlinear least-squares optimization problems, that uses a sketched Jacobian
of the residual in the variable domain and solves a reduced linear least-
squares on each iteration. A sublinear global rate of convergence result is
presented for a trust-region variant of R-SGN, with high probability, which
matches deterministic counterpart results in the order of the accuracy
tolerance. Promising preliminary numerical results are presented for R-SGN on
logistic regression and on nonlinear regression problems from the CUTEst
collection.

optimization,least-squares

##  1 Introduction

We aim to solve the nonlinear least-squares problem

$\displaystyle\min_{x\in\mathbb{R}^{d}}f(x)=\frac{1}{2}\sum_{i=1}^{n}\norm{r_{i}(x)}_{2}^{2}=\frac{1}{2}\|r(x)\|_{2}^{2}$
(1)

where $r=(r_{1},\dots,r_{n}):\mathbb{R}^{d}\to\mathbb{R}^{n}$ is a smooth
vector of nonlinear (possibly nonconvex) residual functions. We define the
Jacobian (matrix of first order derivatives) as

$\displaystyle
J(x)=\left(\partialderivative{r_{i}(x)}{x_{j}}\right)_{ij}\in\mathbb{R}^{n\times
d}$

and can then compactly write the gradient as $\gradient f(x)=J(x)^{T}r(x)$.
The classical Gauss-Newton (GN) algorithm simply applies Newton’s method to
minimising $f$ with only the first-order $J(x)^{T}J(x)$ term in the Hessian,
dropping the second-order terms involving the Hessians of the residuals
$r_{i}$. Thus, at every iterate $x_{k}$, Gauss-Newton approximately minimises
the following convex quadratic local model

$\displaystyle f(x_{k})+\langle
J(x_{k})^{T}r(x_{k}),\hat{s}\rangle+\frac{1}{2}\langle\hat{s},J(x_{k})^{T}J(x_{k})\hat{s}\rangle$

over $\hat{s}\in\mathbb{R}^{d}$. In our approach, which we call Randomised
Subspace Gauss-Newton (R-SGN), we reduce the dimensionality of this model by
minimising in an $l$-dimensional randomised subspace
$\mathcal{L}\subset\mathbb{R}^{d}$, with $l\ll d$, by approximately minimising
the following reduced model

$\displaystyle f(x_{k})+\langle
J_{\mathcal{S}}(x_{k})^{T}r(x_{k}),s\rangle+\frac{1}{2}\langle
s,J_{\mathcal{S}}(x_{k})^{T}J_{\mathcal{S}}(x_{k})s\rangle$ (2)

over $s\in\mathbb{R}^{l}$, where $J_{\mathcal{S}}(x_{k})\in\mathbb{R}^{n\times
l}$ denotes the reduced Jacobian. Compared to the classical Gauss-Newton
model, this reduced model also offers the computational advantage that it only
needs to evaluate $l$ Jacobian actions, giving $J_{\mathcal{S}}(x_{k})$,
instead of the full Jacobian matrix $J(x_{k})$.

In its simplest form, $J_{\mathcal{S}}$ can be thought of as a random
subselection of columns of the full Jacobian $J$, which leads to variants of
our framework that are Block-Coordinate Gauss-Newton (BC-GN) methods. In this
case, for example, if the Jacobian were being calculated by finite-differences
of the residual $r$, only a small number of evaluations of $r$ along
coordinate directions would be needed; such a BC-GN variant has already been
used for parameter estimation in climate modelling (Tett et al., 2017).

##  2 Related Work and Motivation

Block-coordinate descent methods have been, by now, extensively studied,
especially for minimizing convex functions (Richtárik & Takáč, 2014), but not
only; the randomised nonmonotone block proximal-gradient method (Lu & Xiao,
2017) minimises the sum of a smooth (possibly nonconvex) function and a block-
separable (possibly nonconvex nonsmooth) function, with global rates of
convergence being provided for when the expected value of the (true) gradient
is sufficiently small. In a similar vein, Facchinei et al. (2015) propose a
general decomposition framework for the parallel optimization of the sum of a
smooth (possibly nonconvex) function and a block-separable nonsmooth convex
function. Both of these proposals are gradient descent frameworks, while for
improved and robust practical performance, (some) second-order information of
the objective function needs to be employed in the algorithm. As second-order
methods may be too computationally expensive for large-scale applications,
subspace variants have been devised; extensive literature exists on
deterministic choices such as Newton-CG (conjugate gradient) and Krylov
methods, both for calculating approximate Newton directions for general
optimization and approximate Gauss-Newton directions for nonlinear least-
squares (see for example, Nocedal & Wright, 2006; Gratton et al., 2007).
However, though these methods are really powerful and very much state-of-the-
art for inexact second-order methods, they still require (full) Hessian-vector
products, which may be too expensive for some applications (Tett et al.,
2017). Also, we are interested in using randomisation techniques for choosing
the subspace of minimization, in an attempt to exploit the benefits of
Johnson-Lindenstrauss (JL) Lemma-like results, that essentially reduce the
dimension of the optimization problem without loss of information. Such
sketching techniques have already been proposed, especially for convex
optimization, as we describe next. The sketched Newton algorithm (Pilanci &
Wainwright, 2017) requires a sketching matrix that is proportional to the rank
of the Hessian, which may be too computationally expensive. By contrast,
sketched online Newton (Luo et al., 2016) uses streaming sketches to scale up
a second-order method, comparable to Gauss–Newton, for solving online learning
problems. The randomised subspace Newton (Gower et al., 2019) efficiently
sketches the full Newton direction for a family of generalised linear models,
such as logistic regression. The stochastic dual Newton ascent algorithm in Qu
et al. (2016) requires a positive definite upper bound $M$ on the Hessian and
proceeds by selecting random principal submatrices of $M$ that are then used
to form and solve an approximate Newton system. The randomized block cubic
Newton method in Doikov & Richtárik (2018) combines the ideas of randomized
coordinate descent with cubic regularization and requires the optimization
problem to be block separable.

Here, we propose a randomized subspace Gauss-Newton method for nonlinear
least-squares problems, that, at each iteration, only needs a sketch of the
Jacobian matrix in the variable domain, which it then uses to solve a reduced
linear least-squares problem for the step calculation. To ensure global
convergence of the method, from any starting point, we include a trust-region
technique (and also have results for a quadratic regularization variant);
unlike most prior work, we focus on the general nonconvex case of problem (1).

##  3 The R-SGN Algorithm

As mentioned above, at each iterate $x_{k}$, $k\geq 0$, R-SGN uses Jacobian
actions $J_{\mathcal{S}}(x_{k})$ in an $l$-dimensional randomised subspace
$\mathcal{L}\subset\mathbb{R}^{d}$, $l\ll d$. To obtain these actions we draw
a random sketching matrix $S_{k}\in\mathbb{R}^{l\times d}$ from a chosen
random matrix distribution $\mathcal{S}$ at each iteration, and set

$J_{\mathcal{S}}(x_{k})\mathrel{\mathop{:}}=J(x_{k})S_{k}^{T}$

in the local model (2). This model is then approximately minimized over a
trust region ball, $\norm{s}_{2}\leq\Delta_{k}$, so that a typical Cauchy
decrease condition (see e.g. Conn et al., 2000) is satisfied,

$\displaystyle m_{k}(0)-m_{k}(s_{k})\geq
c_{1}\|g_{k}\|_{2}\min\left(\Delta_{k},\frac{\|g_{k}\|_{2}}{\|B_{k}\|_{2}}\right),$
(3)

for some constant $c_{1}>0$; where
$g_{k}\mathrel{\mathop{:}}=J_{\mathcal{S}}(x_{k})^{T}r(x_{k})$ and
$B_{k}\mathrel{\mathop{:}}=J_{\mathcal{S}}(x_{k})^{T}J_{\mathcal{S}}(x_{k})$.
The step is then either accepted or rejected depending on the ratio $\rho_{k}$
between the actual objective decrease and the decrease predicted by the model,

$\displaystyle\rho_{k}\mathrel{\mathop{:}}=\frac{f(x_{k})-f(x_{k}+S_{k}^{T}s_{k})}{f(x_{k})-m_{k}(s_{k})}.$
(4)

A full description of the R-SGN with trust region algorithm is provided in
Algorithm 1 below.

Algorithm 1 R-SGN with Trust Region

Input: $x_{0}\in\mathbb{R}^{d}$

Parameters:  $l<d$, $\eta\in(0,1)$, $0<\gamma_{1}<1<\gamma_{2}$, such that
$\gamma_{2}=\gamma_{1}^{-c}$ for some $c\in\mathbb{N}$,
$\Delta_{0}\in\mathbb{R}$.

for $k=0$ to $N$ do

Randomly draw a sketching matrix $S_{k}\in\mathbb{R}^{l\times d}$.

Compute step $s_{k}$ to approximately minimise the model (2) satisfying (3).

Compute decrease $\rho_{k}$ given by (4).

if $\rho_{k}\geq\eta$ then

$x_{k+1}=x_{k}+S_{k}^{T}s_{k}$

$\Delta_{k+1}=\gamma_{2}\Delta_{k}$

else

$\Delta_{k+1}=\gamma_{1}\Delta_{k}$

end if

end for

##  4 A global rate of convergence for R-SGN

We assume the following properties of the residual $r(x)$, the Jacobian $J(x)$
and the random sketching matrices $S_{k}$.

######  Assumption 1.

The residual $r$ is continuously differentiable, and $r$ and its Jacobian $J$
are Lipschitz continuous on $\mathbb{R}^{d}$.

######  Assumption 2.

Let $\epsilon_{S},\delta_{S}\in(0,1)$. At each iterate $x_{k}$, with
probability at least $1-\delta_{S}$, we have that

$\displaystyle\|S_{k}\gradient
f(x_{k})\|_{2}^{2}\geq(1-\epsilon_{S})\|\gradient f(x_{k})\|_{2}^{2},$ (5)

and

$\displaystyle\|S_{k}\|_{2}\leq S_{max}.$ (6)

######  Assumption 3.

The probability in Assumption 2 satisfies

$\displaystyle 1-\delta_{S}>c_{2},$ (7)

where $c_{2}=\frac{c+2}{2c+2}$, with $c$ being a user chosen parameter defined
in Algorithm 1. If $c=1$, i.e. we have $\gamma_{2}=\gamma_{1}^{-1}$ in
Algorithm 1, then $c_{2}=3/4$.

The following result shows that the R-SGN algorithm produces an iterate with
arbitrarily small $\|\gradient f(x_{k})\|_{2}$, with exponentially small
failure probability, in a quantifiable number of iterations.

######  Theorem 1.

Let Assumptions 1, 2, 3 hold. Let $\epsilon>0$, and $\delta_{1}\in(0,1)$ such
that $(1-\delta_{S})(1-\delta_{1})>c_{2}$. Then the R-SGN algorithm takes at
most

$\displaystyle
N\leq\frac{1}{(1-\delta_{S})(1-\delta_{1})-c_{2}}\mathcal{O}\left(\frac{f(x_{0})-f^{*}}{(1-\epsilon_{S})\epsilon^{2}}\right)$
(8)

iterations and evaluations of the residual and sketched Jacobian such that
$\min_{k\leq N}\|\gradient f(x_{k})\|_{2}\leq\epsilon$, with probability at
least $1-e^{-\frac{\delta_{1}^{2}}{2}(1-\delta_{S})N}$.

We note that as a function of the tolerance $\epsilon$, this bound matches
deterministic complexity bounds for first-order and Gauss-Newton methods
(Cartis et al., 2012), despite having only partial Jacobian information
available at each iteration.

We also have similar global rates of convergence results for R-SGN with
quadratic regularization techniques instead of trust region. There is no
convexity or special structure requirement on $f$ or $r$ in our results. Our
proof employs techniques from convergence/complexity analysis of optimisation
methods based on probabilistic models in Cartis & Scheinberg (2018); Gratton
et al. (2018). However, our result only assumes a weaker condition, namely,
that the ’model gradient’ $S_{k}\gradient f(x_{k})$ has similar norm to that
of the full gradient $\gradient f(x_{k})$, while previous results assume the
model gradient itself approximates the true gradient.

###  4.1 Discussion on generating the random matrix $S_{k}$

We give a few suitable choices of the random matrix ensemble $\cal{S}$
satisfying Assumption 2.

######  Definition 1 (Non-uniformity dependent oblivious JL embedding).

Let $\epsilon_{S},\delta_{S}\in(0,1)$, $\nu_{S}\in(0,1]$, $d\in\mathbb{N}$. A
distribution on $S\in\mathbb{R}^{l\times d}$ with
$l=l(d,\nu_{S},\epsilon_{S},\delta_{S})$ is a
$(\nu_{S},\epsilon_{S},\delta_{S})$-oblivious JL embedding if, given fixed
$y\in\mathbb{R}^{d}$ with $\|y\|_{\infty}/\|y\|_{2}\leq\nu_{S}$, we have that
with probability at least $1-\delta_{S}$, a matrix $S$ drawn from the
distribution satisfies

$\displaystyle(1-\epsilon_{S})\|y\|_{2}^{2}\leq\|Sy\|_{2}^{2}\leq(1+\epsilon_{S})\|y\|_{2}^{2}.$
(9)

Thus we can satisfy (5) with probability at least $1-\delta_{S}$ at each R-SGN
iteration if our random matrix distribution $\cal{S}$ is a
$(\nu_{S},\epsilon_{S},\delta_{S})$-oblivious JL embedding, and we have that
$\|\gradient f(x_{k})\|_{\infty}/\|\gradient f(x_{k})\|_{2}\leq\nu_{S}$ for
all iterates $x_{k}$ by taking $y=\gradient f(x_{k})$ in Definition
1.111$\|\gradient f(x_{k})\|_{\infty}/\|\gradient f(x_{k})\|_{2}\leq\nu_{S}$
is not required if $\nu_{S}=1$, as then the inequality always holds.

The well studied oblivious JL-embedding (see Woodruff, 2014), is a special
case of Definition 1 with $\nu_{S}=1$. In particular, we have the following
result.

######  Lemma 1 (Dasgupta & Gupta, 2003).

We say $S\in\mathbb{R}^{l\times d}$ is a Gaussian matrix if $S_{ij}$ are
identically distributed as $N(0,{l}^{-1/2})$. Let
$\epsilon_{S},\delta_{S}\in(0,1)$, then the distribution of Gaussian matrices
$S\in\mathbb{R}^{l\times d}$ with
$l=\mathcal{O}(|\log\delta_{S}|/\epsilon_{S}^{2})$ is an
$(1,\epsilon_{S},\delta_{S})$-oblivious JL embedding.

The following hashing/sparse embedding matrices are also
$(1,\epsilon_{S},\delta_{S})$-oblivious JL embeddings.

######  Lemma 2 (Kane & Nelson, 2014; Cohen et al., 2018).

We define $S\in\mathbb{R}^{l\times d}$ to be a s-hashing matrix if,
independently for each $j\in[d]$, we sample without replacement
$i_{1},i_{2},\dots,i_{s}\in[l]$ uniformly at random and let $S_{i_{k}j}=\pm
1/\sqrt{s}$, $k=1,2,\dots,s$. Let $\epsilon_{S},\delta_{S}\in(0,1)$, then the
distribution of s-hashing matrices $S\in\mathbb{R}^{l\times d}$ with
$s=\mathcal{O}(|\log\delta_{S}|/\epsilon_{S})$ and
$l=\mathcal{O}\left(|\log\delta_{S}|/\epsilon_{S}^{2}\right)$ is an
$(1,\epsilon_{S},\delta_{S})$-oblivious JL embedding.

The distribution of sampling matrices is not usually an oblivious JL
embedding. However it can be shown to be a non-uniformity dependent oblivious
JL embedding.

######  Lemma 3.

We define $S\in\mathbb{R}^{l\times d}$ to be a sampling matrix if,
independently for each $i\in[l]$, we sample $j\in[d]$ uniformly at random and
let $S_{ij}=(d/l)^{-1/2}$. Let $\epsilon_{S},\delta_{S},\nu_{S}\in(0,1)$, then
the distribution of sampling matrices $S\in\mathbb{R}^{l\times d}$ with
$l=\mathcal{O}(d\nu_{S}^{2}|\log\delta_{S}|/\epsilon_{S}^{2})$ is an
$(\epsilon_{S},\delta_{S},\nu_{S})$-oblivious JL embedding.

Note that R-SGN with a sampling choice for $S_{k}$ leads to block-coordinate
variants (BC-GN) of R-SGN, with fixed block size $l$.

The above properties of Gaussian and hashing matrices imply that their
embedding dimension $l$ is independent of the variable dimension $d$, while
for sampling matrices $l\propto d\nu_{S}^{2}$; this has direct implications on
the size of the sketch in R-SGN; in particular, it does not have to grow
asymptotically. However, when $\|\gradient f(x_{k})\|_{\infty}\leq
Cd^{-1/2}\|\gradient f(x_{k})\|_{2}$ for some constant $C$ (thus the maximum
gradient component is no larger than a constant multiple of the average
gradient component), then sampling matrices also have an embedding dimension
$l$ that is independent of the variable dimension $d$. Thus the more uniformly
distributed the magnitude of the gradient entries, the better sampling works
in R-SGN (namely, in BC-GN), ensuring a.s. global convergence.

It can be easily verified that (6) is satisfied for sampling and hashing
matrices. For Gaussian matrices, one may use the non-asymptotic bound
established for the maximum singular value of Gaussian matrices in Rudelson &
Vershynin (2010) to show $\|S_{k}\|_{2}$ is bounded with high probability.
Assumption 2 can then be satisfied with a union bound.

##  5 Preliminary Numerical Results

For simplicity, in our performance evaluation of R-SGN, we use sampling
sketching matrices as defined in Lemma 3, which leads to a BC-GN variant of
R-SGN. We first consider logistic regression, written in the form (1), by
letting $r_{i}(x)=\ln(1+\exp(-y_{i}a_{i}^{T}x))$, where
$a_{i}\in\mathbb{R}^{d}$ are the observations and $y_{i}\in\\{-1,1\\}$ are the
class labels; we also include a quadratic regularization term
$\lambda\|x\|_{2}^{2}$ by treating it as an additional residual.

Figure 1: R-SGN on the chemotherapy dataset

Figure 2: R-SGN on the gisette dataset

We first test on the chemotherapy and gisette datasets from OpenML (Vanschoren
et al., 2013) for $100$ iterations with $\lambda=10^{-10}$, using block sizes
of 0.1%, 0.5%, 1%, 5% and 100% of the original for the $61,359$ dimensional
chemotherapy dataset and the $5,000$ dimensional gisette dataset; in a similar
testing setup to Gower et al. (2019). As R-SGN is randomised, we perform five
runs of the algorithm for each block size starting at $x_{0}=0$. We terminate
once the objective $f(x_{k})$ goes below $10^{-5}$ and plot $f(x_{k})$ against
iterations and runtime in each Figure. On the chemotherapy dataset, we see
from Figure 1 that we are able to get comparable performance to full GN
($d=61,359$ in purple) using only $1\%$ of the original block size ($l=614$ in
green) at $1/20$th of the runtime. For the gisette dataset, we see from Figure
2 that similarly, we are able to get good performance compared to GN
($d=5,000$ in purple) using $5\%$ of the original block size ($l=250$ in red)
at $1/60$th of the runtime.

We next test on the artif and oscigrne nonlinear least-squares problems from
the CUTEst collection (Gould et al., 2015) with dimension $5,000$ and $10,000$
respectively in both $n$ and $d$. As before we run R-SGN five times for each
problem for $100$ iterations from the given starting points for each problem,
with block sizes of 1%, 5%, 10%, 50% and 100% of the original. As we can see
from the results in Figure 3 and Figure 4, R-SGN does not perform as well as
on the logistic regression problems, due possibly to the increased
difficulty/nonlinearity of these problems. However, it is still able to reach
low accuracy solutions reasonably well, achieving a reduction of several
orders of magnitude in the objective after just one second for both problems
at $50\%$ block size (plotted in red). The CUTEst examples show that more
sophisticated approaches may be needed to tackle general nonlinear least-
squares problems; for example instead of keeping the block size fixed at $l$,
we may consider increasing $l$ over iterations, a topic of future
investigation.

Figure 3: R-SGN on the artif dataset

Figure 4: R-SGN on the oscigrne dataset

##  6 Conclusions

We have presented an optimization algorithm for solving nonlinear least-
squares problems that uses a sketched Gauss-Newton approximation to the
objective’s second derivatives, in a randomised subspace of the full space. A
global rate of convergence, with high probability, is presented. We have
demonstrated promising numerical results on logistic regression problems and
nonlinear CUTEst test problems.

## References

  * Cartis & Scheinberg (2018) Cartis, C. and Scheinberg, K.  Global convergence rate analysis of unconstrained optimization methods based on probabilistic models.  _Mathematical Programming_ , 169(2):337–375, 2018\.
  * Cartis et al. (2012) Cartis, C., Gould, N. I., and Toint, P. L.  How much patience do you have? A worst-case perspective on smooth nonconvex optimization.  _Optima. Mathematical Optimization Society Newsletter_ , (88):1–10, 2012.
  * Cohen et al. (2018) Cohen, M. B., Jayram, T., and Nelson, J.  Simple analyses of the sparse Johnson-Lindenstrauss transform.  2018\.
  * Conn et al. (2000) Conn, A. R., Gould, N. I., and Toint, P. L.  _Trust region methods_.  SIAM, 2000.
  * Dasgupta & Gupta (2003) Dasgupta, S. and Gupta, A.  An elementary proof of a theorem of Johnson and Lindenstrauss.  _Random Structures & Algorithms_, 22(1):60–65, 2003.
  * Doikov & Richtárik (2018) Doikov, N. and Richtárik, P.  Randomized block cubic Newton method.  In _International Conference on Machine Learning_ , pp. 1290–1298, 2018.
  * Facchinei et al. (2015) Facchinei, F., Scutari, G., and Sagratella, S.  Parallel selective algorithms for nonconvex big data optimization.  _IEEE Transactions on Signal Processing_ , 63(7):1874–1889, 2015.
  * Gould et al. (2015) Gould, N. I., Orban, D., and Toint, P. L.  CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization.  _Computational Optimization and Applications_ , 60(3):545–557, 2015.
  * Gower et al. (2019) Gower, R., Koralev, D., Lieder, F., and Richtárik, P.  RSN: randomized subspace Newton.  In _Advances in Neural Information Processing Systems_ , pp. 614–623, 2019.
  * Gratton et al. (2007) Gratton, S., Lawless, A. S., and Nichols, N. K.  Approximate Gauss–Newton methods for nonlinear least squares problems.  _SIAM Journal on Optimization_ , 18(1):106–132, 2007.
  * Gratton et al. (2018) Gratton, S., Royer, C. W., Vicente, L. N., and Zhang, Z.  Complexity and global rates of trust-region methods based on probabilistic models.  _IMA Journal of Numerical Analysis_ , 38(3):1579–1597, 2018.
  * Kane & Nelson (2014) Kane, D. M. and Nelson, J.  Sparser Johnson-Lindenstrauss transforms.  _Journal of the ACM_ , 61(1):1–23, 2014.
  * Lu & Xiao (2017) Lu, Z. and Xiao, L.  A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming.  _SIAM Journal on Numerical Analysis_ , 55(6):2930–2955, 2017.
  * Luo et al. (2016) Luo, H., Agarwal, A., Cesa-Bianchi, N., and Langford, J.  Efficient second order online learning by sketching.  In _Advances in Neural Information Processing Systems_ , pp. 902–910, 2016.
  * Nocedal & Wright (2006) Nocedal, J. and Wright, S.  _Numerical optimization_.  Springer, 2006.
  * Pilanci & Wainwright (2017) Pilanci, M. and Wainwright, M. J.  Newton sketch: a near linear-time optimization algorithm with linear-quadratic convergence.  _SIAM Journal on Optimization_ , 27(1):205–245, 2017.
  * Qu et al. (2016) Qu, Z., Richtárik, P., Takác, M., and Fercoq, O.  SDNA: stochastic dual Newton ascent for empirical risk minimization.  In _International Conference on Machine Learning_ , pp. 1823–1832, 2016.
  * Richtárik & Takáč (2014) Richtárik, P. and Takáč, M.  Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.  _Mathematical Programming_ , 144(1-2):1–38, 2014\.
  * Rudelson & Vershynin (2010) Rudelson, M. and Vershynin, R.  Non-asymptotic theory of random matrices: extreme singular values.  In _Proceedings of the International Congress of Mathematicians 2010_ , pp. 1576–1602. World Scientific, 2010.
  * Tett et al. (2017) Tett, S. F., Yamazaki, K., Mineter, M. J., Cartis, C., and Eizenberg, N.  Calibrating climate models using inverse methods: case studies with HadAM3, HadAM3P and HadCM3.  _Geoscientific Model Development_ , 10, 2017.
  * Vanschoren et al. (2013) Vanschoren, J., van Rijn, J. N., Bischl, B., and Torgo, L.  OpenML: networked science in machine learning.  _SIGKDD Explorations_ , 15(2):49–60, 2013.
  * Woodruff (2014) Woodruff, D. P.  Sketching as a tool for numerical linear algebra.  _arXiv preprint arXiv:1411.4357_ , 2014.