Lemma 2, p. 7 — online gradient descent without feasibility: regret ≤ ‖x₁ − x‖²/(2Tη) + (η/(2T)) Σ‖f_t‖² against every x ∈ S
ProvedApproxOLO.FullInfo.lemma_2Let be convex and compact, , , and let be arbitrary. Consider plays of online gradient descent without feasibility (Algorithm 1): , and for each the next point is an infeasible projection of onto , i.e.
where for losses and for payoffs. Then for every ,
The points need not lie in ; the classical regret bound of online gradient descent survives with this weaker projection, which is what makes approximate projections usable.
Formalization Note is Euclidean. The infeasible-projection condition is required for , the steps that produce played points ; Algorithm 1 also computes , which is never played, so the statement covers every -round run of Algorithm 1. is the paper's " rounds" with the factor .
import Mathlib import Definitions.Def_ApproxOLO_FullInfo_Model
namespace ApproxOLO.FullInfo
open Matrix
/-- **Lemma 2 (Online gradient descent without feasibility), Garber, arXiv:1709.03093v1, p. 7.**
Let `S ⊂ ℝ^d` be convex and compact, `η > 0`, `T ≥ 1`, and let `x_1 ∈ S`. If the plays
`x_1, …, x_T` of Algorithm 1 satisfy the infeasible-projection condition (3),
`‖z − x_{t+1}‖² ≤ ‖z − y_{t+1}‖²` for all `z ∈ S`, with `y_{t+1} = x_t − η f_t` (losses) resp.
`x_t + η f_t` (payoffs), then for every `x ∈ S`
`(1/T) Σ x_t · f_t − (1/T) Σ x · f_t ≤ (1/(2Tη)) ‖x_1 − x‖² + (η/(2T)) Σ ‖f_t‖²` (losses), and
`(1/T) Σ x · f_t − (1/T) Σ x_t · f_t ≤ (1/(2Tη)) ‖x_1 − x‖² + (η/(2T)) Σ ‖f_t‖²` (payoffs). -/
theorem lemma_2 {d : ℕ} (S : Set (Vec d)) (hS : Convex ℝ S) (hSc : IsCompact S)
(eta : ℝ) (heta : 0 < eta) (T : ℕ) (hT : 1 ≤ T) (xs fs : ℕ → Vec d) (hx1 : xs 1 ∈ S) :
((∀ t, 1 ≤ t → t < T → ∀ z ∈ S,
euclNorm (z - xs (t + 1)) ^ 2 ≤ euclNorm (z - (xs t - eta • fs t)) ^ 2) →
∀ x ∈ S,
(1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, xs t ⬝ᵥ fs t
- (1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, x ⬝ᵥ fs t
≤ 1 / (2 * T * eta) * euclNorm (xs 1 - x) ^ 2
+ eta / (2 * T) * ∑ t ∈ Finset.Icc 1 T, euclNorm (fs t) ^ 2) ∧
((∀ t, 1 ≤ t → t < T → ∀ z ∈ S,
euclNorm (z - xs (t + 1)) ^ 2 ≤ euclNorm (z - (xs t + eta • fs t)) ^ 2) →
∀ x ∈ S,
(1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, x ⬝ᵥ fs t
- (1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, xs t ⬝ᵥ fs t
≤ 1 / (2 * T * eta) * euclNorm (xs 1 - x) ^ 2
+ eta / (2 * T) * ∑ t ∈ Finset.Icc 1 T, euclNorm (fs t) ^ 2) := by sorry
end ApproxOLO.FullInfo
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.