Lemma 3.9: and the form (13) of
ProvedGeomRescale.lemma_3_9combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
At every stage of Algorithm Rescaling-SFM, for the current . After rescalings, the current matrix is of the form
where and for all .
The analysis of Lemmas 3.10–3.13 rests on this form.
Differences from the source:
- reading: denominator in (13) as printed → denominator ; reason: the proof of Lemma 3.13, display (30), and its trace computation use ; every is nonzero and is free, so the two forms are equivalent
- encoding: throughout the algorithm / at every stage → every state reachable from the initial state, for as in the goal; reason: a run is a relation, so this covers all tie-breaks and argmins; the placeholder of the state before lines 2–3 is included, and the statement holds there too
- encoding: the set → the underlying finite set of a list; reason: a vector found twice is one element, with the sum of its coefficients
- encoding: a ground set with elements →
1 ≤ n; reason: the parameter of Algorithm 2 is undefined at ; the hypothesis excludes only that case - generalization: the run of Algorithm 2 with → the runs for every , with ; reason: gives the paper's run, with rounded as in Theorem 3.6; the statement holds on every such run
- reading: with no case for → at in the step relation; reason: occurs (for at line 2 of Algorithm 1), and the run needs a value there
- reading: in (10) and in line 8 of Algorithm 2, returned after line 15 of Algorithm 1 incremented → , the bases the call computed; reason: line 15 has incremented , so no was computed
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Alg_Setting import Definitions.Def_GeomRescale_fR import Definitions.Def_GeomRescale_enlarge import Definitions.Def_GeomRescale_norm2 import Definitions.Def_GeomRescale_eps import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_Reachable open NonmonotoneSubmod.Shared open SchrijverSFM.Alg open Classical
Formal statement
namespace GeomRescale
/-- Lemma 3.9 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.9 and display (13), p.11): at every stage of Algorithm Rescaling-SFM,
`Γ ⊆ B(f_μ)`, and after `t` rescalings `R = αI_n + ∑_{g ∈ Γ} γ_g ggᵀ/‖g‖₂²`, with
`α = 1/(1 + ε)^{2t}` and `γ_g > 0` for all `g ∈ Γ`.
**Formalization Note.** "At every stage" is every reachable state; `t` is the counter `s.i` of
completed rescalings. The set `Γ` is `s.Γ.toFinset`, and `μ` is the current `s.vn.μ`. The page prints the
denominator of (13) as `‖g‖₂`, but the proof of Lemma 3.13, display (30), and the trace computation after it
use `‖g‖₂²`, which is stated here; since every `g ∈ Γ` is nonzero and `γ_g` is free, the two forms say the
same thing. -/
theorem lemma_3_9 {n : ℕ} (hn : 1 ≤ n) (f : Finset (Fin n) → ℤ) (hsub : Submodular (fR f))
(hf0 : f ∅ = 0) (Λ : ℝ) (hΛ : Ltwo (fR f) ≤ Λ) (s : St n) (hs : Reachable f Λ s) :
(∀ g ∈ s.Γ, g ∈ baseB (enlarge (fR f) (s.vn.μ : ℝ))) ∧
∃ γ : (Fin n → ℝ) → ℝ, (∀ g ∈ s.Γ, 0 < γ g) ∧
s.R = (1 / (1 + eps n) ^ (2 * s.i)) • (1 : Matrix (Fin n) (Fin n) ℝ) +
∑ g ∈ s.Γ.toFinset, (γ g / norm2 g ^ 2) • Matrix.vecMulVec g g := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.9 and display (13), p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.