Lemma 12 — LP dual of the signed correction
ProvedMomentSearch.lemma_12distributionally-robust-optimizationlinear-programming-dualitylower-boundsmomentsp2o-gran-per-chapterp2o-plan-paperp2o-v1search
Let and . For all ,
Moreover, the infimum defining is attained: some solution of the correction system has .
The lemma turns the bound on the correction value into a bound on increments of polynomials that are bounded by on the grid.
Differences from the source:
- encoding: γ* equals the maximum of the set of increments → γ* is the greatest element of that set (IsGreatest); reason: same meaning: the maximum exists and equals γ*
- encoding: deg q ≤ k → q.natDegree ≤ k; reason: Lean convention; both admit the zero polynomial
Preamble
import Mathlib import Definitions.Def_MomentSearch_correctionNorm
Formal statement
namespace MomentSearch
/-- **Lemma 12** (dual of the signed correction), Megow, Stein, Verschae, *Distributionally Robust Search: The Power of Information and the Limits of Moments*, arXiv:2611.04559 (held version, sha256 fbfa4b43…), §4.1, p.11 (PDF p.13); restated
App. C.1, p.22 (PDF p.24).
For all `m, m₀ ∈ [n]₀`,
`γ*(m, m₀) = max { q(τ_m) − q(τ_{m₀}) : q a polynomial with deg q ≤ k and |q(τ_t)| ≤ 1 for all t ∈ [n]₀ }`.
Moreover, the infimum in Equation (4) is attained.
**Formalization Note.** "max" is `IsGreatest`: `γ*` belongs to the set of increments and bounds
it above. "deg q ≤ k" is `q.natDegree ≤ k`, which admits the zero polynomial. Attainment is an
`a` solving (7) with `‖a‖₁ = γ*`. `n ≥ 2` is the standing assumption (§2.1). -/
theorem lemma_12 {n : ℕ} (hn : 2 ≤ n) (k : ℕ) (m m₀ : Fin n) :
IsGreatest
{y : ℝ | ∃ q : Polynomial ℝ, q.natDegree ≤ k ∧
(∀ t : Fin n, |q.eval (grid n (t : ℕ))| ≤ 1) ∧
y = q.eval (grid n (m : ℕ)) - q.eval (grid n (m₀ : ℕ))}
(correctionNorm n k m m₀) ∧
∃ a : Fin n → ℝ, SolvesCorrection n k m m₀ a ∧
∑ t : Fin n, |a t| = correctionNorm n k m m₀ := by sorry
end MomentSearch
Source
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43…), §4.1, Lemma 12, p.11 (PDF p.13); restated App. C.1, p.22 (PDF p.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.