\subsection{Notation}

\section{Introduction}
Future generation wireless systems are expected to support a wide range of smart devices while achieving high spectrum and energy efficiency. It is known that the conventional orthogonal multiple access (OMA) is difficult to meet these future requirements due to inefficient use of radio resources \cite{tse_book}. This calls for more efficient multiplexing schemes for providing connectivity to the growing number of devices. In fact, this call may have been partially answered in the classical studies on the class of broadcast channel (BC) \cite[Ch. 6.2.2]{tse_book}, where superposition coding and successive interference cancellation (SIC) are two key ingredients for achieving the capacity of the scalar Gaussian BC effectively. Building upon this result, many popular multiple access schemes have successfully adopted these two techniques for enabling simultaneous wireless access for multiple users/devices. These schemes are sometimes referred to as non-orthogonal multiple access (NOMA) \cite{Ding17J,9693417}. Since the major development of finite blocklength information theory \cite{5452208}, refining the performance of multiple access schemes with homogeneous and finite blocklength constraints has drawn some attention, e.g., \cite{8277977,8345745,8933345}.

Recently, the coexistence between enhanced mobile broadband (eMBB) and ultra-reliable low-latency communications (URLLC) was discussed in \cite{8403963,8476595,8647460}. Notably, \cite{8476595,8647460} introduce heterogenous NOMA to serve both eMBB and URLLC users using the same time/frequency resources. However, in the downlink BC, the decoding of URLLC signals cannot leverage SIC but can only treat the \emph{partially} received eMBB symbols as noise owing to the URLLC latency constraint. To address this issue, \cite{9518265,9838392} introduces early decoding which allows the strong user with short packets to perform SIC based on partially received superimposed symbol blocks when certain conditions regarding the channel and blocklength are met. That said, SIC could introduce error propagation, extra decoding latency and complexity and may compromise users' privacy. In addition, most of the works assume using capacity-achieving signaling such as Gaussian codes \cite[Eq. (6)]{7605463} and shell codes, i.e., codewords drawn from a power shell \cite[Eq. (5)]{7605463}. In practice, the current prevailing approach is to adopt channel coding with discrete constellations, e.g., quadrature amplitude modulation (QAM) \cite{TS138212_v16p8}. This motivates us to design practical schemes based on \emph{discrete signaling} and \emph{single-user decoding (SUD)} for multiplexing heterogeneous services, aiming at approaching the performance under Gaussian codes or shell codes with perfect SIC.

Discrete signaling and treating interference as noise (TIN), i.e., SUD, in the infinite blocklength regime have been investigated in our previous works \cite{8291591,9535131}. However, under \emph{heterogeneous finite blocklength} and \emph{non-vanishing error probability} constraints, how to effectively manage heterogeneous interference across received symbol sequences has not been investigated. Moreover, the characterization of second-order achievable rates with practical modulations and TIN for this scenario is lacking. In this paper, we introduce a new downlink transmission scheme based on practical discrete signaling and low-complexity SUD for the downlink BC with heterogeneous blocklength and error probability constraints. We first design the discrete input distribution for each downlink user according to the heterogeneity in interference statistics. We then analyze the achievable rate of each user given its own blocklength and error probability requirements. Simulation results show that in terms of the achievable rate and error probability performance, the proposed scheme with QAM and TIN can operate close to the benchmark scheme which assumes using capacity-achieving signaling and perfect SIC.

\textbf{Notations}: All logarithms are base 2. $Q^{-1}(x)$ denotes the inverse of Q function $Q(x)=\int^{\infty}_{x}\frac{1}{\sqrt{2\pi}}e^{-\frac{t^2}{2}}dt$. We write $f(x) = O(g(x))$ if $\exists M\in\mathbb{R}^+,x_0\in\mathbb{R}$ such that $|f(x)| \leq Mg(x), \forall x\geq x_0$. Random variables are represented by uppercase letters, e.g., $X$, and their realizations are represented by lowercase letters, e.g., $x$. $X^{[n]}$ denotes the sequence $X[1],\ldots,X[n]$.

\section{System Model}\label{sec:model}
We consider a scalar downlink BC that consists of one transmitter and two receivers. We leave the generalization to the $K$-user case in our journal version \cite{JSACQiu22}. We denote by $\boldsymbol{x}_i \in \mathbb{C}^{N_i}$ the transmitted packet of coded symbols for user $i$, where $i\in \{1,2\}$ and $N_i$ is the length. We assume that $N_1 \leq N_2$ without loss of generality. Thus, the proposed scheme do not preclude the homogeneous blocklength case. The transmitter broadcasts the superimposed coded symbols of length $N_2$
\begin{align}
\boldsymbol{x} = ([\boldsymbol{x}_1,\boldsymbol{0}_{N_2-N_1}]+\boldsymbol{x}_2)=\boldsymbol{x}'_1+\boldsymbol{x}'_2 \in \mathbb{C}^{N_2}, \label{eq:sys1}
\end{align}
to both users, where we define $\boldsymbol{x}'_i \triangleq [\boldsymbol{x}_i,\boldsymbol{0}^{N_2-N_i}]$. Here, we consider that $\boldsymbol{x}_1$ needs to be transmitted as soon as possible owing to its urgency, e.g., URLLC services. Thus, $\boldsymbol{x}_1$ is superimposed with the first $N_1$ symbols of $\boldsymbol{x}_2$. We emphasize that the position of $\boldsymbol{x}_1$ in $\boldsymbol{x}'_1$ does not affect our scheme. In addition, we have the following individual power constraint $P_i$ and total power constraint $P$, and $P_i \leq P$.
\begin{align}
&\frac{1}{N_i}\sum\nolimits_{j=1}^{N_i}|x_i[j]|^2 \leq P_i,\label{eq:power_ind}\\
&\frac{1}{N_2}\sum\nolimits^{N_2}_{j=1}(|x'_1[j] |^2+|x'_2[j] |^2) \leq P.\label{eq:power_total}
\end{align}

We denote by $h_i \in \mathbb{C}$ the channel of user $i$, $i\in\{1,2\}$. We assume that $h_i$ is subject to quasi-static fading, i.e., $h_i$ remains unchanged over the duration of each transmission frame. The received signals are given by
\begin{align}
y_1[j] =& h_1(x_1[j]+x_2[j])+z_1[j], \;j=1,\ldots,N_1,\label{eq:y1} \\
y_2[j] =& \left\{ {\begin{array}{*{20}{c}}
h_2(x_1[j]+x_2[j])+z_2[j],\; j=1,\ldots,N_1\\
h_2x_2[j]+z_2[j], \;j=N_1+1,\ldots,N_2\\
\end{array}} \right.\label{eq:y2},
\end{align}
respectively, where $z_i[j] \sim \mathcal{CN}(0,1)$ is the i.i.d. Gaussian noise. Clearly, user 2's symbols $y_2[N_1+1],\ldots,y_2[N_2]$ are interference-free. We assume that the transmitter has the knowledge of channel magnitudes while the receiver has full channel state information. We stress that even for such a fundamental channel model, many problems are yet to be solved, e.g., the optimal communication strategy, the optimal input distribution, and the second-order converse. Two important performance metrics are jointly considered in this paper, namely the achievable rate $R_i$ and upper bound on the average decoding error probability $\epsilon_i$ for user $i\in\{1,2\}$.

\section{Proposed Discrete Signaling with SUD}
In this section, we introduce the proposed scheme with discrete signaling and TIN. Although we use binary codes and QAM as the underlying channel codes and constellations, respectively, our scheme does not preclude the use of non-binary codes \cite{8066336} and multi-dimensional constellations \cite{8291591}.

We assume that $|h_1|>|h_2|$. This corresponds to the interesting case where the URLLC user, i.e., user 1, is the strong user but performing SIC may not be feasible based on partially received superimposed symbols. The case of $|h_1|<|h_2|$ will be discussed later.

\subsubsection{Encoding}
For user $i\in\{1,2\}$, a length-$k_i$ binary source sequence $\boldsymbol{u}_i$ is encoded into a length-$n_i$ binary codeword $\boldsymbol{c}_i$. Codeword $\boldsymbol{c}_i$ is then interleaved, i.e., using bit-interleaved coded modulations (BICM) \cite{CIT-019}, and modulated onto a length-$N_i$ sequence $\boldsymbol{v}_i$. Each user only uses a \emph{single} channel. This ensures that the encoding and decoding (TIN) complexities for each user are the same as in the single-user case.

\subsubsection{Modulation Mapping}\label{sec:2u_const}
To handle heterogeneous interference as shown in \eqref{eq:y2}, user 2 uses two sets of constellations $\Lambda_{2,1}$, and $\Lambda_{2,2}$ while user 1 users one constellation set $\Lambda_1$. Specifically, the modulated symbols satisfy $v_1[j] \in \Lambda_1, \forall j \in \{1,\ldots,N_1\}$ for user 1 and $v_2[j] \in \Lambda_{2,1}, \forall j \in \{1,\ldots,N_1\}$, $v_2[j] \in \Lambda_{2,2}, \forall j \in \{N_1+1\ldots,N_2\}$ for user 2. Let $\Lambda_1$, $\Lambda_{2,1}$, and $\Lambda_{2,2}$ represent three regular QAM constellations with zero means and minimum distance 1. We further define $m_1\triangleq \log |\Lambda_1|$, $m_{2,1}\triangleq \log |\Lambda_{2,1}|$ and $m_{2,2}\triangleq \log |\Lambda_{2,2}|$ to be the modulation orders. The relationship between codeword length $n_i$ and coded symbol length $N_i$ for user $i$ satisfies
\begin{align}
n_1 =& N_1m_1, \label{u1n1}\\
n_2 =& N_1m_{2,1}+ (N_2-N_1)m_{2,2}.\label{u2n2}
\end{align}

We then introduce the design criteria for modulation orders. To do so, we first need to introduce the following sub-block power constraints. Since user 2 uses two constellation sets, we can decompose user 2's symbol block $\boldsymbol{x}_2$ into two sub-blocks. The power constraints for these sub-blocks satisfy
\begin{align}
&\frac{1}{N_i-N_{i-1}}\sum\nolimits_{j=N_{i-1}+1}^{N_i}|x_2[j]|^2 \leq P_{2,i},i\in\{1,2\},\label{eq:power_c2sub}\\
&\frac{N_1}{N_2}P_{2,1}+\frac{N_2-N_1}{N_2}P_{2,2}  = P_2,\label{eq:power_c2p}\\
&\frac{N_1}{N_2}(P_1+P_{2,1})+\frac{N_2-N_1}{N_2}P_{2,2}= P\label{eq:power_c2c1p},
\end{align}
where \eqref{eq:power_c2sub} gives the sub-block power constraint for $\boldsymbol{x}_2$ and $N_0=0$, \eqref{eq:power_c2p} gives the relationship between sub-block power constraint \eqref{eq:power_c2sub} and individual power constraint \eqref{eq:power_ind} for user 2, and \eqref{eq:power_c2c1p} gives the relationship between each user's power constraint and total power constraint \eqref{eq:power_total}. The introduction of sub-block power constraints allows to assign different power to each sub-block of $\boldsymbol{x}_2$ for handling heterogeneous interference. Then, we introduce the following constraints on modulation orders $m_1$, $m_{2,1}$, and $m_{2,2}$
\begin{align}
m_1\hspace{-1mm}+\hspace{-1mm}m_{2,1} \leq& \left\lfloor\log  \left(1\hspace{-1mm}+\hspace{-1mm}6(P_1\hspace{-1mm}+\hspace{-1mm}P_{2,1})\max\{|h_1|^2,|h_2|^2\}\right)\right\rfloor,\label{con1}\\
m_{2,1}\leq& \left\lfloor\log  \left(6(P_1+P_{2,1})|h_2|^2\right)\right\rfloor,\label{con2}\\
m_{2,2}\leq& \left\lfloor\log  \left(1+6P_{2,2}|h_2|^2\right)\right\rfloor,\label{con3}
\end{align}
where the flooring operation $\lfloor .\rfloor$ applies because the modulation orders must be integers. The motivation for introducing the modulation order constraints is to strike a balance between the achievable rate and the interference statistics. This can be seen by noting that under TIN and fixed channel gains, increasing the modulation order of only one user increases its achievable rate (until it reaches capacity) but also introduces more interference to other users. One can see that the RHS of \eqref{con1} is reminiscent of the single-user capacity of the strong user while the RHS of \eqref{con2} is reminiscent of the single-user capacity of user 2. The reason for excluding 1 inside the logarithm of \eqref{con2} while including 6 inside all logarithms is closely related to the minimum distance of individual constellation, which will be explained in Section \ref{sec:2up}c. By looking at \eqref{con1}, it is also worth noting that the sum capacity of the $K$-user downlink BC can be upper bounded by the single-user capacity of the strongest user \cite[Ch. 6.2.2]{tse_book}. Thus, one can regard \eqref{con1} as a sum-rate constraint. In addition, \eqref{con1} with $m_{2,1}=0$, \eqref{con2}, and \eqref{con3} are the individual modulation order constraints, where similar arguments apply.

\subsubsection{Power Assignments}\label{sec:2up}
We introduce two \emph{layers} power assignments. The first one is to assign power across different users' modulated symbols at the same time instant within the same sub-block of $\boldsymbol{x}$. The second layer power assignment is performed on top of the first layer power assignment by assigning power across different sub-blocks of $\boldsymbol{x}$.

$3a)$ \emph{First Layer Power Assignment}: The power to $v_1[j]$ and $v_2[j]$ for $j=1,\ldots,N_1$ is chosen such that the superimposed symbol satisfies
\begin{align}
v_1[j]+\sqrt{2^{m_1}}v_2[j]\in\Lambda_1+\sqrt{2^{m_1}}\Lambda_{2,1}, \label{eq:first_P_assign}
\end{align}
where the superimposed constellation $\Lambda_1+\sqrt{2^{m_1}}\Lambda_{2,1}$ is a regular QAM with cardinality $2^{m_1+m_{2,1}}$, zero mean, and minimum distance $d_{\min}(\Lambda_1+\sqrt{2^{m_1}}\Lambda_{2,1})=1$.

