PaperlayerView exact revision on arXiv

Source-linked AI summary

FALKON: An Optimal Large Scale Kernel Method

Alessandro Rudi, Luigi Carratino, Lorenzo Rosasco

arXiv:1705.10958v3stat.MLcs.LG

TL;DR

Kernel methods have strong statistical properties but are difficult to apply at large scale because of stringent time and memory requirements. The paper proposes FALKON, combining randomized projections, iterative solvers, and preconditioning, and shows that it achieves KRR-level accuracy with substantially reduced resources. Experiments report strong performance on large-scale problems using a single machine.

  • Problem

    Kernel methods and KRR provide optimal statistical accuracy but require computational resources that limit their application to large datasets.

  • Method

    FALKON combines randomized projections, iterative solvers, and preconditioning to solve an approximated KRR problem efficiently.

  • Results

    FALKON achieves the same optimal learning rate as full KRR with O(n√n) time and O(n) memory, up to logarithmic factors, and outperforms previous methods on many large-scale problems.

  • Takeaways & Limitations

    FALKON provides a scalable kernel method capable of processing millions of points on a single machine while retaining optimal statistical accuracy.

  • Takeaways & Limitations

    Iterative and direct kernel approaches remain constrained by substantial memory or kernel-evaluation requirements, especially when storing the full kernel matrix.

Abstract

from arXiv · show

Kernel methods provide a principled way to perform non linear, nonparametric learning. They rely on solid functional analytic foundations and enjoy optimal statistical properties. However, at least in their basic form, they have limited applicability in large scale scenarios because of stringent computational requirements in terms of time and especially memory. In this paper, we take a substantial step in scaling up kernel methods, proposing FALKON, a novel algorithm that allows to efficiently process millions of points. FALKON is derived combining several algorithmic principles, namely stochastic subsampling, iterative solvers and preconditioning. Our theoretical analysis shows that optimal statistical accuracy is achieved requiring essentially $O(n)$ memory and $O(n\sqrt{n})$ time. An extensive experimental analysis on large scale datasets shows that, even with a single machine, FALKON outperforms previous state of the art solutions, which exploit parallel/distributed architectures.

1 Introduction

Kernel methods offer strong theoretical and statistical properties for nonlinear learning, but their time and memory demands limit large-scale use. FALKON addresses this bottleneck with near-linear memory, subquadratic time, and strong empirical performance.

  • Kernel methods are popular nonparametric tools for nonlinear learning but typically require at least quadratic time and memory in the number of data points.
  • Existing KRR approximations can preserve optimal statistical accuracy, but typically still require roughly O(n^2) time and memory.
  • FALKON combines Nyström approximation, preconditioning, and iterative solvers to scale kernel methods to millions of points.
  • O(n√n) time and O(n) memory suffice for optimal statistical accuracy, up to logarithmic factors.
  • Experiments show that FALKON outperforms previous methods on many large-scale problems using a single machine and a fraction of their computational resources.

2 Statistical and Computational Trade-offs in Kernel Methods

Kernel ridge regression achieves optimal statistical accuracy but is computationally expensive. The section examines iterative solvers and random projections as routes to reduce computation while preserving accuracy.

  • Computations: Direct KRR requires O(n^2) space and kernel evaluations, with O(n^2c_K + n^3) time to compute and invert the kernel matrix.
  • Statistics: KRR achieves minimax-optimal error O(n^-1/2) when λ_n = n^-1/2 under basic assumptions.
  • Gradient methods and early stopping: Gradient methods reduce iteration cost, but storing the kernel matrix still requires O(n^2) memory and O(n^2t) time for t iterations.
  • Gradient methods and early stopping: Basic gradient descent needs roughly O(√n) iterations for suitable statistical accuracy, compared with O(n^1/4) for accelerated methods and potentially O(1) epochs for stochastic methods.
  • Random projections: Random projections, including Nyström methods, approximate the kernel matrix using M sampled training points and reduce memory when M ≪ n.
  • Random projections: M = Õ(√n) can suffice for the same optimal statistical accuracy as exact KRR, reducing kernel evaluations to O(n√n) while best time remains basically O(n^2).

3 FALKON

FALKON combines randomized projections with preconditioning and iterative solvers to efficiently solve an approximated KRR system. Its complexity and statistical analysis establish a scalable route to KRR-level accuracy.

  • FALKON uses randomized projections to approximate both the KRR problem and its preconditioning.
  • Preconditioning: Preconditioning improves the condition number of the linear system, reducing iterations, but standard KRR preconditioning retains its memory and kernel-evaluation requirements.
  • FALKON algorithm: FALKON solves the preconditioned system with conjugate gradient, avoiding the need to specify a step size.
  • Computations: The algorithm requires O(nMt + M^3) time and O(M^2) memory, with block computations limiting storage requirements.
  • Main complexity result: O(n√n) computations and O(n) memory are sufficient for optimal KRR statistical accuracy, up to logarithmic factors.

4 Theoretical Analysis

