Distributed Stochastic Gradient Descent

Prior work already covered PySpark pipelines, Hadoop, and Kubernetes. This session closes the distributed gradient-descent family. The next major block is federated learning.

The goal here is to see how stochastic gradient descent (SGD) — a weight-update rule that follows the slope of the loss — behaves when data and workers live on many machines. On one box the story is a single model, a single dataset, and a single slope. On many boxes the same slope is computed in pieces, and those pieces must be mixed so that one global model (a shared set of weights that has seen every shard) can still learn.

Four variants appear, in this order: ordinary SGD on one model, synchronous distributed SGD, asynchronous SGD, decentralized SGD, then a preview of overlap SGD and quantized SGD.

The running picture is Amazon-scale retail traffic: purchases and processing happen across the world, so one zone cannot hold every record. Each zone trains on its own slice and returns a slope. The rest of the notes rebuild that slope from a one-weight toy network, then put the same update onto a server, onto a server with no waiting, and onto a neighbor graph with no server at all.

8.1 The Distributed Training Problem

On a single machine the story is simple. You hold one model and one dataset. You compute a loss (a number that says how wrong the current prediction is). You compute a gradient of that loss with respect to the weights (the slope of the loss as a function of those weights). You update the weights. Distributed training breaks that picture because the dataset no longer sits in one place.

A worker node is a machine that trains on a shard of the data. A server (also called a master) is a machine that combines worker results. The dataset is split across workers because one box cannot hold every record.

Think of a worldwide checkout desk. You cannot run every purchase through one cash register. Each geographic zone keeps its own receipts, trains on those receipts, and reports a local slope. The verbal picture from class is the same: you cannot run worldwide purchase processing on a single system, so each zone trains on its own slice.

That picture is the Amazon-scale retail example that runs through the whole session. Purchases and processing happen across the world. One zone feeds one copy of the model and computes a local loss. Another zone feeds another copy and computes another loss. Each copy produces its own gradient.

The analogy maps as follows. A zone is a worker. The receipts in that zone are a data shard. The local slope is a worker gradient. The shared catalog of prices (the model) must still be one catalog, not a different catalog per city. The analogy breaks when zones have wildly different traffic mixes: averaging slopes still mixes them, but the mix is only as fair as the shards are representative.

8.1.1 Why Gradients Must Be Combined

The gradients are scattered along servers and worker machines. No single worker has seen the full dataset, so no single local slope is a complete training signal. The training loop must collect those gradients, average them, and form one global gradient — a single update direction for a shared model.

Let $K$ be the number of workers. Let $g_k$ be the gradient computed on worker $k$. The verbal rule is: collect all the gradients, average them, and compute the global gradient.

Averaging is the same idea already used in earlier distributed work: local results become one number the whole system can apply. After the average exists, the server (or the workers, in a peer design) applies that one direction to the shared weights.

The verbal explanation of the aim is blunt. You want a global model that represents all of the data. That means the model has learned from the complete dataset, not from one zone alone.

Standard data-parallel training writes the same mix as a sum of local gradients, then takes a step:

$$\nabla W=\nabla W_1+\nabla W_2+\cdots +\nabla W_K,w\leftarrow w-\alpha \nabla W$$

The lecture form averages first, then steps with learning rate $\eta$:

$$w\leftarrow w-\eta \bar{g}=w-\eta \cdot \frac{1}{K}\sum _{k=1}^K{g}_k$$

Those two writings agree when $\alpha =\eta /K$ (or when each local $g_k$ is already a mean over its shard and the server uses a matching scale). The exam version is the lecture average: collect, average, apply one global gradient.

Two ways to get that global model appear.

Centralized aggregation. Workers send gradients to a server. The server aggregates. After aggregation, the server's weights are treated as equal to training on all of the data. In the parameter-server writing, each round is four stages: workers pull the current weights, workers push local gradients, the server aggregates, and the server updates the stored model. That is the master-worker design used in the synchronous and asynchronous sections below.

Peer exchange. There is no centralized server. Workers exchange gradients with neighbors. Model 3 talks to model 2. Model 2 talks to model 1. Model 1 and model 3 do not need a direct link. After several rounds of exchange, every model holds a copy of the mixed information. The models converge. A little extra loss compared with a perfect central average is acceptable. The requirement is still one global model.

