text:
\section{Analysis of \fedac for general convex objectives}
\label{sec:gcvx}
\subsection{Main theorems}
In this section we study the convergence of \fedac for general convex ($\mu = 0$) objectives. Let $F$ be a general convex function, the main idea is to apply \fedac to the $\ell_2$-augmented $\tilde{F}_{\lambda}(w)$ defined as
\begin{equation}
    \tilde{F}_{\lambda}(w) := F(w) + \frac{1}{2} \lambda \|w - w_0\|^2,
    \label{eq:aug}
\end{equation}
where $w_0$ is the initial guess. Let $w_{\lambda}^*$ be the optimum of $\tilde{F}_{\lambda}(w)$ and define $\tilde{F}_{\lambda}^* := \tilde{F}_{\lambda}(w_{\lambda}^*)$.

One can verify that if $F$ satisfies \cref{asm1} with general convexity ($\mu = 0$) and $L$-smoothness, then $\tilde{F}_{\lambda}$ satisfies \cref{asm1} with smoothness $L+\lambda$ and strong-convexity $\lambda$ (variance does not change). If $F$ satisfies \cref{asm2}, then $\tilde{F}_{\lambda}$ also satisfies \cref{asm2} with the same $Q$-\nth{3}-order-smoothness (\nth{4}-order central moment does not change).

Now we state the convergence theorems. Note that the bounds in \cref{tab:conv:rate} can be obtained by replacing $K = T/R$. Recall $\|D_0 := \|w_0 - w^*\|$.
\begin{theorem}[Convergence of \fedaci for general convex objective, under \cref{asm1}]
    \label{fedaci:a1:gcvx}
    Assume \cref{asm1} where $F$ is general convex. Then for any $T \geq 24$,\footnote{We assume this constant lower bound for technical simplification.} applying \fedaci to $\tilde{F}_{\lambda}$ \eqref{eq:aug} with
    \begin{equation}
        \lambda
        =
        \max \left\{\frac{\sigma}{M^{\frac{1}{2}}T^{\frac{1}{2}} D_0},
        \frac{L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}}}{T D_0^{\frac{2}{3}}},
        \frac{2LK}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right) \right\},
    \end{equation}
    and hyperparameter
    \begin{equation}
        \eta = \min \left\{ \frac{1}{L + \lambda},
        \frac{K}{\lambda T^2} \log^2  \left( \euler + \min \left\{ \frac{\lambda L M T D_0^2}{\sigma^2}, \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right\}\right),
        \frac{L^{\frac{1}{3}} K^{\frac{1}{3}}  D_0^{\frac{2}{3}}}{\lambda^{\frac{2}{3}}T \sigma^{\frac{2}{3}}},
        \frac{L^{\frac{1}{4}} K^{\frac{1}{4}}  D_0^{\frac{1}{2}}}{\lambda^{\frac{3}{4}} T \sigma^{\frac{1}{2}}}
        \right\}
    \end{equation}
    yields
    \begin{align}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
       \leq &
       \frac{2L K D_0^2}{T^2} \log^{2} \left( \euler^2 + \frac{T^2}{K} \right)
       +
       \frac{2\sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}}
       \log^2 \left( \euler^2 + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right)
       \\
       & \qquad
       +
       \frac{1005 L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}}}{T}
       \log^4 \left( \euler^4 +  \frac{L^{\frac{2}{3}} T D_0^{\frac{2}{3}} }{K^{\frac{2}{3}} \sigma^{\frac{2}{3}}} \right).
   \end{align}
\end{theorem}
The proof of \cref{fedaci:a1:gcvx} is deferred to \cref{sec:fedaci:a1:gcvx}.

\begin{theorem}[Convergence of \fedacii for general convex objective, under \cref{asm1}]
    \label{fedacii:a1:gcvx}
    Assume \cref{asm2} where $F$ is general convex. Then for any $T \geq 10^3$, applying \fedacii to $\tilde{F}_{\lambda}$ \eqref{eq:aug} with
    \begin{equation}
        \lambda =
        \max \left\{ \frac{\sigma}{M^{\frac{1}{2}} T^{\frac{1}{2}} D_0},
        \frac{L^{\frac{1}{2}} K^{\frac{3}{4}} \sigma^{\frac{1}{2}} }{T D_0^{\frac{1}{2}} },
        \frac{18 LK}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right)         \right\},
    \end{equation}
    and hyperparameter
    \begin{equation}
        \eta =
        \min \left\{
        \frac{1}{L+\lambda}
            ,
        \frac{9K}{\lambda T^2}
        \log^2 \left( \euler +
        \min \left\{ \frac{\lambda LMT D_0^2}{\sigma^2}, \frac{\lambda^3 T^4 D_0^2}{LK^3 \sigma^2} \right\} \right),
        \frac{L^{\frac{1}{3}} D_0^{\frac{2}{3}} }{\lambda^{\frac{2}{3}} T^{\frac{2}{3}} \sigma^{\frac{2}{3}}}
        \right\}
    \end{equation}
    yields
    \begin{align}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq &
        \frac{10LKD_0^2}{T^2}  \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        +
        \frac{5 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}} \log \left( \euler + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right)
        \\
        & \qquad +
        \frac{16411 L^{\frac{1}{2}} K^{\frac{3}{4}} \sigma^{\frac{1}{2}}  D_0^{\frac{3}{2}}}{T}
        \log^4 \left( \euler^4 +
        \frac{L^{\frac{1}{2}} T D_0^{\frac{1}{2}}}{K^{\frac{3}{4}} \sigma^{\frac{1}{2}}} \right).
    \end{align}
\end{theorem}
The proof of \cref{fedacii:a1:gcvx} is deferred to \cref{sec:fedacii:a1:gcvx}.

\begin{theorem}[Convergence of \fedacii for general convex objective, under \cref{asm2}]
    \label{fedacii:a2:gcvx}
    Assume \cref{asm2} where $F$ is general convex. Then for any $T \geq 10^3$, applying \fedacii to $\tilde{F}_{\lambda}$ \eqref{eq:aug} with
    \begin{equation}
        \lambda =
        \max \left\{
        \frac{\sigma}{M^{\frac{1}{2}} T^{\frac{1}{2}} D_0},
        \frac{L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} }{M^{\frac{1}{3}} T D_0^{\frac{2}{3}} },
        \frac{Q^{\frac{1}{3}} K \sigma^{\frac{2}{3}}}{ T^{\frac{4}{3}} D_0^{\frac{1}{3}}},
        \frac{18 LK}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        \right\},
    \end{equation}
    and hyperparameter
    \begin{equation}
        \eta =
        \min \left\{
        \frac{1}{L+\lambda}
            ,
         \frac{9K}{\lambda T^2}
            \log^2 \left( \euler +
            \min \left\{ \frac{\lambda LMT D_0^2}{\sigma^2},
            \frac{\lambda^2 M T^3 D_0^2}{K^2 \sigma^2},
            \frac{\lambda^5 L T^8 D_0^2}{Q^2 K^6 \sigma^4} \right\} \right)
        ,
        \frac{ L^{\frac{1}{3}} K^{\frac{1}{3}} M^{\frac{1}{3}} D_0^{\frac{2}{3}}}{\lambda^{\frac{2}{3}}T \sigma^{\frac{2}{3}}}
        \right\}
    \end{equation}
    yields
    \begin{align}
        & \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq
        \frac{10LKD_0^2}{T^2}  \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        +
        \frac{5 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}} \log \left( \euler + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right)
        \\
        & +
        \frac{139 L^{\frac{1}{3}} K^{\frac{2}{3}}  \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}}}{M^{\frac{1}{3}}T}
        \log^3 \left( \euler^3 +
        \frac{L^{\frac{2}{3}} M^{\frac{1}{3}} T D_0^{\frac{2}{3}}}{  K^{\frac{2}{3}} \sigma^{\frac{2}{3}}} \right)
        +
        \frac{\euler^{19} Q^{\frac{1}{3}} K  \sigma^{\frac{2}{3}} D_0^{\frac{5}{3}} }{T^{\frac{4}{3}}}
        \log^8 \left( \euler^8 +  \frac{L T^{\frac{4}{3}} D_0^{\frac{1}{3}}}{Q^{\frac{1}{3}} K  \sigma^{\frac{2}{3}} }  \right).
    \end{align}
\end{theorem}
The proof of \cref{fedacii:a2:gcvx} is deferred to \cref{sec:fedacii:a2:gcvx}.

