# Multi-Beam Forming with Movable-Antenna Array

Wenyan Ma, , Lipeng Zhu, , and Rui Zhang W. Ma and L. Zhu are with the
Department of Electrical and Computer Engineering, National University of
Singapore, Singapore 117583 (e-mail<EMAIL_ADDRESS>zhulp@nus.edu.sg). R.
Zhang is with School of Science and Engineering, Shenzhen Research Institute
of Big Data, The Chinese University of Hong Kong, Shenzhen, Guangdong 518172,
China (e-mail: rzhang@cuhk.edu.cn). He is also with the Department of
Electrical and Computer Engineering, National University of Singapore,
Singapore 117583 (e-mail: elezhang@nus.edu.sg).

###### Abstract

Conventional multi-beam forming with fixed-position antenna (FPA) arrays needs
to trade-off between maximizing the beamforming gain over desired directions
and minimizing the interference power over undesired directions. In this
letter, we study the enhanced multi-beam forming with a linear movable-antenna
(MA) array by exploiting the new degrees of freedom (DoFs) via antennas’
position optimization. Specifically, we jointly optimize the antenna position
vector (APV) and antenna weight vector (AWV) to maximize the minimum
beamforming gain over multiple desired directions, subject to a given
constraint on the maximum interference power over undesired directions. We
propose an efficient alternating optimization algorithm to find a suboptimal
solution by iteratively optimizing one of the APV and AWV with the other being
fixed. Numerical results show that the proposed multi-beam forming design with
MA arrays can significantly outperform that with the traditional FPA arrays
and other benchmark schemes in terms of both beamforming gain and interference
suppression.

###### Index Terms:

Movable-antenna (MA) array, multi-beam forming, beamforming gain, interference
suppression.

##  I Introduction

Multi-beam forming is an important signal processing technique in multiple-
antenna systems to achieve concurrent signal transmissions to multiple
receivers or receptions from multiple transmitters. By designing the amplitude
and/or phase of the antenna weight vector (AWV), the transmit/receive signals
at different antennas can be constructively superimposed to maximize the
beamforming gain over desired directions, or destructively canceled to
minimize the interference power over undesired directions. With the
development of array signal processing and antenna manufacturing technologies,
multi-beam forming has been widely applied e.g., in satellite communications
to enhance the coverage of multiple areas [1], in mobile communications to
support broadcasting/multicasting [2], in radar systems to track multiple
targets [3], etc. However, since the conventional fixed-position antenna (FPA)
arrays usually have a fixed geometry once manufactured, the spatial
correlations of steering vectors over different steering angles are fixed for
an FPA array. Therefore, existing multi-beam forming methods with the FPA
arrays need to trade-off between maximizing the beamforming gain over desired
directions and minimizing the interference over undesired directions, which
limits the performance of multiple-antenna systems [2, 4].

Recently, movable antenna (MA) was proposed as a promising technology for
efficiently improving the wireless channel conditions and enhancing the
communication performance via the local movement of antennas [5, 6, 7, 8, 9,
10, 11]. Preliminary studies have demonstrated the advantages of MAs in
improving the received signal-to-noise ratio (SNR) [5], the MIMO channel
capacity [6, 10], and the performance of multiuser communications [7, 11] over
their FPA counterparts. Moreover, it has been shown in [12] that an MA array
can significantly enhance the single-beam forming over FPA arrays by jointly
optimizing the antenna position vector (APV) and AWV. Under certain null-
steering directions and numbers of MAs, an MA array can achieve the full
beamforming gain over the desired direction with null steering over undesired
directions. However, the performance improvement on multi-beam forming with MA
arrays has not been investigated in the existing literature [5, 6, 7, 8, 9,
10, 11, 12].

In this letter, we investigate the enhanced multi-beam forming with a linear
MA array by jointly optimizing its APV and AWV. We aim to maximize the minimum
beamforming gain over desired directions (i.e., max-min beamforming gain),
subject to a given constraint on the maximum interference power over undesired
directions. The formulated optimization problem is non-convex with respect to
both the APV and AWV. To address this problem, we propose an alternating
optimization algorithm to iteratively optimize one of the APV and AWV with the
other being fixed, where the convex relaxation technique is leveraged to find
a suboptimal solution for each subproblem. Simulation results show that the
proposed multi-beam forming design with MA arrays can significantly outperform
that with the traditional FPA arrays and other benchmark schemes in terms of
both beamforming gain and interference suppression.

Notations: Symbols for vectors (lower case) and matrices (upper case) are in
boldface. $\|\bm{a}\|_{2}$ denotes the $2$-norm of vector $\bm{a}$. We use
$(\cdot)^{\mathsf{*}}$, $(\cdot)^{\mathsf{T}}$, and $(\cdot)^{\mathsf{H}}$ to
denote conjugate, transpose, and conjugate transpose, respectively. The real
part of vector $\bm{a}$ is denoted by ${\rm{Re}}\\{\bm{a}\\}$.
$\mathbb{C}^{P\times{Q}}$ and $\mathbb{R}^{P\times{Q}}$ denote the sets of
$P\times{Q}$ dimensional complex and real matrices, respectively. $\bm{a}[p]$
and $\bm{A}[p,q]$ denote the $p$th entry of vector $\bm{a}$ and the entry of
matrix $\bm{A}$ in its $p$th row and $q$th column, respectively.
${\rm{Tr}}(\bm{A})$ denotes the trace of matrix $\bm{A}$.
$\textrm{diag}(\bm{a})$ denotes a square diagonal matrix with the elements of
vector $\bm{a}$ on the main diagonal.

##  II System Model and Problem Formulation

As shown in Fig. 1, we consider a linear MA array with $N$ antennas, where the
MAs’ positions can be adjusted in the given one-dimensional (1D) line segment
of length $D$. Let $x_{n}\in[0,D]$ denote the $n$th MA’s position, and the APV
of all $N$ MAs is denoted by
$\bm{x}\triangleq[x_{1},x_{2},\ldots,x_{N}]^{\mathsf{T}}\in\mathbb{R}^{N}$
with $0\leq x_{1}<x_{2}<\ldots<x_{N}\leq D$ without loss of generality. Thus,
the steering vector of the MA array can be written as a function of the APV
$\bm{x}$ and the steering angle $\theta$:

$\displaystyle\bm{\alpha}(\bm{x},\theta)=\left[e^{j\frac{2\pi}{\lambda}x_{1}\cos(\theta)},\ldots,e^{j\frac{2\pi}{\lambda}x_{N}\cos(\theta)}\right]^{\mathsf{T}}\in\mathbb{C}^{N},$
(1)

where $\lambda$ is the wavelength. Denoting the AWV as
$\bm{w}\in\mathbb{C}^{N}$, the beamforming gain over steering angle $\theta$
can thus be expressed as

$\displaystyle
G(\bm{w},\bm{x},\theta)=\left|\bm{w}^{\mathsf{H}}\bm{\alpha}(\bm{x},\theta)\right|^{2}.$
(2)

As shown in Fig. 1, let $\\{\theta_{k}\\}_{k=1}^{K}$ denote the set of $K$
desired signals’ directions and $\\{\phi_{l}\\}_{l=1}^{L}$ denote the set of
$L$ undesired interference directions. Then, we aim to maximize the minimum
signal power over $\\{\theta_{k}\\}_{k=1}^{K}$ by jointly optimizing the APV
$\bm{x}$ and the AWV $\bm{w}$, subject to a given constraint on the maximum
interference power over $\\{\phi_{l}\\}_{l=1}^{L}$, which can be formulated as
the following optimization problem:

$\displaystyle\textrm{(P1)}~{}~{}\max_{\bm{x},\bm{w},\delta}\quad$
$\displaystyle\delta$ (3a) s.t. $\displaystyle x_{1}\geq 0,x_{N}\leq D,$ (3b)
$\displaystyle x_{n}-x_{n-1}\geq D_{0},~{}~{}n=2,3,\ldots,N,$ (3c)
$\displaystyle G(\bm{w},\bm{x},\theta_{k})\geq\delta,~{}~{}k=1,2,\ldots,K,$
(3d) $\displaystyle G(\bm{w},\bm{x},\phi_{l})\leq\eta,~{}~{}l=1,2,\ldots,L,$
(3e) $\displaystyle\|\bm{w}\|_{2}\leq 1,$ (3f)

where constraint (3b) ensures that the MAs are moved within the feasible
region $[0,D]$; $D_{0}$ in constraint (3c) is the minimum distance between
adjacent MAs to avoid antenna coupling; $\eta$ in constraint (3e) is a given
threshold on the maximum interference power; and the AWV power is normalized
to be no larger than one in constraint (3f). Note that problem (P1) is a non-
convex optimization problem since constraints (3d) and (3e) are non-convex
with respect to $\bm{w}$ and $\bm{x}$. Furthermore, the coupling between
$\bm{w}$ and $\bm{x}$ in constraints (3d) and (3e) renders (P1) more
challenging to solve.

Figure 1: The considered linear MA array.

##  III Proposed Algorithm

