{"id":"22b9a21d-78c8-449f-bc5d-5ae5714891f6","arxiv_id":"2502.02668","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Imbalanced clusters are provably easier to recover than balanced ones, and a two-step gradient ascent algorithm with normalized-sample initialization achieves Θ~(d²p²) sample complexity.","lead":"A gradient-based projection pursuit algorithm is proved to recover hidden imbalanced cluster directions from high-dimensional data with roughly d²p² samples, and the sample requirement shrinks as the rare cluster becomes rarer. The paper also gives a low-degree-polynomial lower bound of d^1.5 p samples, so the two bounds bracket the difficulty of this recovery problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Initialization gap: ninit=Ω(1/p) gives only constant probability of a good start, so the claimed 1−o(1) success in Theorems 1 and 2 is not proven as stated; ninit=ω(1/p) is the natural repair.","rationale":"I read the paper's central claim as the first provable Θ~(d²p²) sample complexity for projection pursuit recovery of imbalanced clusters. The proof structure is otherwise coherent: fresh mini-batches, two-phase learning rates, and the projection-index selection are all aimed at making Lemma 1 applicable. The single load-bearing point is the initialization. Lemma 2 is a per-sample statement; the amplification to 1−o(1) requires ninit p→∞, which the stated ninit=Ω(1/p) does not guarantee. The reader's weakest assumption identifies exactly this, and I agree. The issue is repairable and does not overturn the asymptotic sample-complexity message, so the conditional verdict stands. I would not reject: the gap is a constant-factor/probability-quantification issue, not a structural flaw in the algorithm or the concentration machinery.","tokens_in":36953,"tokens_out":7558,"duration_ms":67415,"concrete_test":"Compute P(max_{j≤ninit}⟨u_j,u*⟩≥Θ(1/√(pd))) = 1−(1−Θ(p))^{ninit} for ninit=c/p with a fixed constant c and for ninit=ω(1/p). If the former is Θ(1) rather than 1−o(1) while the latter is 1−o(1), then the theorems' ninit=Ω(1/p)/Θ(1/p) is insufficient and must be strengthened to ω(1/p); also verify that the total sample count ninit+2sn remains Θ~(d²p²) for p∈(1/√d,1/2) under that strengthening.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorems claim recovery with probability 1−o(1) using ninit=Ω(1/p) (Theorem 1) or ninit=Θ(1/p) (Theorem 2). Lemma 2 shows each normalized-sample initialization is good (⟨u0,u*⟩≥Θ(1/√(pd))) with probability only Θ(p). For ninit=c/p, the probability that at least one initialization is good is 1−(1−Θ(p))^{ninit}=1−e^{−Θ(c)}, a constant in (0,1), not 1−o(1). This breaks Precondition 1 of Lemma 1, on which every subsequent concentration and progress argument depends. The same flaw appears in the Bernoulli-Rademacher proof. The repair ninit=ω(1/p) (e.g., ninit=⌈(log d)/p⌉) makes the failure probability exp(−Θ(ninit p))→0 and remains compatible with the stated Θ~(d²p²) total budget: in the worst case p=1/√d, ninit=ω(√d) and the budget Θ~(d) leaves room (e.g., ninit=√d log d). Thus the central sample-complexity message is plausible, but the theorem statements as written overclaim the success probability.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies gradient-based projection pursuit in the planted-vector model. It proposes a two-stage Riemannian gradient-ascent algorithm (Algorithm 1) using normalized-sample initializations and fresh mini-batches, and analyzes its sample complexity for two signal distributions: imbalanced two-cluster signals with the ReLU^2 projection index, and Bernoulli-Rademacher sparse signals with a kurtosis index. The central claims are that the imbalanced-cluster direction is recoverable with ~Θ(d^2 p^2) samples with probability 1-o(1), and that the Bernoulli-Rademacher direction is recoverable with ~Θ(d^3 p^4) samples with probability 1-o(1). The paper also derives a low-degree lower bound of the form n = ~O(d^{1.5} p) for the imbalanced setting, and reports synthetic and real-data experiments on FashionMNIST and the Human Activity Recognition dataset.","tokens_in":37175,"tokens_out":9428,"duration_ms":84784,"significance":"If the theorem statements were fully proved, the main contribution would be a provable demonstration that, in planted-vector projection pursuit, imbalanced clusters become statistically easier as the minority probability p shrinks, complementing existing spectral and low-degree results. The low-degree calculation extends the Mao-Wein framework to a non-symmetric signal distribution, and the experiments, including the information-gain evaluation on real data, support the practical relevance of the method. The paper is also careful to label the low-degree conjecture as a conjecture and to state limitations in the appendix. However, the probability claims in Theorems 1 and 2 currently outrun the proofs: two union-bound steps support only constant success probability, so the significance is conditional on a repair.","major_comments":[{"comment":"Precondition 1 of Lemma 1 requires that, with probability 1-o(1), at least one of the ninit normalized-sample initializations satisfies <u0,u*> ≥ Θ(1/sqrt(pd)). Lemma 2 establishes this event only with per-initialization probability Θ(p). For ninit = Ω(1/p), as stated in Theorem 1, or ninit = Θ(1/p), as stated in Theorem 2, the probability that at least one initialization succeeds is 1 - (1 - Θ(p))^{ninit} = 1 - exp(-Θ(1)), a constant strictly between 0 and 1, not 1-o(1). Since every subsequent gradient-concentration argument in Appendices B.1 and C.1 starts from this good initialization, the claimed success probability in Theorems 1 and 2 is not proved as written. The natural repair is to state ninit = ω(1/p), for example ninit = ceil((log d)/p), which makes the initialization failure probability exp(-Θ(ninit p)) -> 0 and remains compatible with the stated total sample budgets in both theorems.","section":"§2.4, Lemma 2 and Theorem 1; also Theorem 2"},{"comment":"Precondition 2 of Lemma 1 is stated per gradient step with failure probability 1 - O(1/s), and the proof applies a union bound over s = Ω(log d) steps. This yields a total failure probability of O(1), not o(1): (1 - C/s)^s tends to e^{-C}. The applications in the proofs of Theorems 1 and 2 also state concentration bounds 'with probability at least 1 - Θ(1/s)' and then iterate over s = Θ(log d) steps, so the same constant-failure issue arises there. To obtain the 1-o(1) conclusion of Lemma 1, the per-step failure probability must be o(1/s), for example 1/s^{1+ε}, which would require restating Precondition 2 or choosing the concentration parameters and sample size accordingly. As written, the high-probability claim in Theorems 1 and 2 is again only a constant success probability.","section":"§2.3, Lemma 1 and Appendix A; applications in Appendices B.1 and C.1"}],"minor_comments":[{"comment":"The parameter range is misstated: the theorem says p ∈ (1/2, 1/sqrt(d)), while the surrounding text and the proof use p ∈ (1/sqrt(d), 1/2).","section":"Theorem 1 statement"},{"comment":"The interval p ∈ (1/sqrt(p), 1/2) is a typo; it should be p ∈ (1/sqrt(d), 1/2).","section":"Remark 1"},{"comment":"The pseudocode is ambiguous: line 5 passes a single vector u to the gradient-ascent subroutine, but Algorithm 2 loops over j = 1,...,ninit and needs a collection of initializations; lines 5-6 also overwrite ^u before line 7 selects among the set {^u_j}. Please clarify that the two-stage ascent is applied to each of the ninit initializations and that the returned set is produced before selection.","section":"Algorithm 1 pseudocode"},{"comment":"The conclusion describes the low-degree bound as 'n = ~Θ(d^{1.5} p)', but Theorem 3 only demonstrates failure of low-degree tests for n = O(d^{1.5} p); this is a lower bound of Ω(d^{1.5} p), not a matching Θ statement, since no corresponding upper bound is proved.","section":"Section 5, conclusion"},{"comment":"In the caption of Figure 1b, the parameter choices are listed as p ∈ {d^{-0.5}, d^{-0.5}, 0.3}; the repeated d^{-0.5} appears to be a typo, likely d^{-0.4}, and the red-line slopes (3, 1.8, 1) should be checked against those parameter values.","section":"Figure 1 caption"}],"recommendation":"major_revision","confidential_remarks":"The two technical gaps identified in the major comments are local and plausibly repairable within the manuscript's scope: restating ninit as ω(1/p) and tightening the per-step failure probability in Lemma 1 to o(1/s) would make the theorem statements consistent with the proofs. If the authors make those repairs carefully, I would be willing to support acceptance. The paper's topic and methods appear suitable for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core claim—that gradient projection pursuit with ReLU2 recovers imbalanced clusters using ~Theta(d^2 p^2) samples—is plausible and well-supported by the appendix. But the theorem statements as written overclaim the success probability: Lemma 2 gives each normalized-sample initialization a good overlap with probability Theta(p), so ninit = Omega(1/p) only yields a constant chance that any initialization is good, not 1 - o(1). The same issue affects Theorem 2. The repair is straightforward—take ninit = omega(1/p), e.g. ceil(log(d)/p)—and this fits the stated sample budget. So the main sample-complexity message survives, but the formal statements need revision.\n\nWhat is actually new: the ReLU2 analysis for imbalanced clusters with a provable ~Theta(d^2 p^2) bound; the low-degree lower bound n = Omega~(d^1.5 p) for B(p), correctly labeled as conditional on the Low-Degree Conjecture; and the general Lemma 1 framework that cleanly separates initialization, gradient concentration, and model selection. The Bernoulli-Rademacher analysis is new but suboptimal compared to spectral methods, and the authors say so. The experiments on FashionMNIST and HAR are a genuine plus: ReLU2 projection pursuit gives useful label information at small sample sizes. The appendix is detailed; the concentration arguments for the gradient and the model-selection step are non-trivial and, as far as I checked, mostly sound.\n\nWeak spots beyond the initialization issue: Theorem 1's stated interval p in (1/2, 1/sqrt(d)) is reversed (should be (1/sqrt(d), 1/2)); a typo, but one that must be corrected. The low-degree bound is conditional on a conjecture, which is standard but should be kept prominent. The empirical section would be stronger with code or full hyperparameter details; without them, the real-data results are suggestive rather than fully reproducible.\n\nWho should read this: people working on statistical-computational gaps for planted vector problems, and anyone using projection pursuit in low-sample regimes. It deserves a serious referee; with the initialization fix and the typo corrected, I would be comfortable with the main theorem.","headline":"The sample-complexity story is plausible and the appendix is substantial, but Theorems 1 and 2 overclaim success probability due to an initialization gap that needs a simple fix.","tokens_in":37760,"tokens_out":3066,"would_cite":true,"duration_ms":29707,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H12","62F12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Gradient projection pursuit provably recovers imbalanced cluster directions with ~(d^2 p^2) samples, and imbalance reduces cost.","keywords":["projection pursuit","planted vector","imbalanced clusters","gradient ascent","sample complexity","low-degree polynomials","Riemannian gradient","Bernoulli-Rademacher"],"falsifier":"Run only the initialization stage on synthetic planted data: for each $p$ and $d$, draw $\\lceil C/p\\rceil$ normalized samples and record the frequency with which the best overlap reaches $\\Theta(1/\\sqrt{pd})$; if that frequency converges to $1-e^{-C}$ instead of to $1$, Theorem 1's probability claim is false as stated.","tokens_in":36710,"feed_emoji":"🎯","tokens_out":14229,"duration_ms":127250,"temperature":0.7,"pith_summary":"This paper proves a sample-complexity guarantee for projection pursuit in a planted-vector model: a gradient-based algorithm recovers the hidden direction of an imbalanced two-cluster distribution with $\\widetilde{\\Theta}(d^2 p^2)$ samples, where $d$ is dimension and $p$ is the probability of the rare cluster. The central claim is that imbalance helps—as $p$ shrinks, the sample cost drops, so recovering a rare cluster is provably easier than recovering a balanced one. The same proof machinery gives a Bernoulli–Rademacher planted-vector guarantee with $\\widetilde{\\Theta}(d^3 p^4)$ samples, and the paper derives low-degree lower bounds close to both rates. The upshot is that projection pursuit is not only cheap to run, at $\\mathcal{O}(nd)$ per epoch, but also statistically analyzable, coming within a $\\sqrt{dp}$ factor of a conjectured computational-hardness benchmark. On FashionMNIST and the Human Activity Recognition dataset, the ReLU² projection separates one class from the rest even with only a few hundred samples.","feed_headline":"Imbalanced clusters are easier to find: ~(d^2 p^2) samples","feed_subtitle":"Projection pursuit provably recovers imbalanced cluster directions; the rarer the cluster, the fewer samples it needs.","key_machinery":"The load-bearing object is the planted-vector model $x\\sim N(\\nu u^\\ast, I_d-u^\\ast u^{\\ast\\top})$ with $\\nu\\sim B(p)$, two clusters at $\\mu_1=\\sqrt{(1-p)/p}$ and $\\mu_2=-\\sqrt{p/(1-p)}$; unit variance means PCA-type whitening cannot see the signal. The argument runs on the Riemannian gradient of the ReLU² projection index, projected orthogonal to the current direction and renormalized; Lemma 4 shows the expected gradient along $u^\\ast$ is $\\Theta(\\langle u,u^\\ast\\rangle^2/\\sqrt{p})$ in the early regime and $\\Theta(\\langle u,u^\\ast\\rangle)$ near convergence, so a large first learning rate $\\eta_1=\\Omega(\\sqrt{dp})$ makes geometric progress and a small second rate $\\eta_2=\\Theta(1)$ polishes the estimate. Fresh mini-batches make gradient estimates independent across the $s=\\Theta(\\log d)$ steps, and normalized-sample initialization yields overlap $\\Theta(1/\\sqrt{pd})$ with probability $p$, beating random initialization for small $p$.","core_discovery":"In the paper's own terms, Theorem 1 states that for any $\\beta>0$ and $p\\in(1/\\sqrt{d},1/2)$, there exist parameters such that Algorithm 1, run with $\\varphi(x)=\\max\\{0,x\\}^2$, outputs $\\hat{u}$ with $\\langle\\hat{u},u^\\ast\\rangle\\ge 1-\\beta$ with probability $1-o(1)$, using $n=\\widetilde{\\Theta}(d^2p^2)$ samples from the imbalanced-clusters planted-vector model $\\nu\\sim B(p)$. The proof is organized by Lemma 1, which reduces convergence to three preconditions: at least one normalized-sample initialization must start with overlap $\\Theta(1/\\sqrt{pd})$; the Riemannian gradient estimate must expand that overlap multiplicatively while $\\langle u,u^\\ast\\rangle$ is below a threshold; and the projection index $\\psi=\\varphi$ must separate converged from unconverged directions by a sample-efficient threshold. A separate low-degree calculation (Theorem 3) shows that no low-degree polynomial test can solve the hypothesis-testing problem for $n=\\widetilde{\\Theta}(d^{1.5}p)$ samples, so the algorithm's guarantee sits near the conjectured computational limit.","pith_inferences":["An implicit consequence is that the ReLU² projection is effectively locating a rare, heavy-tailed group, so the algorithm should transfer to outlier detection; this is testable by contaminating standard data with a rare cluster and checking whether the sample-complexity slope tracks $p$.","The $\\sqrt{dp}$ gap to the low-degree lower bound is left open, but the paper's moment-based analysis suggests a spectral method built on higher-order moments, exploiting the distribution's skewness, might close it.","Because fresh mini-batches are needed only for the analysis, the low-dimensional experiments with resampling suggest a practical streaming variant could reuse a single pass over data; that is a natural testable extension."],"forward_implications":["Imbalanced clusters are provably easier: in the planted model, the sample-complexity bound $\\widetilde{\\Theta}(d^2p^2)$ decreases as the rare cluster becomes rarer.","The general Lemma 1 template applies to other projection indices and distributions; the paper instantiates it for kurtosis on Bernoulli–Rademacher vectors at $\\widetilde{\\Theta}(d^3p^4)$ samples.","Under the Low-Degree Conjecture, no polynomial-time test can beat $\\widetilde{\\Theta}(d^{1.5}p)$ samples in the imbalanced setting, so the gradient algorithm is within a $\\sqrt{dp}$ factor of the conjectured computational limit.","On FashionMNIST and Human Activity Recognition, the ReLU² projection yields directions with high information gain about class labels even when only a few hundred samples are available."],"supporting_citations":[{"why":"Supplies the planted-vector problem, the low-degree lower-bound method, and the Theta-tilde(d^2 p^2) bound for Bernoulli–Rademacher that the paper extends to imbalanced clusters.","marker":"[24]"},{"why":"Provides the normalized-sample initialization that gives the algorithm a good starting overlap with probability p.","marker":"[35]"},{"why":"Gives the gradient-based planted-vector recovery framing and the observation that practical sample complexity can beat the theoretical bounds.","marker":"[34]"},{"why":"Gives the moment-matching low-degree bound whose assumptions fail for small p, motivating the paper's new lower-bound proof.","marker":"[8]"},{"why":"Formalizes the low-degree likelihood-ratio formalism used to state the computational-hardness conjecture.","marker":"[19]"},{"why":"States the Low-Degree Conjecture on which the computational lower bound rests.","marker":"[12]"},{"why":"Establishes the optimality of thresholding the likelihood ratio, which the low-degree lower-bound argument starts from.","marker":"[26]"}],"fun_headline_variants":["Rare clusters need fewer samples in projection pursuit","Imbalanced clusters: fewer samples, easier recovery","Projection pursuit finds rare clusters with fewer samples","Imbalanced clusters: provably easier recovery"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on having at least one of the random starting directions begin close to the true direction with near-certain probability, but the bound it proves gives each starting direction only a constant chance of being close, so the stated number of starts does not deliver the claimed near-certainty.","fun_headline_variants_meta":{"raw":{"variants":["Rare clusters need fewer samples in projection pursuit","Imbalanced clusters: fewer samples, easier recovery","Projection pursuit finds rare clusters with fewer samples","Imbalanced clusters: provably easier recovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000668,"raw_usage":{"total_tokens":3049,"prompt_tokens":947,"completion_tokens":2102,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":2044}},"tokens_in":563,"tokens_out":2102,"duration_ms":16014,"temperature":1.0,"reasoning_tokens":2044,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:32:09.608238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run only the initialization stage on synthetic planted data: for each $p$ and $d$, draw $\\lceil C/p\\rceil$ normalized samples and record the frequency with which the best overlap reaches $\\Theta(1/\\sqrt{pd})$; if that frequency converges to $1-e^{-C}$ instead of to $1$, Theorem 1's probability claim is false as stated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the normalized-sample initialization that gives the algorithm a good starting overlap with probability p."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the gradient-based planted-vector recovery framing and the observation that practical sample complexity can beat the theoretical bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the Low-Degree Conjecture on which the computational lower bound rests."},{"cited_title":"Neyman, E","cited_arxiv_id":null,"evidence_quote":"Establishes the optimality of thresholding the likelihood ratio, which the low-degree lower-bound argument starts from."}],"review_version":1}