PaperlayerView exact revision on arXiv

Source-linked AI summary

Less is More: Nyström Computational Regularization

Alessandro Rudi, Raffaello Camoriano, Lorenzo Rosasco

arXiv:1507.04717v6stat.MLcs.LG

TL;DR

Large-scale kernel methods are limited by the memory and time costs of full kernel matrices, motivating Nyström subsampling. The paper proves high-probability learning guarantees for random-design sampling and proposes an incremental Nyström KRLS method in which subsampling jointly controls computation and regularization. The resulting approaches achieve optimal learning bounds when the subsampling level is suitably chosen, with experiments reporting state-of-the-art performance on benchmark large-scale datasets.

  • Problem

    Full kernel matrices make standard kernel methods computationally infeasible at large sample sizes, while prior theory did not directly characterize generalization in random-design statistical learning.

  • Method

    The paper analyzes uniform and approximate-leverage-score Nyström subsampling for KRLS and develops an incremental procedure whose subsampling level controls both computation and regularization.

  • Results

    The analysis gives optimal finite-sample bounds for uniform and leverage-score Nyström methods in the random-design setting, while experiments report state-of-the-art benchmark performance.

  • Takeaways & Limitations

    Choosing the subsampling level appropriately can preserve optimal learning guarantees while reducing memory requirements and enabling efficient incremental model selection.

  • Takeaways & Limitations

    The theoretical analysis assumes a unique minimal-norm minimizer; cases where minimizers do not exist are left to a longer version because the analysis is considerably more involved.

Abstract

from arXiv · show

We study Nyström type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling level is suitably chosen. These results suggest a simple incremental variant of Nyström Kernel Regularized Least Squares, where the subsampling level implements a form of computational regularization, in the sense that it controls at the same time regularization and computations. Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.

1 Introduction

The paper studies Nyström subsampling for large-scale kernel methods, focusing on generalization guarantees and how the subsampling level affects statistical and computational behavior. It extends prior analyses to random-design statistical learning with high-probability estimates and establishes optimal finite-sample bounds for uniform and leverage-score sampling.

  • Motivation: Nyström approaches replace the empirical kernel matrix with a smaller matrix formed by column subsampling, reducing memory and time requirements while preserving practical performance.The paper investigates these methods as a response to the scalability limitations of standard kernel methods.
  • Goals: The study characterizes Nyström learning schemes' generalization properties and examines the subsampling level from both statistical and computational perspectives.This dual role motivates a Nyström variant of Kernel Regularized Least Squares.
  • Theory gap: Prior theory mainly analyzed empirical-kernel-matrix discrepancies or fixed-design regression, providing limited direct information about algorithmic generalization in random-design settings.Earlier sharp analyses were derived in expectation rather than with high-probability estimates.
  • Contribution: The paper extends these results to statistical learning with random design and high-probability estimates, where the analysis is considerably more complex.This is identified as the study's main technical contribution.
  • Contribution: The main result gives optimal finite-sample bounds for both uniform and leverage-score-based Nyström subsampling strategies.The result addresses both sampling approaches within the random-design statistical learning setting.

2 Supervised learning with KRLS and Nystr¨om approaches

The paper formulates kernel regularized least squares in an RKHS and replaces its full training-set representation with a subset of input points. It considers uniform and approximate-leverage-score Nyström sampling to obtain more efficient solutions while retaining the framework's learning objective.

  • Supervised learning setup: The learning problem is defined over a probability distribution on input-output pairs, with the goal of minimizing expected risk over a measurable hypothesis space.Random-design regression with squared loss is given as a basic example.
  • Kernel framework: Kernel methods use a separable reproducing kernel Hilbert space whose kernel provides function evaluation through the reproducing property.The associated kernel matrix is symmetric positive semidefinite.
  • KRLS: KRLS has a unique solution represented using the training points, labels, and the empirical kernel matrix, allowing minimization to be restricted to the training-set span.This representation is justified by the representer theorem.
  • Scalability: Storing the full empirical kernel matrix and solving its linear system become computationally infeasible as the training size increases.Nyström strategies address this bottleneck by replacing the full training-set span with a smaller one.
  • Nyström KRLS: Nyström KRLS selects m ≤ n training inputs and computes the corresponding solution from the reduced kernel matrices using a Moore-Penrose pseudoinverse.The selected subset determines the approximation strategy.
  • Plain Nyström: Plain Nyström samples the subset uniformly without replacement from the training set.This is one of the two primary techniques considered.
  • ALS Nyström: Approximate-leverage-score Nyström samples training points independently with replacement using probabilities proportional to approximate leverage scores.The scores approximate the regularized leverage scores within a multiplicative factor T with confidence δ for t ≥ t0.
  • Main result: The paper's main result shows that KRLS based on plain or approximate-leverage-score Nyström provides optimal empirical solutions to the stated problem.The sampling probabilities for the ALS method are determined by the approximate leverage scores.