In this section, we propose an alternating optimization algorithm to tackle
the coupling between optimization variables $\bm{w}$ and $\bm{x}$ in problem
(P1). Specifically, we iteratively solve two subproblems of (P1) in an
alternate manner, where each subproblem optimizes one of $\bm{w}$ and $\bm{x}$
with the other being fixed. Then, the overall algorithm is summarized, and the
convergence and computational complexity of the proposed algorithm is
analyzed. Finally, a low-complexity initialization scheme is presented.

###  III-A Optimization of $\bm{w}$ with Given $\bm{x}$

In this subsection, we aim to optimize the AWV $\bm{w}$ in problem (P1) with a
given APV $\bm{x}$. Since constraint (3d) is non-convex with respect to
$\bm{w}$, we use the successive convex approximation (SCA) technique to relax
it. Specifically, for the given $\bm{w}^{t}\in{\mathbb{C}^{N}}$ obtained in
the $t$th iteration of SCA, since $G(\bm{w},\bm{x},\theta_{k})$ is convex with
respect to $\bm{w}$, we can construct the following linear surrogate function
$\bar{G}(\bm{w},\bm{x},\theta_{k}|\bm{w}^{t})$ to globally minorize
$G(\bm{w},\bm{x},\theta_{k})$ by applying the first-order Taylor expansion at
$\bm{w}^{t}$:

$\displaystyle
G(\bm{w},\bm{x},\theta_{k})\geq\bar{G}(\bm{w},\bm{x},\theta_{k}|\bm{w}^{t})$
(4) $\displaystyle\triangleq
G(\bm{w}^{t},\bm{x},\theta_{k})+2{\rm{Re}}\\{(\bm{w}^{t})^{\mathsf{H}}\bm{\alpha}(\bm{x},\theta_{k})\bm{\alpha}(\bm{x},\theta_{k})^{\mathsf{H}}(\bm{w}-\bm{w}^{t})\\}$
$\displaystyle=2{\rm{Re}}\\{(\bm{w}^{t})^{\mathsf{H}}\bm{\alpha}(\bm{x},\theta_{k})\bm{\alpha}(\bm{x},\theta_{k})^{\mathsf{H}}\bm{w}\\}-G(\bm{w}^{t},\bm{x},\theta_{k}).$

Hereto, for the given $\bm{w}^{t}\in{\mathbb{C}^{N}}$ in the $t$th iteration,
the optimization of $\bm{w}$ can be transformed into

$\displaystyle\textrm{(P2)}~{}~{}\max_{\bm{w},\delta_{\bm{w}}}\quad$
$\displaystyle\delta_{\bm{w}}$ (5a) s.t.
$\displaystyle\bar{G}(\bm{w},\bm{x},\theta_{k}|\bm{w}^{t})\geq\delta_{\bm{w}},~{}~{}k=1,2,\ldots,K,$
(5b) $\displaystyle\eqref{P1e},\eqref{P1f}.$

Since constraint (5b) is linear and constraints (3e) and (3f) are convex
quadratic with respect to $\bm{w}$, problem (P2) is a convex quadratically
constrained quadratic program (QCQP) problem and can be efficiently solved by
using CVX [13].

###  III-B Optimization of $\bm{x}$ with Given $\bm{w}$

In this subsection, we aim to optimize the APV $\bm{x}$ with a given AWV
$\bm{w}$. To deal with the non-convex constraints (3d) and (3e), we relax them
by using the SCA technique. For ease of exposition, we define
$\vartheta_{k}\triangleq\frac{2\pi}{\lambda}\cos(\theta_{k})$. Furthermore,
the $n$th element of $\bm{w}$ is denoted by $w_{n}=|w_{n}|e^{j\angle{w_{n}}}$,
with amplitude $|w_{n}|$ and phase $\angle{w_{n}}$. Thus,
$G(\bm{w},\bm{x},\theta_{k})$ in constraint (3d) can be further expressed as

$\displaystyle
G(\bm{w},\bm{x},\theta_{k})=\left|\sum_{n=1}^{N}w_{n}^{\mathsf{*}}e^{jx_{n}\vartheta_{k}}\right|^{2}$
(6)
$\displaystyle=\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\cos\big{(}\vartheta_{k}(x_{n}-x_{m})-(\angle{w_{n}}-\angle{w_{m}})\big{)}$
$\displaystyle\triangleq\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\cos\left(f_{k}(x_{n},x_{m})\right),$

where
$f_{k}(x_{n},x_{m})\triangleq\vartheta_{k}(x_{n}-x_{m})-(\angle{w_{n}}-\angle{w_{m}})$.
Since $G(\bm{w},\bm{x},\theta_{k})$ is neither convex nor concave over
$\bm{x}$, we construct a convex surrogate function to locally approximate
$G(\bm{w},\bm{x},\theta_{k})$ based on the second-order Taylor expansion.
Specifically, for a given $z_{0}\in{\mathbb{R}}$, the second-order Taylor
expansion of $\cos(z)$ is

$\displaystyle\cos(z_{0})-\sin(z_{0})(z-z_{0})-\frac{1}{2}\cos(z_{0})(z-z_{0})^{2}.$
(7)

Since $\cos(z_{0})\leq 1$ and $(z-z_{0})^{2}\geq 0$, we can construct the
concave quadratic surrogate function $g(z|z_{0})$ to minorize $\cos(z)$ as

$\displaystyle\cos(z)\geq
g(z|z_{0})\triangleq\cos(z_{0})-\sin(z_{0})(z-z_{0})-\frac{1}{2}(z-z_{0})^{2}.$
(8)

Then, for the given
$\bm{x}^{i}\triangleq[x_{1}^{i},x_{2}^{i},\ldots,x_{N}^{i}]^{\mathsf{T}}$ in
the $i$th iteration of SCA, by letting $z\leftarrow f_{k}(x_{n},x_{m})$ and
$z_{0}\leftarrow f_{k}(x_{n}^{i},x_{m}^{i})$, the surrogate function that
provides a global lower-bound for $G(\bm{w},\bm{x},\theta_{k})$ can be
constructed as

$\displaystyle
G(\bm{w},\bm{x},\theta_{k})\geq\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|g(f_{k}(x_{n},x_{m})|f_{k}(x_{n}^{i},x_{m}^{i}))$
$\displaystyle\triangleq\frac{1}{2}\bm{x}^{\mathsf{T}}\bm{A}_{k}\bm{x}+\bm{b}_{k}^{\mathsf{T}}\bm{x}+c_{k},$
(9)

where $\bm{A}_{k}\in{\mathbb{R}^{N\times N}}$,
$\bm{b}_{k}\in{\mathbb{R}^{N}}$, and $c_{k}\in{\mathbb{R}}$ are given by

$\displaystyle\bm{A}_{k}$
$\displaystyle\triangleq-2\vartheta_{k}^{2}(\gamma\textrm{diag}(\bar{\bm{w}})-\bar{\bm{w}}\bar{\bm{w}}^{\mathsf{T}}),$
(10) $\displaystyle\bm{b}_{k}[n]$ $\displaystyle\triangleq
2\vartheta_{k}^{2}\sum_{m=1}^{N}|w_{n}w_{m}|(x_{n}^{i}-x_{m}^{i})$
$\displaystyle~{}~{}~{}~{}-2\vartheta_{k}\sum_{m=1}^{N}|w_{n}w_{m}|\sin\left(f_{k}(x_{n}^{i},x_{m}^{i})\right),$
$\displaystyle c_{k}$
$\displaystyle\triangleq\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\cos\left(f_{k}(x_{n}^{i},x_{m}^{i})\right)$
$\displaystyle~{}~{}~{}~{}+\vartheta_{k}\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\sin\left(f_{k}(x_{n}^{i},x_{m}^{i})\right)(x_{n}^{i}-x_{m}^{i})$
$\displaystyle~{}~{}~{}~{}-\frac{1}{2}\vartheta_{k}^{2}\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|(x_{n}^{i}-x_{m}^{i})^{2},$

with $\bar{\bm{w}}\triangleq[|w_{1}|,|w_{2}|,\ldots,|w_{N}|]^{\mathsf{T}}$ and
$\gamma\triangleq\sum_{n=1}^{N}|w_{n}|$. Thus, constraint (3d) can be relaxed
as a quadratic constraint (QC):

$\displaystyle\frac{1}{2}\bm{x}^{\mathsf{T}}\bm{A}_{k}\bm{x}+\bm{b}_{k}^{\mathsf{T}}\bm{x}+c_{k}\geq\delta_{\bm{x}},~{}~{}k=1,2,\ldots,K.$
(11)

Furthermore, by defining
$\textbf{1}_{N}\triangleq[1,1,\ldots,1]^{\mathsf{T}}\in{\mathbb{R}^{N}}$ and
$\bm{D}_{\bm{w}}\triangleq\textrm{diag}([\sqrt{|w_{1}|},\sqrt{|w_{2}|},\ldots,\sqrt{|w_{N}|}]^{\mathsf{T}})\in{\mathbb{R}^{N\times
N}}$, we have $\textrm{diag}(\bar{\bm{w}})=\bm{D}_{\bm{w}}\bm{D}_{\bm{w}}$ and
$\bar{\bm{w}}=\bm{D}_{\bm{w}}\bm{D}_{\bm{w}}\textbf{1}_{N}$. Then,
$\bm{x}^{\mathsf{T}}\bm{A}_{k}\bm{x}$ can be further expressed as

