text:
\section{Preliminaries and Useful Lemmas}

In this section, we provide preliminary and useful results in order to prove Theorems \ref{Thm: PL-PL convergence} and \ref{Thm: nonconvex-PL convergence}. For notational convenience, we use  the following short-hand notations:

\begin{table}[h!]
\begin{center}
    \begin{tabular}{ c c }
    \toprule
    Notation & Description  \\
    \midrule
    $\displaystyle \bpsi^i_t = \left( \Lambda^i_t \, , \, \delta^i_t \right)$
    & maximization variables of node $i$ iteration $t$  \\
    $\displaystyle \Psi_t
    = \left( \bpsi^1_t \,;\, \cdots \, ; \, \bpsi^n_t \right)$
    &
    \begin{tabular}{@{}c@{}}concatenation of all nodes' maximization \\ models at iteration $t$ \end{tabular}  \\
    $\displaystyle \wbar_t = \frac{1}{n} \sum_{i \in [n]} \w^i_t$
    & average model at iteration $t$ \vspace{0cm}\\
    $\displaystyle a_t = \E [ \Phi(\wbar_t) ] - \Phi^*$ & \begin{tabular}{@{}c@{}}optimality gap measure \\ between $\Phi(\wbar_t)$ and $\min_{\w} \Phi(\w)$ \end{tabular}  \vspace{0.2cm}\\
    $\displaystyle b_t = \E [ \Phi(\wbar_t) - f(\wbar_t, \Psi_t)]$ & \begin{tabular}{@{}c@{}}optimality gap measure \\ between $f(\wbar_t, \Psi_t)$ and $\max_{\Psi} f(\wbar_t, \Psi)$ \end{tabular} \vspace{0.2cm}\\
    $\displaystyle e_t = \frac{1}{n} \sum_{i \in [n]} \E \norm{\w^i_t - \wbar_{t}}^2 $ & \begin{tabular}{@{}c@{}}average deviation of the local models  \\ from the average model at iteration $t$ \end{tabular} \\
    $\displaystyle g_t
    = \E \norm{\frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2$  & \begin{tabular}{@{}c@{}}norm squared of  \\ local gradients w.r.t $\w$ at iteration $t$ \end{tabular} \\
    $\displaystyle h_t
    = \E \norm{\gr \Phi(\wbar_{t}) - \frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2$ & \begin{tabular}{@{}c@{}}norm squared of deviation in gradients w.r.t $\w$ \\ of $\max_{\Psi} f(\wbar_t, \Psi)$ and local functions $f^i(\w^i_t , \bpsi^i_t)$ \end{tabular}\\
    \bottomrule
    \end{tabular}
    \vspace{1mm}
    \caption{Table of notations.}
    \label{Table: Notations}
\end{center}
\end{table}

Now, we present a set of useful lemmas and observations which we will invoke to prove the convergence results for both PL-PL and nonconvex-PL loss cases. The following lemma establishes the Lipschitz gradient parameter for the global function given those of the local objectives.

\begin{lemma} \label{Lemma: f Lipschitz}
If the local functions $f^i$s have Lipschits gradients with parameters stated in Assumption \ref{assumption:smooth}, then the global function $f$ has also Lipschitz gradients as follows: for any $\w, \w', \Psi, \Psi'$ it holds that
\begin{gather}
    \norm{\grw f(\w, \Psi) \! - \! \grw f(\w', \Psi)}
    \leq
    L_1 \norm{\w \! - \! \w'}, \,
    \norm{\grw f(\w, \Psi) \! - \! \grw f(\w, \Psi')}
    \leq
    \frac{L_{12}}{\sqrt{n}} \norm{\Psi \! - \! \Psi'}_F, \\
    \norm{\grPsi f(\w, \Psi) \! - \! \grPsi f(\w', \Psi)}_F
    \leq
    \frac{L_{21}}{\sqrt{n}} \norm{\w \! - \! \w'}, \,
    \norm{\grPsi f(\w, \Psi) \! - \! \grPsi f(\w, \Psi')}_F
    \leq
    \frac{L_2}{n} \norm{\Psi \! - \! \Psi'}_F.
\end{gather}
\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof Lemma: f Lipschitz}.
\end{proof}

Recall the definition of the function $\Phi(\cdot)$, that is,

\begin{align}
    \Phi(\w)
    \coloneqq
    \max_{\Psi} f(\w, \Psi)
    =
    \max_{\bpsi^1, \cdots, \bpsi^n} \frac{1}{n} \sum_{i \in [n]} f^i(\w,\bpsi^i)
    =
    \max_{(\Lambda^1, \delta^1), \cdots, (\Lambda^n, \delta^n)} \frac{1}{n} \sum_{i \in [n]} f^i(\w,\Lambda^i, \delta^i).
\end{align}

Next lemma shows that $\Phi$ has Lipschitz gradients and characterizes its parameter.

\begin{lemma}[\cite{nouiehed2019solving}] \label{lemma:L_Phi}
If Assumptions \ref{assumption:smooth} and \ref{assumption:PL} (ii) hold, that is, the local objectives have Lipschitz gradients and $-f(\w, \cdot)$ is $\mu_2$-PL, then we have

\begin{align}
    \gr \Phi(\w)
    =
    \grw f(\w, \Psi^*(\w)),
\end{align}

where $\Psi^*(\w) \in \argmax_{\Psi} f(\w, \Psi)$ for any $\w$. Moreover, $\Phi$ has Lipschitz gradients with parameter $L_{\Phi} = L_1 + \frac{L_{12} L_{21}}{2n\mu_2}$.
\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof lemma:L_Phi}.
\end{proof}

Next lemma shows the contraction of the sequence $\{\E [ \Phi(\wbar_t) ]\}_{t \geq 0}$ when running the update rule of \texttt{FedRobust} method in Algorithm \ref{Alg: FedRobust}. Please refer to Table \ref{Table: Notations} to recall the definition of $h_t$ and $g_t$.

\begin{lemma} \label{Lemma: Phi contraction}
If Assumptions \ref{assumption:stoch-gradients} and \ref{assumption:smooth} hold, then the iterates of {\normalfont \texttt{FedRobust}} satisfy the following contraction inequality for any iteration $t \geq 0$

\begin{align}
    \E [ \Phi(\wbar_{t+1}) ] - \E [ \Phi(\wbar_{t}) ]
    \leq
    - \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1}{2} h_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L_{\Phi} \right) g_t
    +
    \eta_1^2 \frac{L_{\Phi}}{2} \frac{\sigmaw}{n}.
\end{align}

\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof Lemma: Phi contraction}.
\end{proof}

Next lemma further bounds $h_t$ w.r.t. the two sequences $b_t$ and $e_t$.

\begin{lemma} \label{Lemma: h_t bound}
If Assumptions \ref{assumption:smooth} and \ref{assumption:PL} (ii) hold, that is, the local objectives have Lipschitz gradients and $-f(\w, \cdot)$ is $\mu_2$-PL, then we have

\begin{align} \label{eq:h_t-final}
    h_t
    \leq
    \frac{4 L_{12}^2}{\mu_2 n} b_t
    +
    2 L_1^2 e_t.
\end{align}

\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof Lemma: h_t bound}.
\end{proof}

Next lemma establishes a contraction bound on the sequence $b_t$.

\begin{lemma} \label{Lemma: b_t contraction}
If Assumptions \ref{assumption:stoch-gradients}, \ref{assumption:smooth} and \ref{assumption:PL} (ii) hold, then the sequence of $\{b_t\}_{t \geq 0}$ generated by the {\normalfont \texttt{FedRobust}} iterations with $\eta_2 \leq 1/L_2$ satisfies the following contraction bound:

\begin{align}  \label{eq:b_t-final}
    b_{t+1}
    &\leq
    (1 - \mu_2 \eta_2 n) \left( 1 + \eta_1 \frac{4 L_{12}^2}{\mu_2 n} \right) b_t
    +
    \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) g_t \\
    &\quad +
    \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) e_t
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{2} L_2 \sigmapsi,
\end{align}

where $L_{\Phi}$ is the Lipschitz gradient parameter of the function $\Phi(\cdot)$ characterized in Lemma \ref{lemma:L_Phi}.
\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof Lemma: b_t contraction}.
\end{proof}

Next lemma bounds $e_t$, that is the average deviation of local parameter models from their average.

\begin{lemma} \label{lemma:e_t g_l bound}
If Assumptions \ref{assumption:bounded-degree}, \ref{assumption:stoch-gradients} and \ref{assumption:smooth} hold and the step-size $\eta_1$ satisfies $32 \eta_1^2 (\tau - 1)^2 L_1^2 \leq 1$, then the sequence $e_t = \frac{1}{n} \sum_{i \in [n]} \E \norm{\w^i_t - \wbar_{t}}^2$ is bounded as follows

\begin{align}
    e_{t}
    &\leq
    16 \eta_1^2 (\tau - 1)^2 \rho^2
    +
    4 \eta_1^2 (\tau - 1) (n+1) \frac{\sigmaw}{n}
    +
    20 \eta_1^2 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l,
\end{align}

where $t_c$ denotes the index of the most recent server-worker communication, i.e. $t_c = \floor*{\frac{t}{\tau}} \tau$ and we also denote $\rho^2 \coloneqq 3\rho_f^2 + 6 L_{12}^2 (\epsilon_1^2 + \epsilon_2^2)$.
\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof lemma:e_t g_l bound}.
\end{proof}

Next generic lemma is adopted form \cite{haddadpour2019convergence}.

\begin{lemma} \label{lemma:elimination}
Assume that two non-negative sequences $\{P_t\}_{t \geq 0}$ and $\{g_t\}_{t \geq 0}$ satisfy the following inequality for each iteration $t \geq 0$ and some constants $0 < \Upsilon < 1$, $L \geq 0$, $B \geq 0$, and $\Gamma \geq 0$:

\begin{align}
    P_{t+1}
    &\leq
    \Upsilon P_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L \right) g_t
    +
    \eta_1^2 B \sum_{l=t_c+1}^{t-1} g_l
    +
    \Gamma,
\end{align}

where $t_c = \floor*{\frac{t}{\tau}} \tau$. Then, for each $t \geq 0$ we have

\begin{align}
    P_{t}
    &\leq
    \Upsilon^t P_0
    +
    \frac{\Gamma}{1 - \Upsilon},
\end{align}

if $\eta_1$ satisfies the following condition

\begin{align}
    \eta_1 \left( L + \frac{2B}{\Upsilon^{\tau-1} (1 - \Upsilon)} \right) \leq 1.
\end{align}

\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof lemma:elimination}.
\end{proof}

Next lemma bounds the overall optimality gap $b_t$ averaged over $T$ iterations.

\begin{lemma} \label{lemma: sum b_t}
If Assumptions \ref{assumption:stoch-gradients}, \ref{assumption:smooth} and \ref{assumption:PL} (ii) hold and the step-sizes satisfy the conditions $\eta_2 \leq 1/{L_2}$ and $\frac{\eta_2}{\eta_1} \geq \frac{8 L_{12}^2}{\mu_2^2 n^2}$, then the average of the sequence  $\{b_t\}_{t = 0}^{T-1}$ generated from the {\normalfont \texttt{FedRobust}} can be bounded as follows:

\begin{align}
    \frac{1}{T} \sum_{t=0}^{T-1} b_{t}
    &\leq
    \frac{4 L_{2}^2}{\mu_2^2 n^2} \frac{\epsilon_1^2 + \epsilon_2^2}{\eta_2 T}
    +
    \frac{\eta_1}{\eta_2} \frac{1}{\mu_2 n} \frac{1}{T} \sum_{t=0}^{T-1} \E \norm{\gr \Phi(\wbar_{t})}^2 \\
    &\quad +
    \frac{\eta_1^2}{\eta_2} \frac{1}{\mu_2 n} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{1}{T} \sum_{t=0}^{T-1} g_{t}
    +
    \frac{1}{\eta_2} \frac{2}{\mu_2 n} \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) \frac{1}{T} \sum_{t=0}^{T-1} e_{t} \\
    &\quad +
    \frac{\eta_1^2}{\eta_2} \frac{1}{\mu_2 n} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \eta_2 \frac{L_2}{\mu_2 n} \sigmapsi,
\end{align}

where $L_{\Phi}$ is the Lipschitz gradient parameter of the function $\Phi(\cdot)$ characterized in Lemma \ref{lemma:L_Phi} and $\epsilon_1, \epsilon_2$ represent the radius of the affine perturbation balls, i.e. $\Vert \Lambda^i - I \Vert \leq \epsilon_1$ and $\Vert \delta^i \Vert \leq \epsilon_2$ for each node $i \in [n]$.
\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof lemma: sum b_t}.
\end{proof}

Next lemma bounds the averaged local model deviations $e_t$ over $T$ iterations.

\begin{lemma}\label{lemma: sum e_t}
If Assumptions \ref{assumption:bounded-degree}, \ref{assumption:stoch-gradients} and \ref{assumption:smooth} hold and the step-size $\eta_1$ satisfies $32 \eta_1^2 (\tau - 1)^2 L_1^2 \leq 1$, then the average of the sequence $e_t$ over $t=0,\cdots,T-1$ is bounded as follows

\begin{align}
    \frac{1}{T} \sum_{t=0}^{T-1} e_{t}
    &\leq
    20 \eta_1^2 (\tau - 1)^2 \frac{1}{T} \sum_{t=0}^{T-1} g_t
    +
    16 \eta_1^2 (\tau - 1)^2 \rho^2
    +
    8 \eta_1^2 (\tau - 1) (n+1) \frac{\sigmaw}{n}.
\end{align}

\end{lemma}

\begin{proof}
We defer the proof to Section \ref{proof lemma: sum e_t}.
\end{proof}

