text:
\section{Analysis of \fedacii under \cref{asm1} or \ref{asm2}}
\label{sec:fedacii}
In this section we study the convergence of \fedacii.
We provide a complete, non-asymptotic version of \cref{fedacii:a2} on the convergence of \fedacii under \cref{asm2} and provide the detailed proof, which expands the proof sketch in \cref{sec:proof:sketch:2}.
We also study the convergence of \fedacii under \cref{asm1}, which we defer to the end of this section (see \cref{sec:fedacii:a1}) since the analysis is mostly shared.

Recall that \fedacii is defined as the \fedac algorithm with the following hyperparameter choice:
\begin{equation}
  \eta \in \left(0, \frac{1}{L}\right], \quad  \gamma = \max \left\{ \sqrt{\frac{\eta}{\mu K}}, \eta \right\}, \quad \alpha  = \frac{3}{2 \gamma \mu} - \frac{1}{2}, \quad \beta = \frac{2 \alpha^2 - 1}{\alpha - 1}
\tag{\fedacii}.
\end{equation}
As we discussed in the proof sketch \cref{sec:proof:sketch:2}, for \fedacii, we keep track of the convergence via the ``centralized'' potential $\Phi_t$.
\begin{equation}
  \Phi_t := F( \overline{w_{t}^{\mathrm{ag}}})  - F^* + \frac{1}{6}\mu \|\overline{w_{t}} - w^*\|^2.
  \label{eq:centralied:potential}
\end{equation}
Recall $\overline{w_t}$ is defined as $\frac{1}{M} \sum_{m=1}^M w_t^m$ and $\overline{w_t^{\mathrm{ag}}}$ is defined as $\frac{1}{M} \sum_{m=1}^M w_t^{\mathrm{ag},m}$. We use $\mathcal{F}_t$ to denote the $\sigma$-algebra generated by $\{w_\tau^m, w_\tau^{\mathrm{ag, m}}\}_{\tau \leq t, m \in [M]}$. Since \fedac is Markovian, conditioning on $\mathcal{F}_t$ is equivalent to conditioning on $\{w_t^m, w_t^{\mathrm{ag, m}}\}_{m \in [M]}$.

\subsection{Main theorem and lemmas: Complete version of \cref{fedacii:a2}}
Now we introduce the main theorem on the convergence of \fedacii under \cref{asm2}.
\begin{theorem}[Convergence of \fedacii under \cref{asm2}, complete version of \cref{fedacii:a2}]
  \label{fedacii:a2:full}
  Let $F$ be $\mu > 0$ strongly convex, and assume \cref{asm2}, then for
  \begin{equation}
    \eta := \min \left\{ \frac{1}{L}, \frac{9K}{\mu T^2} \log^2 \left( \euler
     + \min \left\{ \frac{\mu M T \Phi_0}{\sigma^2} + \frac{\mu^2 MT^3 \Phi_0}{LK^2 \sigma^2}, \frac{\mu^5 T^8 \Phi_0}{Q^2 K^6 \sigma^4} \right\} \right) \right\},
  \end{equation}
  \fedacii yields
  \begin{align}
    \expt [\Phi_T] \leq & \min \left\{ \exp \left( - \frac{\mu T}{3 L} \right), \exp \left( - \frac{\mu^{\frac{1}{2}} T}{3 L^{\frac{1}{2}} K^{\frac{1}{2}}} \right)\right\} \Phi_0
    + \frac{4 \sigma^2}{\mu M T} \log \left( \euler + \frac{\mu MT \Phi_0}{\sigma^2} \right)
    \\
    &
    \quad +
    \frac{55 LK^2 \sigma^2}{\mu^2 MT^3} \log^3 \left( \euler + \frac{\mu^2 MT^3 \Phi_0}{LK^2\sigma^2} \right)
    + \frac{\euler^{18} Q^2 K^6 \sigma^4}{\mu^5 T^8} \log^8\left( \euler
    + \frac{\mu^5 T^8 \Phi_0}{Q^2 K^6 \sigma^4} \right),
  \end{align}
  where $\Phi_t$ is the ``centralized'' potential defined in \cref{eq:centralied:potential}.
\end{theorem}
\begin{remark}
  The simplified version \cref{fedacii:a2} in main body can be obtained by replacing $K$ with $T/R$ and upper bound $\Phi_0$ by $LD_0^2$.
\end{remark}

The proof of \cref{fedacii:a2:full} is based on the following two lemmas regarding convergence and stability respectively.
To clarify the hyperparameter dependency, we state our lemma for general $\gamma \in \left[\eta, \sqrt{ \frac{\eta}{\mu}} \right]$, which has one more degree of freedom than \fedacii where $\gamma = \max \left\{ \sqrt{\frac{\eta}{\mu K}}, \eta\right\}$ is fixed.

\begin{lemma}[Potential-based perturbed iterate analysis for \fedacii]
  \label{fedacii:conv:main}
  Let $F$ be $\mu>0$-strongly convex, and assume \cref{asm1}, then for $\alpha = \frac{3}{2 \gamma \mu} - \frac{1}{2}$, $\beta =\frac{2 \alpha^2 - 1}{\alpha - 1}$,
  $\gamma \in \left[\eta, \sqrt{ \frac{\eta}{\mu}}\right]$, $\eta \in (0, \frac{1}{L}]$, \fedac yields

  \begin{equation}
    \expt [\Phi_T] \leq \exp \left( - \frac{1}{3}\gamma \mu T \right) \Phi_0
    + \frac{3\eta^2 L \sigma^2 }{2 \gamma \mu M}
    + \frac{\gamma \sigma^2}{2 M}
    + \frac{3}{\mu} \max_{0 \leq t < T}   \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right],
  \end{equation}

where $\Phi_t$ is the decentralized potential defined in \cref{eq:centralied:potential}.
\end{lemma}
The proof of \cref{fedacii:conv:main} is deferred to \cref{sec:fedacii:conv:main}. Note that \cref{fedacii:conv:main} only requires \cref{asm1} (recall that \cref{asm1} is strictly weaker than \cref{asm2}), which enables us to recycle this Lemma towards the convergence proof of \fedacii under \cref{asm1} (see \cref{sec:fedacii:a1}).

The following lemma studies the discrepancy overhead by \nth{4}-th order stability, which requires \cref{asm2}.
\begin{lemma}[Discrepancy overhead bounds]
  \label{fedacii:stab:main}
  Let $F$ be $\mu>0$-strongly convex, and assume \cref{asm2}, then for the same hyperparameter choice as in \cref{fedacii:conv:main}, \fedac satisfies (for all $t$)
  \begin{align}
     & \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right]
    \leq  \begin{cases}
      44 \eta^4 Q^2 K^2 \sigma^4 \left(1 + \frac{\gamma^2\mu}{\eta}\right)^{4K}
       & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right],
      \\
      44 \eta^4 Q^2 K^2 \sigma^4
       &
      \text{if~} \gamma = \eta.
    \end{cases}
  \end{align}
\end{lemma}
The proof of \cref{fedacii:stab:main} is deferred to \cref{sec:fedacii:stab:main}.

Now we plug in the choice of $\gamma = \max \left\{ \sqrt{\frac{\eta}{\mu K}}, \eta\right\}$ to \cref{fedacii:conv:main,fedacii:stab:main}, which leads to  the following lemma.
\begin{lemma}[Convergence of \fedacii for general $\eta$]
  \label{fedacii:a2:general:eta}
    Let $F$ be $\mu > 0$-strongly convex, and assume \cref{asm2}, then for any $\eta \in (0, \frac{1}{L}]$, \fedacii yields
    \begin{align}
      \expt[\Phi_T]
      \leq & \exp \left(  - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0
      + \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
      + \frac{2 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M}
      + \frac{\euler^9 \eta^4 Q^2 K^2 \sigma^4}{\mu},
      \label{eq:fedacii:a2:general:eta}
    \end{align}
    where $\Phi_t$ is the decentralized potential defined in \cref{eq:centralied:potential}.
\end{lemma}
\begin{proof}[Proof of \cref{fedacii:a2:general:eta}]
  It is direct to verify that $\gamma = \max \left\{\eta, \sqrt{\frac{\eta}{\mu K}} \right\} \in \left[\eta, \sqrt{\frac{\eta}{\mu}}\right]$ so both \cref{fedacii:conv:main,fedacii:stab:main} are applicable.
  Applying \cref{fedacii:conv:main} yields
  \begin{align}
    \expt[\Phi_T] \leq & \exp\left( - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0
    +
    \min\left\{ \frac{3\eta L \sigma^2}{2 \mu M}, \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} \right\}
    \\
                       & + \max\left\{ \frac{\eta \sigma^2}{2M}, \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }          \right\}
    + \frac{3}{\mu} \max_{0 \leq t < T}  \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right].
    \label{eq:fedacii:proof:1}
  \end{align}
  We bound $\min\left\{ \frac{3\eta L \sigma^2}{2 \mu M}, \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} \right\}$ with $\frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M}$, and bound $\max\left\{ \frac{\eta \sigma^2}{2M}, \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }          \right\}$ with $\frac{\eta \sigma^2}{2M} + \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }$.
  By AM-GM inequality and $\mu \leq L$, we have
  \begin{equation}
    \frac{\eta \sigma^2}{2M}
    \leq
    \frac{ \eta^{\frac{3}{2}} \mu^{\frac{1}{2}} K^{\frac{1}{2}} \sigma^2}{4 M} + \frac{ \eta^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    \leq
    \frac{ \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{4\mu^{\frac{1}{2}} M} + \frac{ \eta^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
  \end{equation}
  Thus
  \begin{align}
         & \min\left\{ \frac{3\eta L \sigma^2}{2 \mu M}, \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} \right\}
    + \max\left\{ \frac{\eta \sigma^2}{2M}, \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }          \right\}
    \\
    \leq & \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} + \frac{\eta \sigma^2}{2M} + \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    \leq
    \frac{7 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M} + \frac{3 \eta^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} },
    \label{eq:fedacii:proof:1:1}
  \end{align}

  Applying \cref{fedacii:stab:main} yields (for all $t$)
  \begin{align}
         & \frac{3}{\mu} \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right]
    \leq
    \begin{cases}
      \frac{132}{\mu} \eta^4 Q^2 K^2 \sigma^4  \left(1 + \frac{1}{K}\right)^{4K}
       & \text{if~} \gamma = \sqrt{\frac{\eta}{\mu K}}
      \\
      \frac{132}{\mu} \eta^4 Q^2 K^2 \sigma^4,
       &
      \text{if~} \gamma = \eta
    \end{cases}
    \\
    \leq & 132 \euler^{4} \mu^{-1} \eta^4 Q^2 K^2 \sigma^4 \leq \euler^9 \mu^{-1} \eta^4 Q^2 K^2 \sigma^4,
    \label{eq:fedacii:proof:2}
  \end{align}
  where in the last inequality we used the estimation that $132 \euler^{4} < \euler^9$.

  Combining \cref{eq:fedacii:proof:1,eq:fedacii:proof:1:1,eq:fedacii:proof:2} yields
  \begin{align}
    \expt[\Phi_T]
    \leq & \exp \left(  - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0
    + \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    + \frac{2 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M}
    + \frac{\euler^9 \eta^4 Q^2 K^2 \sigma^4}{\mu}.
  \end{align}
\end{proof}

The main \cref{fedacii:a2:full} then follows by plugging the appropriate $\eta$ to \cref{fedacii:a2:general:eta}.
\begin{proof}[Proof of \cref{fedacii:a2:full}]
  To simplify the notation, we denote the decreasing term in \cref{eq:fedacii:a2:general:eta} in \cref{fedacii:a2:general:eta} as $\varphi_{\downarrow}(\eta)$ and the increasing term as $\varphi_{\uparrow}(\eta)$, namely
  \begin{align}
    \varphi_{\downarrow}(\eta) := \exp \left(  - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0,
    \quad
    \varphi_{\uparrow}(\eta) := \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    + \frac{2 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M}
    + \frac{\euler^9 \eta^4 Q^2 K^2 \sigma^4}{\mu}.
  \end{align}
  Now let
  \begin{equation}
    \eta_0 := \frac{9K}{\mu T^2} \log^2 \left( \euler
     + \min \left\{ \frac{\mu M T \Phi_0}{\sigma^2} + \frac{\mu^2 MT^3 \Phi_0}{LK^2 \sigma^2}, \frac{\mu^5 T^8 \Phi_0}{Q^2 K^6 \sigma^4} \right\} \right)
  \end{equation}
  then $\eta := \min \left\{ \frac{1}{L}, \eta_0 \right\}$. Therefore, the decreasing term $\varphi_{\downarrow}(\eta)$ is upper bounded by $\varphi_{\downarrow}(\frac{1}{L}) + \varphi_{\downarrow}(\eta_0)$, where
  \begin{equation}
    \varphi_{\downarrow} \left(\frac{1}{L} \right)
    \leq
    \min \left\{ \exp \left( - \frac{\mu T}{3 L} \right), \exp \left( - \frac{\mu^{\frac{1}{2}} T}{3 L^{\frac{1}{2}} K^{\frac{1}{2}}} \right)\right\} \Phi_0,
    \label{eq:fedacii:a2:1}
  \end{equation}
  and
  \begin{align}
    \varphi_{\downarrow}(\eta_0)
    \leq & \exp \left(  - \frac{1}{3} \sqrt{\frac{\eta_0 \mu}{K}} T \right) \Phi_0
    =
    \left( \euler
     + \min \left\{ \frac{\mu M T \Phi_0}{\sigma^2} + \frac{\mu^2 MT^3 \Phi_0}{LK^2 \sigma^2}, \frac{\mu^5 T^8 \Phi_0}{Q^2 K^6 \sigma^4} \right\} \right)^{-1} \Phi_0
    \\
    \leq & \frac{\sigma^2}{\mu MT} + \frac{LK^2 \sigma^2}{\mu^2 MT^3} + \frac{Q^2 K^6 \sigma^4}{\mu^5 T^8}.
    \label{eq:fedacii:a2:2}
  \end{align}
  On the other hand
  \begin{align}
    \varphi_{\uparrow}(\eta)  \leq \varphi_{\uparrow}(\eta_0)
    \leq
    &
    \frac{3 \sigma^2}{\mu M T} \log \left( \euler + \frac{\mu MT \Phi_0}{\sigma^2} \right)
    +
    \frac{54 LK^2 \sigma^2}{\mu^2 MT^3} \log^3 \left( \euler + \frac{\mu^2 MT^3 \Phi_0}{LK^2\sigma^2} \right)
    \\
    & + \frac{9^4 \euler^9 Q^2 K^6 \sigma^4}{\mu^5 T^8} \log^8\left( \euler
    + \frac{\mu^5 T^8 \Phi_0}{Q^2 K^6 \sigma^4} \right).
    \label{eq:fedacii:a2:3}
  \end{align}
  Combining \cref{fedacii:a2:general:eta,eq:fedacii:a2:1,eq:fedacii:a2:2,eq:fedacii:a2:3} gives
  \begin{align}
    & \expt[\Phi_T] \leq \varphi_{\downarrow} \left(\frac{1}{L} \right) + \varphi_{\downarrow}(\eta_0) + \varphi_{\uparrow}(\eta_0)
    \\
    \leq & \min \left\{ \exp \left( - \frac{\mu T}{3 L} \right), \exp \left( - \frac{\mu^{\frac{1}{2}} T}{3 L^{\frac{1}{2}} K^{\frac{1}{2}}} \right)\right\} \Phi_0
    + \frac{4 \sigma^2}{\mu M T} \log \left( \euler + \frac{\mu MT \Phi_0}{\sigma^2} \right)
    \\
    &
    +
    \frac{55 LK^2 \sigma^2}{\mu^2 MT^3} \log^3 \left( \euler + \frac{\mu^2 MT^3 \Phi_0}{LK^2\sigma^2} \right)
    + \frac{\euler^{18} Q^2 K^6 \sigma^4}{\mu^5 T^8} \log^8\left( \euler
    + \frac{\mu^5 T^8 \Phi_0}{Q^2 K^6 \sigma^4} \right),
  \end{align}
  where in the last inequality we used the estimate $9^4 \euler^9 + 1 < \euler^{18}$.
\end{proof}

\subsection{Perturbed iterate analysis for \fedacii: Proof of \cref{fedacii:conv:main}}
\label{sec:fedacii:conv:main}
In this subsection we will prove \cref{fedacii:conv:main}.
We start by the one-step analysis of the centralized potential defined in \cref{eq:centralied:potential}.
The following two propositions establish the one-step analysis of the two quantities in $\Phi_t$, namely $\|\overline{w_{t}} - w^*\|^2$ and $F( \overline{w_{t}^{\mathrm{ag}}}) - F^*$.
We only require minimal hyperparameter assumptions, namely $\alpha \geq 1, \beta \geq 1, \eta \leq \frac{1}{L}$ for these two propositions.
We will then show how the choice of $\alpha, \beta$ are determined towards the proof of \cref{fedacii:conv:main} in order to couple the two quantities into potential $\Phi_t$.

\begin{proposition}
  \label{fedacii:conv:1}
  Let $F$ be $\mu>0$-strongly convex, and assume \cref{asm1}, then for \fedac with hyperparameters assumptions $\alpha \geq 1$, $\beta \geq 1$, $\eta \leq \frac{1}{L}$, the following inequality holds
  \begin{align}
         & \expt [ \|\overline{w_{t+1}} - w^*\|^2 |\mathcal{F}_t]
    \\
    \leq & \left( 1 - \frac{1}{2} \alpha^{-1} \right)\|\overline{w_t} - w^*\|^2 + \frac{3}{2} \alpha^{-1} \| \overline{w_t^{\mathrm{md}}} - w^*\|^2 + \frac{3}{2} \gamma^2  \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) \right\|^2
    \\
         & - 2 \gamma  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , (1-\alpha^{-1}(1-\beta^{-1})) \overline{w_t} + \alpha^{-1} (1 - \beta^ {-1}) \overline{w_t^{\mathrm{ag}}} - w^*\right\rangle
    \\
         &
    + \gamma^2 \left( 1 + 2 \alpha \right)  \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) - \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\|^2
    +  \frac{\gamma^2 \sigma^2}{M}.
    \label{eq:fedacii:conv:1}
  \end{align}