$\displaystyle\bm{x}^{\mathsf{T}}\bm{A}_{k}\bm{x}$
$\displaystyle=-2\vartheta_{k}^{2}\left(\gamma\bm{x}^{\mathsf{T}}\textrm{diag}(\bar{\bm{w}})\bm{x}-\bm{x}^{\mathsf{T}}\bar{\bm{w}}\bar{\bm{w}}^{\mathsf{T}}\bm{x}\right)$
(12)
$\displaystyle=-2\vartheta_{k}^{2}\left(\gamma\|\bm{D}_{\bm{w}}\bm{x}\|_{2}^{2}-\left|\textbf{1}_{N}^{\mathsf{T}}\bm{D}_{\bm{w}}\bm{D}_{\bm{w}}\bm{x}\right|^{2}\right)$
$\displaystyle\overset{(a)}{=}-2\vartheta_{k}^{2}\left(\|\bm{D}_{\bm{w}}\textbf{1}_{N}\|_{2}^{2}\|\bm{D}_{\bm{w}}\bm{x}\|_{2}^{2}-\left|\textbf{1}_{N}^{\mathsf{T}}\bm{D}_{\bm{w}}\bm{D}_{\bm{w}}\bm{x}\right|^{2}\right)$
$\displaystyle\overset{(b)}{\leq}0,$

where the equality $(a)$ holds since
$\gamma=\|\bm{D}_{\bm{w}}\textbf{1}_{N}\|_{2}^{2}$; and the inequality $(b)$
holds due to the Cauchy–Schwarz inequality, i.e.,
$\|\bm{u}\|_{2}^{2}\|\bm{v}\|_{2}^{2}\geq|\bm{u}^{\mathsf{T}}\bm{v}|^{2}$ for
any two equal-sized vectors $\bm{u}$ and $\bm{v}$. Notice from (12) that
$\bm{A}_{k}$ is a negative semi-definite (NSD) matrix. Thus, constraint (11)
is a convex QC over $\bm{x}$.

On the other hand, since constraint (3e) has a similar structure as constraint
(3d), we can relax the non-convex constraint (3e) by modifying the procedure
of constructing the relaxed convex QC constraint (11). Specifically, since
$\cos(z_{0})\geq-1$ and $(z-z_{0})^{2}\geq 0$ in (7), we can construct the
convex quadratic surrogate function $\tilde{g}(z|z_{0})$ to majorize $\cos(z)$
as

$\displaystyle\cos(z)\leq\tilde{g}(z|z_{0})\triangleq\cos(z_{0})-\sin(z_{0})(z-z_{0})+\frac{1}{2}(z-z_{0})^{2}.$
(13)

Then, the surrogate function that provides a global upper-bound for
$G(\bm{w},\bm{x},\phi_{l})$ can be constructed as

$\displaystyle
G(\bm{w},\bm{x},\phi_{l})\leq\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\tilde{g}(\tilde{f}_{l}(x_{n},x_{m})|\tilde{f}_{l}(x_{n}^{i},x_{m}^{i}))$
$\displaystyle\triangleq\frac{1}{2}\bm{x}^{\mathsf{T}}\tilde{\bm{A}}_{l}\bm{x}+\tilde{\bm{b}}_{l}^{\mathsf{T}}\bm{x}+\tilde{c}_{l},$
(14)

where
$\tilde{f}_{l}(x_{n},x_{m})\triangleq\varphi_{l}(x_{n}-x_{m})-(\angle{w_{n}}-\angle{w_{m}})$
with $\varphi_{l}\triangleq\frac{2\pi}{\lambda}\cos(\phi_{l})$;
$\tilde{\bm{A}}_{l}\in{\mathbb{R}^{N\times N}}$,
$\tilde{\bm{b}}_{l}\in{\mathbb{R}^{N}}$, and $\tilde{c}_{l}\in{\mathbb{R}}$
are given by

$\displaystyle\tilde{\bm{A}}_{l}$ $\displaystyle\triangleq
2\varphi_{l}^{2}(\gamma\textrm{diag}(\bar{\bm{w}})-\bar{\bm{w}}\bar{\bm{w}}^{\mathsf{T}}),$
(15) $\displaystyle\tilde{\bm{b}}_{l}[n]$
$\displaystyle\triangleq-2\varphi_{l}^{2}\sum_{m=1}^{N}|w_{n}w_{m}|(x_{n}^{i}-x_{m}^{i})$
$\displaystyle~{}~{}~{}~{}-2\varphi_{l}\sum_{m=1}^{N}|w_{n}w_{m}|\sin\left(\tilde{f}_{l}(x_{n}^{i},x_{m}^{i})\right),$
$\displaystyle\tilde{c}_{l}$
$\displaystyle\triangleq\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\cos\left(\tilde{f}_{l}(x_{n}^{i},x_{m}^{i})\right)$
$\displaystyle~{}~{}~{}~{}+\varphi_{l}\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|\sin\left(\tilde{f}_{l}(x_{n}^{i},x_{m}^{i})\right)(x_{n}^{i}-x_{m}^{i})$
$\displaystyle~{}~{}~{}~{}+\frac{1}{2}\varphi_{l}^{2}\sum_{n=1}^{N}\sum_{m=1}^{N}|w_{n}w_{m}|(x_{n}^{i}-x_{m}^{i})^{2}.$

Notice that $\tilde{\bm{A}}_{l}$ is a positive semi-definite (PSD) matrix,
which can be proven similarly by the procedure in (12). Thus, constraint (3e)
can be relaxed as a convex QC over $\bm{x}$:

$\displaystyle\frac{1}{2}\bm{x}^{\mathsf{T}}\tilde{\bm{A}}_{l}\bm{x}+\tilde{\bm{b}}_{l}^{\mathsf{T}}\bm{x}+\tilde{c}_{l}\leq\eta,~{}~{}l=1,2,\ldots,L.$
(16)

Therefore, in the $i$th iteration of SCA, $\bm{x}$ can be optimized by solving
the following optimization problem

$\displaystyle\textrm{(P3)}~{}~{}\max_{\bm{x},\delta_{\bm{x}}}\quad$
$\displaystyle\delta_{\bm{x}}$ (17a) s.t.
$\displaystyle\eqref{P1b},\eqref{P1c},\eqref{beamgain1},\eqref{beamgain2}.$

Since constraints (3b) and (3c) are linear and constraints (11) and (16) are
convex quadratic with respect to $\bm{x}$, problem (P3) is a convex QCQP
problem and can be efficiently solved by using CVX [13].

###  III-C Overall Algorithm and Performance Analysis

Based on the solutions for problems (P2) and (P3) presented above, we are
ready to summarize the overall alternating optimization algorithm for solving
problem (P1). The details of the proposed algorithm are summarized in
Algorithm 1, where $\epsilon$, $\epsilon_{\bm{w}}$, and $\epsilon_{\bm{x}}$
are predefined convergence thresholds for the overall algorithm, iterative
optimization of $\bm{w}$, and iterative optimization of $\bm{x}$,
respectively. Specifically, from step 4 to step 8, we iteratively solve
problem (P2) to optimize the AWV $\bm{w}$ with a given APV $\bm{x}$. Then,
from step 9 to step 14, we iteratively optimize $\bm{x}$ by solving problem
(P3) with a given $\bm{w}$. The overall algorithm iteratively solves problems
(P2) and (P3) until convergence.

Algorithm 1 Alternating Optimization Algorithm for Problem (P1)

1:  _Input:_ $N$, $L$, $K$, $\eta$, $\\{\theta_{k}\\}_{k=1}^{K}$,
$\\{\phi_{l}\\}_{l=1}^{L}$, $D$, $D_{0}$, $\epsilon$, $\epsilon_{\bm{w}}$,
$\epsilon_{\bm{x}}$, $\bm{x}^{0}$, $\bm{w}^{0}$.

2: Initialization: $t\leftarrow 0$, $i\leftarrow 0$,
$\bm{x}\leftarrow\bm{x}^{0}$, $\delta\leftarrow 0$.

3: while Increase of $\delta$ is above $\epsilon$ do

4: while Increase of $\delta_{\bm{w}}$ in (5a) is above $\epsilon_{\bm{w}}$ do

5: Obtain $\bm{w}^{t+1}$ by solving problem (P2).

6: $t\leftarrow t+1$.

7: end while

8: $\bm{w}\leftarrow\bm{w}^{t}$, $t\leftarrow 0$.

9: while Increase of $\delta_{\bm{x}}$ in (17a) is above $\epsilon_{\bm{x}}$
do

10: Obtain $\\{\bm{A}_{k},\bm{b}_{k},c_{k}\\}_{k=1}^{K}$ via (10); obtain
$\\{\tilde{\bm{A}}_{l},\tilde{\bm{b}}_{l},\tilde{c}_{l}\\}_{l=1}^{L}$ via
(15).

11: Obtain $\bm{x}^{i+1}$ by solving problem (P3).

12: $i\leftarrow i+1$.

13: end while

14: $\bm{x}\leftarrow\bm{x}^{i}$, $i\leftarrow 0$.

15: $\delta\leftarrow\min\\{G(\bm{w},\bm{x},\theta_{k})\\}_{k=1}^{K}$.

16: end while

