{"id":"eea1faf0-b9ad-481f-b3ce-afea070754cb","arxiv_id":"2505.23324","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A random projection ensemble for quadratic discriminant analysis gives a fast classifier that is provably perfectly accurate in ultrahigh dimensions when the Kullback-Leibler separation between classes grows linearly with dimension.","lead":"Researchers propose RPE-QDA, a classification method that averages many random projections of quadratic discriminant analysis to handle datasets with far more variables than samples. It proves that the method can achieve perfect classification when class separation grows with dimension, while running much faster than classical QDA.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's proof does not handle the singular sample covariance: Lemma 2 assumes positive-definite covariances, but when p>n the sample covariance has rank n_k-1, so the SLLN/DCT step for the sample RPE-QDA discriminant is not justified as written.","rationale":"The sample-version theorem is central, and its proof as written applies a positive-definite-covariance lemma to a singular sample covariance. This is not a stylistic issue: the R-expectation of the projected inverse can be infinite, so the SLLN step in the proof of Theorem 3 is unjustified without an additional argument. The concern is conditional because the deferred Lemma 4 might supply that argument; hence the reader's CONDITIONAL verdict is appropriate, but the specific load-bearing assumption to check is not (A3), it is the finiteness/singularity condition in the sample proof. The simulations use n=100 with d=10, so the practical regime is far from the small-rank failure mode, but the theorem as stated has no such lower bound on n_min relative to d.","tokens_in":24131,"tokens_out":28681,"duration_ms":325275,"concrete_test":"Inspect the supplementary proof of Lemma 4 to see whether it proves finiteness of E_R[R^T(R bSigma_k R^T)^{-1}R] for singular bSigma_k of rank n_k-1 under (A4). If the proof relies on Lemma 2, it is invalid because lambda_min(bSigma_k)=0. Analytically, fix p=3, d=1, bSigma=diag(1,1,0) and compute E[r_3^2/(r_1^2+r_2^2)] with r_i iid N(0,1); this is infinite since r_3^2 is independent of the chi-square-2 denominator, so the projected quadratic form has infinite expectation. A valid proof must either impose n_min > d+2 or give a separate tail bound for the singular projected inverse.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The sample-version claim (Theorem 3) is a central part of the paper. Its proof reduces to showing, for fixed Z and training data, that B^{-1} sum of sample projected discriminants converges to its R-expectation, and that this expectation is close to the population discriminant. The text says this follows 'similar to the proof of Theorem 2' and via Lemma 4, whose proof is deferred to the supplementary. The available text, however, uses Lemma 2 to bound expectation and variance of the projected inverse. Lemma 2 is stated for positive definite Sigma and gives upper bounds proportional to 1/lambda_min(Sigma). For the sample covariance bSigma_k in the regime p > n_k, lambda_min(bSigma_k)=0, so the bound is infinite and Lemma 2 does not apply. This is not a merely technical nuisance: for a fixed singular bSigma of rank r, the R-expectation of the projected inverse can be infinite. For example, with p=3, d=1 and bSigma=diag(1,1,0), the (3,3) entry of E_R[R^T(R bSigma R^T)^{-1} R] is E[r_3^2/(r_1^2+r_2^2)] = E[r_3^2] E[1/chi_2^2] = infinity. Thus the random projected quadratic forms appearing in bDRPE can have infinite expectation, and the SLLN used in the proof of Theorem 2 does not carry over to the sample version. Assumption (A4) only requires d=o(n_min); it does not state the stronger condition n_min > d+2 that would make the inverse Wishart expectation finite. Unless Lemma 4 in the supplementary supplies a genuinely different singular-case argument, Theorem 3 lacks a load-bearing step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes RPE-QDA, a random-projection ensemble version of quadratic discriminant analysis for ultrahigh-dimensional classification. The method averages QDA discriminant functions computed in B random d-dimensional subspaces, avoiding inversion of the p×p sample covariance. The main theoretical results are Theorems 1–3: under assumptions (A1)–(A4), the population QDA rule, the population RPE-QDA rule, and the sample RPE-QDA rule all achieve perfect classification in suitable asymptotic limits. The paper also quantifies the information loss of random projection by showing that the RPE-QDA discriminant is asymptotically equivalent to a scaled KL divergence with scaling factor d/p (Remark 1, Theorem 2). The methodology is evaluated in four simulation schemes and four gene-expression data sets, with comparisons to several existing high-dimensional classifiers.","tokens_in":24545,"tokens_out":10297,"duration_ms":114210,"significance":"If the results hold, the paper makes a useful contribution: it offers a computationally inexpensive QDA procedure that can separate populations differing in covariance structure even when means, traces, and other low-dimensional summary measures are identical, a setting where several existing methods fail (Schemes 2 and 4). The d/p scaling of the discriminant is a clean and falsifiable quantification of the cost of random projection. The paper also provides code links and extensive numerical comparisons. However, the sample-version theorem currently rests on a deferred lemma and on an application of Lemma 2 to singular sample covariances, which is not justified in the submitted text; this is the main obstacle to accepting the theoretical claims as they stand.","major_comments":[{"comment":"The proof of Theorem 3 reduces the first term in equation (15) to a conditional SLLN for the sequence bD^{R_b}(Z) given (Z, X_n, Y_m), saying this follows 'similar to the proof of Theorem 2'. That argument uses Lemma 2, whose bound on E_R[R^T(RΣR^T)^{-1}R] is stated only for positive-definite Σ. For p > n_k, the sample covariance bΣ_k is singular with rank n_k − 1, so λ_min(bΣ_k) = 0 and Lemma 2 does not apply. This is not a purely technical gap: for a fixed singular bΣ of rank r, the conditional expectation can be infinite unless r > d+1. For example, with p=3, d=1, and bΣ = diag(1,1,0), the (3,3) entry of E_R[R^T(R bΣ R^T)^{-1}R] equals E[r_3^2/(r_1^2+r_2^2)] = E[r_3^2] E[1/χ_2^2] = ∞, so the projected quadratic form has infinite conditional mean and the SLLN is not available. Assumption (A4) only imposes d = o(n_min); it does not ensure n_min > d+2 for every fixed n at which the inner B→∞ limit is taken. Unless Lemma 4 in the supplementary supplies a genuinely different singular-case argument, Theorem 3 is not proved as written. A concrete fix would be to strengthen (A4) to n_min > d+2 for all n in the sequence or to provide a truncated-moment argument that avoids infinite conditional expectations.","section":"Section 7.1, proof of Theorem 3, and Lemma 4"}],"minor_comments":[{"comment":"The definitions a ∧ b = max{a,b} and a ∨ b = min{a,b} are reversed relative to standard usage and are inconsistent with the later definitions of n_min = ∧_k n_k and n_max = ∨_k n_k; this should be corrected.","section":"Section 1.2, Notations"},{"comment":"The sentence 'as RR^T ∼ Wishart(I_p, p)' has a dimension mismatch: R is d × p, so RR^T is a d × d Wishart matrix with p degrees of freedom, not Wishart(I_p, p).","section":"Section 7.1, proof of Theorem 2"},{"comment":"The notation 'p^{-1}KL_{k,k'}{1+o(1)}' inside a probability statement is ambiguous: the o(1) term should be made explicit as deterministic or as holding with probability tending to one uniformly in the relevant random variables.","section":"Theorem 2(b) and Lemma 3"}],"recommendation":"major_revision","confidential_remarks":"The supplementary file containing the proofs of Lemmas 2–4 was not part of the review package. Since Theorem 3 depends directly on Lemma 4 and on a singular-covariance extension of Lemma 2, I recommend that the editor obtain the supplement before any final decision. The singular-covariance issue raised in the major comment is not resolved in the main text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: RPE-QDA is a solid extension of Cannings–Samworth to QDA. The genuinely new bit is aggregating discriminant functions rather than decisions, which lets them derive a d/p scaling relation between the RPE discriminant and the KL divergence. That is a clean, parameter-free characterization and I believe it. The population version (Theorem 2) is well structured, and the simulations support the claim that RPE-QDA beats summary-statistic competitors in scale-only or eigen-direction settings. The paper also does the right thing in comparing with Palias–Kabán and showing where the summary-measure bounds go trivial.\n\nThe main soft spot is Theorem 3. As written, the proof leans on Lemma 2 to control the projected inverse, but Lemma 2 is stated for positive-definite covariances. In the sample version, the covariance has rank n_k−1, so the minimum eigenvalue is zero and the bound is infinite. The stress-test example shows that the R-expectation of the projected inverse can be infinite even when the projected matrix is invertible almost surely (e.g., d=1, rank 2). The assumption d=o(n_min) eventually gives n_k > d+2, so the expectation becomes finite in the limit, but that is exactly a step that needs a separate argument. The proof just says \"similar to Theorem 2\" and defers Lemma 4 to the supplement. If Lemma 4 supplies a genuine singular-case bound, fine; if not, the sample-version claim is unproven. I would not desk-reject over this, but the supplement needs to be available and the proof needs to address it explicitly.\n\nMinor things: the KL notation is muddled — the proof of Theorem 1 computes KL(P1||P0) while calling it KL_{0,1}; harmless under (A3) since the minimum is over both directions, but confusing. Table 5 reports standard deviations for real data without saying what is being averaged over (LOOCV is deterministic given the projections). And the main text repeatedly refers to lemmas in a supplement that was not available with the arXiv posting.\n\nNet: this is a real methodological contribution with an honest comparison to the literature. The population theory is credible, and the numerical evidence is broad. The sample-version proof is the one load-bearing piece I would want to see before trusting Theorem 3. I would send it to reviewers — a competent referee can check the supplementary in a day. My recommendation is to engage with it, ask for the supplement, and require a fix of the singular-covariance step before acceptance.","headline":"Worth a serious referee: the d/p scaling with KL divergence is a real insight, but the sample-version theorem rests on a deferred proof that must handle singular sample covariances.","tokens_in":25024,"tokens_out":5024,"would_cite":true,"duration_ms":49751,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that averaging QDA over many random low-dimensional projections drives the misclassification probability to zero as the dimension grows, even when the number of variables far exceeds the sample size.","keywords":["random projection ensemble","quadratic discriminant analysis","ultrahigh-dimensional classification","perfect classification","Kullback-Leibler divergence","misclassification probability","Johnson-Lindenstrauss lemma","computational complexity"],"falsifier":"Simulate two Gaussian classes with equal means and covariance matrices that differ only on a block of p^α coordinates with α<1, so the KL divergence grows like p^α and assumption (A3) fails. If RPE-QDA's error still converges to zero as p grows, the linear-KL condition is stronger than needed; if the error stays bounded away from zero, assumption (A3) is the load-bearing separation requirement.","tokens_in":23952,"feed_emoji":"🎲","tokens_out":8115,"duration_ms":75060,"temperature":0.7,"pith_summary":"The paper sets out to show that quadratic discriminant analysis (QDA) can be made to work in ultrahigh-dimensional settings, where the number of variables p dwarfs the sample size n, by averaging the QDA decision rule over many random low-dimensional projections of the data. The central claim is that this random-projection ensemble classifier, RPE-QDA, achieves perfect classification in the limit: its misclassification probability goes to zero as the dimension p grows (population version) and as both sample size and dimension grow (sample version), under assumptions that tolerate sub-exponential growth of p in n and identical class means. The reason the method succeeds is that the averaged projected discriminant function turns out to be asymptotically proportional to the Kullback-Leibler divergence between the competing Gaussian populations, scaled only by the factor d/p, where d is the small projection dimension. This makes the approach attractive because it needs no sparsity assumptions or hand-picked summary statistics of the covariance matrices, and it runs at a small fraction of classical QDA's computational cost. The paper matters because it identifies a wide regime, class separation growing linearly in p in any coordinate pattern, in which a simple, fast, projection-based quadratic rule is provably asymptotically perfect.","feed_headline":"Projected QDA hits perfect classification as dimension grows","feed_subtitle":"Averaging quadratic discriminant functions over random subspaces makes error vanish even when p dwarfs n.","key_machinery":"The object doing the work is the RPE-QDA discriminant function $D^{{RPE}}$_{k',k}(Z) = $B^{{-1}}$ Σ_{b=1}^B D^b_{k',k}(Z), the average of B QDA log-discriminants computed after projecting the data with independent i.i.d. standard Gaussian d×p random matrices. The load-bearing estimate is Lemma 2, which bounds the expected projected precision matrix Ψ = E_R[R^T(RΣR^T)^{-1}R] between (d/(p λ_max(Σ))) I and (d/(p λ_min(Σ))) I; this squeezes the averaged discriminant toward a quantity comparable to (d/p)·KL_{k,k'}, converting the ensemble of projections into a scaled version of the KL divergence and yielding the perfect-classification theorems.","core_discovery":"On its own terms, the paper claims that under assumptions (A1)-(A3), namely controlled growth of the means, covariance spectra with at most p^ξ eigenvalues deviating from a common baseline and no eigenvalue growing faster than p^α for α<1, and KL divergence between every pair of classes growing at least linearly in p, the RPE-QDA classifier satisfies lim_{p→∞} lim_{B→∞} $Δ^{{RPE-QDA}}$ = 0 (Theorem 2(c)). For the sample version, Theorem 3 gives lim_{min{n,p}→∞} lim_{B→∞} $Δ^{{RPE-QDA}}$_n = 0 under the additional balanced-design and projection-dimension condition (A4). The companion structural result, highlighted in Remark 1 and Section 3.2, is that the classical QDA discriminant is asymptotically equivalent to the KL divergence after division by p, whereas the RPE-QDA discriminant, after division by d, is asymptotically equivalent to the same KL divergence scaled by d/p; this quantifies the information loss induced by projection and is traded off against a large computational saving.","pith_inferences":["A direct consequence the authors leave implicit: the d/p factor gives a practical rule of thumb — when KL/p is only barely above the threshold ν0, the projection dimension d must be a non-negligible fraction of p to keep the scaled margin positive, so small-d ensembles will be reliable mainly when separation is diffuse across coordinates.","The theory suggests a testable extension to non-Gaussian classes with comparable log-density concentration: the same averaging should approximate a scaled divergence whenever the projected log-likelihood ratios concentrate, which the real-data experiments hint at but do not prove.","Pairing random-projection ensembles with variable screening, as the authors mention in the Discussion, could relax (A3): concentrating KL into a screened subvector would raise the effective per-coordinate divergence while keeping the d/p dilution small."],"forward_implications":["When (A1)-(A3) hold and p grows sub-exponentially in n, RPE-QDA drives the misclassification probability to zero asymptotically; the user only needs projection dimension d = O(log p) and a sufficiently large ensemble size B.","The method stays consistent when class means are identical and only covariance matrices differ, a case where trace-based and distance-based competitors degrade to random guessing (Schemes 2 and 4 of the simulations).","Computational cost drops from order O(nmax p^2 ∨ p^3) for classical QDA to O(B(d p nmax + d^3)), and the B projection steps are embarrassingly parallel.","The discriminant's d/p scaling with KL divergence quantifies how much discriminative power is lost per projection: accuracy improves as d grows, up to the sample-size limit.","Plugging in sample means and covariances costs no extra asymptotic loss: the sample RPE-QDA classifier retains the same d/p-scaled KL structure (Remark 2)."],"supporting_citations":[{"why":"Documents that classical LDA-type rules fail when p/n→∞, the failure regime this paper targets.","marker":"Bickel and Levina (2004)"},{"why":"Supplies the distance-preservation guarantee that motivates random projection as a dimension-reduction tool.","marker":"Johnson and Lindenstrauss (1984)"},{"why":"Provides the elementary JL-type bound used for randomized and sparse projection schemes.","marker":"Dasgupta and Gupta (2003)"},{"why":"Introduces the very sparse random projection distribution used as the STP variant in simulations.","marker":"Li et al. (2006)"},{"why":"The prior random-projection ensemble classifier whose decision-aggregation scheme RPE-QDA refines and outruns computationally.","marker":"Cannings and Samworth (2017)"},{"why":"Sparse QDA baseline; the paper's sparsity-free approach is contrasted with it.","marker":"Li and Shao (2015)"},{"why":"Defines the KL divergence that the discriminant functions are shown to approximate.","marker":"Kullback and Leibler (1951)"},{"why":"Derives a projected-QDA Bayes-error bound based on summary measures that becomes trivial when those measures match, the gap RPE-QDA's KL analysis fills.","marker":"Palias and Kabán (2023)"}],"fun_headline_variants":["Random projection QDA beats the curse of dimensionality","Projected QDA achieves perfect classification when p dwarfs n","RPE-QDA: perfect classification in ultrahigh dimensions","Random projection ensemble rescues QDA in high dimensions","QDA with random projections overcomes the p >> n barrier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee collapses if the true class separation, measured by Kullback-Leibler divergence, does not grow at least in proportion to the dimension p; separation concentrated in a few coordinates is not enough for the theorem, even if a good classifier exists.","fun_headline_variants_meta":{"raw":{"variants":["Random projection QDA beats the curse of dimensionality","Projected QDA achieves perfect classification when p dwarfs n","RPE-QDA: perfect classification in ultrahigh dimensions","Random projection ensemble rescues QDA in high dimensions","QDA with random projections overcomes the p >> n barrier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1605,"prompt_tokens":995,"completion_tokens":610,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":530}},"tokens_in":611,"tokens_out":610,"duration_ms":7025,"temperature":1.0,"reasoning_tokens":530,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:48:58.413690+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate two Gaussian classes with equal means and covariance matrices that differ only on a block of p^α coordinates with α<1, so the KL divergence grows like p^α and assumption (A3) fails. If RPE-QDA's error still converges to zero as p grows, the linear-KL condition is stronger than needed; if the error stays bounded away from zero, assumption (A3) is the load-bearing separation requirement.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Documents that classical LDA-type rules fail when p/n→∞, the failure regime this paper targets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the distance-preservation guarantee that motivates random projection as a dimension-reduction tool."},{"cited_title":"and Gupta, A","cited_arxiv_id":null,"evidence_quote":"Provides the elementary JL-type bound used for randomized and sparse projection schemes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The prior random-projection ensemble classifier whose decision-aggregation scheme RPE-QDA refines and outruns computationally."},{"cited_title":"and Leibler, R","cited_arxiv_id":null,"evidence_quote":"Defines the KL divergence that the discriminant functions are shown to approximate."},{"cited_title":"and Kab\\'an, A","cited_arxiv_id":null,"evidence_quote":"Derives a projected-QDA Bayes-error bound based on summary measures that becomes trivial when those measures match, the gap RPE-QDA's KL analysis fills."}],"review_version":1}