\section{Proof of Theorem \ref{Thm: PL-PL convergence}} \label{proof: Thm PL-PL}
Having established the key lemmas, now we proceed to prove Theorem \ref{Thm: PL-PL convergence} for any $\beta \leq 1/2$. To show the convergence of the sequence $P_t = a_t + \beta b_t$, we firstly need to establish a contraction inequality on $P_{t+1}$ with respect to $P_t$. We begin by the following bound on the sequence $a_t = \E [ \Phi(\wbar_t) ] - \Phi^*$ which is directly implied from Lemma \ref{Lemma: Phi contraction}:

\begin{align} \label{eq: Theorem PL-PL 1}
    a_{t+1}
    \leq
    a_t
    - \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1}{2} h_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L_{\Phi} \right) g_t
    +
    \eta_1^2 \frac{L_{\Phi}}{2} \frac{\sigmaw}{n}.
\end{align}

Using Lemma \ref{Lemma: h_t bound} that shows $h_t \leq 4 L_{12}^2 b_t / (\mu_2 n) + 2 L_1^2 e_t$, the bound in \eqref{eq: Theorem PL-PL 1} yields that

\begin{align} \label{eq: Theorem PL-PL 2}
    a_{t+1}
    \leq
    a_t
    - \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \eta_1 \frac{2 L_{12}^2}{\mu_2 n} b_t
    +
    \eta_1 L_1^2 e_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L_{\Phi} \right) g_t
    +
    \eta_1^2 \frac{L_{\Phi}}{2} \frac{\sigmaw}{n}.
\end{align}

Next, we employ the result of Lemma \ref{Lemma: b_t contraction} which establishes a contraction bound on the $b_t$ sequence. Putting together with \eqref{eq: Theorem PL-PL 2} implies that

\begin{align} \label{eq: Theorem PL-PL 3}
    P_{t+1}
    &=
    a_{t+1} + \beta b_{t+1} \\
    &\leq
    a_t
    -
    \frac{\eta_1}{2} \left( 1 - \beta \right) \E \norm{\gr \Phi(\wbar_{t})}^2 \\
    &\quad +
    \beta \left( \eta_1 \frac{2 L_{12}^2}{\beta \mu_2 n} + (1 - \mu_2 \eta_2 n) \left( 1 + \eta_1 \frac{4 L_{12}^2}{\mu_2 n} \right)\right) b_t \\
    &\quad -
    \left( \frac{\eta_1}{2} \left( 1 - \eta_1 L_{\Phi} \right) - \eta_1^2 \frac{\beta}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \right) g_t \\
    &\quad +
    \left( \eta_1 L_1^2 + \beta \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) \right) e_t \\
    &\quad +
    \frac{\eta_1^2}{2} \left( L_{\Phi} + \beta \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \right) \frac{\sigmaw}{n}
    +
    \eta_2^2 L_2 \frac{\beta}{2} \sigmapsi.
\end{align}

We begin simplifying the above bound by first considering the first two terms in RHS of \eqref{eq: Theorem PL-PL 3}. We can show that the function $\Phi(\cdot)$ is $\mu_1$-PL \citep{yang2020global}, which implies that

\begin{align}
    \E \norm{\gr \Phi(\wbar_{t})}^2
    \geq
    2\mu_1 \E [\Phi(\wbar_t) ] - \Phi^* = 2 \mu_1 a_t.
\end{align}

Therefore, for any $\beta \leq 1/2$ we have

\begin{align}
    a_t
    -
    \frac{\eta_1}{2} \left( 1 - \beta \right) \E \norm{\gr \Phi(\wbar_{t})}^2
    \leq
    \left( 1 - \frac{1}{2} \mu_1 \eta_1 \right) a_t,
\end{align}

which implies the coefficient of $a_t$ in \eqref{eq: Theorem PL-PL 3} is bounded by $1 - \frac{1}{2} \mu_1 \eta_1$. Next, the coefficient of $\beta b_t$ in \eqref{eq: Theorem PL-PL 3} can be bounded as follows:

\begin{align}
    \eta_1 \frac{2 L_{12}^2}{\beta \mu_2 n} + (1 - \mu_2 \eta_2 n) \left( 1 + \eta_1 \frac{4 L_{12}^2}{\mu_2 n} \right)
    &=
    1 - \eta_1 \frac{L_1 L_2}{\mu_2 n} \left( \frac{\mu^2_2 \eta_2 n}{\eta_1 L_1 L_2} - \frac{2 L_{21}^2}{\beta L_1 L_2} - 4 (1 - \mu_2 \eta_2 n) \frac{L_{21}^2}{L_1 L_2} \right) \\
    &\stackrel{(a)}{\leq}
    1 - \eta_1 \frac{L_1 L_2}{\mu_2 n} \\
    &\stackrel{(b)}{\leq}
    1 - \frac{1}{2} \mu_1 \eta_1,
\end{align}

where $(a)$ holds for our choice of $\beta$ and assuming $\frac{\mu^2_2 \eta_2 n}{\eta_1 L_1 L_2} \geq 1 + (4+\frac{2}{\beta})\frac{L_{12}^2}{L_1 L_2}$ and $(b)$ is implies from the fact that

\begin{align}
    \frac{\eta_1 \frac{L_1 L_2}{\mu_2 n}}{\frac{1}{2} \mu_1 \eta_1}
    =
    2 \left( \frac{L_1}{\mu_1} \right) \left( \frac{L_2}{\mu_2 n} \right)
    \geq 1.
\end{align}

Now that we have bounded the coefficients of $a_t$ and $\beta b_t$ in \eqref{eq: Theorem PL-PL 3}, rearranging the terms and using the assumption $\eta_2 \leq 1/{L_2}$ simplifies the contraction on $P_t$ as follows

\begin{align} \label{eq: Theorem PL-PL 4}
    P_{t+1}
    &\leq
    \left( 1 - \frac{1}{2} \mu_1 \eta_1 \right) P_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 \hat{L}_{\beta} \right) g_t
    +
    \tilde{L}_{\beta} e_t
    +
    \eta_1^2 \frac{\hat{L}_{\beta}}{2} \frac{\sigmaw}{n}
    +
    \eta_2^2 \frac{L_2}{2} \beta \sigmapsi,
\end{align}

where we picked the following notations for convenient of the exposition

\begin{gather}
    \tilde{L}_{\beta} = (1 + \beta) \eta_1 L_1^2 + \beta  \eta_2 L_{21}^2, \quad
    \hat{L}_{\beta} =  (1 + \beta) L_{\Phi} + \beta L_1 + 2 \beta \frac{L_{21}^2}{L_2}.
\end{gather}

Next, we use Lemma \ref{lemma:e_t g_l bound} which for $32 \eta_1^2 (\tau - 1)^2 L_1^2 \leq 1$ provides an upper bound on $e_t$ with respect to $g_t$. We can write

\begin{align} \label{eq: Theorem PL-PL 5}
    P_{t+1}
    &\leq
    \left( 1 - \frac{1}{2} \mu_1 \eta_1 \right) P_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 \hat{L}_{\beta} \right) g_t
    +
    20 \eta_1^2 \tilde{L}_{\beta} (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l \\
    &\quad +
    16 \eta_1^2 \tilde{L}_{\beta} (\tau - 1)^2 \rho^2
    +
    4 \eta_1^2 \tilde{L}_{\beta} (\tau - 1) (n+1) \frac{\sigmaw}{n}
    +
    \eta_1^2 \frac{\hat{L}_{\beta}}{2} \frac{\sigmaw}{n}
    +
    \eta_2^2 \frac{L_2}{2} \beta \sigmapsi.
\end{align}

We have shown in Lemma \ref{lemma:elimination} that how a such contraction sequence converges. In particular, let us pick the following notations and apply the result of Lemma \ref{lemma:elimination} to contraction in \eqref{eq: Theorem PL-PL 5}

\begin{align}
    L
    &=
    \hat{L}_{\beta}, \\
    \Upsilon
    &=
    1 - \frac{1}{2} \mu_1 \eta_1, \\
    B
    &=
    20 \tilde{L}_{\beta} (\tau - 1),  \\
    \Gamma
    &=
    16 \eta_1^2 \tilde{L}_{\beta} (\tau - 1)^2 \rho^2
    +
    4 \eta_1^2 \tilde{L}_{\beta} (\tau - 1) (n+1) \frac{\sigmaw}{n}
    +
    \eta_1^2 \frac{\hat{L}_{\beta}}{2} \frac{\sigmaw}{n}
    +
    \eta_2^2 \frac{L_2}{2} \beta \sigmapsi.
\end{align}

It implies that if the step-sizes satisfy the following condition

\begin{gather} \label{eq: condition eta_1 1}
    \eta_1 \left( \hat{L}_{\beta}  + \frac{80  \tilde{L}_{\beta} (\tau - 1)}{\eta_1 \mu_1 \left( 1 - \frac{1}{2} \mu_1 \eta_1 \right)^{\tau-1}} \right)
    \leq
    1,
\end{gather}

then we have

\begin{align}
    P_{t}
    &\leq
    \left( 1 - \frac{1}{2} \mu_1 \eta_1 \right)^t P_0
    +
    32 \eta_1 \frac{\tilde{L}_{\beta}}{\mu_1} (\tau - 1)^2 \rho^2
    +
    8 \eta_1 \frac{\tilde{L}_{\beta}}{\mu_1}  (\tau - 1) (n + 1) \frac{\sigmaw}{n}
    +
    \eta_1 \frac{\hat{L}_{\beta}}{\mu_1} \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{\eta_1} \frac{L_2}{\mu_1} \beta \sigmapsi,
\end{align}

which concludes the proof of Theorem \ref{Thm: PL-PL convergence}. Note to hold this result, in addition to condition \eqref{eq: condition eta_1 1}, we have assumed the following constraints on the step-sizes as well

\begin{gather}
    \eta_2 L_2 \leq 1, \quad
    32 \eta_1^2 (\tau - 1)^2 L_1^2
    \leq
    1, \quad
    \frac{\mu^2_2 \eta_2 n}{\eta_1 L_1 L_2}
    \geq
    1 + \left( 4 + \frac{2}{\beta} \right) \frac{L_{12}^2}{L_1 L_2}.
\end{gather}

\section{Proof of Theorem \ref{Thm: nonconvex-PL convergence}} \label{appendix: proof of Thm nonconvex-PL}
We begin the proof by combining the results of Lemmas \ref{Lemma: Phi contraction} and \ref{Lemma: h_t bound} which yields that for every iteration $t = 0, \cdots, T-1$ we have

\begin{align} \label{eq: Theorem nonconvex-PL 1}
    \E \Phi(\wbar_{t+1}) - \E \Phi(\wbar_t)
    &\leq
    -
    \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_t)}^2
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L_{\Phi} \right) g_t
    +
    \eta_1 \frac{2 L_{12}^2}{\mu_2 n} b_t
    +
    \eta_1 L_1^2 e_t
    +
    \eta_1^2 \frac{L_{\Phi}}{2} \frac{\sigmaw}{n}.
\end{align}

Summing up all the $T$ inequalities in \eqref{eq: Theorem nonconvex-PL 1} for $t = 0, \cdots, T-1$ and dividing by $T$ yields the following

\begin{align}
    \frac{1}{T} \left( \E \Phi(\wbar_{T}) - \Phi(\wbar_0) \right)
    &\leq
    -
    \frac{\eta_1}{2} \frac{1}{T} \sum_{t=0}^{T-1} \E \norm{\gr \Phi(\wbar_{t})}^2 \\
    &\quad -
    \frac{\eta_1}{2} \left(1 - \eta_1 L_{\Phi} \right) \frac{1}{T} \sum_{t=0}^{T-1} g_{t}\\
    &\quad +
    \eta_1 \frac{2 L_{12}^2}{\mu_2 n} \frac{1}{T} \sum_{t=0}^{T-1} b_t \\
    &\quad +
    \eta_1 L_1^2 \frac{1}{T} \sum_{t=0}^{T-1} e_{t} \\
    &\quad +
    \eta_1^2 \frac{L_{\Phi}}{2} \frac{\sigmaw}{n}.
\end{align}

Next we use Lemmas \ref{lemma: sum b_t} and then Lemma \ref{lemma: sum e_t} to replace the terms $\frac{1}{T} \sum_{t=0}^{T-1} b_{t}$ and $\frac{1}{T} \sum_{t=0}^{T-1} e_{t}$ and rewrite the above bound in terms of $\frac{1}{T} \sum_{t=0}^{T-1} g_{t}$. It yields that

\begin{align}
    \frac{1}{T} \left( \E \Phi(\wbar_{T}) - \Phi(\wbar_0) \right)
    &\leq
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 \frac{4 L_{12}^2 L_2}{\mu^2_2 n^2} \right) \frac{1}{T} \sum_{t=0}^{T-1} \norm{\gr \Phi(\wbar_{t})}^2 \\
    &\quad -
    \frac{\eta_1}{2} \left(1 - \eta_1 \left( \hat{L}  + 40 \tilde{L} (\tau - 1)^2 \right) \right) \frac{1}{T} \sum_{t=0}^{T-1} g_{t}\\
    &\quad +
    \frac{\eta_1}{\eta_2} \frac{8 L_{12}^2 L_2^2}{\mu_2^3 n^3}\frac{ \epsilon_1^2 + \epsilon_2^2}{T}
    +
    16 \eta_1^2 \tilde{L} (\tau - 1)^2 \rho^2
    +
    \frac{\eta_1^2}{2} \hat{L} \frac{\sigmaw}{n}
    +
    \eta_1 \eta_2 \frac{4 L_{12}^2}{\mu_2^2 n^2} \hat{L} \sigmapsi,
\end{align}

where we adopt the following short-hand notations

\begin{gather}
    \tilde{L} = \frac{3}{2} \eta_1 L_1^2 + \frac{1}{2}  \eta_2 L_{21}^2, \quad
    \hat{L} =  \frac{3}{2} L_{\Phi} + \frac{1}{2} L_1 + \frac{L_{21}^2}{L_2}.
\end{gather}

