\section{Appendix B: Analysis of Section~\ref{sec:byz}}
In this section we provide the theoretical analysis of the Byzantine robust 
method explained in Section~\ref{sec:byz} and prove the statistical  guarantee. In any iteration  $t$  the following holds
\begin{align*}
    |\cU_t| &  = |(\cU_t\cap\cM_t)|  + |(\cU_t\cap\cB_t)|  \\   
    |\cM_t| & = |(\cU_t\cap\cM_t)| + |(\cM_t\cap\cT_t)|.
\end{align*}
Combining both we have 
\begin{align*}
    |\cU_t| = |\cM_t| - |(\cM_t\cap\cT_t)|+|(\cU_t\cap\cB_t)|.
\end{align*}

\begin{lemma}\label{lem:byzone}
Let $\{\bS_i\}_{i=1}^m \in \mathbb{R}^{n \times s}$  be sketching matrices based on  Lemma~\ref{lem:Hessketch}. Let $\phi_t$ be defined in \eqref{quad} and $\hat{\p}_t$ be defined in  Algorithm~\ref{alg:main_algo}. It holds that 
\begin{align*}
\min_{\p}\phi_t(\p) \leq \phi_t(\hat{\p}_t)& \leq \epsilon_{byz}^2 + (1 - \zeta^2_{byz})\phi(\p^*),
\end{align*}
where $\epsilon_{byz} $ and $\zeta_{byz}$ is defined in ~\eqref{gbyz} and ~\eqref{alpbyz} respectively.

\end{lemma}
\begin{proof}
In the following analysis we omit the subscript '$t$'. From the definition of the quadratic function \eqref{quad} we know that    
\begin{align*}
    \phi(\hat{\p}) - \phi(\p^*) & = \frac{1}{2}\|\bH^{\frac12}(\hat{\p}-\p^*)\|^2.
\end{align*}
Now we consider 
\begin{align*}
  \frac{1}{2} \|\bH^{\frac12}(\hat{\p}-\p^*)\|^2 & = \frac{1}{2}\|\bH^{\frac12}(\frac{1}{|\cU|}\sum_{i \in \cU}\hat{\p}_i-\p^*)\|^2  \\
   &=\frac{1}{2}\|\bH^{\frac12}\frac{1}{|\cU|}(\sum_{i \in \cM}(\hat{\p}_i-\p^*) -\sum_{i \in (\cM\cap\cT)}(\hat{\p}_i-\p^*)+\sum_{i \in (\cU\cap\cB)}(\hat{\p}_i-\p^*) )\|^2 \\
   &\leq \underbrace{ \|\bH^{\frac12}\frac{1}{|\cU|}(\sum_{i \in \cM}(\hat{\p}_i-\p^*)\|^2}_{Term 1} + \underbrace{ 2\|\bH^{\frac12}\frac{1}{|\cU|}\sum_{i \in (\cM\cap\cT)}(\hat{\p}_i-\p^*)\|^2 }_{Term 2}+ \underbrace{2\|\bH^{\frac12}\frac{1}{|\cU|}\sum_{i \in (\cU\cap\cB)}(\hat{\p}_i-\p^*) )\|^2}_{Term 3}.
 
\end{align*}
Now we bound each term separately and use the result of the Lemma~\ref{lem:onernd} to bound each term.
\begin{align*}
    Term 1 &=  \|\bH^{\frac12}\frac{1}{|\cU|}(\sum_{i \in \cM}(\hat{\p}_i-\p^*)\|^2 \\& = (\frac{1-\alpha}{1-\beta})^2 \|\bH^{\frac12}\frac{1}{|\cM|}(\sum_{i \in \cM}(\hat{\p}_i-\p^*)\|^2 \\
   & \leq (\frac{1-\alpha}{1-\beta})^2 [\epsilon^2+ \zeta^2_{\cM}\|\bH^{\frac{1}{2}}\p^*\|^2],
    
\end{align*}
where $\zeta_{\cM}= \nu(\frac{\eta}{\sqrt{|\cM|}}+ \frac{\eta^2}{1-\eta})=\nu(\frac{\eta}{\sqrt{(1-\alpha)m}}+ \frac{\eta^2}{1-\eta})$.


Similarly  the Term 2 can be bonded as it is a bound on good machines
\begin{align*}
    Term 2 & = 2\|\bH^{\frac12}\frac{1}{|\cU|}\sum_{i \in (\cM\cap\cT)}(\hat{\p}_i-\p^*)\|^2 \\
    & = 2 (\frac{1-\alpha}{1-\beta})^2 \|\bH^{\frac12}\frac{1}{|\cM\cap\cT|}\sum_{i \in (\cM\cap\cT)}(\hat{\p}_i-\p^*)\|^2\\
    & \leq 2(\frac{1-\alpha}{1-\beta})^2 [\epsilon^2 + \zeta^2_{\cM\cap\cT}\|\bH^{\frac{1}{2}}\p^*\|^2],
    
\end{align*}
where  $\zeta_{\cM\cap\cT}= \nu(\frac{\eta}{\sqrt{|\cM\cap\cT|}}+ \frac{\eta^2}{1-\eta}) \leq  \nu(\frac{\eta}{\sqrt{(1-\beta)m}}+ \frac{\eta^2}{1-\eta})$.


For the Term 3 we know that $\beta > \alpha $ so all the untrimmed worker norm is bounded by a good machine as at least one good machine gets trimmed.
\begin{align*}
    Term 3 & = 2\|\bH^{\frac12}\frac{1}{|\cU|}\sum_{i \in (\cU\cap\cB)}(\hat{\p}_i-\p^*) )\|^2 \\
    & \leq 2\sigma_{max}(\bH)(\frac{|\cU\cap\cB|}{|\cU|})^2 \|\frac{1}{|\cU\cap\cB|}\sum_{i \in (\cU\cap\cB)}(\hat{\p}_i-\p^*) )\|^2 \\
    & \leq 2\sigma_{max}(\bH)(\frac{|\cU\cap\cB|}{|\cU|})^2 \frac{1}{|\cU\cap\cB|}\sum_{i \in (\cU\cap\cB)}\|(\hat{\p}_i-\p^*) )\|^2\\
   & \leq 4\sigma_{max}(\bH)(\frac{|\cU\cap\cB|}{|\cU|})^2 \frac{1}{|\cU\cap\cB|}\sum_{i \in (\cU\cap\cB)}(\|\hat{\p}_i\|^2+ \|\p^*\|^2) \\
   & \leq 4\sigma_{max}(\bH)(\frac{|\cU\cap\cB|}{|\cU|})^2 \max_{i \in \cM}(\|\hat{\p}_i\|^2+ \|\p^*\|^2)\\
   & \leq 4\sigma_{max}(\bH)(\frac{|\cU\cap\cB|}{|\cU|})^2 \max_{i \in \cM}(\|\hat{\p}_i- \p^*\|^2+ 2\|\p^*\|^2)\\
   & \leq 4\kappa (\frac{|\cU\cap\cB|}{|\cU|})^2 \max_{i \in \cM}(\|\bH^{\frac{1}{2}}(\hat{\p}_i- \p^*)\|^2+ 2\|\bH^{\frac{1}{2}}\p^*\|^2)\\
   &\leq   4\kappa (\frac{|\cU\cap\cB|}{|\cU|})^2(\epsilon^2 + (2+\zeta^2_{1})\|\bH^{\frac{1}{2}}\p^*\|^2)\\
   & \leq 4\kappa (\frac{\alpha}{1-\beta})^2(\epsilon^2 + (2+\zeta^2_{1})\|\bH^{\frac{1}{2}}\p^*\|^2),
   
