Proof of Theorem 1 — for every x, max over U of ‖b − (A + ΔA)x‖₂ equals ‖b − Ax‖₂ + Σ cᵢ|xᵢ|, attained
ProvedRobustRegLasso.FeatureWise.per_x_identitylassop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regressionrobust-optimization
Let , let have columns , let , let , and let be the uncertainty set (2). For every the worst-case residual is a maximum, and
That is, the number belongs to the set and bounds it from above; equivalently, the robust objective equals the ℓ¹-regularized objective .
This per-point identity is the heart of Theorem 1: the robust regression objective and the ℓ¹-regularized objective are the same function of .
Formalization Note "max" is stated as IsGreatest of the set of residual norms (the maximum exists and has this value), together with the equality of the EReal supremum and . The paper leaves implicit; for the identity would read and is false, so 0 < n is a hypothesis.
Preamble
import Mathlib import Definitions.Def_RobustRegLasso_FeatureWise_Basic
Formal statement
namespace RobustRegLasso.FeatureWise
theorem per_x_identity {n m : ℕ} (hn : 0 < n) (a : Fin m → EuclideanSpace ℝ (Fin n))
(b : EuclideanSpace ℝ (Fin n)) (c : Fin m → ℝ) (hc : ∀ i, 0 ≤ c i) (x : Fin m → ℝ) :
IsGreatest (residualValues a b c x) (‖b - matVec a x‖ + ∑ i, c i * |x i|) ∧
robustObjective a b c x = ((‖b - matVec a x‖ + ∑ i, c i * |x i| : ℝ) : EReal) := by sorry
end RobustRegLasso.FeatureWise
Source
Xu, Caramanis, Mannor, Robust Regression and Lasso, arXiv:0811.1790v1, p. 4, proof of Theorem 1, first sentence ("Fix x∗. We prove that …") and closing sentence ("Combining Inequalities (4) and (5) …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.