\end{proposition}

\begin{proposition}
  \label{fedacii:conv:2}
  In the same setting of \cref{fedacii:conv:1}, the following inequality holds
  \begin{align}
         & \expt \left[F( \overline{w_{t+1}^{\mathrm{ag}}}) - F^*| \mathcal{F}_t \right]
    \\
    \leq & \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{ag}}}) - F^* \right) - \frac{1}{4} \mu \alpha^{-1} \left\|  \overline{w_{t}^{\mathrm{md}}} - w^*  \right\|^2 - \frac{1}{2} \eta \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2
    \\
         & + {\frac{1}{2} \alpha^{-1} \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), 2 \alpha \beta^{-1} \overline{w_t} + (1 - 2 \alpha \beta^{-1}) \overline{w_t^{\mathrm{ag}}} -  w^* \right\rangle}
    \\
         & + \frac{1}{2}  \eta \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 +  \frac{\eta^2 L \sigma^2 }{2M}.
    \label{eq:fedacii:conv:2}
  \end{align}
\end{proposition}
We defer the proofs of \cref{fedacii:conv:1,fedacii:conv:2} to \cref{sec:proof:fedacii:conv:1,sec:proof:fedacii:conv:2}, respectively.

Now we are ready to prove \cref{fedacii:conv:main}.
\begin{proof}[Proof of \cref{fedacii:conv:main}]
  Since $\gamma \leq \sqrt{\frac{\eta}{\mu}} \leq \sqrt{\frac{1}{\mu L}} \leq \frac{1}{\mu}$, we have $\alpha = \frac{3}{2 \gamma \mu} - \frac{1}{2} \geq 1$, and therefore $\beta = \frac{2 \alpha^2 - 1}{\alpha - 1} \geq 1$. Hence both \cref{fedacii:conv:1,fedacii:conv:2} are applicable.

  Adding \cref{eq:fedacii:conv:2} with $\frac{1}{6} \mu$ times of \cref{eq:fedacii:conv:1} gives (note that the $\|\overline{w_t^{\mathrm{md}}} - w^*\|^2$ term is cancelled because $\frac{1}{4}\mu \alpha^{-1} = \frac{1}{6} \mu \cdot \frac{3}{2}\alpha^{-1}$)
  \begin{align}
     & \expt \left[ \Phi_{t+1} |\mathcal{F}_t \right]
     \leq
    \underbrace{\left( 1 - \frac{1}{2} \alpha^{-1} \right) \Phi_t}_{\text{(I)}}
    +
    \underbrace{\left( \frac{1}{4} \gamma^2 \mu  - \frac{1}{2} \eta  \right) \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2}_{\text{(II)}}
    \\
     & \quad +
    \underbrace{\frac{1}{2} \alpha^{-1} \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), 2 \alpha \beta^{-1} \overline{w_t} + (1 - 2 \alpha \beta^{-1}) \overline{w_t^{\mathrm{ag}}} -  w^* \right\rangle}_{\text{(III)}}
    \\
     & \quad -
    \underbrace{\frac{1}{3} \gamma \mu \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , (1-\alpha^{-1}(1-\beta^{-1})) \overline{w_t} + \alpha^{-1} (1 - \beta^ {-1}) \overline{w_t^{\mathrm{ag}}} - w^*\right\rangle}_{\text{(IV)}}
    \\
     & \quad +
    \underbrace{\left( \frac{1}{2}  \eta  + \frac{1}{6} \gamma^2 \mu (1 + 2 \alpha)  \right) \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2}_{\text{(V)}}
    +  \frac{\eta^2 L \sigma^2 }{2M} + \frac{\gamma^2 \mu \sigma^2}{6 M}.
    \label{eq:fedacii:conv:main:1}
  \end{align}

  Now we analyze the RHS of \cref{eq:fedacii:conv:main:1} term by term.
  \paragraph{Term (I) of \cref{eq:fedacii:conv:main:1}}
  Note that $\alpha^{-1} = \frac{2 \gamma \mu}{3 - \gamma \mu} \geq \frac{2}{3}\gamma \mu$, we have
  \begin{equation}
    \left( 1 - \frac{1}{2} \alpha^{-1} \right) \Phi_t \leq \left( 1 - \frac{1}{3} \gamma \mu \right) \Phi_t.
    \label{eq:fedacii:conv:main:2}
  \end{equation}

  \paragraph{Term (II) of \cref{eq:fedacii:conv:main:1}}
  Since $\gamma^2 \mu \leq \eta$ we have
  \begin{equation}
    \left( \frac{1}{4} \gamma^2 \mu  - \frac{1}{2} \eta  \right) \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2 \leq 0.
    \label{eq:fedacii:conv:main:3}
  \end{equation}

  \paragraph{Term (III) and (IV) of \cref{eq:fedacii:conv:main:1}}
  Since $\beta =\frac{2 \alpha^2 - 1}{\alpha - 1}$, we have $2 \alpha \beta^{-1} = \frac{2 \alpha (\alpha - 1)}{2 \alpha^2 - 1} = (1 - \alpha^{-1} (1 - \beta^{-1}))$, and $1 - 2\alpha\beta^{-1} = \frac{2 \alpha - 1}{2 \alpha^2 - 1} = \alpha^{-1}(1 - \beta^{-1})$. Therefore, the two inner-product terms are cancelled:
  \begin{align}
      & \frac{1}{2} \alpha^{-1} \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), 2 \alpha \beta^{-1} \overline{w_t} + (1 - 2 \alpha \beta^{-1}) \overline{w_t^{\mathrm{ag}}} -  w^* \right\rangle
    \\
      & \qquad - \frac{1}{3} \gamma \mu \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , (1-\alpha^{-1}(1-\beta^{-1})) \overline{w_t} + \alpha^{-1} (1 - \beta^ {-1}) \overline{w_t^{\mathrm{ag}}} - w^*\right\rangle
    \\
    = & \left( \frac{1}{2} \alpha^{-1} - \frac{1}{3} \gamma \mu  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \right)   \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , \frac{2 \alpha - 1}{2 \alpha^2 - 1} \overline{w_t^{\mathrm{ag}}} + \left(\frac{2 \alpha^2 - 2 \alpha}{2 \alpha^2 - 1}  \right) \overline{w_t}  - w^*\right\rangle
    \\
    = & \left( \frac{\gamma \mu}{3 - \gamma \mu} - \frac{1}{3} \gamma \mu  \left( 1 + \frac{\gamma \mu}{3 - \gamma \mu} \right) \right)   \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , \frac{2 \alpha - 1}{2 \alpha^2 - 1} \overline{w_t^{\mathrm{ag}}} + \left(\frac{2 \alpha^2 - 2 \alpha}{2 \alpha^2 - 1}  \right) \overline{w_t}  - w^*\right\rangle
    \tag{since $\alpha^{-1} = \frac{2 \gamma \mu}{3 - \gamma \mu}$}
    \\
    = & 0.
    \label{eq:fedacii:conv:main:4}
  \end{align}

  \paragraph{Term (V) of \cref{eq:fedacii:conv:main:1}} Since $\alpha = \frac{3 - \gamma \mu}{2 \gamma \mu}$ and $\gamma \geq \eta$ we have
  \begin{equation}
    \left( \frac{1}{2}  \eta  + \frac{1}{6} \gamma^2 \mu (1 + 2 \alpha)  \right)
    = \frac{1}{2} \eta + \frac{1}{6} \gamma^2 \mu \left( \frac{6}{2 \gamma \mu}  \right)
    = \frac{1}{2}(\eta + \gamma) \leq \gamma.
    \label{eq:fedacii:conv:main:5}
  \end{equation}

  Plugging \cref{eq:fedacii:conv:main:2,eq:fedacii:conv:main:3,eq:fedacii:conv:main:4,eq:fedacii:conv:main:5} to \cref{eq:fedacii:conv:main:1} gives
  \begin{equation}
    \expt \left[\Phi_{t+1} \middle| \mathcal{F}_t \right] \leq \left( 1 - \frac{1}{3}\gamma\mu \right) \Phi_{t} +  \frac{\eta^2 L \sigma^2 }{2M} + \frac{\gamma^2 \mu \sigma^2}{6 M}
    + \gamma  \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2.
    \label{eq:fedacii:conv:main:6}
  \end{equation}
  Telescoping the above inequality up to timestep $T$ yields
  \begin{align}
    \expt \left[\Phi_T \right]
    \leq & \left( 1 - \frac{1}{3} \gamma \mu \right)^T \Phi_0 +
    \left( \sum_{t=0}^{T-1} \left( 1 - \frac{1}{3} \gamma \mu \right)^t \right) \cdot \left( \frac{\eta^2 L \sigma^2 }{2M} + \frac{\gamma^2 \mu \sigma^2}{6 M} \right)
    \\
         & + \gamma  \sum_{t=0}^{T-1}  \left( 1 - \frac{1}{3}\gamma\mu \right)^{T-t-1}  \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right]
    \\
    \leq & \exp \left( - \frac{1}{3} \gamma \mu T \right) \Phi_0 +  \left( \frac{3\eta^2 L \sigma^2 }{2 \gamma \mu M} + \frac{\gamma \sigma^2}{2 M} \right)
    + \frac{3}{\mu}  \cdot \max_{0 \leq t < T}   \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right],
  \end{align}
  where in the last inequality we used the fact that $(1 - \frac{1}{3}\gamma \mu)^T \leq \exp(- \frac{1}{3}\gamma \mu T)$ and $\sum_{t=0}^{T-1} \left( 1 - \frac{1}{3}\gamma \mu \right)^t  \leq \sum_{t=0}^{T-1} \left( 1 - \frac{1}{3}\gamma \mu \right)^{\infty} = \frac{3}{\gamma \mu}$.
\end{proof}

