App. A, pp. 14–15 — max((nd/16) tanh(ηd/8), min(d log 2/(12η), nd/12)) ≥ min(0.04 nd, 0.01 d^{3/2}√n)
ProvedOnlineCombOpt.Exp2LB.appA_eta_optimizationexponential-weightsinequalitylower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For all integers and every learning rate ,
This is the optimization over the learning rate in the proof of Theorem 1: whatever is, one of the two adversaries of App. A forces a regret of at least , which equals when .
Formalization Note The paper takes the minimum over , reading as at ; here the chain is stated pointwise for each , because Lean reads as . The constants and are the reals and , and .
Preamble
import Mathlib import Definitions.Def_OnlineCombOpt_Exp2LB_Setting open Finset
Formal statement
namespace OnlineCombOpt.Exp2LB
/-- App. A, pp. 14–15 (Audibert, Bubeck, Lugosi, arXiv:1204.4710v2), the optimization over the
learning rate, pointwise in `η > 0`:
`max((nd/16) tanh(ηd/8), min(d log 2/(12η), nd/12)) ≥ min(0.04 nd, 0.01 d^{3/2} √n)`. -/
theorem appA_eta_optimization (n d : ℕ) (η : ℝ) (hη : 0 < η) :
min ((4 : ℝ) / 100 * n * d) ((1 : ℝ) / 100 * d * Real.sqrt d * Real.sqrt n) ≤
max ((n : ℝ) * d / 16 * Real.tanh (η * d / 8))
(min ((d : ℝ) * Real.log 2 / (12 * η)) ((n : ℝ) * d / 12)) := by sorry
end OnlineCombOpt.Exp2LB
Source
Audibert, Bubeck, Lugosi, Regret in Online Combinatorial Optimization, arXiv:1204.4710v2, App. A, pp. 14–15, the displays "sup R_n ≥ max(…)" (p. 14) and "A = min_{η∈[0,+∞)} max(…) ≥ … ≥ min(0.04 nd, 0.01 d^{3/2}√n)" (p. 15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.