: Federated , , and Compositional Optimization

Davoud Ataee Tarzanaghumich
Mingchen Liucr
Christos Thrampoulidisubc
Samet Oymakucr

umichEmail: ,
University of Michigan
ucrEmails: ,
University of California, Riverside
ubcEmail: ,
University of British Columbia
Davoud Ataee Tarzanagh
Machine Learning, ICML

Standard federated optimization methods successfully apply to stochastic problems with single-level structure. However, many contemporary ML problems – including adversarial robustness, hyperparameter tuning, actor-critic – fall under nested bilevel programming that subsumes minimax and compositional optimization. In this work, we propose : A federated alternating stochastic gradient method to address general nested problems. We establish provable convergence rates for in the presence of heterogeneous data and introduce variations for bilevel, minimax, and compositional optimization. introduces multiple innovations including federated hypergradient computation and variance reduction to address inner-level heterogeneity. We complement our theory with experiments on hyperparameter & hyper-representation learning and minimax optimization that demonstrate the benefits of our method in practice.  Code is available at <https://github.com/ucr-optml/FedNest>.

§ INTRODUCTION

In the federated learning (FL) paradigm, multiple clients cooperate to learn a model under the orchestration of a central server <cit.> without directly exchanging local client data with the server or other clients. The locality of data distinguishes FL from traditional distributed optimization and also motivates new methodologies to address heterogeneous data across clients. Additionally, cross-device FL across many edge devices presents additional challenges since only a small fraction of clients participate in each round, and clients cannot maintain state across rounds <cit.>.

Traditional distributed SGD methods are often unsuitable in FL and incur high communication costs. To overcome this issue, popular FL methods, such as  <cit.>, use local client updates, i.e. clients update their models multiple times before communicating with the server (aka, local SGD). Although has seen great success, recent works have exposed convergence issues in certain settings <cit.>. This is due to a variety of factors, including client drift, where local models move away from globally optimal models due to objective and/or systems heterogeneity.

at (-3.2,-.4)[anchor=west] ;

at (6,1.8)[anchor=west] [scale=1]Communication-efficiency:;
at (6.3,1.4)[anchor=west] avoids explicit Hessian;
at (6.3,1.0)[anchor=west] for local hypergradients;

at (6,0.5)[anchor=west] [scale=1]Client heterogeneity:;
at (6.3,0.15)[anchor=west] avoids client drift;

at (6,-0.3)[anchor=west] [scale=1]Finite sample bilevel theory:;
at (6.3,-0.7)[anchor=west] Stochastic inner & outer analysis;

at (6,-1.1)[anchor=west] [scale=1]Specific nested optimization problems:;
at (6.3,-1.5)[anchor=west] Bilevel;
at (6.3,-1.9)[anchor=west] Minimax;
at (6.3,-2.3)[anchor=west] Compositional;

Depiction of federated bilevel nested optimization and high-level summary of (Algorithm <ref>). At outer loop, uses multiple rounds of matrix-vector products to facilitate hypergradient computation while only communicating vectors. At inner loop, uses FedSVRG to avoid client drift and find the unique global minima. Both are crucial for establishing provable convergence of .

Existing FL methods, such as , are widely applied to stochastic problems with single-level structure. Instead, many machine learning tasks – such as adversarial learning <cit.>, meta learning <cit.>, hyperparameter optimization <cit.>, reinforcement/imitation learning <cit.>, and neural architecture search <cit.> – admit nested formulations that go beyond the standard single-level structure. Towards addressing such nested problems, bilevel optimization has received significant attention in the recent literature
<cit.>; albeit in non-FL settings. On the other hand, federated versions have been elusive perhaps due to the additional challenges surrounding heterogeneity, communication, and inverse Hessian approximation.

Contributions: This paper addresses these challenges and develops : A federated machinery for nested problems with provable convergence and lightweight communication. is composed of : a federated stochastic variance reduction algorithm (FedSVRG) to solve the inner problem while avoiding client drift, and : a communication-efficient federated hypergradient algorithm for solving the outer problem. Importantly, we allow both inner & outer objectives to be finite sums over heterogeneous client functions. runs a variant of FedSVRG on inner & outer variables in an alternating fashion as outlined in Algorithm <ref>. We make multiple algorithmic and theoretical contributions summarized below.

* The variance reduction of enables robustness in the sense that local models converge to the globally optimal inner model despite client drift/heterogeneity unlike . While is similar to FedSVRG <cit.> and FedLin <cit.>, we make two key contributions: (i) We leverage the global convergence of to ensure accurate hypergradient computation which is crucial for our bilevel proof.  (ii) We establish new convergence guarantees for single-level stochastic non-convex FedSVRG, which are then integrated within our .

* Communication efficient bilevel optimization: Within , we develop an efficient federated method for hypergradient estimation that bypass Hessian computation. Our approach approximates the global Inverse Hessian-Gradient-Product (IHGP) via computation of matrix-vector products over few communication rounds.

* : To further improve communication efficiency, we additionally propose a Light-algorithm, which computes hypergradients locally and only needs a single communication round for the outer update. Experiments reveal that becomes very competitive as client functions become more homogeneous.

* Unified federated nested theory: We specialize our bilevel results to minimax and compositional optimization with emphasis on the former. For these, significantly simplifies and leads to faster convergence. Importantly, our results are on par with the state-of-the-art non-federated guarantees for nested optimization literature without additional assumptions (Table <ref>).

* We provide extensive numerical experiments on bilevel and minimax optimization problems. These demonstrate the benefits of , efficiency of , and shed light on tradeoffs surrounding communication, computation, and heterogeneity.

§ FEDERATED NESTED PROBLEMS &

We will first provide the background on bilevel nested problems and then introduce our general federated method.

$\mb{N}$ and $\mb{R}$ denotes the set of natural and real numbers, respectively.
For a differentiable function $h(\m{x},\m{y}):\mb{R}^{d_1}\times\mb{R}^{d_2}\rightarrow\mb{R}$ in which $\m{y}=\m{y}(\m{x}):\mb{R}^{d_1}\rightarrow\mb{R}^{d_2}$, we denote $\nabla{h}\in\mb{R}^{d_1}$ the gradient of $h$ as a function of $\m{x}$ and  $\nabla_{\m{x}}{h}$, $\nabla_{\m{y}} h$ the partial derivatives of $h$ with respect to $\m{x}$ and $\m{y}$, respectively. We let $\nabla_{\m{xy}}^2 h$ and $\nabla_{\m{y}}^2 h$ denote the Jacobian and Hessian of $h$, respectively. We consider FL optimization over $m$ clients and we denote $\mathcal{S}=\{1,\ldots,m\}$. For vectors $\m{v} \in \mb{R}^d$ and matrix $\m{M} \in \mb{R}^{d \times d}$, we denote $\|\m{v}\|$ and $\|\m{M}\|$ the respective Euclidean and spectral norms.