For comparison, we also establish the convergence of \fedavg for general convex objective under \cref{asm2}.
\begin{theorem}[Convergence of \fedavg for general convex objective, under \cref{asm2}]
    \label{fedavg:a2:gcvx}
    Assume \cref{asm2} where $F$ is general convex, then for any $T \geq 100$,  applying \fedavg to $\tilde{F}_{\lambda}$ \eqref{eq:aug} with
    \begin{equation}
        \lambda :=
        \max \left\{        \frac{\sigma}{M^{\frac{1}{2}} T^{\frac{1}{2}} D_0},
        \frac{Q^{\frac{1}{3}} K^{\frac{1}{3}} \sigma^{\frac{2}{3}}}{ T^{\frac{2}{3}} D_0^{\frac{1}{3}}},
        \frac{16L }{T} \log (\euler + T)
        \right\},
    \end{equation}
    and hyperparameter $\eta$
    \begin{equation}
        \eta := \min \left\{ \frac{1}{4(L+\lambda)}, \frac{2}{\lambda T} \log \left( \euler + \min \left\{ \frac{\lambda^2 M T^2 D_0^2}{\sigma^2}, \frac{\lambda^6 T^5 D_0^2}{Q^2 K^2 \sigma^4}\right\} \right)\right\}
    \end{equation}
   yields

    \begin{equation}
        \expt \left[ F \left( \sum_{t=0}^{T-1} \frac{\rho_t}{S_T} \overline{w_t} \right)   - F^* \right]
        \leq \frac{50 L D_0^2}{T} \log (\euler + T)
        +
        \frac{6 \sigma D_0}{ M^{\frac{1}{2}} T^{\frac{1}{2}}}
        \log
        \left( \euler^2 +  T \right)
        +
        \frac{3076 Q^{\frac{1}{3}}  K^{\frac{1}{3}}  \sigma^{\frac{2}{3}} D_0^{\frac{5}{3}}} { T^{\frac{2}{3}}}
        \log^4 \left( \euler^5 + T \right)
    \end{equation}

    where $\rho_t := (1 - \frac{1}{2} \eta \lambda)^{T-t-1}$, $S_T := \sum_{t=0}^{T-1}\rho_t$.
\end{theorem}
The proof of \cref{fedavg:a2:gcvx} is deferred to \cref{sec:fedavg:a2:gcvx}.

\subsection{Proof of \cref{fedaci:a1:gcvx} on \fedaci for general-convex objectives under \cref{asm1}}
\label{sec:fedaci:a1:gcvx}
We first introduce the supporting lemmas for \cref{fedaci:a1:gcvx}.
\begin{lemma}
    \label{fedaci:gcvx:1}
    Assume \cref{asm1} where $F$ is general convex, then for any $\lambda > 0$, for any $\eta \leq \frac{1}{L+\lambda}$, applying \fedaci to $\tilde{F}_{\lambda}$ gives
     \begin{align}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq &
        \frac{1}{2}\lambda  D_0^2
        +
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda}{K}}T \right)
        +
        \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \lambda^{\frac{1}{2}} M K^{\frac{1}{2}}}
        +
        \frac{\eta \sigma^2}{2M}
        \\
        &
        +
        \frac{390 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2} {\lambda^{\frac{1}{2}}}
        +
        7 \eta^2 L K \sigma^2
        +
        390 \eta^{\frac{3}{2}} \lambda^{\frac{1}{2}} K^{\frac{1}{2}} \sigma^2
        +
        7 \eta^2 \lambda K \sigma^2.
        \label{eq:fedaci:gcvx:1}
      \end{align}
\end{lemma}
The proof of \cref{fedaci:gcvx:1} is deferred to \cref{sec:fedaci:gcvx:1}.
Now we plug in $\eta$.
\begin{lemma}
    \label{fedaci:gcvx:2}
    Assume \cref{asm1} where $F$ is general convex, then for any $\lambda > 0$, for
    \begin{equation}
        \eta = \min \left\{ \frac{1}{L + \lambda},
        \frac{K}{\lambda T^2}
        \log^2  \left( \euler + \min \left\{ \frac{\lambda L M T D_0^2}{\sigma^2}, \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right\}\right),
        \frac{L^{\frac{1}{3}} K^{\frac{1}{3}}  D_0^{\frac{2}{3}}}{\lambda^{\frac{2}{3}}T \sigma^{\frac{2}{3}}},
        \frac{L^{\frac{1}{4}} K^{\frac{1}{4}}  D_0^{\frac{1}{2}}}{\lambda^{\frac{3}{4}} T \sigma^{\frac{1}{2}}}
        \right\},
    \end{equation}
    applying \fedaci to $\tilde{F}_{\lambda}$ gives
    \begin{align}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq
        &
        \frac{1}{2} \lambda D_0^2
        +
        \frac{3\sigma^2}{2\lambda MT}  \log^2 \left( \euler^2 + \frac{\lambda LMT  D_0^2}{\sigma^2} \right)
        \\
        &
        +
        \frac{592 LK^2 \sigma^2}{\lambda^2 T^3} \log^4 \left( \euler^4 + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right)
        \\
        & +
        \frac{412 L^{\frac{1}{2}} K \sigma D_0 }{\lambda^{\frac{1}{2}}  T^{\frac{3}{2}} }
        +
        \frac{1}{2} L D_0^2 \exp \left(  -  \sqrt{\frac{1}{(1 + L/\lambda) K}}T \right).
        \label{eq:fedaci:gcvx:2}
    \end{align}
\end{lemma}

\begin{proof}[Proof of \cref{fedaci:gcvx:2}]
    To simplify the notation, we name the terms of RHS of \cref{eq:fedaci:gcvx:1} as
    \begin{alignat}{2}
        & \varphi_0 (\eta) := \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda}{K}}T \right),
        &&
        \\
        &
        \varphi_1 (\eta) := \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \lambda^{\frac{1}{2}} M K^{\frac{1}{2}}},
        \quad
        &&
        \varphi_2(\eta) :=\frac{\eta \sigma^2}{2M},
        \\
        & \varphi_3 (\eta) :=
        \frac{390 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2} {\lambda^{\frac{1}{2}}},
        \quad
        &&
        \varphi_4 (\eta) :=
        7 \eta^2 L K \sigma^2,
        \\
        &
        \varphi_5 (\eta) :=
        390 \eta^{\frac{3}{2}} \lambda^{\frac{1}{2}} K^{\frac{1}{2}} \sigma^2,
        \quad
        &&
        \varphi_6 (\eta) :=
        7 \eta^2 \lambda K \sigma^2.
    \end{alignat}
Define
\begin{equation}
    \eta_1 := \frac{K}{ \lambda T^2}
    \log^2  \left( \euler^2 + \min \left\{ \frac{\lambda L M T D_0^2}{\sigma^2}, \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right\}\right)
    ,
    \quad
    \eta_2 := \frac{ L^{\frac{1}{3}} K^{\frac{1}{3}} D_0^{\frac{2}{3}}}{\lambda^{\frac{2}{3}}T \sigma^{\frac{2}{3}}},
    \quad
    \eta_3 := \frac{ L^{\frac{1}{4}} K^{\frac{1}{4}}  D_0^{\frac{1}{2}}}{\lambda^{\frac{3}{4}} T \sigma^{\frac{1}{2}}}.
\end{equation}
then $\eta = \min \left\{ \eta_1, \eta_2, \eta_3, \frac{1}{L + \lambda}\right\}$.
Now we bound $\varphi_1(\eta), \ldots, \varphi_6(\eta)$ term by term.
\begin{align}
    \varphi_1(\eta)
    & \leq
    \varphi_1(\eta_1)
    \leq
    \frac{\sigma^2}{2\lambda MT} \log \left( \euler + \frac{\lambda LMT  D_0^2}{\sigma^2} \right),
    \\
    \varphi_2(\eta)
    & \leq
    \varphi_2(\eta_1)
    \leq
    \frac{K \sigma^2}{2 \lambda M  T^2} \log^2 \left( \euler + \frac{\lambda LMT  D_0^2}{\sigma^2}  \right)
    \leq
    \frac{\sigma^2}{2\lambda MT} \log^2 \left( \euler + \frac{\lambda LMT  D_0^2}{\sigma^2} \right),
    \tag{since $K \leq T$}
    \\
    \varphi_3(\eta)
    & \leq
    \varphi_3(\eta_1)
    \leq
    \frac{390LK^2 \sigma^2}{\lambda^2 T^3} \log^3 \left( \euler + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right),
    \\
    \varphi_4(\eta)
    & \leq
    \varphi_4(\eta_1)
    \leq
    \frac{7 LK^3 \sigma^2}{\lambda^2 T^4}
    \log^4 \left( \euler + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right)
    \leq
    \frac{7LK^2 \sigma^2}{\lambda^2 T^3} \log^4 \left( \euler + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right),
    \tag{since $K \leq T$}
    \\
    \varphi_5(\eta)
    & \leq
    \varphi_5(\eta_2)
    =
    \frac{390 L^{\frac{1}{2}} K   D_0 \sigma}{\lambda^{\frac{1}{2}} T^{\frac{3}{2}}},
    \\
    \varphi_6(\eta)
    & \leq
    \varphi_6(\eta_3)
    \leq
    7 \eta_3^2 \lambda K \sigma^2 = \frac{7 L^{\frac{1}{2}} K^{\frac{3}{2}}  D_0 \sigma}{\lambda^{\frac{1}{2}} T^2 }
    \leq
    \frac{7 L^{\frac{1}{2}} K   D_0 \sigma}{\lambda^{\frac{1}{2}} T^{\frac{3}{2}}}.
    \tag{since $K \leq T$}
\end{align}
In summary
\begin{equation}
    \sum_{i=1}^6 \varphi_i(\eta) \leq \frac{\sigma^2}{\lambda MT}\log^2 \left( \euler^2 + \frac{\lambda LMT  D_0^2}{\sigma^2} \right)
    +
    \frac{397LK^2 \sigma^2}{\lambda^2 T^3} \log^4 \left( \euler^4 + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right)
    +
    \frac{397 L^{\frac{1}{2}} K   D_0 \sigma}{\lambda^{\frac{1}{2}} T^{\frac{3}{2}}}.
    \label{eq:fedaci:gcvx:2:1}
