Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 (Generalized Duality), p. 5 — the Kernel DRO primal (2) equals the dual (4)

Proved
KernelDRO.Duality.theorem_3_1

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributionally-robust-optimizationdualitykernel-methodsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rkhs

Let X\mathcal XX be a compact metric space with its Borel σ\sigmaσ-algebra and P\mathcal PP the set of Borel probability measures on X\mathcal XX. Let H\mathcal HH be a real Hilbert space with a continuous feature map φ:X→H\varphi:\mathcal X\to\mathcal Hφ:X→H, so that f∈Hf\in\mathcal Hf∈H acts by f(ξ)=⟨f,φ(ξ)⟩Hf(\xi)=\langle f,\varphi(\xi)\rangle_{\mathcal H}f(ξ)=⟨f,φ(ξ)⟩H​, and let C⊆H\mathcal C\subseteq\mathcal HC⊆H be closed and convex with nonempty ambiguity set KC={P∈P:∫φ dP∈C}\mathcal K_{\mathcal C}=\{P\in\mathcal P:\int\varphi\,dP\in\mathcal C\}KC​={P∈P:∫φdP∈C}. Let Θ\ThetaΘ be any set of decisions and l:Θ×X→[−∞,∞)l:\Theta\times\mathcal X\to[-\infty,\infty)l:Θ×X→[−∞,∞) a loss such that every l(θ,⋅)l(\theta,\cdot)l(θ,⋅) is upper semicontinuous and proper (not identically −∞-\infty−∞). Then

  1. for every θ∈Θ\theta\in\Thetaθ∈Θ,
sup⁡P∈KC∫l(θ,ξ) dP(ξ)  =  inf⁡{f0+δC∗(f): f0∈R, f∈H, l(θ,ξ)≤f0+f(ξ) ∀ξ∈X},\sup_{P\in\mathcal K_{\mathcal C}}\int l(\theta,\xi)\,dP(\xi)\;=\;\inf\Big\{f_0+\delta^*_{\mathcal C}(f):\ f_0\in\mathbb R,\ f\in\mathcal H,\ l(\theta,\xi)\le f_0+f(\xi)\ \forall\xi\in\mathcal X\Big\},P∈KC​sup​∫l(θ,ξ)dP(ξ)=inf{f0​+δC∗​(f): f0​∈R, f∈H, l(θ,ξ)≤f0​+f(ξ) ∀ξ∈X},

where δC∗(f)=sup⁡μ∈C⟨f,μ⟩H\delta^*_{\mathcal C}(f)=\sup_{\mu\in\mathcal C}\langle f,\mu\rangle_{\mathcal H}δC∗​(f)=supμ∈C​⟨f,μ⟩H​ is the support function of C\mathcal CC; 2. consequently the Kernel DRO problem (2) and its dual (4) have the same value:

(P):=inf⁡θsup⁡P∈KC∫l(θ,ξ) dP(ξ)  =  inf⁡θ, f0, f{f0+δC∗(f): l(θ,⋅)≤f0+f on X}=:(D).\mathrm{(P)}:=\inf_\theta\sup_{P\in\mathcal K_{\mathcal C}}\int l(\theta,\xi)\,dP(\xi)\;=\;\inf_{\theta,\,f_0,\,f}\Big\{f_0+\delta^*_{\mathcal C}(f):\ l(\theta,\cdot)\le f_0+f\text{ on }\mathcal X\Big\}=:\mathrm{(D)}.(P):=θinf​P∈KC​sup​∫l(θ,ξ)dP(ξ)=θ,f0​,finf​{f0​+δC∗​(f): l(θ,⋅)≤f0​+f on X}=:(D).

The worst-case expected loss over a set of distributions described through their kernel mean embeddings is thus computed by a single minimization over an RKHS function f0+ff_0+ff0​+f that majorizes the loss; no Lipschitz constant or RKHS norm of lll is needed.

Formalization Note ∫l dP\int l\,dP∫ldP is the published extended-real expectation erealExpectation; all values are extended reals. The paper's Slater clause ri(KC)≠∅\mathrm{ri}(\mathcal K_{\mathcal C})\ne\emptysetri(KC​)=∅ names no topology on measures and is used in the proof only to guarantee a primal solution (p. 15); it is read as KC≠∅\mathcal K_{\mathcal C}\ne\emptysetKC​=∅, which it implies, so the statement is at least as strong as the paper's. Continuity of φ\varphiφ (equivalently of the kernel) is not in Assumption 3.1 but is used by Appendix D. Every printed "min" is read as an infimum: dual attainment is not proved and can fail. A compact X⊂Rd\mathcal X\subset\mathbb R^dX⊂Rd is an instance of the compact metric space.