$3b)$ \emph{Second Layer Power Assignment}: On top of the first layer power assignment, we assign the power $P_1+P_{2,1}$ and $P_{2,2}$ to the first $N_1$ and the last $N_2-N_1$ symbols, respectively, of $\boldsymbol{x}$ such that the total power constraint is fulfilled. As a result, the transmitted signals for users 1 and 2 after the proposed two layers power assignments are
\begin{align}
x_1[j]=&\eta_1\sqrt{P_1+P_{2,1}}v_1[j],\; j=1,\ldots,N_1, \label{eq:x1} \\
x_2[j]=& \left\{ {\begin{array}{*{20}{c}}
\eta_1 \sqrt{2^{m_1}(P_1+P_{2,1})}v_2[j],\;j=1,\ldots,N_1\\
\eta_2\sqrt{P_{2,2}}v_2[j], \;j=N_1+1,\ldots,N_2\\
\end{array}} \right.,\label{eq:x2}
\end{align}
respectively, where $\eta_1 = \sqrt{\frac{6}{2^{m_1+m_{2,1}}-1}}$ and $\eta_2 = \sqrt{\frac{6}{2^{m_{2,2}}-1}}$ are the normalization factors to ensure both $\Lambda_1+\sqrt{2^{m_1}}\Lambda_{2,1}$ and $\Lambda_{2,2}$ have unit energy. For $X_1\overset{\text{unif}}{\sim}\eta_1\sqrt{P_1+P_{2,1}}\Lambda_1$ and $X_{2,1}\overset{\text{unif}}{\sim}\eta_1\sqrt{2^{m_1}(P_1+P_{2,1})}\Lambda_{2,1}$, and the power assignment in Section \ref{sec:2up}a, we obtain $P_1\hspace{-1mm}=\hspace{-1mm}\mathbb{E}[|X_1|^2]$ and $P_{2,1}\hspace{-1mm}=\hspace{-1mm}\mathbb{E}[|X_{2,1}|^2]$ wher
\begin{align}
P_1
=& \frac{2^{m_1}-1}{2^{m_1+m_{2,1}} -1}\left(\frac{N_2}{N_1}P - \frac{N_2-N_1}{N_1}P_{2,2}\right), \label{eq:P1}\\
P_{2,1}
=&\frac{2^{m_1+m_{2,1}}-2^{m_1}}{2^{m_1+m_{2,1}} -1}\left(\frac{N_2}{N_1}P - \frac{N_2-N_1}{N_1}P_{2,2}\right).\label{eq:P21}
\end{align}
Thus, when $P_{2,2}$ is given, $P_1$ and $P_{2,1}$ become deterministic. In our scheme, we consider balanced second layer power assignment for each sub-block of superimposed symbol block $\boldsymbol{x}$ such that $P_{2,2}=P_1+P_{2,1}$. This also means that each sub-block of $\boldsymbol{v}_2$ has different power $P_{2,2}\neq P_{2,1}$ as long as $P_1 \neq 0$. We will show that this choice is good enough for the proposed scheme with QAM and TIN decoding to achieve rate pairs very close to those assume Gaussian and shell codes with perfect SIC and globally optimized $P_1$, $P_{2,1}$ and $P_{2,2}$ for maximizing achievable rate regions.

$3c)$ \emph{Minimum Distance}: By looking into the individual constellation while treating the other user's signals as noise, one can see that after the channel effects, i.e., $h_1x_1[j]\in h_1\eta_1\sqrt{P_1+P_{2,1}}\Lambda_1$ and $h_2x_2[j]\in h_2\eta_1\sqrt{P_1+P_{2,1}}\Lambda_{2,1}$, the minimum distance of each constellation satisfies
\begin{align}
d_{\min}\left(h_1\eta_1\sqrt{P_1+P_{2,1}}\Lambda_1\right)\overset{\eqref{con1}}{\geq}&1, \\
d_{\min}\left(h_2\eta_1 \sqrt{2^{m_1}(P_1+P_{2,1})}\Lambda_{2,1}\right)\overset{\eqref{con2}}{\geq}&1.\label{eq:dmin2}
\end{align}
Notice that in \eqref{eq:dmin2}, the logarithm in \eqref{con2} without 1 inside leads to a constant minimum distance lower bound. Hence, for any $(h_1,h_2)$ satisfying $|h_1|>|h_2|$, both constraints \eqref{con1}, \eqref{con2}, and the proposed power assignments in \eqref{eq:x1}-\eqref{eq:x2} \emph{guarantee constant minimum distance lower bound} for the superimposed constellation and each individual constellation after channel effects and normalization. The constant minimum distance lower bound is beneficial to TIN decoding for handling structural interference. It is worth noting that the structural interference comes from the fact that the interfering signal is uniformly distributed over a regular QAM in our design. In contrast, the conventional assumption of using Gaussian input distribution makes the interference Gaussian which is highly unstructured. As for $j=N_1+1,\ldots,N_2$, the constellation $\Lambda_{2,2}$ is already a regular QAM with $d_{\min}(\Lambda_{2,2})=1$ and $x_2[j]$ is interference-free. Thus, the first layer power assignment is not required here. With \eqref{con3}, one can easily verify that $d_{\min}(h_2\eta_2\sqrt{P_{2,2}}\Lambda_{2,2})\hspace{-1mm}\geq \hspace{-1mm}1$.

\subsubsection{TIN Decoding}
At the receiver, each user decodes its own messages by treating the other user's signals as noise. Hence, the other user's codebook information is completely unnecessary for the proposed scheme. For user $i$, $i\in\{1,2\}$, the decoder first computes the log-likelihood ratio (LLR) for each bit of the interleaved codeword $\boldsymbol{\tilde{c}}_i$ from the received signals $\boldsymbol{y}_i$ given in Section \ref{sec:model}. Then, the LLR sequence is deinterleaved and passed into a soft-input soft-out decoder. The decoding process is the same as that in the point-to-point channel using BICM \cite{CIT-019}.

\begin{remark}
When $|h_2|<|h_1|$, the first layer power assignment swaps the arguments between constellations $\Lambda_1$ and $\Lambda_{2,1}$ and their modulation orders in \eqref{eq:first_P_assign} in Section \ref{sec:2up}a. That is, we assign the power to $v_1[j]$ and $v_2[j]$ by $v_2[j]+2^{m_{2,1}}v_1[j]$ for $j=1,\ldots,N_1$. The rest of the steps do not change.
\demo
\end{remark}

\section{Finite Blocklength Achievable Rate Analysis}\label{sec:FBL}
In this section, we derive the second-order achievable rate of the downlink BC with discrete signaling and TIN with given blocklength and error probability constraints. The channel order is not required here due to the fact that TIN decoding is adopted. We define the normalized constellations after power assignments for $\boldsymbol{x}_1$ and the two sub-blocks of $\boldsymbol{x}_2$ as $\mathcal{X}_1$, $\mathcal{X}_{2,1}$, and $\mathcal{X}_{2,2}$, respectively.

\subsection{Achievable Rate of User 1}
We first analyze the information density, which is the key to our second-order achievable rate approximation. Based on the definition of information density in \cite{5452208}, the information density of user 1 is derived as
\begin{align}
&i(X_1^{[N_1]};Y_1^{[N_1]}) = \sum\nolimits_{j=1}^{N_1}i(X_1[j];Y_1[j])\label{eq:u1id_basic}\\
=&\hspace{-1mm}\sum_{j=1}^{N_1} \log\hspace{-1mm} \left( \frac{\sum\limits_{x_2[j] \in \mathcal{X}_{2,1}}P(y_1[j]|x_1[j],x_2[j])}{\sum\limits_{x_1[j] \in
\mathcal{X}_1}\sum\limits_{x_2[j] \in \mathcal{X}_{2,1}}P(y_1[j]|x_1[j],x_2[j])P(x_1[j])}\right)\hspace{-1mm}, \label{eq:u1id_basic1}
\end{align}
where we note that $X_1[j], X_2[j]$, and $Y_1[j]$ are i.i.d. for $j=1,\ldots,N_1$ and thus $i(X_1[j];Y_1[j])$ is also i.i.d., $P(y_i[j]|x_1[j],x_{2}[j])=\frac{1}{\pi}e^{-|y_i[j]-h_i(x_1[j]+x_{2}[j])|^2}$ for $i\in\{1,2\}$, and $P(x_1[j]) = \frac{1}{|\mathcal{X}_1|}$ and $P(x_2[j]) = \frac{1}{|\mathcal{X}_{2,1}|}$ due to uniform input distributions of $x_1[j]$ and $x_2[j]$, respectively, for $j=1,\ldots,N_1$. Then, we derive the mutual information for user 1 as
\begin{align}\label{eq:NI1}
I(X_1^{[N_1]};Y_1^{[N_1]})=N_1\mathbb{E}[i(X_1;Y_1)] = N_1I(X_1;Y_1),
\end{align}
where we have dropped the index $[j]$ because $i(X_1[j];Y_1[j])$ is i.i.d.. Further to \eqref{eq:NI1}, we derive $I(X_1;Y_1)$ in \eqref{eq:u1I}.
\begin{figure*}[t]
\begin{align}\label{eq:u1I}
I(X_1;Y_1)= \log|\mathcal{X}_1|-\frac{1}{|\mathcal{X}_{1}|\cdot|\mathcal{X}_{2,1}|}\sum_{x_{1}\in\mathcal{X}_{1}}\sum_{x_{2,1}\in\mathcal{X}_{2,1}}\mathbb{E}_{Z_1}\left[\log \left(\frac{\sum\limits_{x'_1\in \mathcal{X}_1}\sum\limits_{x'_{2,1}\in \mathcal{X}_{2,1}}e^{-|Z_1+h_1(x_1-x'_1+x_{2,1}-x'_{2,1})|^2}}{\sum\limits_{x'_{2,1}\in \mathcal{X}_{2,1}}e^{-|Z_1+h_1(x_{2,1}-x'_{2,1})|^2}}\right) \right].
\end{align}
\hrule
\end{figure*}
Next, we derive the dispersion function for user 1 as
\begin{align}
V(X_1^{[N_1]};&Y_1^{[N_1]})
\overset{\eqref{eq:u1id_basic}}{=}\text{Var}\left[\sum\nolimits_{j=1}^{N_1}i(X_1[j];Y_1[j])\right]\\
=&\sum\nolimits_{j=1}^{N_1}\text{Var}[i(X_1[j];Y_1[j])
= N_1V(X_1;Y_1),\label{eq:u1Vint}
\end{align}
where \eqref{eq:u1Vint} holds because $x_1[j]$ and $x_1[j']$ are independent and $y_1[j]$ and $y_1[j']$ are independent for any $j\neq j'$ and $j,j'\in \{1,\ldots,N_1\}$. We then derive $V(X_1;Y_1)$ in \eqref{eq:u1V}.
\begin{figure*}[t]
\begin{align}
V(X_1;Y_1
=&\frac{1}{|\mathcal{X}_{1}|\cdot|\mathcal{X}_{2,1}|}\sum_{x_{1}\in\mathcal{X}_{1}}\sum_{x_{2,1}\in\mathcal{X}_{2,1}}\mathbb{E}_{Z_1}\left[\left(\log\left( \frac{\sum\limits_{x'_1\in \mathcal{X}_1}\sum\limits_{x'_{2,1}\in \mathcal{X}_{2,1}}e^{-|Z_1+h_1(x_1-x'_1+x_{2,1}-x'_{2,1})|^2}}{\sum\limits_{x'_{2,1}\in \mathcal{X}_{2,1}}e^{-|Z_1+h_1(x_{2,1}-x'_{2,1})|^2}}\right)\right)^2 \right]\nonumber \\
&-\left(\frac{1}{|\mathcal{X}_{1}|\cdot|\mathcal{X}_{2,1}|}\sum_{x_{1}\in\mathcal{X}_{1}}\sum_{x_{2,1}\in\mathcal{X}_{2,1}}\mathbb{E}_{Z_1}\left[\log \left(\frac{\sum\limits_{x'_1\in \mathcal{X}_1}\sum\limits_{x'_{2,1}\in \mathcal{X}_{2,1}}e^{-|Z_1+h_1(x_1-x'_1+x_{2,1}-x'_{2,1})|^2}}{\sum\limits_{x'_{2,1}\in \mathcal{X}_{2,1}}e^{-|Z_1+h_1(x_{2,1}-x'_{2,1})|^2}}\right) \right]\right)^2 \label{eq:u1V}.
\end{align}
\hrule
\end{figure*}

