Eq. (4) — under any admissible disturbance, ‖b − (A + ΔA)x‖₂ ≤ ‖b − Ax‖₂ + Σ |xᵢ|cᵢ
ProvedRobustRegLasso.FeatureWise.eq_4_upper_boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regressionrobust-optimization
Let have columns , let , let , and let be the feature-wise uncoupled uncertainty set of (2). For every coefficient vector and every disturbance ,
Taking the supremum over , this is the upper half of the identity behind Theorem 1: the worst-case residual never exceeds the ℓ¹-regularized objective.
Formalization Note The paper's display (4) bounds the maximum over ; the Lean statement gives the equivalent pointwise bound for each admissible disturbance, which avoids any supremum. The hypothesis is the paper's standing assumption on (2).
Preamble
import Mathlib import Definitions.Def_RobustRegLasso_FeatureWise_Basic
Formal statement
namespace RobustRegLasso.FeatureWise
theorem eq_4_upper_bound {n m : ℕ} (a : Fin m → EuclideanSpace ℝ (Fin n))
(b : EuclideanSpace ℝ (Fin n)) (c : Fin m → ℝ) (hc : ∀ i, 0 ≤ c i) (x : Fin m → ℝ)
(δ : Fin m → EuclideanSpace ℝ (Fin n)) (hδ : δ ∈ uncertaintySet c) :
perturbedResidual a δ b x ≤ ‖b - matVec a x‖ + ∑ i, |x i| * c i := by sorry
end RobustRegLasso.FeatureWise
Source
Xu, Caramanis, Mannor, Robust Regression and Lasso, arXiv:0811.1790v1, p. 4, Eq. (4), proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.