A ring All-Reduce is the textbook cousin of this peer picture: each worker both trains and talks to neighbors, so there is no dedicated master that only averages. Neighbor averaging in Section 8.6 is the same idea with a distance threshold instead of a fixed ring.

The rest of this session first rebuilds ordinary SGD on one weight. Then it rebuilds the same update in the distributed, asynchronous, and decentralized settings.

Imagine $K=4$ workers drawn as four dots on a map, each holding an arrow (its gradient). Centralized aggregation is a star: every arrow is mailed to a hub, the hub draws one mean arrow, and the hub mails the new weight back. Peer exchange is a path: the arrow at node 3 is blended into node 2, then into node 1. After enough blends, every node’s arrow points about the same way. The landmark on that picture is the hub: if the hub dies, the star stops; the path can still mix around a dead far node.

The same pattern appears on multi-GPU machines: GPU 1 through GPU 4 each hold a shard and send a gradient to a server. Geography is optional. Any split of the data across devices is the same problem.

Retail platforms, payment switches, and warehouse-scale GPU clusters all hit this wall: the data is large and sharded, the model must still be one model. Federated learning later adds a privacy constraint (do not ship the records, only the slopes or weights), but the mixing step is the same average.

8.1.2 Student Questions and Answers

Several students asked how this session sits on the stack that already covered pipelines and cluster tools.

The next question is the distributed view of SGD itself, not the cluster tooling.

The aim of that collection step is easy to understate.

8.1.3 Industry Applications

Real-world: multi-zone retail and payment traffic cannot train on one box. Each geographic zone holds a subset of Amazon-like transactions. Each zone trains locally and returns a gradient. The same pattern appears on multi-GPU machines: GPU 1 through GPU 4 each hold a shard and send a gradient to a server.

8.2 Stochastic Gradient Descent on a Single Weight

Before workers and servers, the update itself must be solid. The vanilla setting is one model, one weight, and one mini-batch loss. Every later distributed rule is this same minus-the-slope step, only the slope is computed on a shard or applied on a busy server.

Think of a hiker on a foggy hill. The ground under their boots is the loss. A tiny step along the weight axis is a probe. The slope they feel is the gradient. Walk opposite the uphill arrow and the loss falls. The analogy breaks on a ridge or a saddle: a one-dimensional weight has no sideways ridge, but a real network does.

8.2.1 Weight Update Rule

Let $w_t$ be the current weight at iteration $t$ (where you stand now). Let $w_{t+1}$ be the next weight. Let $\eta$ (eta) be the learning rate — how large a step we take. Let $\nabla L$ be the gradient of the loss with respect to the weight (the slope of $L$ as a function of $w$).

The verbal rule is: new weight equals old weight minus learning rate times the gradient.

Learning means the weights converge. Convergence is a sequence of these iterations. $w_t$ is where you are. $w_{t+1}$ is the next iterate. The learning rate scales the gradient of the loss. Too large an $\eta$ jumps over the valley. Too small an $\eta$ crawls.

8.2.2 A One-Weight Network and Squared Loss

Take the smallest useful network: one weight, no bias. The map is $y=mx$. Here the slope $m$ is the weight $w$. The input is $x$. The prediction is $\hat{y}=wx$. The verbal setup is: a simple neural network with only one weight; $x$ multiplied with the weight; ignore the bias.

The weight is initialized at $2$. The input is $x=3$. The true output is $y=10$. The model predicts

$$\hat{y}=wx=2\times 3=6$$

The ground-truth value is $10$. The difference is the error. The model is wrong because the prediction sits away from the true value. You cannot change the input. The weight is the reason for the loss.

Use a mean squared error with a one-half factor so the later derivative is clean. Let $L$ be the loss. The verbal form is: predicted value minus ground truth, whole square, times one by two.

Substitute the numbers from the initialized network:

$$L=\frac{1}{2}(\hat{y}-y{)}^2=\frac{1}{2}(6-10{)}^2=\frac{1}{2}\times 16=8$$

Loss $8$ is the number you get after substitution. Loss tells how bad the prediction is. Higher loss means a worse prediction. Lower loss means a better prediction.

A true line through the origin with $x=3$ and $y=10$ would need $w=10/3\approx 3.33$. Starting at $w=2$ is too small, so $\hat{y}=6$ undershoots $10$. The update should raise $w$.