\end{align*}
where  $\zeta_{1}= \nu(\eta+ \frac{\eta^2}{1-\eta}) = \frac{\nu}{1-\eta}$ and $\kappa= \frac{\sigma_{max}(\bH)}{\sigma_{min}(\bH)}$.


Combining all the bounds on Term1 , Term2 and Term3 we have 
\begin{align*}
  \frac{1}{2} \|\bH^{\frac12}(\hat{\p}-\p^*)\|^2 & \leq    \epsilon_{byz}^2+ \zeta^2_{byz}\|\bH^{\frac{1}{2}}\p^*\|^2,
\end{align*}
where 
\begin{align*}
    \epsilon_{byz}^2 &= \left(3 \left(\frac{1-\alpha}{1-\beta}\right)^2 +4\kappa \left(\frac{\alpha}{1-\beta}\right)^2 \right)\epsilon^2, \\
   
    \zeta^2_{byz} & =2 \left(\frac{1-\alpha}{1-\beta} \right)^2\zeta^2_{\cM\cap\cT} + \left(\frac{1-\alpha}{1-\beta} \right)^2\zeta^2_{\cM} + 4\kappa \left(\frac{\alpha}{1-\beta}\right)^2(2+\zeta^2_1).
\end{align*}
Finally we have 
\begin{align*}
 \phi(\hat{\p}) - \phi(\p^*) &  \leq  \epsilon_{byz}^2- \zeta^2_{byz}\phi(\p^*) \\
 \Rightarrow \phi(\hat{\p}) & \leq \epsilon_{byz}^2 + (1 - \zeta^2_{byz})\phi(\p^*).
\end{align*}

\end{proof}

\begin{lemma}\label{lem:byzdelta}
Let $\zeta_{byz} \in (0,1),\epsilon_{byz}$ be any fixed parameter. And $\hat{p}_t$ satisfies $\phi_t(\hat{\p}_t) \leq \epsilon_{byz}^2+ (1 -\zeta_{byz}^2) \min_{\p}\phi_t(\p)$. Under the Assumption~\ref{asm:hess}(Hessian $L$-Lipschitz) and 
$\mathbf{\Delta}_t =\w_t-\w^*$ satisfies
\begin{align*}
\mathbf{\Delta}^T_{t+1}\bH_t\mathbf{\Delta}_{t+1}& \leq L\| \mathbf{\Delta}_{t+1}\|\|\mathbf{\Delta}_t\|^2 +  \frac{\zeta^2_{byz}}{1-\zeta^2_{byz}}\mathbf{\Delta}_t^T\bH_t\mathbf{\Delta}_t + 2\epsilon_{byz}^2.
\end{align*}
\end{lemma}

\begin{proof}
 We choose $\zeta= \zeta_{byz}$ and $\epsilon=\epsilon_{byz}$ from the Lemma~\ref{lem:byzone} and follow  the proof of Lemma~\ref{lem:delta} to obtain the desired bound.
\end{proof}

\textbf{Proof of Theorem~\ref{thm:byzsmooth} }
\begin{proof}
 We get the desired bound by developing from the result of the Lemma~\ref{lem:byzdelta} and following the proof of Theorem~\ref{thm:smooth}
\end{proof}
{"config": "arxiv", "file": "2006.08737/appendix1.tex"}