Exercises

Per-worker storage: $s + 1 = 6$ partitions. Recovery threshold: $K = N - s = 45$. Straggler tolerance: $s = 5$ (master ignores slowest 5 of 50 workers).

$\mathbf{G} = \mathbf{G}_{\text{stack}} \mathbf{1}_N$ where $\mathbf{G}_{\text{stack}} = [\mathbf{g}_1, \mathbf{g}_2, \ldots, \mathbf{g}_N] \in \mathbb{R}^{d \times N}$ is the matrix of stacked gradients and $\mathbf{1}_N$ is the all-ones query vector.

Coded gradient computation is the $q = 1$ specialization of polynomial codes (Chapter 5).

$H_{200} \approx 5.878$; $H_{40} \approx 4.279$; $H_{200} - H_{40} \approx 1.599$.

$5.878 / 1.599 \approx 3.68\times$.

Exact gradient coding (Tandon et al.) recovers $\mathbf{G} = \sum_k \mathbf{g}_k$ exactly from any $K = N - s$ responses, at per-worker storage $s + 1$.

Approximate gradient coding (Charles et al.) recovers an estimate $\widehat{\mathbf{G}}$ with $\mathbb{E}\| \widehat{\mathbf{G}} - \mathbf{G}\|^2 \leq \epsilon \|\mathbf{G}\|^2$, at per-worker storage $\Theta(\log N / \epsilon)$ — sub-linear in $N$.

$\mathcal{S}_1 = \{1, 2, 3\}$, $\mathcal{S}_2 = \{2, 3, 4\}$, $\mathcal{S}_3 = \{3, 4, 5\}$, $\mathcal{S}_4 = \{4, 5, 6\}$, $\mathcal{S}_5 = \{5, 6, 1\}$, $\mathcal{S}_6 = \{6, 1, 2\}$. Each worker stores $s + 1 = 3$ consecutive partitions.

$\mathbf{B} = \begin{pmatrix} 1 & -1 & 1 & 0 & 0 & 0 \\ 0 & 1 & -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 & 1 & 0 \\ 0 & 0 & 0 & 1 & -1 & 1 \\ 1 & 0 & 0 & 0 & 1 & -1 \\ -1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix}$ Each row $\mathbf{B}_{k, :}$ has support exactly on $\mathcal{S}_k$.

$K = N - s = 4$. Master can tolerate any $2$ stragglers out of $6$ workers.

Storage assignment: $\mathcal{S}_k = \{k\}$ — each worker stores its own partition only. Encoding matrix: $\mathbf{B} = \mathbf{I}_N$ (the identity).

Recovery threshold: $K = N - s = N$. Master needs all $N$ responses (one per partial gradient). This is exactly uncoded SGD: every worker's response is needed for the full sum. Straggler tolerance: $0$.

$s = 0$ recovers uncoded as a degenerate case of gradient coding. The framework is strictly more general — increasing $s$ trades storage for straggler tolerance.

$\rho = c / [(N - s) \epsilon] = c / (70 \cdot 0.05) = c / 3.5$ for some constant $c$. Taking $c = 8$ for safety: $\rho \approx 2.3$ — but this should be normalized so that $\rho N$ is the per-worker storage. Re-do: per-worker storage $\rho N \approx 2.3 \cdot 100 / 100 \approx$... let's be careful. From the theorem, per-worker storage scales as $1/[(1 - s/N) \epsilon] = 1/(0.7 \cdot 0.05) \approx 28.6$ partitions per worker.

Exact gradient coding for $s = 30$ requires $s + 1 = 31$ partitions per worker. Approximate at $\epsilon = 0.05$ requires $\sim 29$ — comparable at this $\epsilon$ but with a smooth tradeoff: tighter $\epsilon$ requires more storage, looser $\epsilon$ much less.

At loose error tolerances ($\epsilon \geq 0.1$), approximate coding beats exact by a factor of $5-10\times$ in storage. For tight tolerances ($\epsilon \leq 0.01$), the gap narrows.

$\mathbf{w}_{t+1} = \mathbf{w}_t - \eta \widehat{\mathbf{G}}_t$ with $\widehat{\mathbf{G}}_t = \mathbf{G}_t + \boldsymbol{\eta}_t$, $\mathbb{E}\|\boldsymbol{\eta}_t\|^2 \leq \epsilon \|\mathbf{G}_t\|^2$.

