PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization Properties of Learning with Random Features

Alessandro Rudi, Lorenzo Rosasco

arXiv:1602.04474v5stat.MLcs.LG

TL;DR

The paper studies whether random-feature ridge regression can retain kernel ridge regression's generalization while using fewer features. It analyzes random-feature approximations under least-squares loss and shows that optimal accuracy can hold with substantially reduced computation, while faster rates may require more features or specialized sampling.

  • Problem

    Prior results suggested that O(n) random features were needed for O(1/√n) learning bounds, while few studies addressed the generalization properties of random-feature learning.

  • Method

    The paper analyzes random features within a ridge regression approach for least-squares loss, including alternative sampling schemes for faster rates.

  • Results

    O(√n) random features can achieve O(1/√n) learning error with the same prediction accuracy as exact kernel ridge regression; faster rates may require more features.

  • Takeaways & Limitations

    Random features can reduce computations while preserving the optimal statistical accuracy of exact kernel ridge regression for large classes of learning problems.

  • Takeaways & Limitations

    The learning bounds are optimal, but the paper provides no lower bounds on them.

Abstract

from arXiv · show

We study the generalization properties of ridge regression with random features in the statistical learning framework. We show for the first time that $O(1/\sqrt{n})$ learning bounds can be achieved with only $O(\sqrt{n}\log n)$ random features rather than $O({n})$ as suggested by previous results. Further, we prove faster learning rates and show that they might require more random features, unless they are sampled according to a possibly problem dependent distribution. Our results shed light on the statistical computational trade-offs in large scale kernelized learning, showing the potential effectiveness of random features in reducing the computational complexity while keeping optimal generalization properties.

1 Introduction

The paper asks whether random features can preserve the generalization properties of kernel methods while using fewer centers, and shows this is possible for ridge regression under standard assumptions. It also derives faster rates that may require more features or problem-dependent sampling.

  • Motivation: Kernel methods achieve optimal statistical results with centers equal to the input points, but their O(n^2) memory requirements limit large-scale use.Randomized approaches reduce the number of centers and can yield substantial memory gains.
  • Related results: O(√n log n) uniformly sampled random centers suffice for O(1/√n) learning bounds, matching full kernel ridge regression.This result was established for ridge regression with random centers sampled from the training points.
  • Research question: The paper studies whether random features have comparable generalization properties, addressing a literature gap focused mainly on kernel approximation.Only a few prior results considered generalization from learning with random features.
  • Motivation: O(n) random features were previously associated with O(1/√n) learning bounds, suggesting computational savings could reduce learning accuracy.Later analyses indicated that fewer features might suffice with problem-dependent sampling.
  • Contributions: Under standard assumptions, O(√n) random features achieve O(1/√n) learning error with the same prediction accuracy as exact kernel ridge regression.The authors identify problems where computational costs decrease without prediction-accuracy loss.
  • Contributions: Faster convergence rates are possible, but the required feature count may increase and can be weakened through more complex, potentially problem-dependent sampling schemes.Such schemes may require knowledge of the data-generating distribution or data-driven sampling.

2 Learning with random features and ridge regression

The paper combines finite-dimensional random-feature approximations with ridge regression to reduce kernel-method complexity. This raises the central question of whether fewer features preserve prediction accuracy for nonlinear kernels.

  • Kernel ridge regression: Kernel ridge regression uses a positive definite kernel and has optimal statistical properties, but requires O(n^2) space and roughly O(n^3) time.These costs arise from storing and processing the n by n kernel matrix.
  • Finite features: Replacing the kernel representation with a finite feature map of dimension M reduces complexity to O(nM) space and O(nM^2 + M^3) time when M ≪ n.The resulting computation is standard ridge regression on an n by M feature matrix.
  • Random Fourier features: Random Fourier features provide a Gaussian-kernel example by sampling frequencies and offsets according to distributions derived from the kernel's Fourier representation.The Gaussian kernel's inverse Fourier transform supplies the relevant sampling distribution.
  • Random-feature approximation: Random features approximate kernels through φ_M(x) = M^-1/2(ψ(x,ω_1),...,ψ(x,ω_M)), with independently sampled ω_i.The construction applies to kernels admitting an integral representation.
  • Random features with ridge regression: Combining random features with ridge regression preserves convex optimization while potentially reducing computation when M is much smaller than n.The paper analyzes whether this approximation causes a loss of prediction accuracy.

