papers/hanzo-federated-agents/sections/13-proof-of-coordinate-wise-median-robustne.tex

\section{Proof of Coordinate-Wise Median Robustness}

\label{app:cwmed-proof}

\begin{theorem}[Robustness of Coordinate-Wise Median]
\label{thm:cwmed-robust-full}
Let $\mathcal{X} = \{x_1, \ldots, x_N\} \subset \mathbb{R}^d$ with $f < N/2$
adversarial values and $h = N - f$ honest values drawn from distribution
$\mathcal{D}$ with mean $\mu$ and coordinate-wise standard deviation $\sigma_j$.
The coordinate-wise median $\hat{\mu}_j = \med(\{x_{i,j}\}_{i=1}^N)$ satisfies:
\begin{equation}
    |\hat{\mu}_j - \mu_j| \leq O\!\left(\frac{f}{h} \cdot \sigma_j\right)
    + O\!\left(\frac{\sigma_j}{\sqrt{h}}\right)
    \qquad \forall j \in [d],
\end{equation}
with probability $\geq 1 - 2\exp(-h/8)$.
\end{theorem}

\begin{proof}
Fix coordinate $j$. Let $F_h$ be the empirical CDF of the $h$ honest values
$\{x_{i,j}\}_{i \in H}$. The true median $m_j = F_h^{-1}(1/2)$ satisfies
$|m_j - \mu_j| = O(\sigma_j / \sqrt{h})$ by the CLT for order statistics.

The adversary can shift the sample median by at most $f$ positions in the
sorted order. The median of $N = h + f$ values corresponds to the
$(N/2)$-th order statistic. With $f$ adversarial values placed optimally,
the sample median corresponds to at most the $(h/2 + f)$-th honest order
statistic, i.e., the $((h/2 + f)/h)$-th quantile of the honest distribution.
Since $f < h/2$ (implied by $f < N/3$), this is the $(1/2 + f/h)$-th quantile.
By the quantile deviation bound:
$|F_h^{-1}(1/2 + f/h) - F_h^{-1}(1/2)| \leq (f/h) \cdot \sigma_j / p_j$,
where $p_j$ is the density of the honest distribution at $m_j$. Under
sub-Gaussianity, $p_j = O(1/\sigma_j)$, giving $O(f \sigma_j / h)$.
Combining with the honest-median deviation completes the proof.
\end{proof}