\end{equation}
On the other hand $\varphi_0(\eta) \leq \varphi_0(\eta_1) + \varphi_0(\eta_2) + \varphi_0(\eta_3) + \varphi_0(\frac{1}{L + \lambda})$, where
\begin{align}
    \varphi_0(\eta_1)
    & =
    \frac{1}{2} L D_0^2  \left( \euler^2 + \min \left\{ \frac{\lambda L M T D_0^2}{\sigma^2}, \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right\}\right)^{-1}
     \leq  \frac{\sigma^2}{2\lambda M T} + \frac{195 L K^2 \sigma^2}{\lambda^2 T^3},
    \\
    \varphi_0(\eta_2)
    & \leq
    \frac{3!}{2}  L D_0^2 \left( \sqrt{\frac{\eta_2 \lambda}{K}}T \right)^{-3}
    =
     \frac{3 L K^{\frac{3}{2}} D_0^2}{\eta_2^{\frac{3}{2}} \lambda^{\frac{3}{2}} T^3}
     =
     \frac{3 L^{\frac{1}{2}} K D_0 \sigma }{\lambda^{\frac{1}{2}}    T^{\frac{3}{2}} },
    \\
    \varphi_0(\eta_3)
    & \leq
    \frac{4!}{2}  L D_0^2 \left( \sqrt{\frac{\eta_3 \lambda}{K}}T \right)^{-4}
    =
    \frac{12 L K^2 D_0^2}{\eta_3^{2} \lambda^{2} T^4}
    =
    \frac{12 L^{\frac{1}{2}} K^{\frac{3}{2}}  \sigma D_0}{\lambda^{\frac{1}{2}}  T^{2}}
    \leq
    \frac{12 L^{\frac{1}{2}} K D_0 \sigma }{\lambda^{\frac{1}{2}}    T^{\frac{3}{2}} }.
\end{align}
In summary
\begin{equation}
    \varphi_0(\eta)
    \leq
    \frac{1}{2} L D_0^2 \exp \left(  -  \sqrt{\frac{\lambda}{(L + \lambda) K}}T \right)
    +
    \frac{\sigma^2}{2 \lambda M T}
    + \frac{195 L K^2  \sigma^2}{\lambda^2 T^3}
    +
    \frac{15 L^{\frac{1}{2}} K   D_0 \sigma}{\lambda^{\frac{1}{2}}  T^{\frac{3}{2}} }.
    \label{eq:fedaci:gcvx:2:2}
\end{equation}
Combining \cref{fedaci:gcvx:1,eq:fedaci:gcvx:2:1,eq:fedaci:gcvx:2:2} gives
\begin{align}
    & \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
    \leq \sum_{i=0}^6 \varphi_i(\eta) + \frac{1}{2} \lambda D_0^2
    \\
    \leq &
    \frac{1}{2} \lambda D_0^2
    +
    \frac{3\sigma^2}{2\lambda MT}  \log^2 \left( \euler^2 + \frac{\lambda LMT  D_0^2}{\sigma^2} \right)
    +
    \frac{592 LK^2 \sigma^2}{\lambda^2 T^3} \log^4 \left( \euler^4 + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right)
    \\
    & +
    \frac{412 L^{\frac{1}{2}} K \sigma D_0 }{\lambda^{\frac{1}{2}}  T^{\frac{3}{2}} }
    +
    \frac{1}{2} L D_0^2 \exp \left(  -  \sqrt{\frac{1}{(1 + L/\lambda) K}}T \right).
\end{align}
\end{proof}
The main \cref{fedaci:a1:gcvx} then follows by plugging in the appropriate $\eta$.
\begin{proof}[Proof of \cref{fedaci:a1:gcvx}]
To simplify the notation, we name the terms on the RHS of \cref{eq:fedaci:gcvx:2} as
\begin{alignat}{2}
    &
    \psi_0(\lambda) := \frac{1}{2} \lambda D_0^2,
    \quad
    &&
    \psi_1(\lambda) := \frac{3\sigma^2}{2\lambda MT}  \log^2 \left( \euler^2 + \frac{\lambda LMT  D_0^2}{\sigma^2} \right),
    \\
    &
    \psi_2(\lambda) :=  \frac{592 LK^2 \sigma^2}{\lambda^2 T^3} \log^4 \left( \euler^4 + \frac{\lambda^2 T^3 D_0^2}{K^2 \sigma^2} \right),
    \quad
    &&
    \psi_3(\lambda) := \frac{412 L^{\frac{1}{2}} K   D_0 \sigma}{\lambda^{\frac{1}{2}}  T^{\frac{3}{2}} },
    \\
    &
    \psi_4(\lambda) := \frac{1}{2} L D_0^2 \exp \left(  -  \sqrt{\frac{1}{(1 + L/\lambda) K}}T \right).
    &&
\end{alignat}
Let
\begin{equation}
    \lambda_1 := \frac{\sigma}{M^{\frac{1}{2}}T^{\frac{1}{2}} D_0},
    \quad
    \lambda_2 := \frac{L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}}}{T D_0^{\frac{2}{3}}},
    \quad
    \lambda_3 := \frac{2KL}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right),
\end{equation}
then
\(
    \lambda := \max \left\{ \lambda_1, \lambda_2, \lambda_3 \right\}.
\)
By helper \cref{helper:inv:times:log}, $\psi_1$ and $\psi_2$ are monotonically decreasing w.r.t $\lambda$ for $\lambda > 0$. $\psi_3$ is trivially decreasing. Thus
\begin{align}
    \psi_1(\lambda)
    & \leq
    \psi_1(\lambda_1)
    \leq
    \frac{3\sigma D_0}{2M^{\frac{1}{2}} T^{\frac{1}{2}}}
    \log^2 \left( \euler^2 + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right),
    \label{eq:fedaci:a1:gcvx:proof:1}
    \\
    \psi_2(\lambda)
    & \leq
    \psi_2(\lambda_2)
    \leq
    \frac{592 L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}}}{T}
    \log^4 \left( \euler^4 +  \frac{L^{\frac{2}{3}} T D_0^{\frac{2}{3}} }{K^{\frac{2}{3}} \sigma^{\frac{2}{3}}} \right),
    \label{eq:fedaci:a1:gcvx:proof:2}
    \\
    \psi_3(\lambda)
    & \leq
    \psi_3(\lambda_2)
    =
    \frac{412 L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}}}{T}.
    \label{eq:fedaci:a1:gcvx:proof:3}
\end{align}
Now we analyze $\psi_4(\lambda_3)$. Note first that
\(
        \frac{\lambda_3}{L} = \frac{2K}{T^2} \log^{2} \left( \euler^2 + \frac{T^2}{K} \right).
\)
Since $T \geq 24$ we have $\frac{T^2}{K} \geq 24$. By helper \cref{helper:inv:times:log}, $x^{-1} \log^{2} (\euler^2 + x)$ is monotonically decreasing over $(0, +\infty)$, thus
\begin{equation}
    \frac{\lambda_3}{L} = \frac{2K}{T^2} \log^{2} \left( \euler^2 + \frac{T^2}{K} \right)
    \leq
    \frac{1}{12} \log^2 (\euler^2 + 24) < 1.
\end{equation}
Hence
\begin{equation}
    1 + \frac{L}{\lambda_3}
    \leq
    \frac{2L}{\lambda_3}
    =
    \frac{T^2}{K} \log^{-2}\left( \euler^2 + \frac{T^2}{K} \right).
\end{equation}
We conclude that
\begin{align}
    \psi_4(\lambda)
    & \leq
    \psi_4(\lambda_3)
    =
    \frac{1}{2} L D_0^2 \exp \left(  -  \sqrt{\frac{1}{(1 + L/\lambda_3) K}}T \right)
    \leq
    \frac{1}{2} L D_0^2 \left( \euler^2 + \frac{T^2}{K} \right)^{-1}
    \leq
    \frac{LKD_0^2}{2T^2}.
    \label{eq:fedaci:a1:gcvx:proof:4}
\end{align}
Finally note that
\begin{align}
    \psi_0(\lambda) & \leq \frac{1}{2} \lambda_1 D_0^2 + \frac{1}{2} \lambda_2 D_0^2 + \frac{1}{2} \lambda_3 D_0^2
    = \frac{\sigma D_0}{2 M^{\frac{1}{2}} T^{\frac{1}{2}} } + \frac{L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}} }{2 T} + \frac{L K D_0^2}{T^2} \log^{2} \left( \euler^2 + \frac{T^2}{K} \right).
    \label{eq:fedaci:a1:gcvx:proof:5}
