Motivation
A kernel method can represent a nonlinear function without writing down all its features. That convenience still leaves a computational object: the matrix of kernel values on the training inputs. If there are inputs, this matrix has entries. A random feature construction replaces it by a product , where has only columns. When is modest, storing the feature matrix and fitting a linear model in its columns can be useful.
This raises three distinct questions. Does the approximation preserve the positive semidefinite geometry needed by kernel methods? How many random features make the approximation accurate on a specified dataset? How does an error in the matrix change the fitted predictor? We will answer these questions with elementary, fully stated bounds. None of the answers alone says how well a learned function predicts fresh observations.
The important randomness here is the feature draw. We first hold the inputs and labels fixed. Thus , the number of observations, and , the number of random features, have different roles. Increasing makes a particular computational approximation more accurate; it does not create additional training observations.
Definitions
Definition 12.1.1
(A scalar random-feature representation)
Let be an input set and a probability space. A real feature is measurable in for each fixed . Assume for every . Define
Choose independently with common law , where , and set
The expectation defining exists by Cauchy–Schwarz. Fix inputs , with repetitions allowed. Define , , and . Each column is one feature draw evaluated at all inputs. The same draws must be used for the training and test feature maps of a single fitted model.
For the concentration theorem assume a known such that, simultaneously for the selected inputs, for -almost every . A bound valid over the whole domain is sufficient, but is stronger than this finite-data assumption. Write and use for Euclidean operator norm. Throughout, denotes the natural logarithm. All probabilities below concern the independent feature draws unless stated otherwise.
Concept lensStructural
The Gram matrix as a second-moment matrix
Put . Then is the second-moment matrix of this random vector, and is its sample second-moment matrix. Positive semidefiniteness, the rank bound and unbiasedness are then the familiar properties of an average of rank-one outer products, and approximating becomes a moment-estimation problem for one random vector in .
Theorem/proposition
Theorem 12.1.2
(Unbiased PSD approximation and finite-data concentration)
Both and are positive semidefinite, and . Entrywise, . Under the boundedness assumption, for every ,
Consequently, if and
then with probability at least the entrywise error is at most and the operator error is at most . Also,
The factor counts entries; it does not assume independence between them. It is acceptable for the displayed upper bound on probability to exceed one: it is then uninformative. A refined count can use symmetry, but we retain the simpler valid constant.
Theorem 12.1.3
(Ridge predictions are stable under PSD Gram perturbations)
Let be any real symmetric PSD matrices, , and . Put and define
For ,
In particular, on the first theorem's event, . These are deterministic perturbation statements conditional on the matrices, without any distributional assumption on the labels.
For , the vector is exactly the training prediction of feature ridge regression minimizing . Indeed, the normal equation is . The unique solution is , as multiplication verifies. The factor already belongs to ; there is no additional division of by in this convention.
Proof sketch or proof idea
Geometry and the meaning of unbiasedness
Proof
(Positive semidefiniteness, rank and unbiasedness)
For any , finite summation and the feature representation give
Thus even a poor sampled approximation remains PSD. The rank bound follows from the number of columns of . Taking the expectation of the average defining each entry proves unbiasedness. This conclusion does not require independence; independence will enter the variance and exponential bounds. Unbiasedness concerns the matrix, not a nonlinear operation such as taking its inverse or fitting a predictor.
The bounded-variable exponential estimate
The concentration step is proved directly rather than by appeal to an unnamed inequality.
Proof
(A tilted-variance bound, then a union bound over entries)
Let a real random variable lie in , and let . Boundedness permits differentiation for every real . Under the tilted probability measure with density proportional to , the second derivative is the variance of . With ,
Since , integrating this second-derivative bound gives for every real . For negative one may integrate along the segment from to zero, giving the same nonnegative quadratic bound.
Fix indices and put . These variables are independent, lie in , and have mean . Their joint exponential moment factors, so for Markov's inequality gives
Choose to obtain . Apply the same argument to and add the two tails. The union bound over the pairs proves the displayed matrix probability. Solving its right side to be at most gives the feature budget, rounded up to an integer when implemented.
For any matrix and unit vector , the triangle inequality followed by Cauchy–Schwarz gives whenever . Summing the squared coordinate bounds proves . For the mean-square statement, independence gives variance of each averaged entry equal to the single-draw variance divided by . Add these variances over entries. Finally , so each variance is at most . Cross-entry covariance is irrelevant because the squared Frobenius norm is a sum of entry squares.
Proof X-ray
Which independence is actually needed?
Three different facts carry the proof, and each uses a different hypothesis. Boundedness, on the selected inputs, is used only through the range of each product , which feeds the tilted-variance bound. Independence of the draws is used only to factor the exponential moment into identical factors; that factorization is what turns one-draw control into a rate in .
Entries of the matrix share these draws and are usually dependent. The final union bound only adds probabilities, so it needs no independence across entries, and this is why the price is the count rather than any covariance calculation. If all columns are copies of one random feature, the factorization over is false and increasing the column count need not improve accuracy. The operator bound is a separate deterministic step and owes nothing to probability.
Passing from matrix error to fitted predictions
Proof
(Resolvent identity and a cancellation for predictions)
PSD implies that every eigenvalue of and is at least . Hence both inverses have norm at most . With and , direct multiplication proves the resolvent identity
Apply this identity to and multiply the three operator bounds to obtain the coefficient estimate. The useful cancellation for predictions is
Their difference is , giving the prediction estimate. This argument does not require the two Gram matrices to have the same eigenvectors, nor does it require the error to be smaller than . Positive regularization ensures invertibility even when or the input list contains duplicates.
The same shift by can also be read eigenvalue by eigenvalue.
Concept lensAlgebraic
Regularization as a spectral buffer
In an eigenvector direction with Gram eigenvalue , training ridge multiplies the corresponding label coordinate by . The positive shift prevents division by a vanishing eigenvalue. The perturbation proof above remains valid without a common eigenbasis; the scalar picture explains why its bounds deteriorate as the regularization parameter approaches zero. It does not justify setting that parameter to zero in the theorem.
Worked examples
Worked example 12.1.4
(A two-point kernel and an exact sampled Gram matrix)
Take . Draw with equal probabilities and define , . Then and . On inputs the exact Gram matrix is .
Draw four features, three with and one with . In this order,
Its eigenvalues are and , both nonnegative. Its entrywise and operator errors are both . If of the draws are constant features, the off-diagonal estimate is while both diagonal entries are exactly one. Since , that off-diagonal entry is unbiased. The event when has probability ; the displayed matrix is a possible outcome, not the mean matrix.
Worked example 12.1.5
(A trigonometric feature and a conservative feature budget)
For real inputs let be uniform on and . The product identity gives
The second term integrates to zero, so the kernel is . Its values can be negative, but its Gram matrices are PSD by the feature representation. Here and . No assumption on the magnitudes of the fixed input coordinates is needed for this bound.
For , , , the sufficient budget for a feature bound is . For this trigonometric feature it is . These are sufficient worst-case budgets, not claims that fewer features must fail. The matrix-norm consequence is only ; a small error in every entry need not be a similarly small operator error.
Worked example 12.1.6
(The same matrix error after ridge fitting)
Return to the two-point example, choose labels and , so . The label vector lies in the eigenvalue-one direction of and the eigenvalue-one-half direction of the sampled Gram matrix. Therefore
The prediction difference has norm . The deterministic operator-error bound uses and yields , which is valid but loose. The generic entrywise consequence is weaker still. A theorem can be useful as a guarantee without predicting the exact observed error. This example isolates the feature randomness: the trained prediction changes even though the inputs and labels are fixed.
Common mistakes
Counterexample mode
Finite second moments of features do not imply exponential concentration
Let have density and put for every . Then and . The feature second moment exists and the kernel is the constant . Its estimate is the average of independent copies of , so it is still unbiased and PSD.
For every integer , the event forces the average to exceed four. Since for ,
This polynomial lower bound eventually exceeds any bound of the form with fixed positive constants . The bounded-feature theorem cannot be retained merely by replacing its hypothesis with a finite feature second moment. Other tail assumptions or robust estimators require separate arguments.
Common mistake
(Extending a finite-list bound to a whole input domain)
A finite dataset is also essential to the particular union-bound conclusion. Here is an extreme bounded example. Let the inputs be all finite subsets of , draw uniformly on , and put . For every fixed finite the feature is zero almost surely, so the true kernel is identically zero. Yet after any draws, choosing makes . Thus the supremum error over this entire input family equals one for every realized draw list. This does not contradict a finite fixed-list theorem: was chosen after seeing the draws. Extending a finite net to a continuum needs additional control such as regularity and a covering argument; boundedness alone supplies no such extension.
If has a sigma-algebra, is jointly measurable, is fixed, and the training inputs are random and independent of the feature draws, one can condition on the inputs and apply the same theorem whenever its bound is valid uniformly for those possible inputs. Averaging the conditional failure probabilities preserves the bound. Inputs selected by inspecting these same feature draws are not covered by that conditioning argument.
Common mistake
(Reading a training-prediction comparison as a test or population guarantee)
The ridge result compares two training prediction vectors on the same data. A new test input requires approximation control of its kernel values against the training inputs as well; finitely many preselected test points can be included in the original fixed list. Even then, kernel approximation compares two predictors. A statement about population risk requires assumptions about observation sampling, the loss, and the training procedure, and an additional statistical argument. Neither an unbiased kernel nor a small training-matrix error establishes generalization by itself.
Summary
A common set of independent random features produces an unbiased PSD Gram approximation. A bounded feature envelope yields an explicit exponential entrywise bound on a fixed finite input list, followed by a conservative operator bound. Positive ridge regularization converts operator error into a deterministic training-prediction comparison. The number of features controls this computational approximation; it does not replace a statistical analysis of learning from observations.
Exercises
Quick check
(In the two-point feature model, compute the exact variance of the off-diagonal estimate for arbitrary . What happens to unbiasedness and concentration if all columns repeat one single random draw, and why can sampling a fresh feature separately for every matrix entry destroy the PSD guarantee?)
Solution · Answer
Every off-diagonal summand is one or minus one with equal probability, hence mean zero and variance one. Independent averaging gives variance . Repeating one draw instead gives an estimate always equal to one or minus one, independent of the stated column count. Its expectation remains zero but its variance remains one, and its absolute error is always one. Independence, or more generally pairwise uncorrelatedness, gives the variance; perfect dependence here destroys the improvement. Other dependence structures need their own analysis.
Entry-specific sampling need not even give symmetry: independently estimated ordered off-diagonal entries in the two-point model can disagree. More strongly, enforcing symmetry still does not ensure PSD in general. Use inputs , draw with independent Rademacher coordinates, and set . Its true Gram matrix is . Estimate each unordered off-diagonal pair using a separate independent feature draw, reflect that estimate across the diagonal, and set the diagonals to one. Every entry is unbiased, yet with positive probability the estimate is
This symmetric matrix is indefinite; its determinant is . Sharing a complete feature vector and taking its outer product preserves PSD for each draw. Sampling entries separately, even symmetrically and without bias, does not.
Quick check
(Let the target Gram matrix be and suppose . Prove that any approximation with columns has operator error at least one. What restriction follows for the entrywise error , and does this refute the concentration theorem?)
Solution · Answer
The rank of is at most , so its nullspace contains a unit vector . Then , which proves operator error at least one. The entrywise-to-operator bound gives , so entrywise error below is impossible in this rank regime. There is no contradiction. In any bounded representation of , the diagonal condition forces . For , our sufficient concentration budget exceeds . Its coarse operator estimate also retains the factor . Low rank, entrywise accuracy and operator accuracy are different requirements.
Quick check
(Fix a test input before sampling. Suppose on the training block, for its kernel values against the training points, and all features at these points are bounded by . Bound in terms of , , , and .)
Solution · Answer
Put . The prediction difference is . The assumptions give , , and . The training-block bound gives , so the ridge theorem gives . Hence
The bound is deterministic on the stated approximation event. Applying the concentration theorem to the enlarged fixed list supplies a probability for that event. Neither step establishes a population-risk bound.
Quick check
(For a single input, let the squared feature be or with equal probabilities. With , label and , compute the expected kernel estimate and the expected ridge prediction, and compare them with the exact values. Which inference does this rule out?)
Solution · Answer
The exact kernel is one, and the estimate is zero or two, so its expectation is indeed one. The exact ridge prediction is . The sampled prediction is zero or , with expected value . An unbiased kernel approximation does not make the fitted prediction unbiased: inversion and matrix multiplication form a nonlinear map of the random Gram matrix. This calculation needs no finite-sample concentration approximation; all expectations are exact.