Finally, we use the assumption $\eta_1 ( \hat{L}  + 40 \tilde{L} (\tau - 1)^2 ) \leq 1$ to remove the term $\frac{1}{T} \sum_{t=0}^{T-1} g_{t}$ and apply $\frac{\eta_1}{\eta_2} \leq \frac{\mu_2^2 n^2}{8 L_{12}^2}$ to simply the bound and conclude the proof:

\begin{align}
    \frac{1}{T} \sum_{t=0}^{T-1} \E \norm{\gr \Phi(\wbar_{t})}^2
    &\leq
    \frac{4 \Delta_{\Phi}}{\eta_1 T}
    +
    \frac{4 L_2^2}{\mu_2^2 n^2}\frac{ \epsilon_1^2 + \epsilon_2^2}{\eta_1 T}
    +
    64 \eta_1 \tilde{L} (\tau - 1)^2 \rho^2 \\
    &\quad +
    16 \eta_1 \tilde{L}  (\tau - 1) (n + 1) \frac{\sigmaw}{n}
    +
    2 \eta_1 \hat{L} \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{\eta_1} L_2 \sigmapsi.
\end{align}

\section{Proof of Useful Lemmas}

\subsection{Proof of Lemma \ref{Lemma: f Lipschitz}} \label{proof Lemma: f Lipschitz}
Proof of all four cases in the claim is simple. We derive the proof for the fourth one as an instance. Recall definition of the global function $f$, that is

\begin{align}
    f(\w, \Psi)
    =
    \frac{1}{n} \sum_{i \in [n]} f^i(\w,\bpsi^i).
\end{align}

Therefore, the gradient of $f$ with respect to $\Psi$ is

\begin{align}
    \grPsi f(\w, \Psi)
    =
    \begin{pmatrix}
        \frac{\partial}{\partial \bpsi^1} f(\w, \Psi)\\
        \vdots \\
        \frac{\partial}{\partial \bpsi^n} f(\w, \Psi)
    \end{pmatrix}
    =
    \frac{1}{n}
    \begin{pmatrix}
        \grpsi f^1(\w, \bpsi^1)\\
        \vdots \\
        \grpsi f^n(\w, \bpsi^n)
    \end{pmatrix}.
\end{align}

We can then write for any $\w, \Psi=(\bpsi^1; \cdots; \bpsi^n), \Psi'=({\bpsi'}^1; \cdots;{\bpsi'}^n)$ and using Assumption \ref{assumption:smooth} that
\begin{align}
    \norm{\grPsi f(\w, \Psi) \! - \! \grPsi f(\w, \Psi')}^2_F
    &=
    \frac{1}{n^2} \sum_{i \in [n]} \norm{\grpsi f^i(\w, \bpsi^i) - \grpsi f^i(\w, {\bpsi'}^i)}^2_F \\
    &\leq
    \frac{L_2^2}{n^2} \sum_{i \in [n]} \norm{\bpsi^i - {\bpsi'}^i}^2_F \\
    &=
    \frac{L_2^2}{n^2} \norm{\Psi \! - \! \Psi'}^2_F.
\end{align}

\subsection{Proof of Lemma \ref{lemma:L_Phi}} \label{proof lemma:L_Phi}
The detailed proof can be found in \cite{nouiehed2019solving}, Lemma A.5. Note that in our case, according to Lemma \ref{Lemma: f Lipschitz} the function $f$ has Lipschitz gradients with constants $L_1, L_{12}/\sqrt{n}, L_{21}/\sqrt{n}, L_2/n$; implying the Lipschitz gradient parameter of the function $\Phi$ to be
\begin{align}
    L_{\Phi} = L_1 + \frac{(L_{12}/\sqrt{n}) (L_{21}/\sqrt{n})}{2 \mu_2} = L_1 + \frac{L_{12} L_{21}}{2n \mu_2}.
\end{align}

\subsection{Proof of Lemma \ref{Lemma: Phi contraction}} \label{proof Lemma: Phi contraction}
We invoke Lemma \ref{lemma:L_Phi} which shows that the gradient of the function $\Phi(\cdot)$ is $L_{\Phi}$-Lipschitz. We can write

\begin{align} \label{eq: Phi contraction 1}
    \Phi(\wbar_{t+1}) - \Phi(\wbar_{t})
    &\leq
    \left \langle \gr \Phi(\wbar_{t}) , \wbar_{t+1} - \wbar_{t} \right \rangle
    +
    \frac{L_{\Phi}}{2} \norm{\wbar_{t+1} - \wbar_{t}}^2 \\
    &=
    -\eta_1 \left \langle \gr \Phi(\wbar_{t}), \frac{1}{n} \sum_{i \in [n]} \sgrw f^i(w^i_t , \bpsi^i_t) \right \rangle
    +
    \eta_1^2 \frac{L_{\Phi}}{2} \norm{\frac{1}{n} \sum_{i \in [n]} \sgrw f^i(w^i_t , \bpsi^i_t)}^2 ,
\end{align}

where we use the update rule of \texttt{FedRobust} and note that the difference of averaged models can be written as $\wbar_{t+1} - \wbar_{t} = -\eta_1 \frac{1}{n} \sum_{i \in [n]} \sgrw f^i(w^i_t , \bpsi^i_t)$. Moreover, since the stochastic gradients $\sgrw f^i$ are unbiased and variance-bounded by $\sigmaw$, we can take expectation from both sides of \eqref{eq: Phi contraction 1} and further simplify it as follows

\begin{align}
    \E [\Phi(\wbar_{t+1}) - \E [\Phi(\wbar_{t})]
    \leq
    - \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1}{2} h_t
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L_{\Phi} \right) g_t
    +
    \eta_1^2 \frac{L_{\Phi}}{2} \frac{\sigmaw}{n}.
\end{align}

In above, we used the inequality $ 2 \langle \bba, \bbb \rangle = \Vert \bba \Vert^2 + \Vert \bbb \Vert^2 - \Vert \bba - \bbb \Vert^2$ as well as the notations for $g_t$ and $h_t$ as defined in Table \ref{Table: Notations}.

\subsection{Proof of Lemma \ref{Lemma: h_t bound}} \label{proof Lemma: h_t bound}
We begin bounding $h_t$ by adding/subtracting the term $\grw f(\wbar_t, \Psi_t)$ and use the inequality $\Vert \bba + \bbb \Vert^2 \leq 2\Vert \bba \Vert^2 + 2\Vert \bbb \Vert^2$ to write

\begin{align} \label{eq: h_t 1}
    h_t
    &=
    \E \norm{\gr \Phi(\wbar_{t}) - \frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2 \\
    &\leq
    2 \E \norm{\gr \Phi(\wbar_{t}) - \grw f(\wbar_t, \Psi_t)}^2
    +
    2 \E \norm{\grw f(\wbar_t, \Psi_t) - \frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2.
\end{align}

The first term in RHS of \eqref{eq: h_t 1} can be bounded as follows:

\begin{align}  \label{eq: h_t 2}
    \E \norm{\gr \Phi(\wbar_t) - \grw f(\wbar_t, \Psi_t)}^2
    &=
    \E \norm{\grw f(\wbar_t, \Psi^*(\wbar_t)) - \grw f(\wbar_t, \Psi_t)}^2 \\
    &\stackrel{(a)}{\leq}
    \frac{L_{12}^2}{n} \E \norm{\Psi^*(\wbar_t) - \Psi_t}^2_F \\
    &\stackrel{(b)}{\leq}
    \frac{2 L_{12}^2}{\mu_2 n} \E \left[ \Phi(\wbar_{t}) - f(\wbar_{t}, \Psi_{t}) \right] \\
    &\stackrel{(c)}{=}
    \frac{2 L_{12}^2}{\mu_2 n} b_t.
\end{align}

In above and to derive $(a)$, we employ the result of Lemma \ref{Lemma: f Lipschitz} which shows that given Assumption \ref{assumption:smooth}, the gradient function $\grw f(\w, \cdot)$ is $L_{12}/\sqrt{n}$ Lipschitz. To derive $(b)$, we use Assumption \ref{assumption:PL} (ii) and lastly, $(c)$ is implied from the definition of $b_t$. The second term in RHS of \eqref{eq: h_t 1} can be bounded by noting that the local gradients $\grw f^i(\cdot, \bpsi^i)$ are $L_1$-Lipschitz, which we can write

\begin{align} \label{eq: h_t 3}
    \E \norm{\grw f(\wbar_t, \Psi_t) - \frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2
    &=
    \E \norm{\frac{1}{n} \sum_{i \in [n]} \grw f^i(\wbar_t , \bpsi^i_t) - \frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2 \\
    &\leq
    \frac{L_1^2}{n} \sum_{i \in [n]} \E \norm{\w^i_t - \wbar_{t}}^2 \\
    &=
    L_1^2 e_t.
\end{align}

Finally, plugging \eqref{eq: h_t 2} and \eqref{eq: h_t 3} back in \eqref{eq: h_t 1} implies the claim of the lemma, that is

\begin{align} \label{eq:h_t-final}
    h_t
    \leq
    \frac{4 L_{12}^2}{\mu_2 n} b_t
    +
    2 L_1^2 e_t.
\end{align}

\subsection{Proof of Lemma \ref{Lemma: b_t contraction}} \label{proof Lemma: b_t contraction}
We begin the proof by noting the definition of $b_t$ and use the fact that the gradients $\grPsi f(\w, \cdot)$ are $\frac{L_2}{n}$-Lipschitz (Refer to Lemma \ref{Lemma: f Lipschitz}). We can accordingly write

\begin{align} \label{eq:b_t bound 1}
    \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t+1})
    &\leq
    \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t})
    -
    \langle \gr_{\Psi} f(\wbar_{t+1}, \Psi_{t}) , \Psi_{t+1} - \Psi_{t} \rangle \\
    &\quad +
    \frac{L_2}{2n} \norm{\Psi_{t+1} - \Psi_{t}}^2_F.
\end{align}

In this work, we define the inner product for any two matrices $A,B$ as follows

\begin{align}
    \langle A , B \rangle \coloneqq \operatorname{Tr} (A^\top B).
\end{align}

Note that according to the ascent update rule of \texttt{FedRobust} in Algorithm \ref{Alg: FedRobust}, we can write

\begin{align}
    \Psi_{t+1} - \Psi_{t} = \eta_2 \tilde{\partial}_t f,
\end{align}

where we adopt the following short-hand notation for the stochastic gradients at iteration $t$ with respect to the maximization variables $\bpsi^i_t = (\Lambda^i_t, \delta^i_t)$

\begin{align}
    \tilde{\partial}_t f
    =
    \begin{pmatrix}
        \sgrpsi f^1(\w^1_t, \bpsi^1_t)\\
        \vdots \\
        \sgrpsi f^n(\w^n_t, \bpsi^n_t)
    \end{pmatrix}
    =
    \begin{pmatrix}
        \sgr_{\Lambda} f^1(\w^1_t, \Lambda^1_t, \delta^1_t)
        &
        \sgr_{\delta} f^1(\w^1_t, \Lambda^1_t, \delta^1_t)\\
        \vdots & \vdots\\
        \sgr_{\Lambda} f^n(\w^n_t, \Lambda^n_t, \delta^n_t)
        &
        \sgr_{\delta} f^n(\w^n_t, \Lambda^n_t, \delta^n_t)
    \end{pmatrix}.
\end{align}

We also denote the gradients by $\partial_t f = \E [\tilde{\partial}_t f]$ where the expectation is with respect to the randomness in stochastic gradients $\sgrpsi f^i$. According to Assumption \ref{assumption:stoch-gradients}, each of the local stochastic gradients $\sgrpsi f^i(\w^i_t, \bpsi^i_t)$ are variance-bounded by $\sigmapsi$. Therefore, we can bound the variance of $\tilde{\partial}_t f$ as $\E \Vert \tilde{\partial}_t f - \partial_t f \Vert_F^2 \leq n \sigmapsi$. Now, we can plug these back in \eqref{eq:b_t bound 1} which implies

\begin{align} \label{eq:b_t bound 2}
    \Phi(\wbar_{t+1}) - \E f(\wbar_{t+1}, \Psi_{t+1})
    &\leq
    \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t})
    -
    \eta_2 \frac{n}{2} \norm{\gr_{\Psi} f(\wbar_{t+1}, \Psi_{t})}^2_F + \eta_2^2 \frac{L_2}{2} \sigmapsi\\
    &\quad +
    \eta_2 \frac{n}{2} \norm{\gr_{\Psi} f(\wbar_{t+1}, \Psi_{t}) - \frac{1}{n} \partial_t f}^2_F
    -
    \frac{\eta_2}{2n} \left( 1 - \eta_2 L_2 \right)
    \norm{\partial_t f}^2_F,
\end{align}

where the expectation is with respect to the randomness of the stochastic gradients $\tilde{\partial}_t f$ while conditioning on all the randomness history. Now recall from Assumption \ref{assumption:PL} (ii) that $- f(\wbar_{t+1}, \cdot)$ is $\mu_2$-PL implying that $\Vert \gr_{\Psi} f(\wbar_{t+1}, \Psi_{t}) \Vert^2_F \geq 2 \mu_2 (\Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t}))$. Moreover, assume that $\eta_2 \leq 1/L_2$ to remove the last term in \eqref{eq:b_t bound 2}. Putting altogether implies that

\begin{align} \label{eq:b_t bound 3}
    \Phi(\wbar_{t+1}) - \E f(\wbar_{t+1}, \Psi_{t+1})
    &\leq
    (1 - \mu_2 \eta_2 n) \left( \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t}) \right)
    +
    \eta_2^2 \frac{L_2}{2} \sigmapsi\\
    &\quad +
    \eta_2 \frac{n}{2} \norm{\gr_{\Psi} f(\wbar_{t+1}, \Psi_{t}) - \frac{1}{n} \partial_t f}^2_F.
\end{align}

Next, we continue to bound the last term in RHS of \eqref{eq:b_t bound 3}. We can write

\begin{align} \label{eq:b_t bound 4}
    \norm{\gr_{\Psi} f(\wbar_{t+1}, \Psi_{t}) - \frac{1}{n} \partial_t f}^2_F
    &=
    \frac{1}{n^2} \sum_{i \in [n]} \norm{\grpsi f^i(\wbar_{t+1}, \bpsi^i_t) - \grpsi f^i(\w^i_t, \bpsi^i_t)}^2_F \\
    &\leq
    \frac{L_{21}^2}{n^2} \sum_{i \in [n]} \norm{\wbar_{t+1} - \w^i_t}^2 \\
    &\leq
    \frac{2 L_{21}^2}{n^2} \sum_{i \in [n]} \norm{\w^i_t - \wbar_{t}}^2
    +
    \frac{2 L_{21}^2}{n} \norm{\wbar_{t+1} - \wbar_{t}}^2,
\end{align}

where the first inequality above uses Assumption \ref{assumption:smooth} on Lipschitz continuity of local gradients and the second inequality simply uses the inequality $\Vert \bba + \bbb \Vert^2 \leq 2\Vert \bba \Vert^2 + 2\Vert \bbb \Vert^2$. Next, let us bound the term $\Vert \wbar_{t+1} - \wbar_{t} \Vert^2$ in expectation as follows. Using the descent update rule in Algorithm \ref{Alg: FedRobust} and considering Assumption \ref{assumption:stoch-gradients} on variance of the stochastic gradients $\sgrw f^i$ we can write

\begin{align} \label{eq:b_t bound 5}
    \E \norm{\wbar_{t+1} - \wbar_{t}}^2
    &=
    \eta_1^2 \E \norm{\frac{1}{n} \sum_{i \in [n]} \sgrw f^i(\w^i_t , \bpsi^i_t)}^2 \\
    &\leq
    \eta_1^2 \E \norm{\frac{1}{n} \sum_{i \in [n]} \grw f^i(\w^i_t , \bpsi^i_t)}^2
    +
    \eta_1^2 \frac{\sigmaw}{n} \\
    &=
    \eta_1^2 g_t + \eta_1^2 \frac{\sigmaw}{n},
\end{align}

where we use the short-hand notation of $g_t$ also listed in Table \ref{Table: Notations}. Plugging \eqref{eq:b_t bound 5} back in \eqref{eq:b_t bound 4} and noting the notation $e_t = \frac{1}{n} \sum_{i \in [n]} \E \norm{\w^i_t - \wbar_{t}}^2$ implies that

\begin{align} \label{eq:b_t bound 6}
    \E \norm{\gr_{\Psi} f(\wbar_{t+1}, \Psi_{t}) - \frac{1}{n} \partial_t f}^2_F
    &\leq
    \frac{2 L_{21}^2}{n} e_t
    +
    \eta_1^2 \frac{2 L_{21}^2}{n} g_t
    +
    \eta_1^2 \frac{2 L_{21}^2}{n} \frac{\sigmaw}{n}.
\end{align}

Before proceeding to bound more terms, let us recall what we have shown till this point. We plug \eqref{eq:b_t bound 6} back in \eqref{eq:b_t bound 3}, take the expectation with respect to all the sources of randomness and use the notation $ b_t = \E [ \Phi(\wbar_t) - f(\wbar_t, \Psi_t)]$ to conclude

\begin{align} \label{eq: b_t bound 8}
    b_{t+1}
    &\leq
    (1 - \mu_2 \eta_2 n) \E \left[ \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t}) \right] \\
    &\quad +
    \eta_2 L_{21}^2 e_t
    +
    \eta_1^2 \eta_2 L_{21}^2 g_t
     +
    \eta_1^2 \eta_2 L_{21}^2 \frac{\sigmaw}{n}
    +
    \eta_2^2 \frac{L_2}{2} \sigmapsi.
