Permutation Compressors for Provably Faster Distributed Nonconvex Optimization

1 INTRODUCTION

• Communication is a key bottleneck in distributed training, motivating methods that reduce communication among compute nodes.Modern deep models are trained using specialized distributed and parallel systems.Source: §1 · p. 1

1.1 THE PROBLEM AND ASSUMPTIONS

• The optimization goal is an approximately stationary point of a potentially nonconvex objective while keeping worker-to-server communication small.The setup assumes differentiable local functions and a lower-bounded objective.Source: §1.1 · pp. 1–2

1.2 A BRIEF OVERVIEW OF THE STATE OF THE ART

• MARINA is presented as the state-of-the-art method for theoretical communication complexity, relying on biased gradient estimators and independent unbiased compressors.Its communication cost combines rounds with transmitted floats per round; the analysis assumes independent compressors.Source: §1.2 · pp. 2–3

1.3 SUMMARY OF CONTRIBUTIONS

• The paper extends MARINA to correlated compressors, introduces Hessian variance without additional assumptions, and corroborates its theoretical predictions on synthetic quadratics and MNIST autoencoder training.The new analysis also establishes results for smooth nonconvex and smooth Polyak–Łojasiewicz functions.Source: §1.3 · p. 3
• PermK improves MARINA’s communication complexity by up to √n when d ≥ n and 1 + d/√n when d ≤ n in the low-Hessian-variance regime.The improvement degrades as Hessian variance grows, recovering the earlier complexity in the worst case.Source: §1.3 · p. 3

2 BEYOND INDEPENDENCE: THE POWER OF CORRELATED COMPRESSORS

• Without independence, MARINA’s rate can depend on ω rather than ω/n; the paper generalizes its analysis to correlated unbiased compressors.This extends the method beyond the independence assumption used in prior analyses of unbiased compression.Source: §2 · pp. 3–4

2.1 AB INEQUALITY: A TOOL FOR A MORE PRECISE CONTROL OF COMPRESSION VARIANCE

• The AB inequality bounds aggregate compression variance using constants A and B; standard unbiased compressors satisfy it without independence, while independence can improve A.The inequality is stated for unbiased compressors and arbitrary input vectors.Source: §2.1 · p. 4

2.2 WHY CORRELATION MAY HELP

• For fixed A, increasing B can reduce the bound on aggregate variance, motivating appropriately correlated compressors.The section describes this as the key intuition behind their usefulness.Source: §2.2 · p. 4

2.3 INPUT VARIANCE COMPRESSORS

• Input-variance compressors with A = B are singled out because they have favorable communication-complexity properties in the later analysis.The paper introduces them as a special class of compressors.Source: §2.3 · p. 4

2.4 PERMK: PERMUTATION BASED SPARSIFIERS

• PermK uses random permutations in both dimension regimes; for d ≥ n it is unbiased with A = B = 1, while for n ≥ d each worker uses a dependent Rand1 sparsifier.The simple constructions fix K rather than allowing it to be chosen freely.Source: §2.4 · p. 5

3 HESSIAN VARIANCE

• Under MARINA's assumptions, L± is finite when L+ is finite and can be small even when L− is large, a regime where analysis gains are most pronounced.Source: §3 · p. 6

3.1 HESSIAN VARIANCE CAN BE ZERO

• When all local functions are identical, Hessian variance is zero even though L− and L+ may be arbitrarily large; EF21 then cannot improve as n grows.Source: §3.1 · p. 7
• With fi(x)=φ(x)+b_i^T x+c_i, Hessian variance remains zero despite potentially different minimizers, a setting not corresponding to overparameterized machine learning.The passage describes this setting as generally challenging for standard methods.Source: §3.1 · p. 7

3.2 SECOND ORDER CHARACTERIZATION

• A second-order characterization links Hessian variance to local Hessians; for quadratics it is the largest-eigenvalue size of their matrix-valued variance.Definition 4 remains applicable even when the local functions are not twice differentiable.Source: §3.2 · p. 7

4 IMPROVED ITERATION AND COMMUNICATION COMPLEXITY

