{"id":"298b62ba-5e86-4b71-a589-cc444bc59c75","arxiv_id":"2607.23914","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Oja's algorithm undergoes a sharp phase transition at n ≈ d log d / [δ(2θ²−δ)]: below the threshold the overlap with the planted direction vanishes; above it, it tends to sqrt((θ²−δ/2)/(θ²(1+δ/2))), and exactly at threshold the overlap has a random Gaussian law.","lead":"Oja's online PCA algorithm requires n proportional to d log d samples — not just n proportional to d — before its output starts to align with the true top eigenvector, and the paper pins down the exact threshold and the random overlap at criticality. For a smart generalist, this is a clean example of how streaming algorithms can be far more sample-hungry than offline PCA, with an exact, testable phase-transition law.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Core risk is the martingale-replacement and ODE approximations (Lemmas 6.2, 6.6); the centering misstatement in Lemma 3.2 makes the proof's exact claims technically false, though the effect appears lower-order.","rationale":"The reader's weakest assumption identifies the same load-bearing region: the martingale replacement (Lemma 6.2) and the ODE approximation (Lemma 6.6). I reviewed the error bounds and found them internally consistent, but they are not machine-checked and the centering misstatement in Lemma 3.2 shows the proof's exact claims are not all literally true. The bias is lower-order and appears not to affect the leading constants, so I do not see a reason to change the verdict from CONDITIONAL. A concrete independent check of the bias and the L2 decay would settle whether the approximations hold as stated.","tokens_in":25612,"tokens_out":35482,"duration_ms":301907,"concrete_test":"Independently recompute E[M_k|F_{k−1}] from (16) using the exact distribution of (A,C,D): if the centering is corrected to (d−2)/d, the bias is zero. Then simulate the scaled quantity d^{−1}∑ c_d^{n−k} S_k for n ≈ γ_* d log d at d = 5,000 and 20,000 and check its empirical variance decays like log d / d. If the decay is slower, or the bias term is O(ρ/d) rather than O(ρ/d^2), the constants γ_*, ρ_* would be suspect.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on two approximation steps. Lemma 6.2 replaces the true martingale increments M_k by the iid products δA_kC_k, bounding the difference S_k by ρ_{k-1} times bounded moments; Lemma 6.6 approximates the discrete recursion by the logistic ODE over k ≤ 2t_d d. Both error bounds are then propagated through the amplification factor c_d^{n−k} ≈ exp(α(n−k)/d) over n ≈ γ_* d log d steps. The written bounds are plausible: E(S_k^2) ≤ C Eρ_{k−1}^2 ≤ C exp(2αk/d)/d, so the L2 norm of the weighted sum is O(n exp(2αn/d)/d^3), which vanishes for n/dlogd ≤ γ_*; the ODE error is C(√(t_d/d)+t_d/d)exp(C t_d)→0 for t_d = log log d. However, Lemma 3.2's definition of M_k is not exactly centered: the term −δ^2ρ(B^2||D||^2/d − (θ^2ρ^2+1))/2 uses E[B^2||D||^2/d | F] = (θ^2ρ^2+1)(d−2)/d, not (θ^2ρ^2+1), so E[M_k|F_{k−1}] = δ^2ρ(θ^2ρ^2+1)/d ≠ 0. This makes S_k in Lemma 6.2 not a true martingale difference, and the L2 variance computation omits the squared mean. Quantitatively the omitted bias contributes O(ρ/d^2) per step and O(log d/d) after amplification, so it is negligible for the threshold; but the proof as written is technically incorrect, and the same type of uncaught O(ρ/d) error in the drift would shift γ_* and ρ_*. Thus the load-bearing concern is whether the error estimates in Lemmas 6.2, 6.6, and the centering in Lemma 3.2 remain valid after exponential amplification over the d log d horizon.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes Oja's online PCA algorithm on the Gaussian spiked covariance model with random initialization and step size δ/d. It claims a sharp phase transition in the scaling n/(d log d): below γ_* the overlap with the signal vanishes, above γ_* it converges to ρ_*, and in an O(d) window around criticality the overlap has an explicit Gaussian-mixture limit. The proof is based on an approximate one-dimensional recursion for the signed overlap, a martingale approximation that replaces the noise by i.i.d. products, and a comparison with the logistic ODE after a search phase of length γ_* d log d. The same constants and critical law are claimed for a spherical-gradient variant. Numerical experiments and QQ plots are provided in support.","tokens_in":26119,"tokens_out":26617,"duration_ms":223476,"significance":"If the results are correct, they establish that random-initialized Oja requires Θ(d log d) samples for any nonvanishing overlap, in contrast to offline PCA's Θ(d) scaling, and they give exact constants and a non-Gaussian critical distribution. This is a substantial contribution to the high-dimensional theory of online PCA and stochastic gradient descent. The paper is commendably concrete: the constants γ_* and ρ_* are explicit closed-form expressions, the critical law is stated exactly, the logistic-ODE solution is used rather than a qualitative approximation, and the simulations validate the predicted thresholds, plateaus, and Gaussian QQ behavior. The derivation is not circular: the constants come from the recursion, not from the data.","major_comments":[{"comment":"The claimed martingale property of M_k is false as stated. In the last term of Eq. (16), the centering constant is θ^2ρ_{k-1}^2+1, but E[B_k^2 ||D_k||^2/d | F_{k-1}] = (θ^2ρ_{k-1}^2+1)(d-2)/d. Consequently E[M_k|F_{k-1}] = δ^2 ρ_{k-1}(θ^2ρ_{k-1}^2+1)/d ≠ 0. This is a lower-order O(ρ/d^2) contribution to the recursion after division by d, so the main constants and conclusions are probably unaffected. However, Lemma 6.2 explicitly treats S_k = M_k − δ A_k C_k as a martingale difference, so the proof of the central approximation is not valid as written. The fix is to center the last term using the correct conditional mean and absorb the difference into R_k, or to carry the nonzero mean through Lemma 6.2. Given that this lemma underlies Theorems 3.4–3.6, the proof needs correction before publication.","section":"Lemma 3.2, Eq. (16)"},{"comment":"The L^2 bounds that justify replacing M_k by δ A_k C_k omit the squared-mean contribution that appears once S_k is not a true martingale difference. With E[S_k|F_{k-1}] = O(ρ_{k-1}/d), the omitted term is of order n^2 e^{2α n/d}/d^5, which tends to zero at the relevant scalings, so the lemma is salvageable; but the proof should state and estimate this term. In addition, Lemma 6.3's displayed variance computation drops a factor of d: ∑_{k=0}^n c_d^{2k} ∼ d(e^{2α n/d}−1)/(2α), so the second equality should contain an extra 1/d. Without that factor, the expression diverges; restoring it gives the stated limit γ_*δ^2(θ^2+1). These are proof errors in exactly the estimates that feed the critical law, and they should be fixed explicitly.","section":"Lemmas 6.2 and 6.3"}],"minor_comments":[{"comment":"In the proof, for α<0 the intermediate term C/(2α d) exp(2αk/d) is negative; the α<0 case should be bounded separately. The final bound E|ρ_k|^3 ≤ C exp(3αk/d)/d^{3/2} remains true, but the displayed derivation is not valid as written.","section":"Lemma 6.1"},{"comment":"The table headers list δ=0.2 for both tables, but the reported γ_* and ρ_* values correspond to δ=0.6 and δ=1, respectively (compare Figure 6). The labels should be corrected.","section":"Tables 7 and 8"},{"comment":"The formula for γ_* is ambiguous as typeset: it should read γ_* = 1/[2δ(θ^2 − δ/2)_+] or equivalently 1/[δ(2θ^2 − δ)_+], not '1/2δ(θ^2−δ/2)_+'.","section":"Abstract and Eq. (10)"},{"comment":"The Gronwall argument is applied with a right-hand side that depends on k (through √k and k). The argument works because the bound is monotone in k, but this should be stated explicitly.","section":"Lemma 6.6"}],"recommendation":"major_revision","confidential_remarks":"The reader's conditional assessment is fair. The main results are plausible, well supported by the simulations, and likely correct; the issues are technical but load-bearing: the false martingale centering in Lemma 3.2 and the associated L^2 estimates in Lemmas 6.2 and 6.3 must be corrected before the proof can be accepted. I would be willing to review a revision. No concerns about citation practices or novelty disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what you should know: this is a serious attempt to settle the exact phase transition for Oja's algorithm. The constants γ_*, ρ_*, and the critical-window law are new; no prior work had them. The derivation comes from the recursion, not from fitting the simulations, and the Monte Carlo curves and QQ plots line up with the claimed formulas. The equivalence with spherical Oja is also a genuine observation. If the main theorems hold, then Oja from random initialization needs Θ(d log d) samples, with a non-negotiable log d, unlike offline PCA's Θ(d). That is a practically important and mathematically clean result.\n\nThe proof strategy is coherent: decompose the overlap recursion into a linear drift, a cubic term, and a martingale term; bound the noise floor; show the cubic term is negligible in the search phase; then track the escape via the logistic ODE. The error bounds in Lemmas 6.2 and 6.6 are plausible and the rates work out. I did not machine-verify the long calculation, but nothing in the structure smells wrong.\n\nThe soft spot is real. Lemma 3.2 defines M_k in (16) and claims it is a martingale difference. It is not. The last term subtracts (θ²ρ²+1), but E[B²||D||²/d | F] equals (θ²ρ²+1)(d−2)/d, so the conditional mean of M_k is δ²ρ(θ²ρ²+1)/d, not zero. That makes S_k in Lemma 6.2 centered incorrectly, and the L2 bound in that lemma omits the squared mean. Quantitatively the bias is O(ρ/d²) per step, and O(log d/d) after amplification, so it should not change γ_* or ρ_*, but the proof as written is not correct at a load-bearing point. This needs to be fixed — recenter M_k or absorb the term into R_k/d² — and checked carefully, especially through the amplification in Lemma 6.6. There is also no code for the experiments, which is a smaller but real reproducibility gap.\n\nWho this is for: anyone working on high-dimensional online PCA or SGD phase transitions. It deserves a serious referee, with the centering issue as the main required revision. I'd engage with it.","headline":"This paper has the right answer and likely the right proof strategy, but a centering error in Lemma 3.2 makes the proof as written technically false; the fix should be routine.","tokens_in":26559,"tokens_out":6625,"would_cite":true,"duration_ms":54775,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H25","60F05","60G42"],"pacs":[],"model":"deepseek-v4-flash","headline":"For Oja's streaming PCA, positive recovery of the top eigenvector from a random start requires n/(d log d) to exceed an explicit constant γ*, with an exact critical distribution; below it the overlap vanishes.","keywords":["online PCA","Oja's algorithm","phase transition","spiked covariance model","sample complexity","high-dimensional statistics","random initialization","stochastic gradient descent"],"falsifier":"Run Oja at d = 10^4 with θ = 2, δ = 1 (γ* ≈ 0.14, ρ* ≈ 0.76) over many independent random starts: if the median |overlap| leaves 0 substantially before n = γ* d log d, or if it saturates at a value measurably different from ρ* for n much larger than γ* d log d, the predicted threshold or plateau fails. Also test the δ > 2θ² prediction (e.g., θ = 1, δ = 2.5): if overlap recovers for very large n instead of tending to 0, Theorem 3.3 is wrong.","tokens_in":25518,"feed_emoji":"📈","tokens_out":8431,"duration_ms":74228,"temperature":0.7,"pith_summary":"This paper shows that Oja's algorithm—the standard one-pass method for streaming PCA—has a sharp phase transition governed by n/(d log d), not the usual n/d. For data drawn from a spiked covariance model with random initialization, the overlap between the estimator and the true top eigenvector tends to 0 whenever n/(d log d) is below a critical constant γ*, and tends to an explicit positive plateau ρ* above it. At the critical sample size n = γ* d log d + η d, the limiting overlap is random, described by a formula involving a single standard Gaussian variable. The result separates online from offline PCA: streaming requires a log d factor more samples to escape the noise floor, and it also quantifies how step size trades off search time against final accuracy.","feed_headline":"Oja's PCA only succeeds once n/(d log d) passes γ*","feed_subtitle":"Zero overlap below γ*, an exact plateau above; at criticality the overlap is random.","key_machinery":"The central object is the scalar overlap recursion for ρ_k = ⟨v̂_k, v0⟩, reduced in Lemma 3.2 to ρ_k = (1 + α/d)ρ_{k−1} − βρ_{k−1}³/d + M_k/d + R_k/d², with α = δ(θ² − δ/2) and β = δθ²(1 + δ/2). The proof then uses two simplifications: in the subcritical regime the martingale noise M_k is asymptotically equivalent to iid products δ A_k C_k, and once the overlap has risen above the O(d^{−1/2}) floor, the discrete recursion is approximated by the logistic ODE ρ′ = ρ(α − βρ²). The linear factor (1 + α/d)^{n−k} ≈ exp(α(n−k)/d), accumulated over n ≈ γ* d log d steps, carries the signal across the transition, while the cubic term parks the limit at ρ* = sqrt(α/β).","core_discovery":"Let X_k be iid N(0, Σ) with Σ = θ² v0 v0ᵀ + I, and run Oja's update ṽ_k = v̂_{k−1} + (δ/d)⟨X_k, v̂_{k−1}⟩X_k, v̂_k = ṽ_k/‖ṽ_k‖, starting from v̂_0 uniform on the sphere. The paper proves that as n,d → ∞ with n/(d log d) → γ ∈ (0,∞), the absolute overlap |⟨v̂_n, v0⟩| converges in probability to 0 if γ < γ*, and to ρ* if γ > γ*, where γ* = 1/(δ(2θ² − δ)) and ρ* = sqrt((θ² − δ/2)/(θ²(1 + δ/2))). At n = [γ* d log d + η d], the absolute overlap converges weakly to ρ* |G| exp(η/2γ*) / sqrt(ρ*⁴ + G² exp(η/γ*)) with G ∼ N(0,1). If δ > 2θ², the linear gain is negative and the overlap tends to 0 for every n,d. The paper also proves that the same threshold, plateau, and critical law hold for a spher","pith_inferences":["If the d log d law extends beyond Gaussian data, then any single-pass stochastic-gradient estimator initialized near uniform on the sphere should need a log d factor more samples than its offline counterpart; testing with sub-Gaussian or heavy-tailed distributions would reveal whether the constants shift with higher moments.","The random critical law suggests that the first escape from the noise floor is a random event; a testable prediction is that individual trajectories at n = n* are concentrated near 0 or near ρ*, while the averaged law follows the Gaussian formula.","The tradeoff between γ* and ρ* offers a practical rule for choosing δ: δ = θ² minimizes the sample threshold but gives a plateau that decreases with θ, while smaller δ buys accuracy only at the cost of more samples before the search phase ends.","The finite-d experiments in the paper already show the transition sharpening with d; a sharper falsifiable test would estimate γ* from the crossing of median overlap curves across several (θ, δ, d) and compare the fitted values with the formula γ*(θ, δ)."],"forward_implications":["Positive overlap from a random start is impossible when n is merely linear in d; the sample complexity of Oja from random initialization is Θ(d log d), with explicit prefactor γ*.","Above the threshold, more samples do not improve the estimator: the overlap saturates at ρ* < 1, and the only way to push ρ* closer to 1 is to shrink δ, which increases γ* and lengthens the search phase.","At δ* = θ², the threshold γ* equals 1/θ⁴, the same functional form as the classical offline PCA transition; the two transitions coincide positionally even though their time scales differ by log d.","At criticality the limiting overlap is random with a closed-form law, so the transition occupies a Θ(d) window in n and individual runs near the threshold are not reproducible in value.","The same γ*, ρ*, and critical distribution hold for the spherical-gradient variant of Oja, so the result is insensitive to the choice of normalization in the update."],"fun_headline_variants":["Online PCA phase shifts at n/(d log d), not n/d","Oja's algorithm: zero below γ*, plateau above, random at criticality","n/(d log d) sets Oja's PCA transition, not n/d","Streaming PCA threshold: n/(d log d), with random overlap at criticality","Online PCA: n/(d log d) decides success, not n/d"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof rests on the approximation that the true martingale noise in the overlap recursion can be replaced by iid Gaussian products and the discrete dynamics by a logistic ODE, with errors that stay negligible after being amplified by exp(α(n−k)/d) over roughly γ* d log d steps; if those neglected terms are not negligible, the exact constants γ* and ρ* would change.","fun_headline_variants_meta":{"raw":{"variants":["Online PCA phase shifts at n/(d log d), not n/d","Oja's algorithm: zero below γ*, plateau above, random at criticality","n/(d log d) sets Oja's PCA transition, not n/d","Streaming PCA threshold: n/(d log d), with random overlap at criticality","Online PCA: n/(d log d) decides success, not n/d"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00124,"raw_usage":{"total_tokens":5125,"prompt_tokens":1142,"completion_tokens":3983,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":886,"completion_tokens_details":{"reasoning_tokens":3879}},"tokens_in":886,"tokens_out":3983,"duration_ms":26903,"temperature":1.0,"reasoning_tokens":3879,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T23:37:02.316989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Oja at d = 10^4 with θ = 2, δ = 1 (γ* ≈ 0.14, ρ* ≈ 0.76) over many independent random starts: if the median |overlap| leaves 0 substantially before n = γ* d log d, or if it saturates at a value measurably different from ρ* for n much larger than γ* d log d, the predicted threshold or plateau fails. Also test the δ > 2θ² prediction (e.g., θ = 1, δ = 2.5): if overlap recovers for very large n instead of tending to 0, Theorem 3.3 is wrong.","supporting_citations":[],"review_version":1}