\end{align}

To bound the term $\E \left[ \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t}) \right]$, we can decompose it to the following three terms:

\begin{align} \label{eq:decompose1}
    \Phi(\wbar_{t+1}) - f(\wbar_{t+1}, \Psi_{t})
    &=
    \Phi(\wbar_{t}) - f(\wbar_{t}, \Psi_{t}) + f(\wbar_{t}, \Psi_{t}) - f(\wbar_{t+1}, \Psi_{t}) + \Phi(\wbar_{t+1}) - \Phi(\wbar_{t}).
\end{align}

Given the Lipschitz gradient assumption for the local functions in Assumption \ref{assumption:smooth} and using Lemma \ref{Lemma: f Lipschitz} on Lipschitz gradient for the global function, we can write

\begin{align} \label{eq: b_t bound 7}
    f(\wbar_{t}, \Psi_{t}) - f(\wbar_{t+1}, \Psi_{t})
    \leq
    - \langle \grw f(\wbar_t, \Psi_t), \wbar_{t+1} - \wbar_{t} \rangle
    +
    \frac{L_1}{2} \norm{\wbar_{t+1} - \wbar_{t}}^2,
\end{align}

where $\wbar_{t+1} - \wbar_{t} = - \eta_1 \frac{1}{n} \sum_{i \in [n]} \sgrw f^i(\w^i_t , \bpsi^i_t)$. Taking expectation from both sides of \eqref{eq: b_t bound 7} implies that

\begin{align} \label{eq:decompose2}
    \E \left[ f(\wbar_{t}, \Psi_{t}) - f(\wbar_{t+1}, \Psi_{t}) \right]
    &\stackrel{(a)}{\leq}
    \eta_1 \E \norm{\grw f(\wbar_t, \Psi_t) - \gr \Phi(\wbar_t)}^2
    +
    \eta_1 \E \norm{\gr \Phi(\wbar_t)}^2 \\
    &\quad +
    \left( \frac{\eta_1}{2} + \eta_1^2 \frac{L_1}{2} \right) g_t
    +
    \eta_1^2 \frac{L_1}{2} \frac{\sigmaw}{n} \\
    &\stackrel{(b)}{\leq}
    \eta_1 \frac{2 L_{12}^2}{\mu_2 n} b_t
    +
    \eta_1 \E \norm{\gr \Phi(\wbar_t)}^2
    +
    \left( \frac{\eta_1}{2} + \eta_1^2 \frac{L_1}{2} \right) g_t
    +
    \eta_1^2 \frac{L_1}{2} \frac{\sigmaw}{n},
\end{align}

where in inequality $(a)$ we use the inequality $2 \langle \bba, \bbb \rangle \leq \norm{\bba}^2 + \norm{\bbb}^2$ and also the result in \eqref{eq:b_t bound 5}. To derive $(b)$, we use Assumptions \ref{assumption:smooth} and \ref{assumption:PL} (ii), result of Lemma \ref{Lemma: f Lipschitz} and the notation $ b_t = \E [ \Phi(\wbar_t) - f(\wbar_t, \Psi_t)]$  to write

\begin{align}
    \E \norm{\gr \Phi(\wbar_t) - \grw f(\wbar_t, \Psi_t)}^2
    &=
    \E \norm{\grw f(\wbar_t, \Psi^*(\wbar_t)) - \grw f(\wbar_t, \Psi_t)}^2 \\
    &\leq
    \frac{L_{12}^2}{n} \E \norm{\Psi^*(\wbar_t) - \Psi_t}^2_F \\
    &\leq
    \frac{2 L_{12}^2}{\mu_2 n} \E \left[ \Phi(\wbar_{t}) - f(\wbar_{t}, \Psi_{t}) \right] \\
    &=
    \frac{2 L_{12}^2}{\mu_2 n} b_t.
\end{align}

We now have all the ingredients to conclude the claim of Lemma \ref{Lemma: b_t contraction}. To do so, we combine the result of Lemma \ref{Lemma: Phi contraction} which bounds the term $\E [\Phi(\wbar_{t+1})] - \E [\Phi(\wbar_{t})]$, Lemma \ref{Lemma: h_t bound} that shows $h_t \leq 4 L_{12}^2 b_t / (\mu_2 n) + 2 L_1^2 e_t$, and the bound \eqref{eq:decompose2}; plug back in \eqref{eq:decompose1} and then in \eqref{eq: b_t bound 8} and conclude the claim of the lemma, that is

\begin{align}
    b_{t+1}
    &\leq
    (1 - \mu_2 \eta_2 n) \left( 1 + \eta_1 \frac{4 L_{12}^2}{\mu_2 n} \right) b_t
    +
    \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) g_t \\
    &\quad +
    \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) e_t
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{2} L_2 \sigmapsi,
\end{align}

\subsection{Proof of Lemma \ref{lemma:e_t g_l bound}} \label{proof lemma:e_t g_l bound}
To prove this lemma, we first need to establish an intermediate step, which is stated in the following.

\begin{prop} \label{prop:e-t}
If Assumptions \ref{assumption:bounded-degree}, \ref{assumption:stoch-gradients} and \ref{assumption:smooth} hold, then

\begin{align}
    e_{t}
    &\leq
    16 \eta_1^2 (\tau - 1) L_1^2 \sum_{l=t_c+1}^{t-1} e_l
    +
    10 \eta_1^2 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
    +
    8 \eta_1^2 (\tau - 1)^2 \rho^2
    +
    4 \eta_1^2 (\tau - 1) (n+1) \frac{\sigmaw}{n}.
\end{align}

\end{prop}

\begin{proof}[Proof of Proposition \ref{prop:e-t}]
Consider an iteration $t \geq 1$ and let $t_c$ denote the index of the most recent communication between the workers and the server, i.e. $t_c = \floor*{\frac{t}{\tau}} \tau$. Therefore, all the workers share the same local minimization model at iteration $t_c + 1$, i.e. $\w^1_{t_c+1}=\cdots=\w^n_{t_c+1}=\wbar_{t_c+1}$. According to the update rule of \texttt{FedRobust}, we can write for each node $i$ that

\begin{align} \label{eq: prop e_t 1}
    \w^i_{t_c+2} &= \w^i_{t_c+1} - \eta_1 \sgrw f^i(\w^i_{t_c+1}, \bpsi^i_{t_c+1}), \\
    \vdots \\
    \w^i_{t} &= \w^i_{t-1} - \eta_1 \sgrw f^i(\w^i_{t-1}, \bpsi^i_{t-1}).
\end{align}

Summing up all the equalities in \eqref{eq: prop e_t 1} yields that

\begin{align}
    \w^i_{t} &= \w^i_{t_c+1} - \eta_1 \sum_{l=t_c+1}^{t-1} \sgrw f^i(\w^i_l, \bpsi^i_l).
\end{align}

Therefore, the difference of the local models $\w^i_{t}$ and their average $\wbar_{t}$ can be written as

\begin{align}
    \w^i_{t} - \wbar_{t}
    &=
    \w^i_{t_c+1} - \eta_1 \sum_{l=t_c+1}^{t-1} \sgrw f^i(\w^i_l, \bpsi^i_l)
    -
    \left(\wbar_{t_c+1} - \eta_1 \frac{1}{n} \sum_{j \in [n]} \sum_{l=t_c+1}^{t-1} \sgrw f^j(\w^j_l, \bpsi^j_l) \right) \\
    &=
    -\eta_1 \left( \sum_{l=t_c+1}^{t-1} \sgrw f^i(\w^i_l, \bpsi^i_l) - \frac{1}{n} \sum_{j \in [n]} \sum_{l=t_c+1}^{t-1} \sgrw f^j(\w^j_l, \bpsi^j_l) \right).
\end{align}

This yields the following bound on each local deviation from the average $\E \Vert \w^i_{t} - \wbar_{t} \Vert^2$:

\begin{align} \label{eq: prop e_t 2}
    \E \norm{\w^i_{t} - \wbar_{t}}^2
    &=
    \eta_1^2 \E \norm{\sum_{l=t_c+1}^{t-1} \sgrw f^i(\w^i_l, \bpsi^i_l) - \frac{1}{n} \sum_{j \in [n]} \sum_{l=t_c+1}^{t-1} \sgrw f^j(\w^j_l, \bpsi^j_l)}^2 \\
    &\leq
    2 \eta_1^2
    \E \norm{\sum_{l=t_c+1}^{t-1} \sgrw f^i(\w^i_l, \bpsi^i_l) }^2
    +
    2 \eta_1^2
    \E \norm{\frac{1}{n} \sum_{j \in [n]} \sum_{l=t_c+1}^{t-1} \sgrw f^j(\w^j_l, \bpsi^j_l)}^2\\
    &\stackrel{(a)}{\leq}
    2 \eta_1^2
    \underbrace{\E \norm{\sum_{l=t_c+1}^{t-1} \grw f^i(\w^i_l, \bpsi^i_l) }^2 }_{T_3}
    +
    2 \eta_1^2
    \underbrace{\E \norm{\frac{1}{n} \sum_{j \in [n]} \sum_{l=t_c+1}^{t-1} \grw f^j(\w^j_l, \bpsi^j_l)}^2 }_{T_4} \\
    &\quad +
    2 \eta_1^2 (t - t_c - 1) (n+1) \frac{\sigmaw}{n},
\end{align}

where we used Assumption \ref{assumption:stoch-gradients} to bound the variance of the stochastic gradients and derive $(a)$. The term $T_4$ in \eqref{eq: prop e_t 2} can simply be bounded as

\begin{align}
    T_4
    \leq
    \E \norm{\frac{1}{n} \sum_{j \in [n]} \sum_{l=t_c+1}^{t-1} \grw f^j(\w^j_l, \bpsi^j_l)}^2
    \leq
    (t - t_c - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\frac{1}{n} \sum_{j \in [n]} \grw f^j(\w^j_l, \bpsi^j_l)}^2
\end{align}

Note that $t_c$ denotes the latest server-worker communication before iteration $t$, hence $t - t_c \leq \tau$ where $\tau$ is the duration of local updates in each round. Therefore, we have