§.§ Preliminaries on Federated Nested Optimization

In federated bilevel learning, we consider the  following nested optimization problem as depicted in Figure <ref>:

\begin{align}
\begin{array}{ll}
\underset{\m{x} \in \mb{R}^{{d}_1}}{\min} &
\begin{array}{c}
f(\m{x})=\frac{1}{m} \sum_{i=1}^{m} f_{i}\left(\m{x},\m{y}^*(\m{x})\right) %{\rm\sf (outer)}
\end{array}\\
\text{subj.~to} & \begin{array}[t]{l} \m{y}^*(\m{\m{x}})
\in \underset{ \m{y}\in \mb{R}^{{d}_2}}{\textnormal{argmin}}~~\frac{1}{m}\sum_{i=1}^{m} g_i\left(\m{x},\m{y}\right). % ~~~~~~~~~~~~~~~~~~~~{\rm\sf (inner)}
\end{array}
\end{array}
\end{align}

Recall that $m$ is the number of clients. Here, to model objective heterogeneity, each client $i$ is allowed to have its own individual outer & inner functions $(f_i,g_i)$. Moreover, we consider a general stochastic oracle model, access to local functions $(f_i,g_i)$ is via stochastic sampling as follows:

\begin{align}
\nonumber
f_i(\m{x},\m{y}^*(\m{x})) &:= \mb{E}_{\xi \sim \mc{C}_i}\left[f_i(\m{x}, \m{y}^*(\m{x}); \xi)\right],\\g_i(\m{x},\m{y}) &:= \mb{E}_{\zeta \sim \mc{D}_i}\left[g_i(\m{x}, \m{y}; \zeta)\right],
\end{align}

where $(\xi, \zeta)\sim(\mc{C}_i, \mc{D}_i)$ are  outer/inner sampling distributions for the $i^{\text{th}}$ client. We emphasize that for $i \neq j$, the tuples $(f_i,g_i,\mc{C}_i, \mc{D}_i)$ and $(f_j,g_j,\mc{C}_j, \mc{D}_j)$ can  be different.

[Hyperparameter tuning] Each client has local validation and training datasets associated with objectives $(f_i,g_i)_{i=1}^m$ corresponding to validation and training losses, respectively. The goal is finding hyper-parameters $\x$ that lead to learning model parameters $\y$ that minimize the (global) validation loss.

The stochastic bilevel problem (<ref>) subsumes two popular problem classes with the nested structure: Stochastic MiniMax & Stochastic Compositional. Therefore, results on the general nested problem (<ref>)  also imply the results in these special cases. Below, we briefly describe them.

Minimax optimization. If $g_i(\x,\y;\zeta):=-f_i(\x,\y;\xi)$ for all $i \in \mc{S}$, the stochastic bilevel problem (<ref>) reduces to the stochastic minimax problem

\begin{align}\label{fedminmax:prob}
\min_{\m{x}\in\mb{R}^{d_1}}~f(\m{x}):=\frac{1}{m} \max_{\m{y}\in\mb{R}^{d_2}}\sum_{i=1}^{m} \E[f_{i}\left(\m{x},\m{y}; \xi\right)].
\end{align}

Motivated by applications in fair beamforming, training generative-adversarial networks (GANs) and robust machine learning, significant efforts have been made for solving (<ref>) including <cit.>.

[GANs] We train a generative model $g_{\x}(\cdot)$ and an adversarial model $a_{\y}(\cdot)$ using client datasets ${\mc{C}}_i$. The local functions may for example take the form $f_i(\x,\y)=\E_{s\sim {\mc{C}}_i}\{\log a_{\y}(s)\} +\E_{z\sim {\cal{D}}_{\text{noise}}}\{\log[1-a_{\y}(g_{\x}(z))]\}$.

Compositional optimization. Suppose $f_i(\m{x},\m{y};\xi):=f_i(\m{y};\xi)$ and $g_i$ is quadratic in $\m{y}$ given as $g_i(\m{x},\m{y};\zeta):=\|\m{y}-\m{r}_i(\m{x};\zeta)\|^2$. Then, the bilevel problem (<ref>) reduces to

\begin{align}\label{fedcompos:prob2}
\begin{array}{ll}
\underset{\m{x} \in \mb{R}^{{d}_1}}{\min} &
\begin{array}{c}
f(\m{x})=\frac{1}{m} \sum_{i=1}^{m} f_{i}\left(\m{y}^*(\m{x})\right) %{\rm\sf (outer)}
\end{array}\\
\text{subj.~to} & \begin{array}[t]{l} \m{y}^*(\m{\m{x}})=\underset{ \m{y}\in \mb{R}^{{d}_2}}{\textnormal{argmin}}~~\frac{1}{m}\sum_{i=1}^{m} g_i\left(\m{x},\m{y}\right) % ~~~~~~~~~~~~~~~~~~~~{\rm\sf (inner)}
\end{array}
\end{array}
\end{align}

with $f_i(\m{y}^*(\m{x})) := \mb{E}_{\xi \sim \mc{C}_i}[f_i( \m{y}^*(\m{x}); \xi)]$ and $g_i(\m{x},\m{y}):= \mb{E}_{\zeta \sim \mc{D}_i}[g_i(\m{x},\m{y};\zeta)]$.
Optimization problems in the form of (<ref>) occur for example in model agnostic meta-learning and policy evaluation in reinforcement learning <cit.>.

Assumptions. Let $\m{z}=(\m{x},\m{y}) \in \mb{R}^{d_1+d_2}$. Throughout, we make the following assumptions on inner/outer objectives.

[Well-behaved objectives]

For all $i \in [m]$:

$f_i(\m{z}), \nabla f_i(\m{z}), \nabla g_i(\m{z}), \nabla^2 g_i (\m{z})$ are $\ell_{f,0}$,$\ell_{f,1}$,$\ell_{g,1}$, $\ell_{g,2}$-Lipschitz continuous, respectively; and

$g_i(\m{x},\m{y})$ is $\mu_{g}$-strongly convex in $\m{y}$ for all $\m{x}\in \mb{R}^{d_1}$.