3 Theoretical analysis

The analysis establishes high-probability error bounds for Nyström-regularized least squares under capacity, noise, and regularity assumptions, with optimal rates when regularization and subsampling are suitably selected. The proof separates sample, approximation, and computational errors, allowing computational resources and regularization to be tailored jointly.

  • Assumptions: The assumptions constrain the kernel covariance operator, effective dimensions, output noise, and target-function regularity.The effective dimension N(λ) measures hypothesis-space capacity, while the regularity condition controls bias or approximation error.
  • Main results: Theorem 1 gives optimal finite-sample error bounds for plain and approximate-leverage-score Nyström subsampling under Assumptions 1–4.The rates are stated for a regularization choice λ = ∥C∥n^−1/(2v+γ+1) and suitable subsampling conditions.
  • Implications: The results are described as minimax optimal and extend earlier expectation-based or fixed-design analyses to a general statistical learning setting.The comparison places the bounds alongside other regularization methods that achieve optimal error rates.
  • Error decomposition: The learning error decomposes into sample, approximation, and computational terms, with the computational term depending on the subsampling scheme.For plain Nyström and approximate leverage scores, subsampling-specific bounds control the computational contribution.
  • Computational regularization: Choosing λ to minimize statistical terms and m to match their order yields the Theorem 1 learning rate while tailoring computation to data-dependent generalization properties.The same subsampling level can therefore act as a computational regularizer alongside λ.

4 Incremental updates and experimental analysis

The paper develops an incremental Nyström procedure for exploring subsampling levels and evaluates its computational and predictive performance. Experiments show reduced model-selection cost and state-of-the-art predictive performance, while smaller subsamples can preserve accuracy and act as regularization.

  • Experimental design: Incremental Nyström model selection explores varying subsampling levels and compares statistical and computational benefits on large-scale datasets.The experiments use uniformly sampled training points, cross-validation, repeated trials, and benchmark comparisons.
  • Efficient model selection: O(nm^2 + m^3) computes the whole regularization path, versus O(nm^2T + m^3T) for a naive procedure analyzing T subsampling levels.The incremental method exploits rank-one Cholesky updates.
  • Interplay between λ and m: A small m can match the performance of the largest subsample while reducing computation and memory; on cpuSmall, RMSE changes from 12.2 to 13.3 while time and memory are approximately halved.The comparison uses m = 5000, λ = 10^-12 versus m = 2679, λ = 10^-15 over five trials.
  • Interplay between λ and m: For pumadyn32nh, m = 62 and λ = 10^-7 achieves average test RMSE 0.33, matching m = 1000 and λ = 10^-3 with a 3-fold speedup.The result is averaged over 10 trials for the joint training and validation phase.
  • Predictive performance comparison: The proposed incremental Nyström approach matches state-of-the-art predictive performances on the evaluated benchmark datasets.The comparison includes KRLS, random Fourier features, Fastfood, and batch Nyström baselines.

A The incremental algorithm

The incremental algorithm updates Nyström solutions as the subsampling level increases. Cholesky updates and triangular solves yield total cost O(nm^2 + m^3) for computing the sequence of estimators.

  • Incremental construction: The algorithm incrementally computes the estimator ˜α as the number of selected Nyström points grows from 1 to m.It maintains an incremental Cholesky decomposition of the corresponding Gram matrices.
  • Incremental construction: Rank-one Cholesky updates construct R_{t+1} from a bordered version of R_t.The update uses the vectors u_{t+1} and v_{t+1}.
  • Complexity: O(nm^2 + m^3) is the total cost for computing ˜α_2 through ˜α_m.Each rank-one update and triangular solve contributes O(t^2), while computing c_t contributes O(nt).

