Lemma 3.13 (corrected: ): a base of small -norm
ProvedGeomRescale.lemma_3_13combinatorial-optimizationp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
At any stage of Algorithm Rescaling-SFM with , there exists a point such that
Combined with Lemmas 3.11 and 3.12, this forces below the bound of Lemma 3.8 after rescalings.
Differences from the source:
- correction: at any stage → at any stage with ; reason: at line 1 of Algorithm 2 for every , so no exists; the proof's argmin over and the use in Theorem 3.6 need
- 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: 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_GeomRescale_fR import Definitions.Def_GeomRescale_norm2 import Definitions.Def_GeomRescale_qnorm import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_Reachable open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Lemma 3.13, corrected (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.13, p.12, proof p.32): at any stage of Algorithm
Rescaling-SFM with `Γ ≠ ∅`, there exists a point `ḡ ∈ Γ` such that
`‖ḡ‖_Q √(det(R)^{1/n} − 1) ≤ ‖ḡ‖₂`.
**Formalization Note.** The page says "at any stage", but `Γ = ∅` until the first rescaling, so no
`ḡ` exists there. The appendix proof takes an argmin over `Γ`, and the proof of Theorem 3.6 applies
the lemma after `T ≥ 1` rescalings. `det(R) ≥ 1` along a run, so the square root is of a nonnegative
number. -/
theorem lemma_3_13 {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)
(hΓ : s.Γ ≠ []) :
∃ g ∈ s.Γ, qnorm s.Q g * √(s.R.det ^ (1 / (n : ℝ)) - 1) ≤ norm2 g := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.13, p.12, proof p.32
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.