Throughout, we use $\kappa_g=\ell_{g,1}/\mu_g$ to denote the condition number of the inner function $g$.
[Stochastic samples]
For all $i \in [m]$:

* $\nabla f_i(\m{z};\xi)$, $\nabla g_i(\m{z};\zeta)$, $\nabla^2 g_i(\m{z}; \zeta)$ are unbiased estimators of $\nabla f_i(\m{z})$, $\nabla g_i(\m{z})$, $\nabla^2g_i(\m{z})$, respectively; and

* Their variances are bounded, i.e., $\mb{E}_{\xi}[\|\nabla f_i(\m{z};\xi)-\nabla f_i(\m{z})\|^2] \leq \sigma_f^2$,   $\mb{E}_{\zeta}[\|\nabla g_i(\m{z};\zeta) -\nabla g_i(\m{z})\|^2] \leq \sigma_{g,1}^2$, and $\mb{E}_{\zeta}[\|\nabla^2 g_i(\m{z};\zeta)-\nabla^2 g_i(\m{z})\|^2] \leq \sigma_{g,2}^2$ for some $\sigma_f^2, \sigma_{g,1}^2$, and $\sigma_{g,2}^2$.

These assumptions are common in the bilevel optimization literature <cit.>. Assumption <ref> requires that the inner and outer functions are well-behaved. Specifically, strong-convexity of the inner objective is a recurring assumption in bilevel optimization theory implying a unique solution to the inner minimization in (<ref>).

§.§ Proposed Algorithm:

In this section, we develop , which is formally presented in Algorithm <ref>. The algorithm operates in two nested loops. The outer loop operates in rounds $k\in\{1,\ldots,K\}$. Within each round, an inner loop operating for $T$ iterations is executed. Given estimates $\m{x}^k$ and  $\m{y}^k$, each iteration $t\in\{1,\ldots,T\}$ of the inner loop produces a new global model $\m{y}^{k,t+1}$ of the inner optimization variable $\m{y}^*(\m{x}^k)$ as the output of an optimizer . The final estimate $\m{y}^{k+1}=\m{y}^{k,T}$ of the inner variable is then used by an optimizer to update the outer global model $\m{x}^{k+1}$.

The subroutines and are gradient-based optimizers.

Each subroutine involves a certain number of local training steps indexed by $\nu\in\{0,\ldots,\tau_i-1\}$ that are performed at the $i^{\text{th}}$ client. The local steps of iterate over local models $\m{y}_{i,\nu }$ of the inner variable. Accordingly, iterates over local models $\m{x}_{i,\nu }$ of the global variable. A critical component of is a communication-efficient federated hypergradient estimation routine, which we call .

The implementation of , and is critical to circumvent the algorithmic challenges of federated bilevel optimization. In the remaining of this section, we detail the challenges and motivate our proposed implementations. Later, in Section <ref>, we provide a formal convergence analysis of .

§.§ Key Challenge: Federated Hypergradient Estimation

is a gradient-based optimizer for the outer minimization in (<ref>); thus each iteration involves computing $\nabla f(\x)=(1/m)\sum_{i=1}^{m}\nabla f_i(\x,\y^*(\x))$. Unlike single-level FL, the fact that the outer objective $f$ depends explicitly on the inner minimizer $\y^*(\x)$ introduces a new challenge.

A good starting point to understand the challenge is the following evaluation of $\nabla f(\x)$ in terms of partial derivatives. The result is well-known from properties of implicit functions.

Under Assumption <ref>, for all $i\in [m]$:

\begin{align*}
\nabla f_i(\m{x}, \m{y}^*(\m{x}))&= \nabla^{\texttt{D}}f_i\left(\m{x},\m{y}^*(\m{x})\right)+\nabla^{\texttt{I}}f_i\left(\m{x},\m{y}^*(\m{x})\right),
\end{align*}

where the direct and indirect gradient components are:

\begin{align}\label{main_grad:decom}
&  \nabla^{\texttt{D}} f_i(\m{x},\m{y}^*(\m{x})):= \nabla_{\m{x}}f_i\left(\m{x},\m{y}^*(\m{x})\right),\\
\nonumber
&\nabla^{\texttt{I}} f_i(\m{x},\m{y}^*(\m{x})):=- \nabla^2_{\m{x}\m{y}} g(\m{x},\m{y}^*(\m{x}))\\
&\quad \qquad\cdot \left[\nabla^2_{\m{y}}g(\m{x},\m{y}^*(\m{x}))\right]^{-1} \nabla_\m{y} f_i \left(\m{x},\m{y}^*(\m{x})\right).\label{main_grad:decom2}
\end{align}

We now use the above formula

to describe the two core challenges of bilevel FL optimization.

First, evaluation of any of the terms in (<ref>) requires access to the minimizer $\m{y}^*(\m{x})$ of the inner problem. On the other hand, one may at best hope for a good approximation to $\m{y}^*(\m{x})$ produced by the inner optimization subroutine. Of course, this challenge is inherent in any bilevel optimization setting, but is exacerbated in the FL setting because of client drift. Specifically, when clients optimize their individual (possibly different) local inner objectives, the global estimate of the inner variable produced by SGD-type methods may drift far from (a good approximation to) $\m{y}^*(\m{x})$. We explain in Section <ref> how solves that issue.

The second challenge comes from the stochastic nature of the problem.

Observe that the indirect component in (<ref>) is nonlinear in the Hessian $\nabla_{\m{y}}^2 g(\m{x}, \m{y}^*(\m{x}))$,   complicating an unbiased stochastic approximation of $\nabla f_i(\m{x}, \m{y}^*(\m{x}))$. As we expose here,  solutions to this complication developed in the non-federated bilevel optimization literature, are not directly applicable in the FL setting. Indeed, existing stochastic bilevel algorithms, e.g.  <cit.>, define $\bar{\nabla}f(\m{x},\m{y}):= \bar{\nabla}^{\texttt{D}}f(\m{x},\m{y})+\bar{\nabla}^{\texttt{I}}f(\m{x},\m{y})$ as a surrogate of $\nabla f(\m{x},  \m{y}^*(\m{x}))$ by replacing $\m{y}^*(\m{x})$ in definition (<ref>) with an approximation $\m{y}$ and using the following stochastic approximations:

