Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4, p. 20 — if C(I_t) ⊆ E(W_t, U_t) and the test (12) holds, the period's regret is at most ε

Proved
CtxInvOpt.Pointed.lemma4_low_regret_period

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

ellipsoidal-coneinverse-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Let d=m+1d=m+1d=m+1, ϵ>0\epsilon>0ϵ>0, let C0⊆SdC_0\subseteq S^dC0​⊆Sd and c⋆∈C0c^\star\in C_0c⋆∈C0​, and let the expert actions xs⋆∈ψ(c⋆,Xs,fs)x^\star_s\in\psi(c^\star,\mathcal X_s,f_s)xs⋆​∈ψ(c⋆,Xs​,fs​) be optimal for c⋆c^\starc⋆. Fix a period ttt with Xt∈B\mathcal X_t\in\mathfrak BXt​∈B and ft∈Ff_t\in\mathfrak Fft​∈F, a positive definite diagonal WtW_tWt​ and an orthonormal UtU_tUt​ such that

C(It)⊆E(Wt,Ut).C(\mathcal I_t)\subseteq E(W_t,U_t).C(It​)⊆E(Wt​,Ut​).

Let the policy play xtπ∈ψ(Ute1,Xt,ft)x^\pi_t\in\psi(U_te_1,\mathcal X_t,f_t)xtπ​∈ψ(Ut​e1​,Xt​,ft​), let δtπ\delta^\pi_tδtπ​ be the effective difference and δˉ=Ut−1δtπ\bar\delta=U_t^{-1}\delta^\pi_tδˉ=Ut−1​δtπ​. If (12) holds, δˉ[2:d]′Wtδˉ[2:d]≤ϵ2\bar\delta_{[2:d]}'W_t\bar\delta_{[2:d]}\le\epsilon^2δˉ[2:d]′​Wt​δˉ[2:d]​≤ϵ2, then the one-period regret is at most ϵ\epsilonϵ:

(ft(xtπ)−ft(xt⋆))′c⋆≤ϵ.\big(f_t(x^\pi_t)-f_t(x^\star_t)\big)'c^\star\le\epsilon.(ft​(xtπ​)−ft​(xt⋆​))′c⋆≤ϵ.

Periods that pass the test are therefore cheap, and EllipsoidalCones does not spend a cone update on them.

Formalization Note Lean period ttt is the paper's t+1t+1t+1, and knowledgeSet C0 X f xstar t is the paper's C(It+1)C(\mathcal I_{t+1})C(It+1​). The paper's parameter ϵ>0\epsilon>0ϵ>0 is a hypothesis (for ϵ<0\epsilon<0ϵ<0 the test can hold while the regret is 0>ϵ0>\epsilon0>ϵ).

Preamble
import Mathlib
import Definitions.Def_CtxInvOpt_Greedy_Online
import Definitions.Def_CtxInvOpt_Pointed_EllCone
Formal statement
namespace CtxInvOpt.Pointed

open Matrix

/-- **Lemma 4, p. 20.** Let `C(I_t) ⊆ E(W_t, U_t)` (Lean period `t`, the paper's `t + 1`), where the
knowledge set is built from `C₀ ⊆ S^d` and expert actions optimal for `c⋆ ∈ C₀`. If the policy plays
`x^π_t ∈ ψ(U_t e₁, X_t, f_t)` and the test (12) `δ̄′_{[2:d]} W_t δ̄_{[2:d]} ≤ ε²` holds for
`δ̄ = U_t⁻¹δ^π_t`, then the one-period regret `(f_t(x^π_t) − f_t(x⋆_t))′c⋆` is at most `ε`. -/
theorem lemma4_low_regret_period {n m : ℕ} {ε : ℝ} (hε : 0 < ε)
    (C0 : Set (EuclideanSpace ℝ (Fin (m + 1)))) (hC0 : C0 ⊆ CtxInvOpt.Offline.unitSphere (m + 1))
    (cstar : EuclideanSpace ℝ (Fin (m + 1))) (hcstar : cstar ∈ C0)
    (X : ℕ → Set (EuclideanSpace ℝ (Fin n)))
    (f : ℕ → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin (m + 1)))
    (xstar : ℕ → EuclideanSpace ℝ (Fin n))
    (hxstar : ∀ s, xstar s ∈ CtxInvOpt.Offline.argminSet cstar (X s) (f s))
    (t : ℕ) (hX : CtxInvOpt.Offline.IsActionSet (X t)) (hf : CtxInvOpt.Offline.IsContext (f t))
    (w : Fin m → ℝ) (hw : ∀ i, 0 < w i)
    (U : Matrix (Fin (m + 1)) (Fin (m + 1)) ℝ) (hU : U ∈ Matrix.orthogonalGroup (Fin (m + 1)) ℝ)
    (hK : CtxInvOpt.Greedy.knowledgeSet C0 X f xstar t ⊆ ellCone w U)
    (xpi : EuclideanSpace ℝ (Fin n)) (hxpi : xpi ∈ CtxInvOpt.Offline.argminSet (axisVec U) (X t) (f t))
    (h12 : tailQuad w (rotCoord U (effDiff (f t xpi - f t (xstar t)))) ≤ ε ^ 2) :
    inner ℝ (f t xpi - f t (xstar t)) cstar ≤ ε := by sorry

end CtxInvOpt.Pointed
Source
Besbes, Fonseca, Lobel, Contextual Inverse Optimization: Offline and Online Learning, arXiv:2106.14015v3, p. 20, Lemma 4; proof App-12–App-13
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me