Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (12a) — ϵ^=Rx+Ry\widehat\epsilon=\mathcal R_x+\mathcal R_yϵ=Rx​+Ry​

Proved
DynChoiceJEO.eq_12a

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

choice-modelsconvex-optimizationonline-convex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1saddle-point

For any function Ψ\PsiΨ, any sets X⊆RNX\subseteq\mathbb R^NX⊆RN, Y⊆RkY\subseteq\mathbb R^kY⊆Rk, any sequences xt,yt,ptx_t,y_t,p_txt​,yt​,pt​ and weights θt\theta_tθt​,

ϵ^({xt,yt;pt,θt}t∈[T])=Rx({xt,yt;pt,θt}t∈[T])+Ry({xt,yt;pt,θt}t∈[T]),\widehat\epsilon\big(\{x_t,y_t;p_t,\theta_t\}_{t\in[T]}\big)=\mathcal R_x\big(\{x_t,y_t;p_t,\theta_t\}_{t\in[T]}\big)+\mathcal R_y\big(\{x_t,y_t;p_t,\theta_t\}_{t\in[T]}\big),ϵ({xt​,yt​;pt​,θt​}t∈[T]​)=Rx​({xt​,yt​;pt​,θt​}t∈[T]​)+Ry​({xt​,yt​;pt​,θt​}t∈[T]​),

with Rx,Ry\mathcal R_x,\mathcal R_yRx​,Ry​ from (12b), (12c). The error term of Theorem 1 thus splits into a primal and a dual regret, each controlled by an online convex optimization algorithm.

Differences from the source:

  • encoding: X ⊆ ℝᴺ, Y ⊆ ℝᵏ → X : Set (Fin N → ℝ), Y : Set (Fin k → ℝ); reason: Lean's standard model of Euclidean space; same instances
  • encoding: index set [T] = {1,…,T} → Fin T = {0,…,T−1}; reason: reindexing; same sequences
  • encoding: max / min over Y, X → real sSup / sInf of the image; reason: the identity holds for whatever real values the sSup and sInf take, and they are the paper's max/min whenever these exist
  • generalization: p, p_t in the paper's parameter space (empirical frequency vectors in the application) → an arbitrary type P; reason: no structure of the data space is used; specializes to the paper's parameter space
  • generalization: standing assumptions of §3 (X, Y convex compact; Ψ convex-concave) → not assumed; reason: the identity is algebraic and holds for every Ψ, X, Y and weights; it specializes to the paper's setting
  • encoding: Ψ(x,y;p) on X × Y → a total function Ψ : (Fin N → ℝ) → (Fin k → ℝ) → P → ℝ; reason: a Ψ given on X × Y extends arbitrarily off it, and convexity and concavity are only asked on X and Y; same instances
Preamble
import Mathlib
import Definitions.Def_DynChoiceJEO_epsHat
import Definitions.Def_DynChoiceJEO_Rx
import Definitions.Def_DynChoiceJEO_Ry
Formal statement
namespace DynChoiceJEO

/-- **Eq. (12a): `ε̂ = R_x + R_y`.**
Ho-Nguyen & Kılınç-Karzan, *Dynamic Data-Driven Estimation of Non-Parametric Choice Models*, arXiv:1702.05702v5, eq. (12a), p.13: "ϵ̂({x_t,y_t;p_t,θ_t}_{t∈[T]}) = R_x({x_t,y_t;p_t,θ_t}_{t∈[T]})
+ R_y({x_t,y_t;p_t,θ_t}_{t∈[T]})", with `R_x`, `R_y` from (12b), (12c).

The error term `ε̂` of (11a) splits into the primal regret `R_x` and the dual regret `R_y`.

**Formalization Note** The identity is stated for all `Ψ`, `X`, `Y`, sequences and weights,
without the standing assumptions of §3, which it does not need. `[T]` is `Fin T`. -/
theorem eq_12a {N k T : ℕ} {P : Type*} (Ψ : (Fin N → ℝ) → (Fin k → ℝ) → P → ℝ)
    (X : Set (Fin N → ℝ)) (Y : Set (Fin k → ℝ)) (x : Fin T → Fin N → ℝ)
    (y : Fin T → Fin k → ℝ) (pt : Fin T → P) (θ : Fin T → ℝ) :
    epsHat Ψ X Y x y pt θ = Rx Ψ X x y pt θ + Ry Ψ Y x y pt θ := by sorry

end DynChoiceJEO
Source
Ho-Nguyen & Kılınç-Karzan, Dynamic Data-Driven Estimation of Non-Parametric Choice Models, arXiv:1702.05702v5, eqs. (12a)–(12c), p.13
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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