We then have the following proposition for the second-order achievable rate of user 1.
\begin{proposition}\label{prof:u1}
Define $\epsilon_1$ to be the upper bound on the average TIN decoding error probability of user 1. For the channel model in \eqref{eq:y1}, user 1's achievable rate by treating user 2's signals as interference is bounded by
\begin{align}\label{eq:u1rate}
R_1 \hspace{-1mm} \leq \hspace{-1mm} I(X_1;Y_1)\hspace{-1mm}-\hspace{-1mm}\sqrt{\frac{V(X_1;Y_1)}{N_1}}Q^{-1}\left(\epsilon_1\right)\hspace{-1mm}+\hspace{-1mm}O\left(\frac{\log  N_1}{N_1}\right)\hspace{-1mm}, \hspace{-1mm}
\end{align}
where $I(X_1;Y_1)$ is in \eqref{eq:u1I} and $V(X_1;Y_1)$ is in \eqref{eq:u1V}.
\end{proposition}
\emph{Proof of Proposition \ref{prof:u1} (Sketch):} We denote by $M_1$ the codebook size for user 1. First, user 1's decoding error probability under TIN as a function of $N_1$ can be upper bounded by using the dependence testing bound \cite[Th. 17]{5452208}
\begin{align}
\epsilon_1(N_1) \leq& \mathbb{E}\left[2^{-\max\left\{0,i(X_1^{[N_1]};Y_1^{[N_1]})-\log \frac{M_1-1}{2}\right\}}\right]\\
\leq& \mathbb{P}\left[ \frac{M_1-1}{2}2^{-i(X^{[N_1]},Y^{[N_1]})}> \frac{1}{\sqrt{N_1}}\right]\hspace{-1mm}+\hspace{-1mm}\frac{1}{\sqrt{N_1}}.\label{eq:RCU}
\end{align}
With \eqref{eq:RCU}, we then use the Berry-Esseen central limit theorem \cite[Th. 2, Ch. XVI-5]{Feller_book} and get
\begin{align}\label{eq:CLT_u1}
\epsilon_1(N_1) \leq& Q\left( \frac{N_1I(X_1;Y_1)-\log  \frac{M_1-1}{2} -\log  \sqrt{N_1}}{\sqrt{N_1 V(X_1;Y_1)}}\right) \nonumber \\
&+O\left(\frac{1}{\sqrt{N_1}}\right) \leq \epsilon_1,
\end{align}
where we have used the properties in \eqref{eq:NI1} and \eqref{eq:u1V}. The last inequality of \eqref{eq:CLT_u1} ensures that the error probability \eqref{eq:RCU} is upper bounded by $\epsilon_1$ for all $N_1$. One can then solve for $\log (M_1-1)$ and perform the first-order Taylor expansion of $Q^{-1}(.)$ about $\epsilon_1$. Finally, dividing both sides of the resultant inequality by $N_1$ and using the fact that $R_1=\frac{\log M_1}{N_1}\leq\frac{\log (M_1-1)+1}{N_1}$ for $M_1\geq 2$, we obtain \eqref{eq:u1rate}. \demo

Since user 1 has the shortest symbol blocks, each intended symbol for user 1 experiences the same interference statistics, which is similar to the homogeneous blocklength case. However, the interference experienced by user 2 behaves differently from user 1 as we will see in the next section.

\subsection{Achievable Rate of User 2}\label{sec:u2}
Since $\boldsymbol{x}_2$ will be partially interfered, $X_2[j]$ and $Y_2[j]$ are i.i.d. when either $j = 1,\ldots,N_1$ or $j=N_1+1,\ldots,N_2$ whereas $X_2[j](Y_2[j])$ and $X_2[j'](Y_2[j'])$ are \emph{not necessarily} identically distributed for $j\in\{1,\ldots,N_1\}$ and $j'\in\{N_1+1,\ldots,N_2\}$. In this case, we let $X_{2,1}$($Y_{2,1}$) to represent the random variables $X_2[j]$($Y_2[j]$) for $j \in \{1, . . . ,N_1\}$ and let $X_{2,2}$($Y_{2,2}$) to represent the random variables $X_2[j]$($Y_2[j]$) for $j \in \{N_1 + 1, . . . ,N_2\}$. The information density for user 2 is
\begin{align}
&i(X_2^{[N_2]};Y_2^{[N_2]}) = \sum\nolimits_{j=1}^{N_2}i(X_2[j];Y_2[j]) \label{eq:u2id_basic}\\
&=\hspace{-1mm}\sum_{j=1}^{N_1}\log  \left( \frac{\sum\limits_{x_1[j]\in\mathcal{X}_1}P(y_2[j]|x_2[j],x_1[j])}{\sum\limits_{x_2[j]\in\mathcal{X}_{2,1}}\sum\limits_{x_1[j]\in\mathcal{X}_1}P(y_2[j]|x_2[j],x_1[j])P(x_2[j])}\right)\nonumber \\
&+\hspace{-2mm}\sum\limits_{j=N_1+1}^{N_2}\log \left( \frac{P(y_2[j]|x_2[j])}{\sum\limits_{x_2[j]\in\mathcal{X}_{2,2}}P(y_2[j]|x_2[j])P(x_2[j])} \right).\label{eq:u2id}
\end{align}
With \eqref{eq:u2id}, the mutual information under TIN for user 2 is
\begin{align}\label{eq:NI2}
I(X_2^{[N_2]};Y_2^{[N_2]})=\sum\nolimits^2_{i=1}(N_i-N_{i-1})I(X_{2,i};Y_{2,i}),
\end{align}
where $I(X_{2,1};Y_{2,1})$ can be easily obtained similarly to \eqref{eq:u1I} by swapping the arguments between user 1 and user 2, and $I(X_{2,2};Y_{2,2})$ is the mutual information of the single-user channel. Next, we derive the dispersion function as
\begin{align}\label{eq:N2V2}
V(X_2^{[N_2]};Y_2^{[N_2]}) =\sum\nolimits^2_{i=1}(N_i-N_{i-1})V(X_{2,i};Y_{2,i}),
\end{align}
where $V(X_{2,1};Y_{2,1})$ can be easily obtained from \eqref{eq:u1V} by swapping the arguments between user 1 and user 2, and $V(X_{2,2};Y_{2,2})$ is the dispersion of the single-user channel.

Having derived the mutual information and dispersion, we have the following proposition for the second-order achievable rate of user 2.
\begin{proposition}\label{prof:u2}
Define $\epsilon_2$ to be the upper bound on the average TIN decoding error probability of user 2. For the channel model in \eqref{eq:y2}, user 2's achievable rate by treating user 1's signals as interference is bounded by
\begin{align}\label{eq:u2rate}
R_2 \leq& \frac{\sum^2_{i=1}N_i-N_{i-1}}{N_2}I(X_{2,i};Y_{2,i}) \nonumber\\
&-\frac{\sqrt{\sum^2_{i=1}(N_i-N_{i-1})V(X_{2,i};Y_{2,i})}}{N_2}Q^{-1}\left(\epsilon_2\right)\nonumber\\
&+O\left(\frac{\log  N_2}{N_2}\right).
\end{align}
\end{proposition}
The proof of Proposition \ref{prof:u2} follows from that of Proposition \ref{prof:u1} and is omitted due to space limitation. The impacts of the length of interfering symbols on user 2's achievable rate are clearly shown in \eqref{eq:u2rate}. This is different from the homogeneous blocklength case for which a single signal-to-interference-plus-noise ratio (SINR), i.e., $\frac{P_2|h_2|^2}{P_1|h_2|^2+1}$, could not capture the effects of partially interfered symbol sequences.

\subsection{Modulation and Code Design}
With the derived achievable rates, we can design the modulations and channel codes for the proposed schemes. First, consider the blocklength $(N_1,N_2)$ and error probability $(\epsilon_1,\epsilon_2)$ requirements for both users. We design the modulations $(\Lambda_1,\Lambda_{2,1},\Lambda_{2,2})$ whose orders satisfying \eqref{con1} such that the achievable rate pair computed by using \eqref{eq:u1rate} and \eqref{eq:u2rate} reach a target rate pair $(R_1,R_2)$. Note that given the modulations, the power assignments become deterministic according to Section \ref{sec:2up}. Moreover, users 1 and 2's codeword lengths satisfy $(n_1,n_2)=(N_1m_1,N_1m_{2,1}+(N_2-N_1)m_{2,2})$ according to \eqref{u1n1} and \eqref{u2n2} in Section \ref{sec:2u_const}. To match users 1 and 2's transmission rates with their corresponding achievable rates, i.e., $(R_1,R_2) =  (\frac{k_1}{n_1}m_1,\frac{k_2}{n_2}(\frac{N_1}{N_2}m_{2,1}+\frac{N_2-N_1}{N_2}m_{2,2}))$, the information lengths of users 1 and 2's channel codes are obtained as $(k_1,k_2)=(R_1N_1,R_2N_2)$. The problem can now be converted into designing good point-to-point codes with the specified information and codeword lengths.

\section{Simulation Results}\label{sec:sim}
\subsection{Achievable Rate}\label{sec:rate_sim}
We present a design example to showcase the performance of the proposed scheme with QAM and TIN. We define the signal-to-noise ratio $\msf{SNR}_i \triangleq P|h_i|^2$ for user $i\in\{1,2\}$. We consider $(\msf{SNR}_1,\msf{SNR}_2)=(18,5)$ in dB, $(N_1,N_2)=(128,256)$, and $(\epsilon_1,\epsilon_2)=(10^{-6},10^{-4})$. For comparison purposes, we have included two benchmark schemes using shell codes and Gaussian codes and assume perfect SIC regardless of blocklength. We stress that the perfect SIC assumption in the benchmark schemes is used for comparison purposes only. Hence, the performance of the benchmark schemes with perfect SIC serves as an upper bound of all achievable schemes that take into account imperfect SIC, e.g., \cite{9518265,9838392}. The achievable rates of the benchmark schemes can be derived by following from Section \ref{sec:FBL}. Note that although both Gaussian and shell codes achieve capacity in the infinite blocklength regime, shell codes have a larger second-order achievable rate due to smaller dispersion \cite[Eqs. (23)\&(25)]{7605463}.

\begin{figure}[t!]
	\centering
\includegraphics[width=3.4in,clip,keepaspectratio]{Subplot1.pdf}
\caption{(a) Achievable rate; (b) Dispersion; (c) Error probability of user 1; (d) Error probability of user 2. Label: $\square$ QAM without SIC analytical, $--$ Shell codes with perfect SIC, $-\cdot-\cdot$ Gaussian codes with perfect SIC, $-\hspace{-1mm}\bullet\hspace{-1mm}-$ 5G CA-polar BER, $-\cdot\bullet-\cdot$ 5G CA-polar BLER.}
\label{fig:ar2}
\end{figure}

The second-order achievable rate pairs (without the third-order term) and the corresponding dispersion of the proposed scheme and the aforementioned two benchmark schemes are shown in Figs. \ref{fig:ar2}(a) and \ref{fig:ar2}(b), respectively. The modulation orders for the proposed scheme are $(m_1,m_{2,1},m_{2,2})=(0,4,4),(2,4,4),(4,2,4),(6,0,4),(6,0,0)$, corresponding to the data points from left to right in the figure. Note that the proposed scheme uses balanced second layer power assignment, i.e., $P_1+P_{2,1}=P_{2,2}$ while the two benchmark schemes use brute-force search for $(P_1,P_{2,1},P_{2,2})$ to obtain their largest possible rate regions. Observe that the proposed scheme with QAM and TIN can achieve rate pairs very close to those under Gaussian signaling and perfect SIC. Meanwhile it is shown in Fig. \ref{fig:ar2}(b) that the dispersion of QAM in the proposed scheme is much smaller than that of Gaussian codes and is no larger than that of shell codes. Since short blocklength and ultra-low target error probability are the main features of URLLC communication scenarios, the second-order term has a substantial impact on the achievable rate. Hence, our results demonstrate that the proposed scheme is promising in supporting heterogeneous URLLC services. Notice that user 1's rate can remain to be the single-user rate while user 2's rate is increasing as shown in the bottom right corner of Fig. \ref{fig:ar2}(a). This is achieved by setting $P_{2,1}=0$ such that increasing $P_{2,2}$ does not affect user 1's second-order achievable rate.

\subsection{Error Probability}\label{sec:err}

We build a practical set-up of the proposed scheme by using off-the-shelf codes. For illustrative purpose, we consider the same channel setting as in Section \ref{sec:rate_sim}, where the proposed scheme with modulation orders $(m_1,m_{2,1},m_{2,2})=(2,4,4)$ achieves a rate pair of $(R_1,R_2) = (1.0174,1.5644)$. Since $(N_1,N_2)=(128,256)$, the channel codes for users 1 and 2 are with $(n_1,k_1)=(256,130)$ and $(n_2,k_2)=(1024,400)$, respectively. Each user employs a 5G standard CRC-aided polar (CA-polar) code with an 11-bit CRC and adopts successive-cancellation list decoding \cite{TS138212_v16p8}. We set the decoding list size 32 for user 1 and 64 for user 2. The bit error rate (BER) and block error rate (BLER) for users 1 and 2 are reported in Figs. \ref{fig:ar2}(c) and \ref{fig:ar2}(d), respectively. We also include the average block error probability upper bound of the benchmark schemes with Gaussian codes and shell codes with perfect SIC as well as that of the proposed scheme with QAM and TIN. The error probability is obtained by rearranging the second-order achievable rate, i.e., \eqref{eq:u1rate} and \eqref{eq:u2rate}. Note that all schemes achieve the same rate pair and use the same power allocation.