Standard analysis (Bubeck 2015 §6.2) gives $\mathbb{E}[F(\mathbf{w}_T) - F^*] \leq (1 - \mu/L)^T \cdot (F(\mathbf{w}_0) - F^*) + \frac{\epsilon \sigma^2} {\mu}$, where the additional term arises from the approximation noise.

As $T \to \infty$, the first term vanishes and the floor $\epsilon \sigma^2 / \mu$ remains. For $\epsilon = 10^{-3}$, $\sigma^2 = 1$, $\mu = 0.1$, the floor is $\sim 10^{-2}$ — small, often acceptable in practice.

The master decodes the exact sum $\mathbf{G} = \sum_k \mathbf{g}_k$ from the coded responses. This is a deterministic function of the responses; no random masking is involved. The master could in principle invert the system to learn individual gradients (especially if it has fewer than $N$ unknowns relative to known structure).

Each user computes their coded gradient $\tilde{\mathbf{g}}_k$ (Section 6.2), then adds pairwise random masks $\mathbf{r}_{k,j}$ before sending. The masks cancel in the aggregate, so the master sees $\tilde{\mathbf{g}}_k + \sum_{j} \mathbf{r}_{k,j}$ but not individual $\tilde{\mathbf{g}}_k$ — let alone the underlying $\mathbf{g}_k$. The composition is well-defined because both operations are linear.

Composition is additive: per-user storage grows by $O(\log n)$ for mask seeds; per-round communication grows by $O(n^2)$ for the pairwise mask exchange. Recovery threshold is unchanged ($K = N - s$).

Sparsification: each user's individual gradient $\mathbf{g}_k$ is approximated by zeroing out small-magnitude entries. Approximate coding: the aggregate $\mathbf{G}$ is approximated; individual gradients are still computed exactly.

Sparsification: per-user, before aggregation. Approximate coding: at the master, after all responses arrive.

Sparsification: when uplink bandwidth is the bottleneck (mobile FL, narrowband wireless). Approximate coding: when straggler tolerance and per-worker storage are the bottlenecks (datacenter clusters with heterogeneous compute).

The two are orthogonal and can be combined: each user sparsifies and the aggregation is done with approximate coding. Production systems sometimes layer both for compounded savings.

The cyclic structure of $\mathbf{B}$ ensures that any $N - s$ row submatrix has rank $N - s$ (this is a standard property of the equiangular cyclic encoding; see Tandon et al. Lemma 1).

The all-ones vector $\mathbf{1}_N^T$ lies in the row span of $\mathbf{B}$ by construction (column sums of $\mathbf{B}$ equal $1$ at each coordinate). Restricting to the responder rows preserves this: the cyclic encoding is designed so that any $N - s$ rows can reconstruct the all-ones row via a unique linear combination.

Since $\mathbf{B}_{\mathcal{T}, :}$ has full row rank and $\mathbf{1}_N^T$ lies in its row span, the linear system $\mathbf{D} \mathbf{B}_{\mathcal{T}, :} = \mathbf{1}_N^T$ has a unique solution $\mathbf{D} = \mathbf{1}_N^T \mathbf{B}_{\mathcal{T}, :}^\dagger$. The decoder applies this $\mathbf{D}$ to the responses $\tilde{\mathbf{g}}_{\mathcal{T}}$ and recovers $\sum_k \mathbf{g}_k$ exactly. $\blacksquare$

$\widehat{\mathbf{G}} = \widehat{\mathbf{D}} \mathbf{B}_{\mathcal{T}, :} \mathbf{g}$ with $\widehat{\mathbf{D}} = \mathbf{1}_N^T \mathbf{B}_{\mathcal{T}, :}^\dagger$ (least-squares). Error: $\|(\widehat{\mathbf{D}} \mathbf{B}_{\mathcal{T}, :} - \mathbf{1}_N^T) \mathbf{g}\|^2$.

The smallest singular value of an $(N-s) \times N$ random matrix with density $\rho$ is, with high probability, $\sigma_{\min}(\mathbf{B}_{\mathcal{T}, :}) \geq c\sqrt{(N-s)\rho}$ (Bai-Yin / Marchenko-Pastur). This bounds the conditioning of the pseudo-inverse.