8.2.3 Gradient as Slope

A gradient is a slope. School algebra already has this. If you change the denominator by a small amount, how much does the numerator change? For two points the slope is

$$\frac{y_2-y_1}{x_2-x_1}$$

The verbal restatement is: you sit at $x_1$ and move to $x_2$. The change in $x$ approaches zero. The change that movement causes on the $y$-axis is the gradient.

Here the $x$-axis is the weight. The $y$-axis is the loss. The gradient asks: how fast is the loss changing when you slightly change the weight? In other words, how sensitive is the loss to a tiny change in the weight?

That school-slope picture is the working analogy for the rest of the lecture. The later closed form $(wx-y)x$ looks different on paper. Geometrically it is the same object: $\Delta L/\Delta w$ in the limit of a tiny $\Delta w$.

8.2.4 Worked Example: Finite-Difference Gradient

Keep $x=3$ and $y=10$. Start at $w=2$ with loss $8$. Nudge the weight by a tiny change of $0.01$.

A plot of $L(w)=\frac{1}{2}(3w-10{)}^2$ is a parabola opening upward. The horizontal axis is $w$. The vertical axis is $L$. The vertex sits at $w=10/3\approx 3.33$, where $L=0$. At $w=2$ you are left of the vertex, on a downward slope as $w$ grows, so the tangent is negative. The landmark is that vertex: every update should walk toward it, not away.

8.2.5 Sign of the Gradient and the Minus Sign in the Update

The sign is not decoration. It tells you which way to move.

• If the gradient sign is negative, increasing the weight decreases the loss. You need to increase the weight.
• If the gradient sign is positive, increasing the weight increases the loss. You need to decrease the weight.

Why is this gradient negative? Because $y_2-y_1$ is a smaller loss minus a larger loss. As the weight increases, the loss decreases, so the slope is negative.

Plug the negative gradient into the update. Let $w_{\text{new}}$ be the updated weight. The verbal formula is: new weight equals old weight minus eta times the gradient value.

$$w_{\text{new}}=w-\eta \nabla L$$

Here $\nabla L=-12$ (the rounded slope). Then

$$w_{\text{new}}=w-\eta (-12)=w+12\eta$$

The minus sign in the update and the minus sign in the gradient cancel. The weight increases. That is exactly what the three-point picture asked for. If the gradient had been positive, the same minus sign would have reduced the weight.

A short rule to memorize:

• Negative gradient: add to the weight to reduce the loss.
• Positive gradient: subtract from the weight to reduce the loss.
• The formula $w-\eta \nabla L$ does this automatically.

8.2.6 Completing the Update Step

Apply the rounded gradient $-12$ to $w=2$. The verbal arithmetic is: old weight minus learning rate times the gradient minus twelve, which is $3.2$. The only learning rate that turns $2$ and $-12$ into $3.2$ is $\eta =0.1$:

$$w_{\text{new}}=2-0.1\times (-12)=2+1.2=3.2$$

The first demo states the new weight $3.2$ without speaking $\eta$. The later asynchronous demo uses $\eta =0.1$ on the same update family. Those two classroom numbers lock together: $\eta =0.1$ is the step size for this lecture.

You can replay the same table by hand. Fix the input. Change the weight. Recompute prediction and loss. That is the role of the gradient: it tells you how a small weight change moves the loss, and the update uses that slope to walk toward a better weight.

Gradient magnitude also matters. Too much loss means a larger update, positive or negative. Near a minimum the magnitude is small, so only tiny adjustments are needed. The verbal test is: if I change the weight just a little, how much does the loss move?

This one-weight walk is the same update a search engine uses when it nudges ranking weights from click logs, and the same update a warehouse GPU uses on a shard of images. The distributed sections only change who computes $g$ and when $w$ is allowed to move.

8.2.7 Student Questions and Answers

The sign of the slope is the most common first confusion.

A second confusion is to treat the input as a knob.

8.3 Mini-Batch Gradient Descent

The same slope idea now meets a dataset with many samples. Mini-batch gradient descent splits the full dataset into smaller batches and updates from each small batch instead of from one giant pass.

