PaperlayerView exact revision on arXiv

Source-linked AI summary

EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback

Peter Richtárik, Igor Sokolov, Ilyas Fatkhullin

arXiv:2106.05203v1cs.LGmath.OCstat.ML

TL;DR

Existing error-feedback analyses are limited by single-node settings, strong assumptions, or extra unbiased compressors that increase communication cost. The paper proposes EF21, analyzes it under standard assumptions in distributed heterogeneous settings, and reports faster convergence rates and consistent practical superiority over EF.

  • Problem

    Existing error-feedback analyses require restrictive settings or assumptions, or add unbiased compressors that increase communication cost.

  • Method

    The paper proposes EF21, a new error-feedback mechanism designed for distributed heterogeneous data using biased compression.

  • Results

    EF21 achieves an O(1/T) rate for smooth nonconvex problems, improves on the previous O(1/T^2/3) result, and has a linear rate for Polyak-Lojasiewicz functions.

  • Takeaways & Limitations

    EF21 consistently and substantially outperforms EF in experiments and can use much larger learning rates.

  • Takeaways & Limitations

    The EF–EF21 equivalence is restricted because Top-k is not additive, while rescaled unbiased compressors are randomized and fail the stated condition.

Abstract

from arXiv · show

Error feedback (EF), also known as error compensation, is an immensely popular convergence stabilization mechanism in the context of distributed training of supervised machine learning models enhanced by the use of contractive communication compression mechanisms, such as Top-$k$. First proposed by Seide et al (2014) as a heuristic, EF resisted any theoretical understanding until recently [Stich et al., 2018, Alistarh et al., 2018]. However, all existing analyses either i) apply to the single node setting only, ii) rely on very strong and often unreasonable assumptions, such global boundedness of the gradients, or iterate-dependent assumptions that cannot be checked a-priori and may not hold in practice, or iii) circumvent these issues via the introduction of additional unbiased compressors, which increase the communication cost. In this work we fix all these deficiencies by proposing and analyzing a new EF mechanism, which we call EF21, which consistently and substantially outperforms EF in practice. Our theoretical analysis relies on standard assumptions only, works in the distributed heterogeneous data setting, and leads to better and more meaningful rates. In particular, we prove that EF21 enjoys a fast $O(1/T)$ convergence rate for smooth nonconvex problems, beating the previous bound of $O(1/T^{2/3})$, which was shown a bounded gradients assumption. We further improve this to a fast linear rate for PL functions, which is the first linear convergence result for an EF-type method not relying on unbiased compressors. Since EF has a large number of applications where it reigns supreme, we believe that our 2021 variant, EF21, can a large impact on the practice of communication efficient distributed learning.

1 Introduction

Modern machine learning training uses over-parameterized models and enormous datasets, motivating optimization methods designed for efficient distributed computation. This paper studies nonconvex distributed optimization and communication-efficient first-order methods using biased compression.

  • 1 Introduction: Over-parameterized models and enormous datasets make training efficiency a central optimization-design concern.The paper notes that successful models may have more parameters than available training data points.
  • 1 Introduction: Sophisticated architectures generally create nonconvex optimization problems, while large datasets necessitate partitioning computation across multiple machines.Workers may further parallelize local computation with hardware accelerators.
  • 1 Introduction: The paper focuses on solving nonconvex distributed optimization problems with communication-efficient first-order methods using biased compression operators.The stated goal includes clean convergence analysis without strong assumptions such as globally bounded gradients.
  • 1 Introduction: The paper develops theoretical results, analyzes the connection between EF and EF21, and evaluates the methods experimentally.The main theory appears in Section 3, while experiments are described in Section 5.

2 Background and Motivation

The paper reviews why biased compression and error feedback are difficult to analyze, then introduces EF21 as a distributed method designed to address these gaps. It claims stronger convergence guarantees and better empirical performance than prior EF-based approaches.

  • Error feedback and biased compression: Biased compressors can make naive first-order methods diverge, motivating error feedback as a stabilization mechanism.Top-k gradient descent can exhibit exponential divergence, while error feedback was proposed as a fix but initially remained heuristic.
  • Open theoretical gaps: Existing theory is limited by single-node analyses, strong assumptions, restricted regimes, or additional unbiased compressors that increase communication cost.Open questions include linear convergence for heterogeneous distributed data using biased compressors only.
  • EF21 approach: EF21 is a new error-feedback mechanism that naturally operates in distributed heterogeneous data settings and targets communication-efficient first-order optimization with biased compressors.The method is proposed to remove assumptions such as globally bounded gradients from the analysis.
  • Theoretical results: O(1/T) convergence is established for EF21 in the smooth nonconvex setting, improving on the previous O(1/T^2/3) result while requiring weaker assumptions.The paper argues that bounded-gradient and bounded-dissimilarity assumptions are too strong for meaningful error-feedback analyses.
  • Theoretical results: EF21 has a linear convergence rate for Polyak-Lojasiewicz functions without introducing additional unbiased compressors.This addresses an open problem in the general heterogeneous data setting and contrasts with prior results requiring special regimes or extra communication.
  • Empirical results: Extensive experiments on synthetic problems and deep-learning benchmarks report that EF21 consistently and substantially outperforms EF, partly because it permits larger learning rates.The paper also proposes EF21+, a more aggressive variant with even better empirical behavior.

