Pith. sign in

REVIEW 4 major objections 5 minor 56 references

Improving TensorSketch Using Complex Random Variables

T0 review · 4 major / 5 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 Replacing TensorSketch's random signs with fourth roots of unity yields an unbiased degree-$p$ kernel sketch with $2^p/D$ variance at the same input-sparsity runtime.

desk verdict The proof targets a non-conjugated inner product, so the headline 2^p/D variance bound is unestablished; the underlying idea is promising and may be repairable, but the submitted proof is internally inconsistent. read the letter →

arxiv 2608.10523 v1 pith:GGBUIA63 submitted 2026-08-11 cs.DS cs.AIstat.ML

Amit Sharma , Mohammad Azhar Khan , Rameshwar Pratap , Keegan Kang This is my paper · ORCID
classification cs.DScs.AIstat.ML
keywords TensorSketchpolynomialkernelcomplexrandomvariablesfourthrootsofunityCountvariancereductionfeaturemapsinput-sparsitysketching
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

TensorSketch is a hashing-based way to estimate the degree-$p$ polynomial kernel $\langle x, y\rangle^p$ without forming the $p$-fold tensor product, running in input-sparsity time. This paper claims that a simple swap---using independent random fourth roots of unity $\{1,i,-1,-i\}$ in place of the usual $\pm 1$ signs, then concatenating the real and imaginary parts of the complex sketch into a real vector---gives an unbiased estimator with variance at most $\frac{2^{p+1}-2}{D}\|x\|_2^{2p}\|y\|_2^{2p}$. That would improve the exponential dependence on degree from $3^p/D$ to $2^p/D$ while keeping TensorSketch's fast $O(p(\mathrm{nnz}(x)+D\log D))$ runtime, something the earlier complex-to-real construction for dense random-projection sketches did not achieve. The paper supports the claim with experiments on synthetic and real datasets measuring kernel approximation error and wall-clock time.

What carries the argument

The central object is the Complex-to-Real TensorSketch map: $p$ independent CountSketch matrices whose sign functions $s_r$ take values in $\{1,i,-1,-i\}$ uniformly, combined through FFT-based circular convolution so that the sketch of $x^{\otimes p}$ is never formed explicitly. The mechanism that carries the argument is the fourth-root moment structure $E[s]=0$, $E[|s|^2]=1$, $E[s^2]=0$, together with independence across the $p$ layers, which makes the variance expansion factor as a product of $p$ identical single-sketch moments. Lemma 4 evaluates these single-sketch moments exactly, and the probabilistic bound follows by replacing inner products with their norm upper bounds.

What would settle it

Compute the $p=1$, $d=2$ case $x=y=(1,1)$ by direct expansion: the paper's bound on $E[|\langle Cx, Cy\rangle|^2]$ is $4+4/D$, whereas the correct expansion with the conjugate on the second factor gives $4+8/D$, so the claimed variance inequality fails on this instance.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the variance improvement previously obtained only with dense complex random projections can be reproduced inside the hashing architecture of TensorSketch. The construction sketches $x$ and $y$ with $p$ independent CountSketch matrices whose signs are uniform fourth roots of unity, combines them by FFT convolution into a complex sketch of length $D/2$, and defines the final embedding as the real vector formed by stacking real and imaginary parts. The paper proves unbiasedness for $\langle x^{\otimes p}, y^{\otimes p}\rangle$ and derives the variance bound $\frac{2^{p+1}-2}{D}\|x\|_2^{2p}\|y\|_2^{2p}$. Because the signs have zero mean, unit squared magnitude, and zero square, most cross terms in the moment expansion vanish, and the $p$ independent sketch layers factor into products of single-layer second moments. The claimed result matches the variance of the dense complex-to-real sketch while retaining input-sparsity runtime.

Load-bearing premise

The load-bearing premise is that the squared magnitude of the complex sketch inner product can be expanded as $\langle CX, CY\rangle\langle CX, CY\rangle$ without conjugating the second factor; if that identity is wrong, the cross-term cancellations behind the $2^p/D$ variance bound do not occur.

Editorial extensions

