Pith. sign in

REVIEW 1 major objections 4 minor 1 cited by

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Tensor Sketch, a random feature map for polynomial kernels, sketches the p-fold tensor power in O(d + D log D) time and, by Theorem 9, estimates the kernel inner product with variance at most (3p-1)/D times the p-th powers of the input…

desk verdict The paper's only new contribution—Theorem 9's polynomial variance bound—is unsupported; the proof rests on a false lemma, though the underlying Tensor Sketch algorithm remains correctly and usefully described. read the letter →

arxiv 2505.08146 v2 pith:CVUH3WSO submitted 2025-05-13 cs.DS cs.LG

Ninh Pham , Rasmus Pagh This is my paper · ORCID
classification cs.DScs.LG
keywords TensorSketchpolynomialkernelapproximationrandomfeaturemapsCountFastFourierTransformhash-basedsketchingAMSmethods
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes Tensor Sketch, a randomized feature map that approximates the polynomial kernel $\kappa(x,y)=\langle x,y\rangle^p$ without forming the $d^p$-dimensional tensor product. For $n$ vectors in $\mathbb{R}^d$ it computes $D$-dimensional embeddings in time $O(n(d + D \log D))$, by convolving $p$ Count Sketches with the fast Fourier transform. The central claim is that the inner product of two sketches is unbiased for $\langle x,y\rangle^p$, with variance at most $\frac{3p-1}{D}\lVert x\rVert_2^{2p}\lVert y\rVert_2^{2p}$. If this bound holds, sketch width $D$ proportional to $p/\varepsilon^2$ controls the approximation error, which would make high-degree polynomial kernels practical on large, high-dimensional data at near-linear cost.

What carries the argument

The load-bearing object is the pair of composite hashes $(H,S)$ on tensor indices, together with fast polynomial convolution. Because each of the $p$ levels contributes one Count Sketch of $x$, the Count Sketch of the tensor product is the convolution of those $p$ sketches; representing sketches as polynomials of degree $D-1$ makes that convolution an $O(D\log D)$ FFT operation. The quantitative engine is Theorem 9's variance bound, which transfers the fourth-moment analysis of products of the classic sign-hash sketches (the paper's Lemma 8) to the collision-filtered second moment of $\langle C_{x^{(p)}},C_{y^{(p)}}\rangle$. This transfer is what converts a naive $3^p/D$ dependence into the stated $(3p-1)/D$ bound.

What would settle it

Concretely, take $d=3$, $p=3$, $D=4$, $x=(1,2,3)$, $y=(3,2,1)$, and enumerate all admissible combinations of the 2-wise independent bucket hashes and 4-wise independent sign hashes on $[3]$; the exact variance of $\langle C_{x^{(3)}},C_{y^{(3)}}\rangle$ must satisfy $\operatorname{Var}\le \frac{8}{4}\lVert x\rVert_2^6\lVert y\rVert_2^6$. A variance above that bound, or one that scales like $3^p/D$ rather than $p/D$ as $p$ increases, would falsify Theorem 9.

Watch

Extended reading notes

Core claim

Tensor Sketch is the Count Sketch of the $p$-th tensor power $x^{(p)}$, computed without materializing $x^{(p)}$. The composite hash $H(i_1,\dots,i_p)=(\sum_{j=1}^p h_j(i_j)) \bmod D$ routes each tensor coordinate to a bucket, and $S(i_1,\dots,i_p)=\prod_{j=1}^p s_j(i_j)$ attaches a random sign; with these hashes the sketch of $x^{(p)}$ is assembled from $p$ independent Count Sketches of $x$ by component-wise multiplication in the Fourier domain followed by an inverse FFT. Theorem 9 states that the resulting sketch is unbiased, $\mathbb{E}\langle C_{x^{(p)}},C_{y^{(p)}}\rangle=\langle x,y\rangle^p$, and that its variance is at most $\frac{3p-1}{D}\lVert x\rVert_2^{2p}\lVert y\rVert_2^{2p}$. The inhomogeneous kernel $(c+\langle x,y\rangle)^p$ is included by appending a coordinate of value $\sqrt{c}$ to every data vector. The revised analysis is the paper's main improvement over its earlier conference version, whose variance bound was incorrect.