3 Main Results

The paper re-engineers error feedback through a Markov compressor that compresses differences from previously compressed vectors, yielding EF21 for single-node and distributed optimization. The analysis covers heterogeneous data under smoothness and lower-boundedness assumptions, while extending to EF21+ and establishing convergence results.

  • Motivation: Naive biased compression can diverge because persistent gradient distortion destabilizes optimization near a limiting iterate.The distortion can remain nonzero when local gradients at the minimizer do not vanish.
  • Markov compressors: EF21 compresses vectors relative to previously compressed estimates, so the transmitted discrepancy can progressively vanish.This replaces the unavailable limiting vector with a recursively maintained compressed vector, making the mechanism implementable.
  • Markov compressors: Under assumptions about input-sequence convergence, the Markov compressor's distortion converges to zero; linear input convergence is one sufficient case.The construction is then deployed in gradient descent and distributed gradient descent.
  • EF21: EF21 is formalized first for a single node and then extended to multiple nodes by applying the Markov compressor to each local gradient.The master averages the gradient estimators and broadcasts the updated model after each gradient-like step.
  • Convergence analysis: The analysis assumes smoothness and lower boundedness, with Theorem 1 and Theorem 2 providing the stated convergence guarantees for Algorithm 2.The supplied theorem passages identify the assumptions and stepsize conditions but do not include the resulting rate formulas.
  • EF21+: EF21+ is a hybrid method that often performs particularly well in practice, and both main theorems apply under an additional deterministic-compressor assumption.Top-k is given as an example of a deterministic compressor.

4 Relationship between EF and EF21

The paper reviews EF and establishes that EF21 produces identical iterates to EF only under restrictive compressor conditions. These conditions exclude important practical compressors such as Top-k.

  • Restricted equivalence: Despite the restricted theorem, EF21 is named for its close conceptual relationship with EF.The paper describes this connection as unexpected but informative.
  • Original EF: EF is presented in an equivalent algorithmic form to facilitate comparison with EF21.The method initializes each node’s error to zero, compresses the first local gradient message, and repeatedly feeds compression errors into subsequent messages.
  • Original EF: EF compensates compression errors by adding each message’s error to the next vector before compression.The error is the difference between the intended and compressed messages, and the process repeats across iterations.
  • Restricted equivalence: Theorem 3 states that EF and EF21 generate the same iterates when the compressor is deterministic, positively homogeneous, and additive.The proof proceeds by induction using the compressor properties and the methods’ update rules.
  • Restricted equivalence: Top-k is deterministic and positively homogeneous but not additive, while rescaled unbiased compressors are randomized and fail the deterministic condition.Thus, the theorem’s equivalence conditions are not met by these practical compressor families.

5 Experiments

Experiments evaluate EF, EF21, and EF21+ on heterogeneous distributed logistic regression using compressed communication. The proposed methods tolerate larger stepsizes and achieve target accuracy with fewer communicated bits than EF.

  • Experimental setup: The experiments solve nonconvex-regularized logistic regression on datasets split across 20 clients in a heterogeneous distributed regime.The datasets come from LibSVM, with each client assigned an equal data partition except for the final remainder.
  • Stepsize tolerance: EF21 and EF21+ avoid the accuracy plateau observed for EF across stepsize choices with Top-1 compression.This allows the proposed methods to operate with larger or much larger stepsizes.
  • Communication efficiency: In all cases, EF21 and EF21+ outperform EF in bits/n and rapidly reach the desired accuracy.Classical GD has the worst convergence rate in these experiments.
  • Communication efficiency: EF21 tolerates larger stepsizes than EF, while EF21+ tolerates much larger stepsizes.The comparison uses individually fine-tuned k values and stepsizes for each method.
  • Additional experiments: Additional experiments cover nonconvex logistic regression, least-squares problems satisfying the PL inequality, and deep learning.These experiments are reported in the appendix.