\begin{align}\label{eq.inverse-estimator.a}
& \bar{\nabla}^{\texttt{D}}f(\m{x},\m{y})  \approx  \nabla_{\m{x}} f(\m{x}, \m{y};\dot{\xi}),
\\
\nonumber
& \bar{\nabla}^{\texttt{I}}f(\m{x},\m{y})  \approx  -\nabla^2_{\m{xy}}g(\m{x},\m{y};\zeta_{N'+1}) \\
& \Big[\frac{N}{\ell_{g,1}}\prod\limits_{n=1}^{N'}\big(\m{I}-\frac{1}{\ell_{g,1}} \nabla^2_{\m{y}} g(\m{x},\m{y};\zeta_n)\big)\Big] \nabla_\m{y} f(\m{x},\m{y};\dot{\xi}).
\label{eq.inverse-estimator.b}
\end{align}

Here, $N'$ is drawn from $\{0,  \ldots, N-1\}$ uniformly at random (UAR) and  $\{\dot{\xi}, \zeta_{1}, \ldots,\zeta_{N'+1}\}$ are i.i.d. samples.
<cit.> have shown that using (<ref>), the inverse Hessian estimation bias exponentially decreases with the number of samples $N$.

One might hope to directly leverage the above approach in a local computation fashion by replacing the global outer function $f$ with the individual function $f_i$. However, note from (<ref>) and (<ref>) that the proposed stochastic approximation of the indirect gradient involves in a nonlinear way the global Hessian,  which is not available at the client [We note that the approximation in (<ref>) is not the only construction, and bilevel optimization can accommodate other forms of gradient surrogates <cit.>. Yet, all these approximations require access (in a nonlinear fashion) to the global Hessian; thus, they suffer from the same challenge in FL setting.]. Communication efficiency is one of the core objectives of FL making the idea of communicating Hessians between clients and server prohibitive. Is it then possible, in a FL setting, to obtain an accurate stochastic estimate of the indirect gradient while retaining communication efficiency? In Section <ref>, we show how and its subroutine , a matrix-vector products-based (thus, communication efficient) federated hypergradient estimator, answer this question affirmatively.

§.§ Outer Optimizer:

This section presents the outer optimizer , formally described in Algorithm <ref>. As a subroutine of (see Line 9, Algorithm <ref>), at each round $k=0,\ldots,K-1$, takes the most recent global outer model $\x^k$ together the updated (by ) global inner model $\y^{k+1}$ and produces an update $\x^{k+1}$. To lighten notation, for a round $k$, denote the function's input as $(\m{x}, \m{y}^+)$ (instead of $(\x^k,\y^{k+1})$) and the output as $\m{x}^+$ (instead of $\x^{k+1}$).

For each client $i\in \mathcal{S}$, uses   stochastic approximations of $\bar{\nabla}^{\texttt{I}} f_i(\m{x},\m{y}^+)$ and $\bar{\nabla}^{\texttt{D}}f_i(\m{x},\m{y}^+)$, which we call  $\m{h}_i^{\texttt{I}}(\m{x}, \m{y}^+)$ and $\m{h}_i^{\texttt{D}}(\m{x}, \m{y}^+)$, respectively.  The specific choice of these approximations (see Line 5) is critical and is discussed in detail later in this section. Before that, we explain how each client uses these proxies to form  local updates of the outer variable.

In each round, starting from a common global model $\m{x}_{i,0}=\m{x}$, each client $i$ performs $\tau_i$ local steps (in parallel):

\begin{align}\label{eqn:update1:fedout}
\m{x}_{i,\nu +1} = \m{x}_{i,\nu }-\alpha_i\m{h}_{i,\nu },
\end{align}

and then the server aggregates local models via $\m{x}^+=|\mc{S}|^{-1} \sum_{i\in \mc{S}} \m{x}_{i,\tau_i}$. Here, $\alpha_i \in (0,\alpha]$ is the local stepsize,

\begin{equation}\label{eqn:hyper:estim}
\begin{aligned}
\m{h}_{i,\nu }:=&\m{h}^{\texttt{I}}(\m{x},\m{y}^{+})+  \m{h}^{\texttt{D}}(\m{x},\m{y}^{+})\\
&-\m{h}_i^{\texttt{D}}(\m{x},\m{y}^{+})+\m{h}_i^{\texttt{D}}(\m{x}_{i,\nu },\m{y}^{+})\,,
\end{aligned}
\end{equation}

$\m{h}^{\texttt{I}}(\m{x},\m{y}) := |\mc{S}|^{-1}\sum_{i\in\mathcal{S}} \m{h}_i^{\texttt{I}} (\m{x},\m{y})$, and $\m{h}^{\texttt{D}}(\m{x},\m{y}) := |\mc{S}|^{-1}\sum_{i\in\mathcal{S}} \m{h}_i^{\texttt{D}} (\m{x},\m{y})$.

The key features of updates (<ref>)–(<ref>) are exploiting past gradients (variance reduction) to account for objective heterogeneity. Indeed,

the ideal update in would perform the update $\m{x}_{i,\nu +1} =\m{x}_{i,\nu }-\alpha_i\big(\m{h}^{\texttt{I}}(\m{x}_{i,\nu },\m{y}^{+})+ \m{h}^{\texttt{D}}(\m{x}_{i,\nu },\m{y}^{+})\big)$ using the global gradient estimates. But this requires each client $i$ to have access to both direct and indirect gradients of all other clients–which it does not, since clients do not communicate between rounds. To overcome this issue, each client $i$ uses global gradient estimates, i.e., $ \m{h}^{\texttt{I}}(\m{x},\m{y}^{+})+\m{h}^{\texttt{D}}(\m{x},\m{y}^{+})$ from the beginning of each round as a guiding direction in its local update rule. However, since both $\m{h}^{\texttt{D}}$ and $\m{h}^{\texttt{I}}$ are computed at a previous  $(\m{x},\m{y}^{+})$, client $i$ makes a correction by subtracting off the stale direct gradient estimate $\m{h}_i^{\texttt{D}}(\m{x},\m{y}^{+})$ and adding its own local estimate $\m{h}_i^{\texttt{D}}(\m{x}_{i,\nu },\m{y}^{+})$. Our local update rule in Step 11 of Algorithm <ref> is precisely of this form, i.e.,  $\m{h}_{i,\nu }$ approximates

$\m{h}^{\texttt{I}}(\m{x}_{i,\nu },\m{y}^{+})+ \m{h}^{\texttt{D}}(\m{x}_{i,\nu },\m{y}^{+})$

via (<ref>). Note here that the described local correction of only applies to the direct gradient component (the indirect component would require global Hessian information). An alterantive approach leading to is discussed in Section <ref>.

applied to special nested problems. Algorithm <ref> naturally allows the use of other optimizers for minimax & compositional optimization. For example, in the minimax problem (<ref>), the bilevel gradient components are $\nabla^{\texttt{D}} f_i(\m{x},\m{y}^*(\m{x}))=\nabla_{\m{x}}f_i\left(\m{x},\m{y}^*(\m{x})\right)$ and $\nabla^{\texttt{I}} f_i(\m{x},\m{y}^*(\m{x}))=0$ for all $i \in\mc{S}$. Hence, the hypergradient estimate (<ref>) reduces to

\begin{equation}\label{eqn:hyper:estim:minmax}
\m{h}_{i,\nu } = \m{h}^{\texttt{D}}(\m{x},\m{y}^{+})-\m{h}_i^{\texttt{D}}(\m{x},\m{y}^{+})+\m{h}_i^{\texttt{D}}(\m{x}_{i,\nu },\m{y}^{+}).
\end{equation}

For the compositional problem (<ref>), Hessian becomes the identity matrix, the direct gradient is the zero vector, and  $\nabla_{\m{xy}}g(\m{x},\m{y})=- (1/m)\sum_{i=1}^m\nabla \m{r}_i(\m{x})^{\top}$. Hence, $\m{h}_i= \ell_{g,1}\nabla  \m{r}_i(\m{x})^{\top} \m{p}_{0}$ for all $i \in\mc{S}$.

More details on these special cases are provided in Appendices <ref> and <ref>.

Indirect gradient estimation & . Here, we aim to address one of the key challenges in nested FL: inverse Hessian gradient product.  Note from (<ref>) that the proposed stochastic approximation of the indirect gradient involves in a nonlinear way the global Hessian, which is not available at the client. To get around this, we use a client sampling strategy and recursive reformulation of (<ref>) so that $\bar{\nabla}^{\texttt{I}}f_i(\m{x},\m{y})$ can be estimated in an efficient federated manner. In particular, given $N \in \mb{N}$, we select $N' \in \{0 \ldots, N-1\}$ and $\mc{S}_0, \ldots, \mc{S}_{ N'} \in \mc{S}$ UAR. For all $i \in \mc{S}$, we then define

\begin{equation}\label{eq:grad:est}
\begin{aligned}
&\m{h}^{\texttt{I}}_i(\m{x},\m{y}) =-\nabla^2_{\m{xy}}g_i(\m{x},\m{y};\zeta_{i}) \m{p}_{N'},
\end{aligned}
\end{equation}

where $\m{p}_{N'}=|\mc{S}_0|^{-1}\wh{\m{H}}_\m{y} \sum_{i\in\mc{S}_0} \nabla_\m{y} f_i(\m{x}, \m{y};\xi_{i,0})$ and $\wh{\m{H}}_\m{y}$ is the approximate inverse Hessian:

\begin{align}
\frac{ N}{\ell_{g,1}} \prod_{n=1}^{N'} \Big (\m{I} - \frac{1}{ \ell_{g,1}  |\mc{S}_n|} \sum_{i=1}^{|\mc{S}_n|} \nabla_{\m{y}}^2 g_i(\m{x},\m{y}; \zeta_{i,n}) \Big).
\label{eq:hessinv:est}
\end{align}

The subroutine provides a recursive strategy to compute $\m{p}_{N'}$  and multiplies $\m{p}_{N'}$
with the Jacobian to drive an indirect gradient estimate. Importantly, these approximations require only matrix-vector products and vector communications.

Under Assumptions <ref> and <ref>, the approximate inverse Hessian $\wh{\m{H}}_\m{y}$ defined in (<ref>) satisfies the following for any $\x$ and $\y$:

\begin{align}
\nonumber
\left\|\left[\nabla^2_{\m{y}} g (\m{x}, \m{y})\right]^{-1} - \mb{E}_{\mc{W}}[\wh{\m{H}}_{\m{y}}]\right\| &\le \frac{1}{\mu_g} \left(\frac{\kappa_g-1}{\kappa_g} \right)^N,\\
\mb{E}_{\mc{W}}\left[\left\|\left[\nabla^{2}_{\m{y}} g (\m{x}, \m{y})\right]^{-1}-\wh{\m{H}}_{\m{y}}\right\|\right] &\le \frac{2}{\mu_g}. \label{Hessian_Invs_ineq}
\end{align}

Here, $\mc{W}:=\left\{\mc{S}_n, \xi_{i},\zeta_{i}, \xi_{i,0}, \zeta_{i,n} \mid i \in \mc{S}_n, ~~~0\leq n\leq  N' \right\}$. Further, for all $~i \in \mc{S}$, $\m{h}_i^{\texttt{I}}(\m{x},\m{y})$ defined in (<ref>) satisfies

\begin{align}
\left\| \mb{E}_{\mc{W}} \left[\m{h}_i^{\texttt{I}}(\m{x},\m{y})\right]- \bar{\nabla}^{\texttt{I}} f_i(\m{x},\m{y}) \right\|&\leq b,
\end{align}

where $b:= \kappa_g\ell_{f,1}\big( (\kappa_g-1)/\kappa_g \big)^{N}$.

§.§ Inner Optimizer:

In FL, each client performs multiple local training steps in isolation on its own data (using for example SGD) before communicating with the server. Due to such local steps, suffers from a client-drift effect under objective heterogeneity; that is, the local iterates of each client drift-off towards the minimum of their own local function. In turn, this can  lead to convergence to a point different from the  global optimum $\y^*(\x)$ of the inner problem; e.g., see <cit.>. This behavior is particularly undesirable in a nested optimization setting since it directly affects the outer optimization; see, e.g. <cit.>.

In light of this observation, we build on the recently proposed FedLin <cit.> which improves FedSVRG <cit.> to solve the inner problem; see Algorithm <ref>. For each $i\in \mc{S}$, let  $\m{q}_i(\m{x}, \m{y})$ denote an unbiased estimate of the gradient $\nabla_{\m{y}} g_i(\m{x},\m{y})$. In each round, starting from a common global model $\m{y}$, each client $i$ performs $\tau_i$ local SVRG-type training steps in parallel:

$\m{y}_{i,\nu +1} = \m{y}_{i,\nu }-\beta_i\m{q}_{i,\nu },$

where $\m{q}_{i,\nu }:= \m{q}_i(\m{x},\m{y}_{i,\nu })-\m{q}_i(\m{x},\m{y})+\m{q}(\m{x},\m{y})$, $\beta_i \in (0,\beta]$ is the local inner stepsize, and $\m{q}(\m{x},\m{y}) := |\mc{S}|^{-1}\sum_{i\in\mathcal{S}} \m{q}_i(\m{x},\m{y})$. We note that for the optimization problems (<ref>), (<ref>), and (<ref>), $\m{q}_i(\m{x},\m{y}_{i,\nu })$ is equal to $\nabla_\m{y} g_i(\m{x}, \m{y}_{i,\nu };\zeta_{i,\nu })$, $-\nabla_\m{y} f_i(\m{x}, \m{y}_{i,\nu };\xi_{i,\nu })$, and $\m{y}_{i,\nu }-\m{r}_i(\m{x};\zeta_{i,\nu })$, respectively; see  Appendices <ref>–<ref>.

§.§ Light-: Communication Efficiency via Local Hypergradients

Each epoch $k$ requires $2T+N+3$ communication rounds as follows: $2T$ rounds for SVRG of ,

$N$ iterations for inverse Hessian approximation within and $3$ additional aggregations. Note that, these are vector communications and we fully avoid Hessian communication.

In Appendix <ref>, we also propose simplified variants of and , which are tailored to homogeneous or  high-dimensional FL settings. These algorithms can then either use local Jacobian / inverse Hessian or their approximation, and can use either SVRG or SGD.

Light-: Specifically, we propose where each client runs IHGP locally.  This reduces the number of rounds to $T+1$, saving $T+N+2$ rounds (see experiments in Section <ref> for performance comparison and Appendix <ref> for further discussion.)

§ CONVERGENCE ANALYSIS FOR

In this section, we present convergence results for . All proofs are relegated to Appendices <ref>–<ref>.

Suppose Assumptions <ref> and <ref> hold.  Further, assume  $\alpha_i^k=\alpha_k/\tau_i$ and $\beta_i^k=\beta_k/\tau_i$ for all $ i \in \mathcal{S}$, where

\begin{align}\label{eqn:param:choice}
%&\tau_i\geq 1,\forall i\in\mc{S},~~~\beta_i=\frac{{\beta}_k}{\tau_i},~~\textnormal{where}~~
\beta_k &= \frac{\bar{\beta} \alpha_k}{T},~~~\alpha_k=\min\left\{\bar{\alpha}_1, \bar{\alpha}_2, \bar{\alpha}_3, \frac{\bar{\alpha}}{\sqrt{K}}\right\}
\end{align}

for some positive constants $\bar\alpha_1,\bar\alpha_2,\bar\alpha_3,\bar{\alpha}$, and $\bar{\beta}$ independent of $K$. Then, for any $T\geq 1$, the iterates $\{(\m{x}^k,\m{y}^k)\}_{k\geq0}$ generated by satisfy

\begin{equation*}
\begin{aligned}%\label{eq.theorem1}
\frac{1}{K} \sum_{k=1}^K\mb{E}\left[\left\|\nabla f(\m{x}^k)\right\|^2\right] =~&{\cal O}\Big(\frac{\bar{\alpha}\max(\sigma_{g,1}^2, \sigma_{g,2}^2,\sigma_f^2)}{\sqrt{K}} \\
& + \frac{1}{\min(\bar{\alpha}_1, \bar{\alpha}_2, \bar{\alpha}_3)K} + b^2 \Big),
\end{aligned}
\end{equation*}

where  $b=\kappa_g\ell_{f,1}\big( (\kappa_g-1)/\kappa_g \big)^{N}$ and $N$ is the input parameter to .

Under the same conditions as in Theorem <ref>,  if
$N={\cal O}(\kappa_g \log K)$ and $T=\mc{O}(\kappa_g^{4})$, then

\begin{equation*}
\frac{1}{K} \sum_{k=1}^K\mb{E}\left[\left\|\nabla f(\m{x}^k)\right\|^2\right]= \mc{O}\left(\frac{\kappa_g^4}{K} + \frac{\kappa_g^{2.5}}{\sqrt{K}}\right).
\end{equation*}

For $\epsilon$-accurate stationary point, we need $K=\mc{O}(\kappa^5_g \epsilon^{-2})$.

Above, we choose $N\propto \kappa_g \log K$ to guarantee $b^2\lesssim 1/\sqrt{K}$. In contrast, we use $T\gtrsim\kappa_g^4$ inner SVRG epochs. From Section <ref>, this would imply the communication cost is dominated by SVRG epochs $N$ and $\order{\kappa_g^4}$ rounds.

From Corollary <ref>, we remark that matches the guarantees of non-federated alternating SGD methods, such as ALSET <cit.> and  BSA <cit.>, despite federated setting, i.e. communication challenge, heterogeneity in the client objectives, and device heterogeneity.

at (0,0) ;
at (0,-2.1) [scale=0.9]FedNest epochs;
at (-2.6,0) [scale=0.9, rotate=90]Test accuracy;

Comparison between FedNest and LFedNest.

at (0,0) ;
at (0,-2.1) [scale=0.9]Communication rounds;

SVRG in provides better convergence and stability.

at (0,0) ;
at (0,-2.1) [scale=0.9]Communication rounds;

Larger $\tau$ in provides better performance.

Hyper-representation experiments on a 2-layer MLP and MNIST dataset.

§.§ Minimax Federated Learning

We focus on special features of federated minimax problems and customize the general results to yield improved convergence results for this special case. Recall from (<ref>) that $g_i(\x,\y)=-f_i(\x,\y)$ which implies that $b=0$ and following Assumption <ref>,  $f_i(\x,\y)$ is $\mu_f$–strongly concave in $\y$ for all $\x$.

Denote $\kappa_f=\ell_{f,1}/\mu_f$. Assume same conditions as in Theorem <ref>  and

$T=\mc{O}(\kappa_f)$. Then,

\begin{equation*}
\frac{1}{K} \sum_{k=1}^K\mb{E}\left[\left\|\nabla f(\m{x}^k)\right\|^2\right]=\mc{O}\left(\frac{\kappa^2_f}{K} + \frac{\kappa_f}{\sqrt{K}}\right).
\end{equation*}

Corrollary <ref> implies that for the minimax problem, the convergence rate of to the stationary point of $f$ is  $\mc{O}({1/\sqrt{K}})$. Again, we note this matches the convergence rate of non-FL algorithms (see also Table <ref>) such as SGDA <cit.> and SMD <cit.>.

§.§ Compositional Federated Learning

Observe that in the compositional problem (<ref>), the outer function is $f_i(\m{x},\m{y};\xi)=f_i(\m{y};\xi)$ and the inner function is  $g_i(\m{x},\m{y};\zeta)=\frac{1}{2}\|\m{y}-\m{r}_i(\m{x};\zeta)\|^2$, for all $i \in \mc{S}$. Hence, $b=0$ and $\kappa_g=1$.

Under the same conditions as in Theorem <ref>, if we select $T=1$ in (<ref>). Then,

\begin{equation*}
\frac{1}{K} \sum_{k=1}^K\mb{E}\left[\left\|\nabla f(\m{x}^k)\right\|^2\right]=\mc{O}\left(\frac{1}{\sqrt{K}}\right).
\end{equation*}

Corrollary <ref> implies that for the  compositional problem (<ref>), the convergence rate of to the stationary point of $f$ is  $\mc{O}({1/\sqrt{K}})$. This matches the convergence rate of non-federated stochastic algorithms such as SCGD <cit.> and NASA <cit.> (Table <ref>).

§.§ Single-Level Federated Learning

Building upon the general results for stochastic nonconvex nested problems, we establish new convergence guarantees for single-level stochastic non-convex federated SVRG which is integrated within our .  Note that in the single-level setting,  the optimization problem (<ref>) reduces to

\begin{align}\label{fedsingle:prob2}
\underset{\m{x} \in \mb{R}^{{d}_1}}{\min} ~~f(\m{x})=\frac{1}{m} \sum_{i=1}^{m} f_{i}\left(\m{x}\right)
\end{align}

with $f_i(\m{x}) := \mb{E}_{\xi \sim \mc{C}_i}[f_i(\m{x}; \xi)]$, where  $\xi\sim\mc{C}_i$ is sampling distribution for the $i^{\text{th}}$ client.

We make the following assumptions on (<ref>) that are counterparts of Assumptions <ref> and <ref>.
[Lipschitz continuity]
For all $i \in [m]$, $\nabla f_i(\m{x})$ is $L_f$-Lipschitz continuous.

[Stochastic samples]
For all $i \in [m]$, $\nabla f_i(\m{x};\xi)$ is an unbiased estimator of $\nabla f_i(\m{x})$ and its variance is bounded, i.e., $\mb{E}_{\xi}[\|\nabla f_i(\m{x};\xi)-\nabla f_i(\m{x})\|^2] \leq \sigma_f^2$.

Suppose Assumptions <ref> and <ref> hold.  Further, assume  $\alpha_i^k=\alpha_k/\tau_i$ for all $ i \in \mathcal{S}$, where

\begin{align}\label{eqn:param:s:choice}
\alpha_k&=\min\left\{\bar{\alpha}_1,\frac{\bar{\alpha}}{\sqrt{K}}\right\}
\end{align}

for some positive $\bar{\alpha}_1$ and  $\bar{\alpha}$. Then,

\begin{equation*}
\frac{1}{K} \sum_{k=1}^K\mb{E}\left[\left\|\nabla f(\m{x}^k)\right\|^2\right]=\mc{O}\left( \frac{ \Delta_f}{ \bar{\alpha}_1 K} + \frac{  \frac{\Delta_f}{\bar{\alpha}} + \bar{\alpha}\sigma_f^2 }{\sqrt{K}}\right),
\end{equation*}

where $\Delta_{f}:= f(\m{x}^0)-\mb{E}[f(\m{x}^K)]$.

Theorem <ref> extends recent results by <cit.> from the stochastic strongly convex to the stochastic nonconvex setting. The above rate is also consistent with existing single-level non-FL guarantees <cit.>.

§ NUMERICAL EXPERIMENTS

In this section, we numerically investigate the impact of several attributes of our algorithms on a hyper-representation problem <cit.>, a hyper-parameter optimization problem for loss function tuning <cit.>, and a federated minimax optimization problem.

§.§ Hyper-Representation Learning

Modern approaches in meta learning such as MAML <cit.> and reptile <cit.> learn representations (that are shared across all tasks) in a bilevel manner. Similarly, the hyper-representation problem optimizes a classification model in a two-phased process. The outer objective optimizes the model backbone to obtain better feature representation on validation data. The inner problem optimizes a header for downstream classification tasks on training data. In this experiment, we use a 2-layer multilayer perceptron (MLP) with 200 hidden units. The outer problem optimizes the hidden layer with 157,000 parameters, and the inner problem optimizes the output layer with 2,010 parameters. We study both i.i.d and non-i.i.d. ways of partitioning the MNIST data exactly following FedAvg <cit.>, and split each client's data evenly to train and validation datasets. Thus, each client has 300 train and 300 validation samples.

Figure <ref> demonstrates the impact on test accuracy of  several important components of . Figure <ref> compares $\fednest$ and $\lfedblo$. Both algorithms perform well on the i.i.d. setup, while on the non-i.i.d. setup, $\fednest$ achieves i.i.d. performance, significantly outperforming $\lfedblo$. These findings are in line with our discussions in Section <ref>. $\lfedblo$ saves on communication rounds compared to $\fednest$ and performs well on homogeneous clients. However, for heterogeneous clients, the isolation of local Hessian in $\lfedblo$ (see Algorithm <ref> in Appendix <ref>) degrades the test performance.  Next, Figure <ref> demonstrates the importance of SVRG in $\fedinn$ algorithm for heterogeneous data (as predicted by our theoretical considerations in Section <ref>). To further clarify the algorithm difference in Figures <ref> and <ref>, we use $\fednest_\mathrm{SGD}$ to denote the algorithm where SGD is used in . Finally, Figure <ref> elucidates the role of local epoch $\tau$ in $\fedout$: larger $\tau$ saves on communication and improves test performance by enabling faster convergence.

at (0,0) ;
at (0,-1.65) [scale=0.7]FedNest epochs;
at (-2,0) [scale=0.7, rotate=90]Balanced Test Accuracy;

FedNest achieves similar performance as non-federated bilevel loss function tuning.

at (0,0) ;
at (0,-1.65) [scale=0.7]Communication rounds;

SVRG in $\fedinn$ provides better convergence and stability especially in non-iid setup.

Loss function tuning on a 3-layer MLP and imbalanced MNIST dataset to maximize class-balanced test accuracy. The brown dashed line is the accuracy on non-federated bilevel optimization <cit.>, and the black dashed line is the accuracy without tuning the loss function.

§.§ Loss Function Tuning on Imbalanced Dataset

We use bilevel optimization to tune a loss function for learning an imbalanced MNIST dataset. We aim to maximize the class-balanced validation accuracy (which helps minority/tail classes). Following the problem formulation in <cit.>, we tune the so-called VS-loss function <cit.> in a federated setting. In particular, we first create a long-tail imbalanced MNIST dataset by exponentially decreasing the number of examples per class (e.g. class 0 has 6,000 samples, class 1 has 3,597 samples and finally, class 9 has only 60 samples). We partition the dataset to 100 clients following again $\fedavg$ <cit.> on both i.i.d. and non-i.i.d. setups. Different from the hyper-representation experiment, we employ 80%-20% train-validation on each client and use a 3-layer MLP model with 200, 100 hidden units, respectively. It is worth noting that, in this problem, the outer objective $f$ (aka validation cost) only depends on the hyperparameter $\m{x}$ through the optimal model parameters $\y^*(\x)$; thus, the direct gradient $\nabla^{\texttt{D}} f_i(\m{x},\m{y}^*(\m{x}))$ is zero for all $i \in\mc{S}$.

Figure <ref> displays test accuracy vs epochs/rounds for our federated bilevel algorithms. The horizontal dashed lines serve as non-FL baselines: brown depicts accuracy reached by bilevel optimization in non-FL setting, and, black depicts accuracy without any loss tuning. Compared to these, Figure <ref> shows that $\fednest$ achieves near non-federated performance. In Figure <ref>, we investigate the key role of SVRG in $\fedinn$ by comparing it with possible alternative implementation that uses SGD-type updates. The figure confirms our discussion in Section <ref>: SVRG offers significant performance gains that are pronounced by client heterogeneity.

§.§ Federated Minimax Problem

at (0,0) ;
at (0,-1.45) [scale=0.7]Epoch;
at (-2,0) [scale=0.7, rotate=90]$\|\y-\y^*\|^2$;

at (0,0) ;
at (0,-1.45) [scale=0.7]Epoch;
at (-2,0) [scale=0.7, rotate=90]$\|\x-\x^*\|^2$;

FedNest converges linearly despite heterogeneity. LFedNest slightly outperforms FedAvg-S.

We conduct experiments on the minimax problem (<ref>) with
\[
f_i(\m{x},\m{y}):=-\left[\frac{1}{2}\|\m{y}\|^2 - \m{b}_i^\top \m{y} + \m{y}^\top \m{A}_i \m{x}\right] + \frac{\lambda}{2} \|\m{x}\|^2,
\]

to compare standard FedAvg saddle-point (FedAvg-S) method updating $(\m{x},\m{y})$ simultaneously <cit.> and our alternative approaches (LFedNest and FedNest). This is a saddle-point formulation of $\min_{\m{x} \in \mb{R}^{d_1}} \frac{1}{2} \|\frac{1}{m} \sum_{i=1}^m \m{A}_i \m{x} - \m{b}_i\|^2$.
We set  $\lambda=10$, $\m{b}_i=\m{b}_i' - \frac{1}{m}\sum_{i=1}^m \m{b}_i'$ and $\m{A}_i = t_i \m{I}$, where $\m{b}_i' \sim \mathcal{N}(0, s^2 I_d)$, and $t_i$ is drawn UAR over $(0,0.1)$. Figure <ref> shows that LFedNest and FedNest outperform FedAvg-S thanks to their alternating nature. FedNest significantly improves the convergence of LFedNest due to controlling client-drift. To our knowledge, FedNest is the only alternating federated SVRG for minimax problems.

§ RELATED WORK

Federated learning. was first introduced by <cit.>, who showed it can dramatically reduce communication costs. For identical clients, coincides with local SGD <cit.> which has been analyzed by many works <cit.>. Recently, many variants of have been proposed to tackle issues such as convergence and client drift. Examples include FedProx <cit.>, <cit.>,  FedSplit <cit.>, FedNova <cit.>, and, the most closely relevant to us FedLin <cit.>. A few recent studies are also devoted to the extension of to the minimax optimization <cit.> and compositional optimization <cit.>. In contrast to these methods, makes alternating SVRG updates between the global variables $\m{x}$ and $\m{y}$, and yields sample complexity bounds and batch size choices that are on par with the non-FL guarantees (Table <ref>). Evaluations in the Appendix <ref> reveal that both alternating updates and SVRG provides a performance boost over these prior approaches.

Bilevel optimization. This class of problems was first introduced by <cit.>, and since then, different types of approaches have been proposed. See <cit.> for surveys.
Earlier works in <cit.> reduced the bilevel problem to a single-level optimization problem. However, the reduced problem is still difficult to solve due to for example a large number of constraints. Recently, more efficient gradient-based  algorithms have been proposed by estimating the hypergradient of $\nabla f(\m{x})$ through iterative updates <cit.>. The asymptotic and  non-asymptotic analysis of bilevel optimization has been provided in <cit.> and <cit.>, respectively. There is also a line of work focusing on minimax optimization <cit.> and compositional optimization <cit.>. Closely related to our work are <cit.> and <cit.> which provide non-asymptotic analysis of SGD-type methods for minimax and compositional problems with outer nonconvex objective, respectively.

A more in-depth discussion of related work is given in Appendix <ref>. We summarize the complexities of different methods for FL/non-FL bilevel optimization in Table <ref>.

§ CONCLUSIONS

We presented a new class of federated algorithms for solving general nested stochastic optimization spanning bilevel and  problems. runs a variant of federated SVRG on inner & outer variables in an alternating fashion. We established provable convergence rates for under arbitrary client heterogeneity and introduced variations for min-max and compositional problems and for improved communication efficiency (). We showed that, to achieve an $\epsilon$-stationary point of the nested problem, requires $O(\epsilon^{-2})$ samples in total, which matches the complexity of the non-federated nested algorithms in the literature.

§ ACKNOWLEDGEMENTS

Davoud Ataee Tarzanagh was supported by ARO YIP award W911NF1910027 and NSF CAREER award CCF-1845076. Christos Thrampoulidis was supported by NSF Grant Numbers CCF-2009030 and HDR-1934641, and an NSERC Discovery Grant. Mingchen Li and Samet Oymak were supported by the NSF CAREER award CCF-2046816, Google Research Scholar award, and ARO grant W911NF2110312.

: Federated , , and Compositional Optimization
The appendix is organized as follows: Section <ref> introduces the algorithm. Section <ref> discusses the related work. We provide all details for the proof of the  main theorems in Sections <ref>, <ref>, <ref>, and <ref> for federated bilevel, , compositional, and single-level optimization, respectively. In Section <ref>, we state a few auxiliary technical lemmas. Finally, in Section <ref>, we provide the detailed parameters of our numerical experiments (Section <ref>) and then introduce further experiments.