Gradient Descent Selects The Minimum-Norm Solution

Why the Optimization Path Matters

When a linear system has more coefficients than independent equations, it can have many exact solutions. Fitting the data perfectly therefore does not, by itself, say which solution an optimization algorithm will produce. The choice matters in statistical learning: among solutions with the same training loss, their coefficient vectors can have different Euclidean norms and make different predictions away from the observed design.

For squared loss, gradient descent has a precise selection rule when it starts at zero. Under a suitable step size, its iterates converge to the solution with smallest Euclidean norm. The conclusion concerns both the objective and the initialization: the loss has many minimizers, while the optimization path chooses one particular minimizer.

Setup and Definitions

Let \(A\in\mathbb{R}^{n\times p}\), where \(p>n\), and let \(b\in\mathbb{R}^n\). Consider the squared loss

Assume the system \(Aw=b\) is consistent: at least one \(w\) satisfies it. Consistency does not require the rows of \(A\) to be linearly independent. Write \(r=\operatorname{rank}(A)\), and let \(\|A\|_{\mathrm{op}}\) denote the largest singular value of \(A\).

The gradient is \(\nabla L(w)=A^\top(Aw-b)\). With a fixed step size \(\eta>0\), gradient descent from zero is the sequence

The factor \(1/2\) in the definition of \(L\) makes this gradient expression direct. Using the unscaled loss \(\|Aw-b\|_2^2\) would multiply the gradient by \(2\), so its step-size condition would need to be adjusted accordingly.

Three Worked Examples

Main Result and Proof

To prove the claim, take a singular value decomposition restricted to the nonzero singular values:

The columns of \(U_r\) and \(V_r\) are orthonormal, and \(s_j\leq\|A\|_{\mathrm{op}}\). Consistency means \(b\) lies in the column space of \(A\), so \(b=U_rc\), where \(c=U_r^\top b\).

First, \(w_t\) lies in the span of the columns of \(V_r\) for every \(t\). It is true at \(t=0\), and each update adds a vector in the range of \(A^\top\), which is that span. Write \(w_t=V_rz_t\). Substituting into the update, and using \(A^\top=V_r\Sigma_rU_r^\top\), gives

Consequently, each coordinate obeys

Solving this scalar recurrence yields

The step-size assumption gives \(0<\eta s_j^2<2\), so \(|1-\eta s_j^2|<1\). Therefore \(z_{j,t}\to c_j/s_j\) for each \(j\), and

It remains to verify that this limit is the minimum-norm solution, rather than merely some solution. Denote it by \(w_*\). Then \(Aw_*=U_rU_r^\top b=b\), since \(b\) lies in the column space of \(A\). Any other solution \(w\) can be decomposed uniquely as \(w=V_ra+v\), where \(v\) is orthogonal to every column of \(V_r\). Because \(Av=0\), the equation \(Aw=b\) forces \(\Sigma_ra=U_r^\top b\), hence \(a=\Sigma_r^{-1}U_r^\top b\). Orthogonality gives

with equality only when \(v=0\). This proves both minimality and uniqueness, and completes the proof. \(\square\)

What Converges, and What the Step Size Guarantees

The theorem gives convergence of the coefficients, not just a vanishing training loss. In fact, the same coordinate calculation shows that the residual converges to zero. Since \(Aw_t-b=U_r(\Sigma_rz_t-c)\), its \(j\)th coordinate in the \(U_r\) basis is \(-c_j(1-\eta s_j^2)^t\). Define \(q=\max_{1\leq j\leq r}|1-\eta s_j^2|\), which is less than one. Then

The inequality uses \(\sum_j c_j^2=\|b\|_2^2\), which holds because \(b=U_rc\) and \(U_r\) has orthonormal columns. This bound describes convergence for a fixed finite-dimensional system; it does not claim that the rate is uniform over matrices whose nonzero singular values can become arbitrarily small.

The strict step-size condition also matters. If a step size is too large, a coordinate associated with a large singular value can fail to contract. At the boundary \(\eta=2/\|A\|_{\mathrm{op}}^2\), a coordinate at the largest singular value has multiplier \(-1\), so it need not converge. The theorem uses a strict inequality to ensure contraction in every nonzero singular direction.

Why Zero Initialization Selects This Solution

The decisive geometric fact in the proof is that every gradient lies in the row space of \(A\), the span of the vectors seen by the data. Starting at zero keeps the whole sequence in that row space. The minimum-norm solution is precisely the solution in that space: any additional component orthogonal to it leaves \(Aw\) unchanged while increasing the squared norm.

This explains why exact fitting alone is not enough to identify the algorithm's limit. The data specify a set of solutions; the initialization and update determine which member is reached. Here the initialization is zero, and the update never adds a component in the null space of \(A\). These facts, combined with convergence, yield minimum-norm selection.

Common Pitfalls

• Claiming every interpolator is the limit. The reasoning “the loss reaches zero, so the algorithm has found the minimum-norm solution” skips the selection argument. The correction is to show that the iterates stay in the row space and then establish convergence.
• Assuming consistency means full row rank. Consistency only means that at least one solution exists. Rows can be dependent, as in the third example; the proof uses the nonzero singular directions and still applies.
• Ignoring the step size. Convergence does not follow for an arbitrary positive step size. The condition \(0<\eta<2/\|A\|_{\mathrm{op}}^2\) ensures that every nonzero singular direction contracts.
• Forgetting the loss scaling. The update here is for \(L(w)=\frac12\|Aw-b\|_2^2\). Removing the factor \(1/2\) doubles the gradient, so the same numerical step size does not give the same iteration.