FALKON matches KRR’s optimal statistical accuracy while reducing the required computational resources to essentially O(n√n) time and O(n) memory, up to logarithmic factors. Its preconditioning yields exponential iteration-error decay, requiring roughly log n iterations, and refined sampling supports faster rates.

  • Main result: FALKON achieves KRR’s optimal statistical accuracy with essentially O(n√n) time and O(n) memory, up to logarithmic factors.The result is described as the best known time/space complexity for optimal KRR-level accuracy.
  • Main result: Roughly log n iterations suffice for optimal statistical accuracy, replacing the O(√n log n) iterations typically required by a simple iterative solver.With the chosen M, this yields O(n√n) time when logarithmic factors are omitted.
  • Main result: The preconditioned system’s additive excess-risk term decreases exponentially with iterations, including as e^-t when its condition number is below a small universal constant.The analysis links convergence to the condition number of the preconditioned system.
  • Fast learning rates: The analysis considers uniform and approximate leverage-score Nyström sampling, with sampling-dependent conditions controlling the preconditioner’s convergence exponent.The generalized analysis applies to approximation schemes satisfying the stated q-approximate leverage-score condition.
  • Fast learning rates: FALKON attains the same fast rates as KRR under the same regularity conditions, with approximate leverage-score sampling requiring M smaller than n^γ/2.Under these conditions, the resulting time complexity is O(nN(λ)) = O(n^(1+γ/2)).

5 Experiments

Across large-scale datasets, FALKON achieves state-of-the-art accuracy and typically outperforms previous approaches while using a fraction of their computational resources. The experiments include million-scale regression and classification tasks, including IMAGENET and HIGGS.

  • Results: FALKON achieves state-of-the-art accuracy and typically outperforms previous approaches across the considered large-scale datasets.The evaluation includes IMAGENET and other million-scale problems.
  • Computational setting: The experiments use a single machine, whereas competing results typically use clusters of GPU workstations.The reported setup includes two Intel Xeon processors, one NVIDIA Tesla K40c, and 128 GB of RAM.
  • Dataset coverage: The evaluated datasets span regression and classification, including MillionSongs, TIMIT, YELP, SUSY, HIGGS, and IMAGENET.Reported scales range from 4.6×10^5 to 1.1×10^7 examples.
  • Dataset settings: On IMAGENET, FALKON uses a Gaussian kernel with σ = 19, λ = 10^-9, and 5×10^4 Nyström centers for top-1 classification error.The features come from convolutional layers of pre-trained Inception-V4; a linear kernel gives c-err = 22.2%.

G. MATLAB Code for FALKON

The appendix defines generalized FALKON components, including Nyström sampling, weighting, rank-aware preconditioning, and conjugate-gradient estimation. It also provides implementation-oriented alternatives based on QR or eigendecomposition and recalls the analytic notation used later.

  • Preconditioning: The generalized preconditioner uses a positive diagonal weighting matrix D and rank-aware factors Q, T, and A built from KMM.The construction handles non-invertible KMM and guarantees the required structural properties.
  • Sampling: Nyström centers can be selected uniformly or by sampling according to approximate leverage scores.Uniform sampling selects a random subset, while leverage-score sampling uses probabilities derived from approximate scores.
  • Implementation: Rank-revealing QR and eigendecomposition provide alternative ways to compute the preconditioner factors.The eigendecomposition is conceptually simpler but slower because of larger hidden constants.
  • Algorithm: Generalized FALKON defines its estimator through t conjugate-gradient iterations applied to a preconditioned linear system.The resulting coefficient vector βt belongs to the reduced rank-dimensional space.
  • Analytic notation: The appendix establishes notation for Hilbert spaces, operator norms, adjoints, traces, tensor products, and spectral decompositions.These definitions support the functional-analytic treatment of FALKON’s excess risk.

C Analytic results

The analytic-results section bounds the condition number of FALKON’s preconditioned linear system and decomposes its excess risk into quantities controlled probabilistically later.

  • Conditioning: The section analyzes the condition number of FALKON’s preconditioned linear system.This controls the iterative behavior of the algorithm.
  • Excess risk: It decomposes FALKON’s excess risk into analytical quantities that are subsequently controlled in probability.The section is organized around these two analytic components.

C.1 Analytic results (I): Controlling condition number of W

The analysis characterizes the preconditioned system matrix W as an identity perturbation and bounds its condition number through the perturbation norm.

  • The characterization of W expresses it as A−⊤V∗(Ĉ_n + λI)VA−1.Here V is a partial isometry and λ is the regularization parameter.
  • W = I + E, where E is defined from the difference between empirical operators after preconditioning.This representation isolates the deviation from the identity matrix in the preconditioned system.
  • The smallest eigenvalue satisfies λmin(W) ≥ 1 − ∥E∥.The bound follows from the spectral properties of the self-adjoint perturbation E.
  • When ∥E∥ < 1, W is positive and its condition number is controlled by the perturbation magnitude.The preceding eigenvalue bounds provide the condition-number control used in the analysis.

C.2 Analytic results (II): The computational oracle inequality

