Theorem 4.4 — zero ordinary Lasso validation loss is NP-complete
OpenAggCG.Supplement.theorem_4_4algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is a polynomial-time many-one reduction from Signed Partition to deciding whether a full-column-rank rational Lasso training pair and rational validation pair admit some , with , for which
The problem is NP-complete. For an input with signed-partition numbers, the reduction has training variables and observations, validation observations, and a training design depending only on ; every quantity has polynomial binary length, with no sparsity constraint or added penalty.
Differences from the source:
- encoding: the source states a rational decision problem → Lean gives explicit self-delimiting codes for matrices, vectors, endpoints, and Signed Partition instances; reason: these codes determine the same many-one reduction language
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_AggCG_Supplement_LassoZeroLang
Formal statement
namespace AggCG.Supplement
/-- **Theorem 4.4** (Ordinary scalar Lasso squared-validation zero-loss ERM; Sharma, *Computational
Complexity of Data-Driven Configuration for Integer Programming, Clustering, and Learning Algorithms*,
STOC 2027 submission (manuscript sha256 f7ea0248…), p.6, PDF p.7):
(1) there is a polynomial-time many-one reduction `f` from Signed Partition to the decision problem
"given a full-column-rank rational training pair `(X, y)`, a rational validation pair `(X_val, y_val)` and
rational endpoints `0 < λ_lo < λ_hi`, is there `λ ∈ [λ_lo, λ_hi]` with `‖X_val ŵ(λ) − y_val‖₂² = 0`";
on an input with `r` numbers it produces a valid instance with `p = 2r + 3` training variables, `p`
training observations and `r + 3` validation observations, whose training design is a fixed function of
`r` alone;
(2) the decision problem is NP-complete.
**Formalization Note** "Polynomial binary length" of all output quantities is implied by the polynomial
running time of `f`. No sparsity restriction or extra validation penalty is imposed (`LassoZeroLang`). -/
theorem theorem_4_4 :
(∃ f : List Bool → List Bool, CookLevin.IsPolyTimeComputable f ∧
(∀ x, SignedPartitionLang x ↔ LassoZeroLang (f x)) ∧
∃ design : (r : ℕ) → Matrix (Fin (2 * r + 3)) (Fin (2 * r + 3)) ℚ,
∀ (d : List ℤ) (T : ℤ), ∃ I : LassoInst, f (encodeSP d T) = I.encode ∧ I.Valid ∧
∃ (hn : I.n = 2 * d.length + 3) (hp : I.p = 2 * d.length + 3), I.q = d.length + 3 ∧
∀ i j, I.X i j = design d.length (Fin.cast hn i) (Fin.cast hp j)) ∧
CookLevin.NPComplete LassoZeroLang := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem 4.4, p.6, PDF p.7