\end{align}
Combining \cref{fedaci:gcvx:2,eq:fedaci:a1:gcvx:proof:1,eq:fedaci:a1:gcvx:proof:2,eq:fedaci:a1:gcvx:proof:3,eq:fedaci:a1:gcvx:proof:4,eq:fedaci:a1:gcvx:proof:5} gives
\begin{align}
     & \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
    \leq \sum_{i=0}^4 \psi_i(\lambda)
    \\
    \leq &
    \frac{2L K D_0^2}{T^2} \log^{2} \left( \euler^2 + \frac{T^2}{K} \right)
    +
    \frac{2\sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}}
    \log^2 \left( \euler^2 + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right)
    \\
    & \qquad
    +
    \frac{1005 L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}}}{T}
    \log^4 \left( \euler^4 +  \frac{L^{\frac{2}{3}} T D_0^{\frac{2}{3}} }{K^{\frac{2}{3}} \sigma^{\frac{2}{3}}} \right).
\end{align}
\end{proof}

\subsubsection{Proof of \cref{fedaci:gcvx:1}}
\label{sec:fedaci:gcvx:1}
We first introduce a supporting proposition for \cref{fedaci:gcvx:1}.
\begin{proposition}
    \label{fedaci:gcvx:0}
    Assume $F$ is general convex and $L$-smooth, and let $\Psi_t$ be the decentralized potential \cref{eq:fedaci:potential} for $\tilde{F}_{\lambda}$, namely
    \begin{equation}
        \Psi_t := \frac{1}{M} \sum_{m=1}^M \left( \tilde{F}_{\lambda}(w_t^{\mathrm{ag},m}) - \tilde{F}_{\lambda}^*  \right)  + \frac{1}{2} \lambda \|\overline{w_T} - w_{\lambda}^*\|^2.
    \end{equation}
    Then
    \begin{equation}
        \Psi_T \geq F(\overline{w_T^{\mathrm{ag}}}) - F^* - \frac{1}{2} \lambda D_0^2
        ,
        \qquad
        \Psi_0 \leq \frac{1}{2} L \|w_0 - w^*\|^2.
    \end{equation}
\end{proposition}

\begin{proof}[Proof of \cref{fedaci:gcvx:0}]
    Since $w_{\lambda}^*$ optimizes $\tilde{F}_{\lambda}(w)$ we have $\tilde{F}_{\lambda}(w_{\lambda}^*) \leq \tilde{F}_{\lambda}(w^*)$ (recall $w^*$ is defined as the optimum of the un-augmented objective $F$), and thus
    \begin{equation}
        \tilde{F}_{\lambda}^* = F(w_{\lambda}^*) + \frac{1}{2}\lambda \|w_{\lambda}^* - w_0\|^2
        \leq
        F(w^*) + \frac{1}{2} \lambda \|w^* - w_0\|^2.
        \label{eq:fedaci:gcvx:0:1}
    \end{equation}
    Consequently, $\Psi_T$ is lower bounded as
    \begin{align}
        \Psi_T & = \frac{1}{M} \sum_{m=1}^M \left( \tilde{F}_{\lambda}(w_T^{\mathrm{ag},m}) - \tilde{F}_{\lambda}^*  \right)
        + \frac{1}{2} \lambda \|\overline{w_T} - w_{\lambda}^*\|^2
        \geq
        \frac{1}{M} \sum_{m=1}^M \left( \tilde{F}_{\lambda}(w_T^{\mathrm{ag},m}) - \tilde{F}_{\lambda}^*  \right)
        \\
        & = \frac{1}{M} \sum_{m=1}^M \left[ \left( F(w_T^{\mathrm{ag},m}) + \frac{1}{2}\lambda  \|w_T^{\mathrm{ag},m} - w_0\|^2 \right)
        -
        \tilde{F}_{\lambda}^*
         \right]
        \\
        & \geq \frac{1}{M} \sum_{m=1}^M \left[  F(w_T^{\mathrm{ag},m}) - F^*  + \frac{1}{2}\lambda  \left( \|w_T^{\mathrm{ag},m}  - w_0\|^2  - \|w^* - w_0\|^2 \right) \right]
        \tag{by \cref{eq:fedaci:gcvx:0:1}}
        \\
        & \geq \frac{1}{M} \sum_{m=1}^M \left( F(w_T^{\mathrm{ag},m}) - F^* \right) - \frac{1}{2}\lambda \|w^* - w_0\|^2
        \\
        & \geq F(\overline{w_T^{\mathrm{ag}}}) - F^* - \frac{1}{2} \lambda \|w^* - w_0\|^2
        \tag{by convexity}
        \\
        &   = F(\overline{w_T^{\mathrm{ag}}}) - F^* - \frac{1}{2} \lambda D_0^2.
    \end{align}
    The initial potential $\Psi_0$ is upper bounded as
    \begin{align}
        \Psi_0 & = \tilde{F}_{\lambda}(w_0) - \tilde{F}_{\lambda}^*
        + \frac{1}{2} \lambda \|w_{\lambda}^* - w_0\|^2
        \\
        & =   F(w_0) - \left( F(w_{\lambda}^*) + \frac{1}{2}\lambda  \|w_{\lambda}^* - w_0\|^2 \right)
        + \frac{1}{2} \lambda \|w_{\lambda}^* - w_0\|^2
        \tag{by definition of $\tilde{F}_{\lambda}$ \eqref{eq:aug}}
        \\
        & =  F(w_0) - F(w_{\lambda}^*) \leq F(w_0) - F^* \tag{by optimality $F(w_{\lambda}^*) \geq F^*$}
        \\
        & \leq \frac{1}{2} L \|w_0 - w^*\|^2 = \frac{1}{2} L D_0^2.
        \tag{by $L$-smoothness of $F$}
     \end{align}
\end{proof}

\cref{fedaci:gcvx:1} then follows by applying \cref{fedaci:general:eta} and \cref{fedaci:gcvx:0}.
\begin{proof}[Proof of \cref{fedaci:gcvx:1}]
By \cref{fedaci:general:eta} on the convergence of \fedaci, for any $\eta \in (0, \frac{1}{L + \lambda}$),
\begin{equation}
    \expt \left[ \Psi_T \right]
    \leq
     \exp \left(  -  \sqrt{\frac{\eta \lambda}{K}}T \right) \Psi_0
    + \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \lambda^{\frac{1}{2}} M K^{\frac{1}{2}} }
    + \frac{\eta \sigma^2}{2M}
    + \frac{390 \eta^{\frac{3}{2}} (L + \lambda) K^{\frac{1}{2}} \sigma^2} {\lambda^{\frac{1}{2}}}
    + 7 \eta^2 (L + \lambda) K \sigma^2.
\end{equation}
Applying \cref{fedaci:gcvx:0} gives
    \begin{align}
    \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
    \leq &
    \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda}{K}}T \right)
    +
    \frac{1}{2}\lambda  D_0^2
    +
    \frac{\eta^{\frac{1}{2}} \sigma^2}{2 \lambda^{\frac{1}{2}} M K^{\frac{1}{2}}}
    +
    \frac{\eta \sigma^2}{2M}
    \\
    &
    +
    \frac{390 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2} {\lambda^{\frac{1}{2}}}
    +
    7 \eta^2 L K \sigma^2
    +
    390 \eta^{\frac{3}{2}} \lambda^{\frac{1}{2}} K^{\frac{1}{2}} \sigma^2
    +
    7 \eta^2 \lambda K \sigma^2.
  \end{align}
\end{proof}

\subsection{Proof of \cref{fedacii:a1:gcvx} on \fedacii for general-convex objectives under \cref{asm1}}
\label{sec:fedacii:a1:gcvx}
We omit some technical details since the proof is similar to \cref{fedaci:a1:gcvx}.
We first introduce the supporting lemma for \cref{fedacii:a1:gcvx}.
\begin{lemma}
    \label{fedacii:a1:gcvx:1}
    Assume \cref{asm1} where $F$ is general convex, then for any $\lambda > 0$, for any $\eta \leq \frac{1}{L+\lambda}$, applying \fedacii to $\tilde{F}_{\lambda}$ gives
     \begin{equation}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq
        \frac{1}{2}\lambda  D_0^2
        +
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda T^2}{9K}} \right)
        +
        \frac{\eta^{\frac{1}{2}} \sigma^2}{\lambda^{\frac{1}{2}} M K^{\frac{1}{2}}}
        +
        \frac{200 \eta^2 L^2 K \sigma^2}{\lambda}
        +
        200 \eta^2 \lambda K \sigma^2.
        \label{eq:fedacii:a1:gcvx:1}
      \end{equation}
