distributed-optimization.
46 of 378 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-003 | PyTorch FSDP | Fully Sharded Data Parallel as an industry-grade PyTorch component: a sharding factor F generalising replication through full sharding, communication overlapped by backward prefetching, and a rate limiter over the CUDA caching allocator. The first cluster in #114 whose practices its paper actually supports. | Read |
| NOTE-006 | GPipe | Pipeline parallelism by splitting a mini-batch into micro-batches. Bubble overhead is O((K−1)/(M+K−1)) and negligible once M ≥ 4K; re-materialization plus partitioning cuts peak activation memory from O(N×L) to O(N + (L/K)(N/M)). | Read |
| NOTE-029 | ZeRO++: Extremely Efficient Collective Communication for Giant Model Training | Attacks each of ZeRO’s three communication collectives separately — block-quantized weight all-gather, a secondary weight shard held redundantly to trade memory for communication, and an all-to-all quantized gradient reduction replacing reduce-scatter. 4× less communication, up to 2.16× throughput at 384 GPUs. | Read |
| NOTE-030 | Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism | Splits a transformer layer across GPUs by choosing the partition that needs no communication in the middle — column-parallel then row-parallel — so a whole layer costs two all-reduces forward and two backward. No compiler, no library changes, a few lines of PyTorch. 8.3B parameters on 512 GPUs at 76% scaling efficiency. | Read |
| NOTE-033 | Using DeepSpeed and Megatron to Train Megatron-Turing NLG 530B | The 3D-parallelism report — 8-way tensor, 35-way pipeline, data parallel over 560 DGX A100 nodes — and an unusually complete training recipe, including a batch-size ramp from 32 to 1920 and β₂ lowered to 0.95 to suppress loss spikes. Also the corpus’s cleanest artefact of pre-Chinchilla misallocation: 530B parameters trained on 270B tokens. | Read |
| NOTE-050 | PipeMare: Asynchronous Pipeline Parallel DNN Training | Drops the synchronous bubble in pipeline parallelism by letting stages run on stale weights, and makes that converge with two corrections — rescale the learning rate by the stage’s delay, and approximate the weights the backward pass should have seen. Up to 4.6× the pipeline utilization of GPipe, at up to 2× less weight and optimizer memory than PipeDream. | Read |
| NOTE-074 | Advances and Open Problems in Federated Learning | A 66,000-word multi-institution survey defining federated learning and cataloguing its open problems. Its durable contribution to this record is the cross-device / cross-silo distinction, which separates two settings with almost nothing in common operationally. | Skimmed |
| NOTE-089 | Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices | By arranging workers into a virtual d-dimensional grid and using chunk indices from Butterfly All-Reduce to ensure no two peers share the same group in consecutive rounds, Moshpit All-Reduce achieves the communication efficiency of all-reduce while tolerating node failures—combining the best properties of all-reduce and gossip without their respective drawbacks. | Read |
| NOTE-095 | Epidemic Learning: Boosting Decentralized Learning with Randomized Communication | Fully randomizing the communication topology at every round, rather than using a fixed or semi-dynamic graph, provably reduces the transient iterations needed to enter the linear speedup regime by a factor of s^2, because the random averaging step contracts the inter-node model drift by O(1/s) regardless of spectral properties of any fixed graph. | Read |
| NOTE-096 | Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training | 99.9% of gradient exchanges in distributed SGD are redundant; by sparsifying to the top 0.1% of gradients and using error accumulation with momentum correction to neutralize staleness, communication bandwidth can be slashed by 600x with no accuracy loss. | Read |
| NOTE-097 | Asynchronous Stochastic Gradient Descent with Delay Compensation | The stale gradient g(w_t) used in ASGD is merely the zero-order approximation of the correct gradient g(w_{t+tau}); adding a first-order Taylor correction term—approximating the Hessian via a scaled diagonal of the gradient outer product—substantially reduces the bias introduced by delay without extra communication cost. | Read |
| NOTE-099 | Distributed Deep Learning in Open Collaborations | By accumulating gradients until a fixed global batch size is reached regardless of how many peers are active, DeDLOC makes collaborative training mathematically equivalent to large-batch synchronous SGD, preserving training stability while tolerating dynamic peer arrival, departure, and heterogeneous hardware. | Read |
| NOTE-100 | Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent | The parameter server is a communication bottleneck because every node talks to it at every step — O(n) traffic on the busiest node. D-PSGD replaces this with neighbor-only gossip averaging via a doubly stochastic weight matrix W, reducing per-node communication to O(Deg). On a ring, that is O(1). The computational complexity is identical to C-PSGD, so decentralized wins whenever communication dominates. | Read |
| NOTE-103 | ZeRO: Memory Optimizations Toward Training Trillion Parameter Models | Data parallelism wastes memory by replicating all model states on every device; partitioning these states instead of replicating them yields linear memory reduction with device count while keeping communication volume nearly identical to standard data parallelism. | Read |
| NOTE-105 | Subspace Networks: Scaling Decentralized Training with Communication-Efficient Model Parallelism | Because transformer projection matrices naturally converge to low-rank subspaces during training (rank collapse), explicitly constraining those matrices to a shared low-dimensional subspace forces activations to lie in that subspace too, enabling lossless inter-layer compression that avoids the error accumulation that defeats naive lossy compression in model-parallel settings. | Read |
| NOTE-107 | Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction | When server-to-worker communication is non-negligible (tau_s > 0), there is a fundamental trade-off: increasing n can improve either the dimension- dependent communication term or the variance-dependent compute term, but not both—even when all workers share the same data distribution. This exposes an inherent scalability wall in centralized federated optimization that gradient compression cannot overcome. | Read |
| NOTE-109 | Communication-Efficient Learning of Deep Networks from Decentralized Data | Performing multiple local SGD steps on each client’s private data before averaging model parameters is far more communication-efficient than a single gradient step per round, and the resulting averaged model is robust to non- IID and unbalanced data distributions provided all clients share the same initialization each round. | Read |
| NOTE-111 | Distributed asynchronous deterministic and stochastic gradient optimization algorithms | Gradient descent does not require synchronized updates across processors — convergence holds as long as (1) delays are bounded (partially asynchronous model) or (2) each processor updates infinitely often (totally asynchronous model). | Read |
| NOTE-112 | Deep learning with Elastic Averaging SGD | Coupling local workers to a center variable through a soft elastic force (rather than hard averaging) lets workers explore different regions of a nonconvex loss surface; more exploration leads to better solutions in deep networks that have many local optima, and this can be achieved with far less frequent communication than parameter-server baselines. | Read |
| NOTE-115 | 1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed | Error-compensated compression is incompatible with Adam because Adam’s non- linear variance term corrupts the error cancellation mechanism; freezing the variance after it stabilizes converts Adam into a linear (momentum SGD) update that admits lossless error compensation, yielding both Adam’s convergence speed and 1-bit communication efficiency. | Read |
| NOTE-117 | Don’t Use Large Mini-Batches, Use Local SGD | Large-batch SGD converges to sharp minima that generalize poorly; switching to local SGD mid-training introduces beneficial gradient noise that finds flatter minima, recovering single-machine generalization performance without sacrificing parallelism or communication efficiency. | Read |
| NOTE-119 | Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates | The fundamental statistical cost of Byzantine robustness is captured exactly by the term alpha/sqrt(n) added to the standard 1/sqrt(nm) minimax rate, where alpha = f/m is the fraction of Byzantine workers, n is per-worker sample count, and m is total workers. This additive penalty is unavoidable (proven tight via a lower bound) and arises because up to alpha fraction of workers can inject arbitrary gradient signals. | Read |
| NOTE-120 | Asynchronous Local Computations in Distributed Bayesian Learning | Replacing synchronous all-agent communication with pairwise gossip and filling the saved communication budget with multiple cheap local ULA gradient steps allows agents to exploit fast local computation while reducing expensive communication; because the extra stochasticity from gossip and mini-batch gradients is zero-mean with bounded variance, it does not break asymptotic convergence. | Read |
| NOTE-124 | Async-HFL: Efficient and Robust Asynchronous Federated Learning in Hierarchical IoT Networks | Adding an intermediate asynchronous gateway aggregation layer in a three- tier hierarchy simultaneously reduces backhaul communication (by averaging locally before uploading) and stabilizes convergence, while gradient- diversity-based device selection and ILP-based topology management provide the system management needed to realize these gains under real-world heterogeneity. | Read |
| NOTE-127 | Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms | All major communication-efficient SGD algorithms differ only in how they trade off three communication-reduction strategies—periodic averaging (tau), mixing matrix sparsity (W), and auxiliary variables (v)—and a single unified bound on the “network error” captures all three, enabling direct comparison and new hybrid designs. | Read |
| NOTE-128 | Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling | Standard local-update federated SA algorithms converge to the wrong point under heterogeneity because multiple local steps using different local operators accumulate drift; injecting a global correction signal at each local step (the FedHSA update) cancels this drift exactly, enabling unbiased convergence even with Markovian noise and no projection step. | Read |
| NOTE-130 | OpenDiLoCo: An Open-Source Framework for Globally Distributed Low-Communication Training | DiLoCo’s dual-optimizer local-SGD approach reduces inter-node communication by up to 500x with negligible quality loss, and pseudo-gradients can be all- reduced in FP16 without performance degradation, making billion-scale decentralized training practical. | Read |
| NOTE-133 | Local SGD Converges Fast and Communicates Little | Workers can run SGD independently for H steps before averaging, and as long as H = O(sqrt(T/(Kb))), this infrequent synchronization incurs no asymptotic cost in convergence rate—communication can be slashed without sacrificing linear speedup. | Read |
| NOTE-135 | SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficient | In pipeline parallelism, computation scales as O(n^3) while communication scales as O(n^2) with model size, so sufficiently large models can be trained efficiently even over internet-grade connections—SWARM exploits this by using stochastic pipelines that dynamically rebalance load across unreliable heterogeneous nodes. | Read |
| NOTE-136 v2 | Coordination of groups of mobile autonomous agents using nearest neighbor rules | Even if a network is disconnected at every individual time step — no single round of communication reaches everyone — the agents can still reach consensus as long as the union of communication graphs over any fixed- length sliding window has a spanning tree. | Read |
| NOTE-137 | Towards Crowdsourced Training of Large Neural Networks using Decentralized Mixture-of-Experts | Mixture-of-Experts architectures are uniquely suited to volunteer computing because each input activates only a small fraction of all experts, making asynchronous training with stale gradients far less harmful than in dense networks, while the DHT enables scalable decentralized bookkeeping without any central coordinator. | Read |
| NOTE-141 | Generalized EXTRA stochastic gradient Langevin dynamics | Standard decentralized SGLD (DE-SGLD) suffers from a bias due to network effects that does not vanish even with full-batch gradients; adapting the EXTRA correction mechanism from decentralized optimization to Langevin dynamics eliminates this bias and yields faster convergence. | Read |
| NOTE-142 | HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent | When the optimization problem is sparse (each gradient update touches only a small fraction of the decision variable), memory overwrites between processors are rare and introduce negligible error, making lock-free parallel SGD both safe and efficient. | Read |
| NOTE-145 | DiLoCo: Distributed Low-Communication Training of Language Models | Replacing the plain-averaging outer step of FedAvg with Nesterov momentum, while using AdamW for inner optimization over H~500 steps, enables language model pretraining across geographically distributed devices with minimal bandwidth requirements and strong robustness to data heterogeneity and worker availability. | Read |
| NOTE-148 | Smoothing DiLoCo with Primal Averaging for Faster Training of LLMs | DiLoCo’s performance improves with more inner steps because the two-loop structure inadvertently provides stronger smoothing of the iterate sequence; GPA replicates this smoothing effect at every step by decoupling the gradient-computation interpolation constant from the model-evaluation averaging constant, eliminating the need for a two-loop structure. | Read |
| NOTE-150 | LAYUP: Asynchronous decentralized gradient descent with LAYer-wise UPdates | Because the backward pass takes roughly twice as long as the forward pass, running them in separate threads with a 1:2 forward-to-backward thread ratio keeps both passes continuously busy; additionally, applying updates layer- by-layer as gradients arrive rather than waiting for the full gradient halves the average staleness, improving convergence robustness without any gradient compensation scheme. | Read |
| NOTE-151 | Stochastic Gradient Push for Distributed Deep Learning | Using the PushSum protocol’s ratio-based de-biasing trick removes the requirement for symmetric (bidirectional) communication, allowing decentralized SGD to operate on directed graphs and substantially reduce communication overhead versus AllReduce SGD in bandwidth-constrained settings. | Read |
| NOTE-152 | PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization | Making the compressor linear (i.e., equivariant under averaging) unlocks all-reduce aggregation instead of slower all-gather; combined with warm- starting the subspace iteration from the previous step and error feedback, a single power iteration step matches the quality of a full SVD while being dramatically cheaper. | Read |
| NOTE-153 | Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD | By decoupling synchronization into a background thread that maintains an anchor model and having workers pull back toward that anchor rather than waiting for direct peer communication, computation and communication are fully overlapped, reducing the effective communication-to-computation ratio from ~35% to ~1.5% in practical settings. | Read |
| NOTE-154 | Distributed Optimization with Gradient Tracking over Heterogeneous Delay-Prone Directed Networks | Embedding the robustified Ratio Consensus protocol into ADD-OPT and augmenting the network graph with virtual delay nodes transforms a delayed directed network into a delay-free augmented network, allowing existing convergence proofs to apply with the augmented spectral radius replacing the original, at the cost of a smaller allowable step-size. | Read |
| NOTE-155 | signSGD: Compressed Optimisation for Non-Convex Problems | When gradients and noise are dense (a condition empirically verified in deep networks), the sign of the gradient is an effective update direction; aggregating signs by majority vote across workers is equivalent to maximum- likelihood decoding of a repetition code, achieving sqrt(M)-fold variance reduction with M workers using only 1 bit per parameter per direction. | Read |
| NOTE-156 | Byzantine-Tolerant Machine Learning | Averaging is catastrophically fragile: a single Byzantine worker can steer the aggregate to any arbitrary vector. The fix is to replace aggregation with selection — choose the gradient vector that is most “centrally located” among its nearest correct neighbors, using the n-f-2 nearest neighbors to ensure the majority of those neighbors are correct workers. | Read |
| NOTE-157 | SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum | Adding a slow outer momentum step after every tau inner steps of local SGD or a decentralized optimizer consistently improves both optimization and generalization at negligible extra communication cost, because slow momentum corrects accumulated drift between workers at the outer level. | Read |
| NOTE-184 | Training Deep Nets with Sublinear Memory Cost | Two contributions, and the famous one is the second. First, treat memory allocation over the computation graph as a compiler problem — liveness analysis, in-place operations, memory sharing. Then, on top of that, drop most intermediate feature maps and recompute them segment by segment during the backward pass. Dividing an n-layer chain into sqrt(n) segments costs sqrt(n) memory for one extra forward pass; the extreme of the same analysis is log n memory for n log n extra forward computation. | Read |
| NOTE-333 v2 | Wan | An open 14B text-to-video recipe whose evidence is mostly systems measurement: 2D context parallelism cuts communication overhead from over 10% to under 1%, and caching and 8-bit kernels give 1.62× and 1.27×. Its three modelling ablations run on 1.3B text-to-image. Two are read from training loss, and on FID one of them favours the rejected option. The applications in §5 are demonstrated almost entirely by figures. | Read |
| NOTE-338 v2 | Step-Video-T2V | A 30B text-to-video DiT on a 16×16×8 VAE. By the authors’ own benchmark the VAE reconstructs about as well as HunyuanVideo’s 8×8×4, and an independent measurement in Open-Sora 2.0 disagrees. Video DPO raises a tie-weighted preference score from 45% to 55% on 300 prompts. Every architecture comparison is reported without numbers, and the “state of the art” in the abstract is contradicted by the paper’s own Table 9. | Read |