If this is right

  • If the variance bound holds, a sketch of dimension $D$ for degree $p$ has variance growing like $2^p$ instead of $3^p$, so the same accuracy is reached at smaller sketch dimensions when $p$ is large.
  • The real-valued embedding can be fed directly to linear classifiers and other real-feature learners, just like standard TensorSketch.
  • The construction retains the $O(p(\mathrm{nnz}(x)+D\log D))$ runtime, so it replaces dense random-projection sketches for high-dimensional sparse inputs at no asymptotic slowdown.
  • The result extends the complex-to-real variance improvement from dense sketches to hashing-based sketches, closing the gap between the two sketching families.

Reading between the lines

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

  • Inference: Conditional on the proof being correct, the fourth-root cancellation mechanism is generic to products of independent linear forms, so the same idea may transfer to feature hashing, compact bilinear pooling, and other quadratic-form estimators.
  • Inference: The paper bounds variance only; a high-probability $(\epsilon,\delta)$ guarantee would require fourth-moment control, which is a natural next step and is not implied by the variance bound alone.
  • Inference: A sharper empirical test would fix the target error and compare the sketch dimensions each method needs; that design should expose the $2^p$ versus $3^p$ gap more directly than fixed-dimension KL divergence.
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

4 major / 5 minor

Summary. This paper proposes a Complex-to-Real (CtR) variant of TensorSketch for approximating degree-p polynomial kernels. The construction replaces the real Rademacher signs of the classical TensorSketch with independent uniform draws from the fourth roots of unity, takes the complex sketch into C^{D/2}, and then forms a real D-dimensional sketch by concatenating real and imaginary parts. The paper claims (Theorem 2) that the resulting estimator is unbiased for <x,y>^p and has variance bounded by (2^{p+1}-2)/D ||x||_2^{2p} ||y||_2^{2p}, while retaining the input-sparsity sketching time O(p(nnz(x)+D log D)). The proof is in Appendix A.1 and relies on moment identities for the complex signs (Lemmas 1 and 4). The paper also contains experiments comparing KL divergence and runtime against real TensorSketch and JL-type baselines, and an appendix theorem claiming that the complex CountSketch alone does not reduce variance.

Significance. If the main theorem were correctly proved, the contribution would be significant: it would extend the 2^p variance scaling achieved by Wacker et al.'s dense Complex-to-Real sketches to the input-sparsity TensorSketch framework, improving over the 3^p scaling of the real-valued TensorSketch. The paper also provides a clear algorithmic construction, a tabular comparison, and experiments on synthetic and real data. However, the central theoretical result is not established: the proof is built on an incorrect treatment of complex inner products, and the same algebraic error recurs in the supporting lemmas and in the appendix theorem. The experiments cannot compensate for an invalid proof of the main claim.