\subsubsection{Proof of \cref{fedacii:conv:1}}
\label{sec:proof:fedacii:conv:1}
\begin{proof}[Proof of \cref{fedacii:conv:1}]
  By definition of the \fedac procedure (\cref{alg:fedac}),
  \begin{equation}
    \overline{w_{t+1}} - w^* = (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - \gamma \cdot \frac{1}{M} \sum_{m=1}^M \nabla f(w_t^{\mathrm{md},m}; \xi_t^m) - w^*.
  \end{equation}
  Taking conditional expectation gives
  \begin{equation}
    \expt \left[ \|\overline{w_{t+1}} - w^*\|^2 \middle| \mathcal{F}_t \right]
    \leq
    \left\| (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - \gamma \cdot \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md},m})- w^* \right\|^2
    + \frac{1}{M}\gamma^2 \sigma^2.
    \label{eq:fedacii:conv:1:0}
  \end{equation}
  The squared norm in \cref{eq:fedacii:conv:1:0} is bounded as
  \begin{align}
         & \left\| (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - \gamma \cdot \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md},m})- w^* \right\|^2
    \\
    =    & \left\| (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - \gamma \nabla F (\overline{w_t^{\mathrm{md}}}) - w^*
    + \gamma \left(  \nabla F (\overline{w_t^{\mathrm{md}}}) - \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}}) \right)\right\|^2
    \\
    \leq & {\left( 1 + \frac{1}{2} \alpha^{-1} \right)} \left\|  (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - w^* - \gamma \nabla F (\overline{w_t^{\mathrm{md}}}) \right\|^2
    \\
         & + \gamma^2  {\left( 1 + 2 \alpha \right)} \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) - \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\|^2
    \tag{apply helper \cref{helper:unbalanced:ineq} with $\zeta = \frac{1}{2}\alpha^{-1}$}
    \\
    =    & \underbrace{\left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\| (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - w^* \right\|^2}_{\text{(I)}}
    + \underbrace{\gamma^2  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) \right\|^2}_{\text{(II)}}
    \\
         & \underbrace{- 2 \gamma  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}), (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - w^*\right\rangle}_{\text{(III)}}
    \\
         & + \gamma^2 \left( 1 + 2 \alpha \right)  \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) - \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\|^2.
    \label{eq:fedacii:conv:1:1}
  \end{align}

  The first term (I) of \cref{eq:fedacii:conv:1:1} is bounded via Jensen's inequality as follows:
  \begin{align}
         & \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\| (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - w^* \right\|^2
    \\
    \leq & \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left( (1 - \alpha^{-1}) \|\overline{w_t} - w^*\|^2 + \alpha^{-1} \| \overline{w_t^{\mathrm{md}}} - w^*\|^2 \right) \tag{Jensen's inequality}\
    \\
    \leq & \left( 1 - \frac{1}{2} \alpha^{-1} \right)\|\overline{w_t} - w^*\|^2 + \frac{3}{2} \alpha^{-1} \| \overline{w_t^{\mathrm{md}}} - w^*\|^2.
    \label{eq:fedacii:conv:1:2}
  \end{align}
  where in the last inequality of \cref{eq:fedacii:conv:1:2} we used the fact that $( 1 + \frac{1}{2} \alpha^{-1})(1 - \alpha^{-1}) = 1 - \frac{1}{2} \alpha^{-1} - \frac{1}{2} \alpha^{-2} < 1 - \frac{1}{2} \alpha^{-1}$, and $( 1 + \frac{1}{2} \alpha^{-1}) \alpha^{-1} \leq \frac{3}{2}\alpha^{-1}$ as $\alpha \geq 1$.

  The second term (II) of \cref{eq:fedacii:conv:1:1} is bounded as (since $\alpha \geq 1$)
  \begin{equation}
    \gamma^2  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) \right\|^2 \leq \frac{3}{2} \gamma^2  \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) \right\|^2.
    \label{eq:fedacii:conv:1:3}
  \end{equation}

  To analyze the third term (III) of \cref{eq:fedacii:conv:1:1}, we note that by definition of $\overline{w_t^{\mathrm{md}}}$,
  \begin{align}
      & - 2 \gamma  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}), (1 - \alpha^{-1}) \overline{w_t} + \alpha^{-1} \overline{w_t^{\mathrm{md}}} - w^*\right\rangle
    \\
    = & - 2 \gamma  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , (1-\alpha^{-1}(1-\beta^{-1})) \overline{w_t} + \alpha^{-1} (1 - \beta^ {-1}) \overline{w_t^{\mathrm{ag}}} - w^*\right\rangle.
    \label{eq:fedacii:conv:1:4}
  \end{align}
  Plugging \cref{eq:fedacii:conv:1:1,eq:fedacii:conv:1:2,eq:fedacii:conv:1:3,eq:fedacii:conv:1:4} back to \cref{eq:fedacii:conv:1:0} yields
  \begin{align}
         & \expt [ \|\overline{w_{t+1}} - w^*\|^2 |\mathcal{F}_t]
    \\
    \leq & \left( 1 - \frac{1}{2} \alpha^{-1} \right)\|\overline{w_t} - w^*\|^2 + \frac{3}{2} \alpha^{-1} \| \overline{w_t^{\mathrm{md}}} - w^*\|^2 + \frac{3}{2}\gamma^2  \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) \right\|^2
    \\
         & - 2 \gamma  \left( 1 + \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F (\overline{w_t^{\mathrm{md}}}) , (1-\alpha^{-1}(1-\beta^{-1})) \overline{w_t} + \alpha^{-1} (1 - \beta^ {-1}) \overline{w_t^{\mathrm{ag}}} - w^*\right\rangle
    \\
         &
    + \gamma^2 \left( 1 + 2 \alpha \right)  \left\| \nabla F (\overline{w_t^{\mathrm{md}}}) - \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\|^2
    +  \frac{\gamma^2 \sigma^2}{M},
  \end{align}
  completing the proof of \cref{fedacii:conv:1}.
\end{proof}

\subsubsection{Proof of \cref{fedacii:conv:2}}
\label{sec:proof:fedacii:conv:2}
\begin{proof}[Proof of \cref{fedacii:conv:2}]
  By definition of the \fedac procedure we have
  \begin{equation}
    \overline{w_{t+1}^{\mathrm{ag}}}
    =
    \overline{w_t^{\mathrm{md}}} - \eta \cdot \frac{1}{M} \sum_{m=1}^M \nabla f(w_t^{\mathrm{md},m}; \xi_t^m),
  \end{equation}
  and thus by $L$-smoothness (\cref{asm1}(b)) we obtain
  \begin{equation}
    F( \overline{w_{t+1}^{\mathrm{ag}}})
    \leq
    F(\overline{w_t^{\mathrm{md}}}) - \eta \left\langle \nabla F(\overline{w_t^{\mathrm{md}}}), \frac{1}{M} \sum_{m=1}^M \nabla f(w_t^{\mathrm{md},m}; \xi_t^m) \right\rangle + \frac{\eta^2 L}{2} \left\| \frac{1}{M} \sum_{m=1}^M \nabla f(w_t^{\mathrm{md},m}; \xi_t^m)  \right\|^2.
  \end{equation}
  Taking conditional expectation, and by bounded variance (\cref{asm1}(c))
  \begin{equation}
    \expt \left[F( \overline{w_{t+1}^{\mathrm{ag}}}) |\mathcal{F}_t \right]
    \leq  F(\overline{w_t^{\mathrm{md}}})
    - \eta \left\langle \nabla F(\overline{w_t^{\mathrm{md}}}), \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\rangle + \frac{\eta^2 L}{2} \left\| \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 + \frac{\eta^2 L \sigma^2 }{2M}.
    \label{eq:fedacii:conv:2:0:1}
  \end{equation}
  By polarization identity we have
  \begin{align}
    & \left\langle \nabla F(\overline{w_t^{\mathrm{md}}}), \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\rangle
    \\
    = &
    \frac{1}{2}
    \left( \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2 + \left\| \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m}) \right\|^2 - \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right).
    \label{eq:fedacii:conv:2:0:2}
  \end{align}
  Combining \cref{eq:fedacii:conv:2:0:1,eq:fedacii:conv:2:0:2} gives
  \begin{align}
         & \expt \left[F( \overline{w_{t+1}^{\mathrm{ag}}}) |\mathcal{F}_t \right]
    \\
    =    & F(\overline{w_t^{\mathrm{md}}}) - \frac{1}{2} \eta \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2
    + \frac{1}{2} \eta \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
    \\
         & - \frac{1}{2} \eta (1 - \eta L) \left\| \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 +  \frac{\eta^2 L \sigma^2 }{2M}
    \\
    \leq & F(\overline{w_t^{\mathrm{md}}}) - \frac{1}{2} \eta \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2 \
    + \frac{1}{2}  \eta \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 +  \frac{\eta^2 L \sigma^2 }{2M},
    \label{eq:fedacii:conv:2:1}
  \end{align}
  where the last inequality is due to the assumption that $\eta \leq \frac{1}{L}$.

  Now we relate $F( \overline{w_{t}^{\mathrm{md}}})$ and $F( \overline{w_{t}^{\mathrm{ag}}})$ as follows
  \begin{align}
         & F(\overline{w_t^{\mathrm{md}}})  - F^*
    \\
    =    & \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{ag}}}) - F^* \right)
    + \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{md}}}) - F(\overline{w_{t}^{\mathrm{ag}}}) \right)
    + \frac{1}{2} \alpha^{-1} \left(F(\overline{w_{t}^{\mathrm{md}}}) - F^* \right)
    \\
    \leq & \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{ag}}}) - F^* \right)
    + \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), \overline{w_{t}^{\mathrm{md}}} - \overline{w_{t}^{\mathrm{ag}}} \right\rangle
    \\
         & + \frac{1}{2} \alpha^{-1}
    \left( \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), \overline{w_{t}^{\mathrm{md}}} - w^* \right\rangle  - \frac{\mu}{2}  \left\|  \overline{w_{t}^{\mathrm{md}}} - w^*  \right\|^2 \right)
    \tag{$\mu$-strong convexity}
    \\
    =    & \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{ag}}}) - F^* \right) - \frac{1}{4} \mu \alpha^{-1} \left\|  \overline{w_{t}^{\mathrm{md}}} - w^*  \right\|^2
    \\
         &
    + {\frac{1}{2} \alpha^{-1} \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), 2 \alpha \overline{w_t^{\mathrm{md}}} - (2 \alpha - 1) \overline{w_t^{\mathrm{ag}}} -  w^* \right\rangle}
    \tag{rearranging}
    \\
    =    & \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{ag}}}) - F^* \right) - \frac{1}{4} \mu \alpha^{-1} \left\|  \overline{w_{t}^{\mathrm{md}}} - w^*  \right\|^2
    \\
         &
    + {\frac{1}{2} \alpha^{-1} \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), 2 \alpha \beta^{-1} \overline{w_t} + (1 - 2 \alpha \beta^{-1}) \overline{w_t^{\mathrm{ag}}} -  w^* \right\rangle},
    \label{eq:fedacii:conv:2:2}
  \end{align}
  where the last equality is due to the definition of $\overline{w_t^{\mathrm{md}}}$.

  Plugging \cref{eq:fedacii:conv:2:2} back to \cref{eq:fedacii:conv:2:1} yields
  \begin{align}
         & \expt \left[F( \overline{w_{t+1}^{\mathrm{ag}}})  - F^* \middle|\mathcal{F}_t \right]
    \\
    \leq & \left( 1 - \frac{1}{2} \alpha^{-1} \right) \left(F(\overline{w_{t}^{\mathrm{ag}}}) - F^* \right) - \frac{1}{4} \mu \alpha^{-1} \left\|  \overline{w_{t}^{\mathrm{md}}} - w^*  \right\|^2 - \frac{1}{2} \eta \left\| \nabla F(\overline{w_t^{\mathrm{md}}}) \right\|^2
    \\
         & + {\frac{1}{2} \alpha^{-1} \left\langle \nabla F(\overline{w_{t}^{\mathrm{md}}}), 2 \alpha \beta^{-1} \overline{w_t} + (1 - 2 \alpha \beta^{-1}) \overline{w_t^{\mathrm{ag}}} -  w^* \right\rangle}
    + \frac{1}{2}  \eta \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 +  \frac{\eta^2 L \sigma^2 }{2M},
  \end{align}
  completing the proof of \cref{fedacii:conv:2}.
\end{proof}

\subsection{Discrepancy overhead bound for \fedacii: Proof of \cref{fedacii:stab:main}}
\label{sec:fedacii:stab:main}
In this subsection we prove \cref{fedacii:stab:main} regarding the regarding the growth of discrepancy overhead introduced in \cref{fedacii:conv:main}. The core of the proof is the \nth{4}-order stability of \fedacii.
Note that most of the analysis in this subsection follows closely with the analysis on \fedaci (see \cref{sec:fedaci:stab:main}), but the analysis is technically more complicated.

We will reuse a set of notations defined in \cref{sec:fedaci:stab:main}, which we restate here for clearance. Let $m_1, m_2 \in [M]$ be two arbitrary distinct machines. For any timestep $t$, denote $\Delta_{t} := w_{t}^{m_1} - w_t^{m_2}$,  $\Delta_t^{\mathrm{ag}} := w_{t}^{\mathrm{ag}, m_1} - w_t^{\mathrm{ag}, m_2}$ and $\Delta_t^{\mathrm{md}} := w_{t}^{\mathrm{md}, m_1} - w_t^{\mathrm{md}, m_2}$ be the corresponding vector differences. Let $\Delta_t^{\varepsilon} = \varepsilon_t^{m_1} - \varepsilon_t^{m_2}$, where $\varepsilon_t^m := \nabla f(w_t^{\mathrm{md},m}; \xi_t^m) - \nabla F(w_t^{\mathrm{md}, m})$ be the bias of the gradient oracle of the $m$-th worker evaluated at $w_t^{\mathrm{md}}$.

The proof of \cref{fedacii:stab:main} is based on the following propositions.

