Theorem A.1 — Gaussian maximum and dyadic chaining
OpenZOGlobalLB.Supplement.theorem_A_1chaininggaussian-processesp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
There is a universal constant with both of the following properties.
- If are centered jointly Gaussian variables with , not necessarily independent, then
- If is a separable centered Gaussian process on a totally bounded metric space whose metric is , then, for every base point ,
Here is the covering number for the canonical metric.
Differences from the source:
- encoding: norms and the entropy integral as nonnegative extended quantities → lintegrals followed by the power; reason: preserves infinite values and avoids the Bochner integral's nonintegrable default
- encoding: a separable process → a countable index subset with the same absolute supremum almost surely; reason: this is the standard separable-version property and makes the supremum measurable without restricting null-set representatives
Preamble
import Mathlib import Definitions.Def_HighDimProb_RandomProcesses_CanonicalMetric import Definitions.Def_HighDimProb_Chaining_CoveringNumber open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace ZOGlobalLB
namespace Supplement
/-- **Theorem A.1 (Gaussian maximum and dyadic chaining).** Xia, Yuan,
*On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization*, arXiv:2610.19652,
Theorem A.1, pp.33--34.
One universal constant simultaneously gives (i) the `L²` maximum bound for finitely many
centered, jointly Gaussian variables, without independence, and (ii) the `L²` absolute-supremum
Dudley bound for a separable centered Gaussian process on a totally bounded canonical metric
space, including the arbitrary base-point term and the entropy integral up to the diameter.
**Formalization Note.** `L²` norms and the entropy integral are valued in `ℝ≥0∞`, preserving an
infinite value rather than using the Bochner integral's default zero. `IsGaussianProcess` means
all finite-dimensional marginals are jointly Gaussian. Process separability is stated by the
standard almost-sure countable-supremum property. The ambient metric is required
to equal the published canonical `L²` metric. Total boundedness makes the covering number finite at
every positive scale and also prevents `Metric.diam` from taking its unbounded-set junk value. -/
theorem theorem_A_1 :
∃ C : ℝ, 0 < C ∧
(∀ (K : ℕ), 0 < K → ∀ (Ω : Type) [MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P] (Z : Fin K → Ω → ℝ) (v₀ : ℝ), 0 ≤ v₀ →
IsGaussianProcess Z P →
(∀ i, Integrable (Z i) P ∧ ∫ ω, Z i ω ∂P = 0 ∧
∫⁻ ω, ENNReal.ofReal ((Z i ω) ^ 2) ∂P ≤ ENNReal.ofReal (v₀ ^ 2)) →
(∫⁻ ω, (⨆ i : Fin K, ENNReal.ofReal |Z i ω|) ^ 2 ∂P) ^ (1 / 2 : ℝ) ≤
ENNReal.ofReal C * ENNReal.ofReal v₀ *
ENNReal.ofReal (Real.sqrt (Real.log (2 * K)))) ∧
(∀ (T : Type) [MetricSpace T] [Nonempty T]
(htot : TotallyBounded (Set.univ : Set T))
(Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(Z : T → Ω → ℝ), IsGaussianProcess Z P →
(∀ t, Integrable (Z t) P ∧ ∫ ω, Z t ω ∂P = 0 ∧
Integrable (fun ω => (Z t ω) ^ 2) P) →
(∀ t s, dist t s = HighDimProb.RandomProcesses.canonicalMetric P Z t s) →
(∃ D : Set T, D.Countable ∧ ∀ᵐ ω ∂P,
(⨆ t : T, ENNReal.ofReal |Z t ω|) =
⨆ t : D, ENNReal.ofReal |Z t.1 ω|) →
∀ t₀ : T,
(∫⁻ ω, (⨆ t : T, ENNReal.ofReal |Z t ω|) ^ 2 ∂P) ^ (1 / 2 : ℝ) ≤
ENNReal.ofReal C *
((∫⁻ ω, ENNReal.ofReal ((Z t₀ ω) ^ 2) ∂P) ^ (1 / 2 : ℝ) +
∫⁻ η in Set.Ioc 0 (Metric.diam (Set.univ : Set T)),
if HighDimProb.Chaining.coveringNumber T η = ⊤ then ⊤
else ENNReal.ofReal (Real.sqrt (Real.log
(2 * (HighDimProb.Chaining.coveringNumber T η).toNat))))) := by sorry
end Supplement
end ZOGlobalLB
Source
Xia, Yuan, On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization, arXiv:2610.19652, Theorem A.1, pp.33-34