Think of grading a stack of 400 exam scripts. You can recompute the class average after every single script (noisy, slow). You can wait until all 400 are marked (stable, late). Or you can mark 32, average those, adjust your marking scheme, then mark the next 32. That middle cadence is a mini-batch. The analogy breaks when scripts are not shuffled: a batch of only one question type is a biased average, just as an unshuffled shard is a biased gradient.

8.3.1 Three Ways to Use the Dataset

Suppose the dataset has $400$ samples. Three update styles exist.

1. Sample-wise (batch size $1$). Loop over every sample. For each pair $(x,y)$, predict, compute a gradient, and update at once. Immediate update. No waiting. No averaging.
2. Full batch. Compute a gradient on the entire dataset. Average those gradients. Then update once.
3. Mini-batch. Take a subset. Compute gradients on that subset. Average those gradients. Update from the average. Repeat on the next subset.

The thing that matters is when the weight changes. Sample-wise updates are the most frequent and the most expensive. Full-batch updates are the most stable and the slowest to show a step. Mini-batch sits in the middle.

When to pick which: use sample-wise only on tiny models and tiny data. Use full batch when $N$ fits in memory and you want a true mean slope. Use mini-batch for almost every large model.

Textbook gradient descent (GD) is the full-batch column: sum (or average) $g_i$ over the whole set, then one update. SGD in the narrow sense is the sample-wise column. In this course, and in data-parallel training, “SGD” usually means the mini-batch column: a subset per step, because no worker sees the full set.

8.3.2 Why Mini-Batches for Large Models

Updating after every sample becomes too time-consuming on huge models. Real-world: transformers and large language models can contain some $120$ billion parameters. In those cases a per-sample loop is too complex. Choose the approach from the size of the model.

A compact picture uses a frozen weight such as $1.5$ and four inputs. Each input varies. The weight stays fixed for the batch. Each sample produces a loss and then a gradient, using the finite-difference or derivative method above. Then take the average gradient and apply one update.

That average is the same mixing step a parameter server performs in distributed SGD. GPU 1, GPU 2, GPU 3, and GPU 4 each send a gradient. The server averages. Then one global update runs. Mini-batch on one machine and synchronous distributed SGD on four GPUs differ only in where the shards live.

On a 400-sample set with $B=32$ you get $400/32=12.5$, so after shuffling you take twelve batches of $32$ and one leftover batch of $16$, or you drop the leftover, or you pad. Each of those batches is one average and one update. A 120-billion-parameter transformer cannot afford $400$ separate backward passes per tiny batch of text if a grouped backward is already expensive; the grouped backward is the mini-batch.

Draw the 400-sample set as a long tape. Sample-wise is a tick after every square. Full batch is one tick at the end of the tape. Mini-batch is a tick every $B$ squares. The landmark is the tick: that is when $w$ is allowed to move. Takeaway: the slope formula does not change; the clock that applies it does.

Multi-GPU training in a data center is mini-batch SGD with hardware shards. Each GPU holds part of the global batch. The server (or an All-Reduce) averages GPU gradients and applies one global update. Recommendation systems and speech models use the same cadence: group examples, freeze weights, average, step.

8.3.3 Student Questions and Answers

8.3.4 Industry Applications and Exam Notes

Real-world: Multi-GPU training is mini-batch SGD with hardware shards. Each GPU holds part of the batch. The server averages GPU gradients and applies one global update.

8.4 Synchronous Distributed SGD

Synchronous distributed SGD is mini-batch SGD with a barrier. Every worker starts from the same global weight. Every worker computes a gradient on its own data shard. The server waits until all gradients arrive. The server averages. The server applies one global update. Then it sends the new weight back. No worker starts the next round on a private model.

The finite-difference slope from Section 8.2 is slow to type on every sample. The same slope has a closed form. That algebra looks unlike $(y_2-y_1)/(x_2-x_1)$, but it is geometrically the same change in loss when $w$ changes.

8.4.1 Derivative of Squared Loss

Keep

$$L=\frac{1}{2}(\hat{y}-y{)}^2,\hat{y}=wx$$

Substitute the prediction:

$$L=\frac{1}{2}(wx-y{)}^2$$

The verbal plan is: treat the inside as $u$, so the loss is one-half $u$ square. Use the power rule: $x^m$ differentiates to $m{x}^{m-1}$. Set $u=wx-y$. Then $L=\frac{1}{2}{u}^2$. Differentiating with respect to $u$ produces a factor $2u$ that cancels the one-half:

$$\frac{dL}{du}=u$$

The chain rule also needs $du/dw$. The derivative is with respect to $w$, not with respect to $x$. The input $x$ is data. The weight $w$ is the parameter. So

$$\frac{du}{dw}=x$$

and the full chain is

$$\begin{array}{rl}\frac{dL}{dw}& =\frac{dL}{du}\cdot \frac{du}{dw}\\ & =u\cdot x\\ & =(wx-y)x\end{array}$$

Spot-check on the Section 8.2 toy: $w=2$, $x=3$, $y=10$:

$$g=(2\times 3-10)\times 3=(6-10)\times 3=-12$$

That matches the rounded finite-difference slope $-12$. Dimensional check: $wx-y$ is a prediction error (same units as $y$); multiplying by $x$ turns that error into a slope on the $w$-axis.

A common slip is to differentiate with respect to the input. Then $du/dx=w$ and you would write $(wx-y)w$, which is the wrong parameter and the wrong table.

8.4.2 Worked Example: Four Workers, One Global Weight

For brevity the global weight is a scalar $w_t=1.5$. In a real net this would be a whole set of weights. In the first round every worker receives $1.5$.

Each worker has its own data shard. The spoken pairs and later “closer to 3, 5, 7, 9” line up with four points $(x,y)=(1,3),(2,5),(3,7),(4,9)$. Worker 1 is spoken as $(1,3)$ and worker 4 as gradient $-12$. The inner two pairs follow from those gradients and from the spoken targets $5$ and $7$:

$$g=(1.5\cdot x-y)x$$

Solving for $y$ on workers 2 and 3 with the consistent closed form recovers $y=5$ and $y=7$. These four points lie on the line $y=2x+1$. The toy model has no bias, so it cannot fit that line exactly; the best scalar $w$ is a compromise near $70/30\approx 2.33$. One synchronous step should raise $1.5$ toward that compromise, not away from it.

8.4.3 One Global Model, Not Four Local Models

A common wrong picture is: worker 1 updates model 1, worker 2 updates model 2, and so on, leaving four final models. That is not this algorithm.

Workers do not create four different final models. They send gradients. Worker 1 computes $g_1$. Worker 2 computes $g_2$. Worker 3 computes $g_3$. Worker 4 computes $g_4$. The master node receives all four. The master performs one global update. Then the new weight is shared with every worker.

That loop is the parameter-server four-stage cycle (pull weights, push gradients, aggregate, update) with a barrier on stage 3: the server does not update until every worker has pushed. An All-Reduce implements the same barrier without a dedicated master: workers average among themselves, then each applies the same $\bar{g}$. The lecture exam picture is the master: one global update.

Inputs: a shared $w$, $K$ shards, learning rate $\eta$. Outputs: one new $w$, identical on every worker after the broadcast. Time cost: one local backward per worker plus a wait for the slowest worker plus one average. Space cost: one model replica per worker plus the server copy.

8.4.4 Aggregation Beyond Simple Averaging

The average used above is FedAvg-style: a simple mean of worker gradients (or of worker models). It is fine for teaching. It is not the end of the research story. Aggregation is not as simple as a plain mean. A large literature studies better mixing rules.

Standard federated averaging (FedAvg) weights each model by how many local samples it trained on:

$$M_{\text{agg}}=\sum _{i=1}^K\frac{n_i}{N}{M}_i,N=\sum _{i=1}^K{n}_i$$

If every shard has the same $n_i$, this collapses to the lecture mean. Federated SGD (FedSGD) is the gradient analog: average gradients instead of weights. The classroom four-worker step is FedSGD with equal shard sizes. Unequal zones (a huge US-East log and a tiny APAC log) need the $n_i/N$ weights, or the tiny zone punches above its data.

FedAvg is the ideal case: shards look like the same distribution (IID), workers have similar speed, and no worker is adversarial. Real federated systems break those conditions, which is why later aggregators exist (median-based mixers, proximal terms, personalization). For this lecture, keep the simple mean, and remember that it is a baseline.