The following \cref{fedacii:stab:1} studies the growth of $\begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\ \Delta_{t} \end{bmatrix}$ at each step.
\cref{fedacii:stab:1} is analogous to \cref{fedaci:stab:1}, but the $\mathcal{A}$ is different. Note that \cref{fedacii:stab:1} requires only \cref{asm1}.
\begin{proposition}
  \label{fedacii:stab:1}
  Let $F$ be $\mu>0$-strongly convex, assume \cref{asm1} and assume the same hyperparameter choice is taken as in  \cref{fedacii:stab:main} (namely $\alpha = \frac{3}{2 \gamma \mu} - \frac{1}{2}$, $\beta =\frac{2 \alpha^2 - 1}{\alpha - 1}$, $\gamma \in [\eta, \sqrt{ \frac{\eta}{\mu}}]$, $\eta \in (0, \frac{1}{L}]$).
  Suppose $t+1$ is not a synchronization gap, then there exists a matrix $H_t$ such that $\mu I \preceq H_t \preceq LI$ satisfying
  \begin{equation}
    \begin{bmatrix}
      \Delta_{t+1}^{\mathrm{ag}} \\ \Delta_{t+1}
    \end{bmatrix}
    =
    \mathcal{A} (\mu, \gamma, \eta, H_t)
    \begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\ \Delta_{t} \end{bmatrix}
    -
    \begin{bmatrix} \eta I \\ \gamma I \end{bmatrix}
    \Delta_t^{\varepsilon},
  \end{equation}
  where $\mathcal{A}(\mu, \gamma, \eta, H)$ is a matrix-valued function defined as
  \begin{equation}
    \mathcal{A}(\mu, \gamma, \eta, H) = \frac{1}{9 - \gamma \mu (6 + \gamma \mu)}
    \begin{bmatrix}
      (3 - \gamma \mu)(3 - 2\gamma \mu)(I - \eta H)
       & 3 \gamma \mu (1 - \gamma \mu) (I - \eta H)
      \\
      (3 - 2 \gamma \mu) (2 \gamma \mu - (3 - \gamma \mu) \gamma H)
       &
      3 (1 - \gamma \mu) ((3 - \gamma \mu)I - \gamma^2 \mu H)
    \end{bmatrix}.
    \label{eq:fedacii:A:def}
  \end{equation}
\end{proposition}
The proof of \cref{fedacii:stab:1} is almost identical with \cref{fedaci:stab:1} except the choice of $\alpha$ and $\beta$ are different. We include this proof in \cref{sec:fedacii:stab:1} for completeness.

The following \cref{fedacii:stab:bound} studies the uniform norm bound of $\mathcal{A}$ under the proposed transformation $\mathcal{X}$. The transformation $\mathcal{X}$ is the same as the one studied in \fedaci, which we restate here for the ease of reference.
The bound is also similar to the corresponding bound for on \fedaci as shown in \cref{fedaci:stab:bound}, though the proof is technically more complicated due to the complexity of $\mathcal{A}$.
We defer the proof of  \cref{fedacii:stab:bound} to \cref{sec:fedacii:stab:bound}.
\begin{proposition}[Uniform norm bound of $\mathcal{A}$ under transformation $\mathcal{X}$]
  \label{fedacii:stab:bound}
  Let $\mathcal{A}(\mu, \gamma, \eta, H)$ be defined as in \cref{eq:fedacii:A:def}.
  and assume $\mu > 0$, $\gamma \in [\eta, \sqrt{\frac{\eta}{\mu}}]$, $\eta \in (0,\frac{1}{L}]$.
  Then the following uniform norm bound holds
  \begin{equation}
    \sup_{\mu I \preceq H \preceq LI}
    \left\| \mathcal{X}(\gamma, \eta)^{-1} \mathcal{A}(\mu, \gamma, \eta, H) \mathcal{X}(\gamma, \eta) \right\| \leq
    \begin{cases}
      1 + \frac{\gamma^2 \mu}{\eta} & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}}\right], \\
      1                              & \text{if~} \gamma =  \eta,
    \end{cases}
  \end{equation}
  where $\mathcal{X} (\gamma, \eta)$ is a matrix-valued function defined as
  \begin{equation}
    \mathcal{X}(\gamma, \eta) :=
    \begin{bmatrix}
      \frac{\eta}{\gamma} I & 0
      \\
      I                     & I
    \end{bmatrix}.
    \label{eq:fedacii:X:def}
  \end{equation}
\end{proposition}

\cref{fedacii:stab:1,fedacii:stab:bound} suggest the one-step growth of $ \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
  \Delta_{t}^{\mathrm{ag}}
  \\
  \Delta_{t}
\end{bmatrix}  \right\|^4$ as follows.
\begin{proposition}
  \label{fedacii:stab:2}
  In the same setting of \cref{fedacii:stab:main}, the following inequality holds (for all possible $t$)
  \begin{equation}
    \sqrt{
      \expt \left[ \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
        \Delta_{t+1}^{\mathrm{ag}}
        \\
        \Delta_{t+1}
      \end{bmatrix}  \right\|^4 \middle| \mathcal{F}_t \right]
    }
    \leq
    7 \gamma^2 \sigma^2 +
    \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^2
    \cdot
    \begin{cases}
      \left(1 + \frac{\gamma^2 \mu}{\eta} \right)^2 & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}}\right], \\
      1                                              & \text{if~} \gamma =  \eta,
    \end{cases}
  \end{equation}
  where $\mathcal{X}$ is the matrix-valued function defined in \cref{eq:fedacii:X:def}.
\end{proposition}
We defer the proof of \cref{fedacii:stab:2} to \cref{sec:fedacii:stab:2}.

The following \cref{fedacii:stab:3} links the discrepancy overhead we wish to bound for \cref{fedacii:stab:main} with the quantity analyzed in \cref{fedacii:stab:2} via \nth{3}-order-smoothness (\cref{asm2}(a)).
The proof of \cref{fedacii:stab:3} is deferred to \cref{sec:fedacii:stab:3}.
\begin{proposition}
  \label{fedacii:stab:3}
  In the same setting of \cref{fedacii:stab:main}, the following inequality holds (for all possible $t$)
  \begin{equation}
    \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
    \leq
    \frac{289 \eta^4 Q^2}{324 \gamma^4} \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^4,
  \end{equation}
  where $\mathcal{X}$ is the matrix-valued function defined in \cref{eq:fedacii:X:def}.
\end{proposition}

We are ready to complete the proof of \cref{fedacii:stab:main}.
\begin{proof}[Proof of \cref{fedacii:stab:main}]
  Let $t_0$ be the latest synchronized step prior to $t$. Applying \cref{fedacii:stab:2} gives
  \begin{align}
    & \sqrt{
      \expt \left[ \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
        \Delta_{t+1}^{\mathrm{ag}}
        \\
        \Delta_{t+1}
      \end{bmatrix}  \right\|^4 \middle| \mathcal{F}_{t_0} \right]
    }
    \\
    \leq & 7 \gamma^2 \sigma^2 +
    \sqrt{
    \expt \left[
    \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^2 \middle| \mathcal{F}_{t_0}\right]}
    \cdot
    \begin{cases}
      \left(1 + \frac{\gamma^2 \mu}{\eta} \right)^2 & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}}\right], \\
      1                                              & \text{if~} \gamma =  \eta.
    \end{cases}
  \end{align}
  Telescoping from $t_0$ to $t$ gives (note that $\Delta_{t_0}^{\mathrm{ag}} = \Delta_{t_0} = 0$)
  \begin{align}
    \expt \left[ \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
     \\
      \Delta_{t}
    \end{bmatrix}  \right\|^4 \middle| \mathcal{F}_{t_0} \right]
  & \leq
  49 \gamma^4 \sigma^4 (t - t_0)^2
  \cdot
  \begin{cases}
    \left( 1 + \frac{\gamma^2 \mu}{\eta} \right)^{4(t-t_0)} & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right], \\
    1                              & \text{if~} \gamma =  \eta
  \end{cases}
  \\
  & \leq
  49 \gamma^4 \sigma^4 K^2
  \cdot
  \begin{cases}
    \left( 1 + \frac{\gamma^2 \mu}{\eta} \right)^{4K} & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right], \\
    1                              & \text{if~} \gamma =  \eta,
  \end{cases}
  \end{align}
  where the last inequality is due to $t - t_0 \leq K$ since $K$ is the maximum synchronization interval.

  Consequently, by \cref{fedacii:stab:3} we have
  \begin{align}
    &
    \expt \left[  \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \middle| \mathcal{F}_{t_0}  \right]
    \leq \frac{289 \eta^4 Q^2}{324 \gamma^4} \expt \left[ \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
     \\
      \Delta_{t}
    \end{bmatrix}  \right\|^4 \middle| \mathcal{F}_{t_0} \right]
    \\
    \leq &
    \begin{cases}
      44 \eta^4 Q^2 K^2 \sigma^4 \left(1 + \frac{\gamma^2\mu}{\eta}\right)^{4K}
       & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right],
      \\
      44 \eta^4 Q^2 K^2 \sigma^4
       &
      \text{if~} \gamma = \eta,
    \end{cases}
  \end{align}
  where in the last inequality we used the estimate that $\frac{289}{324} \cdot 49 < 44$.
\end{proof}

\subsubsection{Proof of \cref{fedacii:stab:1}}

\label{sec:fedacii:stab:1}
\begin{proof}[Proof of \cref{fedacii:stab:1}]
  The proof of  \cref{fedacii:stab:1} follows instantly by plugging $\alpha = \frac{3}{2\gamma \mu} - \frac{1}{2}$, $\beta = \frac{2 \alpha^2 - 1}{\alpha - 1} = \frac{9 - \gamma \mu (6 + \gamma \mu)}{3 \gamma \mu (1 - \gamma\mu)}$ to the general claim on \fedac \cref{fedac:general:stab}:
  \begin{align}
    & \begin{bmatrix}
      (1 - \beta^{-1}) (I - \eta H)
       &
      \beta^{-1} (I - \eta H)
      \\
      (1 - \beta^{-1}) (\alpha^{-1} - \gamma H)
       &
      \beta^{-1} (\alpha^{-1} I - \gamma H) + (1 - \alpha^{-1}) I
    \end{bmatrix}
    \\
    = & \frac{1}{9 - \gamma \mu (6 + \gamma \mu)}
    \begin{bmatrix}
      (3 - \gamma \mu)(3 - 2\gamma \mu)(I - \eta H)
       & 3 \gamma \mu (1 - \gamma \mu) (I - \eta H)
      \\
      (3 - 2 \gamma \mu) (2 \gamma \mu - (3 - \gamma \mu) \gamma H)
       &
      3 (1 - \gamma \mu) ((3 - \gamma \mu)I - \gamma^2 \mu H)
    \end{bmatrix}.
  \end{align}
\end{proof}