17:  _Output:_ $\bm{w}$, $\bm{x}$.

First, we analyze the convergence of Algorithm 1 as follows. In the $t$th
iteration for solving problem (P2), we have the following inequalities for
constraint (5b):

$\displaystyle G(\bm{w}^{t},\bm{x},\theta_{k})$
$\displaystyle\overset{(c_{1})}{=}\bar{G}(\bm{w}^{t},\bm{x},\theta_{k}|\bm{w}^{t})$
(18)
$\displaystyle\overset{(c_{2})}{\leq}\bar{G}(\bm{w}^{t+1},\bm{x},\theta_{k}|\bm{w}^{t})\overset{(c_{3})}{\leq}G(\bm{w}^{t+1},\bm{x},\theta_{k}),$

where the equality $(c_{1})$ holds since the first-order Taylor expansion in
(4) is tight at $\bm{w}^{t}$; the inequality $(c_{2})$ is valid since
$\bar{G}(\bm{w},\bm{x},\theta_{k}|\bm{w}^{t})$ is maximized in the $t$th
iteration, while its equality can be attained by letting
$\bm{w}^{t+1}=\bm{w}^{t}$; the inequality $(c_{3})$ holds because
$\bar{G}(\bm{w},\bm{x},\theta_{k}|\bm{w}^{t})$ globally minorizes
$G(\bm{w},\bm{x},\theta_{k})$. Hence, the sequence
$\\{G(\bm{w}^{t},\bm{x},\theta_{k})\\}_{t=0}^{\infty}$ is monotonically
increasing and can converge to its maximum value. Moreover, since
$\delta=\min\\{G(\bm{w},\bm{x},\theta_{k})\\}_{k=1}^{K}$, the increment of
$\delta$ can be guaranteed after solving problem (P2). Similarly, the
monotonic convergence for solving problem (P3) can be guaranteed. Moreover,
the alternating optimization of variables $\bm{x}$ and $\bm{w}$ guarantees the
non-decreasing objective value of problem (P1) during the outer iterations of
Algorithm 1, which is also upper-bounded by a finite beamforming gain.
Therefore, Algorithm 1 is guaranteed to converge.

Next, we analyze the computational complexity of Algorithm 1 as follows. Let
$I$, $I_{\bm{w}}$, and $I_{\bm{x}}$ denote the maximum number of iterations of
repeating steps 4–15 for alternately solving problems (P2) and (P3), that of
repeating steps 5-6 for solving problem (P2), and that of repeating steps
10-12 for solving problem (P3), respectively. The complexity for solving the
QCQP problem (P2) or (P3) is in the order of
$\mathcal{O}((K+L+2)^{0.5}N(N^{2}+K+L)\ln(1/\beta))$ with accuracy $\beta$ for
the interior-point method [14]. Therefore, the total algorithm complexity is
in the order of
$\mathcal{O}((K+L+2)^{0.5}N(N^{2}+K+L)\ln(1/\beta)(I_{\bm{w}}+I_{\bm{x}})I)$.

###  III-D Initialization

In this subsection, we propose a low-complexity initialization scheme to
obtain $\bm{x}^{0}$ and $\bm{w}^{0}$ in Algorithm 1. Intuitively, all MAs
should be sufficiently separated to reduce their coupling effect. Thus, we set
$\bm{x}^{0}$ as uniformly sampled in $[0,D]$, with spacing $\frac{D}{N+1}$,
i.e.,
$\bm{x}^{0}=[\frac{D}{N+1},\frac{2D}{N+1},\ldots,\frac{ND}{N+1}]^{\mathsf{T}}$.
For a uniform linear array (ULA) with APV $\bm{x}^{0}$, we can obtain the
globally optimal AWV $\bm{w}^{0}$ [4]. Specifically, we first solve the
following convex semi-definite programming (SDP) problem to obtain a PSD
matrix $\bm{W}^{0}\in{\mathbb{C}^{N\times N}}$:

$\displaystyle\textrm{(P0)}~{}~{}\max_{\bm{W}^{0},\delta_{0}}\quad$
$\displaystyle\delta_{0}$ (19) s.t.
$\displaystyle{\rm{Tr}}(\bm{W}^{0}\bm{\Gamma}(\bm{x}^{0},\theta_{k}))\geq\delta_{0},~{}~{}k=1,2,\ldots,K,$
$\displaystyle{\rm{Tr}}(\bm{W}^{0}\bm{\Gamma}(\bm{x}^{0},\phi_{l}))\leq\eta,~{}~{}l=1,2,\ldots,L,$
$\displaystyle{\rm{Tr}}(\bm{W}^{0})\leq 1,$

where
$\bm{\Gamma}(\bm{x},\theta)\triangleq\bm{\alpha}(\bm{x},\theta)\bm{\alpha}(\bm{x},\theta)^{\mathsf{H}}\in{\mathbb{C}^{N\times
N}}$. Next, we can obtain $\bm{r}_{\bm{w}}\in{\mathbb{C}^{2N-1}}$ based on
$\bm{W}^{0}$ by

$\displaystyle\bm{r}_{\bm{w}}[m]=\sum_{p=\max(m-N+1,1)}^{\min(m,N)}\bm{W}^{0}[p,p-m+N],$
(20)

for $m=1,2,\ldots,2N-1$. Indeed, $\bm{r}_{\bm{w}}$ is the autocorrelation
vector of $\bm{w}^{0}$, with
$\bm{r}_{\bm{w}}[m]\triangleq\sum_{p=\max(m-N+1,1)}^{\min(m,N)}\bm{w}^{0}[p]\bm{w}^{0}[p-m+N]^{\mathsf{*}}$,
$m=1,2,\ldots,2N-1$. Finally, we can reconstruct $\bm{w}^{0}$ from
$\bm{r}_{\bm{w}}$ according to the spectral factorization theorem [4].

##  IV Numerical Results

In this section, we provide numerical results to validate our proposed design
for multi-beam forming with MA arrays. We set the convergence threshold as
$\epsilon=10^{-4}$ and $\epsilon_{\bm{w}}=\epsilon_{\bm{x}}=10^{-2}$. The
minimum distance between adjacent MAs is set as $D_{0}=\lambda/2$. The
threshold on the maximum interference power is set as $\eta=0.1$.

The considered benchmark schemes are listed as follows: 1) FPA: The
$N$-dimensional FPA-based ULA with half-wavelength antenna spacing is
considered. The optimal AWV is obtained according to Section III-D. 2)
Alternating position selection (APS): The 1D line segment for MA positioning
is quantized into discrete locations with equal-distance $D_{0}=\lambda/2$. We
apply Algorithm 1, where steps 10 and 11 for the optimization of $\bm{x}$ with
a given $\bm{w}$ are replaced by sequentially optimizing one MA’s position
with the other $(N-1)$ MAs’ positions being fixed, and an exhaustive search
over discrete locations is utilized for each MA. 3) Algorithm 1 without
iteration (AWI): Problems (P2) and (P3) are solved once without outer
iterations in Algorithm 1.

In Fig. 2, we illustrate the beamforming patterns for the proposed method and
the benchmark schemes. We set $D=8\lambda$, $N=8$, $K=2$, $L=2$,
$\theta_{1}=30^{\circ}$, $\theta_{2}=120^{\circ}$, $\phi_{1}=10^{\circ}$, and
$\phi_{2}=150^{\circ}$. From Fig. 2, the proposed method achieves much higher
max-min beamforming gain than the benchmark schemes and even approaches close
to the full beamforming gain (i.e., $N=8$). The proposed method can achieve
$99.7\%$ of the full beamforming gain, while the FPA, APS, and AWI schemes
achieve $36.9\%$, $80.0\%$, and $86.8\%$ of it, respectively. This is because
as compared to the benchmark schemes, the proposed method can adjust the
steering vector $\bm{\alpha}(\bm{x},\theta)$ by optimally exploiting the new
degrees of freedom (DoFs) in the APV $\bm{x}$, such that the correlations
among all signal directions $\\{\bm{\alpha}(\bm{x},\theta_{k})\\}_{k=1}^{K}$
are maximized, while the correlation between each pair of signal direction in
$\\{\bm{\alpha}(\bm{x},\theta_{k})\\}_{k=1}^{K}$ and interference direction in
$\\{\bm{\alpha}(\bm{x},\phi_{l})\\}_{l=1}^{L}$ is minimized.

Figure 2: Comparison of beam patterns with MA and FPA arrays. Figure 3: Max-
min beamforming gain versus $N$. Figure 4: Max-min beamforming gain versus
$L$.

Fig. 3 compares the max-min beamforming gain versus $N$ for different schemes.
We set $D=10\lambda$, $K=2$, and $L=2$. $\\{\theta_{k}\\}_{k=1}^{K}$ and
$\\{\phi_{l}\\}_{l=1}^{L}$ are randomly generated following uniform
distribution over $[0,180^{\circ}]$. From Fig. 3, the proposed method always
outperforms all benchmark schemes, and the performance gap increases with $N$.
Moreover, the proposed method still has $64.1\%$ performance improvement over
the FPA scheme with only $N=4$ MAs’ positions that can be optimized. This
result shows that the proposed method can be applied to practical multiple-MA
systems even with small numbers of MAs.

