Theorem 1, p. 14 — Algorithm 3 has expected α-regret at most α²R²/(Tη) + ηF²/2 + 3Fε
ProvedApproxOLO.FullInfo.theorem_1There is a universal constant (the constant of Lemma 5, fixing the number of Ellipsoid iterations in every call of Algorithm 2) such that the following holds. Let , let , be an instance of online linear optimization, an -approximation oracle for some , , , , and let be loss/payoff vectors fixed in advance (oblivious adversary). Run Algorithm 3 (online gradient descent with infeasible projections onto ) for rounds, and let be the points it plays. Then
This holds in both regimes: (losses, regret against times the best fixed point of ) and (payoffs). With and tuned in it gives vanishing expected -regret using only the approximation oracle.
Formalization Note The expected -regret is Eq. (1) evaluated at the expected per-round losses/payoffs : in round 1 and for , with the distribution and points returned by the call of round . This equals the expectation of (1) by linearity, because the iterates and the distributions never depend on the sampled points and the losses are fixed in advance; no probability space is built. A run of Algorithm 3 is a run predicate: is arbitrary and every call of rounds is a complete run of Algorithm 2 (the call of round only produces ). Added hypotheses: (the central-cut update), (the factor ). The oracle-complexity bound and the two "In particular" settings of the theorem are not stated: they are bounds with hidden constants. is Euclidean.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_ApproxOLO_FullInfo_Model
namespace ApproxOLO.FullInfo
open Matrix
/-- **Theorem 1 (Main Theorem), Garber, arXiv:1709.03093v1, p. 14 (regret bound).** There is a
universal constant `c > 0` (the constant of Lemma 5 fixing the Ellipsoid iterations in every
call of Algorithm 2) such that for every `d ≥ 2`, instance, `α > 0`, oracle, `η > 0`,
`ε ∈ (0, (α + 2)R]`, `T ≥ 1` and loss/payoff vectors `f_1, …, f_T ∈ F`, every run of
Algorithm 3 satisfies `E[α-regret({(s_t, f_t)}_{t∈[T]})] ≤ α²R²/(Tη) + ηF²/2 + 3Fε`,
where the expected `α`-regret is (1) evaluated at the expected per-round losses/payoffs
`E[s_t · f_t]`. -/
theorem theorem_1 : ∃ c : ℝ, 0 < c ∧ ∀ (d : ℕ), 2 ≤ d →
∀ (K Fs : Set (Vec d)) (R Fb C alpha eta eps : ℝ) (O : Vec d → Vec d) (T : ℕ)
(fs : ℕ → Vec d) (s1 : Vec d) (outs : ℕ → Alg2Out d),
IsInstance K Fs R Fb C → 0 < alpha → IsApproxOracle K alpha O →
0 < eta → 0 < eps → eps ≤ (alpha + 2) * R → 1 ≤ T →
(∀ t ∈ Finset.Icc 1 T, fs t ∈ Fs) →
IsAlg3Run c K O alpha R eta eps T fs s1 outs →
regretOf K alpha T fs (alg3ExpLoss s1 outs fs)
≤ alpha ^ 2 * R ^ 2 / (T * eta) + eta * Fb ^ 2 / 2 + 3 * Fb * eps := by sorry
end ApproxOLO.FullInfo
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.