$\|\widehat{\mathbf{D}} \mathbf{B}_{\mathcal{T}, :} - \mathbf{1}_N^T\| \leq \sigma_{\min}^{-1} \cdot O(1) \leq O(1/\sqrt{(N-s)\rho})$. Squared: $O(1/[(N-s)\rho])$. Multiplying by $\|\mathbf{g}\|^2$ gives the error bound.

Density $\rho$ acts as a "regularizer" for the decoder: more density = better conditioning = smaller error. The role of random-matrix concentration is to control $\sigma_{\min}$, which determines decoder accuracy.

Assign worker $k$ to store $b_k$ partitions. The encoding matrix has row-$k$ support of size $b_k$ (potentially varying across rows). The decoder finds $\mathbf{D}$ such that $\mathbf{D} \mathbf{B}_{\mathcal{T}, :} = \mathbf{1}_N^T$ for any responder set $\mathcal{T}$.

For symmetric $b_k = b$, the recovery threshold is $K = N - (b - 1)$. Heterogeneous case: the threshold becomes $K^* = \min_{\mathcal{T}} |\mathcal{T}|$ such that $\sum_{k \in \mathcal{T}} b_k \geq N$. This is a covering problem on the worker-partition graph.

Heterogeneous storage leads to a non-uniform partition assignment: some partitions are stored by many workers, others by few. The worst-case responder subset depends on which partitions the stragglers covered. Optimal scheme construction is a combinatorial-optimization problem with no general closed-form solution.

Partial results exist (Ye-Abbe 2018, Wang et al. 2020). The optimal characterization in heterogeneous settings is an open research direction (see Chapter 18).

Coded gradient: $s + 1$ partitions of $d/N$ scalars each = $(s+1) d / N$ scalars. Mask seeds: $O(t \log n)$ bits, negligible. Total: $\approx (s+1) d / N$ scalars.

Coded gradient: one masked $d$-scalar gradient upload. Mask exchange: $O(n)$ pairwise interactions per round. Total: $\approx d \cdot b + O(n^2)$ bits per round.

Stragglers absorbed: $\mathbb{E}[T_{\text{round}}] = (H_n - H_s)/\lambda$. Mask-cancellation overhead: small constant. Total: $\approx (H_n - H_s)/\lambda$.

For typical FL parameters ($n = 1000$, $d = 10^7$, $s = 100$): per-user storage $\approx 10^6$ scalars; per-user uplink $\approx 10^8$ bits; per-round latency $\approx 1\lambda^{-1}$. The uplink dominates the per-round cost; the storage dominates the per-user memory budget.

Coded gradient computation reduces latency substantially but does not reduce the per-user uplink. For uplink-bound deployments, combine with sparsification or quantization. For storage-bound deployments, consider approximate gradient coding (§6.3).

For $L$-smooth, $\mu$-strongly-convex losses with approximate gradient coding, $\mathbb{E}[F(\mathbf{w}_T) - F^*] \leq (1 - \mu/L)^T \cdot (F(\mathbf{w}_0) - F^*) + \epsilon \sigma^2 / \mu$.

For smooth non-convex losses with approximate gradients of relative error $\epsilon$, $\mathbb{E}\|\nabla F(\mathbf{w}_T)\|^2 \leq \mathcal{O}((F(\mathbf{w}_0) - F^*)/T) + O(\epsilon \sigma^2)$. That is, the gradient norm converges to a $\mathcal{O}(\sqrt{\epsilon})$ neighborhood of zero, not the function value to a $\mathcal{O}(\epsilon)$ neighborhood of optimum.

If the loss satisfies the Polyak-Łojasiewicz (PL) condition (which deep networks empirically often do, especially in the over-parameterized regime), the convex-case bound transfers and gives an $\mathcal{O}(\epsilon)$ asymptotic floor on function-value suboptimality. This is consistent with empirical observations in production FL.

The full characterization for general non-convex losses is open. A research-grade exercise would be to validate the PL-based bound on standard FL benchmarks (FEMNIST, Shakespeare, CelebA-FL) and report whether the $\mathcal{O}(\epsilon)$ scaling holds empirically. This direction connects coded computing to the modern non-convex SGD analysis literature.