§B.7 — a (γ − L_zz)t/(4L_cL_zθ)-cover of Θ turns |g| ≤ t/2 at the centres into sup_Θ |g| ≤ t
ProvedCertDRO.Conc.cover_implicationcovering-numberlipschitzp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let , , and , and put
Let and let be a finite -cover of in the Euclidean norm (every has some with ), and let satisfy for all . If for every , then
In the proof of Theorem 4 this is applied to the deviation of the empirical from the population robustness level; it reduces the uniform bound to finitely many fixed-parameter bounds.
Formalization Note The set carries both the centres and the Lipschitz property: is a cover by points of (the one the goal uses), a cover with centres anywhere. The supremum is a real supremum; for it is and the conclusion holds since .
Preamble
import Definitions.Def_CertDRO_Conc_model
Formal statement
namespace CertDRO.Conc
/-- §B.7, p. 44, the covering step: let `C = {θ₁, …, θ_N}` be a `(γ − Lzz) t / (4 Lc Lzθ)`-cover of
`Θ` whose centres lie in a set `S ⊇ Θ`, and let `g` be `2 Lc Lzθ / (γ − Lzz)`-Lipschitz on `S`. If
`|g(θᵢ)| ≤ t/2` at every centre, then `sup_{θ ∈ Θ} |g(θ)| ≤ t`. (`S = Θ` is the internal cover used
by the goal; `S = ℝ^d` allows centres anywhere.) -/
theorem cover_implication {d : ℕ} (Θ S : Set (CertDRO.SGD.Param d)) (C : Finset (CertDRO.SGD.Param d))
(g : CertDRO.SGD.Param d → ℝ)
(Lzz Lzθ γ Lc t : ℝ) (hγ : Lzz < γ) (hLc : 0 < Lc) (hLzθ : 0 < Lzθ) (ht : 0 < t)
(hΘS : Θ ⊆ S) (hCS : ∀ x ∈ C, x ∈ S)
(hcover : Θ ⊆ ⋃ x ∈ C, Metric.closedBall x ((γ - Lzz) * t / (4 * Lc * Lzθ)))
(hg : ∀ θ₁ ∈ S, ∀ θ₂ ∈ S, |g θ₁ - g θ₂| ≤ 2 * Lc * Lzθ / (γ - Lzz) * ‖θ₁ - θ₂‖)
(hC : ∀ θ ∈ C, |g θ| ≤ t / 2) :
⨆ θ : Θ, |g θ| ≤ t := by sorry
end CertDRO.Conc
Source
Sinha, Namkoong, Volpi, Duchi, Certifying Some Distributional Robustness with Principled Adversarial Training, arXiv:1710.10571v5, p. 44, §B.7, second and third sentences after the proof of Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.