{"id":"1826174c-9ca2-4f2f-bfd0-fbc0817f5daa","arxiv_id":"2608.10523","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"The authors propose a complex-to-real version of TensorSketch that they claim reduces the variance growth of polynomial-kernel approximation from 3^p to 2^p while staying fast on sparse data. The proof of this variance bound has a missing conjugation step, so the main theoretical result fails as written.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 5 and the proof of Theorem 2 analyze a non-conjugated inner product; the actual CtR estimator is Re Σ ΦC(x)_j \\overline{ΦC(y)}_j, so the moment expansions — including the unbiasedness step — target the wrong random variable.","rationale":"The reader and I converge on the same root cause: missing conjugation in the complex inner product. I would sharpen it: the flaw already destroys the unbiasedness step, before any variance calculation. In Definition 5 the paper equates Re(ΦC(x)ΦC(y)^T) with Re ΦC(x)^T Re ΦC(y)+Im ΦC(x)^T Im ΦC(y), which is algebraically false; the latter equals Re(ΦC(x)\\overline{ΦC(y)}). The proof then expands the non-conjugated form. I could not verify the reader's specific p=1 counterexample numbers (true E|bkC|² = 4+8/D) — an exact computation for the estimator actually defined gives E[bkC²]=4+4/D and Var=8/D for p=1,x=y=(1,1) — so I mark agreement as partial. The substantive conclusion is unchanged: Theorem 2 is not proved by the manuscript. There is no machine-checked proof or released code, and the empirical section cannot validate the 2^p/D bound. I recommend REJECT: the central theoretical contribution is unsupported, even if a corrected proof might salvage the result.","tokens_in":24488,"tokens_out":42874,"duration_ms":393463,"concrete_test":"Compute the exact moments of the actual CtR estimator for p=1,d=2,x=y=(1,1),D=8 by enumerating all sign pairs (s(1),s(2)∈{±1,±i}) and all hash maps h:{1,2}→[4] (16 assignments), forming Re Σ ΦC_j \\overline{ΦC_j}, and compare E[k̂] and Var(k̂) with the proof's expansion and with Theorem 2. If E[k̂] is 2 and Var is 1, while the proof's non-conjugated expansion gives E=0, the proof is analyzing the wrong estimator; then re-derive Lemma 4 with the conjugate in place and check whether Eq (44) follows.","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing defect is that the paper proves theorems about a different quantity than the one defined by the CtR construction. In Definition 8, ΦCtR is the concatenation of Re ΦC and Im ΦC, so ΦCtR(x)^T ΦCtR(y) equals Re(ΦC(x)\\overline{ΦC(y)}) (coordinatewise conjugate), not Re(ΦC(x)ΦC(y)^T). Nevertheless, the proof of Theorem 2 sets bkC := ΦC(x)ΦC(y)^T and expands bkC = Σ_{u,v} X_uY_v S(u)S(v)1[H(u)=H(v)] with no conjugate. Under Lemma 1 this expansion is degenerate: E[S(u)S(v)] = 0 for every u,v, since for u=v it is E[Π_r s_r(u_r)^2]=0 and for u≠v some independent factor has mean zero. Consequently the proof's unbiasedness argument would give E[bkC]=0 rather than ⟨x,y⟩^p. For p=1,d=2,x=y=(1,1) the actual CtR estimator has E=2 and Var=8/D, while the proof's expansion has expectation 0. The same missing conjugate recurs in Eq (15), where |⟨CX,CY⟩|² is written as ⟨CX,CY⟩² instead of ⟨CX,CY⟩⟨CY,CX⟩, and in Lemma 4's survivor configurations: Eq (69) keeps terms with E[s_i^2]E[s_k^2]=0, so E[(Zsj(x)Zsj(y))^2] is Σ_i x_i^2y_i^2, not 2⟨x,y⟩²-Σ_i x_i²y_i². Equations (44)-(46) and the stated variance bound are not established. Small-enumeration cases suggest the final inequality may be repairable, but the submitted proof does not prove Theorem 2.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24939,"tokens_out":22876,"duration_ms":166078,"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":[{"comment":"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.","section":"Theorem 2 proof, Appendix A.1 (unbiasedness step)"},{"comment":"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.","section":"Appendix A.1, Eq. (15)"},{"comment":"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.","section":"Lemma 4, Eqs. (69) and (75)"},{"comment":"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.","section":"Appendix B, Theorem 5"}],"minor_comments":[{"comment":"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.","section":"Section 3, Eq. (5)"},{"comment":"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)}.","section":"Definition 5"},{"comment":"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.","section":"Lemma 4 proof, Eq. (58)"},{"comment":"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.","section":"Introduction and related work"},{"comment":"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.","section":"Definition 7"}],"recommendation":"reject","confidential_remarks":"The manuscript's central theorem is unproved because of fundamental algebraic errors in handling complex inner products: missing conjugates in Eq. (15), in the definition of bkC, and in the moment calculations of Lemma 4. These are not local typos but systematic errors that permeate the proof of Theorem 2 and the supporting results. In principle the variance claim might be salvageable with a correct analysis of the conjugated inner product, but that would require a substantial re-derivation of the main theorem, not minor editing. I recommend rejection of the current version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi,\n\nThe headline claim — a CtR TensorSketch with 2^p/D variance and input-sparsity time — is not established by this paper. The proof analyzes a different random variable than the one the CtR estimator defines.\n\nAs written, ΦCtR(x)^T ΦCtR(y) equals Re Σ_j ΦC(x)_j overline{ΦC(y)}_j. The proof instead sets bkC = ΦC(X) ΦC(Y)^T, expands Σ_{u,v} X_u Y_v S(u) S(v) 1[H(u)=H(v)] with no conjugation, and concludes E[bkC]=⟨X,Y⟩. But under the paper's own Lemma 1, E[S(u)S(v)]=0 for every u,v: diagonal terms have E[s_i^2]=0, off-diagonal vanish by independence. So that expansion has expectation 0, not ⟨x,y⟩^p. The same missing conjugate appears in Equation (15), where |⟨CX,CY⟩|² is written as ⟨CX,CY⟩², and in Lemma 4, whose moment calculation uses E[s(i)s(k)]=1 for i=k although Lemma 1 states E[s(i)²]=0. For p=1, d=2, x=y=(1,1), the paper's bound on E[|bkC|²] is 4+4/D; the genuine CtR estimator gives 4+8/D. The contradiction with Lemma 1 makes this an internal algebraic error, not a missing edge case.\n\nThere is real value in the attempt. Combining fourth-roots-of-unity signs with FFT-based TensorSketch and the CtR conversion is a natural and genuinely new combination, and the runtime analysis would be correct if the moment bounds held. The writing is clear and the empirical section is honest, though the plots lack error bars and the experiments do not directly verify the claimed 2^p/D scaling.\n\nMy guess is the variance bound may be repairable with a correct conjugate-inner-product analysis — small enumerations are suggestive — but the submitted proof does not get there. As it stands, the central theorem is unsupported, and the paper should not be accepted without a corrected proof. I would still send it to a knowledgeable referee: the question is worth referee time and a good referee can tell whether the fix works. But I would advise the authors to redo the moment computation, not just patch wording.\n\nRecommended verdict: major revision or reject in current form; invite resubmission with a sound proof.","headline":"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.","tokens_in":25429,"tokens_out":4498,"would_cite":false,"duration_ms":38800,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["TensorSketch","polynomial kernel","complex random variables","fourth roots of unity","CountSketch","variance reduction","random feature maps","input-sparsity sketching"],"falsifier":"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.","tokens_in":24284,"feed_emoji":"🧮","tokens_out":17624,"duration_ms":130986,"temperature":0.7,"pith_summary":"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.","feed_headline":"Complex signs shrink TensorSketch variance from 3^p to 2^p","feed_subtitle":"Swapping ±1 for fourth roots of unity keeps hashing speed while slowing the error growth of polynomial-kernel sketches.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines real-valued TensorSketch and its input-sparsity runtime, which this paper modifies; supplies the $3^p/D$ variance baseline.","marker":"[Pham and Pagh, 2013]"},{"why":"Introduces JL-type random feature maps for dot-product kernels with $O(pDd)$ cost, the dense baseline the new construction targets.","marker":"[Kar and Karnick, 2012]"},{"why":"Introduces the Complex-to-Real framework and the $(2^{p+1}-2)/D$ variance bound for dense complex sketches that this paper claims to match.","marker":"[Wacker et al., 2023]"},{"why":"Shows complex random features reduce the degree dependence from $3^p$ to $2^p$ in dense sketches, motivating the sparse variant.","marker":"[Wacker et al., 2024]"},{"why":"Defines CountSketch, the hashing primitive whose real signs are replaced by fourth roots of unity.","marker":"[Charikar et al., 2004]"},{"why":"Provides the frequency-moment sketch analysis adapted in Lemma 4 to treat each bucket as a product of independent linear sketches.","marker":"[Alon et al., 1999]"}],"fun_headline_variants":["Complex TensorSketch: 2^p variance at sparse cost","Complex signs give TensorSketch dense-level variance","Complex hashing cuts TensorSketch variance growth to 2^p","Fourth roots of unity: faster TensorSketch with 2^p variance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Complex TensorSketch: 2^p variance at sparse cost","Complex signs give TensorSketch dense-level variance","Complex hashing cuts TensorSketch variance growth to 2^p","Fourth roots of unity: faster TensorSketch with 2^p variance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000868,"raw_usage":{"total_tokens":3816,"prompt_tokens":1054,"completion_tokens":2762,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":2688}},"tokens_in":670,"tokens_out":2762,"duration_ms":17782,"temperature":1.0,"reasoning_tokens":2688,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:20:45.023781+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS) , volume =","cited_arxiv_id":null,"evidence_quote":"Introduces JL-type random feature maps for dot-product kernels with $O(pDd)$ cost, the dense baseline the new construction targets."},{"cited_title":"Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS) , volume =","cited_arxiv_id":null,"evidence_quote":"Introduces the Complex-to-Real framework and the $(2^{p+1}-2)/D$ variance bound for dense complex sketches that this paper claims to match."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows complex random features reduce the degree dependence from $3^p$ to $2^p$ in dense sketches, motivating the sparse variant."}],"review_version":1}