Observe that the BER and BLER of user 1 are more close to the analytical error probability of QAM at $10^{-6}$ than that for user 2 at $10^{-4}$. In fact, this behavior is similar to the single-user case \cite{8594709}, where CA-polar codes with short blocklength perform better than that with moderate blocklength. This implies that the proposed scheme can allow the good performance of a code on the point-to-point AWGN channel to be \emph{carried over} to the considered multiuser channel under heterogeneous interference. It is also interesting to see that for user 2, the error probability upper bound for QAM slightly outperforms that of Gaussian signaling at $10^{-4}$ and below. This demonstrates that the proposed scheme with the simplest TIN decoding is very promising at short blocklength. For user 1, the analytical error probability of QAM is about 1 dB away from that of the Gaussian code at $10^{-6}$. This is because user 1 does not perform SIC in the proposed scheme while the benchmark schemes assume perfect SIC. Hence, the error performance of the corresponding coded systems also shows similar behavior. In summary, the proposed scheme using off-the-shelf codes can achieve satisfactory performance when compared to the error performance of shell codes with perfect SIC assumption.

\section{Conclusion}
In this paper, we have proposed a new transmission scheme based on discrete signaling and TIN for the downlink BC under heterogeneous blocklength and error probability constraints. To effectively handle heterogeneous interference across received symbol sequences, we have divided the symbol block of each user into sub-blocks and designed the modulation and power for each sub-block. We also have derived the second-order achievable rate under practical modulations and TIN to characterize the behavior of practical coded modulation systems for the considered scenario. Simulation results have shown that under short blocklength constraints, the proposed scheme with QAM and TIN can operate very close to the benchmark schemes that assume perfect SIC with Gaussian signaling. This implies that practical coded modulations together with the simplest single-user decoding are very promising for supporting downlink multiplexing of heterogeneous services with desired latency and reliability requirements while achieving near-optimal rates.

\bibliographystyle{IEEEtran}


\section{Introduction}
\label{sec:intro}
Cerebral Microbleeds (CMBs) are small foci of chronic blood products in normal brain tissue leaked from cerebral small vessels \cite{Greenberg2009}. They are recognized as neurological findings in patients with cerebrovascular disease \cite{Charidimou2012}, dementia \cite{Qiu2010}, normal aging \cite{Zwartbol}, and more recently, COVID-19 \cite{Lersy2021,Lin2020}. CMB size can range from 2 mm to 5-10 mm in diameter \cite{Greenberg2009}. These haemosiderin deposits are superparamagnetic, i.e., they have high magnetic susceptibility. Therefore, they produce inhomogeneity in the magnetic field of the surrounding area, making the decay of the local magnetic resonance imaging (MRI) signal faster. Hence, CMBs are typically seen as hypointense foci in MRI sequences sensitive to susceptibility effects such as gradient-recalled echo (GRE) T2$^*$-weighted imaging (T2$^*$WI) or susceptibility-weighted imaging (SWI). Compared to GRE T2$^*$WI, SWI increases the CMB detection rate from 20\% to 40\% \cite{Haller2018}.

Deep learning methods applied to CMB segmentation \cite{Liu2019,Chen2019,Dou2016,Al-masni2020} mostly consist of two-stage pipelines to search for potential positive objects and to differentiate true positives (TP) from false positives (FP). The state-of-the-art methods in \cite{Liu2019} uses a two-stage approach based on 3D-FRST \cite{Loy} and 3D-ResNet \cite{He_2016_CVPR} trained on high-resolution images and phases to achieve 95\% sensitivity, 71\% precision, and an average FP of 1.6 per scan. However, the accuracies drop to 73\% sensitivity, 67\% precision, and an average FP of 1.9 per scan, when applied to low-resolution scans \cite{Al-masni2020}. Due to learning from only 1-2 different datasets, these methods usually fail to generalize to data with other characteristics obtained in uncontrolled clinical settings.

Data augmentation is a common technique for addressing some of the domain shift issues in medical imaging \cite{ghazi2022fast}, but it is often not enough to cope with all differences in demographics, comorbidities, and acquisition parameters to achieve high generalization accuracy. Therefore, sometimes there is a need for including data with high variability in the training set, especially when the training data is small. However, this requires the acquisition and annotation of some MRI scans from different sites and parameters, which is a time-consuming and labor-intensive task and can cause data privacy challenges.

In this work, a robust deep-learning model is trained and applied to assess COVID-19 CMBs in a retrospective cohort study data, obtained from the capital region of Denmark \cite{Jimenez-Solem2021} and weakly labeled as case-control through matching. MultiResUNet architecture \cite{Ibtehaz2020} is trained on different heterogeneous datasets using the three orthogonal planes of each scan for CMB segmentation and detection. Two public datasets assigned for normal aging, stroke, and Alzheimer’s disease analysis \cite{Momeni2021,Dou2016} as well as an in-house dataset for COVID-19 assessment are used to train and evaluate the models. The obtained results show that the proposed method is robust to low-resolution images and achieves 78\% sensitivity and 80\% precision on the entire test set with an average FP of 1.6 per scan. To show the stability of the method on heterogeneous data, the pipeline is successfully applied to distinguish between the two weakly labeled groups.

\section{Method}
\label{sec:method}
Our study design comprises strategic data selection and preprocessing, data augmentation and training deep learning models, postprocessing for classifier fusion, and standard testing for the detection and group differentiation capability. The utilized deep learning framework includes MultiResUNet models \cite{Ibtehaz2020} trained individually on axial, sagittal, and coronal views, which are later fused for the 3-views agreement.
\iffalse
, as shown in \autoref{fig:schema}.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.35]{figures/CMBpipeline.pdf}
\caption{The utilized CMB segmentation-detection framework.}
\label{fig:schema}
\end{figure}
\fi

\subsection{Data processing}
Two public datasets \cite{Momeni2021,Dou2016} and in-house data with SWI images are used in this study; the first data (DS1) is obtained from \cite{Momeni2021} and contains 57 scans from 30 patients with real CMBs (DS1r) and 3,700 scans from 118 patients with synthetic CMBs (DS1s); the second data (DS2) is obtained from \cite{Dou2016} and contains 20 scans from 20 subjects with real CMBs; the third dataset (DS3) is obtained from different hospitals of the capital region of Denmark and contains 40 scans from 40 patients with CMBs and 22 scans from 22 patients with no CMBs (DS3n). Moreover, 40 scans with no CMBs, matched with those 40 scans with CMBs, are used for testing the group distinguishability of the model.

The DS1 scans were acquired in a spatial resolution of 0.93 $\times$ 0.93 $\times$ 1.75 mm$^3$ using a 3T scanner with 20 ms echo time. The DS2 scans were obtained in a resolution of 0.45 $\times$ 0.45 $\times$ 1 mm$^3$ using a 3T scanner with 24 ms echo time. Finally, the DS3 scans were captured from different sites and scanners (1.5T and 3T) in various resolutions (from 0.2 $\times$ 0.2 $\times$ 1 mm$^3$ to 1 $\times$ 1 $\times$ 6 mm$^3$), to increase our model’s robustness and generalization accuracy.

Since the DS1 and DS2 only provide the CMB center positions on the SWI images, to train a multiview deep network, we need to create volumetric masks for the CMBs. We select patches with an isotropic voxel size of 10 mm$^3$ as the maximum CMB size according to \cite{Greenberg2009} around the CMB centers and estimate the fraction of microbleeds for each pixel using
\begin{equation*}
\alpha_{\text{CMB}} = \frac{I_{pixel} - I_{mean}}{ I_{center} - I_{mean}},
\label{meth_data_pve}
\end{equation*}
where $I_{pixel}$ is the current pixel’s intensity, $I_{center}$ is the center pixel’s intensity, and $I_{mean}$ is the mean intensity of the surrounding pixels in a 2 mm neighborhood. Pixels with $\alpha>0.65$ and $\alpha>0.52$ were labeled as CMBs in DS1 and DS2, respectively. The different $\alpha$ values were obtained due to the difference in echo time or tissue contrast.

The DS3 scans were annotated by clinical experts and weakly labeled by probabilities estimated using the electronic healthcare records \cite{Jimenez-Solem2021} based on logistic regression and odds ratio according to the UK Biobank study \cite{Lu2021a}. For testing group differentiation capability, we selected 40 scans with $p_{\text{CMB}} > 0.3$, annotated them, and matched them on 40 unannotated scans with $p_{\text{CMB}} < 0.01$ based on the magnetic field strength, echo time, slice thickness, and scanner model.

\subsection{CMB segmentation and detection}
A 3D framework is built based on 2D convolutional neural networks (CNNs) to segment and count the number of CMBs. The pipeline consists of MultiResUNet models \cite{Ibtehaz2020}, trained individually on three orthogonal views of the MRI scans and fused later for the mask volume reconstruction. The volumes are first reshaped to 256 $\times$ 256 $\times$ 256 with an isotropic voxel size of 1 mm$^3$. To benefit from the 3D information, thickened 2D slices are then formed by three consecutive images of each MRI scan as inputs to the 3-channel CNNs.

Several MRI-specific transforms are randomly applied to the training images for data augmentation \cite{ghazi2022fast}, including elastic deformation, bias field, rotation, flipping, blurring, motion ghosting, Gibbs ringing, and additive-multiplicative noise. Moreover, intensity normalization and contrast adjustment are applied to the network inputs. Finally, the output probability maps of the central slices from different views are fused by multiplying the three maps to obtain the label masks based on a full agreement between the three predictions. Any quantitative measures like the counts, position, and size of the detected CMBs can then be computed using the output map.

\section{Experiments and results}
\label{sec:experiment}

\subsection{Experimental setup}
Scans from different subjects are randomly partitioned into 70\%, 10\%, and 20\% for training, validation, and testing. To balance different datasets for training, only 10\% of DS3n slices and 5\% of DS1s slices are used, optimized using a grid search method on the validation set.

The networks, pretrained on medical data for skin lesion segmentation \cite{Ibtehaz2020}, are finetuned for CMB segmentation using the Adam Optimizer with cross-entropy loss function and a weight decay of $10^{-6}$. The base learning rate is set to $5\times10^{-4}$ and decreased by 10\% every 10 epochs. The hyperparameter values are obtained using a grid search algorithm on the validation set.

\subsection{Results and discussion}
The test prediction results of our model on different datasets are summarized in \autoref{tab:results_obj_metrics1}. As can be seen, our framework achieves a Dice similarity score (DSC) of 0.79, sensitivity of 0.78, precision of 0.80, and an average FP of 1.64 per scan. Note that CMB segmentation and detection in the wild (DS3) is very challenging, as the data is acquired from uncontrolled clinical settings with different imaging protocols. The high variations in the image parameters, anatomies, and patient conditions can affect the model's accuracy and robustness. The proposed method, trained on a few annotated DS3 scans, has achieved comparable results in the DS3 test set.

\begin{table}[t]
\mysizea
\centering
\caption{CMB segmentation and detection results on different test sets using the proposed framework.}
\vspace{0.1cm}
\begin{tabular}{lcccccc}
\toprule
\textbf{Dataset} & \textbf{TP/scan} & \textbf{FP/scan} & \textbf{FN/scan} & \textbf{DSC} & \textbf{Sensitivity} & \textbf{Precision} \\
\midrule
DS1r & 3.58 & 2.00 & 1.08 & 0.70 & 0.77 & 0.64 \\
DS1s & 8.11 & 1.75 & 1.72 & 0.82 & 0.83 & 0.82 \\
DS2 & 1.00 & 0.00 & 1.00 & 0.67 & 0.50 & 1.00 \\
DS3 & 8.57 & 1.43 & 5.00 & 0.73 & 0.63 & 0.86 \\
DS3n & 0.00 & 0.00 & 0.00 & 1.00 & NA & NA \\
\midrule
All & 6.75 & 1.64 & 1.92 & 0.79 & 0.78 & 0.80 \\
\bottomrule
\end{tabular}
\label{tab:results_obj_metrics1}
\end{table}

The test results of the DS3 show lower sensitivity and higher precision. The higher FN rate can be due to the difference in CMB distribution per scan compared to the other datasets, where many scans could have a single CMB while many others have a large number of CMBs. The higher precision can also be due to the higher resolution of DS3 scans compared to the alternatives. In addition, as expected, no CMBs were detected on DS3n, indicating that our method can be applied to distinguish between healthy and diseased scans. Finally, the lower accuracy obtained on DS2 can be because it has the smallest dataset size in terms of the number of scans and CMBs per scan.

