Gaussian-surrogate separation for nonsmooth convex losses
ProvedLG2021.gaussian_surrogate_separationFor a globally convex Lipschitz function , let and define
Let , let be a Lipschitz constant for , and let , , . Suppose
For (defined to be zero when ),
No differentiability hypothesis is imposed on . The proof uses positive Hessians, Gaussian integration by parts and symmetric density comparison, followed by double Gaussian smoothing and a closed-event limit.
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.
import Mathlib import Definitions.Def_LG2021_GaussianSeparation import Definitions.Def_LG2021_GaussianEstimators open LG2021 LG2021.Concentration MeasureTheory ProbabilityTheory
theorem LG2021.gaussian_surrogate_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 sorry