\end{lemma}
The proof of \cref{fedacii:a1:gcvx:1} is deferred to \cref{sec:fedacii:a1:gcvx:1}.
\begin{lemma}
    \label{fedacii:a1:gcvx:2}
    Assume \cref{asm1} where $F$ is general convex, then for any $\lambda > 0$, for
    \begin{equation}
        \eta =
        \min \left\{
        \frac{1}{L+\lambda}
            ,
        \frac{9K}{\lambda T^2}
        \log^2 \left( \euler +
        \min \left\{ \frac{\lambda LMT D_0^2}{\sigma^2}, \frac{\lambda^3 T^4 D_0^2}{LK^3 \sigma^2} \right\} \right),
        \frac{L^{\frac{1}{3}} D_0^{\frac{2}{3}} }{\lambda^{\frac{2}{3}} T^{\frac{2}{3}} \sigma^{\frac{2}{3}}},
        \right\}
    \end{equation}
    applying \fedacii to $\tilde{F}_{\lambda}$ gives
    \begin{align}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq &
        \frac{1}{2}\lambda  D_0^2
        +
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{T^2}{9(1 + L/\lambda)K}} \right)
        +
        \frac{209 L^{\frac{2}{3}} K D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{\lambda^{\frac{1}{3}} T^{\frac{4}{3}}}
        \\
        & +
        \frac{4 \sigma^2}{\lambda M T} \log \left( \euler +
         \frac{\lambda LMT D_0^2}{\sigma^2} \right)
        + \frac{16201 L^2 K^3 \sigma^2}{\lambda^3 T^4}
        \log^4 \left( \euler^4 +
       \frac{\lambda^3 T^4 D_0^2}{LK^3 \sigma^2} \right).
       \label{eq:fedacii:a1:gcvx:2}
    \end{align}
\end{lemma}
\begin{proof}[Proof of \cref{fedacii:a1:gcvx:2}]
    To simplify the notation, define the terms on the RHS of \cref{eq:fedacii:a1:gcvx:1} as
    \begin{alignat}{2}
        & \varphi_0(\eta) :=
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda T^2}{9K}} \right),
        \quad
        &&
        \varphi_1(\eta) :=
        \frac{\eta^{\frac{1}{2}} \sigma^2}{\lambda^{\frac{1}{2}} M K^{\frac{1}{2}}},
        \\
        &
        \varphi_2(\eta) :=
        \frac{200 \eta^2 L^2 K \sigma^2}{\lambda},
        \quad
        &&
        \varphi_3(\eta) :=
        200 \eta^2 \lambda K \sigma^2.
    \end{alignat}
    Define
    \begin{equation}
        \eta_1 :=  \frac{9K}{\lambda T^2}
        \log^2 \left( \euler +
        \min \left\{ \frac{\lambda LMT D_0^2}{\sigma^2}, \frac{\lambda^3 T^4 D_0^2}{LK^3 \sigma^2} \right\} \right),
        \qquad
        \eta_2 :=
        \frac{L^{\frac{1}{3}} D_0^{\frac{2}{3}} }{\lambda^{\frac{2}{3}} T^{\frac{2}{3}} \sigma^{\frac{2}{3}}},
    \end{equation}
    Then $\eta = \min \left\{ \eta_1, \eta_2\right\}$.
    Since $\varphi_1, \varphi_2, \varphi_3$ are increasing we have
    \begin{align}
        \varphi_1(\eta) \leq \varphi_1 (\eta_1)
        & \leq
        \frac{3 \sigma^2}{\lambda M T} \log \left( \euler +
         \frac{\lambda LMT D_0^2}{\sigma^2} \right),
        \\
        \varphi_2(\eta) \leq \varphi_2 (\eta_1)
        & \leq
        \frac{16200 L^2 K^3 \sigma^2}{\lambda^3 T^4}
        \log^4 \left( \euler +
       \frac{\lambda^3 T^4 D_0^2}{LK^3 \sigma^2} \right),
       \\
       \varphi_3(\eta) \leq \varphi_3 (\eta_2)
       & \leq
       \frac{200 L^{\frac{2}{3}} K D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{\lambda^{\frac{1}{3}} T^{\frac{4}{3}}}.
    \end{align}
    On the other hand, since $\varphi_0$ is decreasing we have $\varphi_0(\eta) \leq \varphi_0(\eta_1) + \varphi_0(\eta_2) + \varphi_0(\frac{1}{L + \lambda})$, where
    \begin{align}
        \varphi_0(\eta_1)
        & \leq
        \frac{\sigma^2}{2 \lambda M T} + \frac{L^2 K^3 \sigma^2}{2 \lambda^3 T^4},
        \\
        \varphi_0(\eta_2)
        & \leq
        \frac{2!}{2} LD_0^2 \left( \sqrt{\frac{\eta_2 \lambda T^2}{9K}}  \right)^{-2}
        =
        \frac{9KL D_0^2}{\eta_2 \lambda T^2}
        =
       \frac{9 L^{\frac{2}{3}} K D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{\lambda^{\frac{1}{3}} T^{\frac{4}{3}}}.
    \end{align}
    Combining the above bounds completes the proof.
\end{proof}
\cref{fedacii:a1:gcvx} then follows by plugging in an appropriate $\lambda$.
\begin{proof}[Proof of \cref{fedacii:a1:gcvx}]
    To simplify the notation, define the terms on the RHS of \cref{eq:fedacii:a1:gcvx:2} as
    \begin{alignat}{2}
        & \psi_0(\lambda):=
        \frac{1}{2}\lambda  D_0^2,
        \quad
        &&
        \psi_1(\lambda):=
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{T^2}{9(1 + L/\lambda)K}} \right),
        \\
        &
        \psi_2(\lambda):=
        \frac{209 L^{\frac{2}{3}} K D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{\lambda^{\frac{1}{3}} T^{\frac{4}{3}}},
        \quad
        && \psi_3(\lambda):=
        \frac{4 \sigma^2}{\lambda M T} \log \left( \euler +
         \frac{\lambda LMT D_0^2}{\sigma^2} \right),
        \\
        &
        \psi_4(\lambda):=
       \frac{16201 L^2 K^3 \sigma^2}{\lambda^3 T^4}
        \log^4 \left( \euler^4 +
       \frac{\lambda^3 T^4 D_0^2}{LK^3 \sigma^2} \right).
    \end{alignat}
    Define
    \begin{align}
        \lambda_1 := \frac{\sigma}{M^{\frac{1}{2}} T^{\frac{1}{2}} D_0},
        \quad
        \lambda_2 := \frac{L^{\frac{1}{2}} K^{\frac{3}{4}} \sigma^{\frac{1}{2}} }{D_0^{\frac{1}{2}} T},
        \quad
        \lambda_3 := \frac{18 LK}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right).
    \end{align}
    Then $\lambda = \max \left\{ \lambda_1, \lambda_2, \lambda_3 \right\}$.
    By helper \cref{helper:inv:times:log} $\psi_3$, $\psi_4$ are decreasing; $\psi_2$ is trivially decreasing, thus
    \begin{align}
        \psi_2(\lambda)
        &
        \leq \psi_2(\lambda_2) = \frac{209 L^{\frac{1}{2}} K^{\frac{3}{4}} D_0^{\frac{3}{2}} \sigma^{\frac{1}{2}}}{T},
        \\
        \psi_3(\lambda)
        &
        \leq \psi_3(\lambda_1)
        =
        \frac{4 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}} \log \left( \euler + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right),
        \\
        \psi_4 (\lambda)
        & \leq
        \psi_4(\lambda_2)
        =
        \frac{16201 L^{\frac{1}{2}} K^{\frac{3}{4}} D_0^{\frac{3}{2}} \sigma^{\frac{1}{2}}}{T}
        \log^4 \left( \euler^4 +
        \frac{L^{\frac{1}{2}} T D_0^{\frac{1}{2}}}{K^{\frac{3}{4}} \sigma^{\frac{1}{2}}} \right).
    \end{align}
    For $\psi_1(\lambda)$ since $T \geq 1000$ we have $\frac{T^2}{K} \geq 1000$, thus
    \begin{equation}
        \frac{\lambda_3}{L} = \frac{18 K}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        \leq
        \frac{18}{1000}\log^2 \left( \euler^2 + 1000 \right) < 1.
    \end{equation}
    Thus $1 + \frac{L}{\lambda_3} \leq \frac{2L}{\lambda_3}$, and therefore
    \begin{equation}
        \psi_1(\lambda) \leq \psi_1(\lambda_3)
        =
        \frac{1}{2} L D_0^2 \left( \euler^2 + \frac{T^2}{K} \right)^{-1} \leq \frac{L K D_0^2}{2T^2}.
    \end{equation}
    Finally
    \begin{align}
        \psi_0(\lambda)  \leq \sum_{i=1}^3 \psi_0(\lambda_i)
        \leq \frac{\sigma D_0}{2 M^{\frac{1}{2}} T^{\frac{1}{2}}}
        +
        \frac{L^{\frac{1}{2}} K^{\frac{3}{4}} D_0^{\frac{3}{2}} \sigma^{\frac{1}{2}}}{2T}
        +
        \frac{9LKD_0^2}{T^2}  \log^2 \left( \euler^2 + \frac{T^2}{K} \right).
    \end{align}
    Consequently,
    \begin{align}
        \sum_{i=0}^4 \psi(\lambda)
        \leq &
        \frac{10LKD_0^2}{T^2}  \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        +
        \frac{5 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}} \log \left( \euler + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right)
        \\
        & \qquad +
        \frac{16411 L^{\frac{1}{2}} K^{\frac{3}{4}} D_0^{\frac{3}{2}} \sigma^{\frac{1}{2}}}{T}
        \log^4 \left( \euler^4 +
        \frac{L^{\frac{1}{2}} T D_0^{\frac{1}{2}}}{K^{\frac{3}{4}} \sigma^{\frac{1}{2}}} \right),
    \end{align}
    completing the proof.
\end{proof}