Due to the different nature of the used datasets in the literature, we classify them as low-resolution (LR) and high-resolution (HR) SWI-based studies for a fair comparison. The HR studies on CMB segmentation involve \cite{Al-masni2020,Liu2019,Dou2016} with scans of spacings 0.5 $\times$ 0.5 $\times$ 2 mm$^3$, 0.45 $\times$ 0.5 $\times$ 1.2 mm$^3$ to 0.54 $\times$ 1.07 $\times$ 2.65 mm$^3$, and 0.45 $\times$ 0.45 $\times$ 2 mm$^3$, respectively, while the LR one is obtained from \cite{Al-masni2020} with scans of spacing 0.8 $\times$ 0.8 $\times$ 2 mm$^3$. In contrast, our LR test set contains scans with spacings of 0.89 $\times$ 0.89 $\times$ 2 mm$^3$ (DS3) and 0.93 $\times$ 0.93 $\times$ 1.75 mm$^3$ (DS1), while the HR test set includes scans with spacings of 0.3 $\times$ 0.3 $\times$ 2 mm$^3$ to 0.34 $\times$ 0.34 $\times$ 4 mm$^3$ (DS3) and 0.45 $\times$ 0.45 $\times$ 1 mm$^3$ (DS2). It should also be noted that \cite{Al-masni2020,Liu2019} benefit from the phase images for segmentation. \autoref{tab:results_obj_metrics1} shows the prediction results of different models on various scan resolutions of the test sets. As seen, our model achieves better results on the LR subset while obtaining poor sensitivity on the HR test set. The reason for such behavior compared to the state-of-the-art could be because the scan resolutions in different studies do not match exactly, our model is trained on much more LR scans ($83\%$ LR scans vs. $17\%$ HR scans), and we do not use phase images for CMB segmentation and detection. Moreover, the HR dataset of DS2 used in this study only includes a small publicly available subset of the one used in \cite{Dou2016}.

Finally, to see how the weakly labeled groups of our COVID-19 study are statistically significantly different in terms of the number of detected CMBs, we use two unannotated scan subsets labeled as non-CMB ($p_{\text{CMB}} < 0.01$) and CMB ($p_{\text{CMB}} > 0.3$). On average per scan, we found 0.62 CMB in the non-CMB scans and 2.60 CMB in the CMB scans, which were statistically significantly different with a $p = 0.001$ using the Wilcoxon signed-rank test. Nest, we set clinical criteria for illness based on 5 CMBs per scan and attempt to distinguish between the groups with more or less than 5 CMBs. To minimize the FP effects, we filter the predicted CMBs by the minimum clinical size of 4.2 mm$^3$ with a 2 mm diameter. \autoref{fig:results_varying_size_cph} shows the difference between the two groups for the filtered CMB size, where the CMB frequency of the two filtered groups is statistically significantly different with a $p = 0.013$ using Fisher’s exact test.

\begin{table}[t]
\mysizea
\centering
\caption{Test CMB segmentation and detection results of different state-of-the-art models on various scan resolutions.}
\vspace{0.1cm}
\begin{tabular}{lccccc}
\toprule
\textbf{Model} & \textbf{Type} & \textbf{Phase} & \textbf{FP/scan} & \textbf{Sensitivity} & \textbf{Precision} \\
\midrule
YOLO + 3D-CNN \cite{Al-masni2020} & LR & Yes & 1.89 & 0.78 & 0.67  \\
& & & & & \\
YOLO + 3D-CNN \cite{Al-masni2020} & HR & Yes & 1.42 & 0.88 & 0.62  \\
& & & & & \\
3D-FRST + 3D-ResNet \cite{Liu2019} & HR & Yes & 1.6 & 0.95 & 0.71  \\
& & & & & \\
3D-FCN + 3D-CNN \cite{Dou2016} & HR & No & 2.74 & 0.91 & 0.44  \\

\midrule
The proposed & LR & No & 1.92 & 0.80 & 0.80  \\
The proposed & HR & No & 0.30 & 0.49 & 0.87 \\
\bottomrule
\end{tabular}
\label{tab:results_obj_metrics2}
\end{table}

\begin{figure}[t]
	\centering

	\includegraphics[width=1.0\linewidth,height=0.42\linewidth]{figures/_varying_size_cph_test_CPH_V2.png}
	\caption{The CMB frequency of the two groups and their statistical significance for the filtered CMB size. As seen, the two groups with more than 5 CMB are significantly different for the CMB size smaller than 5 mm$^3$.}
	\label{fig:results_varying_size_cph}
\end{figure}

\section{Conclusion}
\label{sec:conclusion}
In this work, we developed a deep learning-based framework based on MultiResUNet architecture using different heterogeneous datasets and MRI-specific data augmentation for CMB segmentation and detection and assessed COVID-19 CMBs in a retrospective cohort study. The proposed pipeline was tested on uncontrolled clinical data and outperformed the state-of-the-art methods, especially when applied to low-resolution images. Moreover, the proposed pipeline was able to distinguish between two weakly labeled groups of the heterogeneous COVID-19 data, and the results were statistically significantly different in terms of the number of detected CMBs.

\section{Acknowledgments}
\label{sec:acknowledgments}

This project has received funding from VELUX FONDEN and Innovation Fund Denmark under grant numbers 9084-00018B and 1063-00014B, and Pioneer Centre for AI, Danish National Research Foundation, grant number P1.
This study was conducted using human subject data. Ethical approval was not required for the open-access data as confirmed by the license attached to the data. The Danish cohort study was approved by the relevant legal and ethics boards, including the Danish Patient Safety Authority (Styrelsen for Patientsikkerhed, approval $\#$31-1521-257) and the Danish Data Protection Agency (Datatilsynet, approval $\#$P-2020-320).

\bibliographystyle{IEEEbib-abbrev}


\section{Introduction}
Federated Learning (FL), first proposed by \cite{mcmahan2017communication}, is an emerging collaborative learning technique enabling multiple parties to train a joint machine learning model with input privacy being preserved. By iteratively aggregating local model updates done by participating clients using their local, private data, a joint global model is obtained. The promise of federated learning is that this global model will have superior performance compared to the models that could be obtained by each participant in isolation. Compared with traditional distributed machine learning, FL works with larger local updates and seeks to minimize communication cost while keeping the data of participants local and private. With increasing concerns about data security and privacy protection, federated learning has attracted much research interest (\cite{kairouz2021advances, li2020federated}) and has been proven to work effectively in various application domains (\cite{li2020review, xu2021federated}).

When the datasets at the client sites are not independent and identically distributed (IID), the standard algorithm for federated learning, \texttt{FedAvg}{}, can struggle to achieve  good model performance, with an increase of communication rounds (\cite{zhu2021federated, li2019convergence}) needed for convergence. Moreover, the global model trained with heterogeneous data can be biased towards some of the participants, while performing poorly for others (\cite{mohri2019agnostic}). This is known as unfairness problem in federated learning. There are ways to improve fairness in federated learning, at the cost of model convergence (\cite{mohri2019agnostic, li2019fair, hu2022federated, li2021ditto}). This study aims to contribute to the understanding of how to enable fair federated learning without negatively impacting the convergence rate.

Acceleration techniques for federated learning aim at reducing the communication cost and improving convergence. For instance, momentum-based and adaptive optimization methods such as \texttt{AdaGrad}{}, \texttt{Adam}{}, \texttt{Momentum} \texttt{SGD}{}) have been applied to accelerate the training process \cite{karimireddy2020mime, wang2019slowmo, reddi2020adaptive}). However, default hyperparameters of adaptive optimizers tuned for centralized training do not tend to perform well in federated settings (\cite{reddi2020adaptive}). Furthermore, optimal hyperparameters are not generalizable for federated learning, and hyperparameter optimization with e.g. grid search are needed for each specific federated task, which is infeasible due to the expensive (and sometimes unbounded) nature for federated learning. Further research is need to understand how to adapt optimizers for federated learning with minimal hyperparameter selection.

In this study, to accelerate the training of fair federated learning, we
formulate fairness-aware federated learning as a \emph{dynamical multi-objective optimization problem (DMOO)} problem.
By analyzing the convergence and bias of federated \texttt{Adam}{}, we propose Adaptive Federated Adam (\texttt{AdaFedAdam}{}) to solve the formulated DMOO problem efficiently.
With experiments on standard benchmark datasets, we illustrate that \texttt{AdaFedAdam}{} alleviates model unfairness and accelerates federated training. In additional, \texttt{AdaFedAdam}{} is proved to be robust against different levels of data and resource heterogeneity, which suggests that the its performance on fair federated learning can be expected in real-life use cases.

The remainder of the paper is structured as follows. Section \ref{sec:related_work} summarizes related work including different acceleration techniques for federated training and the fairness problem in federated learning. Then fair federated learning problem is formulated in Section \ref{sec:background} and Federated \texttt{Adam}{} is analyzed in Section \ref{sec:ana_fedadam}. Section \ref{sec:adafedadam} introduces the design of \texttt{AdaFedAdam}{}. Setups and results of empirical experiments are presented in Section \ref{sec:experiments}. Finally, section \ref{sec:conclusion} concludes the paper and suggests future research directions.

\section{RELATED WORK}\label{sec:related_work}
In this section, we review recent techniques to accelerate federated training as well as studies of model fairness in FL.

\subsection{Acceleration techniques for federated learning}
Adaptive methods accelerate centralized training of neural networks over vanilla \texttt{SGD}{} (\cite{kingma2014adam, zeiler2012adadelta}). In the context of federated learning, \cite{hsu2019measuring} and \cite{wang2019slowmo} introduced first-order momentum to update the global model by treating local updates as pseudo-gradients, showing the effectiveness of adaptive methods for federated learning. Further, \cite{reddi2020adaptive} demonstrated a two-level optimization framework \texttt{FedOpt}{} for federated optimization. On the local level, clients optimize the local objective functions while local updates are aggregated as "pseudo-gradients" to update the global model on the server level. From the view of the \texttt{FedOpt}{} framework, \texttt{FedAvg}{} uses \texttt{SGD}{} as its local solver and \texttt{Gradient Descent} with a learning rate of 1 as the server optimizer. By applying adaptive optimizers (e.g. \texttt{Adam}{}) as the server optimizer, we obtain adaptive federated optimizers (e.g. \texttt{FedAdam}{}). It has been empirically validated that adaptive federated optimizers are able to accelerate training, however they need careful fine-tuning (\cite{reddi2020adaptive}).

Fine-tuning for server optimizers is challenging for the following reasons:
\begin{itemize}
    \item Due to the inherent differences of federated and centralized training, default hyperparameters of optimizers which work well on centralized training does not necessarily have satisfactory performances in federated training.
    \item For adaptive optimizers, grid search needs to be done to get multiple hyperparameters optimized (\cite{reddi2020adaptive}), which is prohibitively expensive considering the orchestration cost for the entire federation.
    \item The optimal hyperparameters for server-side optimizers are not generalizable between different federated tasks, and fine-tuning must be done for each individual task.
\end{itemize}
It would greatly ease the use of server-side optimizers if the selection of hyperparameters were automatic. The proposed methods \texttt{AdaFedAdam}{} minimizes the efforts of fine-tuning by adapting default hyperparameters of \texttt{Adam}{} in centralized settings to federated training.

\subsection{Model fairness}
The concept of model unfairness describes the differences of model performance across participants in a federated training process. It was firstly highlighted by \cite{mohri2019agnostic}. Most federated learning algorithms optimize the global model solely focusing on the averaged loss. However, model performances between clients are not uniform when data between participants are heterogeneous, and the global model can be biased towards some participants. To reduce the unfairness, \cite{mohri2019agnostic} proposed the algorithm \texttt{Agnostic Federated Learning}, a minimax optimization approach that only optimizes the single device with the worst performance. Inspired by fair resource allocation, \cite{li2019fair} formulated fair federated learning as a fairness-controlled optimization problem with \(\alpha\)-fairness function (\cite{mo2000fair}). By increasing \(\alpha\) (\(q\) in the article), the desired fairness between participants can be improved at a cost of convergence. The algorithm \texttt{q-FedAvg}{} was proposed to solve the optimization problem, which dynamically adjust step sizes of local \texttt{SGD}{} by iteratively estimating Lipschitz constants. More recently, \cite{hu2022federated} interpreted federated learning as a multi-objective optimization problem, and adapted Multi-Gradient Descent Algorithm (MGDA) to federated settings as \texttt{FedMGDA+} to reduce the unfairness. Alternatively, \cite{li2021ditto} proposed \texttt{Ditto} to improve the performance fairness by personalizing global models on client sites.

Unlike previous work that are based on \texttt{FedAvg}{} with improved fairness at a cost of model convergence, the here proposed approach \change{formulates fair federated learning as a dynamic multi-objective function and proposes \texttt{AdaFedAdam}{} to solve the formulated problem. Compared with other \texttt{FedAvg}{}-based algorithms for fairness control, \texttt{AdaFedAdam}{} offer equivalent fairness guarantee with  improved convergence properties. }

\section{PRELIMINARIES \& PROBLEM FORMULATION}\label{sec:background}
\subsection{Standard federated learning}
Considering the distributed optimization problem to minimize the global loss function \(F(\mathbf{x})\) across \(K\) clients as follows:
\begin{equation}\label{eq:fl}
    \min_{\mathbf{x}}[F(\mathbf{x}) := \sum_{k=1}^{K} p_{k} F_{k}(\mathbf{x})]
\end{equation}
where \(\mathbf{x}\) denotes the parameter set of function \(F\), \(F_k(\mathbf{x})\) is the local objective function of client \(k\) w.r.t local dataset \(D_k\), and \(p_k := \frac{|D_k|}{\sum |D|}\) denotes the relative sample size of \(D_k\) with number of samples \(|D_k|\) in \(D_k\). The data distribution on client \(k\) is denoted by \(\mathcal{D}_k\).

