Lemma 7, p. 38 — y ↦ ((1/n)Σ|yᵢ|^{k*})^{1/k*} is n^{−1/(2∨k*)}-Lipschitz for ‖·‖₂
ProvedUniformDRO.Concentration.lemma_7concentrationlipschitzlp-normp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and . For all ,
that is, the normalized -norm is -Lipschitz with respect to the Euclidean norm.
It gives the Lipschitz constant of the plug-in dual objective as a function of the data, the input to the convex concentration inequality in (28).
Formalization Note The Euclidean distance is written out as , because the default norm on Fin n → ℝ is the sup norm.
Preamble
import Mathlib import Definitions.Def_UniformDRO_Concentration_RobustRisk
Formal statement
namespace UniformDRO.Concentration
/-- Lemma 7 (Duchi & Namkoong, arXiv:1810.08750v6, App. C.1, p. 38): the map
`y ↦ ((1/n) ∑ᵢ |yᵢ|^{k*})^{1/k*}` on `ℝⁿ` is `n^{-1/(2 ∨ k*)}`-Lipschitz for the Euclidean norm.
The Euclidean distance is written out as `√(∑ᵢ (yᵢ - y'ᵢ)²)`, since the default norm on
`Fin n → ℝ` is the sup norm. -/
theorem lemma_7 (k : ℝ) (hk : 1 < k) (n : ℕ) (hn : 0 < n) (y y' : Fin n → ℝ) :
|((1 / n : ℝ) * ∑ i, |y i| ^ kstar k) ^ (1 / kstar k) -
((1 / n : ℝ) * ∑ i, |y' i| ^ kstar k) ^ (1 / kstar k)| ≤
(n : ℝ) ^ (-(1 / max 2 (kstar k))) * Real.sqrt (∑ i, (y i - y' i) ^ 2) := by sorry
end UniformDRO.Concentration
Source
Duchi & Namkoong, arXiv:1810.08750v6, Lemma 7, App. C.1, p. 38; proof pp. 38–39
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.