\subsubsection{Proof of \cref{fedacii:a1:gcvx:1}}
\label{sec:fedacii:a1:gcvx:1}
\cref{fedacii:a1:gcvx:1} is parallel to \cref{fedaci:gcvx:1} where the main difference is the following supporting proposition.
\begin{proposition}
    \label{fedacii:gcvx:0}
    Assume $F$ is general convex and $L$-smooth, and let $\Phi_t$ be the centralized potential \cref{eq:centralied:potential} for $\tilde{F}_{\lambda}$ (with strong convexity estimate $\mu = \lambda$), namely
    \begin{equation}
        \Phi_t := \left( \tilde{F}_{\lambda}(\overline{w_t^{\mathrm{ag}}}) - \tilde{F}_{\lambda}^*  \right)  + \frac{1}{6} \lambda \|\overline{w_T} - w_{\lambda}^*\|^2.
    \end{equation}
    Then
    \begin{equation}
        \Phi_T \geq F(\overline{w_T^{\mathrm{ag}}}) - F^* - \frac{1}{2} \lambda D_0^2
        ,
        \qquad
        \Phi_0 \leq \frac{1}{2} L \|w_0 - w^*\|^2.
    \end{equation}
\end{proposition}
\begin{proof}[Proof of \cref{fedacii:gcvx:0}]
    The proof is almost identical to \cref{fedaci:gcvx:0}.
\end{proof}
\begin{proof}[Proof of \cref{fedacii:a1:gcvx:1}]
    Follows by applying \cref{fedacii:a1:general:eta} and plugging in the bound of \cref{fedacii:gcvx:0}. The rest of proof is the same as \cref{fedaci:gcvx:1} which we omit the details.
\end{proof}

\subsection{Proof of \cref{fedacii:a2:gcvx} on \fedacii for general-convex objectives under \cref{asm2}}
\label{sec:fedacii:a2:gcvx}
We omit some of the proof details since the proof is similar to \cref{fedaci:a1:gcvx}.
We first introduce the supporting lemma for \cref{fedacii:a2:gcvx}.
\begin{lemma}
    \label{fedacii:a2:gcvx:1}
    Assume \cref{asm2} where $F$ is general convex, then for any $\lambda > 0$, for any $\eta \leq \frac{1}{L+\lambda}$, applying \fedacii to $\tilde{F}_{\lambda}$ gives
    \begin{align}
        \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        & \leq
        \frac{1}{2}\lambda  D_0^2
        +
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda T^2}{9K}} \right)
        \\
        &
        +
        \frac{\eta^{\frac{1}{2}} \sigma^2}{\lambda^{\frac{1}{2}} M K^{\frac{1}{2}}}
        +
        \frac{2 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{\lambda^{\frac{1}{2}}M }
        +
        \frac{2 \eta^{\frac{3}{2}} \lambda^{\frac{1}{2}} K^{\frac{1}{2}} \sigma^2}{M}
        +
         \frac{\euler^9 \eta^4 Q^2 K^2 \sigma^4}{\lambda}.
        \label{eq:fedacii:a2:gcvx:1}
    \end{align}
\end{lemma}
\begin{proof}[Proof of \cref{fedacii:a2:gcvx:1}]
    Follows by \cref{fedacii:a2:general:eta,fedacii:gcvx:0}. The proof is similar to \cref{fedaci:gcvx:1} so we omit the details.
\end{proof}
\begin{lemma}
    \label{fedacii:a2:gcvx:2}
    Assume \cref{asm2} where $F$ is general convex, then for any $\lambda > 0$, for
    \begin{equation}
        \eta =
        \min \left\{
        \frac{1}{L+\lambda}
            ,
         \frac{9K}{\lambda T^2}
            \log^2 \left( \euler +
            \min \left\{ \frac{\lambda LMT D_0^2}{\sigma^2},
            \frac{\lambda^2 M T^3 D_0^2}{K^2 \sigma^2},
            \frac{\lambda^5 L T^8 D_0^2}{Q^2 K^6 \sigma^4} \right\} \right)
        ,
        \frac{ L^{\frac{1}{3}} K^{\frac{1}{3}} M^{\frac{1}{3}} D_0^{\frac{2}{3}}}{\lambda^{\frac{2}{3}}T \sigma^{\frac{2}{3}}}
        \right\},
    \end{equation}
    applying \fedacii to $\tilde{F}_{\lambda}$ gives
    \begin{align}
        & \expt \left[F(\overline{w_T^{\mathrm{ag}}}) - F^* \right]
        \leq
        \frac{1}{2}\lambda  D_0^2
        +
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{T^2}{9(1 + L/\lambda)K}} \right)
        +
        \frac{4 \sigma^2}{\lambda M T} \log \left( \euler +
         \frac{\lambda LMT D_0^2}{\sigma^2} \right)
        \\
        &
         +
         \frac{55 L K^2 \sigma^2}{\lambda^2 M T^3}
         \log^3 \left( \euler^3 +
         \frac{\lambda^2 M T^3 D_0^2}{K^2 \sigma^2} \right)
         +
         \frac{83 L^{\frac{1}{2}} KD_0 \sigma}{\lambda^{\frac{1}{2}} M^{\frac{1}{2}} T^{\frac{3}{2}}}
         +
         \frac{\euler^{18} Q^2 K^6 \sigma^4}{\lambda^5 T^8}  \log^8 \left( \euler^8 +  \frac{\lambda^5 L T^8 D_0^2}{Q^2 K^6 \sigma^4} \right).
         \label{eq:fedacii:a2:gcvx:2}
    \end{align}
\end{lemma}
\begin{proof}[Proof of \cref{fedacii:a2:gcvx:2}]
    To simplify the notation, define the terms on the RHS of \cref{eq:fedacii:a2:gcvx:1} as
    \begin{alignat}{3}
        & \varphi_0(\eta) :=
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{\eta \lambda T^2}{9K}} \right),
        \quad
        &&
        \varphi_1(\eta) :=
        \frac{\eta^{\frac{1}{2}} \sigma^2}{\lambda^{\frac{1}{2}} M K^{\frac{1}{2}}},
        \quad
        &&
        \varphi_2(\eta) :=
        \frac{2 \eta^{\frac{3}{2}} L K^{\frac{1}{2}} \sigma^2}{\lambda^{\frac{1}{2}}M },
        \\
        &
        \varphi_3(\eta) :=
        \frac{2 \eta^{\frac{3}{2}} \lambda^{\frac{1}{2}} K^{\frac{1}{2}} \sigma^2}{M},
        \quad
        &&
        \varphi_4(\eta) :=
         \frac{\euler^9 \eta^4 Q^2 K^2 \sigma^4}{\lambda}.
        &&
    \end{alignat}
    Define
    \begin{equation}
        \eta_1 :=  \frac{9K}{\lambda T^2}
        \log^2 \left( \euler +
        \min \left\{ \frac{\lambda LMT D_0^2}{\sigma^2},
        \frac{\lambda^2 M T^3 D_0^2}{K^2 \sigma^2},
        \frac{\lambda^5 L T^8 D_0^2}{Q^2 K^6 \sigma^4} \right\} \right),
        \quad
        \eta_2 :=
        \frac{ L^{\frac{1}{3}} K^{\frac{1}{3}} M^{\frac{1}{3}} D_0^{\frac{2}{3}}}{\lambda^{\frac{2}{3}}T \sigma^{\frac{2}{3}}}.
    \end{equation}
    Then $\eta = \min \left\{ \eta_1, \eta_2\right\}$.
    Since $\varphi_1, \ldots, \varphi_4$ are increasing we have
    \begin{align}
        \varphi_1(\eta) \leq \varphi_1 (\eta_1)
        & \leq
        \frac{3 \sigma^2}{\lambda M T} \log \left( \euler +
         \frac{\lambda LMT D_0^2}{\sigma^2} \right),
        \\
        \varphi_2(\eta) \leq \varphi_2 (\eta_1)
        & \leq
        \frac{54 L K^2 \sigma^2}{\lambda^2 M T^3}
        \log^3 \left( \euler +
        \frac{\lambda^2 M T^3 D_0^2}{K^2 \sigma^2} \right),
       \\
       \varphi_3(\eta) \leq \varphi_3 (\eta_2)
       & =
       \frac{2 L^{\frac{1}{2}} KD_0 \sigma}{\lambda^{\frac{1}{2}} M^{\frac{1}{2}} T^{\frac{3}{2}}},
       \\
       \varphi_4(\eta) \leq \varphi_4 (\eta_1)
       & \leq
       \frac{9^4 \euler^9 Q^2 K^6 \sigma^4}{\lambda^5 T^8}  \log^8 \left( \euler +  \frac{\lambda^5 L T^8 D_0^2}{Q^2 K^6 \sigma^4} \right).
    \end{align}
    On the other hand $\varphi_0(\eta) \leq \varphi_0(\eta_1) + \varphi_0(\eta_2) + \varphi_0(\frac{1}{L + \lambda})$, where
    \begin{align}
        \varphi_0(\eta_1)
        & \leq
        \frac{\sigma^2}{2 \lambda M T} + \frac{L K^2 \sigma^2}{2 \lambda^2 M T^3} + \frac{Q^2 K^6 \sigma^4}{2 \lambda^5 T^8},
        \\
        \varphi_0(\eta_2)
        & \leq
        \frac{3!}{2} LD_0^2 \left( \sqrt{\frac{\eta_2 \lambda T^2}{9K}}  \right)^{-3}
        =
        \frac{81 L K^{\frac{3}{2}} D_0^2}{\eta_2^{\frac{3}{2}} \lambda^{\frac{3}{2}} T^3}
        =
        \frac{81 L^{\frac{1}{2}} KD_0 \sigma}{\lambda^{\frac{1}{2}} M^{\frac{1}{2}} T^{\frac{3}{2}}}.
    \end{align}
    Combining the above bounds completes the proof.
