Scalar ridge validation-loss class
DefinitionAggCG_Supplement_ridgeClassalgorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
A ridge task consists of full-column-rank training data and one validation point . At , its fitted coefficients are and its loss is .
The scalar ridge class contains these loss functions over all full-rank tasks with a fixed number of coefficients.
Definition code
import Mathlib
namespace AggCG.Supplement
open Matrix
/-- A scalar-ridge task with `p` coefficients (Sharma, *Computational Complexity of Data-Driven
Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission
(manuscript sha256 f7ea0248…), §N, p.78, PDF p.79): training data `(X, y)` with `n` samples and one
validation point `(r, t)`. -/
structure RidgeTask (p : ℕ) where
/-- Number of training samples. -/
n : ℕ
/-- Training design. -/
X : Matrix (Fin n) (Fin p) ℝ
/-- Training response. -/
y : Fin n → ℝ
/-- Validation features. -/
r : Fin p → ℝ
/-- Validation target. -/
t : ℝ
namespace RidgeTask
variable {p : ℕ}
/-- Full column rank training design. -/
def FullRank (τ : RidgeTask p) : Prop := Function.Injective τ.X.mulVec
/-- The ridge fit `ŵ(λ) = (XᵀX + λI)⁻¹ Xᵀy`. -/
noncomputable def fit (τ : RidgeTask p) (lam : ℝ) : Fin p → ℝ :=
(τ.Xᵀ * τ.X + lam • (1 : Matrix (Fin p) (Fin p) ℝ))⁻¹ *ᵥ (τ.Xᵀ *ᵥ τ.y)
/-- The nonnegative squared validation loss `(rᵀŵ(λ) − t)²`. -/
noncomputable def loss (τ : RidgeTask p) (lam : ℝ) : ℝ := (τ.r ⬝ᵥ τ.fit lam - τ.t) ^ 2
end RidgeTask
/-- The scalar regularization-parameter family `F = {τ ↦ (rᵀŵ(λ) − t)² : λ > 0}` on the domain of all
full-column-rank tasks with `p` coefficients (Theorem N.3, p.78).
**Formalization Note** For `λ > 0` the matrix `XᵀX + λI` is invertible, so the inverse is the actual
inverse. -/
def ridgeClass (p : ℕ) : Set ({τ : RidgeTask p // τ.FullRank} → ℝ) :=
{g | ∃ lam > 0, ∀ τ, g τ = τ.1.loss lam}
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), §N and Theorem N.3, p.78, PDF p.79