Operation count of a call and of a rescaling
ProvedGeomRescale.operation_countcombinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
There is an absolute constant such that for every and every integer valued submodular with :
- a call of Algorithm 1 with , on any valid input, adds at most to the evaluations of and at most to the arithmetic operations, the final test of line 4 included;
- lines 6–8 of Algorithm 2 evaluate zero times and add at most operations.
This is the count per call and the count per rescaling in the paper.
Differences from the source:
- reading: time counted by line in notation → the counters
evals,opswith the charge table; reason: the paper gives no machine; each charge is at least the cost of the straightforward unit-cost real-arithmetic implementation, up to an absolute factor - generalization: , → one absolute constant before and ; reason: this is the with its quantifiers written out; it also separates the two counters
- 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_eps import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_vnStart import Definitions.Def_GeomRescale_VNStep import Definitions.Def_GeomRescale_Reachable open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- The operation count of the proof of Theorem 3.6 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, proof of Theorem 3.6, p.12), with one
absolute constant `C₁`: a call of Algorithm 1 with `ε = 1/(20n)` increases `evals` by at most `C₁n³`
and `ops` by at most `C₁n⁴`, and lines 6–8 of Algorithm 2 increase `ops` by at most `C₁n⁴` and do not
evaluate `f`.
**Formalization Note.** `C₁` comes before `n`, `f`. The term `n²` in the first clause is the charge of
the final test of line 4, which `Step.exit` adds to `ops`. "Time" is the pair of counters of the charge
table in the docstrings of `vnStart`, `VNStep`, `vnUpdate` and `Step`. -/
theorem operation_count :
∃ C₁ : ℝ, 0 < C₁ ∧ ∀ (n : ℕ), 1 ≤ n → ∀ (f : Finset (Fin n) → ℤ), Submodular (fR f) →
f ∅ = 0 →
(∀ (μ : ℤ) (W : Finset (Fin n)) (Q : Matrix (Fin n) (Fin n) ℝ) (σ : Equiv.Perm (Fin n))
(e o : ℕ) (v : VN n), max 0 (-f Finset.univ) ≤ μ → f W = -μ → Q.PosDef →
Relation.ReflTransGen (VNStep f Q (eps n)) (vnStart f μ W Q σ e o) v →
(v.evals : ℝ) ≤ e + C₁ * (n : ℝ) ^ 3 ∧
(v.ops : ℝ) + (n : ℝ) ^ 2 ≤ o + C₁ * (n : ℝ) ^ 4) ∧
(∀ (Λ : ℝ), Ltwo (fR f) ≤ Λ → ∀ s s' : St n, Reachable f Λ s →
s.mode = Mode.afterCall → Step f Λ s s' →
s'.vn.evals = s.vn.evals ∧ (s'.vn.ops : ℝ) ≤ s.vn.ops + C₁ * (n : ℝ) ^ 4) := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, proof of Theorem 3.6, p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.