Theorem E.11 — expected transitions of independent-edge minimum cuts
OpenAggCG.Supplement.theorem_E_11algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a finite edge set , fixed finite cut family, and independent distances supported on with densities at most , let minimize with deterministic tie breaking. If , then the number of changes on satisfies
For Gaussian graph weights with independent of density at most , this gives whenever , over all .
Differences from the source:
- encoding: the source takes an expectation of a finite transition count → Lean uses local nonconstancy, cardinality, and a lower Lebesgue integral with measurability asserted; reason: this records the same transitions while preventing infinite or nonmeasurable counts from receiving a default finite value
Preamble
import Mathlib import Definitions.Def_AggCG_Supplement_optimalCut import Definitions.Def_AggCG_Supplement_changePoints import Definitions.Def_AggCG_Supplement_BoundedDensityOn
Formal statement
namespace AggCG.Supplement
open MeasureTheory
/-- **Theorem E.11** (Whole-line expected transition bound for independent exponential edge weights;
Sharma, *Computational Complexity of Data-Driven Configuration for Integer Programming, Clustering, and
Learning Algorithms*, STOC 2027 submission (manuscript sha256 f7ea0248…), p.34, PDF p.35), in the model of
§E.4 (p.33): a finite edge set `E` with `N = |E|`, a fixed finite cut family `𝒞 ⊆ 2^E`, independent edge
distances `D_e` supported on `[a, a + B]` with densities at most `κ`, `W_C(s) = Σ_{e∈C} e^{−s D_e}` and
`C_s ∈ argmin_{C∈𝒞} W_C(s)` with deterministic tie breaking.
(1) The expected number `K` of changes of `C_s` on `s ∈ (0, ∞)` satisfies
`E K ≤ κBN(1 + N log N + N/e)`, and with one absolute constant `C`, `E K ≤ C κ B N² log(N + 1)`.
(2) For Gaussian weights `e^{−d_e²/(2σ²)}` with independent primitive distances `d_e ∈ [1, 2]` of densities
at most `κ_d`, on a graph with `n ≥ 2` vertices and `N ≤ n²` edges, the expected number of changes of the
optimal cut over all bandwidths `σ > 0` is at most `C κ_d n⁴ log n`, with one absolute constant `C`.
**Formalization Note** Expectations are lower Lebesgue integrals of `ℕ∞`-valued counts, with almost-sure
measurability of the count part of the claim. The tie rule depends only on the set of tied cuts. -/
theorem theorem_E_11 :
(∀ (E : Type) [Fintype E] [DecidableEq E] (𝒞 : Finset (Finset E)) (tie : CutTieRule E)
(a B κ : ℝ) (ν : E → Measure ℝ) [∀ e, IsProbabilityMeasure (ν e)],
(∀ e, BoundedDensityOn (ν e) κ a (a + B)) →
AEMeasurable (fun D : E → ℝ => ((changeCount (fun s => optimalCut 𝒞 tie fun e => Real.exp (-(s * D e)))
(Set.Ioi 0) : ℕ∞) : ENNReal)) (Measure.pi ν) ∧
∫⁻ D, ((changeCount (fun s => optimalCut 𝒞 tie fun e => Real.exp (-(s * D e))) (Set.Ioi 0) : ℕ∞) :
ENNReal) ∂(Measure.pi ν) ≤
ENNReal.ofReal (κ * B * Fintype.card E *
(1 + Fintype.card E * Real.log (Fintype.card E) + Fintype.card E / Real.exp 1))) ∧
(∃ C : ℝ, 0 < C ∧ ∀ (E : Type) [Fintype E] [DecidableEq E] (𝒞 : Finset (Finset E))
(tie : CutTieRule E) (a B κ : ℝ) (ν : E → Measure ℝ) [∀ e, IsProbabilityMeasure (ν e)],
(∀ e, BoundedDensityOn (ν e) κ a (a + B)) →
∫⁻ D, ((changeCount (fun s => optimalCut 𝒞 tie fun e => Real.exp (-(s * D e))) (Set.Ioi 0) : ℕ∞) :
ENNReal) ∂(Measure.pi ν) ≤
ENNReal.ofReal (C * κ * B * (Fintype.card E : ℝ) ^ 2 * Real.log (Fintype.card E + 1))) ∧
(∃ C : ℝ, 0 < C ∧ ∀ (n : ℕ), 2 ≤ n → ∀ (E : Type) [Fintype E] [DecidableEq E],
Fintype.card E ≤ n ^ 2 → ∀ (𝒞 : Finset (Finset E)) (tie : CutTieRule E) (κd : ℝ)
(ν : E → Measure ℝ) [∀ e, IsProbabilityMeasure (ν e)], (∀ e, BoundedDensityOn (ν e) κd 1 2) →
∫⁻ d, ((changeCount (fun σ => optimalCut 𝒞 tie fun e => Real.exp (-(d e ^ 2 / (2 * σ ^ 2))))
(Set.Ioi 0) : ℕ∞) : ENNReal) ∂(Measure.pi ν) ≤
ENNReal.ofReal (C * κd * (n : ℝ) ^ 4 * Real.log n)) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem E.11, p.34, PDF p.35