Motivation
A learning problem has at least two geometric choices. The representation decides which predictions can be expressed. The fitting rule decides which of those predictions is preferred by the data and the penalty or algorithm. Kernel methods make the first choice through inner products of feature vectors. ReLU networks build functions by combining hinges. Overparameterized linear models show especially clearly why the second choice remains necessary: many parameter vectors can fit the same training observations exactly.
These choices should not be confused with a guarantee of generalization. A class that can approximate every continuous function on an interval may still be difficult to fit from limited observations. A minimum-norm interpolant is an identifiable choice among exact fits, but its population behavior depends on features, target, sampling, and noise. The purpose here is to prove manageable statements about representation and selection, while identifying the statistical questions they leave open.
We begin with kernels because they turn a feature-space problem into a finite matrix problem. We then give a constructive one-dimensional neural approximation argument rather than merely invoking universality. Finally, a singular-value calculation connects overparameterization to the implicit choice made by gradient descent. These results do not amount to a complete theory of learning with neural networks.
Definitions
Definition 3.1.1
(Positive semidefinite kernel and reproducing space)
A real kernel on a set is a symmetric function . It is positive semidefinite when, for every finite selection and real coefficients ,
A reproducing-kernel Hilbert space is a Hilbert space of functions with and . In particular .
The finite matrix is the Gram matrix. Positive semidefiniteness permits zero eigenvalues; it does not mean every Gram matrix is invertible. A feature map produces a kernel , since the quadratic form becomes . For example on the real line has feature map . The factor is needed to obtain the middle coefficient two.
In the kernel results below, assume a reproducing space with this kernel is given. The general construction of a reproducing space from every positive semidefinite kernel is a separate foundational theorem, not proved here. Working with a known finite feature map already gives concrete instances of all the arguments.
Define , the ReLU function. A one-hidden-layer scalar-input expression with an affine term has form . If an architecture does not allow an affine skip term, the identity implements the linear part using two additional units. Constants require an output bias. Declaring these conventions avoids silently changing what the network may represent.
For a matrix , the model is overparameterized in the linear-algebraic sense when is nontrivial, for instance when . Distinct parameters can then produce identical observed predictions. Exact interpolation additionally requires ; having more parameters than observations alone does not guarantee this.
Theorem/Proposition
Theorem 3.1.2
(Representer principle and kernel ridge equations)
Let , , and . The objective
has a unique minimizer in . It belongs to and can be written
This system has a unique solution. If is singular, the function can nevertheless have other coefficient representations.
Theorem 3.1.3
(Constructive approximation by ReLU hinges)
Let partition , and let linearly interpolate a continuous function at these knots. Put . Then
If and is -Lipschitz, then . Every continuous on can therefore be uniformly approximated by such networks as the mesh tends to zero, even without a Lipschitz assumption.
The final sentence uses uniform continuity, not an assumption that every continuous function is Lipschitz. The stated rate applies only in the Lipschitz case. The representation concerns one input dimension; it supplies no dimension-independent complexity guarantee for multivariable targets.
Proof sketch or proof idea
The kernel proof first reduces the search to the finite span and only then solves for coefficients.
Proof
(Orthogonal decomposition, existence, then stationarity)
Since is finite dimensional, it is closed. Decompose any orthogonally as , with and . The reproducing property gives for every training point. Thus and have identical training loss, but . A positive penalty makes optimal. This argument also proves the representer principle for any empirical loss depending only on those evaluations, provided a minimizer exists and the penalty increases strictly with the norm.
For the squared objective, existence now follows by minimizing a continuous coercive function over the finite-dimensional space : , so a minimizing sequence remains bounded. A convergent subsequence attains the infimum. Strict convexity of the squared norm, together with convexity of the loss, gives a unique function minimizer.
Differentiating in every Hilbert-space direction gives the stationarity equation
Choose . Evaluating the resulting representation at the data gives . Conversely, a solution to this system satisfies stationarity and hence minimizes the convex objective. The matrix is positive definite because . Notice that differentiating directly yields . Canceling a singular would be an invalid proof. The Hilbert-space argument avoids that cancellation.
Proof X-ray
What the reproducing property buys, and where the penalty is needed
The reproducing property is used at one point: it turns into , so the component orthogonal to the data sections is invisible to the loss. Everything else is Hilbert-space geometry, and the reduction does not depend on the squared loss. The penalty then plays two separate roles. Strict monotonicity in the norm makes optimal, which is the representer principle; the bound makes minimizing sequences bounded, which gives existence and, with strict convexity, uniqueness of the function.
The key move for the coefficient equation is to differentiate in the infinite-dimensional space rather than in . The Hilbert-space gradient is , and choosing to make it vanish identically yields without canceling . When the matrix can be singular and the canonical system can fail, as the counterexample below shows.
The ReLU proof is a direct verification followed by a convex-combination estimate.
Proof
(Slope changes at the knots and a weighted error)
For the ReLU formula, on the first interval every hinge is zero and the expression has the correct initial value and slope . Crossing changes the slope by . The function remains continuous, so it matches the linear interpolant on every interval. For the error, write with . Interpolation and the triangle inequality yield
For a general continuous target, both endpoint differences are at most its modulus of continuity , so the same weighted expression is at most . Uniform continuity on a compact interval makes this tend to zero. The construction proves existence of suitable weights. It says nothing about whether a specified training algorithm finds them from a specified sample.
Counterexample mode
Without a positive penalty the canonical system can be inconsistent
Claim: the minimizer of is with also when . Take , , , , as in the first worked example. With the system is , and can never equal , so it has no solution. Yet a minimizer exists: the functions are , and is minimized at . The repair is either , or, at , the normal equations , which here reduce to .
A precise implicit choice in an overparameterized model
The third statement concerns an algorithm rather than a function class.
Proposition 3.1.4
(Gradient descent selects the minimum-norm least-squares solution)
Let be nonzero, , , and . Gradient descent from any converges to . In particular, from it converges to , the unique least-squares solution of smallest Euclidean norm.
Proof
(Singular coordinates contract separately)
Start with . Use a compact singular-value decomposition , retaining only its positive singular values . The gradient always belongs to , so every iterate stays in that subspace. Its coordinate obeys
Every multiplier has magnitude below one, and hence . Thus . Its predictions equal the orthogonal projection , so it is a least-squares solution even when interpolation is impossible. All other least-squares solutions add a vector from , orthogonal to . Pythagoras proves that this limit is the unique smallest-Euclidean-norm solution.
With an arbitrary initialization, the gradient has no null-space component, so for every , while the component in obeys the same recurrence. The limit is .
Counterexample mode
A step size that is too large never settles
Claim: from , gradient descent converges to for every positive step size. Take and , as in the third worked example, so and the theorem needs . With the gradient is , and the iterates are : the multiplier has magnitude one, so the sequence oscillates. For the multiplier exceeds one in magnitude and the iterates diverge. The repair is the stated bound , which puts every multiplier strictly between and .
Minimum norm is therefore a statement about the objective, Euclidean parameter geometry, and zero initialization together. Reparameterizing the features can change which predictor is selected.
Explicit and implicit regularization
Ridge regression makes its preference explicit by charging for the squared norm. As its positive penalty becomes small, finite-dimensional ridge coefficients approach the minimum-norm least-squares parameter in a fixed feature geometry. This follows coordinate by coordinate from the singular-value formula: a positive singular direction is multiplied by its singular value divided by the sum of its square and the appropriately scaled penalty, while null directions are zero. The limiting operation keeps the feature map fixed; changing the features at the same time is a different problem.
Concept lensAlgebraic
Kernel ridge as ridge regression on features
Suppose with , and let have rows , so . Ridge regression for with the same normalization solves . The identity shows that with , so both systems give the same predictor. One is , the other ; in the first worked example, gives , the same .
Zero-initialized gradient descent also chooses minimum norm in the linear model, but it does so through its trajectory. At a finite stopping time, a direction with a small singular value has not yet reached its least-squares limit. The recurrence shows its progress factor is one minus a power of the corresponding contraction multiplier. Thus early stopping changes different singular directions by different amounts. This observation motivates a comparison with regularization, without claiming that one stopping time is exactly equivalent to a single ridge penalty in every direction. The two procedures can have similar purposes while producing different fitted functions.
Worked examples
Worked example 3.1.5
(A singular Gram matrix with a unique ridge function)
Use , observations , , labels , and . Then has rows and and has rank one. Since , the ridge system has matrix with rows and , whose determinant is six. It gives . The fitted function is . Adding any multiple of to represents the same function, although those added coefficients do not solve the displayed canonical ridge system. Directly minimizing gives derivative and confirms .
Worked example 3.1.6
(Approximating a square with hinges)
For on , knots give slopes and . The formula gives . On , , whose maximum is at ; symmetry gives the same maximum on the negative interval. The Lipschitz constant yields the valid but looser bound one. On an interval of length , direct expansion shows that the linear interpolant of a square exceeds the square by . Halving the mesh to therefore reduces the exact maximum to . More hinges improve approximation here, but the construction has used target values at the knots.
Worked example 3.1.7
(Two parameters and one observed prediction)
Let and . Every vector interpolates. Its squared norm is , minimized at . Gradient descent on from zero preserves equality of the two coordinates and converges to that point for . In contrast, initialization already fits and remains there, with squared norm ten. Both models fit the observed feature vector exactly, yet at a new feature vector their predictions are zero and four. Training interpolation does not decide which is closer to an unknown population target.
Common mistakes
Common mistake
(Checking a few similarities instead of positive semidefiniteness)
A positive-looking formula need not be a positive semidefinite kernel. The requirement concerns all coefficient vectors and all finite point selections. For example fails already at the one-point selection , whose Gram entry is . Checking a few pairwise similarities is insufficient, while a valid feature-map factorization proves the condition at once.
Common mistake
(Changing the loss normalization without changing the system)
The regularization coefficient depends on the loss normalization. Our average squared loss has factor , so the linear system contains ; for the unnormalized loss it becomes . Using one system with the other objective changes the effective penalty by a factor . Also, a singular Gram matrix is compatible with a unique regularized function; uniqueness of coefficients and uniqueness of functions are different claims.
Approximation is an existence question about functions. Optimization asks whether an algorithm can find useful weights, and generalization asks about fresh data. The hinge construction proves the first. The linear minimum-norm calculation proves a particular algorithmic selection statement. Neither proves generalization for arbitrary neural networks or arbitrary interpolating estimators. Those further claims need additional assumptions and arguments.
Summary
Kernel fitting uses a finite span because orthogonal components change no observed prediction and increase the penalty. ReLU hinges construct piecewise linear approximants by recording slope changes. Overparameterized least squares separates observed predictions from invisible null-space components, exposing the role of initialization. Together these calculations give concrete tools for representation and selection while leaving their statistical limits visible.
Exercises
Quick check
(If and are positive semidefinite kernels and , prove that is positive semidefinite, and give a feature map when both original feature maps are finite dimensional.)
Solution · Answer
Every Gram quadratic form is a nonnegative weighted sum of two nonnegative forms, proving the condition and symmetry. If the original maps are and , concatenate and . Their inner product is the required kernel, including cases where one coefficient is zero.
Quick check
(Interpolate on using knots . Find its hinge representation and uniform interpolation error.)
Solution · Answer
The initial value is , the slopes are and , and their jump is two. Thus . This equals the target on both sides of its only corner, so the uniform error is zero. The corner need not be differentiable for interpolation or the representation to work.
Quick check
(For and , start gradient descent at . Find its limit and explain why the zero-initialization minimum-norm conclusion does not apply.)
Solution · Answer
The initialization already satisfies , so its gradient vanishes and every iterate is . Its null-space component is , which is retained; adding this to gives the same answer. Its norm exceeds that of the zero-initialization limit.
Quick check
(For the square target on , how many equal intervals suffice to make the exact uniform interpolation error at most ? State the number of interior hinges in the displayed architecture.)
Solution · Answer
With intervals, and the exact maximum error is . Therefore suffices, with nine interior hinges. The expression also contains an affine term; if that term is forbidden, its linear part needs the additional ReLU implementation described earlier.