Load-bearing premise

The load-bearing premise is that the composite sign hash on tensor coordinates, though only pairwise independent, obeys the same fourth-moment inequality as products of independent sign sketches once collision indicators are replaced by their expectation; if that transfer is false, the $(3p-1)/D$ variance bound does not follow.

Editorial extensions

If this is right

  • For fixed degree $p$ and bounded input norms, $D=O(p/\varepsilon^2)$ brings the squared error of the kernel estimate below $\varepsilon^2$, so the polynomial kernel is approximated with controlled error at near-linear cost.
  • When $D=O(d)$, embedding $n$ points costs $O(nd\log d)$, removing the $O(dD)$ bottleneck of earlier random feature constructions for polynomial kernels.
  • The hash functions occupy $O(1)$ extra space and are evaluated in constant time, so the same sketch can be recomputed cheaply in streaming or online settings after one pass.
  • The inhomogeneous kernel $(c+\langle x,y\rangle)^p$ falls out of the homogeneous analysis by appending a $\sqrt{c}$ coordinate, so the standard SVM polynomial kernel is covered.
  • For unit-norm inputs the sketch preserves kernel normalization, so kernel methods can be trained in the sketched space with the same feature geometry.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Averaging $R$ independent Tensor Sketches divides the stated variance by $R$, so the same accuracy can be reached with width $D=O(p/(R\varepsilon^2))$; the paper analyzes a single sketch only, but its independence assumptions make this averaging trade-off immediate.
  • For sparse inputs with $s$ nonzeros per vector, only nonzero coordinates need the initial Count Sketch pass, so a natural extension would run in $O(n(s + D\log D))$; the paper states only the dense bound.
  • The linear-in-$p$ variance claimed here is stronger than the exponential-$p$ dependence that later tree-structured polynomial sketching work, cited in the paper's related-work section, attributes to the original Tensor Sketch; reconciling the two analyses is left open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper presents Tensor Sketch, a random feature map for polynomial kernels that computes Count Sketches of tensor powers via FFT-based convolution. It claims an O(n(d + D log D)) construction time for n points in R^d, unbiased estimation of (x,y)^p, and a variance bound in Theorem 9 of at most (3p-1)/D times ||x||^{2p}||y||^{2p}. The paper also contains a survey of later applications and positions its revised variance analysis as the main new theoretical contribution, correcting an error in the conference version of the work.

Significance. The Tensor Sketch algorithm itself is well known and has been widely adopted; the runtime bound and unbiasedness are standard and sound. If Theorem 9 were valid, it would give a relative-error guarantee with D = O(p/eps^2), which is substantially stronger than the exponential dependence on p that the paper attributes to the original Tensor Sketch. However, the theorem rests on Lemma 8, which is false as stated, and its proof establishes only a 3^p bound. The central theoretical claim of the revised analysis is therefore unsupported. The survey of applications is useful, but the manuscript contains no experimental section despite an abstract claim of empirical evaluations.

major comments (1)
  1. [4.3, Theorem 9] Because the proof of Theorem 9 invokes Lemma 8 as its final step, the claimed bound Var[<C_{x(p)},C_{y(p)}>] <= (3p-1)/D ||x||^{2p}||y||^{2p} is not established. With the bound actually proved in Lemma 8, the argument yields at best 3^p/D times the same norm product, an exponential-in-p bound rather than the stated linear-in-p bound. This is not a cosmetic issue: Section 2 states that Ahle et al. (2020) improve on the exponential p-dependence of the original Tensor Sketch, which is consistent with a 3^p/D bound and inconsistent with the linear (3p-1)/D claim of Theorem 9. The paper's advertised correction of the p-dependence is therefore unsupported by the provided proof.