Preamble
import Mathlib
import Definitions.Def_WassersteinDRO_Duality_erealExpectation
import Definitions.Def_KernelDRO_Duality_Setting

open MeasureTheory
Formal statement
namespace KernelDRO.Duality

open WassersteinDRO.Duality

/-- **Theorem 3.1** (Generalized Duality) (Zhu, Jitkrittum, Diehl & Schölkopf, Kernel Distributionally
Robust Optimization, arXiv:2006.06981v3, Theorem 3.1, p. 5; proved on p. 16 from Proposition A.1 by
(15)). Under Assumption 3.1, the Kernel DRO problem
`(P) := min_θ sup_{P,µ} {∫ l(θ, ξ) dP(ξ) : ∫ φ dP = µ, P ∈ 𝒫, µ ∈ 𝒞}` (2) is equivalent to
`(D) := min_{θ, f₀∈ℝ, f∈ℋ} f₀ + δ*_𝒞(f)` subject to `l(θ, ξ) ≤ f₀ + f(ξ), ∀ ξ ∈ 𝒳` (4), where
`δ*_𝒞(f) := sup_{µ∈𝒞} ⟨f, µ⟩_ℋ`; i.e. `(P) = (D)`, and strong duality holds for the inner moment
problem for every `θ` pointwise.

**Formalization Note.** The decision variable `θ` ranges over an arbitrary type `Θ` ("The theorem
holds regardless of the dependency of l on θ", p. 5) and the loss is `l : Θ → 𝒳 → [−∞, ∞)`. Standing
hypotheses (Assumption 3.1, p. 3, and §2, p. 2): `𝒳` is a compact metric space with its Borel
σ-algebra (a compact `𝒳 ⊂ ℝᵈ` is an instance); the RKHS is in feature-map form, a real Hilbert space
`ℋ` with a continuous feature map `φ` (continuity of the kernel is not written in Assumption 3.1 but
is used by §D.2 through a universal, hence continuous, kernel); `𝒞 ⊆ ℋ` is closed and convex; every
`l(θ, ·)` is upper semicontinuous, never `+∞`, and proper (not identically `−∞`, p. 2). The Slater
clause "ri(𝒦_𝒞) ≠ ∅" names no topology on measures and is used in the proof only as "the primal
problem has a non-empty solution set" (p. 15); it is read as `𝒦_𝒞 ≠ ∅`, which it implies under any
reading, so this statement is at least as strong as the paper's. Every "min" (the outer `min_θ` of
(2) and (4) and the inner `min_{f₀, f}`) is read as an infimum: dual attainment is not proved in the
paper and can fail. `∫ l dP` is the published `erealExpectation` and all values are extended
reals. The first conjunct is the pointwise strong duality, the second the literal `(P) = (D)`. -/
theorem theorem_3_1 {X : Type*} [MetricSpace X] [CompactSpace X] [MeasurableSpace X]
    [BorelSpace X] {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
    {Θ : Type*} (φ : X → H) (hφ : Continuous φ) (C : Set H) (hC_closed : IsClosed C)
    (hC_convex : Convex ℝ C) (l : Θ → X → EReal) (hl_usc : ∀ θ, UpperSemicontinuous (l θ))
    (hl_top : ∀ θ ξ, l θ ξ ≠ ⊤) (hl_proper : ∀ θ, ∃ ξ, l θ ξ ≠ ⊥)
    (hK : (ambiguitySet φ C).Nonempty) :
    (∀ θ, primalValue φ C (l θ) = dualValue φ C (l θ)) ∧
      (⨅ θ, primalValue φ C (l θ)) = ⨅ θ, dualValue φ C (l θ) := by sorry

end KernelDRO.Duality
Source
Zhu, Jitkrittum, Diehl & Schölkopf, Kernel Distributionally Robust Optimization, arXiv:2006.06981v3, Theorem 3.1, (2), (4), pp. 3, 5; Assumption 3.1, p. 3; proof via Proposition A.1 and (15), p. 16
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me