Stochastic Gradient Descent And Interpolating Solutions

Why the Optimization Path Matters

When there are more coefficients than observations, a linear model can fit the observed responses exactly in many different ways. The training loss alone does not identify which interpolating coefficient vector an algorithm will return. The update rule, step size, sampling scheme, and initialization all matter to the path; together, they determine what can be selected when the algorithm converges.

For a consistent underdetermined linear problem, full-batch gradient descent and single-example stochastic gradient descent have a useful common feature: when initialized at zero, their updates stay in the row space of the design matrix. If they converge to an interpolator, that row-space constraint makes the limit the minimum-Euclidean-norm interpolator. But their paths are different. Stochastic updates fluctuate away from a solution, and a step size that is too large can prevent convergence.

Setup: A Consistent Underdetermined Problem

Let \(X\) be an \(n\times p\) design matrix with rows \(x_i^\top\), where \(p>n\), and let \(y\in\mathbb{R}^n\). Assume \(X\) has full row rank and the responses are exactly consistent with the linear model: there is at least one \(\theta\in\mathbb{R}^p\) such that \(X\theta=y\). Full row rank ensures that every \(y\in\mathbb{R}^n\) is in the range of \(X\), so consistency is automatic under this assumption.

Write \(H=X^\top X/n\), and let \(\mathcal{R}\) be the row space of \(X\), with \(\mathcal{N}\) its null space. Since \(p>n\) and \(X\) has full row rank, \(\mathcal{N}\) has positive dimension. The minimum-norm interpolator, denoted \(\theta^\dagger\), lies in \(\mathcal{R}\); every other interpolator is of the form \(\theta^\dagger+v\) for some \(v\in\mathcal{N}\). Define \(\mu>0\) and \(L>0\) as the smallest and largest positive eigenvalues of \(H\), respectively, and set \(R^2=\max_i\|x_i\|^2\).

Full-Batch and Stochastic Updates

Full-batch gradient descent uses every observation at each step:

For \(0<\eta<2/L\), the positive-eigenvalue components of the error contract, while the null-space component is unchanged. In particular, starting from zero gives a limit in \(\mathcal{R}\); if that limit interpolates, it must be \(\theta^\dagger\). This is the deterministic gradient-descent selection property.

Single-example SGD samples an index \(i_t\) uniformly from \(\{1,\ldots,n\}\), independently at each iteration, and updates

Conditional on the current iterate, the stochastic gradient is unbiased: \(E[\nabla f_{i_t}(\theta_t)\mid\theta_t]=\nabla F(\theta_t)\). Unbiasedness does not mean each realized update equals the full-batch update. The sampled gradient can point in a different direction, so the path can depend strongly on which observations are drawn and in what order.

Why Sampling Noise Disappears at an Interpolator

The stochastic gradient can be written as the observation-specific residual multiplied by the corresponding data vector. At any interpolator, every residual is zero. Consequently, every observation-specific gradient is zero—not merely their average. This is different from a problem whose optimum has nonzero residuals, where individual stochastic gradients may remain random at the optimum.

A Step-Size Bound for Mean-Square Convergence

The vanishing of noise at a solution is helpful, but it does not ensure that arbitrary step sizes reach one. The following result gives a sufficient fixed-step condition. Its assumptions make the sampling scheme and the space in which convergence is claimed explicit.

Proof. Every update is a multiple of \(x_{i_t}\), which belongs to \(\mathcal{R}\). Thus an iterate initialized in \(\mathcal{R}\) remains there. Let \(e_t=\theta_t-\theta^\dagger\). Since \(X\theta^\dagger=y\), the residual for observation \(i\) at \(\theta_t\) is \(x_i^\top e_t\), and the update gives \[ e_{t+1}=e_t-\eta x_{i_t}x_{i_t}^\top e_t. \] Conditioning on \(e_t\), expanding the squared norm, and using uniform sampling yields

Since \(\|x_i\|^2\leq R^2\), the final term is at most \(\eta^2R^2 e_t^\top H e_t\). Hence

For \(e_t\in\mathcal{R}\), the positive eigenvalues of \(H\) are at least \(\mu\), so \(e_t^\top H e_t\geq\mu\|e_t\|^2\). The step-size condition makes \(2\eta-\eta^2R^2>0\), giving the one-step bound with factor \(q=1-\mu(2\eta-\eta^2R^2)\). Also \(\mu\leq R^2\), because the largest eigenvalue of \(H\) is at most \(\operatorname{tr}(H)=n^{-1}\sum_i\|x_i\|^2\leq R^2\). The function \(2\eta-\eta^2R^2\) is at most \(1/R^2\), so \(q\geq 1-\mu/R^2\geq0\); and \(q<1\). Taking expectations and iterating the one-step inequality proves the displayed bound. Its right side tends to zero, establishing mean-square convergence. \(\square\)

The theorem gives a sufficient bound, not a necessary one: some datasets and sampling schedules may converge with larger steps. It also describes convergence only when the iterate starts in the row space. If \(\theta_0\) has a null-space component, every update leaves that component unchanged, because \(x_i^\top v=0\) for \(v\in\mathcal{N}\). Under the theorem's other conditions, the corresponding limit is \(\theta^\dagger+P_{\mathcal{N}}\theta_0\), where \(P_{\mathcal{N}}\) is orthogonal projection onto \(\mathcal{N}\). In particular, zero initialization removes this dependence.

What the Algorithms Select—and What They Do Not

Under the theorem's assumptions, SGD does not select a different row-space interpolator from full-batch gradient descent: there is only one interpolator in the row space, namely \(\theta^\dagger\). Sampling changes the route to that solution and the rate or stability of progress, rather than the limit, when convergence holds and initialization is zero. The updates can still vary substantially across runs because their sampled directions differ.

The null-space component is a separate source of solution dependence. No data-gradient update can change it. Thus a nonzero initialization can leave a null-space component in the final interpolator even if the row-space part converges perfectly. This distinction is useful: stochastic sampling variability and initialization-dependent null-space variation are not the same phenomenon.

Common Pitfall

• Wrong reasoning: “SGD has sampling noise, so its gradient must keep fluctuating even after it reaches an interpolator.”
• Correction: For exact interpolation under squared loss, each individual residual is zero, so every individual gradient is zero. Sampling creates gradient variance away from the solution, but not at it.
• Another mistake: Treating \(2/R^2\) as \(2\) when \(R^2=2\). The bound is \(2/2=1\), and the sufficient condition is strict: \(\eta<1\).
• Overstating the result: The bound is sufficient, not necessary; violating it means the theorem no longer guarantees convergence, not that every trajectory must diverge.