Explicit-parameter Gaussian-surrogate separation
ProvedLG2021.paper_strong_separationconvex-analysisprobabilitystochastic-optimization
For a globally convex Lipschitz function , let and define
Let and . Set
Suppose has a global Lipschitz constant . For (zero at ),
All parameter inequalities and the Gaussian tail estimate are proved. In particular, . Nonsmooth convex losses are included.
To allow formalization of the separation argument in Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134:2938–2964, the derivation uses the centered Gaussian Hessian score and a direct symmetric-density comparison in the part corresponding to Appendix E. Smoothing supplies the nonsmooth case, and all tail and parameter conditions are explicit. This statement concerns separation; the full regret theorem is stated separately.
Preamble
import Mathlib import Definitions.Def_LG2021_GaussianSeparation import Definitions.Def_LG2021_GaussianEstimators open LG2021 LG2021.Concentration MeasureTheory ProbabilityTheory
Formal statement
theorem LG2021.paper_strong_separation {d n : ℕ} (hd : 0 < d) (hn : 0 < n)
{D : ℝ} (hD : 0 ≤ D) {f : Space d → ℝ} {K : NNReal}
(hK : (K : ℝ) ≤ paperLipschitz d D (parameterLog d D n))
(hf : LipschitzWith K f) (hc : ConvexOn ℝ Set.univ f) :
(1/24 : ℝ) ≤
(sphereMeasure d (paperRadius d (parameterLog d D n)/(2*(d : ℝ)))).real {z |
(gaussianGap (paperRadius d (parameterLog d D n)) f-1/(n : ℝ))/
(4096*(d : ℝ)*Real.sqrt (d : ℝ)) ≤
surrogate (paperLambda d (parameterLog d D n)) f z-f 0} := by sorrySource
Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, Proceedings of the 34th Conference on Learning Theory (COLT 2021), Proceedings of Machine Learning Research 134:2938–2964, 2021, Lemma 5 and Appendix E. Separation argument adapted for formalization.