Initialization And Nullspace Dependence

Why Initialization Matters

In overparameterized linear regression, there may be many coefficient vectors that fit the observed responses exactly. Gradient descent does not generally choose among them without reference to its starting value. The key geometric fact is that every gradient is in the row space of the design matrix. Consequently, updates can change the row-space component of the coefficients but cannot change the component in the design nullspace.

This tutorial derives that dependence for full-batch gradient descent on squared loss. The result separates two parts of the limit: a particular interpolator determined by the data, and the nullspace component inherited from initialization. We focus on exact interpolation, not on the spectral time course of the iterates.

Setup and Definitions

Let \(X\in\mathbb R^{n\times p}\) be a fixed design matrix and \(y\in\mathbb R^n\) a response vector. Assume \(n\leq p\) and \(X\) has full row rank \(n\). These assumptions ensure that \(XX^\top\) is invertible and that every response vector \(y\) can be interpolated. For \(\beta\in\mathbb R^p\), use the squared loss

The factor \(1/2\) makes its gradient \(\nabla\mathcal L(\beta)=X^\top(X\beta-y)\). Full-batch gradient descent with step size \(\eta>0\) and initialization \(\beta_0\) is the sequence

A coefficient vector in \(\mathcal N(X)\) contributes zero to every fitted value on the observed design, because \(Xz=0\). The projector formulas follow from full row rank: \(P_{\mathcal R}\) is symmetric and idempotent, its image is contained in \(\mathcal R(X^\top)\), and \(P_{\mathcal R}X^\top u=X^\top u\) for every \(u\in\mathbb R^n\). Thus it is the orthogonal projector onto that row space.

The Limit from a Nonzero Initialization

The minimum-Euclidean-norm interpolator is

Indeed, it interpolates because \(X\widehat\beta_{\min}=y\), and it lies in the row space. Any other interpolator differs from it by a vector in the nullspace, orthogonal to the row space, so adding a nonzero such vector increases the squared norm.

Proof. Write \(r_k=X\beta_k-y\) for the residual vector. Multiplying the gradient descent update by \(X\) and subtracting \(y\) gives

The matrix \(XX^\top\) is symmetric positive definite. Its eigenvalues \(\lambda\) satisfy \(0<\lambda\leq\lambda_{\max}(XX^\top)\). The step-size condition implies \(-1<1-\eta\lambda<1\) for each eigenvalue. By diagonalizing \(XX^\top\), every eigencomponent of \(r_k\) is multiplied at each step by a factor with absolute value less than one. Therefore \(r_k\to0\), so the fitted values converge to \(y\).

For the coefficient limit, repeatedly substitute the update to obtain

The same eigenvalue condition ensures that the matrix geometric sum converges. Since \(XX^\top\) is invertible,

For example, multiplying the finite sum on the left by \(XX^\top\) gives \(I-(I-\eta XX^\top)^k\), which tends to \(I\); invertibility then gives the stated limit. Substituting this limit into the expression for \(\beta_k\) yields

Finally, each update is a multiple of a vector in \(\mathcal R(X^\top)\). Hence \(P_{\mathcal N}\beta_{k+1}=P_{\mathcal N}\beta_k\), and induction gives \(P_{\mathcal N}\beta_k=P_{\mathcal N}\beta_0\) for every \(k\). This proves both claims. \(\square\)

The theorem gives a precise qualification to the minimum-norm conclusion: gradient descent reaches the minimum-norm interpolator if and only if \(P_{\mathcal N}\beta_0=0\). A zero initialization is one way to ensure this, but it is not necessary; any initialization lying in the row space also suffices. An arbitrary nonzero initialization does not, in general, lead to the minimum-norm solution.

Worked Consequences of Nullspace Dependence

Common Mistake and Practical Meaning

A common mistake is to reason, “Gradient descent converges to an interpolator, so it must converge to the minimum-norm interpolator.” Interpolation alone does not imply minimum norm: when \(p>n\), a nullspace vector can be added to any interpolator without changing its training fit. The correction is to check initialization. Under the theorem's assumptions, minimum norm follows when the initial nullspace projection is zero; otherwise the projection remains in the limit.

This distinction matters when interpreting fitted coefficients and predictions. Two runs with the same design, responses, and step size can reach different interpolating coefficient vectors if their initializations have different nullspace components. Those vectors agree on the observed design but need not agree at new design points. Thus exact training fit does not by itself specify a unique fitted function away from the training data.