B Preliminary definitions

This section introduces finite-rank linear operators that map functions in the Hilbert space to coordinates defined by selected elements. These operators provide the notation used for later Nyström characterizations.

  • Operator definitions: Z_m maps a function f in H to the vector of inner products with z_1 through z_m.Its coordinates are (⟨z_1,f⟩_H,...,⟨z_m,f⟩_H).
  • Kernel specialization: The operators used later include the case m = n with z_i = Kx_i for all training points.This specializes the general operator construction to kernel evaluations.
  • Operator properties: The introduced operators are linear and finite rank.

C Representer theorem for Nystr¨om computational regularization and extensions

The section characterizes Nyström computational regularization through optimization over a subspace H_m and equivalent operator, SVD, and representer-theorem forms. These representations support both theoretical analysis and computation.

  • Subspace formulation: The estimator is defined by minimizing the regularized learning objective over a general subspace H_m of H.The formulation is strictly convex and coercive, yielding a unique solution under the stated setup.
  • Subspace formulation: The minimizer lies in H_m because its orthogonal component cannot improve the objective.The proof decomposes the solution into components in H_m and H_m^⊥ and shows the orthogonal component is zero.
  • Operator representation: An SVD of Z_m yields the projection P_m = VV* whose range is exactly H_m.The columns of V define the subspace representation used in the characterization.
  • Equivalent representations: The estimator admits equivalent expressions obtained by substituting the projection with its SVD factors and solving the resulting reduced system.These forms follow by premultiplying with V* and then V.
  • Representer theorem: The representer theorem gives a computational characterization of the estimator in terms of selected training inputs and kernel matrices.The formulation uses K_nm, K_mm, and the Moore–Penrose pseudoinverse.

C.1 Extensions

The analysis extends beyond the specific subsampling schemes covered by Theorem 1 to a broad family of approximation schemes, including generalized Nyström constructions.

  • Extensions: Theorem 2’s error decomposition applies directly to a large family of approximation schemes.The paper states that several further examples follow from this extension.
  • Generalized Nyström: Generalized Nyström approximations choose a linear operator Z_m mapping the RKHS H into R^m.The resulting KRLS solution is expressed through this operator and associated finite-dimensional matrices.
  • Plain Nyström: Plain Nyström approximations select m training points through a sampling scheme and form a subsampled kernel approximation.The construction uses Z_m = S_m and yields the corresponding Nyström kernel matrix.
  • Reduced rank: Reduced-rank Nyström constructs an m-rank approximation of the kernel matrix associated with p selected dataset points.The approximation is formed from the leading m eigenvectors of the p-point kernel matrix.
  • Sketching matrices: Nyström with sketching matrices is represented by choosing Z_m = R_mS_n, recovering the SPSD sketching model.Here S_n selects all training points and R_m is an m × n sketching matrix.

D Probabilistic inequalities

This section develops probabilistic inequalities used in the main proof, including high-probability bounds for plain and leverage-score-based Nyström approximations and related sample quantities.

  • Probabilistic inequalities: Five main probabilistic inequalities provide the technical ingredients for the main result.The paper identifies Lemmas 6 and 7 and Proposition 1 as especially new or independently useful.
  • Plain Nyström: With probability at least 1 − δ, uniform plain Nyström sampling gives ∥(I − P_m)(C + λI)1/2∥2 ≤ 3λ when m satisfies the stated logarithmic condition.P_m projects onto the span of kernel sections associated with the sampled points.
  • ALS Nyström: Approximate leverage-score sampling constructs P_m from independently sampled indices and provides a high-probability Nyström approximation under leverage-score and sampling conditions.Duplicates are removed when forming the sampled subspace.
  • Effective dimension: The effective-dimension estimate satisfies ^N(λ) ≤ 1.3N(λ) with probability 1 − τ under the stated sample-size condition.This estimate is used to control random quantities in the proof.
  • Concentration bounds: The Hilbert-Schmidt fluctuation term is bounded by the stated expression with probability 1 − τ.The bound depends on κ, N(λ), λ, n, and logarithmic confidence factors.

