Zero squared-validation-loss Lasso decision problem
DefinitionAggCG_Supplement_LassoZeroLangalgorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
An instance consists of a full-column-rank rational training pair, a rational validation pair, and rational endpoints . It is accepted exactly when some in the closed interval makes the ordinary squared validation loss of the Lasso solution zero.
Signed Partition and explicit self-delimiting encodings are included for the reduction in Theorem 4.4.
Definition code
import Mathlib
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_QAlgorithms_ClassicalRationalEncoding
import Definitions.Def_AggCG_Supplement_lassoPath
namespace AggCG.Supplement
open Matrix
/-- The self-delimiting code of a rational matrix with known shape, row by row. -/
def encodeRatMatrix {a b : ℕ} (M : Matrix (Fin a) (Fin b) ℚ) : List Bool :=
(List.ofFn fun i => (List.ofFn fun j => QAlgorithms.LocalHamiltonian.encRat (M i j)).flatten).flatten
/-- The self-delimiting code of a rational vector with known length. -/
def encodeRatVecS {a : ℕ} (v : Fin a → ℚ) : List Bool :=
(List.ofFn fun i => QAlgorithms.LocalHamiltonian.encRat (v i)).flatten
/-- An input of the Lasso validation problem of Theorem 4.4 (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): a rational training pair `(X, y)` with `n`
observations and `p` variables, a rational validation pair `(X_val, y_val)` with `q` observations, and
rational endpoints `λ_lo, λ_hi`. -/
structure LassoInst where
/-- Training observations. -/
n : ℕ
/-- Training variables (coefficients). -/
p : ℕ
/-- Validation observations. -/
q : ℕ
/-- Training design. -/
X : Matrix (Fin n) (Fin p) ℚ
/-- Training response. -/
y : Fin n → ℚ
/-- Validation design. -/
Xv : Matrix (Fin q) (Fin p) ℚ
/-- Validation response. -/
yv : Fin q → ℚ
/-- Lower endpoint. -/
lo : ℚ
/-- Upper endpoint. -/
hi : ℚ
namespace LassoInst
/-- Full column rank training design and `0 < λ_lo < λ_hi`. -/
def Valid (I : LassoInst) : Prop := I.X.rank = I.p ∧ 0 < I.lo ∧ I.lo < I.hi
/-- The input code: the three sizes in unary, then every rational in self-delimiting binary. -/
def encode (I : LassoInst) : List Bool :=
CookLevin.encodeNat I.n ++ CookLevin.encodeNat I.p ++ CookLevin.encodeNat I.q ++
encodeRatMatrix I.X ++ encodeRatVecS I.y ++ encodeRatMatrix I.Xv ++ encodeRatVecS I.yv ++
QAlgorithms.LocalHamiltonian.encRat I.lo ++ QAlgorithms.LocalHamiltonian.encRat I.hi
/-- The ordinary squared validation loss `‖X_val ŵ(λ) − y_val‖₂²` of the Lasso path. -/
noncomputable def valLoss (I : LassoInst) (lam : ℝ) : ℝ :=
∑ i, (((I.Xv.map ((↑) : ℚ → ℝ)) *ᵥ
lassoPath (I.X.map ((↑) : ℚ → ℝ)) (fun k => (I.y k : ℝ)) lam) i - (I.yv i : ℝ)) ^ 2
end LassoInst
/-- The decision problem of Theorem 4.4 (p.6): valid inputs for which some `λ ∈ [λ_lo, λ_hi]` gives zero
ordinary squared validation loss `‖X_val ŵ(λ) − y_val‖₂² = 0`. Strings that encode no valid input are
rejected.
**Formalization Note** `λ` is real; no sparsity restriction or extra penalty is imposed. -/
def LassoZeroLang : CookLevin.Language := fun x =>
∃ I : LassoInst, x = I.encode ∧ I.Valid ∧
∃ lam : ℝ, (I.lo : ℝ) ≤ lam ∧ lam ≤ (I.hi : ℝ) ∧ I.valLoss lam = 0
/-- The code of a Signed Partition input `d_1, …, d_r, T`: each `d_j` with a continuation bit, a stop bit,
then `T`, integers in self-delimiting sign–magnitude binary. -/
def encodeSP (d : List ℤ) (T : ℤ) : List Bool :=
(d.map fun z => true :: QAlgorithms.LocalHamiltonian.encInt z).flatten ++ [false] ++
QAlgorithms.LocalHamiltonian.encInt T
/-- **Signed Partition** (p.6: "integers d_1, …, d_r, T and asks whether some σ ∈ {−1, +1}^r satisfies
Σ_j d_j σ_j = T"). -/
def SignedPartitionLang : CookLevin.Language := fun x =>
∃ (d : List ℤ) (T : ℤ), x = encodeSP d T ∧
∃ σ : Fin d.length → Bool, ∑ j, (if σ j then d.get j else -d.get j) = T
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem 4.4, p.6, PDF p.7