{"id":"81acf65e-9cb3-423f-8e48-08104fa2d754","arxiv_id":"2505.08146","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Tensor Sketch approximates the polynomial kernel with low-dimensional random features in O(n(d + D log D)) time, but the revised variance bound in this version is not established by the proof.","lead":"This paper describes a fast way to approximate polynomial kernel functions, a math tool used to find nonlinear patterns in data, by projecting data into a smaller space in near-linear time. The method was introduced in 2013; this version corrects the error analysis and surveys where the method is now used.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9's (3p-1)/D variance bound rests on Lemma 8, whose proof yields only 3^p; a p=2 example already violates the claimed constant, so the new guarantee is unsupported.","rationale":"The reader's REJECT is correct, and the load-bearing claim is indeed Theorem 9's variance bound. I differ slightly on where the proof fails: the collision-filtered-to-AMS transfer can be repaired, but Lemma 8's stated (3p-1) bound is contradicted by a simple p=2 evaluation. The paper's own proof of Lemma 8 visibly terminates at 3^p, and the exact computation for x=y uniform on 4 coordinates gives 21/4, not <=5. The related-work paragraph's statement that the original Tensor Sketch has exponential p-dependence corroborates the problem: if Theorem 9 were correct, that characterization would be false. The algorithmic construction and runtime analysis are not the issue; the new variance guarantee is unsupported. No adjustment to the reader's rejection is needed.","tokens_in":19151,"tokens_out":23214,"duration_ms":222431,"concrete_test":"Recompute Lemma 8 for p=2, x=y=(1/2,1/2,1/2,1/2), with s1,s2 independent 4-wise hash functions. Using the displayed formula in Lemma 8, each factor has E[(Z_{s_j}(x)Z_{s_j}(y))^2] = 2<x,y>^2 + ||x||^2||y||^2 - 2\\sum_i x_i^2 y_i^2 = 5/2, and E[Z] = <x,y>^2 = 1. Hence Var(Z) = E[Z^2] - E[Z]^2 = (5/2)^2 - 1 = 21/4, which exceeds the lemma's claimed (3p-1) = 5. If this arithmetic is confirmed, Theorem 9's final inequality cannot follow from Lemma 8 as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's new theoretical claim is Theorem 9, Var[<Cx(p),Cy(p)>] <= (3p-1)/D ||x||^{2p} ||y||^{2p}. The proof's last inequality invokes Lemma 8, which asserts Var(Z) <= (3p-1)||x||^{2p}||y||^{2p} for Z = \\prod_{j=1}^p Z_{s_j}(x) Z_{s_j}(y). But the proof of Lemma 8 factorizes across the independent functions s_j, bounds each factor by 3||x||^2||y||^2, and concludes E[Z^2] <= 3^p ||x||^{2p}||y||^{2p}; it never establishes the printed (3p-1) constant. This is not a harmless looseness. For p=2 and x=y=(1/2,1/2,1/2,1/2), the paper's own formula in Lemma 8 gives E[(Z_{s_j}(x)Z_{s_j}(y))^2] = 2<x,y>^2 + ||x||^2||y||^2 - 2\\sum_i x_i^2 y_i^2 = 5/2, so Var(Z) = (5/2)^2 - 1 = 21/4 > 5 = (3p-1)||x||^4||y||^4. Thus Lemma 8 is false as stated. Since Theorem 9 uses this lemma as the final step, the claimed linear-in-p dependence on D is not proven. The paper itself acknowledges an error in the conference version's Lemma 6 and says the dependence on p is being corrected, but the correction repeats a similar unsupported constant. Section 2's claim that the original Tensor Sketch has exponential p-dependence is consistent with a 3^p/D bound and inconsistent with Theorem 9's polynomial bound, further indicating that the proof does not establish the theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19510,"tokens_out":25866,"duration_ms":256161,"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":[{"comment":"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.","section":"4.3, Theorem 9"}],"minor_comments":[{"comment":"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.","section":"4.1, Eq. (2)"},{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Table 1"},{"comment":"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.","section":"3.5, Lemma 8, proof"}],"recommendation":"reject","confidential_remarks":"The load-bearing error is in the main revised theoretical result: Lemma 8 is false, and the proof of Theorem 9 depends on it. The natural fix of replacing (3p-1) with 3^p removes the paper's claimed linear-in-p improvement over Ahle et al. and leaves the paper with a known exponential-in-p bound and no experiments, which is unlikely to meet the bar for this journal unless the authors can supply a genuinely correct proof of the stronger claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me cut to the chase: this is an extended journal re-publication of the well-known Tensor Sketch algorithm, and the only genuinely new thing it offers — the revised variance bound in Theorem 9 — does not hold. The proof depends on Lemma 8, which is false as stated; the proof of Lemma 8 factorizes across p and delivers 3^p, not (3p−1), and a p=2 example violates the claimed constant. So the paper's new theoretical claim is unsupported.\n\nThat said, the paper is not a bad paper in its core. The Tensor Sketch construction itself is correctly described: the convolution trick, the O(n(d + D log D)) runtime, and unbiasedness are standard and sound. The survey of downstream applications is useful, and the authors are transparent that the conference version had an error. The citation pattern looks honest; the self-citation to Pham and Pagh (2013) is appropriate because the algorithm is theirs.\n\nThe soft spots are all in the new analysis. Lemma 8's proof does not establish the printed constant; the step from the factorization to (3p−1) is absent. For p=2, with x=y=(1/2,1/2,1/2,1/2), the paper's own formula gives E[(Z_s(x)Z_s(y))^2] = 2<x,y>^2 + ||x||^2||y||^2 − 2∑ x_i^2 y_i^2 = 5/2, so Var(Z) = (5/2)^2 − 1 = 21/4 > 5 = (3p−1)||x||^4||y||^4. That is a direct counterexample to Lemma 8. Theorem 9 inherits the problem, and the proof also transfers from collision-filtered sums to an AMS second moment without justifying it — a step that is especially problematic since the paper itself admits the composite sign hash is not 4-wise independent.\n\nTwo smaller issues: the abstract promises empirical evaluations that do not appear, and the related-work paragraph says Ahle et al. improve on the exponential p-dependence of the original Tensor Sketch, which contradicts Theorem 9's polynomial bound. If the theorem were true, the original Tensor Sketch would already have polynomial dependence.\n\nVerdict: the algorithm is real and the method works, but this version does not establish the new guarantee. The paper is best seen as a survey with a broken proof. I would not cite the variance bound, and I would not publish as is. That said, it deserves serious peer review: the topic is important, the algorithm is influential, and the variance question is worth a correct answer. A referee could give the authors a concrete path to fix the constant or retract the claim. I'd recommend sending it out with a request for heavy revision.","headline":"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.","tokens_in":20065,"tokens_out":3407,"would_cite":false,"duration_ms":31146,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["Tensor Sketch","polynomial kernel approximation","random feature maps","Count Sketch","Fast Fourier Transform","hash-based sketching","AMS sketch","kernel methods"],"falsifier":"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.","tokens_in":18886,"feed_emoji":"⚡","tokens_out":15388,"duration_ms":133977,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tensor Sketch computes polynomial kernel features in near-linear time","feed_subtitle":"By convolving p Count Sketches with FFTs, it cuts kernel feature time from quadratic to O(n(d + D log D)).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the fast convolution algorithm that computes the Count Sketch of an outer product in O(d + D log D) using polynomial multiplication and FFT.","marker":"Pagh (2013)"},{"why":"Defines Count Sketch and its collision-based inner-product estimator, the primitive Tensor Sketch lifts to tensor powers.","marker":"Charikar et al. (2002)"},{"why":"Provides the sign-hash sketch whose bias and variance lemmas underlie the base case and the moment analysis used in the proof.","marker":"Alon et al. (1999)"},{"why":"Establishes the AMS-on-product-domains variance bound that the paper's Lemma 8 and Theorem 9 invoke for the (3p-1) factor.","marker":"Braverman et al. (2010)"},{"why":"Gives the Maclaurin-based random feature baseline for polynomial kernels whose O(dD) runtime Tensor Sketch improves.","marker":"Kar and Karnick (2012)"},{"why":"Conference version of this method; its incorrect Lemma 6 is the result the revised variance analysis corrects.","marker":"Pham and Pagh (2013)"},{"why":"Supports the existence of small-space, constant-evaluation 2-wise and 4-wise independent hash families used by the sketch.","marker":"Carter and Wegman (1979)"},{"why":"Justifies that the sum-mod-D composition of pairwise independent bucket hashes remains pairwise independent, a step in Theorem 9's proof.","marker":"Pˇ atra¸ scu and Thorup (2012)"}],"fun_headline_variants":["Tensor Sketch: near-linear polynomial kernel features","Avoid the tensor power: sketch polynomial kernels faster","Tensor Sketch cuts polynomial kernel time to near-linear","Polynomial kernel approximation in near-linear time","Tensor Sketch: Count Sketch meets FFT for kernels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tensor Sketch: near-linear polynomial kernel features","Avoid the tensor power: sketch polynomial kernels faster","Tensor Sketch cuts polynomial kernel time to near-linear","Polynomial kernel approximation in near-linear time","Tensor Sketch: Count Sketch meets FFT for kernels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000569,"raw_usage":{"total_tokens":2681,"prompt_tokens":918,"completion_tokens":1763,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":534,"completion_tokens_details":{"reasoning_tokens":1693}},"tokens_in":534,"tokens_out":1763,"duration_ms":12914,"temperature":1.0,"reasoning_tokens":1693,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:03:51.967910+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Finding frequent items in data streams","cited_arxiv_id":null,"evidence_quote":"Defines Count Sketch and its collision-based inner-product estimator, the primitive Tensor Sketch lifts to tensor powers."},{"cited_title":"AMS without 4-wise independence on product domains","cited_arxiv_id":null,"evidence_quote":"Establishes the AMS-on-product-domains variance bound that the paper's Lemma 8 and Theorem 9 invoke for the (3p-1) factor."},{"cited_title":"Fast and scalable polynomial kernels via explicit feature maps","cited_arxiv_id":null,"evidence_quote":"Conference version of this method; its incorrect Lemma 6 is the result the revised variance analysis corrects."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the existence of small-space, constant-evaluation 2-wise and 4-wise independent hash families used by the sketch."}],"review_version":1}