{"id":"75b6a277-bfc0-4c93-a435-06574861ee6b","arxiv_id":"2607.10936","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"The minimax regret of rank-r Bandit PCA is r√(dT) up to logarithmic factors.","lead":"This paper closes the gap between known upper and lower bounds for bandit-feedback online PCA, establishing that the minimax regret is roughly the square root of the product of dimension and horizon, times the rank, up to logarithmic factors. It contributes both a new layered-exploration algorithm and an adaptive adversary that forces any low-regret learner to solve a hidden subspace-estimation problem.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: proof architecture is coherent and the central minimax claim is supported.","rationale":"The reader's ACCEPT with moderate confidence is reasonable. The weakest assumption flagged by the reader—the eigenvalue-stability property Lemma 13—is indeed the most delicate part of the upper bound, and Lemma 28 is the corresponding delicate part of the lower bound. However, on close inspection I found no concrete step where the argument breaks: the induction in Lemma 13 is explicit about the perturbation terms and the constants are chosen to absorb them; Lemma 14's block-wise perturbation analysis is elaborate but internally consistent; and the lower-bound chain from Proposition 24 through Lemma 27 has consistent parameter scalings. I also checked the edge cases in Theorem 2: small r, large r, and very short/long horizons are handled by the MAB reduction with the appropriate logarithmic losses. The manuscript's own stated limitations are honest and do not invalidate the central claim. I therefore see no reason to change the verdict. My 'partial' agreement reflects that the reader's flagged assumptions are the right places to scrutinize, even though I do not find them to constitute a load-bearing objection.","tokens_in":54907,"tokens_out":24854,"duration_ms":254900,"concrete_test":"Independently re-derive Lemma 28's key inequality (Eq. 52 through Eq. 56), making every constant and dimension factor explicit, especially the Jensen step that drops the log-term and the event-E lower bound on the denominator. Confirm that the final bound is c_V β^2/(p max(1,ν)^2) with a universal c_V. A missed factor of d, p, or ν here would propagate through Lemma 27 and Theorem 29, changing the lower bound. Alternatively, formalize Lemmas 13–14 in a proof assistant; if the induction fails, the upper bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reading the full proof, I cannot isolate a concrete flaw that would invalidate the minimax characterization. The most delicate parts are the eigenvalue-stability induction for the upper bound (Lemmas 12–14) and the query-information bound for the lower bound (Lemma 28). I checked the logical dependencies: Lemma 13 supplies the eigenvalue interval [3/4 μ_α, 9/4 μ_α] that justifies Lemma 16, the block-diagonal structure in Lemma 11, and the stability-term bound Lemma 5; in turn, Lemma 13's induction uses Lemma 14 with constants that are internally consistent under the stated step-size assumption η ≲ 1/(r L^2 log^2(dLT/δ)). On the lower-bound side, Lemma 28's scaling c_V β^2/(p max(1,ν)^2) is consistent with the final parameter choices in Theorem 29, and the rescaling for unbounded exponential sampling is explicitly accounted for by the 1/log(eT) factor in Theorem 2. The self-reported limitations—deferred discussion of randomized a,b and the rescaling step—are presentation/constant-factor issues, not threats to the stated result. The main residual risk is absence of machine-checked proofs in the most technical lemmas, but this is verification risk rather than an identified error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies bandit-feedback online PCA (Bandit PCA) with rank-r PSD gain matrices of spectral norm at most one. It claims to close the gap between the prior upper bound O(d sqrt(rT log T)) and lower bound Omega(r sqrt(T/log T)) by establishing the minimax regret as r sqrt(dT) up to polylogarithmic factors. The upper bound is achieved by an online mirror descent algorithm on the spectrahedron with a negative log-determinant regularizer, combined with a layered exploration and epoch-based batching scheme that estimates the gain matrices in a hierarchical, variance-reduced manner. The lower bound is obtained by constructing an adaptive randomized adversary that forces the learner to solve a subspace discovery problem, which is then reduced to adaptive covariance estimation; a query-information bound gives the final Omega(r sqrt(dT/log d) / log(eT)) regret lower bound. The paper also discusses connections to adaptive-measurement quantum tomography and gives an O(d^2 T log d) implementation of the proposed algorithm.","tokens_in":55190,"tokens_out":16622,"duration_ms":169136,"significance":"If the results are correct, they resolve the minimax regret of Bandit PCA up to logarithmic factors, improving both the known upper and lower bounds in complementary rank regimes. The algorithmic innovations—layered sampling, epoch-based estimators, and lazy subspace updates—are substantial and likely to be influential. The lower-bound construction connecting Bandit PCA to adaptive subspace estimation and covariance estimation is elegant and of independent interest. The paper is particularly strong in providing detailed, self-contained proofs in the appendices: the eigenvalue-stability induction (Lemmas 13–14), the operator-norm concentration of epoch estimators (Lemma 12), the query-information bound (Lemma 28), and the reductions in Propositions 24 and Lemma 26 are all explicitly stated with parameter choices. The main residual risk is the high technical complexity of the proof, but I did not find a concrete logical flaw.","major_comments":[],"minor_comments":[{"comment":"The abstract says the learner selects a unit vector w_t in S^{d-1}, while the problem statement in Section 2 says w_t is selected in the unit ball B^d(0,1), and Algorithm 3 line 6 explicitly allows ||w_t|| <= 1. Since all gain matrices are PSD, this difference does not affect the results, but the protocol should be stated consistently. If the intended action set is the unit sphere, specify how the residual sampling on line 6 is implemented with unit vectors; if the unit ball is intended, revise the abstract.","section":"Abstract & Section 2"},{"comment":"The notation \\ell^2_t for the scalar reward is easily confused with an \\ell_2 norm. Consider using y_t or r_t, and reserve \\ell^2 for the squared norm. Also, the superscript placement in the text (sometimes \\ell^2_t, sometimes \\ell2_t) should be unified.","section":"Throughout"},{"comment":"The final parameter tuning leading to r sqrt(dT) log^3(dT) is compressed into the last paragraph of the proof. In particular, the case where the recommended step size violates the condition eta <= c0/(r log^4(dT/gamma)) is dismissed as vacuous; a short explicit derivation of why the resulting bound is vacuous would improve readability and confidence in the stated log^3 rate.","section":"Theorem 7"},{"comment":"The footnote stating that the randomization of a,b is 'for some technical reasons, whose discussion is omitted here due to space limitation' is no longer accurate: the randomization is used explicitly in the posterior-likelihood argument of Lemma 28 and the surrounding proof in Appendix C. Either remove the footnote or point the reader to the relevant appendix.","section":"Section 4.1, Algorithm 5"},{"comment":"Line 6 says to sample w_t with ||w_t|| <= 1 'arbitrarily' such that E[w_t w_t^T] = R_t/p_t,0. Since R_t/p_t,0 is a unit-trace PSD matrix when R_t is PSD, a concrete construction (e.g., sample from the eigen-decomposition, or the implementation given in Appendix B step 7(c)) should be referenced here to avoid ambiguity.","section":"Algorithm 3"},{"comment":"In the proof of the local Grassmannian volume ratio, the ambient dimension is denoted n while the statement uses d. This is minor but should be harmonized, and the scaling argument for the density of principal angles should be stated slightly more explicitly to show where the factor 4^r originates.","section":"Lemma 23"}],"recommendation":"minor_revision","confidential_remarks":"I concur with the reader's overall assessment. The paper is technically strong and the central minimax claim is well supported by the detailed appendix proofs. The issues I found are presentation-level and do not undermine the main theorems. The remaining risk is the sheer complexity of the eigenvalue-stability induction and the lower-bound query-information argument; these are the places where a subtle error would be most likely, but I found no concrete contradiction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Blanchard, Ostrovskii, and Saha close the gap for Bandit PCA: they improve both the known upper and lower bounds and bring the minimax regret to r sqrt(dT) up to polylogs. That's a genuine resolution of a problem open since Kotlowski and Neu 2019. The upper bound uses a new algorithm — OMD over density matrices with layered exploration and epoch-batched off-diagonal estimation. The lower bound is an adaptive adversary that reduces regret to subspace discovery and then to covariance estimation; the query-information lemma is the key step. Both contributions look real.\n\nThe paper is also honest. It flags the rescaling needed for unbounded exponential sampling and defers the discussion of randomized parameters a,b; these are presentation issues, not hidden flaws. The main theorems come with a full appendix, and I checked the dependency structure. Lemma 13 (eigenvalue stability) and Lemma 28 (query information) are the load-bearing walls. The constants line up, the induction is internally consistent, and the step-size assumption matches the claimed bound. I did not find a circular argument. The parameters are chosen analytically; there is no fitted noise. The computational complexity section is a bonus — O(d^2 T log d) total runtime.\n\nSoft spots, in proportion: the proofs are long and not machine-checked, so verification risk is real but not an identified error. The upper bound carries log^3(dT), the lower bound has a 1/log(eT) factor, and the paper says it doesn't know how to remove them. That's a limitation but not a flaw. The quantum tomography connection is suggestive rather than worked out. Minor: the lower-bound reduction requires technical conditions like p >= 32 log d; edge cases are handled by the MAB reduction, so this is fine.\n\nWho will get value: anyone working on matrix-valued bandits, spectral online learning, or adaptive measurement. It will be a useful citation and a good reading-group paper. The central result is important enough and the proof architecture solid enough to deserve serious refereeing. I would send it to peer review and expect acceptance after the usual rounds of checking the delicate lemmas. Not a desk reject.","headline":"Blanchard, Ostrovskii, and Saha genuinely close the minimax gap for Bandit PCA with a clever layered OMD algorithm and an adaptive lower bound; the proofs are long and delicate, but the architecture holds together and the work deserves serious refereeing.","tokens_in":55718,"tokens_out":1899,"would_cite":true,"duration_ms":22544,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that the minimax regret of bandit-feedback online PCA is Θ(r√(dT)) up to polylog factors—an algorithm achieves the rate and an adaptive adversary matches it.","keywords":["bandit PCA","minimax regret","online mirror descent","multiscale exploration","low-rank matrices","subspace estimation","adaptive adversary","quantum tomography"],"falsifier":"Simulate any algorithm against the paper's adaptive adversary with d=10³, r=1, T=10⁶; if average regret falls below 0.01√(dT/log d), Theorem 2 is refuted. Alternatively, instrument the layer eigenvalues during one epoch: leaving the interval [¾·2^{-α}, ⁹⁄₄·2^{-α}] falsifies the upper-bound's eigenvalue-stability lemma.","tokens_in":54762,"feed_emoji":"🎯","tokens_out":8413,"duration_ms":82819,"temperature":0.7,"pith_summary":"In the online learning game studied here, each round an adversary picks a hidden d×d rank-r matrix, the learner picks a unit direction, and the learner observes only the scalar quadratic form of the matrix along that direction. The paper's main claim is that the minimax regret of this game—the unavoidable gap between the learner's total reward and the best fixed direction in hindsight—is Θ(r√(dT)) up to logarithmic factors in d and T. The upper bound is achieved by a new algorithm that runs online mirror descent on the set of density matrices and explores eigenspaces in layers of matching time scales, batching gain estimates over epochs to control variance. The lower bound is produced by an adaptive adversary that hides a low-dimensional subspace and forces any low-regret learner to discover it, reducing the problem to a subspace-estimation task with a matching query lower bound. If the claim holds, it closes a gap in the existing bounds and shows the naive reduction to d²-dimensional linear bandits is loose whenever r≪d.","feed_headline":"Bandit PCA regret rate settled at r√(dT)","feed_subtitle":"A layered exploration algorithm matches an adaptive adversary, closing a √d gap and linking to quantum tomography.","key_machinery":"Key machinery: a layered multiscale exploration scheme. The iterate is a density matrix U_t whose eigenspaces are split into L ≈ log(dT) layers by eigenvalue scale μ_α = 2^{-α}. At each round a layer is sampled with probability proportional to μ_α times the cumulative subspace dimension, a uniform vector in that subspace is played, and gain estimates are batched over epochs of length 2^α per layer, keeping the spectral norm of the batched estimator logarithmic. The load-bearing lemma says the eigenvalues within each layer stay between ¾·2^{-α} and ⁹⁄₄·2^{-α} throughout the epoch; this guarantees the residual sampling matrices are PSD and bounds the stability terms. For the lower bound, an ad","core_discovery":"Central claim: in rank-r Bandit PCA the minimax regret is Θ(r√(dT)) up to polylog factors. The paper proves an upper bound Reg_T ≤ C r√(dT) log³(edT) for gains with operator norm ≤1 and nuclear norm ≤r, and a matching lower bound c min(r√(dT/log d), T)/log(eT) against an adaptive adversary. The upper bound comes from online mirror descent on the spectrahedron with a log-det regularizer plus a layered exploration scheme: eigenspaces are grouped by eigenvalue scale, and the off-diagonal gain estimates are batched over epochs of length 2^α per layer to control variance. The lower bound adversary exposes a hidden subspace gradually, forcing any low-regret learner to discover a constant fraction","pith_inferences":["The epoch-batching template suggests a general design rule for matrix-valued bandits: explore structured subspaces at rates matched to their eigenvalue scales, which may sharpen k-PCA and online covariance estimation as well.","The three log factors in the upper bound (divergence term, operator-norm concentration, layer count) appear independently improvable, so the true rate may be r√(dT) with a single log factor, closer to the lower bound.","An ablation that collapses all layers into one would presumably regress to the earlier d√(rT) regret, confirming that the layered schedule itself—not the mirror-descent step—carries the √d improvement."],"forward_implications":["For small rank r, regret drops from O(d√(rT log T)) to O(r√(dT) log³(dT)), a √d improvement; the naive d²-dimensional linear-bandit reduction is loose whenever r ≪ d.","The algorithm runs in O(d²T log d) time, so the optimal statistical rate is achievable at roughly the cost of eigendecompositions on the active layer block.","The upper bound holds under the convex relaxation ∥G_t∥_* ≤ r, applying to nuclear-norm-bounded gain sequences, not only exact rank-r ones.","The layered scheme connects bandit PCA to adaptive-measurement quantum tomography, where the same piecewise-flat spectral approximation appears in trace-norm-optimal state estimation."],"fun_headline_variants":["Minimax regret for Bandit PCA: r√(dT) up to logs","Bandit PCA: online mirror descent nails optimal regret","Bandit PCA regret matched to lower bound","Optimal regret achieved for Bandit PCA via layered exploration"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The upper-bound analysis rests on a lemma that the eigenvalues of the algorithm's iterate remain inside a constant factor of their layer scale throughout each epoch; if that stability fails, the residual matrices are not PSD and the whole OMD regret bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Minimax regret for Bandit PCA: r√(dT) up to logs","Bandit PCA: online mirror descent nails optimal regret","Bandit PCA regret matched to lower bound","Optimal regret achieved for Bandit PCA via layered exploration"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001182,"raw_usage":{"total_tokens":4770,"prompt_tokens":849,"completion_tokens":3921,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":3851}},"tokens_in":593,"tokens_out":3921,"duration_ms":25994,"temperature":1.0,"reasoning_tokens":3851,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T07:05:18.765342+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate any algorithm against the paper's adaptive adversary with d=10³, r=1, T=10⁶; if average regret falls below 0.01√(dT/log d), Theorem 2 is refuted. Alternatively, instrument the layer eigenvalues during one epoch: leaving the interval [¾·2^{-α}, ⁹⁄₄·2^{-α}] falsifies the upper-bound's eigenvalue-stability lemma.","supporting_citations":[],"review_version":2}