The analysis connects finite-iteration FALKON to the exact Nyström estimator and uses conjugate-gradient convergence to control excess risk.

  • The excess risk of finite-iteration FALKON is bounded by the exact Nyström risk plus an optimization term that decays exponentially with iterations.The computational oracle inequality separates statistical Nyström error from iterative-solver error.
  • The finite-iteration estimator is represented by a vector determined by β_t, the conjugate-gradient iterate after t iterations.The coefficient vector β_t is converted into the corresponding function in the Hilbert space.
  • The preconditioned system matrix W is symmetric positive definite for λ > 0, ensuring conjugate-gradient convergence.Positive definiteness gives invertibility and a finite condition number.
  • FALKON with infinitely many conjugate-gradient iterations equals the exact Nyström estimator.The paper establishes this correspondence through vector representations in the reproducing-kernel Hilbert space.
  • Probabilistic bounds for the preconditioner perturbation are derived for both uniform and approximate leverage-score Nyström sampling.These bounds control the condition number needed for the iterative convergence analysis.

E Proof of Main Results

The proofs establish a computational oracle inequality by relating iterative optimization error to exact Nyström risk and controlling the preconditioned system's condition number.

  • The key novelty is relating the excess risk of the preconditioned iterative solver to the excess risk of the basic Nyström estimator.This translates optimization guarantees into statistical guarantees.
  • FALKON equals the exact Nyström estimator as the number of iterations tends to infinity.This identity provides the reference estimator for the finite-iteration analysis.
  • The preconditioned system decomposes into an identity component and a perturbation E, yielding condition-number control when ∥E∥ < 1.Sampling lemmas bound the relevant operator distance for uniform and approximate leverage-score centers.
  • The computational oracle inequality bounds FALKON risk by Nyström risk plus an iteration-dependent error term.The finite-iteration comparison is formalized through Theorem 1.

E.1 Main Result (I): computational oracle inequality for FALKON with uniform sampling

For uniform Nyström sampling, the analysis controls the conjugate-gradient rate through a sufficient condition on the number of sampled centers, yielding exponential iteration decay.

  • Uniform sampling controls the preconditioner when M satisfies the theorem's sampling-size condition.The resulting bound on the perturbation norm supports control of the preconditioned system.
  • The condition-number bound follows by expressing the preconditioned system through E and controlling ∥E∥ probabilistically.The proof applies the operator characterization and the uniform-sampling estimate.
  • Theorem 6 combines the uniform-sampling condition with the computational oracle inequality to obtain the stated iteration guarantee.The proof uses Theorem 1 together with a union bound over the relevant events.

E.2 Main Result (II): computational oracle inequality for FALKON with leverage scores

Under approximate leverage-score sampling, FALKON’s preconditioning analysis provides high-probability control of the preconditioned system and establishes a convergence exponent of at least 1/2 under stated conditions.

  • Leverage-score preconditioning: Approximate leverage-score sampling is the central mechanism used to obtain the preconditioning guarantee in the theorem’s high-probability analysis.The cited lemmas and theorem specify the sampling rule, regularization threshold, and probability parameters.
  • Leverage-score preconditioning: With probability 1 −δ, the preconditioned operator satisfies ∥bG−1/2 Mλ∥≤η when leverage-score sampling and the required condition on M hold.The analysis selects η = 2e1/2/(e+1).
  • Computational oracle inequality: The leverage-score theorem analyzes the FALKON estimator after t iterations relative to the exact Nyström estimator under λ0 ≤λ ≤∥C∥ and sample-size conditions.The result assumes λ0 =19κ2 and n satisfies the stated lower bounds.
  • Computational oracle inequality: With probability 1 −2δ, the exponent ν satisfies ν ≥1/2 under either uniform sampling with sufficiently large M or approximate leverage-score sampling with λ ≥19κ2.The theorem combines the two sampling regimes under the same overarching conditions.

E.3 Main Results (III): Optimal Generalization Bounds

FALKON attains KRR’s optimal generalization behavior under basic and refined regularity assumptions while using either uniform or approximate leverage-score Nyström sampling. Under capacity and source conditions, the resulting fast rates can approach O(1/n).

  • Basic rates: Under bounded-output assumptions and existence of an optimal-in-class fH, Theorem 3 gives FALKON an optimal generalization bound with uniform Nyström sampling.The estimator uses λ = n−1/2 and the theorem specifies conditions on n, M, and t.
  • Fast rates: Under the capacity condition N(λ) ≤ Q2λ−γ and source condition fH = Cr−1/2g, larger r yields faster learning rates.The capacity parameter γ and source regularity r characterize the assumptions used for refined rates.
  • Fast rates: FALKON achieves the same fast rates as KRR under the same conditions, with approximate leverage scores potentially requiring fewer Nyström points than uniform sampling.The cited result states that the approximate-sampling requirement can be smaller than nγ/2 and much smaller than √n.
  • Computational context: Prior SVD-based preconditioners require O(nMk) work and can become too expensive for the random-projection regime without additional eigenvalue-decay assumptions.The cited discussion contrasts this cost with the setting where randomized projection uses λ = n−1/2 and M = O(√n).
Loading 1705.10958v3…