\remove{
One of the baseline algorithm to solve the federated optimization, \texttt{FedAvg}{}, is noted as follows:
\begin{equation}
    \mathbf{x}^{t+1} = \sum_{k=1}^{K^t} p_{k} \mathbf{x}^{t}_{k} \text{, where } \mathbf{x}^{t}_{k} := \textbf{SGD}(\mathbf{x}^t, \nabla_{\zeta \sim \mathcal{D}_k}, \eta, \mathcal{S}_k)
\end{equation}
In communication round \(t\), a subset of clients \(K^t \subseteq K\) participates the training. For all \(k \in [K^t]\), client \(k\) runs (mini-batch) \texttt{SGD}{} with learning rate \(\eta\) on the global model \(\mathbf{x}^t\) for \(\mathcal{S}_k\) steps. Gradient estimation of each step \(\nabla_{\zeta \sim \mathcal{D}_k}\) is based on batches \(\zeta\) sampled from the local distribution \(\mathcal{D}_k\). Parameters of all local models are averaged weighted by the relative size of their local datasets \(p_k\) to get the global model \(\mathbf{x}^{t+1}\).

Federated learning algorithms enable an two-level optimization structure with a client- and server-level\cite{reddi2020adaptive}. At the client level, local solvers are not limited to SGD to minimize the local loss functions. At the server level, aggregated local updates can be regarded as "pseudo-gradients" of the global model, and can be the input for the server solver to update the global model. This type of two-level optimization includes \texttt{FedAdam}{} and \texttt{FedAdaGrad}, which is obtained by applying \texttt{Adam}{} (\cite{kingma2014adam}) or \texttt{AdaGrad}{} (\cite{lydia2019adagrad}) as the server optimizer.
}
\subsection{Fair federated learning}
\change{
When \(\mathcal{D}_k\) are not identical across clients (the non-IID case), the standard formulation of federated learning can suffer from a significant fairness problem (\cite{mohri2019agnostic}) in addition to a potential loss of convergence. To improve  fairness, federated learning can be formulated with an \(\alpha\)-fairness function as \(\alpha\)-Fair Federated Learning (also known as \(q\)-Fair Federated Learning in \cite{li2019fair}) as follows: }

\begin{equation}\label{eq:ffl}
    \min_{\mathbf{x}}[F(\mathbf{x}) := \sum_{k=1}^{K} \frac{p_{k}}{\alpha+1} F^{\alpha+1}_{k}(\mathbf{x})]
\end{equation}

\change{
where notations is as in \eqref{eq:fl}. With the additional hyperparameter \(\alpha\), \(\alpha\)-Fair Federated Learning is able to control the desired fairness level in federated learning. Setting larger values for \(\alpha\) indicates greater demand for fair/uniform performances across clients at a cost of convergence (\cite{mo2000fair}), and setting \(\alpha=0\) reduces \(\alpha\)-Fair Federated Learning to the standard formulation of Federated Learning in \eqref{eq:fl}.
}

\change{
It is challenging to solve the problem with distributed first-order optimization. With only access to gradients of local objective functions \(\nabla^t F_k(\mathbf{x})\), the gradient of \(F(\mathbf{x})\) at \(\mathbf{x}^t\) and the update rule of distributed \texttt{SGD}{} are given as follows:}
\begin{align}\label{eq:grad_ffl}
    \nabla F(\mathbf{x}^t) &= \sum_{k=1}^{K} p_{k} F^{\alpha}_{k}(\mathbf{x}^t) \nabla F_k(\mathbf{x}^t) \\
    \mathbf{x}^{t+1} &:= \mathbf{x}^t - \eta \nabla F(\mathbf{x}^t)
\end{align}

\change{
It is noticeable that the gradient \(\nabla F(\mathbf{x}^t)\) has decreasing scales due to the factor \(F^\alpha(\mathbf{x}^t)\). As the number of iterations \(t\) increases, a decreasing \(F^\alpha(\mathbf{x}^t)\) scales gradients \(\nabla F(\mathbf{x}^t)\) down drastically. With a fixed learning rate \(\eta\), the update of \texttt{SGD}{} \(-\eta \nabla F(\mathbf{x}^t)\) scales down correspondingly and thus, the convergence deteriorates. To improve the convergence, \cite{li2019fair} proposes \texttt{q-FedAvg}{} to adjust learning rates adaptively. However, the convergence of \texttt{q-FedAvg}{} is not satisfying since 1). the intrinsic challenge of optimizing the learning rate adaptively in \(\alpha\)-Fair Federated Learning still exists and 2). \texttt{FedAvg}{}-based \texttt{q-FedAvg}{} does not utilize acceleration techniques.
}

\subsection{Problem formulation}
\remove{
In real life use cases, participants of federated learning can be expected to join or leave the training at any time according to their availability in either cross-silo or cross-device scenarios. It is important to not only obtain a fair model after the training completes, but also keep the global model fair during the training process. The latter guarantees local performances whenever participants exit the training. Fairness during the training also encourages clients to contribute to the training continuously.
}
\change{
In the field of multi-task learning, neural networks are designed to achieve multiple tasks at the same time by summing multiple component objective functions up as a joint loss function.
}
In a similar spirit to fair federated learning, training multitask deep neural networks also requires to keep similar progress for all component objectives. Inspired by \cite{chen2018gradnorm}, we formulate fair federated learning as a dynamic multi-objective optimization problem (DMOP) in the following form:

\begin{equation}\label{eq:iffl}
    \min_{\mathbf{x}}[F(\mathbf{x}, t) :=
    \frac{\sum_{k=1}^{K} p_{k} I^\alpha_k(t) F_{k}(\mathbf{x})}
    {\sum_{k=1}^{K} p_{k} I^\alpha_k(t)} ]
\end{equation}

where \(p_k\) is the size of dataset on client \(k\), and \(F_k(\mathbf{x})\) is the local objective function of client \(k\). Additionally, \textit{inverse training rate} is defined as \(I_k(t) := F_k(\mathbf{x}^t)/F_k(\mathbf{x}^0)\) for participant \(k\) at round \(t\), to quantify its training progress. \(\alpha \geq 0\) is a hyperparameter to adjust the model fairness similar to \(\alpha\) in \(\alpha\)-fairness function.
The problem reduces to the federated optimization without fairness control if setting \(\alpha=0\), and it restores the minimax approach for multi-objective optimization (\cite{mohri2019agnostic}) if setting \(\alpha\) a sufficiently large value.

\change{
Compared with \(\alpha\)-Fair Federated Learning, the proposed formulation has equivalent fairness guarantee without the problem of decreasing scales of gradients. Considering that the global model \(\mathbf{x}^0\) is initialized with random weights, we assume that \(F_{i}(\mathbf{x}^0) = F_{j}(\mathbf{x}^0)\) for \(\forall i, j \in [K]\). Then we have that the gradient of \(F(\mathbf{x}, t)\) at \(\mathbf{x}^t\) is given by:
}
\begin{align}\label{eq:grad_iffl}
    \nabla F(\mathbf{x}^t, t) = \frac{\sum_{k=1}^{K} p_{k} F^{\alpha}_{k}(\mathbf{x}^t) \nabla F_k(\mathbf{x}^t)}{\sum_{k=1}^{K} p_{k} F^{\alpha}_{k}(\mathbf{x}^t)} \propto \sum_{k=1}^{K} p_{k} F^{\alpha}_{k}(\mathbf{x}^t) \nabla F_k(\mathbf{x}^t)
\end{align}

\change{
The gradient \(F(\mathbf{x}^t, t)\) of the DMOP formulation is proportional to the gradient of the \(\alpha\)-Fair Federated Learning (\eqref{eq:ffl}). Thus, with first-order optimization methods, the solution of the DMOP formulation is also the solution of the \(\alpha\)-fairness function, which has been proved to enjoy \((p, \alpha)\)\textit{-Proportional Fairness} (\cite{mo2000fair}). Moreover, the DMOP formulation of Fair Federated Learning does not have the problem of decreasing gradient scales in the \(\alpha\)-fairness function, so that distributed first-order optimization methods can be applied to solve the problem more efficiently.
}

\section{ANALYSIS OF \textit{FEDADAM}}\label{sec:ana_fedadam}
In this section, we analyze the performance of \texttt{Adam}{} as the server optimizer in federated learning. We first study the effect of using accumulated updates as pseudo-gradients for \texttt{Adam}{} in centralized training. The bias introduced by averaging accumulated local updates without normalization in \texttt{FedAdam}{} is then discussed.

\subsection{From \texttt{Adam}{} to \texttt{FedAdam}{}}
As the de facto optimizer for centralized deep learning, \texttt{Adam}{} provides stable performance with little need of fine-tuning. The pseudo code of \texttt{Adam}{} is shown in \ref{sec:pseudocode} 3. \texttt{Adam}{} provides adaptive stepsize selection based on the initial stepsize \(\eta\) for each individual coordinate of model weights. The adaptivity of stepsizes can be understood as continuously establishing \emph{trust regions} based on estimations of the first- and second-order momentum (\cite{kingma2014adam}), which are updated by exponential moving averages of gradient estimations and their squares with hyperparameters \(\beta_1\) and \(\beta_2\) in each step.

The choice of hyperparameters in \texttt{Adam}{} can be explained by the certainty of directions for model updates. In centralized \texttt{Adam}{}, directions for updates are from gradient estimations \(\nabla_{\zeta \sim \mathcal{D}} F(\mathbf{x})\) obtained from a small batch of data \(\zeta\) with large variances, indicating low certainty of update directions. Thus, large \(\beta_1\) and \(\beta_2\) (\(0.9\) and \(0.999\) by default) are set to assign less weight for each gradient estimation when updating first- and second-order momentum. Low certainty of update directions also only allow small \emph{trust regions} to be constructed from small initial stepsize \(\eta\) (\(0.001\) by default).

In federated learning, \texttt{FedAdam}{} is obtained if we apply \texttt{Adam}{} as the server optimizer and the size-weighted average of clients' local updates at round \(t\), \(\Delta_t\), acts as the pseudo-gradient. Although empirical results have shown that \texttt{FedAdam}{} outperforms the standard \texttt{FedAvg}{} with careful fine-tuning in terms of average loss (\cite{reddi2020adaptive}), several problems exist in \texttt{FedAdam}{}. In the following subsections, we analyze the problem of convergence loss of \texttt{FedAdam}{} and bias of pseudo-gradients used for \texttt{FedAdam}{}.

\subsection{Adam with accumulated updates}
When data between clients are statistically homogeneous, the average of local updates is an unbiased estimator of accumulated updates of multiple centralized \texttt{SGD}{} steps. Therefore, in IID cases, \texttt{FedAdam}{} shrinks as \texttt{Adam}{} with gradient estimation given by accumulated updates of \(N\) \texttt{SGD}{} steps (\texttt{\(N\)-AccAdam}{}). Pseudo-codes of \texttt{\(N\)-AccAdam}{} is given in \ref{sec:pseudocode}. We prove that even in centralized settings, \texttt{\(N\)-AccAdam}{} has less convergence guarantee than standard \texttt{Adam}{} with same hyperparameters.

\begin{theorem}[Convergence of \texttt{\(N\)-AccAdam}{}]\label{thrm:accadam}
\textit{Assume the \(L\)-smooth convex loss function \(f(\mathbf{x})\) has bounded gradients \(\|\nabla\|_{\infty} \leq G\) for all \(\mathbf{x} \in \mathbb{R}^d\). Hyperparameters \(\epsilon\), \(\beta_2\) and \(\eta\) in \texttt{\(N\)-AccAdam}{} are chosen with the following conditions: \(\eta \leq \epsilon/2L\) and \(1-\beta_2 \leq \epsilon^2/16G^2\). The accumulated SGD updates at step \(t\) \(\Delta\mathbf{x}^t := -\sum_{n=1}^{N} \Delta_{n}\mathbf{x}^t /\eta_s\) is applied to Adam, where \(\Delta_n \mathbf{x}^t\) denotes the local update after \(n\) SGD steps with a learning rate of \(\eta_s\) on model \(\mathbf{x}^t\). \texttt{SGD}{} exhibits approximately linear convergence with constants \((A, c)\). In the worst case, the algorithm has no convergence guarantee. In the best cases where \(R_t = N\) for all \(t\in [T]\), the converge rate is given by: }

\begin{equation}\label{eq:accadam}
 \frac{1}{T} \sum_{t=1}^T \|\nabla f(\mathbf{x}^t)\|^2 \leq \frac{f(\mathbf{x}^1) - f(\mathbf{x}^*)(\sqrt{\beta_2}G+\epsilon)}{\underbrace{(\frac{Nc}{1-(1-c)^N} - \frac{1}{2})}_{S}\eta T}
\end{equation}
where \(R_t := \min | \frac{\Delta_{t,i}}{\nabla_{t,i}} |\) for \(i \in [d]\)
\end{theorem}

The proof for Theorem \ref{thrm:accadam} is deferred to \ref{subsec:proof1}. In the best case where \(R_t = N\) (which is almost not feasible), \texttt{\(N\)-AccAdam}{} gains \(S\) speedup compared with \texttt{Adam}{}. However, the computation cost of \texttt{\(N\)-AccAdam}{} is linear to \(N\) but the speedup \(S\) is sublinear to \(N\). Thus, with a fixed computation budget, the convergence rate of \texttt{\(N\)-AccAdam}{} is slower than \texttt{Adam}{} with the same hyperparameters. Compared with gradient estimation by a small batch of data, accumulated updates of multiple \texttt{SGD}{} steps have larger certainty about directions of updates for the global model. To improve the convergence of \texttt{\(N\)-AccAdam}{}, it is possible to construct larger \emph{trust regions} with larger stepsize \(\eta\) and smaller \(\beta\)s with accumulated updates.

