Random Features for Large-Scale Kernel Machines · CiteArk

Recent activity

—Analysis environment started
—Analysis made new progress
—Analysis made new progress
—Research inventory and experiment plan prepared
—Waiting for experiment selection

ArkGraph

Explore ArkGraph and select the steps to run.

Random Features for Large-Scale Kernel Machines

Public

Authors:Ali Rahimi, Benjamin Recht

More

Research claims

Reproduction results

No reproduction results yet

The paper’s claims are available in Research claims.

Full research claim catalog

0 / 17 claims verified

the rest still being verified

Key metricsPaper-reported → reproduced · click a row to expand

On Adult classification, Fourier+LS trained fastest and had 14.9% test error. CVM had the lowest printed error, 14.8%, but required 73 minutes; Binning+LS had the highest printed error of the four entries.Whole claim: Awaiting reproduction0/8 measurements supported · 0 assessed8measurementsExplore results

Experiment plan ready; no runs yet.

Measurement results

0/8 assessed

0 supported0 disputed or conflicting8 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	14.9%	—	Not assessed
	9 seconds	—	Not assessed
	15.3%	—	Not assessed
	1.5 minutes	—	Not assessed
	14.8%	—	Not assessed
	73 minutes	—	Not assessed
	15.1%	—	Not assessed
	7 minutes	—	Not assessed

Open claim details

On Census regression, Fourier features with least squares reported the lowest normalized RMS test error and the shortest training time among the four table entries.Whole claim: Awaiting reproduction0/8 measurements supported · 0 assessed8measurementsExplore results

Experiment plan ready; no runs yet.

Measurement results

0/8 assessed

0 supported0 disputed or conflicting8 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	5%	—	Not assessed
	36 seconds	—	Not assessed
	7.5%	—	Not assessed
	19 minutes	—	Not assessed
	8.8%	—	Not assessed
	7.5 minutes	—	Not assessed
	9%	—	Not assessed
	13 minutes	—	Not assessed

Open claim details

On Forest Cover classification, Binning+LS matched libSVM's printed 2.2% test error, slightly improved on CVM's 2.3%, and trained in 25 minutes versus 7.5 hours for CVM and 44 hours for libSVM. Fourier+LS was slower than binning and had much higher error, 11.6%.Whole claim: Awaiting reproduction0/8 measurements supported · 0 assessed8measurementsExplore results

Experiment plan ready; no runs yet.

Measurement results

0/8 assessed

0 supported0 disputed or conflicting8 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	11.6%	—	Not assessed
	71 minutes	—	Not assessed
	2.2%	—	Not assessed
	25 minutes	—	Not assessed
	2.3%	—	Not assessed
	7.5 hours	—	Not assessed
	2.2%	—	Not assessed
	44 hours	—	Not assessed

Open claim details

The authors caution that KDDCUP99 is inherently oversampled: using only 50 randomly sampled training examples, either an SVM or least squares with random features consistently produced test error on the order of 8%.Whole claim: Awaiting reproduction0/3 measurements supported · 0 assessedExperiment not scheduled; feasibility remains unproven3measurementsExplore results

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Measurement results

0/3 assessed

0 supported0 disputed or conflicting3 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	50 examples	—	Not assessed
	0.001%	—	Not assessed
	8%	—	Not assessed

Open claim details

On the CPU regression dataset, Fourier features with least squares had the lowest normalized RMS test error and trained faster than the binning, CVM, and ASVM entries; the exact ASVM time was second fastest but its error was highest.Whole claim: Awaiting reproduction0/8 measurements supported · 0 assessed8measurementsExplore results

Experiment plan ready; no runs yet.

Measurement results

0/8 assessed

0 supported0 disputed or conflicting8 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	3.6%	—	Not assessed
	20 seconds	—	Not assessed
	5.3%	—	Not assessed
	3 minutes	—	Not assessed
	5.5%	—	Not assessed
	51 seconds	—	Not assessed
	11%	—	Not assessed
	31 seconds	—	Not assessed

Open claim details

On KDDCUP99, Fourier+LS and Binning+LS each reported 7.3% test error. CVM reported 6.2% error and 1.4 seconds in the original ordering, but 18% and 20 seconds after shuffling. The SVM-with-sampling entry reported 8.3% error and less than one second.Whole claim: Awaiting reproduction0/10 measurements supported · 0 assessed10measurementsExplore results

Experiment plan ready; no runs yet.

Measurement results

0/10 assessed

