Async SGD

Asynchronous Parallel Training Methods are the distributed ML training approaches where workers compute and apply gradient updates independently without waiting for synchronization — unlike synchronous methods (AllReduce) where all workers must exchange gradients before any can proceed, async methods like Hogwild!, async SGD, and Local SGD allow faster workers to update the model immediately, eliminating the straggler problem at the cost of using slightly stale gradients, with recent variants like Local SGD achieving comparable accuracy to synchronous training while reducing communication by 10-100×.

Synchronous vs. Asynchronous Training

Synchronous (AllReduce):
 Worker 0: [Forward][Backward][AllReduce][Update]  ← All wait for slowest
 Worker 1: [Forward][Backward][AllReduce][Update]
 Worker 2: [Forward][Backward][   wait  ][AllReduce][Update]  ← Straggler

 Asynchronous:
 Worker 0: [Forward][Backward][Update][Forward][Backward][Update]...
 Worker 1: [Forward][Backward][Update][Forward][Backward][Update]...
 Worker 2: [Forward][ Backward ][Update][Forward][ Backward ]...
 ← No waiting! Each worker proceeds independently

Async SGD Approaches

Parameter Server Architecture

[Parameter Server]
               /    |    |    \
           push/  push/ push/  push/
           pull   pull  pull   pull
            /      |     |       \
       [W0]     [W1]   [W2]    [W3]

 Worker loop:
 1. Pull current parameters from server
 2. Compute gradient on local mini-batch
 3. Push gradient to server
 4. Server applies update (no barrier)
 5. Repeat (using whatever parameters are current)

• Problem: Worker's gradient computed on stale parameters (τ steps old).
• Staleness τ: Number of updates applied since this worker read parameters.
• Large τ → gradient direction may be wrong → slower convergence or divergence.

Hogwild! (Lock-Free SGD)

# Shared parameter vector (no locks)
shared_params = np.zeros(d)  # Shared memory

def worker(data_shard):
    while not converged:
        sample = random_sample(data_shard)
        grad = compute_gradient(shared_params, sample)  # Read (possibly stale)
        shared_params -= lr * grad  # Write (no lock, atomic-ish)

• Works when: Updates are sparse (each update touches few parameters).
• Theory: Converges when sparsity ratio is high → few conflicts between workers.
• Applications: Sparse SVMs, matrix factorization, word2vec.

Local SGD

# Each worker trains independently for H steps, then synchronizes
for epoch in range(num_epochs):
    for h in range(H):  # H local steps
        batch = next(local_dataloader)
        loss = model(batch)
        loss.backward()
        optimizer.step()  # Local update only
    
    # Synchronize every H steps
    all_reduce(model.parameters())  # Average parameters across workers

• H=1: Standard synchronous SGD (AllReduce every step).
• H=10-100: Communicate 10-100× less while maintaining quality.
• Research shows: H=8-32 works well for most CV and NLP tasks.
• Communication reduction: H× less bandwidth used.

Convergence Comparison

Federated Learning

• Extreme async: Devices (phones, hospitals) train locally for days → send update to server.
• Massive staleness: Acceptable because privacy > speed.
• FedAvg: Average model weights from K clients every round.
• Communication: Only model diff/update, not raw data → privacy preserving.

Asynchronous parallel training is the scalability solution for heterogeneous and communication-constrained distributed systems — while synchronous training provides the cleanest convergence guarantees, async methods eliminate the straggler bottleneck and reduce communication overhead, with Local SGD emerging as the practical sweet spot that achieves near-synchronous accuracy while communicating 10-100× less, making it increasingly adopted for large-scale training on heterogeneous clusters and cross-datacenter settings where communication costs dominate.