major comments (4)
  1. [Theorem 2 proof, Appendix A.1 (unbiasedness step)] The proof defines bkC(x,y) := ΦC(X)ΦC(Y)^T and expands it as Σ_{u,v} X_u Y_v S(u)S(v) 1[H(u)=H(v)] without conjugation. This is not the quantity that appears in the CtR estimator of Definition 8: the CtR concatenation Re/Im corresponds to Re(Σ_j ΦC(x)_j \overline{ΦC(y)}_j), i.e., the complex inner product with a conjugate on one factor. Even for the un-conjugated quantity, the unbiasedness argument is invalid because the diagonal terms u=v do not vanish: by Lemma 1, E[S(u)^2] = Π_j E[s_j(u_j)^2] = 0 for every u, so the announced conclusion E[bkC] = ⟨X,Y⟩ is false. For p=1, d=2, x=y=(1,1), the proof's expansion has expectation 0, while the actual CtR estimator has expectation 2. The unbiasedness claim in Theorem 2 is not established.
  2. [Appendix A.1, Eq. (15)] Equation (15) writes |⟨CX,CY⟩|^2 as ⟨CX,CY⟩⟨CX,CY⟩, omitting the conjugation on the second factor. The correct identity is |⟨a,b⟩|^2 = ⟨a,b⟩⟨b,a⟩. This error propagates into the moment bounds (10) and (11), and hence into the final variance bound (12). The missing conjugation changes the survivor configurations in the fourth-moment expansions: configurations of the form i=k≠i'=k' that survive for the conjugated product vanish for the un-conjugated product because they contain factors E[s_i^2]E[s_{i'}^2]=0. Equations (10) and (11) are therefore not validly derived, and the stated variance bound is unsupported.
  3. [Lemma 4, Eqs. (69) and (75)] The second-moment formula for E[Z^2] in Eq. (75) is false for the un-conjugated product Z = Π_j Zsj(x)Zsj(y) as defined. For p=1 and x=y=(1,1), a direct computation gives E[Z^2] = 2 (only the all-four-indices-equal configuration contributes), whereas Eq. (75) yields 2⟨x,y⟩^2 − Σ_i x_i^2 y_i^2 = 6. The survivor configurations listed in Eq. (69), namely i=k≠i'=k' and i=k'≠i'=k, each have zero expectation for independent fourth-root variables because they contain E[s_i^2]E[s_{i'}^2]=0 or E[s_i^2]E[s_k^2]=0. Consequently Lemma 4 does not provide the moment bound used in Equations (44)-(46) of the proof of Theorem 2.
  4. [Appendix B, Theorem 5] The proof of Theorem 5 repeats the same conjugation error. Equation (82)-(83) expands Φ(x)^T Φ(y) and writes the diagonal terms as |σ(i)|^2 x_i y_i, but since the product is not conjugated, the diagonal term is σ(i)^2, which has expectation 0 by Lemma 1. Thus the claimed unbiasedness of the complex CountSketch estimator is not proved, and the theorem's comparison of variances is not a valid supporting statement for the paper's thesis.
minor comments (5)
  1. [Section 3, Eq. (5)] The variance formula for Var(bkCtR) in Eq. (5) is written with a plus sign before 2E[bkC]^2, whereas the derivation from Eq. (4) and the appendix's Eq. (14) require a minus sign; this sign inconsistency should be corrected.
  2. [Definition 5] Definition 5 is internally inconsistent: it defines bkC(x,y) := ΦC(x)ΦC(y)^T, but the CtR estimator obtained by concatenating real and imaginary parts equals Re of the conjugated inner product. The notation should be made unambiguous, for example by writing ΦC(y)^* or \overline{ΦC(y)}.
  3. [Lemma 4 proof, Eq. (58)] The expansion in Eq. (58) reuses the same index names i and k for the four sums, which is ambiguous; the calculation should use four distinct summation indices (i,k,i',k') with explicit conjugates so that the survivor analysis is transparent.
  4. [Introduction and related work] The text attributes the complex-valued JL construction and the CtR construction to Wacker et al. [2023] and Wacker et al. [2024] in a way that may confuse readers; since both references are present in the bibliography, the roles of the two papers should be stated more clearly.
  5. [Definition 7] Definition 7 calls h a 'universal hash function', but the property actually required and used in the proof is 2-wise independence; 'universal' as commonly defined is weaker, so the terminology should be adjusted.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the variance analysis reduces to hash-moment and CtR lemmas, not to its own conclusion; the missing-conjugation issue is a proof error, not a circular one.

full rationale

The derivation of Theorem 2 is not circular. The claimed variance bound is obtained by combining Lemma 1's fourth-roots-of-unity moment identities, Lemma 4's moment evaluations for products of complex CountSketch inner products, and the externally cited Complex-to-Real variance framework of Wacker et al. (2023). No parameter is fitted to the target kernel and then renamed as a prediction, no uniqueness theorem is imported from the authors' own prior work to force the construction, and the central lemmas do not assume the theorem's conclusion. The paper's self-citations (Pratap & Kulkarni 2021, Pratap et al. 2021, Kang & Wong 2018, and coauthored control-variate papers) appear only in the related-work survey of variance-reduction techniques and are not used to justify the sketch's unbiasedness or variance bound. The serious flaw in the manuscript is an internal algebraic error: the proof repeatedly writes the complex inner product without the required conjugation (e.g., Eq. (15) and Lemma 4's second-moment expansion), so the moment expansions as written target a different bilinear expression and the stated proof of Theorem 2 is not valid. That is a correctness defect, not a circular reduction of the theorem to its own inputs. Accordingly, no specific circular step is identified and the circularity score is 0.

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

No free parameters or invented entities are introduced. The central claim depends on a flawed algebraic identity in the proof, not on fitted constants or new postulates.

assumptions (3)
  • domain assumption The hash functions h_r and sign functions s_r satisfy the standard CountSketch independence assumptions (2-wise and 4-wise independent, respectively).
    Definitions 7 and 8 rely on these independence assumptions for the moment computations in the proof.
  • ad hoc to paper The identity |⟨a,b⟩|^2 = ⟨a,b⟩⟨a,b⟩ for complex vectors is treated as valid in Equation (15).
    The proof of Theorem 2 expands the squared modulus of the complex sketch inner product without conjugating the second factor. This identity is false; the correct identity is |⟨a,b⟩|^2 = ⟨a,b⟩⟨b,a⟩. This is the load-bearing premise that invalidates the variance bound.
  • ad hoc to paper Lemma 4's survivor configuration i=k'≠i'=k contributes value 1 to E[(Z)^2].
    The expectation E[s(i)^2 s(k)^2] is 0 for i≠k under fourth roots of unity, so this configuration should not contribute. The moment formula built on this premise is incorrect.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improving TensorSketch Using Complex Random Variables." pith.science (2026). https://pith.science/paper/GGBUIA63

@misc{pith2026260810523,
  author       = {Pith},
  title        = {Pith review of: Improving TensorSketch Using Complex Random Variables},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GGBUIA63}},
  note         = {Machine review of arXiv:2608.10523}
}
abstract

\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$. However, the variance of both estimators grows exponentially with the polynomial degree $p$, scaling as $3^{p}/D$. Recent work by~\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to $2^{p}/D$ for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost $O(pDd)$ and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}~\citep{pham2013fast} that achieves the same variance bound as~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.

Figures

Figures reproduced from arXiv: 2608.10523 by the authors.

Figure 1
Figure 1. KL divergence on the COD–RNA dataset. We report KL divergence between the exact degree-p polynomial kernel and the kernel reconstructed from sketch features for p ∈ {3, 5, 7}. Methods include Real and CtR (complex-to-real) Gaussian and Rademacher JL sketches, as well as Real and CtR TensorSketch. Results are averaged over 20 independent trials. Sketch dimension is varied as D ∈ {d, 3d, 5d} [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 2
Figure 2. Wall-clock sketch construction time on the COD–RNA dataset. We compare Real and CtR (complex-to-real) Gaussian and Rademacher JL sketches, with Real and CtR TensorSketch for p ∈ {3, 7, 10}. The sketch dimension is varied as D ∈ {d, 3d, 5d}. Each point reports the average sketch construction time over 20 independent trials, measured on identical normalized input data. Here as well all dense JL-type sketches exhibit n… view at source ↗
Figure 3
Figure 3. KL divergence on the MAGIC Gamma Telescope dataset. We compare Real and complex-to-real (CtR) Gaussian and Rademacher JL sketches, together with Real and CtR TensorSketch. Results are shown for polynomial degrees p ∈ {3, 5, 7} and sketch dimensions D ∈ {d, 3d, 5d} with n = 3000 standardized and ℓ2-normalized samples. Bars report the mean KL divergence over 20 independent trials [PITH_FULL_IMAGE:figures/full_fig_p02… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Wall-clock sketch construction time on the MAGIC dataset. Methods compared include Real and complex￾to-real (CtR) Gaussian and Rademacher JL sketches, with Real and CtR TensorSketch. Results are shown for polynomial degrees p ∈ {3, 5, 7} and sketch dimensions D ∈ {d, 3…
Figure 5
Figure 5. Figure 5: KL divergence on the synthetic dataset (d = 2). We compare Real and complex-to-real (CtR) Gaussian and Rademacher JL sketches, together with Real and CtR TensorSketch, for approximating degree-p polynomial kernels on synthetic Gaussian data (n = 3000, dimension d = 2, …
Figure 6
Figure 6. Figure 6: Wall-clock sketch construction time on a synthetic dataset. Methods compared include Real and complex-to-real (CtR) Gaussian and Rademacher JL sketches, together with Real and CtR TensorSketch. Results are shown for polynomial degrees p ∈ {10, 15, 20} and sketch dimens…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 36 canonical work pages

  1. [1]

    AMS Without 4-Wise Independence on Product Domains , volume =

    Braverman, Vladimir and Chung, Kai-Min and Liu, Zhenming and Mitzenmacher, Michael and Ostrovsky, Rafail , year =. AMS Without 4-Wise Independence on Product Domains , volume =

    work page

  2. [2]

    2007 , publisher=

    UCI machine learning repository , author=. 2007 , publisher=

    2007

  3. [3]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Hutchinson’s estimator is bad at Kronecker-trace-estimation , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2026 , publisher=

    work page 2026

  4. [4]

    Machine Learning , volume=

    Variance reduction in feature hashing using MLE and control variate method , author=. Machine Learning , volume=. 2022 , publisher=

    work page 2022

  5. [5]

    Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Indyk, Piotr and McGregor, Andrew , title =. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2008 , publisher =

    work page 2008

  6. [6]

    Foundations of computational mathematics , volume=

    User-friendly tail bounds for sums of random matrices , author=. Foundations of computational mathematics , volume=. 2012 , publisher=

    2012

  7. [7]

    Journal of Functional Analysis , volume=

    On the best constants in noncommutative Khintchine-type inequalities , author=. Journal of Functional Analysis , volume=. 2007 , publisher=

    work page 2007

  8. [8]

    Jonas Wacker and Motonobu Kanagawa and Maurizio Filippone , title =. J. Mach. Learn. Res. , volume =. 2024 , url =

    work page 2024

Show all 56 references
  1. [9]

    Chen and Martin Farach

    Moses Charikar and Kevin C. Chen and Martin Farach. Finding frequent items in data streams , journal =. 2004 , url =. doi:10.1016/S0304-3975(03)00400-6 , timestamp =

    2004 doi

  2. [10]

    and Kapralov, Michael and Knudsen, Jakob B

    Ahle, Thomas D. and Kapralov, Michael and Knudsen, Jakob B. Oblivious Sketching of High-Degree Polynomial Kernels , booktitle =. 2020 , publisher =

    2020

  3. [11]

    Oseledets, I. V. , title =. SIAM Journal on Scientific Computing , volume =. 2011 , doi =. https://doi.org/10.1137/090752286 , abstract =

    2011 doi

  4. [12]

    2025 , note =

    Ballard, Grey , title =. 2025 , note =

    2025

  5. [13]

    Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS) , volume =

    Wacker, Jonas and Ohana, Ruben and Filippone, Maurizio , title =. Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS) , volume =. 2023 , publisher =

    2023

  6. [14]

    Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages =

    Pham, Ninh and Pagh, Rasmus , title =. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages =. 2013 , publisher =. doi:10.1145/2487575.2487591 , url =

    2013

  7. [15]

    CoRR , volume =

    Ninh Pham and Rasmus Pagh , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2505.08146 , eprinttype =. 2505.08146 , timestamp =

    2025 doi arXiv

  8. [16]

    2010 , eprint=

    AMS Without 4-Wise Independence on Product Domains , author=. 2010 , eprint=

    2010

  9. [17]

    and Lindenstrauss, Joram , journal =

    Johnson, William B. and Lindenstrauss, Joram , journal =. Extensions of. 1984 , publisher =

    1984

  10. [18]

    The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings , booktitle =

    Krzysztof Marcin Choromanski and Mark Rowland and Adrian Weller , editor =. The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings , booktitle =. 2017 , url =

    2017

  11. [19]

    Approximate nearest neighbors and the fast

    Ailon, Nir and Chazelle, Bernard , booktitle=. Approximate nearest neighbors and the fast. 2006 , organization=

    2006

  12. [20]

    Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS) , volume =

    Kar, Purushottam and Karnick, Harish , title =. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS) , volume =. 2012 , publisher =

    2012

  13. [21]

    Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages =

    Gao, Yang and Beijbom, Oscar and Zhang, Ning and Darrell, Trevor , title =. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages =. 2016 , publisher =. doi:10.1109/CVPR.2016.41 , url =

    2016 doi

  14. [22]

    Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding

    Fukui, Akira and Park, Dong Huk and Yang, Daylen and Rohrbach, Anna and Darrell, Trevor and Rohrbach, Marcus. Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding. Proceedings of the 2016 Conference on Empirical Methods in Natural Language Pro...

    2016 doi

  15. [23]

    Advances in Neural Information Processing Systems , volume =

    Rahimi, Ali and Recht, Benjamin , title =. Advances in Neural Information Processing Systems , volume =. 2007 , publisher =

    2007

  16. [24]

    split SVM : Fast, Space-Efficient, non-Heuristic, Polynomial Kernel Computation for NLP Applications

    Goldberg, Yoav and Elhadad, Michael. split SVM : Fast, Space-Efficient, non-Heuristic, Polynomial Kernel Computation for NLP Applications. Proceedings of ACL-08: HLT, Short Papers. 2008

    2008

  17. [25]

    Proceedings of the 10th IEEE International Conference on Data Mining (ICDM) , pages =

    Rendle, Steffen , title =. Proceedings of the 10th IEEE International Conference on Data Mining (ICDM) , pages =. 2010 , publisher =. doi:10.1109/ICDM.2010.127 , url =

    2010 doi

  18. [26]

    A Perspective on Interaction Effects in Genetic Association Studies , journal =

    Aschard, H. A Perspective on Interaction Effects in Genetic Association Studies , journal =. 2016 , volume =. doi:10.1002/gepi.21989 , issn =

    2016 doi

  19. [27]

    CoRR , volume =

    Andrew Cotter and Joseph Keshet and Nathan Srebro , title =. CoRR , volume =. 2011 , url =. 1109.4603 , timestamp =

    2011 arXiv

  20. [28]

    Kolda and Rachel A

    Ruhui Jin and Tamara G. Kolda and Rachel A. Ward , title =. CoRR , volume =. 2019 , url =. 1909.04801 , timestamp =

    2019 arXiv

  21. [29]

    Meyer and Haim Avron , title =

    Raphael A. Meyer and Haim Avron , title =. CoRR , volume =. 2023 , url =. doi:10.48550/ARXIV.2309.04952 , eprinttype =. 2309.04952 , timestamp =

    2023 doi arXiv

  22. [30]

    Dimitris Achlioptas , title =. J. Comput. Syst. Sci. , volume =. 2003 , url =. doi:10.1016/S0022-0000(03)00025-4 , timestamp =

    2003 doi

  23. [31]

    Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages =

    Li, Ping and Hastie, Trevor and Church, Kenneth Ward , title =. Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages =. 2006 , publisher =. doi:10.1145/1150402.1150436 , url =

    2006

  24. [32]

    and Leiserson, Charles E

    Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford , title =. 2009 , publisher =

    2009

  25. [33]

    Bhisham Dev Verma and Punit Pankaj Dubey and Rameshwar Pratap and Manoj Thakur , title =. Inf. Process. Lett. , volume =. 2025 , url =. doi:10.1016/J.IPL.2024.106517 , timestamp =

    2025

  26. [34]

    Bhisham Dev Verma and Rameshwar Pratap and Manoj Thakur , title =. Mach. Learn. , volume =. 2022 , url =. doi:10.1007/S10994-022-06166-Z , timestamp =

    2022 doi

  27. [35]

    Advances in Neural Information Processing Systems , volume=

    Fully understanding the hashing trick , author=. Advances in Neural Information Processing Systems , volume=

  28. [36]

    Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI) , volume =

    Pratap, Rameshwar and Kulkarni, Raghav , title =. Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI) , volume =. 2021 , publisher =

    2021

  29. [37]

    Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA) , pages =

    Pratap, Rameshwar and Verma, Bhisham Dev and Kulkarni, Raghav , title =. Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA) , pages =. 2021 , publisher =

    2021

  30. [38]

    Proceedings of the 35th International Conference on Machine Learning (ICML) , volume =

    Kang, Keegan and Wong, Weipin , title =. Proceedings of the 35th International Conference on Machine Learning (ICML) , volume =. 2018 , publisher =

    2018

  31. [39]

    Subspace Embeddings for the Polynomial Kernel , booktitle =

    Avron, Haim and Nguy. Subspace Embeddings for the Polynomial Kernel , booktitle =. 2014 , publisher =

    2014

  32. [40]

    Wainwright , title =

    Mert Pilanci and Martin J. Wainwright , title =. 2015 , url =. doi:10.1109/TIT.2015.2450722 , timestamp =

    2015

  33. [41]

    Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages =

    Ahn, Kook Jin and Guha, Sudipto and McGregor, Andrew , title =. Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages =. 2012 , isbn =. doi:10.1145/2213556.2213560 , abstract =

    2012

  34. [42]

    Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =

    Liberty, Edo , title =. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =. 2013 , isbn =. doi:10.1145/2487575.2487623 , abstract =

    2013

  35. [43]

    and Woodruff, David P

    Clarkson, Kenneth L. and Woodruff, David P. , title =. J. ACM , month = jan, articleno =. 2017 , issue_date =. doi:10.1145/3019134 , abstract =

    2017 doi

  36. [44]

    Detection of non-Coding RNAs on the Basis of Predicted Secondary Structure Formation Free Energy Change , volume =

    Uzilov, Andrew and Keegan, Joshua and Mathews, David , year =. Detection of non-Coding RNAs on the Basis of Predicted Secondary Structure Formation Free Energy Change , volume =. BMC bioinformatics , doi =

  37. [45]

    1991 , howpublished =

    Cole, Ron and Fanty, Mark , title =. 1991 , howpublished =

    1991

  38. [46]

    , title =

    Bock, R. , title =. 2004 , howpublished =

    2004

  39. [47]

    , title =

    Scholkopf, Bernhard and Smola, Alexander J. , title =. 2001 , isbn =

    2001

  40. [48]

    Asian Conference on Machine Learning , volume =

    Kang, Keegan and Kushnarev, Sergey and Pin, Wong Wei and Pratap, Rameshwar and Yeo, Haikal and Chen, Yijia , title =. Asian Conference on Machine Learning , volume =

  41. [49]

    Gradient-based learning applied to document recognition , journal =

    Yann LeCun and L. Gradient-based learning applied to document recognition , journal =. 1998 , url =. doi:10.1109/5.726791 , timestamp =

    1998 doi

  42. [50]

    The Space Complexity of Approximating the Frequency Moments , journal =

    Noga Alon and Yossi Matias and Mario Szegedy , abstract =. The Space Complexity of Approximating the Frequency Moments , journal =. 1999 , issn =. doi:https://doi.org/10.1006/jcss.1997.1545 , url =

    1999

  43. [51]

    27th International Symposium on Theoretical Aspects of Computer Science , pages =

    Braverman, Vladimir and Chung, Kai-Min and Liu, Zhenming and Mitzenmacher, Michael and Ostrovsky, Rafail , title =. 27th International Symposium on Theoretical Aspects of Computer Science , pages =. 2010 , volume =. doi:10.4230/LIPIcs.STACS.2010.2449 , annote =

    2010

  44. [52]

    Advances in Neural Information Processing Systems , volume=

    But how does it work in theory? Linear SVM with random features , author=. Advances in Neural Information Processing Systems , volume=

  45. [53]

    International conference on machine learning , pages=

    Towards a unified analysis of random Fourier features , author=. International conference on machine learning , pages=. 2019 , organization=

    2019

  46. [54]

    Advances in neural information processing systems , volume=

    On the power and limitations of random features for understanding neural networks , author=. Advances in neural information processing systems , volume=

  47. [55]

    Advances in Neural Information Processing Systems , volume=

    Scaling neural tangent kernels via sketching and random features , author=. Advances in Neural Information Processing Systems , volume=

  48. [56]

    2025 , eprint=

    Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation , author=. 2025 , eprint=

    2025

Pith tools

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