A.1.1 Experiment 1: Stepsize tolerance (extension)

The extended stepsize experiments vary Top-k sparsity and stepsizes across several datasets. EF21 and EF21+ tolerate substantially larger stepsizes, whereas EF oscillates at large multiples and fails to reach the desired tolerance.

  • Experimental design: The extension varies k by powers of two and tests stepsizes from the largest theoretically accepted value upward by powers of two.This procedure is applied across datasets and methods, with k fixed within each row or comparison.
  • Diagnostic markers: Red diamonds mark iterations where EF21+ uses mostly DCGD steps for at least half of the workers.The marker compares the distortion of the compressor with the distortion of the Markov compressor.
  • Results: EF21 and EF21+ tolerate much larger stepsizes across the extended experiments, improving practical efficiency.The authors connect this tolerance to the methods’ empirical behavior under aggressive stepsize scaling.
  • Results: At large stepsizes of 16×–128×, EF oscillates and convergence to the desired tolerance is hindered.This behavior is reported consistently across the large-stepsize experiments.
  • Experimental design: Figures 3–5 compare EF, EF21, and EF21+ across Top-k values on phishing, mushrooms, and a9a.Rows correspond to k values including {1, 2, 4, 32} or {1, 2, 4, 64}, while labels denote multiples of the theoretically predicted stepsize.

A.1.2 Experiment 2: Fine-tuning 𝑘and the stepsizes (extension)

The extension studies how fine-tuned compression levels affect convergence. The best k values are generally 1, 2, or 4, supporting the communication efficiency of EF21 and EF relative to uncompressed GD.

  • Fine-tuning: For every method, dataset, and k, the stepsize is fine-tuned using results from the preceding experiments.The theoretical stepsize bound from Theorem 1 increases as k increases.
  • Fine-tuning: Figure 7 examines convergence as k varies, with each method, dataset, and k receiving an individually tuned stepsize.The figure uses rows to vary k and labels stepsize multiples relative to the theoretical prediction.
  • Additional comparisons: The appendix also includes a GD-tuning figure and experiments on a PL-condition function using the same datasets as logistic regression.These materials provide additional context for the convergence comparisons.
  • Results: The best k choice is generally 1, 2, or 4, indicating that EF21 and EF are more communication efficient than GD.The conclusion concerns the fine-tuned convergence comparisons in the extension.

A.2.1 Experiment 1: Stepsize tolerance

The experiments test EF, EF21, and EF21+ under increasing stepsizes with Top-k compression and in deep-learning settings. In PL experiments, EF21 and EF21+ tolerate much larger stepsizes than EF, while EF oscillates at very large stepsizes.

  • Stepsize tolerance: The stepsize-tolerance experiments use Top-k compression on phishing, mushrooms, a9a, and w8a datasets.Figures 9–12 compare EF, EF21, and EF21+ while increasing the stepsize relative to the theoretical upper bound.
  • Stepsize tolerance: EF21 and EF21+ tolerate much larger stepsizes than EF in the PL setting.The experiments vary stepsizes as multiples of the largest value predicted by the theory, with k fixed within each row and methods assigned to columns.
  • Stepsize tolerance: At 512×–4096× stepsizes, EF starts oscillating and fails to converge to the desired tolerance.This behavior is reported across the large-stepsize experiments.
  • Deep-learning experiments: Deep-learning experiments compare EF, EF21, EF21+, and SGD using ResNet18 and VGG11 on CIFAR-10.The experiments replace full gradients with minibatch stochastic estimators and run the methods on multiple GPUs.
  • Deep-learning experiments: With tuned stepsizes, EF and EF21-based methods perform similarly during training, with a slight improvement for EF21 and better test accuracy for EF21 across tested settings.The first deep-learning experiment uses k approximately 0.05D, with minibatch sizes 1024 for ResNet18 and 128 for VGG11.
  • Deep-learning experiments: Using smaller k in the Markov compressor makes the method more communication efficient and helps it reach higher test accuracy faster.This experiment fixes minibatch size τ=1024 and stepsize γ=1.6 · 10^-2.

B Proofs for Section 3.1: Distortion of Markov Compressor

The proof develops a recurrence for the Markov compressor’s distortion and unrolls it under a contraction condition. The resulting bound converges to zero as the iteration count grows.

  • Distortion recurrence: The proof introduces a sequence-based distortion analysis for the Markov compressor and defines the inter-iterate change Δ_t.The distortion is analyzed for arbitrary vector sequences in R^d.
  • Distortion recurrence: Choosing s>0 so that 1−θ=(1−α)(1+s)<1 yields a contraction with β=(1−α)(1+s^-1).The parameter choice controls the contraction and additive-error terms in the recurrence.
  • Proof strategy: The proof applies the tower property and then unrolls the resulting distortion recurrence.These steps convert the one-step relation into a bound over iterations.
  • Convergence of distortion: Under Δ_t≤(1−φ)^tΔ_0 for φ>0, the resulting bound converges to zero as t→∞.This is stated in Corollary 1 and the subsequent proof conclusion.