minor comments (4)
  1. [4.1, Eq. (2)] The construction in Section 4.1 says all four hash functions h1,h2,s1,s2 are sampled from 2-wise independent families, while Definition 5 and Section 4.2 require the sign functions s_j to be 4-wise independent for the variance analysis. The construction should state the 4-wise requirement from the outset, or explain why 2-wise signs suffice for the tensor construction in the p-fold algorithm.
  2. [Abstract] The abstract asserts that empirical evaluations demonstrate high approximation accuracy and large runtime improvements, but the manuscript contains no experiments section. This claim should either be supported by experiments or removed.
  3. [Table 1] Table 1 has formatting issues and appears to duplicate entries in the Tensor Sketch row; the time and memory entries should be cleaned up so that each technique has one clear set of complexity bounds.
  4. [3.5, Lemma 8, proof] The final sentence of the proof of Lemma 8 says 'since Var(Z) = E[Z^2] - <x,y>^{2p} <= 3^p ||x||^{2p}||y||^{2p}', which contradicts the stated (3p-1) constant. The statement and proof should be aligned after the correct constant is determined.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the estimator is derived from tensor algebra and Count Sketch convolution, and the variance proof depends on an external moment bound rather than on fitting or self-referential definitions.

full rationale

The derivation chain is self-contained and non-circular. Tensor Sketch is defined as the Count Sketch of the p-fold tensor product (Sections 4.1–4.2), and unbiasedness follows from Lemma 1 plus Count Sketch unbiasedness; no parameter is fitted to any subset of data to force the target value, and no prediction is renamed from an input. The variance bound in Theorem 9 invokes Lemma 8, a moment bound for products of AMS sketches attributed to Braverman et al. (2010), rather than a result that already contains Theorem 9; applying it to the collision-filtered sum is a dependency, not an identity. The only self-citations (Pagh 2013 for the convolution-based Count Sketch construction, and Pham and Pagh 2013 for the conference version) are not load-bearing in the circularity sense: the construction is re-derived in Sections 4.1–4.2, and the 2013 version is explicitly identified as containing an error to be corrected. However, the printed proof of Lemma 8 contains a genuine mismatch: after deriving E[Z^2] ≤ (3||x||^2_2||y||^2_2)^p, it ends 'which completes the proof since Var(Z) = E[Z^2] − ⟨x,y⟩^{2p} ≤ 3^p ||x||^{2p}_2 ||y||^{2p}_2', whereas the lemma statement claims the stronger bound (3p−1)||x||^{2p}_2||y||^{2p}_2. Since Theorem 9 relies on that stronger constant ('The last line holds using the variance bound from Lemma 8'), the advertised polynomial-in-p dependence is not established by the given proof. This is a correctness gap, not circularity: the unsupported constant is neither a fitted input nor an equivalent reformulation of the theorem's conclusion, and no step of the derivation acquires its target by construction or by a self-citation chain. Accordingly the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted; D and p are user inputs. The claims rest on standard tensor algebra, hash constructions, and FFT, plus an unproven moment-independence transfer in Theorem 9. No new entities are postulated.

assumptions (5)
  • standard math Tensor powers are exact feature maps for homogeneous polynomial kernels: <x^(p), y^(p)> = <x,y>^p (Lemma 1).
    Basis of the estimator; standard algebraic identity.
  • standard math There exist 2-wise and 4-wise independent hash families with O(1) storage and O(1) evaluation (Carter-Wegman; Thorup-Zhang).
    Used for the O(1) space claim and fast hashing; cited but not constructed.
  • domain assumption Composite hash H = (h_1 + ... + h_p) mod D is 2-wise independent, and S = s_1 ... s_p is 2-wise independent (Patrascu-Thorup).
    Required for unbiasedness and for collision probability 1/D; cited from prior work.
  • ad hoc to paper The 2-wise independent composite S has enough structure for the fourth-moment analysis in Theorem 9, via Lemma 8.
    This is the load-bearing unsupported step: Lemma 8 is stated and proved for products of p independent 4-wise independent AMS sketches, but the proof of Theorem 9 needs the same bound for a collision-filtered sum over the tensor domain. The paper does not prove this transfer.
  • standard math FFT computes polynomial products of degree D in O(D log D) time.
    Used for the runtime O(d + D log D); standard algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation." pith.science (2026). https://pith.science/paper/CVUH3WSO