3 Main Results

The paper characterizes random-feature ridge regression, showing optimal generalization with substantially fewer features than prior bounds and further reductions under problem-dependent sampling. It also analyzes faster rates, computational gains, and assumptions governing these guarantees.

  • 3 Main Results: The analysis studies random features with ridge regression, beginning with a basic setting and extending to fast rates and problem-dependent sampling.The framework assumes a kernel integral representation and examines generalization as the sample size and feature count grow.
  • 3 Main Results: The results rely on assumptions about effective dimension, eigenfunction-coefficient decay, boundedness, and the existence of an expected-risk minimizer in the RKHS.The paper notes that the minimizer need not exist in an infinite-dimensional RKHS and discusses the consequences of controlling approximation terms uniformly.
  • 3 Main Results: O(√n log n) random features suffice for O(1/√n) learning bounds, matching full kernel ridge regression under the basic setting.This reduces the feature requirement from the O(n) suggested by earlier random-feature analyses while preserving the same learning bound.
  • 3 Main Results: The resulting computational requirements decrease from roughly O(n^3) time and O(n^2) space for kernel ridge regression to O(n^2) time and O(n√n) space.The paper presents this as computational savings without a statistical-accuracy trade-off in the considered setting.
  • 3.2 Refined Results: Fast Learning Rates: Under refined assumptions with parameters r and γ, the learning bound remains optimal, while the required feature count can be smaller than n and may exceed O(√n).For γ > 0 and r > 1/2, M ≪ n can suffice; for r = 1 and γ = 0, O(√n) features achieve O(1/n), whereas r = 1/2 and γ = 0 requires O(n).
  • 3.3 Refined Results: Beyond uniform sampling: Problem-dependent sampling can reduce feature requirements beyond data-independent sampling, with α controlling the rate and potentially allowing a constant number of features.In the slow-rate case r = 1/2, γ = 1, O(n^α/2) features are needed; when γ = 0 and α = γ, a constant number can suffice.

4 Numerical results

The numerical study validates the theoretical random-feature bounds using spline kernels and compares RF-KRR with exact KRR across increasing sample sizes.

  • No lower bounds on the required number of random features are provided, so numerical experiments are used to validate the upper bounds.
  • The experiment uses a spline kernel of order q on X = [0, 1] with uniformly distributed inputs and Gaussian conditional noise.
  • For n ∈ {10^3, . . . , 10^4}, λ is selected by minimizing analytically computed excess risk for KRR.
  • The number of RF-KRR features is selected to achieve excess risk within 5% of the KRR estimator.

5 Conclusion

The paper analyzes random features with ridge regression in a noisy statistical-learning setting. It concludes that random features can reduce computation while preserving exact KRR's optimal statistical accuracy, and identifies extensions for future work.

  • The study provides a thorough analysis of random features with ridge regression under noisy, randomly sampled data.
  • Large classes of learning problems permit reduced computation while preserving the optimal statistical accuracy of exact kernel ridge regression.
  • The authors contrast these results with previous work suggesting that computational gains require sacrificing statistical accuracy.
  • Future directions include empirical leverage scores, accelerated or stochastic gradient methods, distributed techniques, and broader loss functions.

Supplementary Materials

The supplementary materials collect proofs, probabilistic and operator inequalities, auxiliary technical lemmas, and examples of random-feature expansions.

  • Section A contains the proofs for Section 3.
  • Section B recalls concentration inequalities needed for the proofs.
  • Section C recalls operator inequalities used in the proofs.
  • Section D derives auxiliary technical lemmas, while Section E recalls examples of random-feature expansions.

A Proofs