0 supported0 disputed or conflicting10 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	7.3%	—	Not assessed
	1.5 minutes	—	Not assessed
	7.3%	—	Not assessed
	35 minutes	—	Not assessed
	6.2%	—	Not assessed
	1.4 seconds	—	Not assessed
	18%	—	Not assessed
	20 seconds	—	Not assessed
	8.3%	—	Not assessed
	1 seconds	—	Not assessed

Open claim details

In the Forest Cover random-binning experiment, test accuracy continued to improve as more training data were used, and doubling the training-set size reduced test error by as much as 40%.Awaiting reproduction0/1 measurements supported · 0 assessedExperiment not scheduled; feasibility remains unprovenReported 40%

Reported

40%

Observed

—

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Measurement results

0/1 assessed

0 supported0 disputed or conflicting1 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	40%	—	Not assessed

Open claim details

Even with the original KDDCUP99 training order, the paper reports that changing the CVM regularization parameter by 15% produced a 49% test error, indicating strong sensitivity of this comparison to the parameter setting.Whole claim: Awaiting reproduction0/2 measurements supported · 0 assessedExperiment not scheduled; feasibility remains unproven2measurementsExplore results

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Measurement results

0/2 assessed

0 supported0 disputed or conflicting2 not assessed

The complete result group stays with its claim. Assessed rows come first; their judgments do not replace the whole-claim conclusion. Expand a row for conditions, sources, and evidence history.

Each row is a measurement with its reported value, latest available observation, and cumulative evidence state.
Metric and conditions	Reported	Latest observation	Evidence judgment
	15%	—	Not assessed
	49%	—	Not assessed

Open claim details

Qualitative findings

Figure 3 reports that test error decreases quickly as the number P of random binning partitions grows, while training-plus-testing time grows slowly; the authors conclude that good performance can be obtained with a modest number of features.Experiment blocked; see the specific reason

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

Across the five benchmark datasets, the authors characterize ridge regression on random features as faster than and competitively accurate with alternative large-scale kernel methods, while Table 1 shows that the advantage depends on dataset and feature family rather than holding for every individual entry.Experiment blocked; see the specific reason

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

The paper proves exponential concentration for random Fourier kernel estimates. For a fixed pair, the stated tail bound is Pr(|z(x)'z(y)-k(x,y)| >= epsilon) <= 2 exp(-D epsilon^2/2). Uniformly over a compact M, Claim 1 bounds the failure probability by 2^8 (sigma_p diam(M)/epsilon)^2 exp(-D epsilon^2/[4(d+2)]), and states that constant-probability uniform error at most epsilon follows for D = Omega((d/epsilon^2) log(sigma_p diam(M)/epsilon)).Experiment blocked; see the specific reason

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

The paper states that the binary random-binning estimator converges exponentially in P for a fixed pair and gives a uniform convergence guarantee in Claim 2. For compact M, the probability of uniform error at most epsilon is at least 1 - 36 d P alpha diam(M) exp(-(P epsilon^2/8 + ln(epsilon/L_k))/(d+1)).Experiment blocked; see the specific reason

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

The authors report that random Fourier features perform better on tasks relying largely on interpolation, whereas random binning features perform better on memorization tasks where a standard SVM requires many support vectors; they identify Forest Cover as the most dramatic example.Experiment blocked; see the specific reason

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

Other claims4

The paper contrasts evaluating a conventional kernel expansion, which requires O(Nd) operations and retaining much of the dataset unless sparse, with evaluating a learned linear hyperplane on the proposed random features, which it states requires O(D+d) operations and storage.Covered by other claims

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

For a properly scaled continuous positive-definite shift-invariant kernel, drawing frequencies from the kernel's Fourier transform produces random sinusoidal features whose inner product is an unbiased estimator of the kernel; averaging D independent frequency draws lowers estimator variance.Covered by other claims

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

Randomly shifted grids give binary features whose collision probability, and hence expected inner product, equals an eligible kernel. For separable multivariate kernels, independent one-dimensional grids multiply the collision probabilities across dimensions; averaging P independent partitions lowers variance. The appendix derives the pitch density p(delta)=delta k''(delta) for kernels expressible as convex mixtures of hat kernels.Covered by other claims

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details

The random-binning construction based on p(delta)=delta k''(delta) does not yield a random map for the Gaussian kernel because its second derivative is not everywhere positive.Stated by the authors

Initial preparation has not resolved this question; retain it for subsequent investigation and coverage assessment.

Open claim details