@misc{pith2026250508146,
  author       = {Pith},
  title        = {Pith review of: Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CVUH3WSO}},
  note         = {Machine review of arXiv:2505.08146}
}
abstract

Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose $\textit{Tensor Sketch}$, an efficient random feature map for approximating polynomial kernels. Given $n$ training samples in $\mathbb{R}^d$ Tensor Sketch computes low-dimensional embeddings in $\mathbb{R}^D$ in time $\mathcal{O}\left( n(d+D \log{D}) \right)$ making it well-suited for high-dimensional and large-scale settings. We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates. We also discuss extensions and highlight applications where Tensor Sketch serves as a central computational tool.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Improving TensorSketch Using Complex Random Variables

    cs.DS 2026-08 reject novelty 5.0 of 10

    A complex-to-real TensorSketch is claimed to reduce polynomial-kernel sketch variance growth to 2^p/D, but the proof's expansion of the squared modulus of the complex inner product omits conjugation.

Reference graph

Works this paper leans on

84 extracted references · 78 canonical work pages · cited by 1 Pith paper

  1. [1]

    Oblivious sketching of high-degree polynomial kernels

    Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 141--160, 2020

    2020

  2. [2]

    The fast johnson--lindenstrauss transform and approximate nearest neighbors

    Nir Ailon and Bernard Chazelle. The fast johnson--lindenstrauss transform and approximate nearest neighbors. SIAM Journal on Computing, 39 0 (1): 0 302--322, 2009

    2009

  3. [3]

    Katyusha: The first direct acceleration of stochastic gradient methods

    Zeyuan Allen - Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research (JMLR), 18: 0 221:1--221:51, 2017

    2017

  4. [4]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58 0 (1): 0 137--147, 1999

    1999

  5. [5]

    Nguyen, and David P

    Haim Avron, Huy L. Nguyen, and David P. Woodruff. Subspace embeddings for the polynomial kernel. In Advances in Neural Information Processing Systems (NIPS), pages 2258--2266, 2014

    work page 2014

  6. [6]

    Clarkson, and David P

    Haim Avron, Kenneth L. Clarkson, and David P. Woodruff. Faster kernel ridge regression using sketching and preconditioning. SIAM J. Matrix Analysis Applications , 38 0 (4): 0 1116--1138, 2017 a

    work page 2017

  7. [7]

    Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees

    Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In International Conference on Machine Learning (ICML), pages 253--262, 2017 b

    work page 2017

  8. [8]

    Francis R. Bach. On the equivalence between kernel quadrature rules and random feature expansions. Journal of Machine Learning Research (JMLR), 18: 0 21:1--21:38, 2017

    work page 2017