The appendix establishes the proof framework by collecting assumptions, defining kernel and random-feature operators, and decomposing and bounding the excess risk.

  • A.2 Excess-risk decomposition: The proofs begin by introducing notation and decomposing excess risk into five terms that are simplified through several lemmas.
  • A.3 Probabilistic bounds: The main theorem follows after bounding the decomposition terms in probability, including variance and computational-error terms.
  • Assumptions: The analysis assumes compatibility, bounded continuous random features, sub-exponential output noise, and an effective-dimension condition.
  • Assumptions: The source condition requires fH(x) = (L^r g)(x) almost surely for r between 1/2 and 1.
  • Operator framework: The appendix relates the RKHS and integral-operator constructions to the population risk, projection operator, empirical samples, and finite-dimensional feature maps.
  • Operator framework: Random-feature operators are defined for kernels approximated by M independently sampled features, alongside the associated finite-dimensional operators.

A.2 Analytic Result

The analytic result decomposes excess risk into several components, then bounds them through operator identities and concentration-ready quantities. The terms capture variance, model-space interaction, covariance inversion, integral-operator approximation, and approximation error.

  • Interpretation of terms: The five components control output variance, model-space interaction, inverse-covariance approximation, integral-operator approximation, and model approximation error.These roles correspond to the successive terms in the decomposition.
  • Projection property: The projection argument shows that (I −P)ψω = 0 almost surely on the support of π, eliminating the second term in Eq. 17.The result also holds more generally for any f ∈ range(SM).
  • Analytic decomposition: Theorem 4 decomposes the excess risk into terms whose L2(X, ρX) norms are bounded separately.The decomposition is derived under Assumptions 3 and Eq. (15), using Lemmas 2–5.
  • Analytic bound: The decomposition bounds the excess-risk square root by max(1, b1) max(1, b3)(A + B + C(λ, M) + D).The factors b1 and b3 contribute numerical constants, while A, B, C(λ, M), and D determine the rates.
  • Preparation for probability bounds: The probabilistic analysis next estimates β, S, C, and the empirical effective dimension introduced by the analytic decomposition.The random variables depend on both the sample z and the random-feature draw ω.

A.3.1 Estimates for S(λ, M, n)

This subsection bounds the sample-error quantity S(λ, M, n) using concentration inequalities for random vectors and controls the effective dimension induced by the random-feature kernel. The resulting events hold with explicit high probability under feature-count and regularization conditions.

  • Effective dimension: NM(λ) is the effective dimension induced by the random-feature kernel KM, while N(λ) is the corresponding effective dimension for the original kernel.The analysis relates the two through an event where NM(λ) ≤1.5N(λ).
  • Sample concentration: Lemma 6 provides a probability-at-least-1 −δ bound for a sample-dependent term after conditioning on the random features.The proof applies Bernstein’s inequality for sums of zero-mean random vectors.
  • Bound on S(λ, M, n): Lemma 7 bounds S(λ, M, n) with probability at least 1 −3δ under Assumptions 3 and 4.The proof combines bounds for individual terms, a union event, and control of the random-feature effective dimension.
  • Conditions: The required feature condition includes M ≥(4 + 18F∞(λ)) log(12κ2/(λδ)).This condition is used for the concentration argument controlling the random-feature quantities.
  • Operator concentration: Lemma 8 bounds C(λ, M) with probability at least 1 −2δ by combining concentration events for the integral and feature operators.The proof intersects events controlling the relevant operator deviations.

A.3.3 Estimates for β

The analysis controls β by bounding two auxiliary quantities, β1 and β2, and intersecting high-probability events. Under the stated conditions, β is bounded by a constant with probability at least 1 −3δ.

  • Operator approximation: The proof controls the random operator approximation L −LM using concentration for Hilbert-Schmidt-valued random operators.The operators are formed from independently sampled random features and have zero-mean deviations.
  • Bound on β: Lemma 10 bounds β with probability at least 1 −3δ under Assumption 3.The proof first controls β1 and β2, then combines their events.
  • Auxiliary events: The event controlling β1 requires a lower bound on the empirical covariance norm, written as 3/4∥L∥ ≤∥CM∥.This auxiliary event is used to make the subsequent inverse-operator bounds valid.
  • Constant control: Under conditions (a), (b), (c.1), and (c.2), the intersection event gives β ≤(2/3)^−3/2 < 2.The bound follows from simultaneous control of the auxiliary events.

A.4 Proof of the Main Result