Real-world: a paper from IIT Bombay on federated asynchronous simultaneous training is flagged as the next reading. The spoken short name sits in the FedAvg / Fed-async family (the audio sounds like “fed asked”). The matching published title is FedAST: Federated Asynchronous Simultaneous Training — a buffered asynchronous aggregator for training several models at once on a shared client pool, so a slow client on a large model does not stall every task. Keep the lecture’s reading pointer; treat FedAST as the standard short name for that method.

Synchronous averaging is how a four-GPU image trainer stays on one ResNet, and how a payment-fraud model stays on one weight vector while card logs stay in regional warehouses. The next design removes the wait.

8.4.5 Student Questions and Answers

The highlighted gradient column still looks like a new object to some students.

The chain-rule target is the other high-frequency slip.

8.5 Asynchronous SGD and Stale Gradients

Asynchronous SGD still has a server. The change is the barrier. Workers do not wait for each other. Whenever a worker finishes a gradient, it sends that gradient at once. The server updates the global weight at once. Faster workers do not sit idle because a slow worker (a straggler) is late.

8.5.1 Synchronous Versus Asynchronous Updates

Inputs: current server weight $w$, learning rate $\eta$, a stream of worker gradients $g_k$ that may have been computed on older copies of $w$. Outputs: a sequence of server weights, one per arrival, not one per full round.

When to pick which: if GPUs are twins on one fabric, stay synchronous. If one zone’s network is a second slower, go asynchronous and watch staleness.

Federated learning uses the same fork. Synchronous FL waits for a chosen set of agents before aggregating. Asynchronous FL lets trusted agents upload whenever they finish, and the aggregator may close a round on a count, a timer, or a quorum such as $80\%$ or $90\%$.

8.5.2 Worked Example: Immediate Server Updates

Start with a normal SGD picture. Current weight, updated weight, learning rate, gradient. If the gradient is negative, the weight increases. If the gradient is positive, the weight decreases. Now add asynchrony.

8.5.3 Stale Gradients

A stale gradient is a gradient computed using old model parameters but applied to a newer model. Staleness is the gap between the weight used to compute $g$ and the weight that receives $g$.

Walk the server-side clock:

1. Time 0. All workers copy $w=2.0$ and start computing.
2. Time 1. Worker 1 updates the server. Server becomes $2.20$. Fresh update.
3. Time 2. Worker 2 updates the server. Server becomes $2.80$. Worker 2's gradient was computed at $2.0$, so it is already slightly stale relative to $2.20$.
4. Time 3. Worker 3 finally sends a gradient computed from $w=2.0$. The server currently has $2.80$. The gradient belongs to old $w=2.0$ but is applied to $2.80$. That is a stale gradient.

Worker 3 is the loud case. Compute at $2.0$. Apply at $2.80$. The gap is $0.80$ in weight space.

Staleness is not always fatal. If the learning rate is small and the gradients are not too noisy, the system can still converge. Large steps plus very old gradients are the dangerous mix.

Draw a timeline. Horizontal axis: server time. Vertical axis: $w$. The server staircase jumps at each arrival: $2.00$, $2.20$, $2.80$, $3.80$. Horizontal dashed lines mark the weight each worker used to compute ($2.0$ for all three in this trace). The landmark is the gap between a dashed line and the staircase at apply time. Takeaway: the gradient is honest about an old hill, then it is spent on a new hill.

8.5.4 When Workers Receive New Weights

A natural hope is: after worker 1 updates the server to $2.20$, the server immediately broadcasts $2.20$ to everyone else, and those workers restart. In basic asynchronous SGD that broadcast does not happen.

• The server does not wait for all workers.
• The server does not force remaining workers to restart with the newest model after every update.
• Workers keep running. A worker may still be computing a gradient on an older copy.
• No forced broadcast hits worker 2 and worker 3 while they are busy. The server does not interrupt them.

Worker 1 is not left out of the “remaining workers” story. After worker 1 sends its gradient and the server moves to $2.20$, worker 1 may pull the latest $w$ and start the next mini-batch. The pull happens because this batch is done. The server does not interrupt a worker in the middle of a gradient.

Typical pull points (implementation dependent):

• When a worker asks for the next task.
• When a new mini-batch starts.
• When a new epoch starts.
• After some fraction of workers have reported, such as $80\%$ or $90\%$, in variants that wait for a quorum before shipping new weights.