Show all 84 references
  1. [9]

    Harmonic Analysis and the Theory of Probability

    Salomon Bochner. Harmonic Analysis and the Theory of Probability. Courier Corporation, 2005

    2005

  2. [10]

    AMS without 4-wise independence on product domains

    Vladimir Braverman, Kai - Min Chung, Zhenming Liu, Michael Mitzenmacher, and Rafail Ostrovsky. AMS without 4-wise independence on product domains. In International Symposium on Theoretical Aspects of Computer Science (STACS), pages 119--130, 2010

    2010

  3. [11]

    Convex optimization: Algorithms and complexity

    S \' e bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8 0 (3-4): 0 231--357, 2015

    2015

  4. [12]

    Larry Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18 0 (2): 0 143--154, 1979

    1979

  5. [13]

    LIBSVM : A library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. LIBSVM : A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2: 0 27:1--27:27, 2011

    2011

  6. [14]

    Hashing-based-estimators for kernel density in high dimensions

    Moses Charikar and Panos Siminelakis. Hashing-based-estimators for kernel density in high dimensions. In Annual Symposium on Foundations of Computer Science (FOCS), pages 1036--1049, 2017

    2017

  7. [15]

    Finding frequent items in data streams

    Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International colloquium on automata, languages, and programming (ICALP), pages 693--703, 2002

    2002

  8. [16]

    Colwell, and Adrian Weller

    Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tam \' a s Sarl \' o s, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with perfo...

    2021

  9. [17]

    Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions

    Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions. Foundations and Trends in Machine Learning, 9 0 (4-5): 0 249--429, 2016

    2016

  10. [18]

    Kernel pooling for convolutional neural networks

    Yin Cui, Feng Zhou, Jiang Wang, Xiao Liu, Yuanqing Lin, and Serge Belongie. Kernel pooling for convolutional neural networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3049--3058, 2017

    2017

  11. [19]

    Learning to evaluate image captioning

    Yin Cui, Guandao Yang, Andreas Veit, Xun Huang, and Serge Belongie. Learning to evaluate image captioning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5804--5812, 2018

    2018

  12. [20]

    Xiyang Dai, Joe Yue - Hei Ng, and Larry S. Davis. FASON: first and second order information fusion network for texture recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6100--6108, 2017

    2017

  13. [21]

    Alexandre d'Aspremont, Damien Scieur, and Adrien B. Taylor. Acceleration methods. Foundations and Trends in Optimization, 5 0 (1-2): 0 1--245, 2021

    2021

  14. [22]

    Woodruff

    Huaian Diao, Zhao Song, Wen Sun, and David P. Woodruff. Sketching for kronecker product regression and p-splines. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 84, pages 1299--1308, 2018

    2018

  15. [23]

    KONG: kernels for ordered-neighborhood graphs

    Moez Draief, Konstantin Kutzkov, Kevin Scaman, and Milan Vojnovic. KONG: kernels for ordered-neighborhood graphs. In Advances in Neural Information Processing Systems (NeurIPS), pages 4055--4064, 2018

    2018

  16. [24]

    LIBLINEAR : A library for large linear classification

    Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. LIBLINEAR : A library for large linear classification. Journal of Machine Learning Research (JMRL), 9: 0 1871--1874, 2008

    2008

  17. [25]

    Scalable attributed-graph subspace clustering

    Chafik Fettal, Linda Labiod, and Mohamed Nadif. Scalable attributed-graph subspace clustering. In AAAI Conference on Artificial Intelligence (AAAI), volume 37, pages 5256--5264, 2023

    2023

  18. [26]

    What can a single attention layer learn? a study through the random features lens

    Hengyu Fu, Tianyu Guo, Yu Bai, and Song Mei. What can a single attention layer learn? a study through the random features lens. In Advances in Neural Information Processing Systems (NeurIPS), pages 11912--11951, 2023

    2023

  19. [27]

    Multimodal compact bilinear pooling for visual question answering and visual grounding

    Akira Fukui, Dong Huk Park, Daylen Yang, Anna Rohrbach, Trevor Darrell, and Marcus Rohrbach. Multimodal compact bilinear pooling for visual question answering and visual grounding. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 457--468, 2016

    2016

  20. [28]

    Compact bilinear pooling

    Yang Gao, Oscar Beijbom, Ning Zhang, and Trevor Darrell. Compact bilinear pooling. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 317--326, 2016

    2016

  21. [29]

    Alex Gittens and Michael W. Mahoney. Revisiting the nystrom method for improved large-scale machine learning. Journal of Machine Learning Research (JMLR), 17: 0 117:1--117:65, 2016

    2016

  22. [30]

    Compact random feature maps

    Raffay Hamid, Ying Xiao, Alex Gittens, and Dennis DeCoste. Compact random feature maps. In International Conference of Machine Learning (ICML), volume 32, pages 19--27, 2014

    2014

  23. [31]

    Polynomial tensor sketch for element-wise function of low-rank matrix

    Insu Han, Haim Avron, and Jinwoo Shin. Polynomial tensor sketch for element-wise function of low-rank matrix. In International Conference on Machine Learning (ICML), pages 3984--3993. PMLR, 2020

    2020

  24. [32]

    Declaring independence via the sketching of sketches

    Piotr Indyk and Andrew McGregor. Declaring independence via the sketching of sketches. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 737--745, 2008

    2008

  25. [33]

    Text categorization with support vector machines: Learning with many relevant features

    Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant features. In European conference on machine learning (ECML), volume 1398, pages 137--142, 1998

    1998

  26. [34]

    Training linear SVM s in linear time

    Thorsten Joachims. Training linear SVM s in linear time. In International Conference on Knowledge Discovery and Data Mining (KDD), pages 217--226, 2006

    2006

  27. [35]

    Fast alignment-free similarity estimation by tensor sketching

    Alireza Joudaki, Gunnar R \"a tsch, and Andre Kahles. Fast alignment-free similarity estimation by tensor sketching. bioRxiv, 2020

    2020

  28. [36]

    Random feature maps for dot product kernels

    Purushottam Kar and Harish Karnick. Random feature maps for dot product kernels. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 583--591, 2012

    2012

  29. [37]

    Algorithm Design

    Jon Kleinberg and Eva Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., 2005

    2005

  30. [38]

    Principled neuromorphic reservoir computing

    Denis Kleyko, Christopher J Kymn, Anthony Thomas, Bruno A Olshausen, Friedrich T Sommer, and E Paxon Frady. Principled neuromorphic reservoir computing. Nature Communications, 16 0 (1): 0 640, 2025

    2025

  31. [39]

    Sampling methods for the N ystr \" o m method

    Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Sampling methods for the N ystr \" o m method. Journal of Machine Learning Research (JMLR), 13: 0 981--1006, 2012

    2012

  32. [40]

    Lewis, Yiming Yang, Tony G

    David D. Lewis, Yiming Yang, Tony G. Rose, and Fan Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research (JMLR), 5: 0 361--397, 2004

    2004

  33. [41]

    Sgm-net: Skeleton-guided multimodal network for action recognition

    Jiwei Li, Xiang Xie, Qing Pan, Yong Cao, Zhaoyang Zhao, and Guoqiang Shi. Sgm-net: Skeleton-guided multimodal network for action recognition. Pattern Recognition, 107: 0 107490, 2020

    2020

  34. [42]

    Towards a unified analysis of random fourier features

    Zhu Li, Jean - Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards a unified analysis of random fourier features. In International Conference on Machine Learning (ICML), pages 3905--3914, 2019

    2019

  35. [43]

    Fanghui Liu, Xiaolin Huang, Yudong Chen, Jie Yang, and Johan A. K. Suykens. Random fourier features via fast surrogate leverage weighted sampling. In AAAI Conference on Artificial Intelligence (AAAI) , pages 4844--4851, 2020

    2020

  36. [44]

    Fanghui Liu, Xiaolin Huang, Yingyi Chen, and Johan A. K. Suykens. Fast learning in reproducing kernel krein spaces via signed measures. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 388--396, 2021

    2021

  37. [45]

    Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A. K. Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. Transactions on Pattern Analysis and Machine Intelligence (PAMI), 44 0 (10): 0 7128--7148, 2022

    2022

  38. [46]

    Smola, Zoubin Ghahramani, and Bernhard Sch \" o lkopf

    David Lopez - Paz, Suvrit Sra, Alexander J. Smola, Zoubin Ghahramani, and Bernhard Sch \" o lkopf. Randomized nonlinear component analysis. In International Conference on Machine Learning (ICML), pages 1359--1367, 2014

    2014

  39. [47]

    Jing Lu, Steven C. H. Hoi, Jialei Wang, Peilin Zhao, and Zhiyong Liu. Large scale online kernel learning. Journal of Machine Learning Research (JMLR), 17: 0 47:1--47:43, 2016

    2016

  40. [48]

    Low-rank tucker decomposition of large tensors using tensorsketch

    Osman Asif Malik and Stephen Becker. Low-rank tucker decomposition of large tensors using tensorsketch. In Advances in neural information processing systems (NeurIPS), volume 31, 2018

    2018

  41. [49]

    Randomized numerical linear algebra: Foundations and algorithms

    Per-Gunnar Martinsson and Joel A Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29: 0 403--572, 2020

    2020

  42. [50]

    Woodruff

    Michela Meister, Tam \' a s Sarl \' o s, and David P. Woodruff. Tight dimensionality reduction for sketching low degree polynomial kernels. In Advances in Neural Information Processing Systems (NeurIPS), pages 9470--9481, 2019

    2019

  43. [51]

    Kernel mean embedding of distributions: A review and beyond

    Krikamol Muandet, Kenji Fukumizu, Bharath K Sriperumbudur, and Bernhard Sch \"o lkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in Machine Learning, 10 0 (1-2): 0 1--141, 2017

    2017

  44. [52]

    An improved training algorithm for support vector machines

    Edgar Osuna, Robert Freund, and Federico Girosi. An improved training algorithm for support vector machines. In Neural networks for signal processing VII. Proceedings of the 1997 IEEE signal processing society workshop, pages 276--285, 1997

    1997

  45. [53]

    Compressed matrix multiplication

    Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT), 5 0 (3): 0 9:1--9:17, 2013

    2013

  46. [54]

    Pedregosa, G

    F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in P ython. Journal of Machine Learnin...

    2011

  47. [55]

    Yu, and Sanjiv Kumar

    Jeffrey Pennington, Felix X. Yu, and Sanjiv Kumar. Spherical random features for polynomial kernels. In Advances in Neural Information Processing Systems (NIPS), pages 1846--1854, 2015

    2015

  48. [56]

    Fast and scalable polynomial kernels via explicit feature maps

    Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kernels via explicit feature maps. In International Conference on Knowledge Discovery and Data Mining (KDD), pages 239--247. ACM , 2013

    2013

  49. [57]

    The power of simple tabulation hashing

    Mihai Pǎtra s cu and Mikkel Thorup. The power of simple tabulation hashing. Journal of the ACM, 59 0 (3): 0 1--50, 2012

    2012

  50. [58]

    Random features for large-scale kernel machines

    Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems (NIPS), pages 1177--1184, 2007

    2007

  51. [59]

    Learning action recognition model from depth and skeleton videos

    Hossein Rahmani and Mohammed Bennamoun. Learning action recognition model from depth and skeleton videos. In IEEE International Conference on Computer Vision (ICCV), pages 798--807, 2017

    2017

  52. [60]

    Generalization properties of learning with random features

    Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in neural information processing systems (NIPS), pages 3218--3228, 2017

    2017

  53. [61]

    A spectral analysis of dot-product kernels

    Meyer Scetbon and Za \" d Harchaoui. A spectral analysis of dot-product kernels. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3394--3402, 2021

    2021

  54. [62]

    I. J. Schoenberg. Positive definite functions on spheres . Duke Mathematical Journal, 9 0 (1): 0 96 -- 108, 1942. doi:10.1215/S0012-7094-42-00908-6

    1942 doi

  55. [63]

    Learning with Kernels: support vector machines, regularization, optimization, and beyond

    Bernhard Sch \" o lkopf and Alexander Johannes Smola. Learning with Kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2002

    2002

  56. [64]

    High-order attention models for visual question answering

    Israel Schwartz, Alexander Schwing, and Tamir Hazan. High-order attention models for visual question answering. In Advances in Neural Information Processing Systems (NIPS), pages 4906--4915, 2017

    2017

  57. [65]

    Pegasos: P rimal estimated sub-gradient solver for SVM

    Shai Shalev - Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: P rimal estimated sub-gradient solver for SVM . Mathematical Programming, 127 0 (1): 0 3--30, 2011

    2011

  58. [66]

    Kernel Methods for Pattern Analysis

    John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004

    2004

  59. [67]

    Higher-order count sketch: Dimensionality reduction that retains efficient tensor operations

    Yang Shi and Animashree Anandkumar. Higher-order count sketch: Dimensionality reduction that retains efficient tensor operations. In Data Compression Conference (DCC), pages 394--394, 2020

    2020

  60. [68]

    Relative error tensor low rank approximation

    Zhao Song, David P Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1152--1169, 2019

    2019

  61. [69]

    Sriperumbudur and Nicholas Sterge

    Bharath K. Sriperumbudur and Nicholas Sterge. Approximate kernel PCA: Computational versus statistical trade-off . The Annals of Statistics, 50 0 (5): 0 2713 -- 2736, 2022

    2022

  62. [70]

    Sriperumbudur and Zolt \' a n Szab \' o

    Bharath K. Sriperumbudur and Zolt \' a n Szab \' o . Optimal rates for random fourier features. In Advances in neural information processing systems (NIPS), pages 1144--1152, 2015

    2015

  63. [71]

    Few-shot learning for domain-specific fine-grained image classification

    Xiang Sun, Haoming Xv, Jian Dong, Hao Zhou, and Sheng Tan. Few-shot learning for domain-specific fine-grained image classification. IEEE Transactions on Image Processing, 29: 0 10272--10285, 2020

    2020

  64. [72]

    Gilbert, and Ambuj Tewari

    Yitong Sun, Anna C. Gilbert, and Ambuj Tewari. But how does it work in theory? linear SVM with random features. In Advances in Neural Information Processing Systems (NeurIPS), pages 3383--3392, 2018

    2018

  65. [73]

    Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation

    Mikkel Thorup and Yin Zhang. Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. SIAM Journal on Computing, 41 0 (2): 0 293--331, 2012

    2012

  66. [74]

    Tanimoto random features for scalable molecular machine learning

    Alexander Tripp, Sergio Bacallado, Suhas Singh, and Fabio Anselmi. Tanimoto random features for scalable molecular machine learning. In Advances in Neural Information Processing Systems (NeurIPS), 2024

    2024

  67. [75]

    Joel A. Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3 0 (1-2): 0 115--126, 2011

    2011

  68. [76]

    Smola, and Anima Anandkumar

    Yining Wang, Hsiao - Yu Fish Tung, Alexander J. Smola, and Anima Anandkumar. Fast and guaranteed tensor decomposition via sketching. In Advances in Neural Information Processing Systems (NIPS), pages 991--999, 2015

    2015

  69. [77]

    Weinberger, Anirban Dasgupta, John Langford, Alexander J

    Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In International Conference of Machine Learning (ICML), pages 1113--1120, 2009

    2009

  70. [78]

    Christopher K. I. Williams and Matthias W. Seeger. Using the N ystr \" o m method to speed up kernel machines. In Advances in Neural Information Processing Systems (NIPS), pages 682--688, 2000

    2000

  71. [79]

    Woodruff

    David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10 0 (1-2): 0 1--157, 2014

    2014

  72. [80]

    Aggarwal

    Lingfei Wu, Pin - Yu Chen, Ian En - Hsu Yen, Fangli Xu, Yinglong Xia, and Charu C. Aggarwal. Scalable spectral clustering using random binning features. In International Conference on Knowledge Discovery and Data Mining (KDD), pages 2506--2515, 2018

    2018

  73. [81]

    Scalable DBSCAN with random projections

    Haochuan Xu and Ninh Pham. Scalable DBSCAN with random projections. In Advances in Neural Information Processing Systems (NeurIPS), 2024

    2024

  74. [82]

    Nystr \"o m method vs random fourier features: A theoretical and empirical comparison

    Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. Nystr \"o m method vs random fourier features: A theoretical and empirical comparison. Advances in neural information processing systems (NIPS), 25, 2012

    2012

  75. [83]

    On the power and limitations of random features for understanding neural networks

    Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pages 6594--6604, 2019

    2019

  76. [84]

    Scaling neural tangent kernels via sketching and random features

    Amir Zandieh, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin. Scaling neural tangent kernels via sketching and random features. In Advances in Neural Information Processing Systems (NeurIPS), pages 1062--1073, 2021

    2021

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.