\begin{align} \label{eq: prop e_t 4}
    T_4
    \leq
    (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\frac{1}{n} \sum_{j \in [n]} \grw f^j(\w^j_l, \bpsi^j_l)}^2
    \leq
    (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
\end{align}

Now we proceed to bound the term $T_3$ in \eqref{eq: prop e_t 2} as follows:

\begin{align}
    T_3
    &=
    \E \norm{\sum_{l=t_c+1}^{t-1} \grw f^i(\w^i_l, \bpsi^i_l) }^2 \\
    &\leq
    (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\grw f^i(\w^i_l, \bpsi^i_l) }^2 \\
    &\leq
    4 (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\grw f^i(\w^i_l, \bpsi^i_l) - \grw f^i(\wbar_l, \bpsi^i_l) }^2 \\
    &\quad +
    4 (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\grw f^i(\wbar_l, \bpsi^i_l) - \frac{1}{n} \sum_{j \in [n]} \grw f^j(\wbar_l, \bpsi^j_l) }^2 \\
    &\quad +
    4 (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\frac{1}{n} \sum_{j \in [n]} \grw f^j(\wbar_l, \bpsi^j_l) - \frac{1}{n} \sum_{j \in [n]} \grw f^j(\w^j_l, \bpsi^j_l) }^2 \\
    &\quad +
    4 (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\frac{1}{n} \sum_{j \in [n]} \grw f^j(\w^j_l, \bpsi^j_l) }^2
\end{align}

We can simply this bound by using Assumption \ref{assumption:smooth} on Lipschitz gradients for the local objectives $f^i$s and applying the notations for $e_l$ and $g_l$ to derive

\begin{align} \label{eq: prop e_t 3}
    T_3
    &\leq
    4 (\tau - 1) L_1^2 \sum_{l=t_c+1}^{t-1} \E \norm{\w^i_{l} - \wbar_{l}}^2
    +
    4 (\tau - 1) \sum_{l=t_c+1}^{t-1} \E \norm{\grw f^i(\wbar_l, \bpsi^i_l) - \grw f(\wbar_l, \Psi_l) }^2 \\
    &\quad +
    4 (\tau - 1) L_1^2 \sum_{l=t_c+1}^{t-1} e_l
    +
    4 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
\end{align}

We can plug \eqref{eq: prop e_t 4} and \eqref{eq: prop e_t 3} into \eqref{eq: prop e_t 2} and take the average of the both sides over $i = 1,\cdots,n$. This implies that

\begin{align}
    e_{t}
    &\leq
    16 \eta_1^2 (\tau - 1) L_1^2 \sum_{l=t_c+1}^{t-1} e_l
    +
    10 \eta_1^2 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
    +
    8 \eta_1^2 (\tau - 1)^2 \rho^2
    +
    4 \eta_1^2 (\tau - 1) (n+1) \frac{\sigmaw}{n}.
\end{align}

In above, we used the result of Proposition \ref{prop: non-iid degree} that given Assumption \ref{assumption:bounded-degree}, bounds the gradient diversity $\frac{1}{n} \sum_{i \in [n]} \Vert{\grw f^i(\w, \bpsi^i) - \grw f(\w, \Psi)} \Vert^2 \leq \rho^2$, where $\rho^2 = 3\rho_f^2 + 6 L_{12}^2 (\epsilon_1^2 + \epsilon_2^2)$. We defer the proof this proposition to the end of this section. This concludes the proof of Proposition \ref{prop:e-t}.
\end{proof}

Having set the required intermediate steps, we resume the proof of Lemma \ref{lemma:e_t g_l bound}. According to Proposition \ref{prop:e-t}, we can write the term $e_t$ as follows

\begin{align} \label{eq:e_t}
    e_{t}
    &\leq
    C_1 \sum_{l=t_c+1}^{t-1} e_l
    +
    C_2 \sum_{l=t_c+1}^{t-1} g_l
    +
    C_3
\end{align}

where we use the following short-hand coefficients

\begin{align} \label{eq: coefficients}
    C_1
    &\coloneqq
    16 \eta_1^2 (\tau - 1) L_1^2 \\
    C_2
    &\coloneqq
    10 \eta_1^2 (\tau - 1) \\
    C_3
    &\coloneqq
    8 \eta_1^2 (\tau - 1)^2 \rho^2 + 4 \eta_1^2 (\tau - 1) (n+1) \frac{\sigmaw}{n}.
\end{align}

We can then write this bound for every iteration in $[t_c+1 : t]$, that is

\begin{align}
    e_{t_c + 1}
    &=
    0 \\
	e_{t_c + 2}
	&\leq
	C_1 e_{t_c + 1} + C_2 g_{t_c + 1} + C_3 \\
	\vdots \\
	e_{t}
	&\leq
	C_1 \left( e_{t_c + 1} + \cdots + e_{t-1} \right) + C_2 \left( g_{t_c + 1} + \cdots + g_{t-1} \right) + C_3 .
\end{align}

Summing all of the inequalities results in the following

\begin{align}
    \sum_{l=t_c+1}^{t-1} e_l
    \leq
    C_1 (\tau - 1) \sum_{l=t_c+1}^{t-1} e_l
    +
    C_2 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
    +
    C_3 (\tau - 1).
\end{align}

We can further rearrange the terms above and write

\begin{align}
    \sum_{l=t_c+1}^{t-1} e_l
    \leq
    \frac{C_2 (\tau - 1)}{1 - C_1 (\tau - 1)} \sum_{l=t_c+1}^{t-1} g_l
    +
    \frac{C_3 (\tau - 1)}{1 - C_1 (\tau - 1)}.
\end{align}

Now, if we assume that $C_1 (\tau - 1) \leq 1/2$, then we get the following bound on $\sum_{l=t_c+1}^{t-1} e_l$

\begin{align}
    \sum_{l=t_c+1}^{t-1} e_l
    &\leq
    2 C_2 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
    +
    2 C_3 (\tau - 1)
\end{align}

Plugging back in \eqref{eq:e_t} and using the assumption $C_1 (\tau - 1) \leq 1/2$ yields that

\begin{align}
    e_{t}
    &\leq
    C_1 \left( 2 C_2 (\tau - 1) \sum_{l=t_c+1}^{t-1} g_l
    +
    2 C_3 (\tau - 1) \right)
    +
    C_2 \sum_{l=t_c+1}^{t-1} g_l
    +
    C_3\\
    &\leq
    2 C_2 \sum_{l=t_c+1}^{t-1} g_l
    +
    2 C_3,
\end{align}

which concludes the proof of Lemma \ref{lemma:e_t g_l bound}. Lastly, we present the following proposition along with its proof which we used this result to prove Proposition \ref{prop:e-t}.

\begin{prop} \label{prop: non-iid degree}
An immediate implication of Assumptions \ref{assumption:bounded-degree} and \ref{assumption:smooth} is that for any $\w, \Psi$, the diversity of the local gradients is bounded in the following sense

\begin{align}
    \frac{1}{n} \sum_{i \in [n]} \norm{\grw f^i(\w, \bpsi^i) - \grw f(\w, \Psi)}^2
    &\leq
    \rho^2,
\end{align}

where we denote $\rho^2 = 3\rho_f^2 + 6 L_{12}^2 (\epsilon_1^2 + \epsilon_2^2)$.
\end{prop}

\begin{proof} [Proof of Proposition \ref{prop: non-iid degree}]
The proof is simply implied from Assumptions \ref{assumption:bounded-degree} and \ref{assumption:smooth} by writing
\begin{align}
    \frac{1}{n} \sum_{i \in [n]} \norm{\grw f^i(\w, \bpsi^i) - \grw f(\w, \Psi)}^2
    &\leq
    3 \frac{1}{n} \sum_{i \in [n]} \norm{\grw f^i(\w, \Lambda^i, \delta^i) - \grw f^i(\w, I, 0)}^2 \\
    &\quad +
    3 \frac{1}{n} \sum_{i \in [n]} \norm{\grw f^i(\w) - \grw f(\w) }^2 \\
    &\quad +
    3 \frac{1}{n} \sum_{i \in [n]} \norm{\grw f(\w, I, 0) - \grw f(\w, \Psi)}^2 \\
    &\leq
    3\rho_f^2 + 6 L_{12}^2 (\epsilon_1^2 + \epsilon_2^2).
\end{align}

\end{proof}

\subsection{Proof of Lemma \ref{lemma:elimination}} \label{proof lemma:elimination}
\cite{haddadpour2019convergence} proves a similar claim for $\Gamma = 0$. For completeness, we provide the proof for general case when $ \Gamma \neq 0$. Let $t_c$ denote the index of the most recent communication round, i.e. $t_c = \floor*{\frac{t}{\tau}} \tau$. We can write $t = t_c + r$ where $1 \leq r \leq \tau$. Starting from $r=1$, we can write

\begin{align}
    P_{t_c+2}
    &\leq
    \Upsilon P_{t_c+1}
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L \right) g_{t_c+1}
    +
    \Gamma \\
    &\leq
    \Upsilon P_{t_c+1}
    +
    \Gamma,
\end{align}

where the last inequality holds if

\begin{align}
    \eta_1 L \leq 1.
\end{align}

We can continue for $r=2$ as follows

\begin{align}
    P_{t_c+3}
    &\leq
    \Upsilon P_{t_c+2}
    -
    \frac{\eta_1}{2} \left( 1 - \eta_1 L \right) g_{t_c+2}
    +
    \eta_1^2 B g_{t_c+1}
    +
    \Gamma \\
    &\stackrel{(a)}{\leq}
    \Upsilon^2 P_{t_c+1}
    -
    \frac{\eta_1}{2} \Upsilon \left( 1 - \eta_1 L - \eta_1 \frac{2B}{\Upsilon} \right) g_{t_c+1}
    +
    \Gamma (1 + \Upsilon)\\
    &\stackrel{(b)}{\leq}
    \Upsilon^2 P_{t_c+1}
    +
    \Gamma (1 + \Upsilon)
\end{align}

where $(a)$ is due to the inequality $P_{t_c+2} \leq \Upsilon P_{t_c+1} - \frac{\eta_1}{2} ( 1 - \eta_1 L ) g_{t_c+1} + \Gamma$ and $(b)$ holds if

\begin{align}
    1 - \eta_1 L - \eta_1 \frac{2B}{\Upsilon} \geq 0,
\end{align}

or equivalently

\begin{align}
    \eta_1 \left( L + \frac{2B}{\Upsilon} \right) \leq 1.
\end{align}

We can continue the same argument up to $r+1$ and write

\begin{align} \label{eq: lemma P convergence 3}
    P_{t_c+r+1}
    &\leq
    \Upsilon^{r} P_{t_c+1}
    +
    \Gamma (1 + \Upsilon + \cdots + \Upsilon^{r-1}),
\end{align}

if the step-size is as small as follows

\begin{align}
    \eta_1 \left( L + \frac{2B}{\Upsilon^{r-1}} \left( 1 + \Upsilon + \cdots + \Upsilon^{r-2} \right) \right) \leq 1.
\end{align}

Since  $1 + \Upsilon + \cdots + \Upsilon^{r-2} \leq \frac{1}{1 - \Upsilon}$, then the following condition implies all the previous ones on $\eta$

\begin{align}  \label{eq: lemma P convergence 2}
    \eta_1 \left( L + \frac{2B}{\Upsilon^{r-1} (1 - \Upsilon)} \right).
\end{align}

Moreover, since $\Upsilon < 1$, then the strongest condition on $\eta$ is \eqref{eq: lemma P convergence 2} when we put the largest possible value for $r$ which is $\tau$, yielding

\begin{align}
    \eta_1 \left( L + \frac{2B}{\Upsilon^{\tau-1} (1 - \Upsilon)} \right).
\end{align}

Lastly, we note that $1 + \Upsilon + \cdots + \Upsilon^{r-1} \leq \frac{1}{1 - \Upsilon}$ in \eqref{eq: lemma P convergence 3}, and the claim is concluded.

\subsection{Proof of Lemma \ref{lemma: sum b_t}} \label{proof lemma: sum b_t}
Recall the result of Lemma \ref{Lemma: b_t contraction} in which we showed that if $\eta_2 \leq 1/L_2$, then the following contraction bound on the sequence $\{b_t\}_{t \geq 0}$ holds:

\begin{align} \label{eq: lemma sum b_t 1}
    b_{t+1}
    &\leq
    (1 - \mu_2 \eta_2 n) \left( 1 + \eta_1 \frac{4 L_{12}^2}{\mu_2 n} \right) b_t
    +
    \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) g_t \\
    &\quad +
    \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) e_t
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{2} L_2 \sigmapsi,
\end{align}

and consider the coefficient of $b_t$ in above. A simple calculation yields that if the step-sizes satisfy the condition $\frac{\eta_2}{\eta_1} \geq \frac{8 L_{12}^2}{\mu_2^2 n^2}$, then we have

\begin{align}
    (1 - \mu_2 \eta_2 n) \left( 1 + \eta_1 \frac{4 L_{12}^2}{\mu_2 n} \right)
    \leq
    1 - \frac{1}{2} \mu_2 \eta_2 n.
\end{align}

Now, we denote $\gamma = 1 - \frac{1}{2} \mu_2 \eta_2 n$ and apply \eqref{eq: lemma sum b_t 1} to all iterations $t = 0, \cdots, T-1$, which yields that

\begin{align}
    b_{0}
    & \leq
    \frac{2 L_{2}^2}{\mu_2 n} \left(\epsilon_1^2 + \epsilon_2^2 \right), \\
    b_{1}
    &\leq
    \gamma b_0
    +
    \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) g_0
    +
    \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) e_0 \\
    &\quad +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{2} L_2 \sigmapsi, \\
    &\vdots\\
    b_{T-1}
    &\leq
    \gamma b_{T-2}
    +
    \frac{\eta_1}{2} \E \norm{\gr \Phi(\wbar_{t})}^2
    +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) g_{T-2}
    +
    \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) e_{T-2} \\
    &\quad +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{2} L_2 \sigmapsi.
