Second moment analysis (Lemma C.4 and Theorem 4.1) #
Unrolling the one-round bounds of Averaging.OpportunisticOneStep over T i.i.d. uniform rounds
from an arbitrary state x (with s = n β² = ‖y‖², ‖z‖² = restSq, M = s + ‖z‖²,
λ₂ = 2b/d, q = 1 - λ₃/n):
expList_cutDev_le:E ‖y⁽ᵀ⁾ - y‖² ≤ Yb(T)withYb(T) = T (λ₂/n)(1 + 8/n) s + (4λ₂/(n λ₃)) ‖z‖² + 4 T λ₂² M/(n² λ₃);expList_restSq_le:E ‖z⁽ᵀ⁾‖² ≤ qᵀ ‖z‖² + (λ₂/λ₃)(2 s + 2 Yb(T)).
Together they bound E‖y⁽ᵀ⁾ + z⁽ᵀ⁾ - y‖² = E‖y⁽ᵀ⁾ - y‖² + E‖z⁽ᵀ⁾‖² (sum_sq_dev_eq), which gives
Theorem 4.1 after averaging over the initial signs (E ‖y⁽⁰⁾‖² = 1).
Generic recursions #
The last draw of t + 1 i.i.d. uniform draws, averaged first.
‖y' + z' - y‖² = n (β' - β)² + ‖z'‖².
The squared distance to the consensus never increases along a run.
The two recursions, in expectation.
The bound Yb(T) on E ‖y⁽ᵀ⁾ - y‖² (proof of Lemma C.4 and of Theorem 4.1).
Equations
Instances For
Second moment bounds from an arbitrary state (Lemmas C.2 to C.4 unrolled): with
s = n β², z = ‖z‖² the components of the start x,
E ‖y⁽ᵀ⁾ - y‖² ≤ Yb(T) and E ‖z⁽ᵀ⁾‖² ≤ (1 - λ₃/n)ᵀ z + (λ₂/λ₃)(2 s + 2 Yb(T)).
Starting from uniform random signs #
E ‖y⁽⁰⁾‖² = 1 for uniform initial signs.
Second moment from uniform signs, for fixed signs (the bound behind Theorem 4.1): with
s₀ = ‖y⁽⁰⁾‖², r = λ₂/λ₃ and L = λ₂ T/n,
E ‖y⁽ᵀ⁾ + z⁽ᵀ⁾ - y⁽⁰⁾‖² ≤ (1 + 2r)(L (1 + 8/n) s₀ + 4r + 4 L r) + n (1 - λ₃/n)ᵀ + 2 r s₀.
Theorem 4.1 #
Theorem 4.1 with the constant c = 100: if 100 λ₂ log n ≤ λ₃ and
T ≥ 3 (n/λ₃) log n, then E ‖y⁽ᵀ⁾ + z⁽ᵀ⁾ - y⁽⁰⁾‖² ≤ 3 λ₂ T/n (the upper bound T ≤ n/(4λ₂) of
the paper is not needed).