In Fig. 4, we compare the max-min beamforming gain versus $L$ for all schemes.
We set $D=8\lambda$, $N=8$, and $K=2$. It is observed again that the proposed
method always outperforms all other schemes, demonstrating that the proposed
method is robust to the number of interference directions in practice. Even
under a large number of interference directions (e.g., $L=6$), the proposed
multi-beam forming method with MA arrays can still achieve large performance
improvement (about 3 dB gain) as compared to that with the FPA arrays.

##  V Conclusions

In this letter, we studied the multi-beam forming with MA arrays by exploiting
the new DoFs via antennas’ position optimization. We aimed to maximize the
beamforming gain over all signal directions subject to a given constraint on
the maximum power over all interference directions, via the joint optimization
of the APV and AWV. An alternating optimization algorithm was proposed to
obtain a suboptimal solution by iteratively optimizing one of the APV and AWV
with the other being fixed. Simulation results showed that our proposed multi-
beam forming design with MA arrays can significantly enhance the max-min
beamforming gain with effective interference suppression compared to that with
the conventional FPA arrays.

## References

  * [1] D. Peng, D. He, Y. Li, and Z. Wang, “Integrating terrestrial and satellite multibeam systems toward 6G: Techniques and challenges for interference mitigation,” _IEEE Wireless Commun._ , vol. 29, no. 1, pp. 24–31, Feb. 2022.
  * [2] N. D. Sidiropoulos, T. N. Davidson, and Z.-Q. Luo, “Transmit beamforming for physical-layer multicasting,” _IEEE Trans. Signal Process._ , vol. 54, no. 6, pp. 2239–2251, Jun. 2006.
  * [3] L. Schulwitz and A. Mortazawi, “A compact dual-polarized multibeam phased-array architecture for millimeter-wave radar,” _IEEE Trans. Microw. Theory Tech._ , vol. 53, no. 11, pp. 3588–3594, Nov. 2005.
  * [4] E. Karipidis, N. D. Sidiropoulos, and Z.-Q. Luo, “Far–field multicast beamforming for uniform linear antenna arrays,” _IEEE Trans. Signal Processing_ , vol. 55, no. 10, pp. 4916–4927, Oct. 2007.
  * [5] L. Zhu, W. Ma, and R. Zhang, “Modeling and performance analysis for movable antenna enabled wireless communications,” _IEEE Trans. Wireless Commun._ , early access, 2023, doi: 10.1109/TWC.2023.3330887.
  * [6] W. Ma, L. Zhu, and R. Zhang, “MIMO capacity characterization for movable antenna systems,” _IEEE Trans. Wireless Commun._ , early access, 2023, doi: 10.1109/TWC.2023.3307696.
  * [7] L. Zhu, W. Ma, B. Ning, and R. Zhang, “Movable-antenna enhanced multiuser communication via antenna position optimization,” _arXiv preprint arXiv:2302.06978_ , 2023.
  * [8] L. Zhu, W. Ma, and R. Zhang, “Movable antennas for wireless communication: Opportunities and challenges,” _IEEE Commun. Mag._ , early access, 2023, doi: 10.1109/MCOM.001.2300212.
  * [9] W. Ma, L. Zhu, and R. Zhang, “Compressed sensing based channel estimation for movable antenna communications,” _IEEE Commun. Lett._ , early access, 2023, doi: 10.1109/LCOMM.2023.3310535.
  * [10] X. Chen, B. Feng, Y. Wu, D. W. K. Ng, and R. Schober, “Joint beamforming and antenna movement design for moveable antenna systems based on statistical CSI,” _arXiv preprint arXiv:2308.06720_ , 2023.
  * [11] Y. Wu, D. Xu, D. W. K. Ng, W. Gerstacker, and R. Schober, “Movable antenna-enhanced multiuser communication: Optimal discrete antenna positioning and beamforming,” _arXiv preprint arXiv:2308.02304_ , 2023.
  * [12] L. Zhu, W. Ma, and R. Zhang, “Movable-antenna array enhanced beamforming: Achieving full array gain with null steering,” _IEEE Commun. Lett._ , early access, 2023, doi: 10.1109/LCOMM.2023.3323656.
  * [13] M. Grant and S. Boyd, _(Mar. 2014). CVX: MATLAB Software for Disciplined Convex Programming, Version 2.1_ , [Online]. Available: http://cvxr.com/cvx.
  * [14] M. Fu, Y. Zhou, Y. Shi, and K. B. Letaief, “Reconfigurable intelligent surface empowered downlink non-orthogonal multiple access,” _IEEE Trans. Commun._ , vol. 69, no. 6, pp. 3802–3817, Jun. 2021.


marginparsep has been altered.
topmargin has been altered.
marginparwidth has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Efficient Vertical Federated Learning with Secure Aggregation

Anonymous Authors1

###### Abstract

The majority of work in privacy-preserving federated learning (FL) has been
focusing on horizontally partitioned datasets where clients share the same
sets of features and can train complete models independently. However, in many
interesting problems, such as financial fraud detection and disease detection,
individual data points are scattered across different clients/organizations in
vertical federated learning. Solutions for this type of FL require the
exchange of gradients between participants and rarely consider privacy and
security concerns, posing a potential risk of privacy leakage. In this work,
we present a novel design for training vertical FL securely and efficiently
using state-of-the-art security modules for secure aggregation. We demonstrate
empirically that our method does not impact training performance whilst
obtaining $9.1\text{\times}{10}^{2}$ $\sim$ $3.8\text{\times}{10}^{4}$ speedup
compared to homomorphic encryption (HE).

††footnotetext:  1Anonymous Institution, Anonymous City, Anonymous Region,
Anonymous Country. Correspondence to: Anonymous Author
<EMAIL_ADDRESS>
Preliminary work. Under review by the Machine Learning and Systems (MLSys)
Conference. Do not distribute.

##  1 Introduction

Federated Learning (FL) is a machine learning paradigm that enables the
training of a global model using decentralized datasets without requiring
sharing of raw and sensitive data from participating parties McMahan et al.
(2017); Li et al. (2020); Wei et al. (2022). Under FL, individual institutions
or devices train a common global model collaboratively, agreeing on a possible
third party or central server to orchestrate the learning and perform model
aggregation.

In terms of data partitioning, FL can be categorized as either horizontal or
vertical scenarios. Most existing works focus on horizontal FL (HFL), which
requires all participants to use the same feature space but different sample
spaces Yang et al. (2019); Wei et al. (2022); Liu et al. (2022). This
partitioning scheme is usually found in the cross-device setup where clients
are often mobile or IoT devices with heterogeneous datasets and resources
under complex distributed networks Yu & Li (2021); Qiu et al. (2022). Under
Vertical FL (VFL), however, data points a partitioned across clients. This is
often found in cross-silo setups where participating clients, such as
hospitals and research institutions, may hold complementary pieces of
information for the same data points. For example, two different hospitals may
hold different medical data for the same patient.

The need for VFL has arisen massively in the industry these years Liu et al.
(2022; 2020). For example, a financial institution would like to train a
financial crime detection model, but it only has limited features in its own
institution that limit the performance. The institution would like to have
access to more private information, such as account information, that various
banks might have. However, this is a deal breaker for financial applications
as such data is very sensitive, and legal restrictions (e.g., GDPR) can
prevent it from being shared across institutions. With VFL, institutions and
companies that own only small and fragmented data have constantly been looking
for other institutions to collaboratively develop a shared model for
maximizing data utilization Li et al. (2021b).

Due to their different data structures, training procedures for HFL and VFL
can be very different. Each client in HFL trains a complete copy of the global
model on their local dataset and sends model updates to a centralized server
for aggregation. Under VFL, each client, holding certain features of the whole
dataset, contributes to a sub-module of the global model. This means that
intermediate activations or gradients need to be shared between clients during
the training process, posing a potential risk for privacy leakage, as the
original raw data can be reconstructed from said gradients Zhu et al. (2019);
Zhao et al. (2020); Jin et al. (2021). While most research has focused on
designing methods to train the global model under VFL better, fewer efforts
have been devoted to providing a secure way of training. The method proposed
by Liu et al. (2020) only tries to protect the sample IDs, rather than all the
raw private data; Chen et al. (2020) perturbed local embedding to ensure data
privacy and improve communication efficiency, which has strict requirements
for the embedding and can impact the overall performance. There are also
BlindFL Fu et al. (2022), ACML Zhang & Zhu (2020), and PrADA Kang et al.
(2022) are homomorphic encryption (HE) based solutions. These approaches often
incur significant communication and computation overheads. Moreover, their
fixed design cannot be extended to multiple-party scenarios.

Our work aims to provide an efficient and privacy-preserving way of training
under the Vertical FL setup. We begin by describing in Section 2 the specific
problem setup. We then describe a secure aggregation method tailored to solve
this kind of FL problem in Section 4. Finally, we demonstrate its
applicability with extensive experiments described in Section 6 to show that
our SA incurs minimal overhead. In addition, we demonstrate that our method
does not impact training performance whilst obtaining
$9.1\text{\times}{10}^{2}$ $\sim$ $3.8\text{\times}{10}^{4}$ speedup compared
to HE.

##  2 Problem Setup