• The refined analysis extends MARINA to unbiased, potentially correlated compressors and accounts for Hessian variance.Source: §4 · p. 8
• At Theorem 4’s maximum allowed stepsize, MARINA converges in T communication rounds, with T reported in Table 3.Source: §4 · p. 8
• With parameters optimized, MARINA using PermK has better communication complexity than the compared RandK and EF21 with TopK methods.Communication complexity counts rounds multiplied by the maximum floats sent by a worker per round; the initial O(d) communication is excluded.Source: §4 · p. 8

4.1 IMPROVEMENTS IN THE IDEAL ZERO-HESSIAN-VARIANCE REGIME

• For PermK, A = B, eliminating dependence on the potentially very large L2+ when Hessian variance is zero.Source: §4.1 · p. 8
• At zero Hessian variance and d ≥ n, PermK gives O(L_-Δ_0ε^-1d/n), at least √n better than RandK and n× better than GD and EF21.The GD and EF21 communication complexity is O(L_-Δ_0ε^-1d).Source: §4.1 · pp. 8–9
• At zero Hessian variance and d ≤ n, PermK gives O(L_-Δ_0ε^-1), with at least a 1 + d/√n gain over RandK and a d× gain over GD and EF21.The RandK complexity is no better than O(L_-Δ_0ε^-1(1 + d/√n)); GD and EF21 have complexity O(L_-Δ_0ε^-1d).Source: §4.1 · pp. 8–9

5 EXPERIMENTS

• The experiments compare convergence against bits sent per node, using theory-prescribed parameters and grid-searched step sizes; the quadratic tasks vary n and L±, while MNIST varies data homogeneity.The quadratic experiments use d=1000; the MNIST experiment uses n=1000 and d=25088, with at most 26 floats sent per communication round.Source: §5 · p. 9, §5.1 · p. 9, §5.2 · p. 10

5.1 TESTING THEORETICAL PREDICTIONS ON A SYNTHETIC QUADRATIC PROBLEM

• PermK outperforms RandK on the synthetic quadratic tasks; for n≥1000 and L±≤0.21, MARINA with PermK also outperforms EF21 with TopK.When L±=0.91, TopK is superior except when n=10000.Source: §5.1 · p. 9

5.2 TRAINING AN AUTOENCODER WITH MNIST

• On MNIST, PermK outperforms RandK; it is faster than TopK at bp∈{0.9, 1.0}, while TopK is faster at bp∈{0, 0.5} by a difference described as tiny compared with RandK.At bp=0.75, the two compressors have almost the same performance.Source: §5.2 · p. 10

A.2 EXPERIMENT WITH QUADRATIC OPTIMIZATION TASKS: FULL DESCRIPTION

• Quadratic tasks are strongly convex and vary homogeneity through noise scale; zero noise makes worker matrices equal, while increasing noise makes the functions less similar.The task-generation procedure is designed to control L±, and the experiments use theoretical algorithm parameters with step-size grid search.Source: §A.2 · p. 15, §A.1 · p. 15

A.3 COMPARISON OF MARINA WITH RANDK AND MARINA WITH PERMK ON QUADRATIC

• PermK behaves better than RandK across the reported quadratic experiments and tolerates larger step sizes, with the improvement growing as n increases.Plots where algorithms diverged were omitted.Source: §A.3 · p. 16

A.4 COMPARISON OF EF21 WITH TOPK AND MARINA WITH PERMK ON QUADRATIC

• For n≥10000 and L±≤0.21, PermK converges faster than TopK; at large L±, TopK performs better except when n=10000.The appendix also reports that PermK converges faster in all experiments when n>d.Source: §A.4 · p. 16

A.5 EXPERIMENT WITH MNIST: FULL DESCRIPTION

• The MNIST experiment sets bp as the probability that a node takes the shared split D0; bp=1 gives all nodes the same data, while bp=0 gives different splits.Nodes are assigned one of n+1 randomly formed data splits, with n=1000.Source: §A.5 · p. 19
• For bp∈{0.9, 1.0}, PermK outperforms other compressors for every tested λ, and its relative convergence improves as λ increases.The comparisons use λ={0, 0.00001, 0.001} and bp={0, 0.5, 0.75, 0.9, 1.0}.Source: §A.5 · p. 19

A.6 COMPARISON OF MARINA WITH RANDK AND MARINA WITH PERMK ON MNIST

