---
# System prepended metadata

title: Explicit bias decomposition

---

# Explicit bias decomposition


Denote $g$ as the full-batch gradient (i.e $g=\frac{1}{n}\sum_i^n  g_i$)

$clip(g_i) = \frac{g_i}{max(1, \frac{C}{||g_i||_2})}$



We essentially can follow section 3.1 of http://proceedings.mlr.press/v130/qian21a/qian21a.pdf, (translated into our notation) "each g_i can be decomposed as

$$g_i = \beta_i \cdot g + t_i$$

where
$$\beta_i = \frac{\langle g_i, g\rangle}{\lVert g\rVert^2} = \frac{\lVert g_i\rVert}{\lVert g\rVert}cos\theta_i$$

with $\theta_i$ being the angle between $g_i$ and $g$, and $t_i \in g^\perp = \{z \mid \langle z, g\rangle = 0\}$."

Then composing this decomp with the $clip$ function gives us
$$clip(g_i) = \frac{g_i}{max(1, \frac{C}{||g_i||_2})} = \frac{\beta_ig + t_i}{max(1, \frac{C}{||g_i||_2})}$$

Let $M_i = max(1, \frac{C}{||g_i||_2})$. Then we rewrite the above as
$$clip(g_i) = \frac{\beta_i}{M_i} g + \frac{t_i}{M_i}$$

Averaging the clipped gradients across the dataset:

$$\frac{1}{n}\sum_{i=1}^nclip(g_i) =\frac{1}{n}\sum_{i=1}^n(\frac{\beta_i}{M_i} g + \frac{t_i}{M_i})$$

$$ = (\frac{1}{n}\sum_{i=1}^n\frac{\beta_i}{M_i})\; \cdot \; g + (\frac{1}{n}\sum_{i=1}^n\frac{t_i}{M_i}) $$


Finally, adding a vector $\eta_i \sim \mathcal{N}(0, C\sigma^2I)$ for each sample gives

$$\hat{g}_{priv} = \frac{1}{n}\sum_{i=1}^nclip(g_i) + \eta_i = (\underbrace{\frac{1}{n}\sum_{i=1}^n\frac{\beta_i}{M_i})}_{a}\; \cdot \; g \; + \; \underbrace{(\frac{1}{n}\sum_{i=1}^n\frac{t_i}{M_i} + \eta_i}_{c})$$

where $a$ and $c$ are ***magnitude*** and ***direction*** error respectively