In this section, we formally define the problem of VFL for classification. We
consider a $C$ class classification problem defined over a compact space
$\mathcal{X}$ and a label space $\mathcal{Y}=[C]$, where $[L]=\\{1,...,C\\}$.

Following the setup as in previous literature Liu et al. (2022), we define two
kinds of clients in the vertical FL settings. The first type is the _active
party_ , which holds all the samples with the ground-truth label and multiple
features, and there usually is only one active party. The second type is
called the _passive parties_ , which only holds some features that are not
overlapping with the features in the active party. Let Client 0
($\mathcal{C}_{0}$) denote the active party with features $x_{1,...,m}$, and
the rest be the passive parties ($\mathcal{C}_{i}$ with $i=1,...,N$) with
features $x_{m,...,n}$. Passive parties can be clustered by the feature set
they owned. Multiple passive parties can hold different samples with the same
feature set. Let $f$ be the function for the neural network parameterized over
the hypothesis class $w$, which is the weight of the neural network.
$\mathcal{L}(\textbf{w})$ is the loss function, and we assume the widely used
cross-entropy loss.

Since the active party holds the ground-truth label and some features, it is
capable of training the model and making inferences only using its own local
data. The aim of training using VFL is to incorporate other features that
exist in the passive parties to boost performance while maintaining the
privacy of the data features in either active or passive parties.

This setup can be commonly found in real-world scenarios. For example, for the
financial crime detection task, each financial institution will have different
features regarding account information or transaction information. However,
for financial applications, such data is very sensitive, and legal
restrictions (e.g., GDPR) can prevent it from being shared across
institutions. Another example will be in the commercial ad ranking systems, in
the sense that each company or organization might have different information
for the same customer, but the label (the click rate) will only be stored in
the application platform.

Figure 1: Illustration of the VFL problem setup. Only the active party has the
label; each party might have different features.

##  3 centralized solution

This section describes the training method for the problem setup explained in
Section 2.

In a horizontal FL scenario, where datasets are horizontally partitioned, FL
solutions are typically derived from a centralized one, which in turn provides
an upper-bound target efficiency. However, this approach is not well suited in
the case of vertically-partitioned FL, where different feature types are
distributed across different participants.

In order to provide a realistic upper-bound target for the VFL solution, the
centralized solution is designed to impose these data access restrictions from
its conception. In this section, we describe in detail how to train and make
inferences for the centralized model tailored to VFL. The training can be
divided into two steps as explained below.

Pre-training: The first stage is the pre-training phase. It can be pre-
training using features and the label in the active party or the feature
embedding extraction in both active and passive parties. Let $f_{i}$,
$i=1,...,k$ be the embedding extracted from the active party and $f_{i}$,
$i=k,...,l$ be all the embedding from passive parties. Noted that the
embedding from the passive party can be from different clients.

Neural Network with VFL: After the pre-training step, all embeddings are then
served as the input together to the neural network to make the final
prediction. During inference time, the prediction can also be obtained
following these two steps.

##  4 Secure Aggregation Method

In this section, we detail our secure aggregation method for VFL. We
incorporate two different methods to ensure the privacy and security of the
private sensitive information in local datasets that existed on the client
side. First, we use encryption to help the mini-batch selection _without
revealing account information to any third party not holding the account
information_. Second, we adapt the idea of _secure aggregation_ Bonawitz et
al. (2016) for the gradient aggregation during the optimization steps. The
procedures can be divided into three phases: setup phase (Section 4.0.1),
training phase (Section 4.0.2), and testing phase (Section 4.0.3).

Since features are distributed across different clients, both the forward pass
and the backward pass cannot be computed at the same place at the same time.
Therefore, we also explain the setup phase for the key exchange in Section
4.0.1 and the training procedure in detail regarding the mini-batch selection,
forward pass, and backward pass below during the training phase in Section
4.0.2.

####  4.0.1 Setup phase

Similar to the centralized solution, the first step happens at the active
client using only the active dataset to train a pre-train model to obtain the
first stage prediction. The prediction estimation will later be used with the
features from the passive parties to train the neural network.

Key generating step: The first step of secure aggregation is to generate
shared secrets. We use the Elliptic-curve Diffie-Hellman (ECDH) key agreement
protocol Diffie & Hellman (1976); Barker et al. (2017) to generate shared
secrets through insecure channels between all clients. The shared secrets will
be used to build secure pairwise channels by symmetric encryption and
facilitate secure aggregation. During the setup phase, the central aggregator
requests public keys from all participating clients. Then, $\forall i$, Client
$i$ generates one pair of secret key $sk_{i}^{(j)}$ and public key
$pk_{i}^{(j)}$ for each Client $j$ and sends public keys to the aggregator.
$\forall i\neq j,pk_{i}^{\left(j\right)}$ is then forwarded to Client $j$.
Once received, Client $i$ and Client $j$ can generate a shared secret
$ss_{ij}=ss_{ji}$ from $(sk_{i}^{(j)},pk_{j}^{(i)})$ or
$(sk_{j}^{(i)},pk_{i}^{(j)})$.

####  4.0.2 Training Phase

This section explains the training phase in detail.

##### Mini-batch selection

We assume that the active party knows which passive parties hold the features
of a given sample. This can be realized by Private Set Intersection Lu & Ding
(2020); Zhou et al. (2021). We denote the identifier for samples as sample ID,
which is shared among all parties. Since the active party has the information
regarding each sample and the ground truth label, the mini-batch selection
will start from the active party. It will first select a batch of data in the
active party ($\mathcal{C}_{0}$). The sample ID will be encrypted using
$ss_{0\,i}$ as key if the partial features of the sample are held by passive
party $\mathcal{C}_{i}$. The active party will then upload the encrypted ID
batch to the aggregator, which will broadcast it to all passive parties. As
sample IDs are encrypted using different keys, _each passive party can only
decrypt sample IDs existing in its dataset_ , which prevents any party from
knowing extra information about the batch and samples in it.

##### Forward pass

After the pre-training steps in the active party, each sample will have
embeddings $f_{i},i=1,...,k$, which is then fed into the neural network
together with the features embeddings $f_{k,...,l}$ from passive parties.

$\hat{y}=f(w;f,i=1,...,l)$ (1)

In the first round after the setup phase, the active party will initialize the
model parameters, i.e., $w_{t=0}$. During the forward pass, the active party
will send to the aggregator the encrypted batch, the ground-truth labels of
the selected batch, and the initialized model parameters $w_{t=0}$. We assume
it is safe to share the labels, since without any additional information, such
as sample ID, adversaries cannot reveal any sensitive information by only
knowing the labels.

Likewise, once received model weights and the encrypted batch are, passive
party $p$ will try decrypting each value in the batch and then reply with the
following masked vector:

$\Big{(}\sum_{i=k}^{l}\mathbbm{1}(f_{i}^{(j)}\in
D_{p})w_{i}f_{i}^{(j)}\Big{)}_{j=1}^{B}+\mathbf{n}_{p}$ (2)

where $D_{p}$ is the dataset of passive party $p$ and only sums over the
features that exist in the local dataset. $\mathbf{n}_{p}$ is a uniformly
random vector. Notes that the active party will also send the masked
activation to the aggregator to finish the forward pass.

Following the idea of _Secure Aggregation_ , we make added noises cancel out
each other, i.e., $\sum_{p}{\mathbf{n}_{p}}=\mathbf{0}$, which is the
summation of a series of random numbers generated by a Pseudo-Random Generator
(PRG) that can generate sequences of uniformly pseudo-random numbers given a
seed, as shown in Equation 3 and 4.

$\mathbf{n}_{i}=-\sum_{j<i}{\textsc{PRG}(ss_{ij})}+\sum_{j>i}{\textsc{PRG}(ss_{ij})}$
(3)
$\sum_{i}{\mathbf{n}_{i}}=\sum_{i}{\sum_{j>i}{\big{(}\textsc{PRG}(ss_{ij})-\textsc{PRG}(ss_{ji})\big{)}}}=\mathbf{0}$
(4)

Through the chosen added noises, after receiving all masked vectors from all
passive clients, the aggregator can compute output accurately without
knowledge of any individual value from each client by adding them together:

$\big{(}z^{(k)}\big{)}_{k=1}^{B}=\Big{(}\underbrace{\sum_{i=1}^{k}w_{i}f_{i}^{(k)}}_{active}+\underbrace{\sum_{i=k}^{l}w_{i}f_{i}^{(k)}}_{passive}\Big{)}_{k=1}^{B}+\underbrace{\sum_{p}{\mathbf{n}_{p}}}_{noise}$
(5)

where $\sum_{p}{\mathbf{n}_{p}}=\mathbf{0}$.

Due to the fact that all activation are masked using random noise, any party
cannot reveal additional information about other features existing in other
clients, even if the aggregator colludes with one or multiple passive clients.
With $\big{(}z^{(k)}\big{)}_{k=1}^{B}$, the aggregator can then compute the
output.

##### Backward pass

After receiving the label, each client p can compute the partial gradient
$\mathcal{L}(f_{i})$ for the mini-batch with respect to the features that the
local data exists. Then, each client will send back to the aggregator the
masked gradient with mask noise $\mathbf{n}_{p}$ like in the forward pass. The
indicator function is to choose the features that exist in the local dataset
$D_{p}$. Therefore, the formula can be found below:

