Eq. (7) — the dual iterates of Algorithm 1 have average regret at most
ProvedOracleRO.DualSubgrad.eq_7Assume the setting of §3.1: is convex with Euclidean projection operator and for ; for every and every the function is concave on and differentiable at every with ; ; for all and ; and is an -approximate oracle (Figure 1). Let be the iterates of Algorithm 1 with . Then for every and every ,
This is the dual half of the proof of Theorem 3: for each constraint, the dual update is online gradient ascent on the rewards , whose regret guarantee (Lemma 1) holds even though is chosen after .
Formalization Note The page writes ; the statement is for every , which is equivalent without assuming attainment. The bound holds for the defined iterates whatever the oracle answers (rounds after an "infeasible" answer use ).
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_OracleRO_DualSubgrad_Problem import Definitions.Def_OracleRO_DualSubgrad_Algorithm1
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.