• Across the reported MNIST experiments, PermK performs better than RandK, and the practical results reproduce dependencies seen in theory and the synthetic quadratic experiments.Plots where algorithms diverged were omitted.Source: §A.6 · p. 19

A.7 COMPARISON OF EF21 WITH TOPK AND MARINA WITH PERMK ON MNIST DATASET

• At bp∈{0.9, 1.0}, PermK tolerates larger step sizes and converges faster than TopK; at bp∈{0, 0.5}, they tolerate approximately the same step sizes, while TopK performs better for λ∈{0, 0.00001}.Source: §A.7 · p. 20

B MARINA ALGORITHM

• MARINA resets its estimator to the true gradient with probability p; otherwise workers compress gradient differences, with the original analysis assuming independent compression operators.The compressor is sampled independently across workers in the described MARINA setup.Source: B MARINA ALGORITHM · p. 21

C.3 PROOF OF THEOREM 1

• PermK compressors in the stated results are unbiased and belong to IV(1); another PermK construction is unbiased and belongs to IV(A), with A=1−n−d.Source: §C.3 · p. 24, §C.4 · p. 25

C.5 PROOF OF THEOREM 3

• Under twice continuous differentiability, the proof represents each local gradient difference using an averaged Hessian along the line segment between the two points.The passage identifies that averaged Hessian as Hi(x, y).Source: §C.5 · p. 25

C.6 PROOF OF THEOREM 4

• The proof follows Gorbunov et al. (2021) closely, using the AB assumption and Hessian variance to bound a key term and refine the analysis.The remaining steps are described as essentially identical to the earlier analysis.Source: §C.6 · p. 27
• The proof derives an upper bound on the expected estimator quantity using Assumptions 2, 3, and 4.Source: §C.6 · p. 28
• The proof combines inequalities (14) and (15), the stepsize choice, and Lemma 4, then sums the resulting bounds over iterations.Source: §C.6 · pp. 28–29

D POLYAK-ŁOJASIEWICZ ANALYSIS

• Under the PŁ condition, MARINA is stated to have a linear convergence rate; the section compares optimized communication complexities for MARINA with PermK and RandK, and EF21 with TopK.Source: D POLYAK-ŁOJASIEWICZ ANALYSIS · p. 30, Table 5 · p. 30

D.1 PROOF OF LEMMA 6

• The proof of Lemma 6 establishes that L−≥µ for L−>0 and µ from the PŁ assumption.Source: D POLYAK-ŁOJASIEWICZ ANALYSIS · p. 30

D POLYAK-ŁOJASIEWICZ ANALYSIS

• When L±=0 and d≥n, PermK has complexity O(max{dL−/nµ, d}), versus O(max{dL−/√nµ, d}) for RandK; the improvement is strict when dL−/√nµ>d.Source: D POLYAK-ŁOJASIEWICZ ANALYSIS · p. 30
• When d≤n and (1+d/√n)L−/µ>d, PermK improves the RandK complexity from O(max{(1+d/√n)L−/µ, d}) to O(max{L−/µ, d}).Source: D POLYAK-ŁOJASIEWICZ ANALYSIS · p. 30

E.1 EF21 RATE IN THE NON-CONVEX REGIME

• The nonconvex EF21 analysis presents a convergence theorem under Assumptions 1 and 2, with a stepsize condition and an iterate selected uniformly at random.The supplied theorem passages do not show the resulting bound.Source: §E.1 · p. 32

E.2 EF21 IN PŁ REGIME

• The PŁ analysis adapts the preceding proof by applying the PŁ inequality and unrolling a recurrence.The theorem statement specifies Assumptions 1, 2, and 5, but the supplied passage does not show its bound.Source: §E.2 · pp. 33–34

F COMMUNICATION MODEL

• The paper treats worker-to-server communication as the bottleneck and neglects server-to-worker communication.The authors describe this as a standard model and provide a brief explanation of when it is useful.Source: F COMMUNICATION MODEL · p. 35
• The work does not analyze the more difficult regime where server-to-worker communication is also costly.The authors state that the work could be extended to that regime but do not explore the extension.Source: F COMMUNICATION MODEL · p. 35

G.1 ON CONTRACTIVE COMPRESSORS

