Theorem 1 — robust regression with feature-wise uncertainty set (2) is equivalent to ℓ¹-regularized regression (3)
ProvedRobustRegLasso.FeatureWise.theorem_1_robust_eq_l1_regularizedLet and be integers, let have columns , let , and let . Let be the feature-wise uncoupled uncertainty set (2). Then the robust regression problem (1),
is equivalent to the ℓ¹-regularized regression problem (3),
Precisely:
- a vector minimizes the robust objective if and only if it minimizes ;
- the two problems have the same optimal value, .
The theorem identifies robustness to feature-wise bounded perturbations of the data matrix with ℓ¹ regularization: with equal budgets it is the Lasso with the unsquared loss.
Formalization Note "Equivalent" is read as in the proof ("Minimizing over on both sides proves the theorem"): same minimizers and same optimal value. No minimizer is claimed to exist, since the paper does not show one. The robust objective is the supremum over in EReal, and the optimal values are infima in EReal, so neither carries a junk value. The paper leaves implicit; it is a hypothesis (0 < n). The budgets are the paper's standing assumption on (2).
import Mathlib import Definitions.Def_RobustRegLasso_FeatureWise_Basic
namespace RobustRegLasso.FeatureWise
theorem theorem_1_robust_eq_l1_regularized {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 → ℝ, IsMinOn (robustObjective a b c) Set.univ x ↔
IsMinOn (l1RegularizedObjective a b c) Set.univ x) ∧
⨅ x : Fin m → ℝ, robustObjective a b c x =
⨅ x : Fin m → ℝ, ((l1RegularizedObjective a b c x : ℝ) : EReal) := by sorry
end RobustRegLasso.FeatureWise
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.