Theorem 2 — heterogeneous communication characterization
OpenSparseHistComm.Supplement.theorem_2communication-complexitydistributed-estimationhistogram-aggregationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , , , and . There are constants and (depending on these fixed parameters but not on ) such that for every ,
In addition, for every ,
Thus heterogeneous encoders have the exact first-order coefficient furnished by the optimal total covering level, together with the paper's finite-dimensional lower bound.
Differences from the source:
- encoding: for fixed → positive and threshold with an absolute-error bound for every ; reason: this is the standard literal quantifier form of the printed big-O equality
- encoding: real-valued → an infimum, with eventual finiteness stated before conversion to ; reason: nonintegrable or unbounded protocols cannot acquire Lean's junk value zero
- encoding: →
Nat.clog 2 d; reason: this is the exact natural ceiling of the base-two logarithm for
Preamble
import Mathlib import Definitions.Def_SparseHistComm_threshold import Definitions.Def_SparseHistComm_Supplement_Chet open Filter Topology open scoped ENNReal
Formal statement
namespace SparseHistComm
namespace Supplement
/-- **Theorem 2 (Heterogeneous communication characterization)** (Ye–Fan, *Optimal Communication
for Distributed Sparse Histogram Aggregation*, arXiv:2611.04285 (held version, sha256
29df82a4…f27c6f), p.9, (19)–(20)). This includes both the fixed-parameter
`O(log log d)` characterization and the explicit lower bound for every `d ≥ max{2,nk}`.
**Formalization Note** The `O(log log d)` constant may depend on the fixed `n,k,D,δ`, but not on
`d`; it is represented by `C` and `d₀`. Eventual finiteness is stated before `ENNReal.toReal` is
used. All unmarked logarithms are base two, and `Nat.clog 2 d` is `⌈log₂ d⌉`. -/
theorem theorem_2 (n k : ℕ) (D δ : ℝ)
(hn : 1 ≤ n) (hk : 1 ≤ k) (hD0 : 0 ≤ D) (hDk : D < k)
(hδ0 : 0 ≤ δ) (hδ1 : δ < 1) :
(∃ C : ℝ, 0 < C ∧ ∃ d₀ : ℕ, ∀ d ≥ d₀,
Supplement.Chet n k d D δ ≠ ⊤ ∧
|(Supplement.Chet n k d D δ).toReal -
(1 - δ) * (threshold n k D : ℝ) * Real.logb 2 d| ≤
C * Real.logb 2 (Real.logb 2 d)) ∧
∀ d : ℕ, max 2 (n * k) ≤ d →
ENNReal.ofReal ((1 - δ) * (threshold n k D : ℝ) * Real.logb 2 d -
n * k * Real.logb 2 (2 * n * k) - 1 -
n * Real.logb 2 (Real.exp 1 * (k * Nat.clog 2 d + 1))) ≤
Supplement.Chet n k d D δ := by sorry
end Supplement
end SparseHistComm
Source
Ye–Fan, Optimal Communication for Distributed Sparse Histogram Aggregation, arXiv:2611.04285 (held version, sha256 29df82a4…f27c6f), Theorem 2, p.9, (19)–(20); proof pp.16–18