Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (13) — the worst case over U′\mathcal U'U′ is ∥b−Ax∥a+sup⁡c∈Z∣x∣⊤c\|b-Ax\|_a + \sup_{c\in\mathcal Z} |x|^\top c∥b−Ax∥a​+supc∈Z​∣x∣⊤c

Proved
RobustRegLasso.Coupled.eq_13_coupled_worst_case

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

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regressionrobust-optimization

Let ∥⋅∥a\|\cdot\|_a∥⋅∥a​ be an arbitrary norm on Rn\mathbb R^nRn with n≥1n \ge 1n≥1, let a1,…,am,b∈Rna_1,\dots,a_m, b \in \mathbb R^na1​,…,am​,b∈Rn, and let f1,…,fk:Rm→Rf_1,\dots,f_k : \mathbb R^m \to \mathbb Rf1​,…,fk​:Rm→R be convex functions. Consider the coupled uncertainty set and the budget set

U′={(δ1,…,δm):fj(∥δ1∥a,…,∥δm∥a)≤0, j=1,…,k},Z={z∈Rm:fj(z)≤0, j=1,…,k; z≥0}.\mathcal U' = \{(\delta_1,\dots,\delta_m) : f_j(\|\delta_1\|_a,\dots,\|\delta_m\|_a) \le 0,\ j=1,\dots,k\},\qquad \mathcal Z = \{z \in \mathbb R^m : f_j(z) \le 0,\ j = 1,\dots,k;\ z \ge 0\}.U′={(δ1​,…,δm​):fj​(∥δ1​∥a​,…,∥δm​∥a​)≤0, j=1,…,k},Z={z∈Rm:fj​(z)≤0, j=1,…,k; z≥0}.

Then for every x∈Rmx \in \mathbb R^mx∈Rm,

sup⁡ΔA∈U′∥b−(A+ΔA)x∥a=∥b−Ax∥a+sup⁡c∈Z∣x∣⊤c,\sup_{\Delta A \in \mathcal U'} \|b - (A+\Delta A)x\|_a = \|b - Ax\|_a + \sup_{c \in \mathcal Z} |x|^\top c,ΔA∈U′sup​∥b−(A+ΔA)x∥a​=∥b−Ax∥a​+c∈Zsup​∣x∣⊤c,

where ∣x∣=(∣x1∣,…,∣xm∣)|x| = (|x_1|,\dots,|x_m|)∣x∣=(∣x1​∣,…,∣xm​∣) and both suprema are taken in the extended reals.

This identity reduces the robust problem over a coupled set to a convex maximization over the budgets ccc; Corollaries 1 and 2 evaluate its last term for specific sets Z\mathcal ZZ.

Formalization Note. The paper writes "max" on both sides; neither maximum need exist (e.g. Z\mathcal ZZ empty or unbounded), so both are extended-real suprema: when Z=∅\mathcal Z = \emptysetZ=∅ both sides are −∞-\infty−∞, and when ∣x∣⊤c|x|^\top c∣x∣⊤c is unbounded on Z\mathcal ZZ both sides are +∞+\infty+∞. The paper's first line, U′={(δ1,…,δm)∣c∈Z; ∥δi∥a≤ci}\mathcal U' = \{(\delta_1,\dots,\delta_m) \mid c \in \mathcal Z;\ \|\delta_i\|_a \le c_i\}U′={(δ1​,…,δm​)∣c∈Z; ∥δi​∥a​≤ci​}, holds as a set identity only when Z\mathcal ZZ is downward closed in R+m\mathbb R^m_+R+m​; the identity (13) itself holds without that, and it is stated here for U′\mathcal U'U′ as defined on p. 6. The convexity of the fjf_jfj​ is the paper's standing assumption and is not needed for (13). The norm space is nontrivial (n≥1n \ge 1n≥1).

Preamble
import Mathlib
import Definitions.Def_RobustRegLasso_Coupled_Basic
Formal statement
namespace RobustRegLasso.Coupled

/-- Eq. (13), proof of Theorem 4, Appendix B of arXiv:0811.1790v1, p. 19. For the coupled
uncertainty set `U′ = {(δ₁, …, δₘ) | f_j(‖δ₁‖ₐ, …, ‖δₘ‖ₐ) ≤ 0, j = 1, …, k}` with convex
`f_j : ℝᵐ → ℝ`, and `Z = {z ∈ ℝᵐ | f_j(z) ≤ 0, j = 1, …, k; z ≥ 0}`, for every `x`
`sup_{ΔA ∈ U′} ‖b − (A + ΔA)x‖ₐ = ‖b − Ax‖ₐ + sup_{c ∈ Z} |x|ᵀc`, both suprema taken in the extended
reals (so the identity also covers `Z = ∅`, both sides `⊥`, and an unbounded right-hand side, both
sides `⊤`). Requires `E ≠ 0` (`n ≥ 1`); the convexity of the `f_j` is the paper's standing
assumption. -/
theorem eq_13_coupled_worst_case {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
    [Nontrivial E] {m k : ℕ} (a : Fin m → E) (b : E) (f : Fin k → (Fin m → ℝ) → ℝ)
    (hf : ∀ j, ConvexOn ℝ Set.univ (f j)) (x : Fin m → ℝ) :
    robustObjective a b (coupledSet f) x =
      ((‖b - matVec a x‖ : ℝ) : EReal) +
        ⨆ c ∈ budgetSet f, ((∑ i, |x i| * c i : ℝ) : EReal) := by sorry

end RobustRegLasso.Coupled
Source
Xu, Caramanis, Mannor, Robust Regression and Lasso, arXiv:0811.1790v1, p. 19, Eq. (13), proof of Theorem 4, Appendix B; U′ and Z defined on p. 6
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 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