$\Big{(}\sum_{k=1}^{B}\mathbbm{1}(f_{i}^{(k)}\in
D_{p})\nabla\mathcal{L}(f_{i}^{(k)})\Big{)}_{i=1}^{l}+\mathbf{n}_{p}$ (6)

Similarly, the aggregator can compute the summation of masked vectors from
passive clients and send the result to the active client, which can then
compute the aggregate gradient with respect to each model parameter. It is
worth noting that the aggregator only obtains a masked vector, so
$\frac{\partial}{\partial w_{0}}l$ can only be computed locally at the active
party. Thus, the summed batch gradients are only visible to the active party,
and any individual gradient is kept from any participating party to protect
the sensitive data leakage through the individual gradient.

####  4.0.3 Testing Phase

During the testing phase, the active party will first send the encrypted batch
information and the masked vector
$\big{(}\sum_{i=1}^{k}w_{i}f_{i}^{(k)}\big{)}_{k=1}^{B}+\mathbf{n}_{0}$ to the
aggregator. After receiving the encrypted batch information, the encrypted
batch information is shared with the passive clients. Then each passive client
$p$ computes its masked vector
$\Big{(}\sum_{i=m}^{n}\mathbbm{1}(x_{i}^{(k)}\in
D_{p})w_{i}f_{i}^{(k)}\Big{)}_{k=1}^{B}+\mathbf{n}_{p}$ and sends it back to
the aggregator. Lastly, after the aggregator receives all values, it can make
the prediction.

##  5 discussion

###  5.1 Threat-model and Privacy Guarantee

We consider a _threat model_ where both clients and the server are _honest-
but-curious_ , i.e. they are expected to follow the pre-defined training
protocol whilst trying to learn as much information as possible from the
models they receive. To reduce the risk of information leakage, our solution
used state-of-the-art security modules for _Secure Aggregation_ by adding the
masked gradient when communicating with the central aggregator.

Secure Aggregation is achieved through the use of masking and encryption of
gradients before they are sent back to the aggregator. It can thus prevent the
aggregator from using the received model update to gain knowledge about the
sensitive data on the client side. By using a masked gradient, it is
impossible to reconstruct the original data or make inferences about the
sensitive information in the dataset without knowing the mask. Therefore, our
method protects the model from both data reconstruction and membership
inference attacks.

In addition, while our current implementation could be vulnerable to active
adversaries, our FL solution can be extrapolated very easily to include
_malicious_ settings by introducing a public-key infrastructure (PKI) that can
verify the identity of the sender Bonawitz et al. (2017). It can thus be
further protected from malicious attacks.

Although our method does not allow exposing secret keys to other parties and
demonstrates robustness against collusion between the aggregator and passive
parties, in practical settings, the risk of secret key leakage persists. Thus,
for the sake of privacy, it is necessary to routinely regenerate keys for
symmetric encryption and SA, specifically, by executing the setup phase after
every K iteration, in both the training and testing stages. The value of K can
vary in real-world scenarios, but the larger value will inevitably incur
higher risks of keys being compromised. In the event of key leakage, an
attacker will only have access to a limited amount of information instead of
all encrypted information if keys are regenerated periodically.

###  5.2 Other Considerations

Scalability in FL directly defines the maximum number of participating clients
in the system and indirectly dictates how much data will be used during
training and how generalizable the trained model will be. This can be severely
hampered if the individual privacy modules or the underlying FL framework are
limited on the number of clients participating or the particular way of the
data partition. Our core solution is agnostic on the number of participating
clients and the data partition schemes, especially in the cross-silo
scenarios. As a result, our solution’s scalability is only dependent on the
underlying FL framework and on how key generation and key exchange between
clients are handled. Also, our solution is scalable in the sense that, unlike
homomorphic encryption, we employ lightweight masks through random noise, and
the mask can be naturally decrypted through summation.

##  6 Experiments

We conducted extensive experiments on three classification datasets. Federated
learning is simulated with the Virtual Client Engine of the Flower toolkit
(Beutel et al., 2020).

###  6.1 Datasets

Experiments are conducted over three datasets: _Banking dataset_ Moro et al.
(2011), _Adult income dataset_ Kohavi et al. (1996) and _Taobao ad-
display/click dataset_ Li et al. (2021a). The banking dataset is related to
the direct marketing campaigns of a Portuguese banking institution. It
contains $45,211$ rows and $18$ columns ordered by date. The adult income
dataset is a classification dataset aiming to predict whether the income
exceeds 50K a year based on census data. It contains $48,842$ and $14$
columns. We also conduct our experiment over a production scale ad-
display/click dataset of Taobao Li et al. (2021a). The dataset contains $26$
million interactions (click/non-click when an Ad was shown) and $847$ thousand
items across an 8-day period.

###  6.2 Feature and Client Partitioning

Banking Datasets: We keep the housing, loan, contact, day, month, campaign,
pdays, previous, poutcome features in the _active party_. Features default,
balance are seen in _passive parties_ $1$ and $2$, while age, job, marital,
education are kept in _passive parties_ $3$ and $4$.

Adult Income Dataset: We keep features workclass, occupation, capital-gain,
capital-loss, hours-per-week in the active party and race, marital-status,
relationship, age gender, native-country are kept by _passive parties_ $1$ and
$2$, while education is held by _passive parties_ $3$ and $4$.

Taobao Dataset: We keep pid, cms_group_id, final_gender_code, age_level,
pvalue_level, shopping_level, occupation, cate_id, brand, new_user_class_level
, price features in the active party and final_gender_code, age_level,
occupation are possessed by _passive parties_ $1$ and $2$, while pvalue_level,
shopping_level are kept in the _passive parties_ $3$ and $4$.

Model Architecture. Features and models are partitioned among different
parties in experimental settings. In the Banking dataset, the active party
used Linear(57, 64); passive party $1$ and $2$ used unbiased Linear(3, 64);
passive party $3$ and $4$ used unbiased Linear(20, 64). The three local
modules combined are equivalent to Linear(80, 64). The global module owned by
the aggregator comprised Linear(64, 1). In the Adult Income dataset, the
active party, passive party $1$ and $2$, and passive party $3$ and $4$
possessed Linear(27, 64), unbiased Linear(63, 64), and unbiased Linear(16, 64)
respectively. The three are equivalent to Linear(106, 64). The global module
had Linear(64, 1). In the Taobao dataset, Linear(197, 128), Linear(11, 128),
and Linear(6, 128), which were equivalent to Linear(214, 128), were utilised
by the active party, passive party $1$ and $2$, and passive party $3$ and $4$
respectively. The aggregator maintained a global module with Linear(128, 1).
We used a learning rate of 0.01 and a batch size of 256. We applied ReLU
activation to all layers except the output layer.

###  6.3 Compute and Communication Overhead

We conduct experiments over three datasets to measure both the computation and
the communication cost of VFL training. The computation cost is measured
through CPU time (in milliseconds), and the communication cost is measured
through the transmission size (in bytes). We also measure the overhead cost
that shows the extra CPU time or communication compared to unsecured VFL
training. All experiments are reported with 1 setup phase and 5 training
rounds, and each experiment is repeated 10 times, and averages and standard
deviations are reported. Each experiment is repeated 10 times.

As mentioned in Section 5.1, in practice, each party should create new key
pairs routinely to mitigate the risk of adversaries from accessing
confidential information in the event of secret key leakage. In our
experiments, the key pairs and the shared secrets will be regenerated for
every 5 iterations.

###  6.4 Results

| Active Party CPU time (ms) | Passive Party CPU time (ms)
---|---|---
| Training phase | Testing phase | Training phase | Testing phase
Dataset |  Total |  Overhead |  Total |  Overhead |  Total |  Overhead |  Total |  Overhead
Banking |  $1162\pm 527$ |  $198\pm 12$ |  $325\pm 15$ |  $197\pm 12$ |  $152\pm 6$ |  $116\pm 7$ |  $139\pm 6$ |  $114\pm 7$
Adult Income |  $814\pm 496$ |  $202\pm 9$ |  $292\pm 12$ |  $200\pm 10$ |  $165\pm 14$ |  $120\pm 13$ |  $148\pm 16$ |  $118\pm 13$
Taobao |  $2007\pm 649$ |  $185\pm 3$ |  $429\pm 7$ |  $184\pm 3$ |  $142\pm 9$ |  $106\pm 3$ |  $127\pm 5$ |  $105\pm 3$
Table 1: Results on the CPU time using secure aggregation on VFL. The CPU times (in milliseconds) are reported. The overhead columns show extra CPU time compared with unsecured VFL training.  | Active Party Data Transmission (bytes) | Passive Party Data Transmission (bytes)
---|---|---
| Training phase | Testing phase | Training phase | Testing phase
Dataset |  Total |  Overhead |  Total |  Overhead |  Total |  Overhead |  Total |  Overhead
Banking |  959702 |  144826 |  597762 |  144826 |  823803 |  135541 |  464243 |  135541
Adult Income |  1031382 |  144826 |  597762 |  144826 |  895483 |  135541 |  464243 |  135541
Taobao |  1629142 |  144826 |  925442 |  144826 |  1493243 |  135541 |  791923 |  135541
Table 2: Results on the communication both in size (bytes) using secure
aggregation on VFL. The overhead columns show the extra CPU time compared with
unsecured VFL training.

