Theorem 3 — robust regression over equals for an arbitrary norm
ProvedRobustRegLasso.Coupled.theorem_3_arbitrary_normLet be an arbitrary norm on with , let be the columns of and the response, and let be budgets. Consider the feature-wise uncertainty set
Then the robust regression problem is equivalent to the regularized regression problem
in the following sense:
- for every , the maximum of over is attained and equals ;
- a vector minimizes the robust objective if and only if it minimizes the regularized objective.
This is Theorem 1 with the Euclidean norm replaced by an arbitrary norm; it is the step of the proof of (13) that evaluates the inner maximum for fixed budgets.
Formalization Note. is an arbitrary nontrivial real normed space (the nontriviality is the paper's implicit ; with the identity fails). The budgets come from the setting of (2). "Is equivalent to" is read as: equal objectives at every (with the maximum attained) and equal sets of minimizers; existence of a minimizer is not claimed. The robust objective in the minimizer clause is the extended-real supremum.
import Mathlib import Definitions.Def_RobustRegLasso_Coupled_Basic
namespace RobustRegLasso.Coupled
/-- Theorem 3 of arXiv:0811.1790v1, p. 6. For an arbitrary norm `‖·‖ₐ` on `E` (with `E ≠ 0`, i.e.
`n ≥ 1`) and budgets `cᵢ ≥ 0`, the robust regression problem over
`Uₐ = {(δ₁, …, δₘ) | ‖δᵢ‖ₐ ≤ cᵢ}` is equivalent to the regularized problem
`min_x ‖b − Ax‖ₐ + ∑ᵢ cᵢ|xᵢ|`: for every `x` the worst-case residual is attained and equals
`‖b − Ax‖ₐ + ∑ᵢ cᵢ|xᵢ|`, and the two problems have the same minimizers. -/
theorem theorem_3_arbitrary_norm {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[Nontrivial E] {m : ℕ} (a : Fin m → E) (b : E) (c : Fin m → ℝ) (hc : ∀ i, 0 ≤ c i) :
(∀ x : Fin m → ℝ,
IsGreatest (residualValues a b (uncertaintySetA c) x)
(‖b - matVec a x‖ + ∑ i, c i * |x i|)) ∧
{x : Fin m → ℝ | ∀ x' : Fin m → ℝ,
robustObjective a b (uncertaintySetA c) x ≤ robustObjective a b (uncertaintySetA c) x'} =
{x : Fin m → ℝ | ∀ x' : Fin m → ℝ,
‖b - matVec a x‖ + ∑ i, c i * |x i| ≤ ‖b - matVec a x'‖ + ∑ i, c i * |x' i|} := by sorry
end RobustRegLasso.Coupled
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.