The main proof combines the analytic decomposition with probabilistic bounds on β, S, and C to obtain generalization guarantees for random-feature kernel ridge regression. A specialization selects the feature count relative to regularization, and λn = n^−1/2 yields a sufficient random-feature scaling for the target rate.

  • Specialized bound: Theorem 6 specializes the bound by selecting M relative to λ so the excess-risk bound depends only on λ and matches the kernel-ridge upper-bound order.This specialization is designed to recover optimal generalization scaling.
  • General bound: Theorem 5 gives a generalization bound for RF-KRLS over a broad range of λ and M.The proof combines the analytic decomposition with high-probability estimates for β, S(λ, M, n), and C(λ, M).
  • Probability guarantee: The combined event D ∩ E ∩ G has probability at least 1 −9τ.The event intersection combines separate controls for β, S, and C.
  • Rate specialization: Theorem 7 specializes the general result under additional assumptions using p := (2r + γ −1)^−1.The theorem gives the resulting high-probability bound after substituting effective-dimension and uniform-bound assumptions.
  • Learning-rate choice: λn = n^−1/2 together with the stated random-feature count is sufficient to guarantee the corresponding generalization bound.The proof applies Theorem 1 with the resulting choice of λ and M.

D Auxiliary Results

This section develops auxiliary probabilistic, operator-theoretic, and effective-dimension results used to control empirical quantities and decompose the excess risk. The propositions support high-probability bounds for random operators and effective dimensions under boundedness and trace-class assumptions.

  • Concentration tools: Several propositions apply Bernstein-type inequalities to control sample errors and deviations of empirical operators.The results use Bernstein inequalities for random vectors and Hilbert-space-valued operators.
  • Operator concentration: Proposition 6 bounds deviations involving empirical covariance operators under i.i.d. trace-class random-vector assumptions.Its proof applies a concentration proposition to centered, regularized random operators.
  • Assumptions and bounds: The auxiliary results impose regularization, boundedness, trace-class, and sample-size conditions to obtain the stated probability bounds.Examples include λ > 0, bounded random vectors, and lower bounds on m involving F∞(λ), κ, and confidence parameters.
  • Effective dimension: The empirical effective dimension is analytically decomposed and then bounded in probability using the preceding operator results.This decomposition connects empirical and true effective dimensions for later excess-risk analysis.
  • Risk decomposition: Propositions 8 and 9 provide operator inequalities and interpolation tools used in the analytic decomposition of the excess risk.These results concern positive operators on separable Hilbert spaces and support the later risk bounds.

E Examples of Random feature maps

The paper presents random-feature constructions for several kernel families, including translation-invariant, semigroup-invariant, additive homogeneous, neural-network, Gaussian, and dot-product kernels. These examples specify feature maps and sampling distributions, while some variants use structured or deterministic sampling to alter computational or approximation properties.

  • Translation-invariant kernels: Random Fourier features represent translation-invariant kernels using Fourier-based sampling and cosine feature maps.The construction applies when X = R^d and samples frequency-related parameters from a distribution derived from the Fourier transform.
  • Gaussian kernels: Gaussian-kernel features can be sampled by first drawing a Poisson count and then a multinomial allocation across coordinates.The resulting feature functions lie in the Gaussian-kernel RKHS, although their RKHS norms can grow without bound as the index norm increases.
  • Dot-product kernels: Dot-product kernels on a bounded Euclidean ball form another class covered by the random-feature framework.These kernels are expressed as k(x, z) = v(x^⊤z) for an appropriate scalar function v.
  • Semigroup-invariant kernels: Semigroup-invariant kernels admit Laplace feature maps with sampling density proportional to the Laplace transform of the defining function.The construction uses X = [0, ∞)^d and satisfies the stated boundedness assumption.
  • Additive homogeneous kernels: Additive homogeneous kernels use transformed one-dimensional features, while related methods employ structured or low-discrepancy sampling.The cited variants target computational complexity or statistical accuracy relative to ordinary random sampling.
  • Neural-network kernels: Randomized one-layer neural-network features connect finite randomized units with kernels generated by infinite ReLU networks.For bounded X, the construction satisfies the paper’s assumption and samples units from a Gaussian-related distribution.
Loading 1602.04474v5…