Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (7) — the dual iterates of Algorithm 1 have average regret at most GD/T≤ϵGD/\sqrt T\le\epsilonGD/T​≤ϵ

Proved
OracleRO.DualSubgrad.eq_7

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

online-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regretrobust-optimization

Assume the setting of §3.1: U⊆Rd\mathcal U\subseteq\mathbb R^dU⊆Rd is convex with Euclidean projection operator PPP and ∥u−v∥2≤D\|u-v\|_2\le D∥u−v∥2​≤D for u,v∈Uu,v\in\mathcal Uu,v∈U; for every iii and every x∈Dx\in\mathcal Dx∈D the function fi(x,⋅)f_i(x,\cdot)fi​(x,⋅) is concave on U\mathcal UU and differentiable at every u∈Uu\in\mathcal Uu∈U with ∥∇ufi(x,u)∥2≤G\|\nabla_u f_i(x,u)\|_2\le G∥∇u​fi​(x,u)∥2​≤G; ϵ,D,G>0\epsilon,D,G>0ϵ,D,G>0; ui0∈Uu^0_i\in\mathcal Uui0​∈U for all iii and x0∈Dx^0\in\mathcal Dx0∈D; and Oϵ\mathcal O_\epsilonOϵ​ is an ϵ\epsilonϵ-approximate oracle (Figure 1). Let (ut,xt)(u^t,x^t)(ut,xt) be the iterates of Algorithm 1 with T=⌈G2D2/ϵ2⌉T=\lceil G^2D^2/\epsilon^2\rceilT=⌈G2D2/ϵ2⌉. Then for every i∈[m]i\in[m]i∈[m] and every u∈Uu\in\mathcal Uu∈U,

1T∑t=1Tfi(xt,u)−1T∑t=1Tfi(xt,uit)≤GDT≤ϵ.\frac1T\sum_{t=1}^T f_i(x^t,u)-\frac1T\sum_{t=1}^T f_i(x^t,u^t_i)\le\frac{GD}{\sqrt T}\le\epsilon .T1​t=1∑T​fi​(xt,u)−T1​t=1∑T​fi​(xt,uit​)≤T​GD​≤ϵ.

This is the dual half of the proof of Theorem 3: for each constraint, the dual update is online gradient ascent on the rewards fi(xt,⋅)f_i(x^t,\cdot)fi​(xt,⋅), whose regret guarantee (Lemma 1) holds even though xtx^txt is chosen after utu^tut.

Formalization Note The page writes max⁡ui∈U\max_{u_i\in\mathcal U}maxui​∈U​; the statement is for every u∈Uu\in\mathcal Uu∈U, which is equivalent without assuming attainment. The bound holds for the defined iterates whatever the oracle answers (rounds after an "infeasible" answer use xt=x0∈Dx^t=x^0\in\mathcal Dxt=x0∈D).

Preamble
import Mathlib
import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto
import Definitions.Def_OracleRO_DualSubgrad_Problem
import Definitions.Def_OracleRO_DualSubgrad_Algorithm1
Formal statement
namespace OracleRO.DualSubgrad

/-- Eq. (7), p. 8: in the run of Algorithm 1, for every constraint `i` and every `u ∈ 𝒰`,
`(1/T) ∑_{t=1}^T f_i(x^t, u) - (1/T) ∑_{t=1}^T f_i(x^t, u^t_i) ≤ G D / √T ≤ ε`
(the regret guarantee of online gradient ascent on the rewards `f_i(x^t, ·)`). -/
theorem eq_7
    {m n d : ℕ} (Dom : Set (EuclideanSpace ℝ (Fin n))) (U : Set (EuclideanSpace ℝ (Fin d)))
    (f : Fin m → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin d) → ℝ)
    (gradU : Fin m → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin d) →
      EuclideanSpace ℝ (Fin d))
    (P : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d))
    (O : (Fin m → EuclideanSpace ℝ (Fin d)) → Option (EuclideanSpace ℝ (Fin n)))
    (ε D G : ℝ) (u0 : Fin m → EuclideanSpace ℝ (Fin d)) (x0 : EuclideanSpace ℝ (Fin n))
    (hU : Convex ℝ U) (hP : SpectralProjGrad.Shared.IsProjOnto U P)
    (hconc : ∀ i, ∀ x ∈ Dom, ConcaveOn ℝ U (f i x))
    (hgrad : ∀ i, ∀ x ∈ Dom, ∀ u ∈ U, HasGradientAt (f i x) (gradU i x u) u)
    (hgradG : ∀ i, ∀ x ∈ Dom, ∀ u ∈ U, ‖gradU i x u‖ ≤ G)
    (hdiam : ∀ u ∈ U, ∀ v ∈ U, ‖u - v‖ ≤ D)
    (hε : 0 < ε) (hD : 0 < D) (hG : 0 < G)
    (hu0 : ∀ i, u0 i ∈ U) (hx0 : x0 ∈ Dom)
    (hO : IsApproxOracle Dom U f ε O) :
    ∀ i, ∀ u ∈ U,
      (1 / (alg1T G D ε : ℝ)) * ∑ t ∈ Finset.Icc 1 (alg1T G D ε),
          f i (alg1X gradU P O G D ε u0 x0 t) u
        - (1 / (alg1T G D ε : ℝ)) * ∑ t ∈ Finset.Icc 1 (alg1T G D ε),
          f i (alg1X gradU P O G D ε u0 x0 t) (alg1U gradU P O G D ε u0 x0 t i)
        ≤ G * D / Real.sqrt (alg1T G D ε) ∧
      G * D / Real.sqrt (alg1T G D ε) ≤ ε := by sorry

end OracleRO.DualSubgrad
Source
Ben-Tal, Hazan, Koren, Mannor, Oracle-Based Robust Optimization via Online Learning, arXiv:1402.6361v1, p. 8, proof of Theorem 3, (7)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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