The principle: while a worker is running a gradient, it is not stopped. Once it starts a new batch or a new epoch, it may read the cache of new weights. Slow workers may still send gradients computed from old weights. Those gradients may be stale.

8.5.5 Server Load Compared With Synchronous Averaging

Synchronous SGD: workers send gradients, the server averages once, the server updates once. Asynchronous SGD: each finished worker triggers its own weight update. Backpropagation on the workers still happens locally. The extra question is whether the server becomes busier because it applies many single-worker updates instead of one mean.

The steps are similar: a gradient arrives, a weight is written. The count of server writes is higher in the async path, because each arrival is an update rather than one averaged update. Whether that is a heavy difference is something to check in code. It seems more operations happen on the server in the async case.

Complexity: for $K$ workers and $T$ local steps, sync SGD does about $T$ averages and $T$ writes. Vanilla async SGD does about $KT$ writes. The worker-side backward pass count is the same family of work; the server-side apply count is what grows. Network traffic also shifts from one bundled round to many small messages, which can help or hurt depending on latency versus bandwidth.

Parameter-server clusters for huge embedding tables often run this way: many workers stream gradients, the server applies them as they land, and a slow crawler does not freeze the ads model. The cost is the stale apply you just traced from $2.0$ onto $2.80$.

8.5.6 Student Questions and Answers

Several questions clustered on one confusion: when the new $w$ goes back, and whether anyone is forced to restart.

The restart hope is the same confusion asked the other way.

Worker 1’s next batch is a third wording of the pull rule.

A separate confusion is server load, not staleness.

8.6 Decentralized SGD

Decentralized SGD removes the central parameter server. Each worker keeps its own model. Workers periodically exchange parameters with neighbors in a local vicinity. “Vicinity” here means models whose distance is less than or equal to a threshold. Those nearby machines share parameters.

This is not asynchronous SGD with the server unplugged. Asynchronous SGD still has a server and stale gradients. Decentralized SGD is the neighbor-exchange design.

8.6.1 Neighbor Exchange Instead of a Master

The topology matches the peer picture from the opening. Model 3 need not talk to model 1 if both talk to model 2. After several exchanges, information mixes through the graph.

The student wrap-up sometimes labels this neighbor average as “asynchronous.” That label is wrong. Asynchronous SGD still has a server and stale gradients. Decentralized SGD is the neighbor-exchange design. Workers update locally. When workers come closer (distance at most the threshold), they exchange weights, often by averaging.

A ring All-Reduce is the data-center cousin: every node is a worker, there is no dedicated parameter server, and the mix is a fixed ring instead of a distance threshold. Blockchain-style swarm mixing is a further cousin used in some federated settings; the lecture exam object is the threshold neighbor average.

Complexity: each mix ships one weight vector across a short link. With a central master, every worker ships to the same hub (fan-in) and the hub ships back (fan-out), so the hub bandwidth shrinks as $1/K$. Neighbor mix costs grow with the number of edges, not with a single hot spot. The trade-off is mixing time: a long path needs several rounds before the far worker’s data arrives.

8.6.2 When Decentralized Training Helps

Use decentralized SGD when communication costs are high.

Real-world: edge computing on low-end devices. A small device cannot talk to a master all the time. Exchanging with a neighbor is a different cost from sending to a master. Federated learning is another setting where a central controller may be impractical. You may not be able to deploy a machine that acts as master controller.

Failure handling is local. Updates live on each machine. You can exchange only with neighbors inside distance $d\le$ threshold. A dead far-away node does not freeze the whole ring the way a dead parameter server can.

Picture three phones in a corridor. Each trains on its own photos. Every few minutes a phone pairs with whoever is within a few metres and they average weights. The corridor is the distance threshold. The landmark is the missing cloud server: if the building’s uplink dies, mixing can continue indoors.

Phone-to-phone model mixing in a weak-signal warehouse, and peer mixing among hospital sites that will not stand up a shared aggregator, are the same pattern: train locally, average with whoever is close enough, accept a little extra loss.

8.6.3 Student Questions and Answers

The label mix-up is the one confusion to keep.

8.7 Batch Loops, Overlap SGD, and Quantized SGD

The same one-weight update appears in code as three data loops. Two further distributed variants are named for later study: overlap SGD and quantized SGD.

8.7.1 Sample-Wise, Mini-Batch, and Full-Batch Loops