• TopK retains the K largest-magnitude entries and is α-contractive with α = K/d; RankK is α-contractive with α = K/min{a,b}.RankK uses a best rank-K approximation of an a×b matrix.Source: §G.1 · p. 35

G.2 ON ERROR FEEDBACK

• Naive use of biased compressors may cause exponential divergence, motivating error feedback to control compression error and obtain convergence.The passage notes that theoretical understanding of contractive compressors is less developed than for unbiased compressors.Source: §G.2 · p. 36

I.1 CASE d ≥n

• For d ≥ n, the general PermK construction permutes coordinates, assigns blocks to nodes, and randomly distributes any remaining coordinates among nodes.When d = kn + r with 0 ≤ r < n, some nodes send one fewer coordinate.Source: §I.1 · p. 38

I.2 CASE n ≥d

• For n ≥ d, PermK forms a multiset with each coordinate vector repeated q times, appends r zero vectors, and randomly permutes the n entries.Here n = qd + r with 0 ≤ r < d.Source: §I.2 · p. 39

J IMPLEMENTATION DETAILS OF PERMK

• PermK nodes can independently generate the shared permutation samples by starting from the same random seed and using the same generator; Fisher–Yates sampling takes O(d) time.The permutation samples are generated in each communication round.Source: J IMPLEMENTATION DETAILS OF PERMK · p. 40

K.1 BLOCK PERMUTATION COMPRESSOR

• The block permutation compressor partitions coordinates into at most n disjoint blocks and assigns each node a permuted block-specific mapping.The definition constructs the mappings from diagonal indicator matrices for the blocks.Source: §K.1 · p. 40

K.2 PERMUTATION OF MAPPINGS

• A permutation of mappings randomly permutes a collection of deterministic mappings across nodes.The appendix states a lemma placing this construction in U(A, B), but the supplied passage truncates the parameter values.Source: §K.2 · p. 41

L ANALYSIS OF COMPLEXITY BOUNDS

• The complexity analysis introduces a lemma for a function over specified ranges of x and y and nonnegative a and b.The supplied passage does not include the lemma's conclusion.Source: L ANALYSIS OF COMPLEXITY BOUNDS · p. 44

L.1 NONCONVEX OPTIMIZATION

• For n ≤ d, the analysis assumes n divides d and evaluates MARINA with PermK and RandK using communication-complexity expressions parameterized by p and k.The passage defines the comparison setup but does not provide the expressions' values.Source: §L.1.1 · p. 44
• The nonconvex analysis compares communication-complexity bounds for MARINA with PermK and RandK and EF21 with TopK, including a stated state-of-the-art bound for RandK.The text identifies Table 4 as summarizing the bounds, but the supplied passages do not show the bound values.Source: §L.1.1 · pp. 45–46, §L.1.2 · p. 47
• For n ≥ d, the appendix gives an average-bit communication expression for PermK and compares its predicted complexity with RandK and TopK.The supplied passages point to Table 4 for the bounds but do not show the numerical or asymptotic comparisons.Source: §L.1.1 · p. 45, §L.1.2 · pp. 47–48

L.2 PŁ ASSUMPTION

• Under the PŁ assumption, the appendix presents complexity bounds for the compared algorithms with optimal parameters in Table 5.The supplied passages do not show the table's bound values.Source: §L.2.1 · pp. 48–49, §L.2.2 · p. 49

• When L± is large, splitting the functions into nonempty groups where each group's L± is small provides an alternative way to use L±.Source: M GROUP HESSIAN VARIANCE · p. 50
• The group analysis assumes independent compressors across groups and groupwise Assumption 4 constants; independence and unbiasedness make a term vanish in the group AB inequality.Source: M GROUP HESSIAN VARIANCE · pp. 50–51
• For n≤d with equal-sized groups, using PermK in each group yields a communication-complexity bound evaluated with p=1 or p=1/G.Source: M GROUP HESSIAN VARIANCE · pp. 52–53
• Although dL−/n from (36) is always better than dL−/G from (53), (53) can be better when dL±/√n is a bottleneck and L_G± is small.Source: M GROUP HESSIAN VARIANCE · p. 53
• In a two-group quadratic example with distinct positive-semidefinite matrices, each group's L_G± is zero while L± is positive, and the resulting bound improves on (36).Source: M GROUP HESSIAN VARIANCE · p. 53