\subsubsection{Proof of \cref{fedacii:stab:bound}: uniform norm bound}
\label{sec:fedacii:stab:bound}
The proof idea of this proposition is very similar to \cref{fedaci:stab:bound}, though more complicated technically.
\begin{proof}
  Define another matrix-valued function $\mathcal{B}$ as
  \begin{equation}
    \mathcal{B}(\mu, \gamma, \eta, H) := \mathcal{X}(\gamma, \eta)^{-1} \mathcal{A}(\mu, \gamma, \eta, H) \mathcal{X}(\gamma, \eta).
  \end{equation}
  Since $ \mathcal{X}(\gamma, \eta)^{-1} =
  \begin{bmatrix}
    \frac{\gamma}{\eta}I  & 0
    \\
    -\frac{\gamma}{\eta}I & I
  \end{bmatrix}$
  we have
  \begin{align}
      & \mathcal{B}(\mu, \gamma, \eta, H)
    \\
    = & \frac{1}{(9 - (6 + \gamma \mu)\gamma \mu)\eta}
    \begin{bmatrix}
      \left( 3 \gamma^2 \mu ( 1 - \gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu) \right) (I - \eta H) &
      3\gamma^2 \mu(1 - \gamma \mu)(I - \eta H)
      \\
      - (\gamma - \eta)\left( 3 \gamma + 6 \eta - \gamma \mu (3 \gamma + 4\eta) \right) I                    &
      3 (1 - \gamma \mu)\left( 3 \eta - \gamma \mu (\gamma + \eta)  \right) I
    \end{bmatrix}.
  \end{align}
  Define the four blocks of $\mathcal{B}(\mu, \gamma, \eta, H)$ as $\mathcal{B}_{11}(\mu, \gamma, \eta, H)$, $\mathcal{B}_{12}(\mu, \gamma, \eta, H)$, $\mathcal{B}_{21}(\mu, \gamma, \eta)$, $\mathcal{B}_{22}(\mu, \gamma, \eta)$ (note that the lower two blocks do not involve $H$), namely
  \begin{align}
    \mathcal{B}_{11}(\mu, \gamma, \eta, H) & = \frac{3 \gamma^2 \mu ( 1 - \gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta } (I - \eta H),
    \\
    \mathcal{B}_{12}(\mu, \gamma, \eta, H) & = \frac{3\gamma^2 \mu(1 - \gamma \mu)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta }(I - \eta H),
    \\
    \mathcal{B}_{21}(\mu, \gamma, \eta)    & = -\frac{(\gamma - \eta) \mu \left( 3 \gamma + 6 \eta - \gamma \mu (3 \gamma + 4\eta) \right)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta }I,
    \\
    \mathcal{B}_{22}(\mu, \gamma, \eta)    & = \frac{3 (1 - \gamma \mu)\left( 3 \eta - \gamma \mu (\gamma + \eta)  \right)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta}I.
  \end{align}
  \paragraph{Case I: $\eta < \gamma \leq \sqrt{\frac{\eta}{\mu}}$.}
  Since $\gamma \mu \leq 1$, we know that the common denominator
  \begin{equation}
    (9 - (6 + \gamma \mu)\gamma \mu) \eta \geq 2 \eta > 0.
    \label{eq:fedacii:B:denom}
  \end{equation}
  Now we bound the operator norm of each block as follows.

  \paragraph{Bound for $\|\mathcal{B}_{11}\|$.} Since $3 \gamma^2 \mu ( 1 - \gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu) \geq 0$, we have $\mathcal{B}_{11} \succeq 0$, and therefore
  \begin{align}
         & \|\mathcal{B}_{11}(\mu, \gamma, \eta, H)\|
    \\
    \leq & \frac{3 \gamma^2 \mu ( 1 - \gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta } (1 - \eta \mu)
    \\
    \leq & \frac{3 \gamma^2 \mu ( 1 - \gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta }
    \\
    =    &  1 + \frac{3 (\gamma - \eta) \gamma \mu  (1 - \gamma \mu)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta }
    \\
    \leq & 1 + \frac{3 \gamma^2 \mu }{\eta} \cdot \frac{1 - \gamma \mu}{ 9 - 6 \gamma \mu - \gamma^2\mu^2}
    \tag{since $\gamma - \eta \leq \gamma$}
    \\
    \leq & 1 + \frac{\gamma^2 \mu}{3 \eta},
    \label{eq:fedacii:stab:bound:11}
  \end{align}
  where the last inequality is due to $\frac{1 - \gamma \mu}{ 9 - 6 \gamma \mu - \gamma^2\mu^2} \leq \frac{1}{9}$ since $\gamma \mu \leq 1$.

  \paragraph{Bound for $\|\mathcal{B}_{12}\|$.} Similarly we have
  \begin{equation}
    \|\mathcal{B}_{12}(\mu, \gamma, \eta, H)\| \leq \frac{3 \gamma^2 \mu (1 - \gamma\mu)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta}(1-\eta \mu)
    \leq \frac{3 \gamma^2 \mu}{\eta} \cdot \frac{1 - \gamma \mu}{9 - (6 + \gamma \mu)\gamma \mu}
    \leq \frac{\gamma^2 \mu}{3 \eta},
    \label{eq:fedacii:stab:bound:12}
  \end{equation}
  where the last inequality is due to $\frac{1 - \gamma \mu}{ 9 - 6 \gamma \mu - \gamma^2\mu^2} \leq \frac{1}{9}$ since $\gamma \mu \leq 1$.

  \paragraph{Bound for $\|\mathcal{B}_{21}\|$.} Since $\gamma \geq \eta$, we have $(\gamma - \eta) \mu \left( 3 \gamma + 6 \eta - \gamma \mu (3 \gamma + 4\eta) \right) \geq 0$.
  Note that
  \begin{align}
     & (\gamma - \eta) \left( 3 \gamma + 6 \eta - \gamma \mu (3 \gamma + 4\eta) \right)
     \\
     = &  3 \gamma^2 + 3 \gamma \eta - 6 \eta^2 - \gamma \mu (3 \gamma^2 + \gamma \eta - 4 \eta^ 2)
     \\
     = & 4 \gamma^2 - 3\gamma^3 \mu - (\gamma^2 - 3 \gamma \eta + 6 \eta^2 + \gamma^2 \mu \eta - 4\eta^2 \gamma \mu  ),
  \end{align}
  and
  \begin{align}
        & \gamma^2 - 3 \gamma \eta + 6 \eta^2 + \gamma^2 \mu \eta - 4\eta^2 \gamma \mu
    \\
    \geq & \gamma^2 - 3 \gamma \eta + 6 \eta^2 - 3\eta^2 \gamma \mu  \tag{since $\eta \leq \gamma$}
    \\
    \geq & \gamma^2 - 3 \gamma \eta + 3 \eta^2 \tag{since $\gamma \mu \leq 1$}
    \\
    \geq & 0. \tag{AM-GM inequality}
  \end{align}
  Consequently,
  \begin{equation}
    (\gamma - \eta) \mu \left( 3 \gamma + 6 \eta - \gamma \mu (3 \gamma + 4\eta) \right) \leq 4 \gamma^2 \mu - 3 \gamma^3 \mu^2.
    \label{eq:fedacii:stab:bound:tmp}
  \end{equation}
  It follows that
  \begin{align}
         & \|\mathcal{B}_{21}(\mu, \gamma, \eta)\| =  \frac{\mu (\gamma - \eta)  \left( 3 \gamma + 6 \eta - \gamma \mu (3 \gamma + 4\eta) \right)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta }
    \\
    \leq    & \frac{4 \gamma^2 \mu - 3 \gamma^3 \mu^2}{(9 - (6 + \gamma \mu)\gamma \mu) \eta }  \tag{by \cref{eq:fedacii:stab:bound:tmp}}
    \\
    =   &  \frac{\gamma^2 \mu}{\eta} \cdot \frac{4 - 3 \gamma \mu}{9 - 6 \gamma \mu - \gamma^2 \mu^2} \leq  \frac{2\gamma^2 \mu}{3\eta}.
    \label{eq:fedacii:stab:bound:21}
  \end{align}
  where the last inequality is due to $\frac{4 - 3 \gamma \mu}{9 - 6 \gamma \mu - \gamma^2 \mu^2} \leq \frac{2}{3}$ since $\gamma \mu \leq 1$.

  \paragraph{Bound for $\mathcal{B}_{22}$.} Since $\gamma > \eta$ and $\gamma^2 \mu \leq \eta$, we have $3\eta - \gamma \mu(\gamma + \eta) \geq 3 \eta - 2 \gamma^2 \mu \geq \eta$. Thus $\mathcal{B}_{22} \succeq 0$, which implies
  \begin{equation}
    \|\mathcal{B}_{22}(\mu, \gamma, \eta)\|
    = \frac{3 (1 - \gamma \mu)\left( 3 \eta - \gamma \mu (\gamma + \eta)  \right)}{(9 - (6 + \gamma \mu)\gamma \mu) \eta}
    = 1 + \frac{\gamma \mu \left( -6 \eta - 3 \gamma + \gamma \mu (3 \gamma + 4 \eta ) \right) }{(9 - (6 + \gamma \mu)\gamma \mu) \eta }
    \leq 1.
    \label{eq:fedacii:stab:bound:22}
  \end{equation}

  The operator norm of block matrix $\mathcal{B}$ can be bounded via its blocks via \cref{helper:blocknorm} as
    \begin{align}
         & \mathcal{B}(\mu, \gamma, \eta, H)
    \\
    \leq & \max \left\{\| \mathcal{B}_{11}(\mu, \gamma, \eta, H) \|, \| \mathcal{B}_{22}(\mu, \gamma, \eta) \| \right\}
    +
    \max \left\{\| \mathcal{B}_{12}(\mu, \gamma, \eta, H) \|, \| \mathcal{B}_{21}(\mu, \gamma, \eta) \| \right\} \tag{\cref{helper:blocknorm}}
    \\
    \leq & \max \left\{ 1 + \frac{\gamma^2 \mu}{3\eta}, 1 \right\} + \max \left\{ \frac{\gamma^2 \mu}{3\eta}, \frac{2\gamma^2 \mu}{3\eta} \right\}
    \leq 1 + \frac{\gamma^2 \mu}{\eta}.
    \tag{\cref{eq:fedacii:stab:bound:11,eq:fedacii:stab:bound:12,eq:fedacii:stab:bound:21,eq:fedacii:stab:bound:22}}
  \end{align}
  \paragraph{Case II: $\gamma = \eta$.} In this case we have
  \begin{align}
    \|\mathcal{B}_{11}(\mu, \gamma, \eta, H)\| &
    \leq 1 - \eta \mu,
    \\
    \|\mathcal{B}_{12}(\mu, \gamma, \eta, H)\| &
    \leq \frac{3 \eta \mu - 6 \eta^2 \mu^2 + 3 \eta^3 \mu^3}{9 - 6 \eta \mu - \eta^2 \mu^2},
    \\
    \|\mathcal{B}_{21}(\mu, \gamma, \eta)\|    &
    = 0,
    \\
    \|\mathcal{B}_{22}(\mu, \gamma, \eta)\|    & = \frac{9- 15 \eta \mu + 6 \eta^2 \mu^2}{9 - 6 \eta \mu - \eta^2 \mu^2} = 1  - \frac{9 \eta \mu - 7 \eta^2 \mu^2}{9 - 6 \eta \mu - \eta^2 \mu^2}.
  \end{align}

 Similarly the operator norm of block matrix $\mathcal{B}$ can be bounded via its blocks via \cref{helper:blocknorm} as
   \begin{align}
         & \mathcal{B}(\mu, \gamma, \eta, H)
    \\
    \leq & \max \left\{\| \mathcal{B}_{11}(\mu, \gamma, \eta, H) \|, \| \mathcal{B}_{22}(\mu, \gamma, \eta) \| \right\}
    +
    \max \left\{\| \mathcal{B}_{12}(\mu, \gamma, \eta, H) \|, \| \mathcal{B}_{21}(\mu, \gamma, \eta) \| \right\} \tag{\cref{helper:blocknorm}}
    \\
    \leq & \max \left\{ 1 - \eta \mu + \frac{3 \eta \mu - 6 \eta^2 \mu^2 + 3 \eta^3 \mu^3}{9 - 6 \eta \mu - \eta^2 \mu^2}, \frac{9- 15 \eta \mu + 6 \eta^2 \mu^2}{9 - 6 \eta \mu - \eta^2 \mu^2}
    + \frac{3 \eta \mu - 6 \eta^2 \mu^2 + 3 \eta^3 \mu^3}{9 - 6 \eta \mu - \eta^2 \mu^2}\right\}
    \\
    \leq & \max \left\{ 1 - \frac{6 \eta \mu - 4 \eta^3 \mu^3}{9 - 6 \eta \mu - \eta^2 \mu^2} , 1 - \frac{6 \eta \mu - \eta^2\mu^2 - 3 \eta^3 \mu^3}{9 - 6 \eta \mu - \eta^2 \mu^2} \right\} \leq 1.
  \end{align}
  Summarizing the above two cases completes the proof of \cref{fedacii:stab:bound}.
\end{proof}

\subsubsection{Proof of \cref{fedacii:stab:2}}
\label{sec:fedacii:stab:2}
In this section we apply  \cref{fedacii:stab:1,fedacii:stab:bound} to establish \cref{fedacii:stab:2}.
\begin{proof}[Proof of \cref{fedacii:stab:2}]
  If $t+1$ is a synchronized step, then the bound trivially holds since $\Delta_{t+1}^{\mathrm{ag}} = \Delta_{t+1} = 0$ due to synchronization.

  From now on assume $t+1$ is not a synchronized step, for which \cref{fedacii:stab:1} is applicable. Multiplying $\mathcal{X}(\gamma, \eta)^{-1}$ to the left on both sides of \cref{fedacii:stab:1} gives (we omit the details since the reasoning is the same as in the proof of \cref{fedaci:stab:2}.
  \begin{align}
    \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t+1}^{\mathrm{ag}}
      \\
      \Delta_{t+1}
    \end{bmatrix}
    =
    \mathcal{X}(\gamma, \eta)^{-1} \mathcal{A}(\mu, \gamma, \eta, H_t) \mathcal{X}(\gamma, \eta)^{-1} \left( \mathcal{X}(\gamma, \eta) \begin{bmatrix}
        \Delta_{t}^{\mathrm{ag}}
        \\
        \Delta_{t}
      \end{bmatrix}  \right)
    -
    \begin{bmatrix}   \gamma I \\ 0 \end{bmatrix} \Delta_t^{\varepsilon}.
    \label{eq:fedacii:stab:2:1}
  \end{align}
  Before we proceed, we introduce a few more notations to simplify the discussion.
  Denote the shortcut $\mathcal{B}_t := \mathcal{X}(\gamma, \eta)^{-1} \mathcal{A}(\mu, \gamma, \eta, H_t) \mathcal{X}(\gamma, \eta)$,  $\mathcal{X} = \mathcal{X}(\gamma, \eta)$,
  $\tilde{\Delta}_t =  \mathcal{X}^{-1}\begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\  \Delta_{t} \end{bmatrix}$, and $\tilde{\Delta}_t^\varepsilon =  \begin{bmatrix} \gamma I \\ 0 \end{bmatrix} \Delta_t^{\varepsilon}$.
  Then \cref{eq:fedacii:stab:2:1} becomes $\tilde{\Delta}_{t+1} = \mathcal{B}_t \tilde{\Delta}_{t} - \tilde{\Delta}_{t}^{\varepsilon}$. Thus
  \begin{align}
         & \expt \left[ \| \tilde{\Delta}_{t+1} \|^4 |\mathcal{F}_t \right] = \expt \left[ \|  \mathcal{B}_t \tilde{\Delta}_{t} - \tilde{\Delta}_t^\varepsilon  \|^4 |\mathcal{F}_t \right]
    \tag{by \cref{fedacii:stab:1}}
    \\
    =    & \expt \left[  \left(  \| \mathcal{B}_t \tilde{\Delta}_t \|^2
      +
      \|\tilde{\Delta}_t^\varepsilon \|^2
      -
      2 \langle \mathcal{B}_t \tilde{\Delta}_t , \tilde{\Delta}_t^\varepsilon  \rangle \right)^2   \right]
    \\
    =    & \| \mathcal{B}_t \tilde{\Delta}_t \|^4
    + \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^4 |\mathcal{F}_t \right]
    + 4 \expt \left[     \langle \mathcal{B}_t \tilde{\Delta}_t , \tilde{\Delta}_t^\varepsilon  \rangle^2 |\mathcal{F}_t     \right]
    + 2 \| \mathcal{B}_t \tilde{\Delta}_t \|^2 \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^2 |\mathcal{F}_t \right]
    \\
         &
    - 4  \| \mathcal{B}_t \tilde{\Delta}_t \|^2  \expt \left[\langle \mathcal{B}_t \tilde{\Delta}_t , \tilde{\Delta}_t^\varepsilon  \rangle |\mathcal{F}_t     \right]
    - 4 \expt \left[  \| \tilde{\Delta}_{t}^\varepsilon \|^2   \langle \mathcal{B}_t \tilde{\Delta}_t , \tilde{\Delta}_t^\varepsilon  \rangle |\mathcal{F}_t     \right]
    \\
    =    & \| \mathcal{B}_t \tilde{\Delta}_t \|^4 + \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^4 |\mathcal{F}_t \right]
    + 4 \expt \left[     \langle \mathcal{B}_t \tilde{\Delta}_t , \tilde{\Delta}_t^\varepsilon  \rangle^2 |\mathcal{F}_t     \right]
    + 2 \| \mathcal{B}_t \tilde{\Delta}_t \|^2 \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^2 |\mathcal{F}_t \right]
    \\
         &
    - 4 \expt \left[  \| \tilde{\Delta}_{t}^\varepsilon \|^2   \langle \mathcal{B}_t \tilde{\Delta}_t , \tilde{\Delta}_t^\varepsilon  \rangle |\mathcal{F}_t     \right]
    \tag{by independence and $\expt [\tilde{\Delta}_t^\varepsilon |\mathcal{F}_t] = 0$}
    \\
    \leq & \| \mathcal{B}_t \tilde{\Delta}_t \|^4 + \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^4 |\mathcal{F}_t \right]
    + 6 \| \mathcal{B}_t \tilde{\Delta}_t \|^2 \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^2 |\mathcal{F}_t \right]
    + 4 \| \mathcal{B}_t \tilde{\Delta}_t \| \expt \left[  \| \tilde{\Delta}_{t}^\varepsilon \|^3   |\mathcal{F}_t     \right]
    \tag{Cauchy-Schwarz inequality}
    \\
    \leq & \| \mathcal{B}_t \tilde{\Delta}_t \|^4 + 5 \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^4 |\mathcal{F}_t \right]
    + 7 \| \mathcal{B}_t \tilde{\Delta}_t \|^2 \expt \left[ \| \tilde{\Delta}_{t}^\varepsilon \|^2 |\mathcal{F}_t \right]
    \tag{AM-GM inequality}
    \\
    \leq & \| \mathcal{B}_t \tilde{\Delta}_t \|^4
    + 40 \gamma^4  \sigma^4
    + 14 \gamma^2 \sigma^2\| \mathcal{B}_t \tilde{\Delta}_t \|^2
    \tag{bounded \nth{4} central moment via \cref{helper:diff:4th}}
    \\
    \leq & \left( \|\mathcal{B}_t \tilde{\Delta}_t\|^2 + 7 \gamma^2 \sigma^2 \right)^2 \leq  \left( \|\mathcal{B}_t\|^2 \|\tilde{\Delta}_t\|^2 + 7 \gamma^2 \sigma^2 \right)^2.
  \end{align}
  Applying \cref{fedacii:stab:bound},
  \begin{equation}
    \sqrt{\expt \left[ \| \tilde{\Delta}_{t+1} \|^4 |\mathcal{F}_t \right]}
    \leq
    7 \gamma^2 \sigma^2 +  \| \tilde{\Delta}_{t}\|^2 \cdot
    \begin{cases}
      \left(1 + \frac{\gamma^2 \mu}{\eta}\right)^2 & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}}\right], \\
      1                              & \text{if~} \gamma =  \eta.
    \end{cases}
  \end{equation}
  Resetting the notations completes the proof.
