Appendix D, first display — the worst case of over admissible is attained and equals
ProvedRobustRegLasso.WorstCaseExp.appendix_d_robust_identityLet and be integers, , , and . Call , with and , admissible if and for every column . Then
and the maximum is attained: the right-hand side is an upper bound for every admissible and is reached by one of them.
This is the robust-regression identity of the paper's first section applied to the augmented matrix , in which the response is perturbed together with the features. It identifies the left-hand side of Corollary 3 with a worst-case residual.
Formalization Note The paper writes "max"; the statement is IsGreatest of the set of residual norms over admissible , which asserts both the bound and its attainment. The hypotheses and are the paper's setting ( samples, a nonnegative budget); they are left implicit on the page. is indexed by rows (samples) and columns (features), and the norm constraint is on the columns.
import Mathlib import Definitions.Def_RobustRegLasso_WorstCaseExp_Basic
namespace RobustRegLasso.WorstCaseExp
/-- Appendix D, proof of Corollary 3, first display (arXiv:0811.1790v1, p. 22): for `n ≥ 1`,
`c ≥ 0` and every `x`,
`max_{‖σ‖₂ ≤ √n c; ∀j: ‖δⱼ‖₂ ≤ √n c} ‖b + σ − (A + [δ₁, …, δₘ])x‖₂ = ‖b − Ax‖₂ + √n c‖x‖₁ + √n c`,
with the maximum attained. -/
theorem appendix_d_robust_identity {n m : ℕ} (hn : 0 < n) (A : Matrix (Fin n) (Fin m) ℝ)
(b : Fin n → ℝ) (c : ℝ) (hc : 0 ≤ c) (x : Fin m → ℝ) :
IsGreatest
{v : ℝ | ∃ (σ : Fin n → ℝ) (Δ : Matrix (Fin n) (Fin m) ℝ),
Admissible c σ Δ ∧ v = l2norm (b + σ - Matrix.mulVec (A + Δ) x)}
(regularizedLoss A b c x) := by sorry
end RobustRegLasso.WorstCaseExp
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.