\end{align}

Taking the average of the $T$ inequalities above yields that

\begin{align} \label{eq: lemma sum b_t 2}
    (1 - \gamma) \frac{1}{T} \sum_{t=0}^{T-1} b_{t}
    &\leq
    \frac{2 L_{2}^2}{\mu_2 n} \frac{\epsilon_1^2 + \epsilon_2^2}{T}
    +
    \frac{\eta_1}{2} \frac{1}{T} \sum_{t=0}^{T-1} \E \norm{\gr \Phi(\wbar_{t})}^2 \\
    &\quad +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{1}{T} \sum_{t=0}^{T-1} g_{t}
    +
    \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) \frac{1}{T} \sum_{t=0}^{T-1} e_{t} \\
    &\quad +
    \frac{\eta_1^2}{2} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{2} L_2 \sigmapsi.
\end{align}

We can further divide both sides of \eqref{eq: lemma sum b_t 2} by $1 - \gamma$ and conclude

\begin{align}
    \frac{1}{T} \sum_{t=0}^{T-1} b_{t}
    &\leq
    \frac{4 L_{2}^2}{\mu_2^2 n^2} \frac{\epsilon_1^2 + \epsilon_2^2}{\eta_2 T}
    +
    \frac{\eta_1}{\eta_2} \frac{1}{\mu_2 n} \frac{1}{T} \sum_{t=0}^{T-1} \E \norm{\gr \Phi(\wbar_{t})}^2 \\
    &\quad +
    \frac{\eta_1^2}{\eta_2} \frac{1}{\mu_2 n} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{1}{T} \sum_{t=0}^{T-1} g_{t}
    +
    \frac{1}{\eta_2} \frac{2}{\mu_2 n} \left( \eta_1 L_1^2 + \eta_2 L_{21}^2 \right) \frac{1}{T} \sum_{t=0}^{T-1} e_{t} \\
    &\quad +
    \frac{\eta_1^2}{\eta_2} \frac{1}{\mu_2 n} \left( L_1 + L_{\Phi} + 2 \eta_2 L_{21}^2 \right) \frac{\sigmaw}{n}
    +
    \eta_2 \frac{L_2}{\mu_2 n} \sigmapsi.
\end{align}

\subsection{Proof of Lemma \ref{lemma: sum e_t}} \label{proof lemma: sum e_t}

We begin by noting the result of Proposition \ref{prop:e-t} in which we showed the following bound on $e_t$

\begin{align} \label{eq:e_t}
    e_{t}
    &\leq
    C_1 \sum_{l=t_c+1}^{t-1} e_l
    +
    C_2 \sum_{l=t_c+1}^{t-1} g_l
    +
    C_3,
\end{align}

where we defined the coefficients $C_1, C_2, C_3$ in \eqref{eq: coefficients} and recall here for more convenient:

\begin{align}
    C_1
    &\coloneqq
    16 \eta_1^2 (\tau - 1) L_1^2 \\
    C_2
    &\coloneqq
    10 \eta_1^2 (\tau - 1) \\
    C_3
    &\coloneqq
    8 \eta_1^2 (\tau - 1)^2 \rho^2 + 4 \eta_1^2 (\tau - 1) (n+1) \frac{\sigmaw}{n}.
\end{align}

Next, we apply this bound to each iteration $t=0, \cdots, T-1$ as follows

\begin{align}
    &\quad e_0 = 0 \\
    &\left\{
	\begin{array}{ll}
		e_{1}  &= 0 \\
		e_{2} &\leq C_1 e_1 + C_2 g_1 + C_3 \\
		\vdots \\
		e_{\tau} &\leq C_1 \left( e_1 + \cdots + e_{\tau-1} \right) + C_2 \left( g_1 + \cdots + g_{\tau-1} \right) + C_3
	\end{array}
    \right.\\
    &\left\{
	\begin{array}{ll}
		e_{\tau+1}  &= 0 \\
		e_{\tau+2} &\leq C_1 e_{\tau+1} + C_2 g_{\tau+1} + C_3 \\
		\vdots \\
		e_{2\tau} &\leq C_1 \left( e_{\tau+1} + \cdots + e_{2\tau-1} \right) + C_2 \left( g_{\tau+1} + \cdots + g_{2\tau-1} \right) + C_3
	\end{array}
    \right.\\
    &\quad\quad \vdots\\
    &\left\{
	\begin{array}{ll}
		e_{T_c + 1}  &= 0 \\
		e_{T_c + 2} &\leq C_1 e_{T_c + 1} + C_2 g_{T_c + 1} + C_3 \\
		\vdots \\
		e_{T-1} &\leq C_1 \left( e_{T_c + 1} + \cdots + e_{T-2} \right) + C_2 \left( g_{T_c + 1} + \cdots + g_{T-2} \right) + C_3,
	\end{array}
    \right.
\end{align}

where $T_c = \floor*{\frac{T}{\tau}} \tau$ denote the index of the most recent communication between the workers and the server before iteration $T$. Summing the above inequalities yields that

\begin{align} \label{eq: lemma sum e_t 1}
    \sum_{t=0}^{T-1} e_{t}
    &\leq
    C_1 (\tau - 1) \sum_{t=0}^{T-1} e_{t}
    +
    C_2 (\tau - 1) \sum_{t=0}^{T-1} g_t
    +
    C_3 T.
\end{align}

Now if we assume that $C_1 (\tau - 1) = 16 \eta_1^2 (\tau - 1)^2 L_1^2 \leq \frac{1}{2}$, the the claim is concluded by rearranging the terms in \eqref{eq: lemma sum e_t 1}:

\begin{align}
    \frac{1}{T} \sum_{t=0}^{T-1} e_{t}
    &\leq
    2 C_2 (\tau - 1) \frac{1}{T} \sum_{t=0}^{T-1} g_t
    +
    2 C_3.
\end{align}

\section{Proof of Theorem \ref{Thm: generalization}} \label{appendix: proof of Thm generalization}

Fix a distribution $\tilde{P}$ and consider
\begin{equation}
    \max_{\Lambda,\delta}\: \mathbb{E}_{\tilde{P}}[\ell(f_{\w}(\Lambda \mathbf{x}+\delta))] - \lambda \Vert\delta \Vert^2_2 - \lambda \Vert \Lambda - I\Vert^2_F
\end{equation}
Assuming a $1$-Lipschitz loss $\ell$ with $1$-Lipschitz gradient, based on \cite{farnia2018generalizable}'s Lemma 7 the above function's gradient with respect to $\delta$ has a Lipschitz constant bounded by
\begin{equation*}
    \operatorname{Lip}(\nabla f_{\w}):=\bigl(\prod_{i=1}^L \Vert\w_i\Vert_\sigma\bigr)\sum_{i=1}^l\prod_{j=1}^i\Vert \w_j\Vert_\sigma.
\end{equation*}
Similarly, the expected loss's derivative with respect to $\Lambda$ will also be Lipschitz in the spectral norm with a Lipschitz constant upper-bounded by
\begin{equation*}
    B\operatorname{Lip}(\nabla f_{\w})=B\bigl(\prod_{i=1}^L \Vert\w_i\Vert_\sigma\bigr)\sum_{i=1}^l\prod_{j=1}^i\Vert \w_j\Vert_\sigma.
\end{equation*}
Given weights in $\w$, we denote the optimal solution for $\delta$ and $\Lambda$ by $\delta_{\w}$ and $\Lambda_{\w}$, respectively. To apply the Pac-Bayes generalization analysis, we need to bound the change in $\delta_{\w},\Lambda_{\w}$ caused by perturbing $\w$ to $\w + \bm{u}$. Note that since $\lambda>(1+B)\operatorname{Lip}(\nabla f_{\w})$, the maximization problem for optimizing $\Lambda_{\w}, \delta_{\w}$ is maximizing a strongly-concave objective whose solutions will satisfy:
\begin{align*}
    \delta_{\w} &=\frac{1}{\lambda} \mathbb{E}[\nabla\ell\circ f_{\w}(\Lambda_{\w}\mathbf{x}+ \delta_{\w})], \\
    {\Lambda}_{\w}-I &=\frac{1}{\lambda} \mathbb{E}[(\nabla\ell\circ f_{\w}(\Lambda_{\w}\mathbf{x}+ \delta_{\w}))\mathbf{X}^\top]
\end{align*}
which are norm-bounded by $\frac{\operatorname{Lip}(\ell \circ f_{\w})}{\lambda}\le \frac{\prod_{i=1}^d \Vert \w_i \Vert_\sigma }{\lambda}$ and $B\frac{\operatorname{Lip}(\ell \circ f_{\w})}{\lambda}\le B\frac{\prod_{i=1}^d \Vert \w_i \Vert_\sigma }{\lambda}$, respectively. Therefore, for a norm-bounded perturbation $\bm{u}$ where $\Vert\bm{u}_i\Vert_\sigma\le \frac{1}{L}\Vert\w_i\Vert_\sigma$ we can write
\begin{align*}
    &\big\Vert {\delta}_{\w + \bm{u}}- {\delta}_{\w} \big\Vert_2 + \big\Vert\Lambda_{\w + \bm{u}}- \Lambda_{\w} \big\Vert_\sigma  \\
    =\, & \big\Vert \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} ))] - \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} ))] \big\Vert_2 \\
    &\quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} ))\mathbf{X}^\top] - \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} ))\mathbf{X}^\top] \big\Vert_\sigma \\
    =\, & \big\Vert \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} ))] \big\Vert_2 \\
    &\quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[(\nabla \ell(f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} )))\mathbf{X}^\top] \big\Vert_\sigma  \\
    \le \, & \big\Vert \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} ))] \big\Vert_2 \\
    & \quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w + \bm{u}} ))] \big\Vert_2 \\
    & \quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[\nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} ))] \big\Vert_2 \\
    & \quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[(\nabla \ell(f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )))\mathbf{X}^\top] \big\Vert_\sigma \\
    & \quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[(\nabla \ell(f_{\w}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w + \bm{u}} )))\mathbf{X}^\top] \big\Vert_\sigma \\
    & \quad + \big\Vert \frac{1}{\lambda}\mathbb{E}[(\nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w + \bm{u}} )) - \nabla \ell(f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} )))\mathbf{X}^\top] \big\Vert_\sigma \\
    \le \, & \frac{(B+1)\operatorname{lip}(\ell\circ f_{\w})}{\lambda}\bigl( \Vert {\delta}_{\w + \bm{u}}- {\delta}_{\w}\Vert_2 + \Vert\Lambda_{\w + \bm{u}}- \Lambda_{\w} \Vert_\sigma \bigr) \\
    & \quad + (B+1)e^2(\prod_{i=1}^L\Vert\w_i \Vert_\sigma)\sum_{i=1}^d\biggl[ \frac{\Vert \bm{u}_i\Vert_\sigma}{\Vert \w_i\Vert_\sigma} + B(\prod_{j=1}^i\Vert\w_j \Vert_\sigma)\sum_{j=1}^i\frac{\Vert\bm{u}_j\Vert_\sigma}{\Vert\w_j\Vert_\sigma}\biggr],
\end{align*}
where the last inequality follows from Lemma 3 in \cite{farnia2018generalizable}. As a result,
\begin{align*}
     &\big\Vert {\delta}_{\w + \bm{u}} - {\delta}_{\w} \big\Vert_2 + \big\Vert\Lambda_{\w + \bm{u}}- \Lambda_{\w} \big\Vert_\sigma  \\
     \le \, &\frac{\lambda}{\lambda-(B+1)\operatorname{lip}(\ell\circ f_{\w})} \biggl[ (B+1)e^2(\prod_{i=1}^L\Vert\w_i \Vert_\sigma)\sum_{i=1}^d\bigl[ \frac{\Vert \bm{u}_i\Vert_\sigma}{\Vert \w_i\Vert_\sigma} + B(\prod_{j=1}^i\Vert\w_j \Vert_\sigma)\sum_{j=1}^i\frac{\Vert\bm{u}_j\Vert_\sigma}{\Vert\w_j\Vert_\sigma}\bigr]\biggr].
\end{align*}

Then, we can bound the change in the loss function caused by perturbing $\w$ at any $\Vert\mathbf{x}\Vert_2\le B$ with any norm-bounded $\Vert\bm{u}_i\Vert_\sigma\le\frac{1}{L}\Vert\w_i\Vert_\sigma$:
\begin{align*}
    &\big\Vert f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} ) - f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} )\big\Vert_2 \\
    \le \, & \big\Vert f_{\w + \bm{u}}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} ) - f_{\w}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} )\big\Vert_2 \\
    &\, + \big\Vert f_{\w}(\Lambda_{\w + \bm{u}}\mathbf{X} +\delta_{\w + \bm{u}} ) - f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w + \bm{u}} )\big\Vert_2 \\
    &\, + \big\Vert f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w + \bm{u}} ) - f_{\w}(\Lambda_{\w}\mathbf{X} +\delta_{\w} )\big\Vert_2 \\
    \le \, & eB\bigl(\prod_{i=1}^L \Vert \w_i \Vert_\sigma \bigr)\sum_{i=1}^L\frac{\Vert \bm{u}_i\Vert_2}{\Vert \w_i\Vert_2} + (1+B)\bigl(\prod_{i=1}^d \Vert \w_i \Vert_\sigma \bigr) \\
    &\, \frac{e^2}{\lambda - (B+1)\operatorname{Lip}(\nabla f_{\w})}\sum_{i=1}^L \bigl[\frac{\Vert \bm{u}_i\Vert_\sigma}{\Vert \w_i\Vert_\sigma} +B(\prod_{j=1}^i \Vert \w_j \Vert_\sigma)\sum_{j=1}^i\frac{\Vert \bm{u}_j\Vert_\sigma}{\Vert \w_j\Vert_\sigma} \bigr].
