{"id":"04b03f4c-ff27-4091-9ecd-ad567e80455c","arxiv_id":"2502.05134","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Near-optimal sample complexity Θ(rd) is claimed for recovering low symmetric-rank tensors from symmetric rank-one log-concave measurements, with a lower bound of dr^{0.98-o(1)}.","lead":"This paper studies how many random symmetric rank-one measurements are needed to uniquely recover a low symmetric-rank tensor, proving N=Ω(rd) samples suffice for exact recovery via rank minimization. It also contrasts this with the much larger requirement of unstructured empirical risk minimization and gives a near-matching information-theoretic lower bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; Definition 4.1 requires the ε-net of ζS(2r) to lie inside ζS(2r), so every net point inherits the symmetric-rank bound and Proposition 4.7 applies.","rationale":"The paper's central claim rests on Proposition 3.1, whose proof is a covering argument. The reader's rejection is based on the assertion that net points may fail to have bounded symmetric rank. That assertion is contradicted by Definition 4.1, which defines an ε-net of a set X as a subset of X. The proof of Proposition 3.1 explicitly takes ζ' to be the minimal ε-net of ζS(2r), so ζ' ⊆ ζS(2r) and rank_S(T̂) ≤ 2r for every T̂ ∈ ζ'. Proposition 4.7 is therefore applicable to every net point, and the union bound in equation (18) is valid. Lemma 4.5 binds only the cardinality of this net; it does not force the proof to use points from the ζCP(2r) covering. The remaining observations are cosmetic: the high-probability bound on max_i ||X_i||_2 is stated but not written out, and the displayed constant in (11) has a harmless exponent typo. Neither changes the positive power of ε that makes the probability tend to zero as ε → 0. Since the reader's only stated load-bearing concern does not land, and I could not find another gap in the main argument, the appropriate recommendation is to accept the paper, subject to cleaning up the minor presentation issues.","tokens_in":23311,"tokens_out":32535,"duration_ms":330491,"concrete_test":"Analytic check: re-derive Lemma 4.5 and the first paragraph of the proof of Proposition 3.1 with Definition 4.1 in force; verify that the minimal ε-net of ζS(2r) has all points in ζS(2r), so Proposition 4.7's symmetric-rank hypothesis is satisfied. If, contrary to Definition 4.1, the proof used an ε-cover of ζCP(2r) directly as the net, the reader's gap would be real. Checking this directly settles the objection.","verdict_should_be":"ACCEPT","load_bearing_attack":"After checking the proof of Proposition 3.1, I do not find a load-bearing gap. The reader's concern assumes the ε-net points are inherited from the ζCP(2r) covering, but Definition 4.1 explicitly requires an ε-net of ζS(2r) to be a subset of ζS(2r), and the proof chooses the minimal such net. Hence every net point has symmetric rank at most 2r and Proposition 4.7 applies to each of them. Lemma 4.5 is used only to bound the cardinality of this minimal net, not to supply the actual net points. Two minor presentation issues exist: the tail term P[max_i ||X_i||_2 > log^{1/ℓ}(1/ε)] is not explicitly shown to vanish, and the denominator in equation (11) should be Ξ^{1/(2ℓ)} rather than Ξ^{1/ℓ}. Both are immediately repairable and do not affect the ε-exponent that drives the conclusion. The covering-number estimates, Carbery–Wright step, lower bound, and ERM arguments all appear sound.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the sample complexity of exactly recovering a low symmetric-rank tensor from symmetric rank-one measurements Y_i = <T*, X_i^⊗ℓ> with X_i having i.i.d. log-concave entries. The main result (Theorem 2.1) states that for fixed order ℓ and any log-concave D, N ≥ C r d with C > 2ℓ^2 measurement vectors suffice to recover every rank-≤r symmetric tensor via the symmetric rank minimization program (7), with probability one. The proof covers ζS(2r) by a net, applies Carbery–Wright anti-concentration with a lower bound on the second moment from an orthogonal-polynomial expansion, and takes ε→0. A converse (Theorem 2.5) gives an Ω(d r^{0.98}/log r) lower bound via Fano's inequality using a packing construction. Implications for two-layer polynomial networks are discussed (Theorem 2.2).","tokens_in":141,"tokens_out":7258,"duration_ms":162822,"significance":"If correct, the result is a near-optimal Θ(rd) sample complexity for structured tensor recovery, improving on the Θ(d^ℓ) dimension of the symmetric tensor space, and it holds for the broad class of log-concave distributions without norm constraints on the underlying vectors. The proof is self-contained except for the external Carbery–Wright inequality and the ZK23 covering-number bound; no free parameters are fitted, and the lower bound is explicit. The potential concern that the ε-net points might not lie in ζS(2r) is resolved by Definition 4.1, which requires the net to be a subset of the set being covered; the CP-rank covering is used only for cardinality. The remaining issues are presentational.","major_comments":[],"minor_comments":[{"comment":"The denominator in the Carbery–Wright bound is written as Ξ^{1/ℓ}, but since E[P(X)^2] ≥ Ξ implies sqrt(E[P^2]) ≥ Ξ^{1/2}, the correct factor is Ξ^{1/(2ℓ)}. This typo does not affect the ε-exponent that drives the conclusion, but the displayed inequality is inconsistent with Theorem 4.6.","section":"§4.3, Eq. (11)"},{"comment":"The tail term P[max_i ||X_i||_2 > log^{1/ℓ}(1/ε)] is stated to vanish as ε→0 without proof. For log-concave D this follows from standard sub-exponential tail bounds; please include a short argument for completeness.","section":"§4.3, after Eq. (20)"},{"comment":"The abstract contains a typo: 'Low-Ran k' should be 'Low-Rank'.","section":"Abstract"},{"comment":"The notation 'min_{T_hat ∈ ζ′}' is slightly imprecise: ζ′ is a finite set, and the minimum is over its elements. Rewriting as 'min_{T_hat ∈ ζ′}' is fine, but the subsequent union bound in (18) should be phrased with an explicit enumeration of the net points to avoid confusion with the covering-number exponential bound.","section":"§4.3, Eq. (15)"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound as far as I can judge. The stress-test objection about ε-net points not inheriting bounded symmetric rank is unfounded: Definition 4.1 requires the net to be a subset of ζS(2r), and the CP-rank covering is used only to bound the net size. The main proof has a small typo in Eq. (11) and an unproven tail estimate, both easily fixed. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the reader's central objection doesn't survive contact with Definition 4.1. An ε-net of ζS(2r) is required to be a subset of ζS(2r), and the proof uses a minimal such net. Every net point therefore has symmetric rank at most 2r, so Proposition 4.7 legitimately applies. Lemma 4.5 only bounds the size of that net via the CP-rank covering number; it does not supply the net points. The antisymmetric CP-rank counterexample is irrelevant because such tensors are not in the net.\n\nWhat is actually new: the paper gives near-optimal sample complexity for symmetric rank-one measurements with arbitrary log-concave entries, showing Θ(rd) samples suffice and nearly match a Fano lower bound. The ERM contrast (Θ(d^ℓ) vs Θ(rd)) is a clean sanity check. The Carbery–Wright step combined with orthogonal polynomial expansions is a genuine technical contribution, and the polynomial network identifiability application is a reasonable bonus with the NP-hardness caveat acknowledged.\n\nSoft spots are minor. The tail term P[max_i ||X_i||_2 > log^{1/ℓ}(1/ε)] is not explicitly shown to vanish; with log-concave entries and sub-exponential tails it does, but the argument should state this. The denominator in equation (11) should be Ξ^{1/(2ℓ)} from Carbery–Wright, not Ξ^{1/ℓ}; this is a typo in the paper's favor, since correcting it only strengthens the bound. Neither issue affects the ε-exponent that drives the conclusion.\n\nThe lower bound is clean, and the covering-number estimates are used correctly. Overall this is a solid, incremental contribution to high-dimensional tensor recovery. It deserves a serious referee; I would send it out rather than desk-reject, expecting minor revisions only.","headline":"The reader's main objection to the covering argument does not hold up; the paper is essentially sound and deserves serious review.","tokens_in":24040,"tokens_out":3287,"would_cite":true,"duration_ms":31929,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","62H12","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that $N \\ge C r d$ symmetric rank-one measurements recover every order-$\\ell$ tensor of symmetric rank at most $r$ with probability one, for any fixed $\\ell$ and any log-concave distribution, making the sample complexity…","keywords":["symmetric rank-one measurements","low-rank tensor recovery","rank minimization","log-concave distributions","anti-concentration","orthogonal polynomials","sample complexity","two-layer polynomial networks"],"falsifier":"For $T=e_1\\otimes e_2\\otimes e_3-e_2\\otimes e_1\\otimes e_3$, the calculation $\\mathbb{E}\\langle T, X^{\\otimes 3}\\rangle^2=0$ for any iid product distribution shows the second-moment bound cannot hold on all CP-rank-2 points, so the proof must demonstrate that an $\\epsilon$-net of $\\zeta_S(2r)$ of the claimed cardinality can be chosen with bounded symmetric rank; exhibiting a net of that size forced to contain such a point would falsify the argument.","tokens_in":23066,"feed_emoji":"🧮","tokens_out":11633,"duration_ms":115441,"temperature":0.7,"pith_summary":"This paper claims that the sample complexity of recovering an order-$\\ell$ tensor from symmetric rank-one measurements is $\\Theta(rd)$: with $N \\ge C r d$ measurements for any constant $C > 2\\ell^2$, symmetric rank minimization uniquely recovers every tensor of symmetric rank at most $r$, assuming only that the measurement vectors have entries drawn independently from any log-concave distribution. A matching lower bound shows that any estimator needs roughly $\\tilde{\\Omega}(d r^{0.98})$ measurements, so the upper bound is optimal up to a sub-polynomial factor in $r$. The result matters because this measurement model is exactly the teacher-student model for two-layer neural networks with polynomial activation $t^\\ell$, so the theorem says such networks are identifiable from $\\Theta(rd)$ samples without any norm constraints on the weights. It also exposes a sharp contrast with unstructured empirical risk minimization, which requires about $d^\\ell$ samples.","feed_headline":"Near-optimal: ~rd samples recover low-rank tensors","feed_subtitle":"Matches the information-theoretic lower bound up to a tiny factor and identifies two-layer polynomial networks.","key_machinery":"The argument is carried by the symmetric rank minimization program (7), whose analysis reduces to a geometric statement about the unit sphere $\\zeta_S(2r)$ of tensors with symmetric rank at most $2r$: with probability one, no nonzero tensor in this sphere vanishes on all $N$ measurement tensors. The proof bounds the covering number of $\\zeta_S(2r)$ by embedding it into the larger CP-rank sphere $\\zeta_{CP}(2r)$ and using a covering-number bound for CP-rank tensors. It then controls the probability that a fixed candidate tensor is near-orthogonal to all measurements with an anti-concentration inequality for the degree-$\\ell$ polynomial $\\langle T, X^{\\otimes \\ell}\\rangle$ of a log-concave random vector, and supplies the required second-moment lower bound through an orthogonal-polynomial expansion of the measurement polynomial. A union bound over the net, with $N$ chosen so that the net-entropy term is dominated by the anti-concentration exponent, makes the failure probability tend to zero as the net mesh goes to zero.","core_discovery":"The central discovery is Theorem 2.1: for fixed order $\\ell$, any log-concave distribution $D$, and any $C>2\\ell^2$, the symmetric rank minimization program (7) recovers every order-$\\ell$ tensor $T^*$ with $\\mathrm{rank}_S(T^*)\\le r$ from $N\\ge C r d$ measurements $Y_i=\\langle T^*, X_i^{\\otimes \\ell}\\rangle$ with probability one. The proof works by showing that with such $N$ there is no nonzero unit-Frobenius-norm tensor of symmetric rank at most $2r$ that is orthogonal to all measurement tensors, and the same argument gives identifiability of two-layer polynomial networks of width $r$. A companion lower bound, proved with a packing bound and a standard entropy-based information-theoretic inequality, shows that every estimator fails once $N = O(d r^{0.98}/(\\log r + \\ell\\log(Bd)))$, so the $rd$ rate is essentially the information-theoretic limit.","pith_inferences":["If the upper and lower bounds are both tight up to the $r^{0.02}$ gap, then the true minimax sample complexity is probably exactly $\\Theta(rd)$; a natural test is whether the lower-bound exponent $0.98$ can be pushed to $1$.","The proof's dependence on $\\ell^2$ is likely removable: the quadratic term comes from matching the covering entropy $2r\\ell d \\log(1/\\epsilon)$ against the anti-concentration exponent $N/\\ell$, so any sharper covering bound or anti-concentration estimate would reduce it.","Because the upper bound places no norm restrictions on the tensor, it suggests that in the noiseless teacher-student model weight magnitudes are irrelevant for identifiability; in noisy models, by contrast, weight scale should reappear through the signal-to-noise ratio.","A natural extension is to check whether a polynomial-time method, such as a convex relaxation of (7), can match $\\Theta(rd)$; the information-theoretic threshold here provides the target."],"forward_implications":["The sample bound $N=\\Theta(rd)$ is the right answer for this measurement model: recovery is possible at $C r d$ measurements for every log-concave distribution, and impossible for arbitrary estimators below roughly $d r^{0.98}$.","Two-layer polynomial networks with activation $t^\\ell$ and width $r$ are information-theoretically identifiable from $\\Theta(rd)$ input-label pairs, with no bounded-norm assumptions on the hidden weights.","Any consistent estimator, including computationally efficient ones, must ask for at least $\\tilde{\\Omega}(d r^{1-\\gamma})$ measurements for any $\\gamma>0$, providing a benchmark for future algorithms.","Unstructured empirical risk minimization is far less sample-efficient: at fewer than $\\binom{d+\\ell-1}{\\ell}$ measurements it admits zero-training-error models with arbitrarily large generalization error.","The results are noiseless and information-theoretic, so they delineate the fundamental limits before computational tractability is imposed."],"supporting_citations":[{"why":"bounds the covering number of CP-rank tensors, used to control the size of the epsilon-net.","marker":"[ZK23]"},{"why":"gives the anti-concentration estimate for low-degree polynomials of log-concave random vectors.","marker":"[CW01]"},{"why":"supplies the orthogonal-polynomial facts used in proving the second-moment lower bound.","marker":"[Lal]"},{"why":"is the low-rank matrix recovery uniqueness framework that this proof adapts.","marker":"[ENP12]"},{"why":"provides the tensor analogue and the covering-plus-union-bound template for rank minimization.","marker":"[MHWG14]"},{"why":"gives the covering-number monotonicity lemma used to pass from symmetric-rank to CP-rank covering.","marker":"[Ver18]"},{"why":"is the coding-theoretic packing construction used for the lower-bound tensor set.","marker":"[Gil52]"},{"why":"is the companion coding-theoretic packing bound used in the same construction.","marker":"[Var57]"},{"why":"supplies the entropy-based lower-bound argument for the sample-complexity lower bound.","marker":"[CT06]"}],"fun_headline_variants":["Near-optimal sample complexity for low-rank tensor recovery","Tight bounds for symmetric rank-one tensor recovery","Optimal measurements for low-rank tensors from rank-one samples","Matching lower bound: rd samples recover low-rank tensors","Polynomial networks identified: near-optimal tensor recovery"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that every point in the approximating grid used to cover the unit sphere of low-rank tensors has a symmetric decomposition into few rank-one pieces; the paper proves the needed second-moment bound only for such tensors, but the covering bound it relies on does not guarantee the grid points are of that kind.","fun_headline_variants_meta":{"raw":{"variants":["Near-optimal sample complexity for low-rank tensor recovery","Tight bounds for symmetric rank-one tensor recovery","Optimal measurements for low-rank tensors from rank-one samples","Matching lower bound: rd samples recover low-rank tensors","Polynomial networks identified: near-optimal tensor recovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000193,"raw_usage":{"total_tokens":1328,"prompt_tokens":903,"completion_tokens":425,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":346}},"tokens_in":519,"tokens_out":425,"duration_ms":5091,"temperature":1.0,"reasoning_tokens":346,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T20:09:10.981229+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $T=e_1\\otimes e_2\\otimes e_3-e_2\\otimes e_1\\otimes e_3$, the calculation $\\mathbb{E}\\langle T, X^{\\otimes 3}\\rangle^2=0$ for any iid product distribution shows the second-moment bound cannot hold on all CP-rank-2 points, so the proof must demonstrate that an $\\epsilon$-net of $\\zeta_S(2r)$ of the claimed cardinality can be chosen with bounded symmetric rank; exhibiting a net of that size forced to contain such a point would falsify the argument.","supporting_citations":[],"review_version":1}