\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