\end{align*}
Now, for a fixed weight vector $\tilde{\w}$ we consider a multivariate Gaussian distribution $Q$ with zero-mean and diagonal covaraince matrix for perturbation $\bm{u}$ where each entry $\bm{u}_i$ has standard deviation $\kappa_i=\frac{\Vert \tilde{\w}_i\Vert_\sigma}{\sqrt[L]{\prod_{i=1}^L\Vert \tilde{\w}_i\Vert_\sigma}}\kappa$ with $\kappa$ chosen as
\begin{equation}
    \kappa = \frac{\gamma}{8e^5L\sqrt{2d\log(4dL)}B\bigl(\prod_{i=1}^L\Vert \tilde{\w}_i\Vert_\sigma\bigr)\bigl(1+\frac{\lambda}{\lambda-(1+B)\overline{\operatorname{Lip}}(\nabla  f_{\w})}\sum_{i=1}^L\prod_{j=1}^i\Vert\tilde{\w}_j\Vert_\sigma\bigr)}.
\end{equation}
Also, for any $\w$ which satisfies $|\Vert\w_i\Vert_\sigma - \Vert\tilde{\w}_i\Vert_\sigma |\le \frac{\eta}{4L}\Vert\tilde{\w}_i\Vert_\sigma$, we have $\overline{\operatorname{Lip}}(\ell\circ f_{\w})\le e^{\eta/2}\lambda(1-\eta)\le (1-\eta/2)\lambda$. Therefore,
\begin{align*}
    &\operatorname{KL}(P_{\w + \bm{u}}\Vert Q)\\
    \le\, & \sum_{i=1}^d\frac{\Vert\w_i\Vert^2_F}{2\kappa^2_i} \\
    \le \, & O\biggl( L^2B^2 d\log(dL)\frac{(\prod_{i=1}^L\Vert \tilde{\w}_i\Vert^2_\sigma)\bigl(1+\frac{1}{\lambda-(1+B)\overline{\operatorname{Lip}}(\nabla  f_{\w})}\sum_{i=1}^L\prod_{j=1}^i \Vert \tilde{\w}_j\Vert_\sigma \bigr)^2}{\gamma^2} \sum_{i=1}^d\frac{\Vert\w_i\Vert^2_F}{\Vert\tilde{\w}_i\Vert^2_\sigma}\biggr) \\
    \le \, & O\biggl( L^2B^2 d\log(dL)\frac{(\prod_{i=1}^L\Vert \w_i\Vert^2_\sigma)\bigl(1+\frac{1}{\lambda-(1+B)\overline{\operatorname{Lip}}(\nabla  f_{\w})}\sum_{i=1}^L\prod_{j=1}^i \Vert {\w}_j\Vert_\sigma \bigr)^2}{\gamma^2} \sum_{i=1}^d\frac{\Vert\w_i\Vert^2_F}{\Vert{\w}_i\Vert^2_\sigma}\biggr)
\end{align*}
Now we plug the above result into \cite{farnia2018generalizable}'s Lemma 1, implying that given a fixed underlying distribution $P$ and any $\xi>0$ with probability at least $1-\xi$ for any $\w$ satisfying $|\Vert\w_i\Vert_\sigma - \Vert\tilde{\w}_i\Vert_\sigma |\le \frac{\eta}{4L}\Vert \tilde{\w}_i\Vert_\sigma$ we have
\begin{equation}
    \mathcal{L}^{\operatorname{adv}}_{0-1}(\w) - \hat{\mathcal{L}}^{\operatorname{adv}}_{{\gamma}}(\w)
    \le
    \mathcal{O} \left( \sqrt{ \frac{ B^2L^2d\log(Ld)\lambda^2\bigl(\prod_{i=1}^L\Vert \w_i\Vert_{\sigma} \sum_{i=1}^L\frac{\Vert \w_i\Vert^2_F}{\Vert \w_i\Vert^2_{\sigma}}\bigr)^2+\log\frac{m}{\xi}  }{m \gamma^2 (\lambda-(1+B)\operatorname{Lip}(\nabla f_{\w}))^2} }\right).
\end{equation}
Now we use a cover of size $O(\frac{L}{\eta}\log M)$ points where for any feasible $\Vert \w_i\Vert_\sigma$ we can find a point $a_i$ in the cover such that $|\Vert \w_i\Vert_\sigma- a_i|\le\frac{\eta}{4L}a_i$. As a result, we can cover the space of feasible $\w_i$'s with $O\bigl((\frac{L}{\eta}\log M))^L L \bigr)$ number of points. This proves that for a fixed underlying distribution for every $\xi>0$, with probability at least $\xi>0$ for any feasible norm-bounded $\w$ we have
\begin{equation}
    \mathcal{L}^{\operatorname{adv}}_{0-1}(\w) - \hat{\mathcal{L}}^{\operatorname{adv}}_{{\gamma}}(\w)
    \le
    \mathcal{O} \left( \sqrt{ \frac{ B^2L^2d\log(Ld)\lambda^2\bigl(\prod_{i=1}^L\Vert \w_i\Vert_{\sigma} \sum_{i=1}^L\frac{\Vert \w_i\Vert^2_2}{\Vert \w_i\Vert^2_{\sigma}}\bigr)^2+L\log\frac{mL\log(M)}{\eta\xi}  }{m \gamma^2 (\lambda-(1+B)\operatorname{Lip}(\nabla \ell \circ f_{\w}))^2} }\right).
\end{equation}
To apply the result to the network of $n$ nodes, we apply a union bound to have the bound hold simultaneously for the distribution of every node, which proves for every $\xi>0$ with probability at least $1-\xi$ the average worst-case loss of the nodes satisfies the following margin-based bound:
\begin{equation}
    \mathcal{L}^{\operatorname{adv}}_{0-1}(\w) - \hat{\mathcal{L}}^{\operatorname{adv}}_{{\gamma}}(\w)
    \le
    \mathcal{O} \left( \sqrt{ \frac{ B^2L^2d\log(Ld)\lambda^2\bigl(\prod_{i=1}^L\Vert \w_i\Vert_{\sigma} \sum_{i=1}^L\frac{\Vert \w_i\Vert^2_F}{\Vert \w_i\Vert^2_{\sigma}}\bigr)^2+L\log\frac{nmL\log(M)}{\eta\xi}  }{m \gamma^2 (\lambda-(1+B)\operatorname{Lip}(\nabla f_{\w}))^2} }\right).
\end{equation}
Therefore, the proof is complete.

\section{Proof of Theorem \ref{Thm: DRO}} \label{appendix: proof of Thm DRO}
Define random vector $\mathbf{U}=\Lambda\mathbf{X}+\delta$. According to the definition of optimal transport cost $W_c(P_\mathbf{X},P_\mathbf{U})$ for quadratic $c(\mathbf{x},\mathbf{u})=\frac{1}{2}\Vert\mathbf{x}-\mathbf{u} \Vert^2_2$,
\begin{equation}
    W_c(P_\mathbf{X},P_\mathbf{U}) := \min_{P_{\mathbf{X,U}}\in \Pi(P_\mathbf{X},P_\mathbf{U})}\: \mathbb{E}\bigl[ \frac{1}{2}\Vert\mathbf{X}-\mathbf{U} \Vert^2_2 \bigr]
\end{equation}
where $\Pi(P_\mathbf{X},P_\mathbf{U})$ contains any joint distribution $P_{\mathbf{X,U}}$ with marginals $P_\mathbf{X},P_\mathbf{U}$. One distribution in $\Pi(P_\mathbf{X},P_\mathbf{U})$ is the joint distribution of $(\mathbf{X},\Lambda\mathbf{X}+\delta)$ implying that
\begin{align*}
    W_c(P_\mathbf{X},P_\mathbf{U}) &\le \frac{1}{2}\mathbb{E}\bigl[\Vert \mathbf{X}-\Lambda\mathbf{X}-\delta\Vert_2^2\bigr] \\
    &= \frac{1}{2}\mathbb{E}\bigl[\Vert (I-\Lambda)\mathbf{X}-\delta\Vert_2^2\bigr] \\
    &\stackrel{(a)}{\le} \mathbb{E}\bigl[\Vert(I-\Lambda)\mathbf{X}\Vert^2_2\bigr] + \Vert\delta\Vert_2^2 \\
    &\stackrel{(b)}{\le} \operatorname{Tr}\bigl((I-\Lambda)(I-\Lambda)^\top\mathbb{E}[\mathbf{X}\mathbf{X}^\top]\bigr) + \Vert\delta\Vert_2^2 \\
    &\stackrel{(c)}{\le} \lambda \operatorname{Tr}\bigl((I-\Lambda)(I-\Lambda)^\top\bigr) + \Vert\delta\Vert_2^2 \\
    &\stackrel{(d)}{\le} \lambda \Vert I-\Lambda\Vert^2_F+ \Vert\delta\Vert_2^2 \\
    &\le \max\{\lambda,1\}\bigr( \Vert I-\Lambda\Vert^2_F+ \Vert\delta\Vert_2^2\bigl).