C Four Lemmas Needed in the Proofs of Theorems 1 and 2

The section supplies lemmas that characterize Markov-compressor distortion, optimize its contraction parameters, control smooth objective descent, and simplify the allowable stepsize bound.

  • C.1 Compression distortion bound: Lemma 2 characterizes how Markov-compressor distortion changes between consecutive iterations, decreasing by 1−θ(s) with an additive error.The additive error depends on changes in the communicated gradients; for Top-k, no compressor randomness is present.
  • C.1 Compression distortion bound: The additive error decreases to zero as consecutive gradients become closer during convergence.The text links this behavior to the decrease of ∇f_i(x_t+1)−∇f_i(x_t).
  • C.1 Compression distortion bound: The vanilla biased-compressor bound controls distortion but does not provide a recursion for its iteration-to-iteration evolution.This distinguishes the Markov-compressor analysis from the standard biased-compressor analysis.
  • C.2 Parameter optimization: Lemma 3 minimizes β(s)/θ(s) at s*=1/√(1−α)−1, giving θ(s*)=1−√(1−α).The optimization is valid when θ(s)>0, ensuring contraction.
  • C.3 Smooth descent: For an L-smooth function and update x_t+1=x_t−γg_t, Lemma 4 bounds the function value after one step.Only Lipschitz continuity of the gradient is required for this lemma.
  • C.4 Stepsize simplification: A simplified stepsize γ≤1/√(a+b) satisfies aγ^2+bγ≤1 and is at most a factor of two worse than the optimal bound.This bound is used to avoid writing the exact largest admissible stepsize.

D Proof of Theorem 1

The proof of Theorem 1 combines the distortion recurrence, averaging across workers, smoothness, Jensen’s inequality, and a stepsize condition. Summing the resulting inequalities yields a bound interpreted through a uniformly random iterate.

  • Proof of Theorem 1: The proof substitutes the optimized distortion parameters θ and β into the Markov-compressor recurrence.These parameters come from Lemma 3.
  • Proof of Theorem 1: Averaging the recurrence over all workers and applying the tower property and L-smoothness transfers the distortion control into the distributed objective analysis.The proof proceeds worker-wise before aggregating the inequalities.
  • Proof of Theorem 1: Lemma 4 and Jensen’s inequality provide the function-value bound used in the theorem proof.The resulting inequality is then shifted by f_inf and taken in expectation.
  • Proof of Theorem 1: The stepsize condition θ+Lγ≤1 enables summation of the inequalities over t=0,…,T−1.The condition follows from the simplified stepsize bound in Lemma 5.
  • Proof of Theorem 1: The left-hand side of the summed inequality is interpreted as an expectation over x_0,…,x_T−1 chosen uniformly at random.This gives the theorem’s random-iterate interpretation.

E Proof of Theorem 2

The section develops EF21 with stochastic gradient estimators in the multiple-node setting and outlines the corresponding proof machinery. The stochastic analysis replaces a key lemma in the exact-gradient complexity proofs and uses compressor-noise assumptions to control the resulting terms.

  • Proof of Theorem 2: For PL functions, the proof applies the PL inequality, subtracts f(x⋆), and unrolls the resulting recurrence.The displayed proof fragments identify these as the final steps after establishing the relevant coefficient condition.
  • Stochastic extension: Stochastic EF21 replaces each node’s full gradient ∇f_i(x_t) with a stochastic gradient estimator in Algorithm 5.The modified algorithm is presented for multiple nodes, with the changed components highlighted.
  • Stochastic analysis: The stochastic complexity analysis replaces Lemma 2 in the proofs of both complexity theorems and then accounts for that change.The passage describes this proof modification as straightforward.
  • Technical conditions: Lemma 6 assumes compressor-independent noise with zero mean and bounded variance, providing the technical basis for the stochastic analysis.Assumption 3 elevates the resulting inequality to a compressor condition with constants α̂ and σ̂.
  • Technical conditions: The proof uses Young’s inequality and conditional expectations to bound compressed noisy updates before applying the resulting recurrence.The analysis selects s so that the coefficient (1 − α)(1 + s) remains below one.
Loading 2106.05203v1…