Two-layer linear regression and gradient-flow model
DefinitionFeatureDistortion_ModelNotation: , is the input dimension, the feature dimension, the data map, the labels, the features, and the head. Adjoint means Euclidean transpose. The loss is , with no normalization. The probability model, when present, is explicitly specified below; deterministic flow statements involve no random data assumption.
Vec. For each natural number , is the real Euclidean space with coordinates indexed by , with its usual inner product and norm. The case is included and consists only of the zero vector.
Features. For natural numbers , is the space of continuous real-linear maps . There is no rank or normalization assumption. If either dimension is zero, this space consists only of the zero map.
weights. For natural numbers , a continuous real-linear map , and , the weight vector is , where is the Euclidean adjoint. Zero dimensions are permitted; the weight vector is zero if or .
residual. For natural numbers , continuous real-linear maps and , and vectors and , the residual is . All dimensions may be zero; the residual is zero if and is if or . There is no required relation between the arguments.
trainingLoss. For natural numbers , continuous real-linear maps and , and vectors and , the training loss is . There is no normalization by or factor of . If it is zero; if or it is .
headGradient. For natural numbers , continuous real-linear maps and , and vectors and , this definition assigns the vector , where the adjoints are Euclidean. There are no further hypotheses. The vector is zero if any of the dimensions is zero.
featureGradient. For natural numbers , continuous real-linear maps and , and vectors and , this definition assigns the continuous real-linear map from to . Thus the rank-one map takes an inner product with and multiplies by that scalar. No dimension is required to be positive; the map is zero if any of is zero.
Trajectory. For natural numbers , a trajectory is a pair of functions and , called its head and features, respectively; denotes continuous real-linear maps. The structure itself imposes no continuity, differentiability, initial condition, or differential equation on these functions. Both are defined at all real times, and zero dimensions are permitted.
IsFineTuningFlow. For natural numbers , continuous real-linear maps and , vectors and , and a pair of functions and , this predicate means , , and, for every real , existence of derivatives within equal to and . The latter is a derivative in the space of continuous linear maps. At zero, the derivatives are within the half-line. No conditions apply at negative times. Zero dimensions are allowed.
IsLinearProbingFlow. For natural numbers , continuous real-linear maps and , vectors and , and a function , this predicate means and existence, at every real , of a derivative within equal to . The map is fixed. Values at negative times are unconstrained, and zero dimensions are included.
rowSpace. For natural numbers and a continuous real-linear map , this definition assigns the subspace of , where is the Euclidean adjoint. It is the zero subspace if , , or .
OrthonormalRows. For natural numbers and a continuous real-linear map , this predicate means , equivalently for every . It holds for the unique map when ; it cannot hold when .
VisibleOn. For natural numbers , a continuous real-linear map , and a real linear subspace , this predicate means that is injective, where is orthogonal projection: equality of these projections for any implies . If this holds; if and it cannot hold. Zero dimensions are included.
balance. For natural numbers , a vector , and a continuous real-linear map , the balance is the endomorphism of sending to , namely . No normalization is required. It is the zero endomorphism if , and its second summand is zero if .
alignmentError. For a natural number and vectors , the alignment error is . It vanishes exactly when or . No nonzero assumption is imposed. If , including when , the error is zero for every .
secondMoment. For a natural number and any measure on , this definition assigns the operator-valued Bochner integral , where . It is an uncentered second moment. There is no probability or integrability assumption in this definition; the total Bochner integral is zero if its integrand is not integrable. For the operator is zero.
OODLaw. For a natural number , an OOD law consists of a probability measure on , the hypothesis that is integrable with respect to , and the hypothesis that for every nonzero , where and . There is no mean-zero assumption. For , the positivity condition is vacuous and the probability measure is concentrated at the sole zero vector.
oodLoss. For natural numbers , a probability measure on with integrable squared norm and for every nonzero , a target , a vector , and a continuous real-linear map , this definition assigns . Here , with , and is the Euclidean adjoint. If the loss is zero; if it is .
gaussianHead. For a natural number and any real number , this definition assigns the pushforward of standard Gaussian measure on Euclidean under . Positive, negative, and zero are all allowed. For this is the point mass at zero; for it is the point mass at the only vector for every .
Problem. For natural numbers , a problem consists of continuous real-linear maps and , called its data and optimal features; a real-linear isometric bijection , called its rotation; and a vector , called its optimal head. No other conditions are imposed on these fields. In particular, positive determinant is not required of . Zero dimensions are included.
initialFeatures. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the initial feature map is . It does not depend on or and requires no admissibility hypothesis. If or , it is zero.
alignedHead. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the aligned head is . It does not depend on or and requires no admissibility hypothesis. It is zero if , including when .
targetWeights. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the target vector is . It does not depend on or and requires no admissibility hypothesis. It is zero if or .
labels. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the label vector is . It does not depend on and requires no admissibility hypothesis. It is zero if any of is zero.
Admissible. For natural numbers and a problem consisting of continuous real-linear maps and , a real-linear isometric bijection , and , let , , and . Admissibility is the conjunction , , , , , injectivity of , and injectivity of , both on , where denotes orthogonal projection. Each injectivity requirement says equality of the displayed projections of two vectors implies equality of the vectors. These hypotheses exclude zero dimensions and require and .
Formalization note: source-derived model for the source-backed parent; no flow existence, convergence, invariant, or desired risk bound is assumed. Source: Kumar, Raghunathan, Jones, Ma, and Liang, Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution, ICLR 2022, https://arxiv.org/pdf/2202.10054v1. Section 3.1, PDF pp. 4--6, equations (3.2)--(3.5). Source-backed parent: Section 3.4, PDF p. 10, Proposition 3.7, equations (3.10)--(3.11); Appendix A.7, PDF pp. 45--47.
import Mathlib.Analysis.Calculus.Deriv.Basic
import Mathlib.Analysis.InnerProductSpace.Adjoint
import Mathlib.Analysis.InnerProductSpace.PiL2
import Mathlib.Probability.Distributions.Gaussian.Multivariate
/-!
Two-layer linear regression and its gradient flows. Source: Kumar et al.,
arXiv:2202.10054v1, Sections 3.1 and 3.4, PDF pp. 4--6 and 10;
Appendix A.2, PDF pp. 23--26, and A.7, PDF pp. 45--47.
The feature flow is the explicit Frobenius-gradient equation (A.17).
The continuous-linear-map norm is the Euclidean operator norm.
-/
noncomputable section
open MeasureTheory
namespace FeatureDistortion
abbrev Vec (d : ℕ) := EuclideanSpace ℝ (Fin d)
abbrev Features (d k : ℕ) := Vec d →L[ℝ] Vec k
def weights {d k : ℕ} (B : Features d k) (v : Vec k) : Vec d := B.adjoint v
def residual {n d k : ℕ} (X : Vec d →L[ℝ] Vec n) (Y : Vec n)
(v : Vec k) (B : Features d k) : Vec n := X (weights B v) - Y
def trainingLoss {n d k : ℕ} (X : Vec d →L[ℝ] Vec n) (Y : Vec n)
(v : Vec k) (B : Features d k) : ℝ := ‖residual X Y v B‖ ^ 2
def headGradient {n d k : ℕ} (X : Vec d →L[ℝ] Vec n) (Y : Vec n)
(v : Vec k) (B : Features d k) : Vec k :=
(2 : ℝ) • B (X.adjoint (residual X Y v B))
def featureGradient {n d k : ℕ} (X : Vec d →L[ℝ] Vec n) (Y : Vec n)
(v : Vec k) (B : Features d k) : Features d k :=
(2 : ℝ) • InnerProductSpace.rankOne ℝ v (X.adjoint (residual X Y v B))
structure Trajectory (d k : ℕ) where
head : ℝ → Vec k
features : ℝ → Features d k
def IsFineTuningFlow {n d k : ℕ} (X : Vec d →L[ℝ] Vec n) (Y : Vec n)
(v₀ : Vec k) (B₀ : Features d k) (γ : Trajectory d k) : Prop :=
γ.head 0 = v₀ ∧ γ.features 0 = B₀ ∧
∀ t : ℝ, 0 ≤ t →
HasDerivWithinAt γ.head (-headGradient X Y (γ.head t) (γ.features t))
(Set.Ici 0) t ∧
HasDerivWithinAt γ.features (-featureGradient X Y (γ.head t) (γ.features t))
(Set.Ici 0) t
def IsLinearProbingFlow {n d k : ℕ} (X : Vec d →L[ℝ] Vec n) (Y : Vec n)
(v₀ : Vec k) (B₀ : Features d k) (v : ℝ → Vec k) : Prop :=
v 0 = v₀ ∧ ∀ t : ℝ, 0 ≤ t →
HasDerivWithinAt v (-headGradient X Y (v t) B₀) (Set.Ici 0) t
def rowSpace {d n : ℕ} (X : Vec d →L[ℝ] Vec n) : Submodule ℝ (Vec d) :=
LinearMap.range X.adjoint.toLinearMap
def OrthonormalRows {d k : ℕ} (B : Features d k) : Prop :=
B.comp B.adjoint = ContinuousLinearMap.id ℝ (Vec k)
/-- In the stated dimension regime this is positivity of the smallest
principal-angle cosine, rather than merely a nonzero projection. -/
def VisibleOn {d k : ℕ} (B : Features d k) (S : Submodule ℝ (Vec d)) : Prop :=
Function.Injective (fun v : Vec k => S.starProjection (B.adjoint v))
def balance {d k : ℕ} (v : Vec k) (B : Features d k) : Vec k →L[ℝ] Vec k :=
InnerProductSpace.rankOne ℝ v v - B.comp B.adjoint
def alignmentError {k : ℕ} (v₀ u : Vec k) : ℝ :=
|(inner ℝ v₀ u) ^ 2 - (inner ℝ u u) ^ 2|
/-- The uncentered second moment, not the centered covariance operator. -/
def secondMoment {d : ℕ} (μ : Measure (Vec d)) : Vec d →L[ℝ] Vec d :=
∫ x, InnerProductSpace.rankOne ℝ x x ∂μ
structure OODLaw (d : ℕ) where
measure : Measure (Vec d)
isProbability : IsProbabilityMeasure measure
finiteSecondMoment : Integrable (fun x : Vec d => ‖x‖ ^ 2) measure
positiveSecondMoment : ∀ w : Vec d, w ≠ 0 →
0 < inner ℝ w (secondMoment measure w)
def oodLoss {d k : ℕ} (D : OODLaw d) (w : Vec d) (v : Vec k)
(B : Features d k) : ℝ :=
∫ x, (inner ℝ (weights B v - w) x) ^ 2 ∂D.measure
def gaussianHead (k : ℕ) (σ : ℝ) : Measure (Vec k) :=
(ProbabilityTheory.stdGaussian (Vec k)).map (fun z => σ • z)
structure Problem (n d k : ℕ) where
data : Vec d →L[ℝ] Vec n
optimalFeatures : Features d k
rotation : Vec k ≃ₗᵢ[ℝ] Vec k
optimalHead : Vec k
def initialFeatures {n d k : ℕ} (P : Problem n d k) : Features d k :=
P.rotation.toLinearIsometry.toContinuousLinearMap.comp P.optimalFeatures
def alignedHead {n d k : ℕ} (P : Problem n d k) : Vec k :=
P.rotation P.optimalHead
def targetWeights {n d k : ℕ} (P : Problem n d k) : Vec d :=
weights P.optimalFeatures P.optimalHead
def labels {n d k : ℕ} (P : Problem n d k) : Vec n :=
P.data (targetWeights P)
def Admissible {n d k : ℕ} (P : Problem n d k) : Prop :=
0 < k ∧
k ≤ Module.finrank ℝ (rowSpace P.data) ∧
Module.finrank ℝ (rowSpace P.data) + k < d ∧
OrthonormalRows P.optimalFeatures ∧
P.optimalHead ≠ 0 ∧
VisibleOn (initialFeatures P) (rowSpace P.data) ∧
VisibleOn (initialFeatures P) (rowSpace P.data)ᗮ
end FeatureDistortion
Read-back
What the Lean code literally says, in plain math · gpt-6
Vec. For each natural number , is the real Euclidean space with coordinates indexed by , with its usual inner product and norm. The case is included and consists only of the zero vector.
Features. For natural numbers , is the space of continuous real-linear maps . There is no rank or normalization assumption. If either dimension is zero, this space consists only of the zero map.
weights. For natural numbers , a continuous real-linear map , and , the weight vector is , where is the Euclidean adjoint. Zero dimensions are permitted; the weight vector is zero if or .
residual. For natural numbers , continuous real-linear maps and , and vectors and , the residual is . All dimensions may be zero; the residual is zero if and is if or . There is no required relation between the arguments.
trainingLoss. For natural numbers , continuous real-linear maps and , and vectors and , the training loss is . There is no normalization by or factor of . If it is zero; if or it is .
headGradient. For natural numbers , continuous real-linear maps and , and vectors and , this definition assigns the vector , where the adjoints are Euclidean. There are no further hypotheses. The vector is zero if any of the dimensions is zero.
featureGradient. For natural numbers , continuous real-linear maps and , and vectors and , this definition assigns the continuous real-linear map from to . Thus the rank-one map takes an inner product with and multiplies by that scalar. No dimension is required to be positive; the map is zero if any of is zero.
Trajectory. For natural numbers , a trajectory is a pair of functions and , called its head and features, respectively; denotes continuous real-linear maps. The structure itself imposes no continuity, differentiability, initial condition, or differential equation on these functions. Both are defined at all real times, and zero dimensions are permitted.
IsFineTuningFlow. For natural numbers , continuous real-linear maps and , vectors and , and a pair of functions and , this predicate means , , and, for every real , existence of derivatives within equal to and . The latter is a derivative in the space of continuous linear maps. At zero, the derivatives are within the half-line. No conditions apply at negative times. Zero dimensions are allowed.
IsLinearProbingFlow. For natural numbers , continuous real-linear maps and , vectors and , and a function , this predicate means and existence, at every real , of a derivative within equal to . The map is fixed. Values at negative times are unconstrained, and zero dimensions are included.
rowSpace. For natural numbers and a continuous real-linear map , this definition assigns the subspace of , where is the Euclidean adjoint. It is the zero subspace if , , or .
OrthonormalRows. For natural numbers and a continuous real-linear map , this predicate means , equivalently for every . It holds for the unique map when ; it cannot hold when .
VisibleOn. For natural numbers , a continuous real-linear map , and a real linear subspace , this predicate means that is injective, where is orthogonal projection: equality of these projections for any implies . If this holds; if and it cannot hold. Zero dimensions are included.
balance. For natural numbers , a vector , and a continuous real-linear map , the balance is the endomorphism of sending to , namely . No normalization is required. It is the zero endomorphism if , and its second summand is zero if .
alignmentError. For a natural number and vectors , the alignment error is . It vanishes exactly when or . No nonzero assumption is imposed. If , including when , the error is zero for every .
secondMoment. For a natural number and any measure on , this definition assigns the operator-valued Bochner integral , where . It is an uncentered second moment. There is no probability or integrability assumption in this definition; the total Bochner integral is zero if its integrand is not integrable. For the operator is zero.
OODLaw. For a natural number , an OOD law consists of a probability measure on , the hypothesis that is integrable with respect to , and the hypothesis that for every nonzero , where and . There is no mean-zero assumption. For , the positivity condition is vacuous and the probability measure is concentrated at the sole zero vector.
oodLoss. For natural numbers , a probability measure on with integrable squared norm and for every nonzero , a target , a vector , and a continuous real-linear map , this definition assigns . Here , with , and is the Euclidean adjoint. If the loss is zero; if it is .
gaussianHead. For a natural number and any real number , this definition assigns the pushforward of standard Gaussian measure on Euclidean under . Positive, negative, and zero are all allowed. For this is the point mass at zero; for it is the point mass at the only vector for every .
Problem. For natural numbers , a problem consists of continuous real-linear maps and , called its data and optimal features; a real-linear isometric bijection , called its rotation; and a vector , called its optimal head. No other conditions are imposed on these fields. In particular, positive determinant is not required of . Zero dimensions are included.
initialFeatures. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the initial feature map is . It does not depend on or and requires no admissibility hypothesis. If or , it is zero.
alignedHead. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the aligned head is . It does not depend on or and requires no admissibility hypothesis. It is zero if , including when .
targetWeights. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the target vector is . It does not depend on or and requires no admissibility hypothesis. It is zero if or .
labels. For natural numbers and a problem with continuous real-linear maps and , a real-linear isometric bijection , and , the label vector is . It does not depend on and requires no admissibility hypothesis. It is zero if any of is zero.
Admissible. For natural numbers and a problem consisting of continuous real-linear maps and , a real-linear isometric bijection , and , let , , and . Admissibility is the conjunction , , , , , injectivity of , and injectivity of , both on , where denotes orthogonal projection. Each injectivity requirement says equality of the displayed projections of two vectors implies equality of the vectors. These hypotheses exclude zero dimensions and require and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.