Corrected Gaussian-surrogate separation for nonsmooth convex losses
ProvedLG2021.surrogate_strong_separationconvex-analysisprobabilitystochastic-optimization
Gaussian-surrogate separation for globally convex Lipschitz losses, including nonsmooth losses.
To allow formalization of the separation argument of Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134:2938–2964, the formal derivation uses the centered Hermite score, direct symmetric-density comparison, smoothing, and explicit parameter estimates. This preliminary entry is superseded by LG2021.gaussian_surrogate_separation, with the same mathematical content and revised presentation of the formalization.
Preamble
import Mathlib import Definitions.Def_LG2021_GaussianGeometry import Definitions.Def_LG2021_Concentration open LG2021 LG2021.Concentration MeasureTheory ProbabilityTheory
Formal statement
theorem LG2021.surrogate_strong_separation {d : ℕ} (hd : 0 < d) {f : Space d → ℝ}
{K : NNReal} (hf : LipschitzWith K f) (hc : ConvexOn ℝ Set.univ f)
{lambda R B delta eps : ℝ} (hl : 0 < lambda) (hl1 : lambda < 1) (hR : 0 < R)
(hB : 0 ≤ B) (hvar : (1-(1-lambda)^2)*B^2/(2*(1-lambda)^2) ≤ 1)
(hshift : (lambda*R)^2/(2*(1-lambda)^2) ≤ 1)
(htail : (gaussian d).real {x : Space d | B < ‖x‖} ≤ delta)
(hgain : 4 ≤ (lambda/2)*Real.exp (-2)*(R^2/(64*(d : ℝ))))
(herr : ((lambda/2)*Real.exp (-2)*(2*(K : ℝ)*Real.sqrt ((d : ℝ)*delta)))*R^2 ≤
eps/(4096*(d : ℝ)*Real.sqrt (d : ℝ))) :
(1/24 : ℝ) ≤ (sphereMeasure d R).real {z |
(gaussianGap (2*(d : ℝ)*R) f-eps)/(4096*(d : ℝ)*Real.sqrt (d : ℝ)) ≤
surrogate lambda f z-f 0} := by sorrySource
Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134:2938–2964, Lemma 5 and Appendix E.