\end{proof}

\subsubsection{Proof of \cref{fedacii:stab:3}}
\label{sec:fedacii:stab:3}
In this section we will prove \cref{fedacii:stab:3} in two steps via the following two claims. For both two claims $\mathcal{X}$ stands for the matrix-valued functions defined in \cref{eq:fedacii:X:def}.

\begin{claim} \label{fedacii:stab:3:1}
  In the same setting of \cref{fedacii:stab:main}, the following inequality holds (for all possible $t$)
  \begin{equation}
    \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
    \leq
    \frac{Q^2}{4} \left\| \mathcal{X}(\gamma, \eta)^\intercal
  \begin{bmatrix} \frac{9 - 9 \gamma \mu + 2 \gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2}  I \\ \frac{3 \gamma \mu - 3\gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2} I \end{bmatrix}
     \right\|^4
     \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^4.
  \end{equation}
\end{claim}
\begin{claim}
  \label{fedacii:stab:left}
  Assume $\mu > 0$, $\gamma \in [\eta,\sqrt{\frac{\eta}{\mu}}]$, then
  \(
    \left\| \mathcal{X}(\gamma, \eta)^\intercal
  \begin{bmatrix} \frac{9 - 9 \gamma \mu + 2 \gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2}  I \\ \frac{3 \gamma \mu - 3\gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2} I \end{bmatrix} \right\| \leq
    \frac{\sqrt{17} \eta }{3\gamma}.
  \)
\end{claim}

\begin{proof}[Proof of \cref{fedacii:stab:3}]
  Follow trivially with \cref{fedaci:stab:3:1,fedacii:stab:left} as
  \begin{align}
      \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
      & \leq
      \frac{Q^2}{4} \left( \frac{\sqrt{17} \eta}{3 \gamma} \right)^4 \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
        \Delta_{t}^{\mathrm{ag}}
        \\
        \Delta_{t}
      \end{bmatrix}  \right\|^4
      \\
      & =
      \frac{289 \eta^4 Q^2}{324 \gamma^4} \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
        \Delta_{t}^{\mathrm{ag}}
        \\
        \Delta_{t}
      \end{bmatrix}  \right\|^4.
  \end{align}
\end{proof}

Now we finish the proof of these two claims.

\begin{proof}[Proof of \cref{fedacii:stab:3:1}]
  Helper \cref{helper:3rd:Lip} shows that $\left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 $ can be bounded by $\nth{4}$-moment of difference:
  \begin{align}
    &  \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
    \leq
     \frac{Q^2}{4} \cdot \frac{1}{M} \sum_{m=1}^M  \|w_t^{\mathrm{md},m} - \overline{w_t^{\mathrm{md}}}\|^4
    \tag{\cref{helper:3rd:Lip}}
\\
\leq & \frac{Q^2}{4} \| \Delta_t^{\mathrm{md}} \|^4
\tag{convexity of $\|\cdot\|^4$}
\\
=  &
\frac{Q^2}{4}
 \left\|
 \begin{bmatrix} (1 - \beta^{-1}) I \\ \beta^{-1} I \end{bmatrix}^\intercal
 \begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\ \Delta_{t} \end{bmatrix}
 \right\|^4
\tag{definition of ``md''}
\\
\leq & \frac{Q^2}{4} \left\| \mathcal{X}(\gamma, \eta)^\intercal \begin{bmatrix} (1 - \beta^{-1}) I \\ \beta^{-1} I \end{bmatrix} \right\|^4
\cdot \left\| \mathcal{X}(\gamma, \eta)^{-1}
 \begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\ \Delta_{t} \end{bmatrix}
 \right\|^4.
\tag{sub-multiplicativity}
\\
= & \frac{Q^2}{4} \left\| \begin{bmatrix} \frac{9 - 9 \gamma \mu + 2 \gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2}  I \\ \frac{3 \gamma \mu - 3\gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2} I \end{bmatrix} \right\|^4
\cdot \left\| \mathcal{X}(\gamma, \eta)^{-1}
 \begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\ \Delta_{t} \end{bmatrix}
 \right\|^4.
\end{align}
\end{proof}

\begin{proof}[Proof of \cref{fedacii:stab:left}]
  Direct calculation shows that
  \begin{equation}
    \mathcal{X}(\gamma, \eta)^\intercal
    \begin{bmatrix} \frac{9 - 9 \gamma \mu + 2 \gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2}  I \\ \frac{3 \gamma \mu - 3\gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2} I \end{bmatrix}
    =
    \begin{bmatrix}  \frac{3 \gamma^2 \mu (1-\gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu)}{\gamma (9 - 6 \gamma \mu - \gamma^2\mu^2)}  I \\ \frac{3 \gamma^2 \mu ( 1- \gamma \mu)}{\gamma (9 - 6 \gamma \mu - \gamma^2\mu^2)}  I \end{bmatrix}.
  \end{equation}
  Since $\gamma^2 \mu \leq \eta$ and $\gamma \mu \leq 1$, we have
  \begin{equation}
    0 \leq
    \frac{3 \gamma^2 \mu (1-\gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu)}{\gamma (9 - 6 \gamma \mu - \gamma^2\mu^2)}
    \leq
    \frac{\eta}{\gamma} \cdot \frac{12 - 12 \gamma \mu + 2 \gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2\mu^2}
    \leq
    \frac{4\eta}{3\gamma},
  \end{equation}
  and
  \begin{equation}
    0 \leq \frac{3 \gamma^2 \mu (1-\gamma \mu)}{\gamma (9 - 6 \gamma \mu - \gamma^2\mu^2)}
    \leq \frac{\eta}{\gamma} \cdot \frac{3  (1-\gamma \mu)}{9 - 6 \gamma \mu - \gamma^2\mu^2}
    \leq \frac{\eta}{3\gamma}.
  \end{equation}
  Consequently,
  \begin{equation}
    \left\|     \begin{bmatrix}  \frac{3 \gamma^2 \mu (1-\gamma \mu) + \eta (3 - \gamma \mu)(3 - 2 \gamma \mu)}{\gamma (9 - 6 \gamma \mu - \gamma^2\mu^2)}  I \\ \frac{3 \gamma^2 \mu ( 1- \gamma \mu)}{\gamma (9 - 6 \gamma \mu - \gamma^2\mu^2)}  I \end{bmatrix} \right\|
    \leq
    \sqrt{\left( \frac{4 \eta}{3\gamma} \right)^2 + \left( \frac{\eta}{3\gamma} \right)^2}
    \leq
    \frac{\sqrt{17} \eta }{3 \gamma}.
  \end{equation}
\end{proof}

\subsection{Convergence of \fedacii under \cref{asm1}: Complete version of \cref{fedac:a1}(b)}
\label{sec:fedacii:a1}
\subsubsection{Main theorem and lemma}
In this subsection we establish the convergence of \fedacii under \cref{asm1}.
We will provide a complete, non-asymptotic version of \cref{fedac:a1}(b) and provide the proof.
\begin{theorem}[Convergence of \fedacii under \cref{asm1}, complete version of \cref{fedac:a1}(b)]
  \label{fedacii:a1:full}
  Let $F$ be $\mu > 0$ strongly convex, and assume \cref{asm1}, then for
  \begin{equation}
    \eta = \min \left\{ \frac{1}{L}, \frac{9K}{\mu T^2} \log^2 \left( \euler
     + \min \left\{ \frac{\mu M T \Phi_0}{\sigma^2} + \frac{\mu^3 T^4 \Phi_0}{L^2K^3 \sigma^2}\right\} \right)\right\},
  \end{equation}
  \fedacii yields
  \begin{align}
    \expt[\Phi_T] \leq & \min \left\{ \exp \left( - \frac{\mu T}{3 L} \right), \exp \left( - \frac{\mu^{\frac{1}{2}} T}{3 L^{\frac{1}{2}} K^{\frac{1}{2}}} \right)\right\} \Phi_0
    \\
    &
    + \frac{4 \sigma^2}{\mu M T} \log \left( \euler + \frac{\mu MT \Phi_0}{\sigma^2} \right)
    + \frac{8101 L^2 K^3 \sigma^2}{\mu^3 T^4} \log^4\left( \euler + \frac{\mu^3 T^4 \Phi_0}{L^2 K^3 \sigma^2} \right),
  \end{align}
  where $\Phi_t$ is the ``centralized'' potential function defined in \cref{eq:centralied:potential}.
\end{theorem}
\begin{remark}
  The simplified version \cref{fedac:a1}(b) in the main body can be obtained by replacing $K$ with $T/R$ and upper bound $\Phi_0$ by $LD_0^2$.
\end{remark}
Note that most of the results established towards \cref{fedacii:a2:full} can be recycled as long as it does not assume \cref{asm2}.
In particular, we will reuse the perturbed iterate analysis \cref{fedacii:conv:main}, and provide an alternative version of discrepancy overhead bounds, as shown in \cref{fedacii:a1:stab:main}.
The only difference is that now we use $L$-smoothness to bound the discrepancy term.
\begin{lemma}[Discrepancy overhead bounds]
  \label{fedacii:a1:stab:main}
  Let $F$ be $\mu > 0$-strongly convex, and assume \cref{asm1}, then for $\alpha = \frac{3}{2 \gamma \mu} - \frac{1}{2}$, $\beta =\frac{2 \alpha^2 - 1}{\alpha - 1}$, $\gamma \in [\eta, \sqrt{ \frac{\eta}{\mu}}]$, $\eta \in (0, \frac{1}{L}]$, \fedac satisfies (for all $t$)
  \begin{align}
     & \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right]
    \leq  \begin{cases}
      4 \eta^2 L^2 K \sigma^2 \left(1 + \frac{\gamma^2\mu}{\eta}\right)^{2K}
       & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right],
      \\
      4 \eta^2 L^2 K \sigma^2
       &
      \text{if~} \gamma = \eta.
    \end{cases}
  \end{align}
\end{lemma}
The proof of \cref{fedacii:a1:stab:main} is deferred to \cref{sec:fedacii:a1:stab:main}.