\subsection{Bias of pseudo-gradients for \texttt{FedAdam}{}}
In federated settings, when data among clients are heterogeneous, averaging all local updates weighted by sizes of client datasets introduces bias toward a portion of clients. The biased pseudo-gradients lead to even lower convergence and increase the unfairness of \texttt{FedAdam}{}.

\cite{wang2020tackling} has proved that there exists objective inconsistency between the stationary point and the global objective function, and biases are caused by different local \texttt{SGD}{} steps taken by clients. They propose \texttt{FedNova}{} to reduce the inconsistency by normalizing local updates with the number of local steps. The convergence analysis of \texttt{FedNova}{} assumes that all local objective functions have the same \(L\)-smoothness, which is also identical to the smoothness constant of the global objective function. However, in federated learning with highly heterogeneous datasets, smoothness constants \(L_k\) of local objective functions are very different across clients and from the one \(L_g\) of the global objective function. Although the assumption and proof still holds if taking \(L_g := \max (L_k)\) for all \(k \in [K]\), we argue that the inconsistency still exists in \texttt{FedNova}{} if only normalizing local updates with number of steps regardless of differences of \(L_k\)-smoothness constant of local objectives.

In one communication round, with the same numbers of local \texttt{SGD}{} steps and a fixed learning rate \(\eta\), it is likely to happen that while objectives with small \(L\)-constant are still slowly converging, local objectives with large \(L\)-constants have converged in a few steps and extra steps are ineffective. In such cases, normalizing local updates with number of local \texttt{SGD}{} steps implicitly over-weights updates from objectives with smaller \(L\)-constants when computing pseudo-gradients. Normalization of local updates to de-bias the pseudo-gradients is yet to be improved to take both different numbers of local steps and \(L\)-smoothness constants of local objectives into consideration.

\section{\texttt{AdaFedAdam}{}}\label{sec:adafedadam}
To address the drawbacks mentioned above, we propose \texttt{AdaFedAdam}{} (Adaptive \texttt{FedAdam}{}) to make better use of accumulated local updates for fair federated learning (\eqref{eq:iffl}) with little efforts on fine-tuning.
\subsection{Algorithm}

The pseudo-code of the algorithm is presented as Algorithm \ref{alg:adafedadam} and Figure \ref{fig:regu} is an illustration of \texttt{AdaFedAdam}{}.

{\centering
\begin{minipage}{.7\linewidth}
\begin{algorithm}[H]
\small
\caption{Adaptive FedAdam}\label{alg:adafedadam}
\begin{algorithmic}
\Require initial model \(\mathbf{x}^0\), \(\eta\), \(\beta_1\), \(\beta_2\), \(\epsilon\)
\State \(m_{0} \gets 0\), \(v_{0} \gets 0\)
\State \(c_{0,m} \gets 1\), \(c_{0,v} \gets 1\)    \Comment Correction factor for \(m\) and \(v\)
\For{round \(t\) in \(\{0, 1, ... T-1\}\)}
    \State \(\mathbf{g}^t, C^t = \textbf{GetPseudoGradient}(\mathbf{x}^t)\)
    \State \(\beta_{t, 1} \gets \beta^{C^t}_1\), \(\beta_{t, 2} \gets \beta^{C^t}_2\), \(\eta_t \gets C^t\eta\)
    \Comment Adaptive momentum and stepsize

    \State \(c_{t+1,m} \gets c_{t,m} \beta_{t,1}\), \(c_{t+1,v} \gets c_{t,v} \beta_{t,2}\) \Comment Update correction factors
    \State \(m_{t+1} \gets (1-\beta_{t,1})\mathbf{g}^t + \beta_{t,1}m_{t}\)
    \State \(v_{t+1} \gets (1-\beta_{t,2})\mathbf{g}^t \odot \mathbf{g}^t + \beta_{t,2}v_{t}\)
    \State \(\hat{m}_{t+1} \gets m_{t+1}/(1-c_{t+1, m})\)
    \State \(\hat{v}_{t+1} \gets v_{t+1}/(1-c_{t+1, v})\)
    \State \(\mathbf{x}^{t+1} \gets \mathbf{x}^{t} - \eta \hat{m}_{t+1}/(\sqrt{\hat{v}_{t+1}}+\epsilon)\)
\EndFor
\end{algorithmic}
\end{algorithm}
\end{minipage}
\par
}

{\centering
\begin{minipage}{.7\linewidth}
\begin{algorithm}[H]
\small
\caption{Pseudo-gradient calculation}
\begin{algorithmic}
\Require \(\alpha\)
\Procedure{GetPseudoGradient}{$\mathbf{x}$}
\State Broadcast \(\mathbf{x}\) to all clients
\For{client \(k\) in \(\{0, 1, ... K-1\}\) \textbf{parallel}}
    \State Calculate \(F_k(\mathbf{x})\) and \(\nabla F_k(\mathbf{x})\)
    \State \(\mathbf{x}_k = \textbf{LocalSolver}(\mathbf{x}, \eta_k)\) \Comment Client training
    \State \(\mathbf{\Delta}_k \gets \mathbf{x}_k-\mathbf{x}\)
    \State \(\eta'_k \gets \frac{\|\mathbf{\Delta}_k\|_{2}}{\|\nabla F_k(\mathbf{x}^t)\|_{2}}\)
    \State \(\mathbf{U}_k \gets -\frac{\mathbf{\Delta}_k}{\eta'_k}\), \(C_k \gets \log (\eta'_k/\eta_k) + 1\)
    \Comment Normalization \& Certainty estimation
    \State \(I_k = F_k(\mathbf{x}) / F_k(\mathbf{x}^0)\)
    \State Report \((\mathbf{U}_k, C_k, I_k)\) to the server
\EndFor
\State \(\mathbf{g} \gets \frac{\sum S_k I_k^\alpha \mathbf{U}_k}{\sum S_k I_k^\alpha}\), \(C \gets \frac{\sum S_k I_k^\alpha C_k}{\sum S_k I_k^\alpha}\) \Comment Server aggregation
\State \Return \(\mathbf{g}\), \(C\)
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{minipage}
\par
}

\begin{figure}[t]
\centering
\includegraphics[width=0.7\textwidth]{figures/adafedadam_aistats.pdf}
\caption{Illustration of \texttt{AdaFedAdam}{}: \(\mathbf{x}^t\), \(\mathbf{x}^*_k\) and \(\mathbf{x}^*\) denote the global model at round \(t\), the optima of local objective functions of client \(k\) and the optima of the global objective function, respectively. }
\label{fig:regu}
\end{figure}

\texttt{AdaFedAdam}{} has 3 improvements over standard \texttt{FedAdam}{}:
\paragraph{1. Normalization of local updates} Due to different \(L\)-smoothness constants of local objectives and local steps across participants, lengths of accumulated updates \(\mathbf{\Delta}_k\) are not at uniform scales and normalization of local updates is necessary as discussed in Section \ref{sec:ana_fedadam}. Natural scales for local updates are the \(\ell_2\)-norms of local gradients \(\|\nabla F_k(\mathbf{x}^t)\|_2\) on client \(k\). By normalizing \(\mathbf{\Delta}_k\) to the same \(\ell_2\)-norm of \(\|\nabla F_k(\mathbf{x}^t)\|_2\), a normalized update \(\mathbf{U}_k\) and a supportive factor \(\eta'_k\) are obtained. Intuitively, \(\mathbf{\Delta}_k\) can be seen as one update step following a "confident" update direction \(-\mathbf{U}_k\) with a large learning rate \(\eta'_k\) on the model \(\mathbf{x}^t\) given by client \(k\). The certainty of the direction \(\mathbf{U}^k\) is defined as \(C_k := \log(\eta'_k/\eta_k) + 1\) (\(\eta_k\) as the learning rate of the local solver), and the greater \(C_k\) is, the larger update can be made following \(\mathbf{U}_k\).

\paragraph{2. Fairness control} Following the formulation of the loss function in fair federated learning in Section \ref{sec:background}, the pseudo-gradient \(\mathbf{g}^t\) of the global model \(\mathbf{x}^t\) is correspondingly the average of the normalized local updates with adaptive weights \(I^\alpha_k\), where \(I_k\) is the \textit{inverse training rate} and \(\alpha\) is the predefined hyperparameter for fairness control. The certainty of \(\mathbf{g}^t\) is given by the weighted average of local certainties \(C_k\) for all \(k\in[K]\).

\paragraph{3. Adaptive hyperparameters for federated \texttt{Adam}{}}
Hyperparameters of \texttt{FedAdam}{} are adapted as follows to make better use of pseudo-gradients \(\mathbf{g}\) from accumulated updates:
\begin{itemize}[nosep]
    \item  \(\beta_{t,1} \gets \beta_{1} ^ {C}\), \(\beta_{t,2} \gets \beta_{2} ^ {C}\): Adaptive \(\beta_{t,1}\) and \(\beta_{t,2}\) dynamically control the weight of the current update for the momentum estimation. \texttt{AdaFedAdam}{} assigns more weight to more "certain" pseudo-gradients to update the average, and thus \(\beta_1\) and \(\beta_2\) are adapted exponentially following the form of exponentially weighted moving average.
    \item \(\eta_{t} \gets C\eta\): The base stepsize \(\eta_t\) is adjusted based on the certainty of the pseudo-gradient \(C\) as well. Greater certainty enables larger \(\eta_t\) to construct larger \emph{trust regions} and vice versa.
\end{itemize}

Theoretically, \texttt{AdaFedAdam}{} ensures the following features:
\begin{itemize}
    \item \textbf{Fairness guarantee}: The fairness of the model has been formulated into the objective function in fair federated learning to be optimized together with the error with theoretical \((p, \alpha)\)\textit{-Proportional Fairness} (\cite{mo2000fair}). Also, the algorithm can be adapted to different fairness levels by adjusting \(\alpha\) in the problem formulation.
    \item \textbf{Fine-tuning free:} The adaptivity of \texttt{AdaFedAdam}{} derives from dynamic adjustment of hyperparameters for \texttt{Adam}{}. All initial hyperparameters of \texttt{AdaFedAdam}{} can be chosen as the default values in the standard \texttt{Adam}{} for the centralized setting, and they are adaptively adjusted during the federated training process.
    \item \textbf{Allowance for resource heterogeneity:} Thanks to the normalization of local updates, \texttt{AdaFedAdam}{} allows arbitrary numbers of local steps, which could be caused by resource limitation of clients (also known as resource heterogeneity).
    \item \textbf{Compatibility with arbitrary local solvers:} The normalization of local updates only relies on the \(\ell_2\)-norm of the local gradient estimation. Thus, any first-order optimizers are compatible with \texttt{AdaFedAdam}{}.
\end{itemize}
These features of \texttt{AdaFedAdam}{} are empirically validated and discussed in Section \ref{sec:experiments}.
\subsection{Convergence analysis for \texttt{AdaFedAdam}{}}
The convergence guarantee of \texttt{AdaFedAdam}{} for convex functions is proved as follows.

\begin{theorem}[Convergence of \texttt{AdaFedAdam}{}]\label{thrm:ours}
\textit{Assume the \(L\)-smooth convex loss function \(f(\mathbf{x})\) has bounded gradients \(\|\nabla\|_{\infty} \leq G\) for all \(\mathbf{x} \in \mathbb{R}^d\), and hyperparameters \(\epsilon\), \(\beta_{2,0}\) and \(\eta_0\) are chosen according to the following conditions: \(\eta_0 \leq \epsilon/2L\) and \(1-\beta_{2,0} \leq \epsilon^2/16G^2\).The pseudo-gradient \(\mathbf{g}_t\) at step \(t\) is given by Algorithm \ref{alg:adafedadam} with its certainty \(C^t\). The convergence guarantee of \texttt{AdaFedAdam}{} is given by: }

\begin{equation}\label{eq:ours}
 \frac{1}{T} \sum_{t=1}^T \|\nabla f(\mathbf{x}^t)\|^2) \leq \frac{2(f(\mathbf{x}^1) - f(\mathbf{x}^*))(\sqrt{\beta_{2,0}}G+\epsilon)}{RC\eta_0}
\end{equation}
where \(R := \min_t (\min_i | \frac{\mathbf{g}_{t,i}}{\nabla_{t,i}} |)\) for all \(i \in [d], t \in [T]\) and \(C := \min C^t\) for \(t \in [T]\).
\end{theorem}

The proof of Theorem \ref{thrm:ours} is deferred to the \ref{subsec:proof2}. By normalizing local updates to the same \(\ell_2\)-norm of local gradients, the convergence of \texttt{AdaFedAdam}{} can be guaranteed. When the client optimizers are fixed as \texttt{SGD}{} and 1 step is performed locally, the federated training is identical to minibatch \texttt{Adam}{} and Theorem \ref{thrm:ours} gives the identical convergence guarantee of \texttt{Adam}{} (\cite{reddi2019convergence}). It should be noticed that Theorem \ref{thrm:ours} does not provide a tight bound for the convergence rate but only focuses on the convergence guarantee. Better empirical performance of \texttt{AdaFedAdam}{} can be expected.

\section{EXPERIMENTAL RESULTS}\label{sec:experiments}
\paragraph{Experimental setups}To validates the effectiveness and robustness of \texttt{AdaFedAdam}{}, four federated setups are used: 1). Femnist setup: A multi-layer perceptron (MLP) network (\cite{pal1992multilayer}) for image classification on Federated EMNIST dataset (\cite{deng2012mnist}), proposed by \cite{caldas2018leaf} as a benchmark task for federated learning; 2). Cifar10 setup: VGG11 (\cite{simonyan2014very}) for image classification on Cifar10 dataset (\cite{krizhevsky2009learning}) partitioned by Dirichlet distribution \(\textbf{Dir}(0.05)\) for 16 clients; 3). Sent140 setup: A stacked-LSTM model (\cite{gers2000learning}) for sentiment analysis on the Text Dataset of Tweets (\cite{go2009twitter}); 4). Synthetic setup: A linear regression classifier for multi-class classification on a synthetic dataset (Synthetic), proposed by \cite{caldas2018leaf} as a challenging task for benchmarking federated algorithms. A summary of four setups are shown in Table \ref{tab:setups}. Details of the model architectures and experimental settings are available in \ref{subsec:exp_details}.

