Eq. (5) — the disturbance δ*ᵢ = −cᵢ sgn(xᵢ)u is admissible and attains ‖b − Ax‖₂ + Σ cᵢ|xᵢ|
ProvedRobustRegLasso.FeatureWise.eq_5_worst_case_attainedp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regressionrobust-optimization
Let , let have columns , let , let , and let . Let be a unit vector, , chosen as
and arbitrary (of unit norm) if . Define for (with ) and . Then lies in the uncertainty set of (2), and
This is the lower half of the identity behind Theorem 1: an explicit admissible disturbance pushes the residual all the way up to the ℓ¹-regularized objective, so the bound (4) is attained.
Formalization Note The paper leaves implicit; it is needed for a unit vector to exist and is stated as 0 < n. The choice of is universally quantified: any unit that equals whenever . The sign function is Real.sign, with as the computation in (5) requires.
Preamble
import Mathlib import Definitions.Def_RobustRegLasso_FeatureWise_Basic
Formal statement
namespace RobustRegLasso.FeatureWise
theorem eq_5_worst_case_attained {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 → ℝ)
(u : EuclideanSpace ℝ (Fin n)) (hu : ‖u‖ = 1)
(hu_dir : matVec a x ≠ b → u = ‖b - matVec a x‖⁻¹ • (b - matVec a x)) :
worstCaseDisturbance c x u ∈ uncertaintySet c ∧
perturbedResidual a (worstCaseDisturbance c x u) b x =
‖b - matVec a x‖ + ∑ i, c i * |x i| := by sorry
end RobustRegLasso.FeatureWise
Source
Xu, Caramanis, Mannor, Robust Regression and Lasso, arXiv:0811.1790v1, p. 4, Eq. (5) and the definitions of u and δ*ᵢ preceding it, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.