Now plug in the choice of $\gamma = \max \left\{ \sqrt{\frac{\eta}{\mu K}}, \eta\right\}$ to \cref{fedacii:conv:main,fedacii:a1:stab:main}, which leads to the following lemma.
\begin{lemma}[Convergence of \fedacii for general $\eta$ under \cref{asm1}]
  \label{fedacii:a1:general:eta}
    Let $F$ be $\mu > 0$-strongly convex, and assume \cref{asm1}, then for any $\eta \in (0, \frac{1}{L}]$, \fedacii yields
    \begin{equation}
      \expt[\Phi_T]
      \leq \exp \left(  - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0
      + \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
      + \frac{100 \eta^2 L^2 K \sigma^2}{\mu}.
      \label{eq:fedacii:a1:general:eta}
    \end{equation}
\end{lemma}
\begin{proof}[Proof of \cref{fedacii:a1:general:eta}]
  Applying \cref{fedacii:conv:main} yields
  \begin{align}
    \expt[\Phi_T] \leq & \exp\left( - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0
    +
    \min\left\{ \frac{3\eta L \sigma^2}{2 \mu M}, \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} \right\}
    \\
                       & + \max\left\{ \frac{\eta \sigma^2}{2M}, \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }          \right\}
    + \frac{3}{\mu} \max_{0 \leq t < T}  \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right].
    \label{eq:fedaci:proof:1:mod}
  \end{align}
  Applying \cref{fedacii:a1:stab:main} yields (for all $t$)
  \begin{align}
         & \frac{3}{\mu} \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2 \right]
    \leq
    \begin{cases}
      12 \mu^{-1} \eta^2 L^2 K \sigma^2  \left(1 + \frac{1}{K}\right)^{2K}
       & \text{if~} \gamma = \sqrt{\frac{\eta}{\mu K}},
      \\
      12 \mu^{-1} \eta^2 L^2 K \sigma^2
       &
      \text{if~} \gamma = \eta
    \end{cases}
    \\
    \leq & 12 \euler^{2} \mu^{-1} \eta^2 L^2 K \sigma^2.
    \label{eq:fedaci:proof:2:mod}
  \end{align}
  Note that
  \begin{align}
         & \min\left\{ \frac{3\eta L \sigma^2}{2 \mu M}, \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} \right\}
    + \max\left\{ \frac{\eta \sigma^2}{2M}, \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }          \right\}
    \\
    \leq & \frac{3 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M} + \frac{\eta \sigma^2}{2M} + \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    \\
    \leq &
    \frac{7 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M} + \frac{3 \eta^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} }.
    \tag{by AM-GM inequality, and $\mu \leq L$}
  \end{align}
  By Young's inequality,
  \begin{align}
    \frac{7 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M}
    \leq & \left( \frac{3}{4} \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} } \right)^{\frac{1}{3}}
    \left( 3 \cdot \frac{\eta^2 L^\frac{3}{2} K \sigma^2}{\mu^{\frac{1}{2}} M} \right)^{\frac{2}{3}}
    \tag{since $\frac{7}{4} \leq \left( \frac{3}{4} \right)^{\frac{1}{3}} (3)^{\frac{2}{3}} $ }
    \\
    \leq & \frac{1}{4} \cdot \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} } + 2 \cdot \frac{\eta^2 L^\frac{3}{2} K \sigma^2}{\mu^{\frac{1}{2}} M}
    \tag{by Young's inequality}
    \\
    \leq & \frac{\eta^{\frac{1}{2}} \sigma^2}{4 \mu^{\frac{1}{2}} M K^{\frac{1}{2}} } + \frac{2\eta^2 L^2 K \sigma^2}{\mu}.
    \tag{since $L \geq \mu$ and $M \geq 1$}
  \end{align}
  Combining the above inequalities gives
  \begin{equation}
    \expt[\Phi_T]
    \leq \exp \left(  - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0
    + \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    + \frac{(12 \euler^2 + 2) \eta^2 L^2 K \sigma^2}{\mu}.
  \end{equation}
  The proof then follows by the estimate $12 \euler^2 + 2 < 100$.
\end{proof}

\cref{fedacii:a1:full} then follows by plugging in the appropriate $\eta$ to \cref{fedacii:a1:general:eta}.
\begin{proof}[Proof of \cref{fedacii:a1:full}]
  To simplify the notation, we denote the decreasing term in \cref{eq:fedacii:a1:general:eta} in \cref{fedacii:a1:general:eta} as $\varphi_{\downarrow}(\eta)$ and the increasing term as $\varphi_{\uparrow}(\eta)$, namely
  \begin{align}
    \varphi_{\downarrow}(\eta) := \exp \left(  - \frac{1}{3} \max \left\{ \eta \mu, \sqrt{\frac{\eta \mu}{K}}\right\}T \right) \Phi_0,
    \quad
    \varphi_{\uparrow}(\eta) := \frac{\eta^{\frac{1}{2}} \sigma^2}{\mu^{\frac{1}{2}} M K^{\frac{1}{2}} }
    + \frac{100 \eta^2 L^2 K \sigma^2}{\mu}.
  \end{align}
  Let
  \begin{equation}
    \eta_0 := \frac{9K}{\mu T^2} \log^2 \left( \euler
     + \min \left\{ \frac{\mu M T \Phi_0}{\sigma^2} + \frac{\mu^3 T^4 \Phi_0}{L^2K^3 \sigma^2}\right\} \right)
     ,
     \quad
     \text{then }
     \eta = \min \left\{ \frac{1}{L}, \eta_0 \right\}.
  \end{equation}
  Therefore
  \begin{equation}
    \varphi_{\downarrow}(\eta)
    \leq
    \min \left\{ \exp \left( - \frac{\mu T}{3 L} \right), \exp \left( - \frac{\mu^{\frac{1}{2}} T}{3 L^{\frac{1}{2}} K^{\frac{1}{2}}} \right)\right\} \Phi_0
    +
    \frac{\sigma^2}{\mu MT} + \frac{L^2 K^3 \sigma^2}{\mu^3 T^4}.
  \end{equation}
  and
  \begin{align}
    \varphi_{\uparrow}(\eta)  \leq \varphi_{\uparrow}(\eta_0)
    \leq
    &
    \frac{3 \sigma^2}{\mu M T} \log \left( \euler + \frac{\mu MT \Phi_0}{\sigma^2} \right)
    + \frac{8100 L^2 K^3 \sigma^2}{\mu^3 T^4} \log^4\left( \euler + \frac{\mu^3 T^4 \Phi_0}{L^2 K^3 \sigma^2} \right).
    \label{eq:fedacii:a1:3}
  \end{align}
  Consequently,
  \begin{align}
    \expt[\Phi_T] \leq & \varphi_{\downarrow} \left(\frac{1}{L} \right) + \varphi_{\downarrow}(\eta_0) + \varphi_{\uparrow}(\eta_0) \leq \min \left\{ \exp \left( - \frac{\mu T}{3 L} \right), \exp \left( - \frac{\mu^{\frac{1}{2}} T}{3 L^{\frac{1}{2}} K^{\frac{1}{2}}} \right)\right\} \Phi_0
    \\
    &
    + \frac{4 \sigma^2}{\mu M T} \log \left( \euler + \frac{\mu MT \Phi_0}{\sigma^2} \right)
    + \frac{8101 L^2 K^3 \sigma^2}{\mu^3 T^4} \log^4\left( \euler + \frac{\mu^3 T^4 \Phi_0}{L^2 K^3 \sigma^2} \right).
  \end{align}
\end{proof}

\subsubsection{Proof of \cref{fedacii:a1:stab:main}}
\label{sec:fedacii:a1:stab:main}
We first introduce the supporting propositions for \cref{fedacii:a1:stab:main}. We omit most of the proof details since the analysis is largely shared.

The following proposition is parallel to \cref{fedacii:stab:2}, where the difference is that the present proposition analyzes the \nth{2}-order stability instead of \nth{4}-order.
\begin{proposition}
  \label{fedacii:a1:stab:2}
  In the same setting of \cref{fedacii:a1:stab:main}, the following inequality holds (for all possible $t$)

    \begin{equation}
        \expt \left[ \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
          \Delta_{t+1}^{\mathrm{ag}}
          \\
          \Delta_{t+1}
        \end{bmatrix}  \right\|^2 \middle| \mathcal{F}_t \right]
      \leq
      2 \gamma^2 \sigma^2 +
      \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
        \Delta_{t}^{\mathrm{ag}}
        \\
        \Delta_{t}
      \end{bmatrix}  \right\|^2
      \cdot
      \begin{cases}
        \left(1 + \frac{\gamma^2 \mu}{\eta} \right)^2 & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}}\right], \\
        1                                              & \text{if~} \gamma =  \eta,
      \end{cases}
    \end{equation}

    where $\mathcal{X}$ is the matrix-valued function defined in \cref{eq:fedacii:X:def}.
\end{proposition}
\begin{proof}[Proof of \cref{fedacii:a1:stab:2}]
  Apply the uniform norm bound \cref{fedacii:stab:bound}, and the rest of the analysis is the same as \cref{fedaci:stab:2}.
\end{proof}

The following proposition is parallel to \cref{fedacii:stab:3}, where the difference is that the present proposition uses $L$-(\nth{2}-order)-smoothness to bound the LHS quantity.
\begin{proposition}
  \label{fedacii:a1:stab:3}
  In the same setting of \cref{fedacii:a1:stab:main}, the following inequality holds (for all possible $t$)
  \begin{equation}
    \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
    \leq
    \frac{17 \eta^2 L^2}{9 \gamma^2} \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^2,
  \end{equation}
  where $\mathcal{X}$ is the matrix-valued function defined in \cref{eq:fedacii:X:def}.
\end{proposition}
\begin{proof}[Proof of \cref{fedacii:a1:stab:3}]
  By $L$-smoothness (\cref{asm1}(b)),
  \begin{equation}
    \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2
    \leq
    L^2 \|\Delta_t^{\mathrm{md}}\|^2.
  \end{equation}
  By definition of ``md'', sub-multiplicativity, and \cref{fedacii:stab:left},
  \begin{equation}
    \|\Delta_t^{\mathrm{md}}\|^2
    =
    \left\|
    \mathcal{X}(\gamma, \eta)^{\intercal}
    \begin{bmatrix} \frac{9 - 9 \gamma \mu + 2 \gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2}  I \\ \frac{3 \gamma \mu - 3\gamma^2 \mu^2}{9 - 6 \gamma \mu - \gamma^2 \mu^2} I \end{bmatrix}
     \right\|^2
     \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^2
    \leq
    \frac{17 \eta^2}{9 \gamma^2} \left\| \mathcal{X}(\gamma, \eta)^{-1} \begin{bmatrix}
      \Delta_{t}^{\mathrm{ag}}
      \\
      \Delta_{t}
    \end{bmatrix}  \right\|^2.
  \end{equation}
\end{proof}

\cref{fedacii:a1:stab:main} then follows by telescoping \cref{fedacii:a1:stab:2} and plugging in \cref{fedacii:a1:stab:3}.
\begin{proof}[Proof of \cref{fedacii:a1:stab:main}]
  Let $t_0$ be the latest synchronized step prior to $t$, then telescoping \cref{fedacii:a1:stab:2} from $t_0$ to $t$  (note that $\Delta_{t_0} = \Delta_{t_0} = 0$)
  \begin{equation}
    \expt \left[ \left\| \mathcal{X}(\gamma, \eta)^{-1}
      \begin{bmatrix} \Delta_{t}^{\mathrm{ag}} \\ \Delta_{t} \end{bmatrix}
      \right\|^2 \middle| \mathcal{F}_{t_0} \right]
    \leq
    2 \gamma^2 \sigma^2 K \cdot \begin{cases}
      \left(1 + \frac{\gamma^2 \mu}{\eta}\right)^{2K} & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right],
      \\
      1                              & \text{if~} \gamma =  \eta.
    \end{cases}
    \label{eq:fedaci:mod:tmp}
  \end{equation}
  Thus, by \cref{fedacii:a1:stab:3},
  \begin{equation}
    \expt \left[ \left\|  \nabla F(\overline{w_t^{\mathrm{md}}}) -  \frac{1}{M} \sum_{m=1}^M \nabla F (w_t^{\mathrm{md}, m})  \right\|^2  \middle| \right]
    \leq
    \frac{34}{9} \eta^2 \sigma^2 K \cdot \begin{cases}
      \left(1 + \frac{\gamma^2 \mu}{\eta}\right)^{2K} & \text{if~} \gamma \in \left(\eta, \sqrt{\frac{\eta}{\mu}} \right],
      \\
      1                              & \text{if~} \gamma =  \eta.
    \end{cases}
  \end{equation}
  The \cref{fedacii:a1:stab:main} then follows by bounding $\frac{34}{9}$ with $4$.
\end{proof}


TITLE: Consider 2 identical players (i.e. i = 1, 2) with utility function:
QUESTION [0 upvotes]: Consider 2 identical players (i.e. i = 1, 2) with utility function:
πi = b(qi + q-i) - cqi.
Where qi is equal to one if player i contributes to the public good and is zero if she does
not, q-i is the sum of the contributions by all other players, b is the constant marginal
benefit of contributing to the public good, and c is the cost of contributing to the good.
Assume that b = 1/2 and c = 1.
The players have two possible actions: to cooperate to the public good (C), or not to
cooperate to the public good (NC). The players choose actions simultaneously and only
one time.
a) Write down the game in strategic form.
b) What is the Nash equilibrium in pure strategies?

REPLY [0 votes]: So, then if we are trying to answer the point b. and find what is the nash equilibrium in pure strategies to this exercise..how do we answer? because the way I see it, there is no nash equilibrium because:

when Player 1 plays, he will prefer player 2 to play as well because 0>-1/2
when Player 1 plays, player 2 will prefer to not play because 1/2>0

this shows that player 1 and 2 cannot meet, and cannot have the same preferences at the same time and this is the same for all 4 situations so there is no nash equilibrium. Is this right?


TITLE: Number of Binary Operations(Compositions) with a specific neutral element
QUESTION [1 upvotes]: Let $E$ be a finite set of $n$ elements.

If $a\in \mathbb{E}$, for how many compositions on $\mathbb{E}$ is is $a$ the neutral element.

Of these how many are commutative?

REPLY [1 votes]: Any composition on $\mathbb{E}$ is a function $f:(\mathbb{E}X\mathbb{E})\Rightarrow \mathbb{E}$, where |$\mathbb{E}X\mathbb{E}$|$=n^2$. If a composition is to have $a$  as a neutral element all the ordered pairs in  $(\mathbb{E}X\mathbb{E})$ having $a$ as a member must point to the other member of the pair ,e.g.,$(a,a_i)\Rightarrow a_i$. There are $2n-1$ ordered pairs in  $(\mathbb{E}X\mathbb{E})$ with $a$ as member. Since those ordered pairs images' are already fixed we are only concerned with the rest of the ordered pairs. There are $n^2-2n+1$ ordered pairs not containing $a$ as a member.
We can therefore think of the compositions as from a set of cardinality $n^2-2n+1$ into $\mathbb{E}$ of cardinality $n$;we think of the domain as having shrunk to $n^2-2n+1$ . Therefore, the total number of compositions w/ $a$ as a neutral element is $n^{n^2-2n+1}$.
b) We can apply the procedure for finding total number of binary operations on our now shrunken domain, see How to proof that more than half binary algebraic operations on a finite set are non-commutative?.
1) There are $n-1$ ordered pairs where both elements are the same since $(a,a)$ is not included.
2) Since any ordered pair having $a$ as a member is excluded we can select $\begin{pmatrix}
        n-1 \\
        2  \\
        \end{pmatrix}$ ordered pairs where the elements are not repeated.
now we the domain as shrunken to  $\begin{pmatrix}
        n-1 \\
        2  \\
        \end{pmatrix}$ + $n-1$.
Therefore, we can create $n^{(n^2-n)/2}$ binary operations w/ $a$ as the neutral element that are commutative.
Q.E.D.


TITLE: Game Theory applications on industry negotiations/procurement
QUESTION [0 upvotes]: I work for a large corporation in the consumer goods segment. We have a huge and procurement operation, with over a hundred collaborators between negotiaton and logistics. Some with very extensive experience on the categories they negotiate.
Recently there has been a pressure to study how can we improve our negotiations using game theory. As a data scientist on the department I've been tasked with finding possible applications and leading a project to implement them.
Although I have a bachelors degree in statistics I've never studied game theory, so my first step was looking for books and articles to understand the concepts.
It seems that everything I find is one of two types of content:

Short material aimed at people with no background in math, that just explains game theory concepts and their applications to a general negotiation.
Solved exercises or textbook examples that use a very simplified representation of a real negotiation to define optimal strategies for the players.