\end{proof}

\cref{fedacii:a2:gcvx} then follows by plugging in an appropriate $\lambda$.
\begin{proof}[Proof of \cref{fedacii:a2:gcvx}]
    To simplify the notation, define the terms on the RHS of \cref{eq:fedacii:a2:gcvx:2} as
    \begin{alignat}{2}
        & \psi_0(\lambda):=
        \frac{1}{2}\lambda  D_0^2
        ,
        &&
        \psi_1(\lambda):=
        \frac{1}{2} LD_0^2 \exp \left(  -  \sqrt{\frac{T^2}{9(1 + L/\lambda)K}} \right),
        \\
        & \psi_2(\lambda):=
        \frac{4 \sigma^2}{\lambda M T} \log \left( \euler +
         \frac{\lambda LMT D_0^2}{\sigma^2} \right),
        &&
        \psi_3(\lambda):=
        \frac{55 L K^2 \sigma^2}{\lambda^2 M T^3}
         \log^3 \left( \euler^3 +
         \frac{\lambda^2 M T^3 D_0^2}{K^2 \sigma^2} \right),
        \\
        & \psi_4(\lambda):= \frac{83 L^{\frac{1}{2}} KD_0 \sigma}{\lambda^{\frac{1}{2}} M^{\frac{1}{2}} T^{\frac{3}{2}}},
        &&
        \psi_5(\lambda):=
        \frac{\euler^{18} Q^2 K^6 \sigma^4}{\lambda^5 T^8}  \log^8 \left( \euler^8 +  \frac{\lambda^5 L T^8 D_0^2}{Q^2 K^6 \sigma^4} \right).
    \end{alignat}
    Define
    \begin{align}
        \lambda_1 := \frac{\sigma}{M^{\frac{1}{2}} T^{\frac{1}{2}} D_0},
        \quad
        \lambda_2 := \frac{L^{\frac{1}{3}} K^{\frac{2}{3}} \sigma^{\frac{2}{3}} }{M^{\frac{1}{3}} T D_0^{\frac{2}{3}} },
        \quad
        \lambda_3 := \frac{Q^{\frac{1}{3}} K \sigma^{\frac{2}{3}}}{D_0^{\frac{1}{3}} T^{\frac{4}{3}}},
        \quad
        \lambda_4 := \frac{18 LK}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right).
    \end{align}
    Then $\lambda = \max \left\{ \lambda_1, \lambda_2, \lambda_3 \right\}$.
    By \cref{helper:inv:times:log}, $\psi_2$, $\psi_3$, $\psi_5$ are increasing. $\psi_4$ is trivially decreasing, thus
    \begin{align}
        \psi_2(\lambda)
        &
        \leq \psi_2(\lambda_1)
        =
        \frac{4 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}} \log \left( \euler + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right),
        \\
        \psi_3 (\lambda)
        & \leq
        \psi_3(\lambda_2)
        =
        \frac{55 L^{\frac{1}{3}} K^{\frac{2}{3}} D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{M^{\frac{1}{3}}T}
        \log^3 \left( \euler^3 +
        \frac{L^{\frac{2}{3}} M^{\frac{1}{3}} T D_0^{\frac{2}{3}}}{  K^{\frac{2}{3}} \sigma^{\frac{2}{3}}} \right),
        \\
        \psi_4(\lambda)
        & \leq
        \psi_4(\lambda_2)
        =
        \frac{83 L^{\frac{1}{3}} K^{\frac{2}{3}} D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{M^{\frac{1}{3}}T},
        \\
        \psi_5(\lambda)
        & \leq
        \psi_5(\lambda_3)
        =
        \frac{\euler^{18} Q^{\frac{1}{3}} K D_0^{\frac{5}{3}} \sigma^{\frac{2}{3}} }{T^{\frac{4}{3}}}
        \log^8 \left( \euler^8 +  \frac{L T^{\frac{4}{3}} D_0^{\frac{1}{3}}}{Q^{\frac{1}{3}} K  \sigma^{\frac{2}{3}} }  \right).
    \end{align}
    For $\psi_1(\lambda)$ since $T \geq 1000$ we have $\frac{T^2}{K} \geq 1000$, thus
    \begin{equation}
        \frac{\lambda_3}{L} = \frac{18 K}{T^2} \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        \leq
        \frac{18}{1000}\log^2 \left( \euler^2 + 1000 \right) < 1.
    \end{equation}
    Thus $1 + \frac{L}{\lambda_3} \leq \frac{2L}{\lambda_3}$, and therefore
    \begin{equation}
        \psi_1(\lambda) \leq \psi_1(\lambda_3)
        =
        \frac{1}{2} L D_0^2 \left( \euler^2 + \frac{T^2}{K} \right)^{-1} \leq \frac{L K D_0^2}{2T^2}.
    \end{equation}
    Finally
    \begin{align}
        \psi_0(\lambda)  \leq \sum_{i=1}^4 \psi_0(\lambda_i)
        \leq \frac{\sigma D_0}{2 M^{\frac{1}{2}} T^{\frac{1}{2}}}
        +
        \frac{L^{\frac{1}{3}} K^{\frac{2}{3}} D_0^{\frac{4}{3}} \sigma^{\frac{2}{3}}}{2 M^{\frac{1}{3}}T}
        +
        \frac{Q^{\frac{1}{3}} K D_0^{\frac{5}{3}} \sigma^{\frac{2}{3}} }{2T^{\frac{4}{3}}}
        +
        \frac{9LKD_0^2}{T^2}  \log^2 \left( \euler^2 + \frac{T^2}{K} \right).
    \end{align}
    Consequently,
    \begin{align}
        & \sum_{i=0}^4 \psi(\lambda)
        \leq
        \frac{10LKD_0^2}{T^2}  \log^2 \left( \euler^2 + \frac{T^2}{K} \right)
        +
        \frac{5 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}} \log \left( \euler + \frac{L M^{\frac{1}{2}} T^{\frac{1}{2}} D_0}{\sigma} \right)
        \\
        & +
        \frac{139 L^{\frac{1}{3}} K^{\frac{2}{3}}  \sigma^{\frac{2}{3}} D_0^{\frac{4}{3}}}{M^{\frac{1}{3}}T}
        \log^3 \left( \euler^3 +
        \frac{L^{\frac{2}{3}} M^{\frac{1}{3}} T D_0^{\frac{2}{3}}}{  K^{\frac{2}{3}} \sigma^{\frac{2}{3}}} \right)
        +
        \frac{\euler^{19} Q^{\frac{1}{3}} K  \sigma^{\frac{2}{3}} D_0^{\frac{5}{3}} }{T^{\frac{4}{3}}}
        \log^8 \left( \euler^8 +  \frac{L T^{\frac{4}{3}} D_0^{\frac{1}{3}}}{Q^{\frac{1}{3}} K  \sigma^{\frac{2}{3}} }  \right).
    \end{align}
\end{proof}

\subsection{Proof of \cref{fedavg:a2:gcvx} on \fedavg for general-convex objectives under \cref{asm2}}
\label{sec:fedavg:a2:gcvx}
We omit some of the proof details since the proof is similar to \cref{fedaci:a1:gcvx}.
We first introduce the supporting lemma for \cref{fedavg:a2:gcvx}.
\begin{lemma}
    \label{fedavg:a2:gcvx:1}
    Assume \cref{asm2} where $F$ is general convex, then for any $\lambda > 0$,
    for
    \begin{equation}
        \eta := \min \left\{ \frac{1}{4(L+\lambda)}, \frac{2}{\lambda T} \log \left( \euler + \min \left\{ \frac{\lambda^2 M T^2 D_0^2}{\sigma^2}, \frac{\lambda^6 T^5 D_0^2}{Q^2 K^2 \sigma^4}\right\} \right)\right\},
    \end{equation}
    applying \fedavg to $\tilde{F}_{\lambda}$ gives
    \begin{align}
        & \expt \left[ F \left( \sum_{t=0}^{T-1} \frac{\rho_t}{S_T} \overline{w_t} \right)   - F^* \right]
        \leq
        3 \lambda  D_0^2
        +
        2 L D_0^2 \exp \left(  -  \frac{\lambda T}{8(L + \lambda)} \right)
        \\
        & \qquad
        +
        \frac{3 \sigma^2}{ \lambda MT } \log \left( \euler^2 + \frac{\lambda^2 M T^2 D_0^2}{\sigma^2}  \right)
        +
        \frac{3073 Q^2 K^2 \sigma^4}{\lambda^5 T^4} \log^4 \left( \euler^5 + \frac{\lambda^6 T^5 D_0^2}{Q^2 K^2 \sigma^4}  \right),
        \label{eq:fedavg:a2:gcvx:1}
    \end{align}
    where $\rho_t := (1 - \frac{1}{2} \eta \lambda)^{T-t-1}$, $S_T := \sum_{t=0}^{T-1}\rho_t$, and $D_0 = \|\overline{w_0}-w^*\|$.
\end{lemma}
\begin{proof}[Proof of \cref{fedavg:a2:gcvx:1}]
    Apply \cref{fedavg:a2:full}. The rest of analysis is similar to \cref{fedaci:gcvx:1,fedaci:gcvx:2}.
\end{proof}
\begin{proof}[Proof of  \cref{fedavg:a2:gcvx}]
    To simplify the notation, define the RHS of \cref{eq:fedavg:a2:gcvx:1} as
    \begin{alignat}{2}
        & \psi_0(\lambda) := 3 \lambda  D_0^2
        ,
        && \psi_1(\lambda) :=  2 L D_0^2 \exp \left(  -  \frac{T}{8(1 +(L/\lambda))} \right),
        \\
        & \psi_2(\lambda) :=  \frac{3 \sigma^2}{ \lambda MT } \log \left( \euler^2 + \frac{\lambda^2 M T^2 D_0^2}{\sigma^2}  \right)
        ,
        && \psi_3(\lambda) := \frac{3073 Q^2 K^2 \sigma^4}{\lambda^5 T^4} \log^4 \left( \euler^5 + \frac{\lambda^6 T^5 D_0^2}{Q^2 K^2 \sigma^4}  \right).
    \end{alignat}
    Define
    \begin{equation}
        \lambda_1 := \frac{\sigma}{M^{\frac{1}{2}} T^{\frac{1}{2}} D_0},
        \quad
        \lambda_2 := \frac{Q^{\frac{1}{3}} K^{\frac{1}{3}} \sigma^{\frac{2}{3}}}{ T^{\frac{2}{3}} D_0^{\frac{1}{3}}},
        \quad
        \lambda_3 := \frac{16L }{T} \log (\euler + T).
    \end{equation}
    Then $\lambda = \max \left\{ \lambda_1, \lambda_2, \lambda_3 \right\}$. We have (by helper \cref{helper:inv:times:log} $\psi_2, \psi_3$ are decreasing)
    \begin{align}
        \psi_2(\lambda) & \leq \psi_2 (\lambda_1)
        \leq
        \frac{3 \sigma D_0}{ M^{\frac{1}{2}} T^{\frac{1}{2}}}
        \log
        \left( \euler^2 +  T \right),
        \\
        \psi_3(\lambda) & \leq \psi_3 (\lambda_2)
        \leq
        \frac{3073 Q^{\frac{1}{3}}  K^{\frac{1}{3}}  \sigma^{\frac{2}{3}} D_0^{\frac{5}{3}}} { T^{\frac{2}{3}}}
        \log^4 \left( \euler^5 + T \right).
    \end{align}
    Since $T \geq 100$ we have (by helper \cref{helper:inv:times:log}, $x^{-1} \log (\euler + x)$ is decreasing)
    \begin{equation}
        \frac{\lambda_3}{L}
        =
        \frac{16}{T} \log (\euler + T)
        \leq \frac{16}{100} \log(\euler + 100) < 1,
    \end{equation}
    and thus
    \begin{equation}
        \psi_1(\lambda) \leq \psi_1(\lambda_3)
        \leq
        2LD_0^2 \exp \left( - \frac{T}{16 (L /\lambda_3)} \right)
        =
        2LD_0^2 (\euler +  T)^{-1}
        \leq
        \frac{2L D_0^2}{T}.
    \end{equation}
    Finally
    \begin{equation}
        \psi_0(\lambda)
        \leq
        \sum_{i=1}^3 \psi_0(\lambda_i)
        =
        \frac{3 \sigma D_0}{M^{\frac{1}{2}} T^{\frac{1}{2}}}
        +
        \frac{3 Q^{\frac{1}{3}}  K^{\frac{1}{3}}  \sigma^{\frac{2}{3}} D_0^{\frac{5}{3}}} { T^{\frac{2}{3}}}
        +
        \frac{48 L D_0^2}{T} \log (\euler + T).
    \end{equation}
    Accordingly
    \begin{align}
        \sum_{i=0}^{3} \psi_i(\lambda)
        \leq
        \frac{50 L D_0^2}{T} \log (\euler + T)
        +
        \frac{6 \sigma D_0}{ M^{\frac{1}{2}} T^{\frac{1}{2}}}
        \log
        \left( \euler^2 +  T \right)
        +
        \frac{3076 Q^{\frac{1}{3}}  K^{\frac{1}{3}}  \sigma^{\frac{2}{3}} D_0^{\frac{5}{3}}} { T^{\frac{2}{3}}}
        \log^4 \left( \euler^5 + T \right).
    \end{align}
\end{proof}

config: arxiv


TITLE: Reference for an unbiased definition of a symmetric monoidal category
QUESTION [16 upvotes]: In the references I know, a symmetric monoidal category is defined as a monoidal category equipped with some additional data, so in particular the monoidal product is a functor
$$
\mathcal{C}\times \mathcal{C}\to \mathcal{C}.
$$
The word unbiased is sometimes used to mean that there are products
$$
\mathcal{C}^n\to \mathcal{C}
$$
but that is not quite what I mean here. Rather, I want a monoidal category to give me an assignment for every finite set $S$
$$
\mathcal{C}^S\to \mathcal{C}
$$
and for everything to be described in terms of functors involving the category of (unordered) finite sets, maybe some weak kind of functor since associativity isn't strict.

Does this definition exist? That is, is there some obstruction that is not obvious to me that prevents it from working?
Is it written down clearly and cleanly somewhere? This seems like a natural alternative to the standard definition that could sometimes be useful to eliminate certain bookkeeping.
Why isn't this viewpoint more common? Or is it common and I've just been reading the wrong books?

REPLY [11 votes]: This isn't quite an answer to your question either, but Appendix A of my 2003 book Higher Operads, Higher Categories contains something close.
First it defines commutative monoids in the style you describe: as a set $A$ together with a function $A^S \to A$ for each finite set $S$, satisfying some axioms.
Then it defines symmetric multicategories in the same style: as a set $A_0$ (to be thought of as the set of objects) together with, for each set-indexed family of objects $(a_s)_{s \in S}$ and each object $b$, a set $Hom(a_\cdot; b)$, together with suitable composition and identities.
Although symmetric monoidal categories aren't treated there, playing the same game a third time shouldn't be hard.  (Alternatively, you could describe symmetric monoidal categories as symmetric multicategories with certain special properties.)
I first learned of this style of definition from Beilinson and Drinfeld's Chiral Algebras (then a set of notes, now a book, I think).


TITLE: Folland Proposition 1.4 Generating product sigma algebra from generators of measures
QUESTION [1 upvotes]: In the following proposition from Folland Real Analysis, why is $\left\{E \subset X_{\alpha}: \pi_{\alpha}^{-1}(E) \in \mathcal{M}\left(\mathcal{F}_{1}\right)\right\}$ seen to be a $\sigma$-algebra? The author leaves this unjustified and I don't see it myself after some thought.
1.4 Proposition. Suppose that $M_{\alpha}$ is generated by $\varepsilon_{\alpha,} \alpha \in A$. Then $\otimes_{\alpha \in A}$ $\mathcal{M}_\alpha$ is generated by $\mathcal{F}_{1}=\left\{\pi_{\alpha}^{-1}\left(E_{\alpha}\right): E_{\alpha} \in \mathcal{E}_{\alpha}, \alpha \in A\right\}$.
Proof. Obviously $\mathcal{M}\left(\mathcal{F}_{1}\right) \subset \bigotimes_{\alpha \in A} \mathcal{M}_{\alpha}$. On the other hand, for each $\alpha$, the collection $\left\{E \subset X_{\alpha}: \pi_{\alpha}^{-1}(E) \in \mathcal{M}\left(\mathcal{F}_{1}\right)\right\}$ is easily seen to be a $\sigma$ -algebra on $X_{\alpha}$ that contains $\varepsilon_\alpha$ and hence $\mathcal{M}_\alpha$. In other words, $\pi_\alpha^{-1}(E)\in \mathcal{M}(\mathcal{F}_1)$ for all $E\in \mathcal{M}_\alpha$
$\alpha \in A$, and hence $ \bigotimes_{\alpha \in A}\mathcal{M}_\alpha  \subset \mathcal{M}\left(\mathcal{F}_{1}\right)$

REPLY [2 votes]: If $S=\left\{E \subset X_{\alpha}: \pi_{\alpha}^{-1}(E) \in \mathcal{M}\left(\mathcal{F}_{1}\right)\right\}$ then we need $S$ to be closed under compliments and countable unions. If $E \in S$ then $\pi_{\alpha}^{-1}(E) \in \mathcal{M}\left(\mathcal{F}_{1}\right)$. But $\mathcal{M}\left(\mathcal{F}_{1}\right)$ is a $\sigma$-algebra so $\pi_{\alpha}^{-1}(E)^c = \pi_{\alpha}^{-1}(E^c)  \in \mathcal{M}\left(\mathcal{F}_{1}\right)$. This shows that $E^c \in S$. You can make a similar argument to show closure under countable unions.