E Proofs of main theorem

The proofs derive the main theorem by decomposing KRLS+Nyström error, controlling its components probabilistically, and selecting λ and m so computational error matches the statistical terms.

  • Error decomposition: Theorem 2 decomposes the error of the KRLS+generalized Nyström solution into terms that can be bounded separately.This decomposition is the key step used with the probabilistic inequalities developed earlier.
  • Proof setup: The proof represents the approximate solution through a regularized operator g_λ,m(C_n) and relates excess risk to the covariance-weighted prediction error.The representation uses the Nyström subspace through a partial isometry.
  • Intermediate bounds: Proposition 2 gives high-probability bounds for both plain and ALS Nyström under their respective sampling conditions.The proposition controls β, θ, S(λ,n), and C(m) before substituting them into the error decomposition.
  • Main theorem: Theorem 1 follows by combining Proposition 2 with the error decomposition and taking union bounds over the required events.Its probability statement depends on conditions involving λ, m, n, resampling probabilities, and approximate leverage scores.
  • Parameter choice: The regularization parameter is set to λ = ∥C∥n^-1/(2v+γ+1), while m is chosen so the computational error is no larger than the other error terms.The corresponding plain and ALS sampling conditions ensure C(m) ≤ λ.

F Auxiliary results

The auxiliary results establish operator inequalities and projection bounds used to control the terms in the KRLS+Nyström error decomposition.

  • Operator comparisons: Proposition 3 compares operator norms when a projection’s range contains the range induced by another operator.It supplies a projection-based norm comparison used in the proof.
  • Projection bounds: The proof of the projection comparison uses the identity λ(Z*Z + λI)^-1 = I − Z*(ZZ* + λI)^-1Z and positivity arguments.These steps establish the operator ordering required for the norm bound.
  • Cordes inequality: Cordes’ inequality bounds products of positive semidefinite operators and is invoked as an auxiliary norm inequality.The paper states it for positive semidefinite bounded linear operators.
  • Norm transfer: Proposition 5 transfers an operator ordering Y*Y − X*X ⪰ 0 into the norm comparison ∥XZ∥ ≤ ∥YZ∥.This result is used to derive subsequent projection and partial-isometry bounds.
  • Partial-isometry bounds: Proposition 6 bounds expressions involving a positive operator and a partial isometry by the corresponding compressed operators.The bound applies for exponents r,s between 0 and 1/2 and follows from Hansen’s inequality.

G Tail bounds

This section collects high-probability tools for random vectors, matrices, and operators, then applies operator Bernstein bounds to derive concentration results. It also records a κ2-based sample-size condition and associated probability bounds.

  • Assumptions: Proposition 8 assumes iid random vectors in a separable Hilbert space with trace-class covariance operator Q and finite N∞(λ).The proposition also restricts λ to 0 < λ ≤ ∥Q∥ in the displayed result context.
  • Application to operator concentration: The proof of the operator concentration result sets Qλ = Q + λI and applies Proposition 12 to centered random operators Zi.The proof separately controls their almost-sure bound and second-order moment before invoking the operator Bernstein inequality.
  • κ2-dependent bounds: Remark 1 defines κ2 = infλ>0 N∞(λ)(∥Q∥+λ) and gives κ2-dependent sample-size conditions for high-probability bounds.The stated conditions include n ≥ 405κ2 ∨ 67κ2 log κ2 and a further condition associated with a bound below 1/3.
  • Matrix-product approximation: Proposition 9 gives a random-with-replacement matrix-product approximation bound under probabilities lower-bounded by normalized column norms.The sampling distribution must satisfy a β-dependent lower bound involving each column norm and Tr AA⊤.
  • Bernstein inequalities: Propositions 10–12 state Bernstein inequalities for sums of scalar random variables, Hilbert-space random vectors, and selfadjoint positive random operators.The bounds use zero-mean assumptions together with almost-sure bounds and second-moment or variance controls; the absolute-value and operator-norm variants have probability 1−2δ.
Loading 1507.04717v6…