Neither of those helps me too much, as the first kind is common knowledge for anyone with a carreer in negotiation and the second is usually so simplified that I can't think of how to apply it to a real problem we face.
So, I have two questions:

Where could I look for pratical applications of game theory in this industry context?
Is it realistic to assume that negotiations conducted by people with a lot of experience in a category can be improved by modeling and "solving" a game?

Sorry if this doesn't fit here, any direction is appreciated.

REPLY [1 votes]: You might try The Art and Science of Negotiation by Howard Raiffa, a negotiation book by a brilliant game theorist.


TITLE: Disprove any closed set has a point on its boundary
QUESTION [2 upvotes]: I am told that the statement "any closed set has a point on its boundary" is false, yet I don't know how to disprove it. In fact, I think it is true.
Suppose we have [a,b], a closed set. Then, the boundary would be {a,b}, both of which are the elements of the set. So, there we have a closed set that has point(s) on its boundary.
I think one reason why I was told that the statement is false can be related to the empty set since

Empty set is also closed (clopen, but still)
It does not have a point on its boundary
The statement goes "any closed set..", hence empty set is not
excluded.

Supposing that the statement is false due to the above-mentioned reasoning (fact that empty set was not excluded), would "any nonempty closed set has a point on its boundary" be correct?
Thanks.

REPLY [2 votes]: Let $X$ be a topological space and $C\subseteq X$ a closed set. Then $cl(A)=A$ (closure of $A$ is equal to $A$). Our set $A$ has empty boundary if
$$ \emptyset = \partial A = cl(A) \setminus int(A).$$
As $int(A) \subseteq clo(A)$ this is equivalent to $int(A)=cl(A)$. This means, the closed sets with empty boundary are exactly the clopen sets.
Thus, if $X$ is connected, then there are only two sets, which are closed and have empty boundary, namely $\emptyset$ and $X$.

REPLY [2 votes]: It depends whether you are talking about general topological spaces or just $\mathbb{R}$. In $\mathbb{R}$ there are indeed very few examples: the empty set, as you mentioned, and all of $\mathbb{R}$.
In general topological spaces, however, you may have more examples.
It's not hard to see a set is closed if and only if it contains its boundary, and is open if and only if its intersection with its boundary is empty. Therefore, a set has an empty boundary if and only if it's clopen. Therefore in any connected space (like $\mathbb{R}$) the only closed sets satisfying this are the whole space and the empty set, but in disconnected spaces you will have more examples.


TITLE: Are all mathematical conclusions based on truth values (example)?
QUESTION [2 upvotes]: In maths it is assumed that every statement is either true (t) or false (f). When proving theorems such as: For all vector spaces $V$ over a field $K$ and $\lambda \in K$ it holds that $f_{\lambda}:V \to V, v \mapsto \lambda v$ is a linear map. When proving such a statement I usually did not think of truth values at all, the steps in the proof rather felt "intuitive" and were thus correct to me. However, the formal reason why a proof is correct is always connected to truth values isn't it? This would mean that a formal proof would then look like this:
Let $V$ be a vector space over $K$ and $\lambda \in K$ (this means that $V$ is a vector space is a true statement, as well as $K$ is a field and $\lambda \in K$ are true as well). Since $V$ is a vector space, it is by definition true that $V$ is a set. Thus $f_{\lambda} \subseteq V \times V$ with $f_{\lambda}:=\{(v,\lambda v) \ | \ v \in V\}$ is a subset (this is true by set theoretic axioms). Furthermore it holds that if $v_1=v_2$, then $\lambda v_1 = \lambda v_2$ since $V$ is equipped with a well defined multiplication function and by definition of a function this implication is true. Therefore $f_{\lambda}$ is a function. Since $f_{\lambda}$ is a function the element $f_{\lambda}(v_1+v_2)$ exists for all $v_1,v_2 \in V$ and it is true that $f_{\lambda}(v_1+v_2)=f_{\lambda}(v_1)+f_{\lambda}(v_2)$ using the axioms of a vector space which were assumed to be true. Thus the statement is true. Here I am also unsure if it is necessary to know that $f_{\lambda}(v_1+v_2)$ exists in order to proceed in the proof and what harm it would cause if it would not. Then the statement would be somewhat vacuous, I suppose.
In textbooks I don't usually see authors saying that the step in their proof is true, but I am correct in saying that this is what is meant when proving things, right? I suspect that when authors write that "something holds" they also mean that the truth value of the statement is (t).
Another question is, whether it is good to think this way. I would say that, when one is insecure whether ones proof is correct, this might be helpful, however it makes proofs a lot longer and restricts the readability to permanently write down that something is true.

REPLY [3 votes]: It seems to me that, so far you have encountered the (metaphorically speaking) coin that represents logic and proofs but you haven't seen or been shown yet, that it really has two individual sides.
There is as a deductive and a semantic side of it.
On the deductive side, one settles on a set of inference rules which are deemed valid logical principles. For example (where $A, B, C$ are any propositions):

If $A$ and $A \to B$ then we can conclude $B$.
If we want to show $C$, we can instead try to show $A \to C$ and $A$.
If $A$ and $B$ can be shown then $A \land B$.
If $A \land B$ then we can conclude $A$.

And there are a bunch more. These can then be used to give proofs, and in the context of mathematics these are usually presented in the form of text.
Let's write $\vdash P$ when we have given a poof like this for the proposition $P$.
On the semantic side, we proceed differently. We settle to assigning truth values true $T$ or false $F$ to propositions. If the proposition is build from other propositions by combining them via a logical connective like $\to, \lor$ or $\land$, we specify how the truth value of the composite proposition is defined. This is usually presented in the form of truth tables; like here in this case of $\land$ :
$$\boxed{\begin{array}{cc|c}
A & B & A \land B \\
\hline
T & T & T \\
T & F & F \\
F & T & F \\
F & F & F
\end{array}}$$
Using these we can figure out the truth value of any composite proposition $P$ when we are given the truth values of the propositions it is build up from (let's call this the set $\mathsf{atoms}(P)$).
If $P$ is true no matter the truth values of the propositions in $\mathsf{atoms}(P)$, then we call $P$ semantically true and let's write $\vDash P$ to express this. This is why you usually do a table consisting of all the propositions in $\mathsf{atoms}(P)$, try out all their possible truth value assignments over several rows, and check if $P$ always gets $\mathsf{true}$ as a result.
And now, in the best case scenario, when we have chosen the right deduction rules and the right definition of semantics, we get a wonderful connection between the two sides of the coin:

$\vdash P ~~\Longleftrightarrow ~~\vDash P$

Or in words: There is a deductive proof of $P$ if and only if it is semantically true. And by this connection there is no need to repeat writing "which is true" or similar statements during a text-style proof, since we are on one side of the coin then.

To wrap this up, I will give an example by proving the proposition $(A \to B) \lor (B \to C)$ in both ways.
First the more commonly known way, using a truth table:
$$\boxed{\begin{array}{ccc|ccc}
A & B & C & A \to B & B \to C & (A \to B) \lor (B \to C) \\
\hline
T & T & T & T & T & T \\
T & T & F & T & F & T \\
T & F & T & F & T & T \\
T & F & F & F & T & T \\
F & T & T & T & T & T \\
F & T & F & T & F & T \\
F & F & T & T & T & T \\
F & F & F & T & T & T
\end{array}}$$
Next with a deductive text-style proof where I implicitly use the inference rules for classical propositional logic:

We need to show $(A \to B) \lor (B \to C)$. By the law of excluded middle we know that either $B$ or $\neg B$.

In the case that we have $H_1 : B$ we can show $A \to B$, since assuming $A$, we can already show $B$ because of $H_1$. Because of this we can in particular show $(A \to B) \lor (B \to C)$.
If we have $H_2 : \neg B$, then we can prove $B \to C$, since given $B$ we have a contradiction to $H_2$ and therefore by explosion (always sounds so dramatic!) we have $C$. And again, this also shows $(A \to B) \lor (B \to C)$. $\hspace{0.3em} \Box$

If you want a more thourough introduction into these aspects, I can really recommend the books by Peter Smith on Logic. Some are freely available on his website.


TITLE: Unital Commutative Banach $*$-algebra has $1^*=1$
QUESTION [0 upvotes]: I am wondering why $1^*=1$ in a unital commutative Banach $*$-algebra.
I guess I am having trouble with comprehending what the $*$-algebra is.

REPLY [2 votes]: Recall that a unit is unique, and consider the computation:
\begin{equation}
 a^{*} = (1a)^{*} = a^{*} 1^{*} = 1^{*} a^{*},
\end{equation}
where $a$ is any element in the Banach algebra. We see that $1^{*}$ is a unit, and by uniqueness of the unit it follows that $1^{*} = 1$.


TITLE: Learning about EXPTIME and EXPSPACE
QUESTION [1 upvotes]: I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE.  I'd like to learn more about these two topics, but I'm not sure what the best approach is....

REPLY [1 votes]: You may start from the connection between polynomial identity problem and exponential time classes. Polynomial identity problem has significant importance in both algorithm and
complexity theory. The recent breakthrough for faster exponential time exact algorithm for Hamiltonian cycle problem
was derived via a reduction to polynomial identity. From the complexity point of view,
derandomization of polynomial identity implies the separation of NEXP or PP from P/ploy.
Therefore, I believe that polynomial identity will continue to play an important role in both
algorithm and complexity theory. It is closely related to some exponential time algorithmes, and
also the separations between exponential time classes and non-uniform circuit classes.


TITLE: On the Euler characteristic of a Poincaré duality space
QUESTION [8 upvotes]: Background. Suppose that $M$ is an oriented, connected, closed manifold of dimension $d$ with fundamental class $\mu \in H_d(M;\Bbb Z)$. Let $\Delta : M \to M \times M$ be the diagonal map. Then the pushforward $\Delta_\ast\mu \in H_d(M\times M)$ is defined.
If we apply the intersection pairing to $\Delta_\ast\mu$ with itself, we obtain the self-intersection class
$$\Delta_\ast \mu \cdot \Delta_\ast \mu \in H_0(M\times M) \cong \Bbb Z .$$
If I'm not mistaken, then $\Delta_\ast \mu \cdot \Delta_\ast \mu$ is the Euler characteristic
of $M$ multiplied by a suitable generator.
I know of two proofs, but both of them use a certain amount of geometry. The first proof
interprets the intersection of the cycles representing $\Delta_\ast \mu$ (i.e., the image of the diagonal map) as the transversal self-intersection of the
diagonal with itself. The latter is supported in a tubular neighborhood of the diagonal.
Then one makes use of the tubular neighborhood theorem to interpret the that self-intersection as the  transversal intersection of the zero section of tangent bundle with itself. Lastly, one uses the Poincaré–Hopf index theorem to interpret the latter as the Euler characteristic.
The other proof I know of is along the lines of Milnor and Stasheff Chapter 11.  However, the latter would also seem to require the tubular neighborhood theorem to interpret the pullback $\Delta^\ast(u'')$ of the diagonal cohomology class $u'' \in H^d(M\times M)$
as the Euler class of the tangent bundle of $M$.
In summary, as far as I know, there is no proof that $\Delta_\ast \mu \cdot \Delta_\ast \mu$ is the Euler characteristic of $M$ which doesn't make use of the tubular neighborhood theorem. Note too that the intersection $\Delta_\ast \mu \cdot \Delta_\ast \mu$ does not require transversality to define—one may take the Poincaré dual of $\Delta_\ast \mu$, then apply the cup square and then apply Poincaré duality again.
My Question. Suppose now that $M$ is merely an oriented connected Poincaré duality space
of dimension $d$, with fundamental class $\mu$.
Does $\Delta_\ast \mu \cdot \Delta_\ast \mu$ coincide with the Euler characteristic of $M$?
Note that the analogue of the tubular neighborhood theorem is not generally known to hold in the Poincaré case (i.e., there may not be a Poincaré embedding of the diagonal map).

REPLY [14 votes]: It follows from Poincaré duality in $M\times M$. I'll suppress gradings and be vague about signs here.
Let $x_i$ be a rational homology basis for $M$. Let $a_i$ be the cohomology basis that is dual to this basis in the linear algebra sense: $\langle a_i,x_j\rangle=\delta_{ij}$. Let $y_i$ be the homology basis that corresponds to $a_i$ by Poincaré duality. In other words, the intersection product of $x_i$ and $y_j$ is $\pm \delta_{ij}$.
Then $\Delta_\ast\mu$ is the sum of $\pm x_i\times y_i$, and it's also the sum of $\pm y_j\times x_j$, so the intersection product of $\Delta_\ast\mu$ with itself is the sum, over $i$ and $j$, of $\pm\delta_{ij}\delta_{ji}$, i.e. the sum of $\pm\delta_{ii}$. This is the Euler characteristic, if you get the signs right.


TITLE: Definition of left regular representation of $G$.
QUESTION [6 upvotes]: I don't really understand the definition of left regular representation of $G$. Could anyone give me some explanation or examples?

The permutation representation afforded by left multiplication on the elements of $G$ (cosets of $H = 1$) is called the left regular representation of $G$.

REPLY [8 votes]: Let $G$ be a group, then you can get an homomorphisms
$$ f \colon G \to S(G)$$
where $S(G)$ is the group of permutations on $G$, defined as the mapping that send every $g \in G$ in the mapping $f(g) \colon G \to G$ such that for every $x \in G$ the equation
$$f(g)(x)=gx$$
holds.
Associativity and unit axioms grant that $f$ is an homomorphism of groups:

for all $g,h \in G$ and $x \in G$ we have
$$f(gh)(x)=(gh)x=g(hx)=f(g)(hx)=f(g)(f(h)(x))=f(g)\circ f(h)(x)$$
for all $x \in G$ the equality
$$f(1)(x)=1x=x$$
holds.

This homomorphism $f$ is the left regular representation (it represents the elements of the group $G$ as symmetries of the same group seen just as a set).
The name left is to distinguish from the (anti)-homomorphism
$$f' \colon G \to S(G)$$
that to every $g \in G$ associate $f'(g) \colon G \to G$ such that for every $x \in G$ we have $f'(g)(x) = xg$.
Via the correspondence between actions and homomorphisms in symmetric groups left regular representation are those representation that correspond to left-action of $G$ on itself given by multiplication.
Hope this helps.