In Table 1 we report the CPU time as a measure to show the computation cost
using secure aggregation on VFL. The CPU time is reported in milliseconds and
it is reported separately for the active party and passive parties. Table 2
shows the transmission size in bytes for the method and is also demonstrated
on both the active and passive parties.

As demonstrated in both tables, the overhead accounts for a relatively small
part of the total amount, in both CPU time and communication size. The CPU
time overhead is caused by parties adding masks to their original output and
encryption/decryption of sample IDs. The communication overhead is introduced
by broadcasting encrypted sample IDs, which are larger than plain text. As the
masks can be cancelled out by summing them, the unmasking process is very
efficient. The results are from simple models, and the total amount in
practice can dwarf the overhead if more complex models are used.

###  6.5 Abalation Study

In this section, we demonstrate the efficiency of our SA through an ablation
study to compare our method and homomorphic encryption (HE). The experiment
compares how secure aggregation (SA) and HE process dot productions.

Assume the input tensor is of size (Batch size, 8), and the weight tenor is
(8, 8). Tensor shapes in the comparison are smaller than tensors used by a
passive party in experiments. Given that the HE libraries do not support
matrix operations, both SA and HE implementations are not optimized by any
Python modules, such as numpy. We use HE functions from Python module _Phe_
Data61 (2013) and _SEAL-Python_ Huelse (2023). _Phe_ module implements the
Pallier cryptosystem in Python, and _SEAL-Python_ creates Python bindings for
APIs in Microsoft SEAL SEAL  using Pybind11 Jakob et al. (2017). The HE
implementation in this comparison inevitably involves nested Python loops. For
large matrices or more advanced operations, implementations in other
languages, e.g., C++, C#, are more suitable. The results can be found in Fig.
2, which clearly shows the efficiency of SA. It shows that our SA can achieve
$9.1\text{\times}{10}^{2}$ $\sim$ $3.8\text{\times}{10}^{4}$ speedup compared
to HE.

Figure 2: Comparison of average CPU time for different batch sizes, using SA
and HE from Phe and SEAL-Python. Y-axis is in log-scale. The results are
collected from 10 experiments.

##  7 Conclusion

In this work, we consider the challenge of privacy-preserving training in
vertical federated learning settings. We provide the first framework to use
secure aggregation in the setting of vertical FL by implementing state-of-the-
art security modules for Secure Aggregation (SA) by adding noises when
communicating with the central aggregator. Our method is efficient and
accurate in the sense that it will not change the underlying results and
performance by adding security modules. We also provide a unique ablation
study between our method and the homomorphic encryption method (HE) to show
that our method can achieve $9.1\text{\times}{10}^{2}$ $\sim$
$3.8\text{\times}{10}^{4}$ speedup compared to homomorphic encryption (HE).
Our current method works with the pre-training step. A possible avenue for
future work would be to explore how to generalize the secure aggregation
method to include all kinds of vertical FL settings.

## References

  * Barker et al. (2017) Barker, E., Chen, L., Keller, S., Roginsky, A., Vassilev, A., and Davis, R.  Recommendation for pair-wise key-establishment schemes using discrete logarithm cryptography.  Technical report, National Institute of Standards and Technology, 2017\.
  * Beutel et al. (2020) Beutel, D. J., Topal, T., Mathur, A., Qiu, X., Parcollet, T., de Gusmão, P. P., and Lane, N. D.  Flower: A friendly federated learning research framework.  _arXiv preprint arXiv:2007.14390_ , 2020.
  * Bonawitz et al. (2016) Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K.  Practical secure aggregation for federated learning on user-held data.  _arXiv preprint arXiv:1611.04482_ , 2016.
  * Bonawitz et al. (2017) Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K.  Practical secure aggregation for privacy-preserving machine learning.  In _proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 1175–1191, 2017.
  * Chen et al. (2020) Chen, T., Jin, X., Sun, Y., and Yin, W.  Vafl: a method of vertical asynchronous federated learning.  _arXiv preprint arXiv:2007.06081_ , 2020.
  * Data61 (2013) Data61, C.  Python paillier library.  https://github.com/data61/python-paillier, 2013.
  * Diffie & Hellman (1976) Diffie, W. and Hellman, M.  New directions in cryptography.  _IEEE transactions on Information Theory_ , 22(6):644–654, 1976.
  * Fu et al. (2022) Fu, F., Xue, H., Cheng, Y., Tao, Y., and Cui, B.  Blindfl: Vertical federated machine learning without peeking into your data.  In _Proceedings of the 2022 International Conference on Management of Data_ , pp. 1316–1330, 2022.
  * Huelse (2023) Huelse.  Microsoft seal for python.  https://github.com/Huelse/SEAL-Python, 2023.
  * Jakob et al. (2017) Jakob, W., Rhinelander, J., and Moldovan, D.  pybind11 – seamless operability between c++11 and python, 2017.  https://github.com/pybind/pybind11.
  * Jin et al. (2021) Jin, X., Chen, P.-Y., Hsu, C.-Y., Yu, C.-M., and Chen, T.  Cafe: Catastrophic data leakage in vertical federated learning.  _Advances in Neural Information Processing Systems_ , 34:994–1006, 2021.
  * Kang et al. (2022) Kang, Y., He, Y., Luo, J., Fan, T., Liu, Y., and Yang, Q.  Privacy-preserving federated adversarial domain adaptation over feature groups for interpretability.  _IEEE Transactions on Big Data_ , 2022.
  * Kohavi et al. (1996) Kohavi, R. et al.  Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid.  In _Kdd_ , volume 96, pp. 202–207, 1996.
  * Li et al. (2021a) Li, L., Hong, J., Min, S., and Xue, Y.  A novel ctr prediction model based on deepfm for taobao data.  In _2021 IEEE International Conference on Artificial Intelligence and Industrial Design (AIID)_ , pp. 184–187. IEEE, 2021a.
  * Li et al. (2021b) Li, Q., Wen, Z., Wu, Z., Hu, S., Wang, N., Li, Y., Liu, X., and He, B.  A survey on federated learning systems: vision, hype and reality for data privacy and protection.  _IEEE Transactions on Knowledge and Data Engineering_ , 2021b.
  * Li et al. (2020) Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V.  Federated optimization in heterogeneous networks.  _Proceedings of Machine Learning and Systems_ , 2:429–450, 2020.
  * Liu et al. (2020) Liu, Y., Zhang, X., and Wang, L.  Asymmetrical vertical federated learning.  _arXiv preprint arXiv:2004.07427_ , 2020.
  * Liu et al. (2022) Liu, Y., Kang, Y., Zou, T., Pu, Y., He, Y., Ye, X., Ouyang, Y., Zhang, Y.-Q., and Yang, Q.  Vertical federated learning.  2022\.
  * Lu & Ding (2020) Lu, L. and Ding, N.  Multi-party private set intersection in vertical federated learning.  In _2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)_ , pp. 707–714. IEEE, 2020.
  * McMahan et al. (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pp. 1273–1282. PMLR, 2017.
  * Moro et al. (2011) Moro, S., Laureano, R., and Cortez, P.  Using data mining for bank direct marketing: An application of the crisp-dm methodology.  2011\.
  * Qiu et al. (2022) Qiu, X., Fernandez-Marques, J., Porto Buarque de Gusmão, P., Gao, Y., Parcollet, T., and Lane, N. D.  Zerofl: Efficient on-device training for federated learning with local sparsity.  In _International Conference on Learning Representations (ICLR)_ , 2022.
  * (23) SEAL.  Microsoft SEAL (release 4.1).  https://github.com/Microsoft/SEAL, January 2023.  Microsoft Research, Redmond, WA.
  * Wei et al. (2022) Wei, K., Li, J., Ma, C., Ding, M., Wei, S., Wu, F., Chen, G., and Ranbaduge, T.  Vertical federated learning: Challenges, methodologies and experiments.  _arXiv preprint arXiv:2202.04309_ , 2022.
  * Yang et al. (2019) Yang, Q., Liu, Y., Chen, T., and Tong, Y.  Federated machine learning: Concept and applications.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 10(2):1–19, 2019.
  * Yu & Li (2021) Yu, R. and Li, P.  Toward resource-efficient federated learning in mobile edge computing.  _IEEE Network_ , 35(1):148–155, 2021.
  * Zhang & Zhu (2020) Zhang, Y. and Zhu, H.  Additively homomorphical encryption based deep neural network for asymmetrically collaborative machine learning.  _arXiv preprint arXiv:2007.06849_ , 2020.
  * Zhao et al. (2020) Zhao, B., Mopuri, K. R., and Bilen, H.  idlg: Improved deep leakage from gradients.  _arXiv preprint arXiv:2001.02610_ , 2020.
  * Zhou et al. (2021) Zhou, Z., Tian, Y., and Peng, C.  Privacy-preserving federated learning framework with general aggregation and multiparty entity matching.  _Wireless Communications and Mobile Computing_ , 2021:1–14, 2021.
  * Zhu et al. (2019) Zhu, L., Liu, Z., and Han, S.  Deep leakage from gradients.  _Advances in neural information processing systems_ , 32, 2019.