These three loops are the concrete form of Section 8.3. They are also the inner step that each distributed worker runs on its shard.

8.7.2 Overlap SGD and Quantized SGD

Overlap SGD is named as the next distributed variant after async and decentralized. The details are deferred so that code and demos can be inspected together.

The idea, in one paragraph, is to hide network wait inside math that must happen anyway. In a naive synchronous round you finish the whole backward pass, then you all-reduce the gradient, then you step. Overlap SGD starts shipping the first ready gradient buckets while later layers are still computing backward. The communication and the remaining compute sit on the same timeline instead of end-to-end. Frameworks such as multi-GPU data-parallel trainers do this by grouping parameters into buckets and launching an asynchronous reduce as soon as a bucket is ready. The lecture will treat the implementation as a follow-up, not as an exam derivation.

Quantized SGD compresses what workers send. Quantized means: lower the bit size of the data. Gradients (or weights) travel in fewer bits. That is a communication trick, not a new loss. It belongs with overlap SGD in the follow-up session, before the move into federated learning.

A standard integer often uses $32$ bits. If a value only needs the range $\{0,1,2,3\}$, $2$ bits suffice. Mixed-precision training goes further: store some tensors in $16$-bit floating point instead of $32$. The transform is lossy: $1.00$ and $1.01$ may collapse to the same code. Models usually still converge, sometimes to a slightly worse minimum. For distributed SGD the payoff is smaller messages on the wire, which is the industrial reason to quantize shipped gradients.

Federated learning is the next large topic: how to aggregate, how to fill missing features, horizontal federated learning, and vertical federated learning. Horizontal (sample-based) federated learning is the Gboard-style case: the same features, different users. Vertical (feature-based) federated learning is the bank-plus-shop case: the same people, different columns. Distributed SGD is the bridge. Close these variants first.

Shipping FP16 or INT8 gradients between GPU racks is why quantized SGD shows up in production trainers. Overlapping the reduce with backward is why a well-tuned data-parallel job is not twice as slow as a math-only profile would suggest.

8.7.3 Student Questions and Answers

The closing request is a recap of the three main distributed methods.

Exam Guidance Summary

This session did not publish a mark table. The study signal is still sharp.

1. Close the distributed SGD family before federated learning. Know synchronous distributed SGD, asynchronous SGD, and decentralized SGD as three different designs, not three names for one idea.
2. Expect numerical traces like the classroom demos. One-weight finite-difference slope (loss $8\to 7.88$ when $w:2\to 2.01$). Four-worker mean gradient from shards. Async chain $2.00\to 2.20\to 2.80\to 3.80$ with stale gradients.
3. Memorize the sign rule. Positive gradient: decrease the weight. Negative gradient: increase the weight. The minus in $w-\eta \nabla L$ is what makes the rule automatic.
4. Do not confuse sending gradients with training four final models. In synchronous distributed SGD the master applies one global update.
5. Name staleness correctly. A stale gradient is computed on old weights and applied to newer weights. Small $\eta$ and quiet gradients can still converge.
6. Federated learning is flagged as the next high-value block. Aggregation, missing features, horizontal federated learning, and vertical federated learning are the coming topics. Overlap SGD and quantized SGD (lower bit size) are the remaining distributed details to finish first.

Key Industry Applications

1. Amazon-scale multi-zone data. Worldwide purchase and transaction streams do not fit on one trainer. Each zone trains on a subset and returns a gradient so one global model can represent all zones.
2. Multi-GPU mini-batch training. GPU 1 through GPU 4 compute gradients on shards. A server averages and performs one global update. This is synchronous distributed SGD on accelerators.
3. Large language models and transformers. Models with some $120$ billion parameters make per-sample updates too heavy. Mini-batch (and sharded mini-batch) is the practical cadence.
4. Edge computing and low-end devices. Always-on links to a master are expensive. Decentralized SGD exchanges parameters with neighbors inside a distance threshold.
5. Federated learning. Central coordination may be impractical. FedAvg-style means are the teaching baseline. Richer aggregation, including federated asynchronous simultaneous training (IIT Bombay), is active research. Horizontal and vertical federated learning come next.
6. Quantized communication. Lowering bit size of shipped gradients is the industrial reason for quantized SGD: less network cost between workers and servers.