From Eigenvalue Decay to Effective Dimension

Why the Eigenvalue Sequence Matters

The effective dimension in kernel ridge regression is a regularized trace: each covariance eigenvalue contributes a fraction between zero and one, rather than contributing its full size or being discarded outright. The regularization parameter determines which eigenvalues contribute nearly one and which contribute in proportion to their size. This makes the eigenvalue sequence a direct tool for bounding effective dimension.

The aim here is to make that observation precise. We split the trace at the regularization scale, \(\lambda\), and show that the effective dimension is controlled, up to a factor of two, by two quantities: the number of eigenvalues at least \(\lambda\), and the sum of the smaller eigenvalues divided by \(\lambda\). This is a general bound; its usefulness depends on what is known about the spectrum.

Effective Dimension and Spectral Assumptions

Let \(T\) be a positive, compact, self-adjoint, trace-class covariance operator. Write its eigenvalues, counted with multiplicity, in nonincreasing order as \(\mu_1\geq\mu_2\geq\cdots\geq 0\). Trace class means that \(\sum_{j\geq 1}\mu_j<\infty\). For \(\lambda>0\), the effective dimension is the trace of the regularized operator \(T(T+\lambda I)^{-1}\), where \(I\) is the identity operator.

The spectral formula follows from the spectral decomposition of \(T\): on an eigenvector with eigenvalue \(\mu_j\), the operator \(T(T+\lambda I)^{-1}\) acts by multiplication by \(\mu_j/(\mu_j+\lambda)\). The sum is finite because each term is at most \(\mu_j/\lambda\), and \(\sum_j\mu_j<\infty\). In particular, \(N(\lambda)\leq \operatorname{Tr}(T)/\lambda\). The effective dimension need not be an integer: it counts eigen-directions fractionally according to their size relative to \(\lambda\).

Define the set of eigenvalues above the regularization scale by \(H_\lambda=\{j:\mu_j\geq\lambda\}\), and its complement by \(L_\lambda=\{j:\mu_j<\lambda\}\). Since the eigenvalues are summable and \(\lambda>0\), \(H_\lambda\) contains only finitely many indices. The convention to include equality in \(H_\lambda\) makes the split unambiguous.

The Threshold-Split Bound

For an eigenvalue in \(H_\lambda\), the effective-dimension weight is at least one half and at most one. For an eigenvalue in \(L_\lambda\), its weight is between one half of its size relative to \(\lambda\) and that full relative size. Summing these comparisons gives the central result.

Proof. If \(j\in H_\lambda\), then \(\mu_j\geq\lambda\), so \(\frac{1}{2}\leq\frac{\mu_j}{\mu_j+\lambda}\leq 1\). If \(j\in L_\lambda\), then \(\mu_j<\lambda\), and hence \(\mu_j+\lambda\leq 2\lambda\) and \(\mu_j+\lambda\geq\lambda\). It follows that \(\frac{\mu_j}{2\lambda}\leq\frac{\mu_j}{\mu_j+\lambda}\leq\frac{\mu_j}{\lambda}\). Sum the first comparison over \(H_\lambda\) and the second over \(L_\lambda\). The resulting lower bound is \(N(\lambda)\geq\frac{1}{2}|H_\lambda|+\frac{1}{2\lambda}\sum_{j\in L_\lambda}\mu_j=\frac{1}{2}Q(\lambda)\); the upper bound is \(N(\lambda)\leq|H_\lambda|+\frac{1}{\lambda}\sum_{j\in L_\lambda}\mu_j=Q(\lambda)\). All sums converge because the spectrum is summable. \(\square\)

The factor-two comparison has a useful interpretation. Eigenvalues above the threshold contribute order one each. Eigenvalues below it contribute, to within a factor of two, their total spectral mass measured in units of \(\lambda\). Thus a large number of small eigenvalues can still matter if their combined mass is substantial. Counting only eigenvalues above the threshold does not generally control the whole effective dimension.

An Index-Based Bound

Sometimes a useful cutoff is specified by an index \(m\), rather than by the exact set of eigenvalues above \(\lambda\). The first \(m\) eigenvalues can be bounded by one each, while the remaining weights can be bounded by their eigenvalues divided by \(\lambda\). This gives a tail bound that can be applied even when the chosen \(m\) does not coincide with the threshold crossing.

Proof. For each of the first \(m\) eigenvalues, \(0\leq\mu_j/(\mu_j+\lambda)\leq1\). For each remaining eigenvalue, \(\mu_j/(\mu_j+\lambda)\leq\mu_j/\lambda\). Summing the first inequality over \(j\leq m\), the second over \(j>m\), and using the spectral formula gives the upper bound. Since every term of \(N(\lambda)\) is nonnegative, retaining only the first \(m\) terms gives the stated lower bound. Finally, if \(\mu_m\geq\lambda\), then nonincreasing order implies \(\mu_j\geq\lambda\) for \(1\leq j\leq m\); each of those \(m\) terms is at least \(1/2\), yielding \(N(\lambda)\geq m/2\). \(\square\)

What the Bounds Do—and Do Not—Say

The threshold-split and index-based inequalities turn spectral information into effective-dimension bounds. To obtain a specific dependence on \(\lambda\), however, one must know how the eigenvalues or their tails behave. If only the trace \(\sum_j\mu_j\) is known, the general estimate \(N(\lambda)\leq\operatorname{Tr}(T)/\lambda\) is valid, but may be loose. A more informative bound comes from locating a cutoff where the remaining tail mass is small relative to \(\lambda\).

This is also why effective dimension is not simply the number of eigenvalues exceeding \(\lambda\). The threshold count is only one part of \(Q(\lambda)\); the scaled tail is the other. Conversely, the upper bound \(Q(\lambda)\) can be loose when many eigenvalues lie far below \(\lambda\), since it replaces each denominator \(\mu_j+\lambda\) by \(\lambda\). The two-sided result guarantees comparability within a factor of two for the particular threshold split, not an exact value.

• Common mistake: counting only the large eigenvalues. This omits all low-eigenvalue contributions and can substantially understate \(N(\lambda)\). Include the term \(\lambda^{-1}\sum_{\mu_j<\lambda}\mu_j\).
• Common mistake: treating the trace as a hard cutoff. The weight \(\mu_j/(\mu_j+\lambda)\) is not zero below \(\lambda\). Small eigenvalues still contribute, and their aggregate contribution is controlled by their tail mass.
• Common mistake: forgetting multiplicity or threshold equality. Count repeated eigenvalues separately. With \(H_\lambda=\{j:\mu_j\geq\lambda\}\), an eigenvalue equal to \(\lambda\) contributes exactly \(1/2\) and belongs to the high set.
• Common mistake: claiming a rate without a spectral assumption. The splitting argument is general, but a rate as \(\lambda\) changes requires additional information about eigenvalue counts or tail sums.