Theorem 1 — bounds on
OpenSparseHistComm.Supplement.theorem_1communication-complexitydistributed-estimationhistogram-aggregationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every , , , and ,
Moreover, there is a universal constant such that, whenever and ,
These estimates bound the leading homogeneous communication coefficient by deterministic covering and by a concentrated randomized covering law.
Differences from the source:
- encoding: the universal in (15) → one positive constant quantified before all parameters; reason: p.14 states that the implied constant is universal, and this is its literal quantifier form
- encoding: → the published integer-valued
threshold, coerced to in analytic expressions; reason: this preserves the real floor of the product exactly
Preamble
import Mathlib import Definitions.Def_SparseHistComm_Lambda import Definitions.Def_SparseHistComm_threshold
Formal statement
namespace SparseHistComm
namespace Supplement
/-- **Theorem 1 (Bounds on the homogeneous coefficient)** (Ye–Fan, *Optimal Communication for
Distributed Sparse Histogram Aggregation*, arXiv:2611.04285 (held version, sha256
29df82a4…f27c6f), pp.7–8, (14)–(15)). The constant in (15) is universal, as the explicit
estimate on p.14 shows.
**Formalization Note** `threshold n k D = nk - ⌊nD⌋` is integer-valued and is coerced to `ℝ`
in the displayed bounds. `Real.log` is the paper's natural logarithm in (15). -/
theorem theorem_1 :
∃ C : ℝ, 0 < C ∧ ∀ (n k : ℕ) (D δ : ℝ),
1 ≤ n → 1 ≤ k → 0 ≤ D → D < k → 0 ≤ δ → δ < 1 →
(1 - δ) * (threshold n k D : ℝ) ≤ Lambda n k D δ ∧
Lambda n k D δ ≤ (1 - δ) * n * (k - ⌊D⌋) ∧
(0 < δ → max 2 (1 / δ) ≤ (threshold n k D : ℝ) →
Lambda n k D δ ≤ (1 - δ) * (threshold n k D : ℝ) *
(1 + C * Real.sqrt (Real.log (threshold n k D : ℝ) /
(threshold n k 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 1, pp.7–8, (14)–(15); explicit universal bound, p.14