\end{align*}
In the above, $(a)$ holds since for every two vectors $\mathbf{u}_1,\mathbf{u}_2$ we have $\Vert \mathbf{u}_1 + \mathbf{u}_2\Vert^2_2 = \Vert \mathbf{u}_1\Vert^2_2 + \Vert\mathbf{u}_2\Vert^2_2 + 2\mathbf{u}^\top_1 \mathbf{u}_2 \le 2(\Vert \mathbf{u}_1\Vert^2_2 + \Vert\mathbf{u}_2\Vert^2_2)$. $(b)$ follows from the fact that $\mathbb{E}[\Vert(I-\Lambda)\mathbf{X}\Vert^2_2] = \mathbb{E}[\operatorname{Tr}((I-\Lambda)\mathbf{X}\mathbf{X}^\top(I-\Lambda)^\top) = \operatorname{Tr}\bigl((I-\Lambda)(I-\Lambda)^\top\mathbb{E}[\mathbf{X}\mathbf{X}^\top]\bigr)$. $(c)$ holds because of the theorem's assumption implying that $\mathbb{E}[\mathbf{X}\mathbf{X}^\top]\le \lambda I$. Last, $(d)$ holds because we have $\operatorname{Tr} (AA^\top) = \Vert A\Vert^2_F$ for every $A$. Therefore, the proof is complete.

config: arxiv


TITLE: Understanding $\mathcal{A}$-measurable
QUESTION [0 upvotes]: DEFINITION. A function $f$ on $X$ to $\mathbb{R}$ is said to be $\mathcal{A}$ -measurable (or simply measurable) if for every real number $\alpha$ the set
$$
\{x \in X: f(x)>\alpha\}
$$
belongs to $\mathcal{A}$.
LEMMA. The following statements are equivalent for a function fon $X$ to $\mathbb{R}$ :
(a) For every $\alpha \in \mathbb{R},$ the set $A_{\alpha}=\{x \in X: f(x)>\alpha\}$ belongs to $\mathcal{A}$
(b) For every $\alpha \in \mathbb{R},$ the set $B_{\alpha}=\{x \in X: f(x) \leqslant \alpha\}$ belongs to $\mathcal{A}$
(c) For every $\alpha \in \mathbb{R},$ the set $C_{\alpha}=\{x \in X: f(x) \geqslant \alpha\}$ belongs to $\mathcal{A}$
(d) For every $\alpha \in \mathbb{R},$ the set $D_{\alpha}=\{x \in X: f(x)<\alpha\}$ belongs to $\mathcal{A}.$
PROOF. Since $B_{\alpha}$ and $A_{\alpha}$ are complements of each other, statement
(a) is equivalent to statement (b). Similarly, statements (c) and (d) are equivalent. If (a) holds, then $A_{\alpha-1 / n}$ belongs to $\mathcal{A}$ for each $n$ and since
$$
C_{\alpha}=\bigcap_{n=1}^{\infty} A_{\alpha-1 / n}
$$
it follows that $C_{\alpha} \in \mathcal{A} . \quad$ Hence (a) implies (c). $\quad$ since
$$
A_{\alpha}=\bigcup_{n=1}^{\infty} C_{\alpha+1 / n}
$$
it follows that (c) implies (a).

My question is: Why "$C_{\alpha}=\bigcap_{n=1}^{\infty} A_{\alpha-1 / n}$", that is why "$\bigcap$", why not $"\bigcup"$? I didn't understood it, can you explain it? Also I didn't understood that why "$A_{\alpha}=\bigcup_{n=1}^{\infty} C_{\alpha+1 / n}$", that is why "$\bigcup$"?

REPLY [1 votes]: Let us compare
$$B=\bigcup_{n\geq 1}A_{\alpha-1/n}$$
with
$$C=\bigcap_{n\geq 1}A_{\alpha-1/n}$$
Which of $B$ and $C$ is the set $C_{\alpha}$, that is $f(x)\geq\alpha$?
If $x\in B$ then $x\in A_{\alpha-1/n}$ for some integer $n$ that is
$$f(x)>\alpha-\dfrac{1}{n}$$
for some integer $n$. Then it could very well be that $f(x)<\alpha$, there is some room between $\alpha-1/n$ and $\alpha$.
However if you consider $C$ then $x\in C$ means that
$$f(x)>\alpha-\dfrac{1}{n}$$
for every possible integer $n$. That can only happen if $f(x)\geq\alpha$.
The other question is pretty much the same issue, see if you can figure it out on your own.


TITLE: Understanding the cohomology ring of the Grassmannian
QUESTION [2 upvotes]: Some background first: I'm trying to understand the solution of some enumerative geometry problems, such as proving that a smooth cubic contains $27$ lines. I know that this becomes easier once one understands the cohomology of the Grassmannian.
I know that the Grassmannian can be given a CW-complex structure, but I don't understand how to compute the actual cohomology ring. I think that is the subject of Schubert calculus, and names like Pieri's or Giambelli's formulas often pop up. But I have also read elsewhere, such as in Hatcher's book Vector Bundles and K-Theory, that one can use Chern classes to describe the cohomology ring.
My question is, how are the two approaches related, and, most importantly, what is a comprehensive textbook on the subject?

REPLY [3 votes]: The two texts I have most often been referred to for studying the cohomology of the Grassmannian are Young Tableaux by Fulton and Symmetric Functions, Schubert Polynomials, and Degeneracy Loci by Manivel. From my perspective, Manivel takes a fairly combinatorial perspective while Part III of Fulton gives an excellent treatment of this question from a more geometric perspective.


TITLE: What is the meaning of null regression coefficients
QUESTION [1 upvotes]: I have real data $x(t)$ which I model using the linear regression model: $\displaystyle f(t)= \sum_{i=0}^n c_i \phi_i(t)$, where $c_i$ are the regression coefficients I'm trying to find and $\phi_i(t)$ are a basis function (I chose Legendre Polynomials for their orthogonality).
I noticed something strange I couldn't explain i.e. when I fix $n=1$ for my model I get $\hat{c}_0, \hat{c}_1$, normal! Then when I fix $n=2$ for my model I get $\hat{c'}_0=\hat{c}_0, \hat{c'}_1=\hat{c}_1, \hat{c'}_2=0$ (Seems like $n=2$ didn't add anything to the data modeling!)
What is more strange is that when I fix $n=3$, I get $\hat{c''}_0, \hat{c''}_1, \hat{c''}_2, \hat{c''}_3$ that are completely different (no $\hat{c''}_2=0$)
Does anyone understand what is happening here?
This also happens for other even index coefficients $c_4, c_6, \dots$ i.e. when they are the latest regression coefficient in my model they are null but when I add another odd index coefficient they are not. Also I noticed that the coefficient values I obtain are high (as if to indicate an overfitting!)

REPLY [1 votes]: The Legendre polynomials are orthogonal, but your regression results (by changing) show that their values on your data have nonzero covariance.
If $f(t)$ is odd that would explain the odd/even pattern with the $c_i$, where the even degree $c_{2n}$ contribute nothing on their own, but are involved in isolating the contribution of odd powers of $x$.


TITLE: Connectedness and invertibility of Laplacian matrix
QUESTION [0 upvotes]: Context:
In the context of circuit theory and graph theory, suppose we have a graph $G,$ then the Laplacian (Kirchhoff) matrix $L$ is defined as follows:
$$
L = D-A \tag{1}
$$
where $D$ is the degree matrix and $A$ the adjacency matrix. Alternatively, in terms of the incidence matrix $M$ it can be also expressed as:
$$
L = M^T M \tag{2}
$$
I am interested in the case where the graph $G$ is connected. Then if we partition $G$ into connected subgraphs that are themselves connected, the Laplacian can then be represented as a block matrix. Let's assume we partition the graph into two parts, the boundary nodes $B$ and the connection nodes $C.$ Then $|V(G)|=|V(G_B)|+|V(G_C)|.$ The corresponding Laplacian matrix can be put in the form of the following block matrix:
$$
L = \begin{bmatrix}
       L_{BB} & L_{BC}          \\
       L_{CB} & L_{CC}
     \end{bmatrix}
\tag{3}
$$
One often is interested in reducing the size of the network/graph, using a scheme such as the Kron reduction, which relies on taking the Schur complement  (Laplacian matrices are M-Matrices) of $L$ with respect to one of its blocks. But that is only possible if the submatrix of the chosen block is invertible, and in general this is assumed to follow from the connectedness of the graph.
Questions:

Does the fact that $G$ and its subcomponents ($B$ and $C$) are connected ensure that the submatrices of the block representation of the Laplacian $L$ are invertible? (does this follow from a known theorem?) And therefore the Schur complements can be safely taken.
In relation to connected graphs and their corresponding incidence matrices $M$ [*], is there a simple way to see that the kernel of $M$ is given by $\text{ker } M^T=\text{span } \mathbb{1}?$

[*]: The incidence matrix $M$ is usually defined with each column corresponding to an edge of $G,$ where then each column contains exactly one $1$ at the row corresponding to the tail-node of the edge and a $-1$ at the row corresponding to the head-node of the edge.

REPLY [0 votes]: For your first question, I think you can easily prove that $L_{BB}$ and $L_{CC}$ are
weakly chained diagonally dominant matrices from your connection assumptions:
For each row of $L_{BB}$ (similar proof holds for $L_{CC}$) there is two possible cases:

the node associated to the row in $B$ is connected to some node in $C$. Then the row is strictly diagonally dominant (as there are non 0 coefficients in the same row in $L_{BC}$).
the node  associated to the row in $B$ is not connected to some node in $C$ and then diagonally dominant but not strictly. But as you graph is connected, there exists a path from this node to another node $n$ in $B$ which is connected to some node in $C$. The node $n$ is then associated to a row of $L_{BB}$
This is exactly the definition of a weakly chained diagonally dominant matrix.

As these matrices have the property of being non-singular, you can conclude that $L_{BB}$ and $L_{CC}$ are invertible.
$L_{BC}$ (and $L_{CB}$ which is equal to $L_{BC}$ for undirected graph which is the case you seem to consider) can be singular, but you don't need nonsingularity of this matrix for applying Schur complement.


TITLE: Directional Derivative Interpretation
QUESTION [1 upvotes]: I'm trying to understand directional derivatives. If I have a function $f(x,y)$ then $\frac{\partial f}{\partial x}|_{x_0,y_0}=f_x$is the slope of a tangent line to a curve parallel to the X-Z plane
and $\frac{\partial f}{\partial y}|_{x_0,y_0}=f_y$is the slope of a tangent line to a curve parallel to the Y-Z plane at point $(x_0,y_0)$
$\implies \nabla f= <f_x,f_y>$
and now if I want to find the slope of a curve obtained by slicing $f(x,y)$ by a plane parallel to some vector $\overrightarrow u = <a,b>$ then we can get the parametric equation of the line parallel to $\overrightarrow u$ through the point $(x_0,y_0)$
as $$
\begin{matrix}
x=x_0+as\\
y=y_0+bs\\
\end{matrix}
$$
By using the chain rule,
$$
\begin{matrix}
\frac{df}{ds}=\frac{\partial f}{\partial x}\frac{dx}{ds}+\frac{\partial f}{\partial y}\frac{dy}{ds} \\
\frac{df}{ds}=\nabla f \cdot \frac{d\overrightarrow r}{ds}\\
\frac{df}{ds}=\nabla f \cdot \overrightarrow u\\
\end{matrix}
$$
But why is the professor considering $\frac{d\overrightarrow r}{ds}$ as to $\overrightarrow u$
And, why does $\overrightarrow u$ have to be a unit vector? What is the significance of this?
and how is $\frac{df}{ds}$ same as directional derivative.
It all seems muddled and awkward

REPLY [0 votes]: The directional derivative is meant to generalize the notion of partial derivatives - it's a rate of change in a specific direction, similar to how $f_x$ and $f_y$ are the rates of change in the $x$ and $y$ directions respectively. In order for the directional derivative to reduce to the usual partial derivatives when $\vec{u} = \hat{i}$ or $\hat{j}$, we require that $\vec{u}$ be a unit vector. As for why $df/ds$ is the same as the directional derivative, when you slice the graph of your function along a plane, you get a curve lying in that plane. The slope of that curve is the directional derivative, which coincides with the ordinary derivative of the function along the parametrized curve $\vec{r}(s)=\langle x_0 + as, y_0+bs\rangle$.
If we allowed $\vec{u}$ to have a magnitude, we would be scaling our rate of change by another quantity. A good example is the following: Let's say you're walking over a hot surface with temperature $T(x,y)$. One could ask how quickly the temperature you experience is changing with time (i.e. a derivative with respect to time), or the rate of change of temperature you experience per unit distance you've walked (i.e. a derivative with respect to space). The directional derivative is meant to capture the latter, since if $x$ and $y$ have the same units, the directional derivative will have the same units as $f_x$ and $f_y$.
To determine time rate of change, suppose you're walking with position $\vec{r}(t)$ and velocity $d\vec{r}/dt$. By the chain rule, we arrive at
$$\frac{d}{dt}f(\vec{r}(t)) = \left.\nabla f\right|_{\vec{r}(t)} \cdot\frac{d\vec{r}}{dt}$$
Which is almost a directional derivative, except now $d\vec{r}/dt$ may not be a unit vector. In fact, the time rate of change of temperature is precisely the directional derivative multiplied by your speed.


TITLE: In how many ways can the alphabet be ordered such that no four or five vowels are next to each other?
QUESTION [6 upvotes]: The original question:
(i) In how many ways can the alphabet be ordered such that m and n aren't next to each other? (ii) And how many ways such that the five vowels aren't next to each other. (iii) And, such that no four or five vowels are next to each other.
I was able to answer the first two. ($26!$ - $2(25!)$ and $26!$ - $5!22!$) However, I'm not sure about the third. I'd say that it would equal ($26!$ - #combinations with $5$ vowels next to each other - #combinations with really only $4$ vowels next to each other (and not $5$).
Now, #combinations of really only 4 vowels = #combinations of just $4$ vowels - #combinations with $5$ vowels. This would mean that the answer would be $26!$ - #combinations of just $4$ vowels next to each other = $26! -$ $5 $($4!$)($23!$) = $26! - 5!23!$. Somehow I'm not convinced of this answer, because if I'd make all these combinations, I'd be counting some double I feel like. (.... a i e o u ..... and .... a i e o u ..... are the same combinations, but they are both counted). What am I doing wrong? Could it be $26!$ - #combinations with $4$ vowels next to each other + #combinations with $5$ vowels next to each other ?
Thanks in advance for any help.

REPLY [2 votes]: Here’s a way to count the permutations with a block of exactly four vowels. (You’ve done everything else just fine.)
There are $21!$ permutations of the consonants. Each of them defines $22$ slots for the vowels, $20$ between adjacent consonants and $2$ on the ends. There are $5$ ways to choose the lonesome vowel, and $22$ ways to decide where to put it. The block of four vowels has to go in one of the other $21$ slots, and within that slot it can be permuted in $4!$ ways. Thus, there are
$$21!\cdot5\cdot22\cdot21\cdot4!=22!\cdot5!\cdot21$$
such permutations.


TITLE: A special Vandermonde system with integer coefficients
QUESTION [3 upvotes]: Consider the Vandermonde system
  $$\left(\begin{matrix}  1&1&1&\dots&\dots&1\\
  1&2&3&4&\dots&n\\
  1&2^2&3^2&4^2&\dots&n^{2}\\
    1&2^3&3^3&4^3&\dots&n^{3}\\
    \vdots&&&&&\vdots\\
      1&2^{n-1}&3^{n-1}&4^{n-1}&\dots&n^{n-1}\\
  \end{matrix}
  \right)~
  \left(\begin{matrix} x_{1,n}\\ x_{2,n}\\\dots\\\vdots\\ \dots \\ x_{n,n}
  \end{matrix}\right)
  =\left(\begin{matrix} 1\\-1\\1\\-1\\ \vdots\\ (-1)^{n-1}
  \end{matrix}
  \right)
  $$
 The  solution for $n=6$ is  $(21, -70, 105, -84, 35, -6)$.
    Is there a formula for the general solution involving 2 parameters $j$ and $n $ and, may be, binomial coefficients?

REPLY [1 votes]: With help from OEIS A127717 we conjecture that
for $0\le p\lt n$
$$\sum_{k=1}^n k^p (-1)^{k+1}
\sum_{q=k}^n {q-1\choose k-1} q = (-1)^p.$$
This is
$$\sum_{q=1}^n q \sum_{k=1}^q {q-1\choose k-1}
(-1)^{k+1} k^p
= \sum_{q=1}^n q \sum_{k=0}^{q-1} {q-1\choose k}
(-1)^{k} (k+1)^p
\\ = \sum_{q=1}^n q \sum_{k=0}^{q-1} {q-1\choose k}
(-1)^{k} p! [z^p] \exp((k+1)z)
\\ = p! [z^p] \exp(z)
\sum_{q=1}^n q \sum_{k=0}^{q-1} {q-1\choose k}
(-1)^{k}  \exp(kz)
\\ = p! [z^p] \exp(z)
\sum_{q=1}^n q (1-\exp(z))^{q-1}.$$
Now with $(1-\exp(z))^{q-1} = (-1)^{q-1} z^{q-1} + \cdots$ and $n\gt p$
we may certainly extend $q$ to infinity without contributing to $[z^p]$
and we find
$$p! [z^p] \exp(z)
\sum_{q\ge 1} q (1-\exp(z))^{q-1}
\\ = p! [z^p] \exp(z) \frac{1}{(1-(1-\exp(z)))^2}
\\ = p! [z^p] \exp(z) \exp(-2z) = p! [z^p] \exp(-z) = (-1)^p.$$
This is the claim. We see that the desired coefficient is given by
$$\bbox[5px,border:2px solid #00A000]{
x_{k,n} = (-1)^{k+1}
\sum_{q=k}^n {q-1\choose k-1} q.}$$
Remark. A careful examination of the OEIS entry shows that we
can simplify $x_{k,n}.$ We get for the sum
$$\sum_{q=k}^n {q-1\choose k-1} q
= k \sum_{q=k}^n {q\choose k}
= k \sum_{q=0}^{n-k} {q+k\choose k}
\\ = k \sum_{q=0}^{n-k} [z^k] (1+z)^{q+k}
= k [z^k] (1+z)^k \sum_{q=0}^{n-k} (1+z)^q
\\ = k [z^k] (1+z)^k \frac{(1+z)^{n-k+1}-1}{1+z-1}
\\ = k [z^{k+1}] (1+z)^k ((1+z)^{n-k+1}-1)
\\ = k [z^{k+1}] (1+z)^k (1+z)^{n-k+1}
= k [z^{k+1}] (1+z)^{n+1}.$$
We thus have
$$\bbox[5px,border:2px solid #00A000]{
x_{k,n} = (-1)^{k+1}
k {n+1\choose k+1}.}$$