\begin{table}[ht]
\small
  \caption{A summary of setups: the four setups cover different Federated Learning scenarios, non-IID types and task types. }
  \label{tab:setups}
  \centering
  \begin{tabular}{ l | l | l | l | l | l}
    \hline
    \header{Setup} & \header{\# Clients} & \header{Model} & \header{Scenario} & \header{Non-IID Type} & \header{Task Type}\\
    \hline
    Femnist     & 3500  &   MLP     & Cross Device      & Intrinsic  & Computer Vision\\
    Cifar10     & 16    &   CNN   & Cross Silo        & Dirichlet  & Computer Vision\\
    Sent140     & 697   &   LSTM    & Cross Device      & Intrinsic  & Natural Language Process\\
    Synthetic   & 100   &   Linear Model   & Cross Device/Silo & Synthetic  & Classification\\
    \hline
  \end{tabular}
  \vspace{-3mm}
\end{table}

\paragraph{Convergence \& Fairness}We benchmark \texttt{AdaFedAdam}{} against \texttt{FedAvg}{}, \texttt{FedAdam}{}, \texttt{FedNova}{} and \texttt{q-FedAvg}{} with \(q=1\). All hyperparameters of the optimizers are set as the default values in centralized settings. The fairness of the model is quantified by the standard deviation (STD) of local accuracy on clients and the average accuracy of the worst 30\% clients. The training curves are shown in Figure \ref{fig:training_curves} with numerical details in \ref{subsec:full_results}. Figure \ref{fig:training_curves} shows that \texttt{AdaFedAdam}{} consistently converges faster than other algorithms, with better worst 30\% client performance for all setups. Distributions of local accuracy indicate that federated models trained with \texttt{AdaFedAdam}{} provide the most uniform distributions of local accuracy for the participants. It is also noticeable that other federated algorithms without fine-tuning does not provide consistent performance in different setups with default hyperparameters, which validates the necessity of fine-tuning. In contrast, \texttt{AdaFedAdam}{} provides the best and the most stable performances in all setups with default hyperparameters. To summarize, \texttt{AdaFedAdam}{} is able to train federated models with fair performances among participants with better convergence without fine-tuning.

\begin{figure*}[ht]
    \centering
    \includegraphics[width=0.33\textwidth]{figures/convergence/FEMNIST_Test_accuracy.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/FEMNIST_Test_accuracy_of_worst_30.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/FEMNIST_Local_Accuracy_Distribution.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/CIFAR10_Test_accuracy.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/CIFAR10_Test_accuracy_of_worst_30.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/CIFAR10_Local_accuracy_distribution.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/SENT140_Test_accuracy.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/SENT140_Test_accuracy_of_worst_30.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/SENT140_Local_accuracy_distribution.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/SYNTHETIC_Test_accuracy.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/SYNTHETIC_Test_accuracy_of_worst_30.pdf}
    \includegraphics[width=0.33\textwidth]{figures/convergence/SYNTHETIC_Local_accuracy_distribution.pdf}
    \caption{Metrics of local test accuracy during the training process: \texttt{FedAvg}{}, \texttt{FedAdam}{}, \texttt{FedNova}{}, \texttt{q-FedAvg}{} and \texttt{AdaFedAdam}{} on different setups. \textbf{Left: }Average of local test accuracy of participants. \textbf{Middle: }Average of local test accuracy of the worst 30\% participants. \textbf{Right: }Distribution of local test accuracy of participants. For all setups, \texttt{AdaFedAdam}{} consistently outperforms baseline algorithms, with better model convergence and fairness among the participants. }
    \label{fig:training_curves}
\end{figure*}

\paragraph{Choice of \(\alpha\)}Hyperparameter \(\alpha\) is to control the level of desired model fairness. By increasing \(\alpha\), models become more fair between clients at a cost of convergence. For each federated learning process, there exists a Pareto Front (\cite{ngatchou2005pareto}) for the trade-off. Taken the Synthetic setup as an example, the average and relative standard deviation (RSD) of local validation error during the training process and the formed Pareto Front is shown as Figure \ref{fig:pareto}. It is observed that with increase of \(\alpha\) from 1 to 4, the RSD of the local error decreases significantly with a slight decrease of the convergence. With \(\alpha>4\), the RSD of the local error does not reduce significantly but the convergence continues to decrease. By plotting the average and RDS of local error of models trained with \texttt{AdaFedAdam}{} for different \(\alpha\) together with other federated algorithms, it can be observed that \texttt{FedAvg}{}, \texttt{FedAdam}{}, \texttt{FedNova}{} and \texttt{q-FedAvg}{} are sub-optimal in the blue area in Figure \ref{fig:pareto}. By default, \(1\leq\alpha \leq4\) is enough to provide proper model fairness without losing much convergence.

\begin{figure*}[ht]
\centering
\includegraphics[width=0.33\textwidth]{figures/pareto/adafedadam_Average_of_test_error.pdf}
\includegraphics[width=0.33\textwidth]{figures/pareto/adafedadam_RSD_of_test_error.pdf}
\includegraphics[width=0.33\textwidth]{figures/pareto/ParetoFrontoftheSyntheticSetup.pdf}
\caption{\textbf{Left:} Training curves of \texttt{AdaFedAdam}{} with different \(\alpha\) on the Synthetic setup. \textbf{Middle:} RSD of local error of \texttt{AdaFedAdam}{} with different \(\alpha\) on the Synthetic setup. \textbf{Right:} Pareto Front of the Synthetic setup formed by \texttt{AdaFedAdam}{} with different \(\alpha\). By adjusting values of \(\alpha\), the trade-off between the convergence and the fairness can be observed together with the suboptimality of other federated algorithms. }
\label{fig:pareto}
\end{figure*}

\paragraph{Robustness}Experiments to validate the robustness of \texttt{AdaFedAdam}{} against resource heterogeneity and different levels of data heterogeneity are conducted with the Cifar10 setup.

Robustness against resource heterogeneity is important for algorithms to be applied in real life. Due to the heterogeneity of clients' computing resources, the server cannot expect all participants perform requested number of local steps / epochs in each global round and thus, clients may perform arbitrary numbers of local steps on the global model in each communication round. To simulate settings of resource heterogeneity, time-varying numbers of local epochs are randomly sampled from a uniform distribution \(\mathcal{U}(1,3)\) in each communication round for each participant. The results are shonw in Table \ref{tab:rob_as}. With resource heterogeneity, \texttt{AdaFedAdam}{} outperform other federated algorithms with higher average accuracy and more fairness.

\begin{table}[ht]
\small
  \caption{Experimental results of federated algorithms against resource heterogeneity on the Cifar10 setup. Time-varying numbers of local epochs are sampled from a uniform distribution \(\mathcal{U}(1,3)\) in each communication round.}
  \label{tab:rob_as}
  \centering
  \begin{tabular}{l|lll}
    \hline
    \header{Algorithm} & \header{Avg.(\%)} & \header{STD.(\%)} & \header{Worst 30. (\%)} \\
    \hline
        \texttt{FedAvg} & 36.82 \textpm 1.45 & 21.32 \textpm 1.89 & 10.69 \textpm 3.29\\
        \texttt{FedAdam} & 54.57 \textpm 1.87 & 13.03 \textpm 2.53 & 40.32 \textpm 5.11\\
        \texttt{q-FedAvg} & 27.36 \textpm 1.09 & 24.34 \textpm 1.35 & 2.67 \textpm 1.16\\
        \texttt{FedNova} & 38.03 \textpm 1.18 & 24.99 \textpm 2.15 & 6.24 \textpm 2.96\\
        \texttt{AdaFedAdam} & 63.26 \textpm 1.41 & 8.64 \textpm 1.35  &45.07 \textpm 2.38\\

    \hline
  \end{tabular}
  \vspace{-3mm}
\end{table}

Robustness against different non-IID levels ensures the performance of an algorithm in various application cases. To simulate different non-IID levels, the Cifar10 dataset is partitioned by the Dirichlet distribution over labels with different concentration parameters \(\beta \in [0,1]\), denoted as \(\textbf{Dir}(\beta)\). A smaller value of \(\beta\) indicates larger level of data heterogeneity. The results are shown in Table \ref{tab:rob_dir}. With different levels of data heterogeneity, \texttt{AdaFedAdam}{} is able to converge, and better performance and fairness are obtained in settings with less data heterogeneity, as expected.

\begin{table}[H]
\small
  \caption{Experimental results of \texttt{AdaFedAdam}{} in different levels of non-iid settings on the Cifar10 setup. }
  \label{tab:rob_dir}
  \centering
  \begin{tabular}{l|lll}
    \hline
    \header{Distribution} & \header{Avg.(\%)} & \header{STD.(\%)} & \header{Worst 30. (\%)} \\
    \hline
    \(\textbf{Dir}(0.05)\)  &62.81 \textpm 1.02 & 8.18 \textpm 1.33  &46.01 \textpm 2.23\\

    \(\textbf{Dir}(0.1)\)   &66.16 \textpm 1.13 & 6.58 \textpm 0.77 & 55.26 \textpm 2.83\\

    \(\textbf{Dir}(0.5)\)   & 71.43 \textpm 0.81 & 5.4 \textpm 0.22 & 64.93 \textpm 1.04\\

    \(\textbf{Dir}(1)\)    & 72.77 \textpm 0.44 & 3.05 \textpm 0.11 & 69.57 \textpm 0.54\\

    \hline
  \end{tabular}
  \vspace{-3mm}
\end{table}

\paragraph{Compatibility with local momentum} We also show that \texttt{AdaFedAdam}{} is compatible with momentum-based local optimizers beside \texttt{SGD}{}, which can further improve the model performance. Adaptive optimizers as client solvers (e.g. \texttt{Adam}{}) do not guarantee better performance over vanilla \texttt{SGD}{} without synchronizing states of local optimizers, as discussed in \cite{yu2019linear,yuan2020federated}. There are reported algorithms to synchronize states of local optimizers and \texttt{AdaFedAdam}{} is orthogonal and compatible with these algorithms. Full experimental results for different local solvers are deferred to \ref{subsec:full_results}

\begin{table}[ht]
\small
  \caption{Experimental results of the \texttt{AdaFedAdam}{} with different local optimizers on the Synthetic setup, including vanilla \texttt{SGD}{}, \texttt{SGD}{} with momentum and \texttt{SGD}{} with Nesterov momentum. }
  \label{tab:local_solvers}
  \centering
  \begin{tabular}{l|lll}
    \hline
    \header{Local Optimizer} & \header{Avg.(\%)} & \header{STD.(\%)} & \header{Worst 30. (\%)} \\
    \hline
    Vanilla \texttt{SGD}{}  & 94.18 \textpm 0.45 & 8.52 \textpm 0.37 & 87.07 \textpm 2.28\\

    \texttt{SGD}{} w. Momen. & 97.19 \textpm 0.11 & 3.32 \textpm 0.02 & 93.41 \textpm 0.11\\

    \texttt{SGD}{} w. Neste. Momen. & 97.27 \textpm 0.16 & 3.19 \textpm 0.21 & 94.19 \textpm 0.24\\

    \hline
  \end{tabular}
  \vspace{-3mm}
\end{table}

\section{Conclusion}\label{sec:conclusion}
In this work, we formulated federated learning as a dynamic multi-objective optimization problem by adjusting the weights of local objectives to achieve fair model performance among the participants. To solve the problem efficiently, we presented \texttt{AdaFedAdam}{}, which reduces biases in \texttt{FedAdam}{} and accelerates the training of fair federated learning with minor extra efforts in fine-tuning. Empirically we validated the efficiency and fairness of \texttt{AdaFedAdam}{} and verified its Pareto optimality compared with other federated learning algorithms. Further, we demonstrated the robustness of \texttt{AdaFedAdam}{} against resource heterogeneity and different levels of data heterogeneity. We have also shown the compatibility of \texttt{AdaFedAdam}{} with other local optimizers. Future directions include testing \texttt{AdaFedAdam}{} in real-world geographically distributed setups for both cross-silo and cross-device settings with production grade open source frameworks(\cite{yang2019federated, ekmefjord2022scalable}).

\printbibliography[heading=subbibliography]

\newpage