Parallel SGD: When does averaging help?

1 Introduction

• Periodic averaging trades statistical efficiency against hardware efficiency: it can reduce the steps to convergence but makes each step more computationally expensive through communication.The averaging rate can be chosen to optimize wall-clock performance.Source: §1 · p. 1
• The paper asks how frequently independent SGD workers should average and whether more frequent averaging necessarily speeds convergence.It notes that theoretical guarantees for averaging recipes were not available.Source: §1 · p. 2
• Frequent averaging speeds convex convergence when gradient variance is higher far from the optimum, and can yield a smaller noise ball in a simple model.The benefit depends on the gradient-variance envelope.Source: §1 · p. 2
• For non-convex problems, one-shot averaging can produce inaccurate results, while more frequent averaging can avoid this effect.Source: §1 · p. 2
• The multicore experiments on synthetic and real data support the paper’s claims in both convex and non-convex settings.Source: §1 · p. 2

2 Formulation

• For convex components, workers sample component functions uniformly and average their models every K steps to start the next phase.The objective is the mean of m component functions; each phase begins from a common point.Source: §2 · pp. 2–3

2.1 Negative results

• With homogeneous quadratic components sharing a Hessian, linear gradients make periodic averaging equivalent to one-shot averaging, so frequent averaging offers no improvement.This is a case where averaging frequency does not affect the result.Source: §2.1 · p. 3
• Under a uniform gradient-variance bound, earlier averaging steps have no measurable effect, so this conventional model misses benefits of frequent averaging.The analysis also finds the bias term unaffected by averaging frequency for general homogeneous quadratics.Source: §2.1 · p. 3

2.2 Model for Gradient Variance

• The proposed gradient-variance model makes variance depend on distance from the optimum, so early averaging can reduce later variance and speed convergence.The predicted speedup is stronger when the initial distance-related variance term dominates.Source: §2.2 · p. 4

2.3 Stochastic Averaging Analysis

• For a simple quadratic with constant-step SGD and probabilistic averaging, the analysis derives asymptotic variance and shows averaging can yield asymptotic benefits.The expected phase length is the inverse of the averaging probability.Source: §2.3 · p. 4

2.4 Averaging for Non-Convex Problems

• In non-convex problems, workers can converge to different stable points, making one-shot averaging inaccurate even with unbounded gradient samples.The paper examines whether averaging frequency changes this outcome.Source: §2.4 · pp. 4–5
• Objective values were 0.922 with one-shot averaging, 0.274 with averaging 0.1% of the time, and 0.011 with averaging after 10% of steps.The experiment used 24 workers for 10,000 steps on a non-convex objective.Source: §2.4 · p. 5
• In a PCA simulation, principal-component error was evaluated against the number of averaging steps; the reported result identifies one-shot averaging as unsuitable.The experiment used 48 workers, each given 10^4 random samples.Source: §2.4 · p. 5

3 Experiments

• The section evaluates convex regression and logistic regression alongside a CNN on MNIST, using synthetic and canonical datasets.The convex experiments use three least-squares and two logistic-regression datasets; the CNN setup uses four workers with phase length 10.Source: §3 · p. 5, §3.1 · p. 5, §3.2 · p. 7

3.1 Convex Problems

• Experiments use 24 workers and compare one-shot averaging with periodic averaging every 128 or 1024 steps, alongside single-worker results.SGD uses a decaying step size; the objective is normalized to 1 initially and 0 at the optimum.Source: §3.1 · p. 6
• Sparse E2006-tfidf and E2006-log1p show larger periodic-versus-one-shot gaps than dense YearPrediction, consistent with their higher measured ρ.The gap is smaller for logistic regression on both sparse and dense data; overall speedup correlates with measured ρ.Source: Figure 2 · p. 6, §3.1 · p. 7

3.2 Non-convex Problems

• Periodic averaging speeds convergence over one-shot averaging on MNIST and can outperform the best single worker, while one-shot averaging can be worse than the worst worker.The authors attribute one-shot's poor outcome to averaging estimates from different local minima, and periodic averaging's advantage over the best worker to variance reduction.Source: §3.2 · pp. 7–8, Figure 3 · p. 8

• For convex objectives, a proposed gradient-variance model gives intuition for periodic averaging's empirical benefits on least-squares and logistic regression.The paper reports that the variance envelope matters: frequent averaging helps when variance is higher far from the optimum.Source: §4 · p. 8
• For non-convex objectives, one-shot averaging can combine estimates from different local minima, whereas periodic averaging tends to bring workers into a common basin.The paper observes that this can lead to improved solution quality.Source: §4 · p. 8
• Periodic averaging usually outperforms the best worker through its variance-reduction properties.Source: §4 · p. 8

• The proof assumes independent zero-mean noise terms with specified variances and initializes the workers so the iterates have zero expectation.The model runs the update independently in M threads.Source: A Proof of lemma 1 · p. 10
• The derivation uses the update dynamics without averaging, then incorporates an averaging event chosen with probability ζ to obtain an expected system evolution.It seeks the asymptotic value of Q_t by solving a linear equation.Source: A Proof of lemma 1 · pp. 11–12
• The resulting linear system is expressed in matrix form and used to prove the stated result for the chosen assignment of parameters.Source: A Proof of lemma 1 · pp. 12–13