Documentation

Averaging.OpportunisticSecondMoment

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):

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 #

theorem Averaging.Opportunistic.expList_succ_last {α : Type u_1} [Fintype α] (t : ℕ) (F : List α → ℝ) :
Dynamics.expList α (t + 1) F = Dynamics.expList α t fun (l : List α) => Dynamics.avg fun (a : α) => F (l ++ [a])

The last draw of t + 1 i.i.d. uniform draws, averaged first.

theorem Averaging.Opportunistic.rec_le {a : ℕ → ℝ} {q c : ℝ} (hq : 0 ≤ q) (T : ℕ) (h : ∀ t < T, a (t + 1) ≤ q * a t + c) :
a T ≤ q ^ T * a 0 + c * ∑ j ∈ Finset.range T, q ^ j

Unrolling a (t + 1) ≤ q a t + c.

theorem Averaging.Opportunistic.geom_le {q : ℝ} (hq0 : 0 ≤ q) (hq1 : q < 1) (T : ℕ) :
∑ j ∈ Finset.range T, q ^ j ≤ 1 / (1 - q)

Geometric sums: ∑_{j < T} qʲ ≤ 1/(1 - q) for 0 ≤ q < 1.

theorem Averaging.Opportunistic.avgRun_append_singleton {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} (x : V → ℝ) (l : List G.Dart) (e : G.Dart) :
avgRun G x (l ++ [e]) = edgeAvg G (avgRun G x l) e
theorem Averaging.Opportunistic.avgRun_append {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} (x : V → ℝ) (l₁ l₂ : List G.Dart) :
avgRun G x (l₁ ++ l₂) = avgRun G (avgRun G x l₁) l₂
theorem Averaging.Opportunistic.sum_sq_dev_eq {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x x' : V → ℝ) :
∑ v : V, (projCut V₁ x' v + projRest V₁ x' v - projCut V₁ x v) ^ 2 = ↑(Fintype.card V) * (cutCoef V₁ x' - cutCoef V₁ x) ^ 2 + restSq V₁ x'

‖y' + z' - y‖² = n (β' - β)² + ‖z'‖².

theorem Averaging.Opportunistic.IsClusteredRegular.cutCoef_sq_add_restSq_avgRun_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) (l : List G.Dart) :
↑(Fintype.card V) * cutCoef V₁ (avgRun G x l) ^ 2 + restSq V₁ (avgRun G x l) ≤ ↑(Fintype.card V) * cutCoef V₁ x ^ 2 + restSq V₁ x

The squared distance to the consensus never increases along a run.

theorem Averaging.Opportunistic.IsClusteredRegular.expList_restSq_succ_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (x : V → ℝ) (t : ℕ) :
(Dynamics.expList G.Dart (t + 1) fun (l : List G.Dart) => restSq V₁ (avgRun G x l)) ≤ ((1 - lam3 / ↑(Fintype.card V)) * Dynamics.expList G.Dart t fun (l : List G.Dart) => restSq V₁ (avgRun G x l)) + 2 * ↑b / ↑d * Dynamics.expList G.Dart t fun (l : List G.Dart) => cutCoef V₁ (avgRun G x l) ^ 2

The two recursions, in expectation.

theorem Averaging.Opportunistic.IsClusteredRegular.expList_cutDev_succ_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) (γ : ℝ) (t : ℕ) :
(Dynamics.expList G.Dart (t + 1) fun (l : List G.Dart) => ↑(Fintype.card V) * (cutCoef V₁ (avgRun G x l) - γ) ^ 2) ≤ ((1 - 2 * ↑b / ↑d / ↑(Fintype.card V)) * Dynamics.expList G.Dart t fun (l : List G.Dart) => ↑(Fintype.card V) * (cutCoef V₁ (avgRun G x l) - γ) ^ 2) + 2 * ↑b / ↑d * γ ^ 2 + 4 * (2 * ↑b / ↑d) / ↑(Fintype.card V) ^ 2 * ((↑(Fintype.card V) * Dynamics.expList G.Dart t fun (l : List G.Dart) => cutCoef V₁ (avgRun G x l) ^ 2) + Dynamics.expList G.Dart t fun (l : List G.Dart) => restSq V₁ (avgRun G x l))
noncomputable def Averaging.Opportunistic.cutDevBound (N l2 l3 s z : ℝ) (T : ℕ) :

The bound Yb(T) on E ‖y⁽ᵀ⁾ - y‖² (proof of Lemma C.4 and of Theorem 4.1).

Equations
Instances For
    theorem Averaging.Opportunistic.cutDevBound_mono {N l2 l3 s z : ℝ} (hN : 0 < N) (hl2 : 0 ≤ l2) (hl3 : 0 < l3) (hs : 0 ≤ s) (hz : 0 ≤ z) {t T : ℕ} (htT : t ≤ T) :
    cutDevBound N l2 l3 s z t ≤ cutDevBound N l2 l3 s z T
    theorem Averaging.Opportunistic.IsClusteredRegular.expList_secondMoment_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 8 ≤ ↑(Fintype.card V)) (x : V → ℝ) (T : ℕ) :
    (Dynamics.expList G.Dart T fun (l : List G.Dart) => ↑(Fintype.card V) * (cutCoef V₁ (avgRun G x l) - cutCoef V₁ x) ^ 2) ≤ cutDevBound (↑(Fintype.card V)) (2 * ↑b / ↑d) lam3 (↑(Fintype.card V) * cutCoef V₁ x ^ 2) (restSq V₁ x) T ∧ (Dynamics.expList G.Dart T fun (l : List G.Dart) => restSq V₁ (avgRun G x l)) ≤ (1 - lam3 / ↑(Fintype.card V)) ^ T * restSq V₁ x + 2 * ↑b / ↑d / lam3 * (2 * (↑(Fintype.card V) * cutCoef V₁ x ^ 2) + 2 * cutDevBound (↑(Fintype.card V)) (2 * ↑b / ↑d) lam3 (↑(Fintype.card V) * cutCoef V₁ x ^ 2) (restSq V₁ x) T)

    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 #

    theorem Averaging.Opportunistic.IsClusteredRegular.restSq_signVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (σ : V → ℤˣ) :
    restSq V₁ (signVec σ) ≤ ↑(Fintype.card V)
    theorem Averaging.Opportunistic.IsClusteredRegular.card_mul_cutCoef_sq {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) :
    ↑(Fintype.card V) * cutCoef V₁ x ^ 2 = (∑ v : V, cutVec V₁ v * x v) ^ 2 / ↑(Fintype.card V)
    theorem Averaging.Opportunistic.IsClusteredRegular.avg_cutCoef_sq_signVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) :
    (Dynamics.avg fun (σ : V → ℤˣ) => ↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) = 1

    E ‖y⁽⁰⁾‖² = 1 for uniform initial signs.

    theorem Averaging.Opportunistic.IsClusteredRegular.expList_sum_sq_dev_signVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 8 ≤ ↑(Fintype.card V)) (σ : V → ℤˣ) (T : ℕ) :
    (Dynamics.expList G.Dart T fun (l : List G.Dart) => ∑ v : V, (projCut V₁ (avgRun G (signVec σ) l) v + projRest V₁ (avgRun G (signVec σ) l) v - projCut V₁ (signVec σ) v) ^ 2) ≤ (1 + 2 * (2 * ↑b / ↑d / lam3)) * (↑T * (2 * ↑b / ↑d) / ↑(Fintype.card V) * (1 + 8 / ↑(Fintype.card V)) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + 4 * (2 * ↑b / ↑d / lam3) + 4 * (↑T * (2 * ↑b / ↑d) / ↑(Fintype.card V)) * (2 * ↑b / ↑d / lam3)) + ↑(Fintype.card V) * (1 - lam3 / ↑(Fintype.card V)) ^ T + 2 * (2 * ↑b / ↑d / lam3) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2)

    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 Averaging.Opportunistic.log_sixteen_le {x : ℝ} (hx : 16 ≤ x) :
    27 / 10 ≤ Real.log x
    theorem Averaging.Opportunistic.card_mul_pow_le {N l3 : ℝ} {T : ℕ} (hN : 0 < N) (hl3 : 0 < l3) (hq : 0 ≤ 1 - l3 / N) (hT : 3 * N / l3 * Real.log N ≤ ↑T) :
    N * (1 - l3 / N) ^ T ≤ 1 / N ^ 2

    n (1 - λ₃/n)ᵗ ≤ 1/n² once λ₃ t/n ≥ 3 log n.

    theorem Averaging.Opportunistic.IsClusteredRegular.secondMoment_bound_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hc : 100 * (2 * ↑b / ↑d) * Real.log ↑(Fintype.card V) ≤ lam3) (T : ℕ) (hT1 : 3 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) ≤ ↑T) :
    (Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart T fun (l : List G.Dart) => ∑ v : V, (projCut V₁ (avgRun G (signVec σ) l) v + projRest V₁ (avgRun G (signVec σ) l) v - projCut V₁ (signVec σ) v) ^ 2) ≤ 3 * (2 * ↑b / ↑d) * ↑T / ↑(Fintype.card V)

    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).