Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1, p. 11 — the worst-case regret of proxy cost c^π against c⋆ is sin θ(c⋆, c^π), or 1 when θ ≥ π/2

Proved
CtxInvOpt.Offline.lemma1_realized_worst_case_regret

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

inverse-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proxy-policyworst-case-regret

Let n≥1n\ge1n≥1 and d≥2d\ge2d≥2. Fix a proxy cost cπ∈Sdc^\pi\in S^dcπ∈Sd and a true cost c⋆∈Sdc^\star\in S^dc⋆∈Sd. Consider all instances consisting of an action set X∈B\mathcal X\in\mathcal BX∈B (nonempty, compact, diameter at most 111), a 111-Lipschitz context function f:Rn→Rdf:\mathbb R^n\to\mathbb R^df:Rn→Rd, an action xπ∈ψ(cπ,X,f)x^\pi\in\psi(c^\pi,\mathcal X,f)xπ∈ψ(cπ,X,f) chosen by the proxy policy (any minimizer, so ties are broken adversarially), and an optimal action x⋆∈ψ(c⋆,X,f)x^\star\in\psi(c^\star,\mathcal X,f)x⋆∈ψ(c⋆,X,f). The worst-case regret

L(cπ,c⋆)=sup⁡xπ∈ψ(cπ,X,f), X∈B, f∈F(f(xπ)−f(x⋆))′c⋆\mathcal L(c^\pi,c^\star)=\sup_{x^\pi\in\psi(c^\pi,\mathcal X,f),\ \mathcal X\in\mathcal B,\ f\in\mathcal F}\big(f(x^\pi)-f(x^\star)\big)'c^\starL(cπ,c⋆)=xπ∈ψ(cπ,X,f), X∈B, f∈Fsup​(f(xπ)−f(x⋆))′c⋆

is attained and equals

L(cπ,c⋆)={sin⁡θ(c⋆,cπ)if θ(c⋆,cπ)<π/2,1otherwise.\mathcal L(c^\pi,c^\star)=\begin{cases}\sin\theta(c^\star,c^\pi)&\text{if }\theta(c^\star,c^\pi)<\pi/2,\\ 1&\text{otherwise.}\end{cases}L(cπ,c⋆)={sinθ(c⋆,cπ)1​if θ(c⋆,cπ)<π/2,otherwise.​

The lemma converts a policy that acts as if the cost were cπc^\picπ into a purely geometric quantity: its worst-case loss depends only on the angle between cπc^\picπ and the true cost. It is the basis of the upper bound in Theorem 1.

Formalization Note The supremum is stated with IsGreatest: the value is a regret of some admissible instance, and it bounds the regret of every admissible instance. The proxy policy is represented by its cost vector cπc^\picπ (as on p. 10 of the paper). The hypothesis n≥1n\ge1n≥1 is not written in the paper but is needed: in R0\mathbb R^0R0 every regret is 000. The hypothesis d≥2d\ge2d≥2 is the paper's standing assumption of §2.

Preamble
import Mathlib
import Definitions.Def_CtxInvOpt_Offline_Geometry
Formal statement
namespace CtxInvOpt.Offline

/-- **Lemma 1 (Realized worst-case regret), arXiv:2106.14015v3, p. 11.** For a proxy cost
`c^π ∈ S^d` and a true cost `c⋆ ∈ S^d`, the worst-case regret (8)
`L(c^π, c⋆) = sup_{x^π ∈ ψ(c^π, X, f), X ∈ 𝔅, f ∈ 𝔉} (f(x^π) − f(x⋆))′c⋆`
equals `sin θ(c⋆, c^π)` if `θ(c⋆, c^π) < π/2` and `1` otherwise; the supremum is attained. -/
theorem lemma1_realized_worst_case_regret {n d : ℕ} (hn : 1 ≤ n) (hd : 2 ≤ d)
    (cpi cstar : EuclideanSpace ℝ (Fin d)) (hcpi : cpi ∈ unitSphere d)
    (hcstar : cstar ∈ unitSphere d) :
    IsGreatest
      {r : ℝ | ∃ (X : Set (EuclideanSpace ℝ (Fin n)))
          (f : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin d))
          (xpi xstar : EuclideanSpace ℝ (Fin n)),
          IsActionSet X ∧ IsContext f ∧ xpi ∈ argminSet cpi X f ∧
          xstar ∈ argminSet cstar X f ∧ r = inner ℝ (f xpi - f xstar) cstar}
      (regretCap (vecAngle cstar cpi)) := by sorry

end CtxInvOpt.Offline
Source
Besbes, Fonseca, Lobel, Contextual Inverse Optimization: Offline and Online Learning, arXiv:2106.14015v3, p. 11, Lemma 1 (with (8), p. 10); proof App-3–App-5
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