{"id":"c9477de0-b69c-4ebf-9b6c-ed4f48b6275e","arxiv_id":"2411.14021","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A block stochastic Riemannian subgradient algorithm solves the least unsquared deviation orientation-determination problem in cryo-EM with speedups of 5 to 30x and an O(epsilon^-4) convergence guarantee.","lead":"This paper proposes a block stochastic Riemannian subgradient method for determining molecular orientations in cryo-EM images, reporting accuracy comparable to existing common-line methods with roughly 20x speedup. A convergence guarantee of O(epsilon^-4) is given, and a norm-constrained variant is tested for low signal-to-noise ratios.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's O(ε^-4) proof uses a block oracle of size 1/ρ, while Algorithm 2 and the experiments use subsets D, S of size ρK; the subgradient bound B=1/ρ in Appendix A.1 does not hold for the algorithm actually tested.","rationale":"The paper's empirical contribution is real: Tables 1 and 2 show consistent speedups with comparable MSE, and the code is available; the synthetic and simulated real-data setups are clearly described. The central theoretical claim, however, is the O(ε^-4) certificate for Algorithm 2 and its special cases, and Appendix A is its only support. A close reading of A.1 shows the proof's stochastic oracle is not the algorithm defined in Section 3.3. The proof partitions the K rotations into ρK blocks of size 1/ρ and defines each g_i as a sum over the 1/ρ-1 other members of that block, bounding the subgradient norm by 1/ρ. Algorithm 2's BSGD instead sums over S=D, both of size ρK; the bound is then ρK (or K for SGD). So Proposition 1's key bound is false for the implemented algorithm. Because the proof's block size changes the per-iteration work, the stochasticity, and the descent inequality, the theorem does not presently certify the method whose 5-30x speedup is the headline. This is addressable by either normalizing the mini-batch or proving the descent lemma with the true subgradient bound and without the i.i.d. oracle property. The reader's conditional verdict remains appropriate; no stronger action is needed.","tokens_in":14787,"tokens_out":12849,"duration_ms":134104,"concrete_test":"Instrument the released code to record max_{i∈D} ||Σ_{j∈S} (R_i c_ij - R_j c_ji) c_ij^T / ||R_i c_ij - R_j c_ji|| ||_F during ReSync-BSGD with ρ=0.1, K=3000, and compare it to 1/ρ=10 and to ρK=300. If the observed values are of order ρK, recompute the descent inequality in Proposition 1 with the corrected subgradient bound and with the unnormalized mini-batch sum; if the inequality no longer holds, Theorem 1 must be restated for a normalized mini-batch or for blocks of size 1/ρ.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is that the stochastic oracle analyzed in Appendix A.1 is not the algorithm defined in Section 3.3. Algorithm 2 fixes |D|=ρ1K and |S|=ρ2K; for ReSync-BSGD, |D|=|S|=ρK and the update for i∈D uses g_i(X_i)=Σ_{j∈S} ∂f_{i,j}(X_i). Appendix A.1 instead constructs random blocks with 'm=ρK blocks, each block having a size of 1/ρ' and defines g_i by summing f_{i,j} over the block containing i, asserting ||∇g_i||≤B=1/ρ. Under the standard normalization of unit common-line vectors, the algorithm's actual subgradient satisfies ||∇g_i||≤Σ_{j∈S} ||c_ij|| ≈ ρK, not 1/ρ. For ρ=0.1 and K=3000 this is 300 rather than 10. Proposition 1 and the constants in (23) are derived with B=1/ρ, so the descent inequality is not established for the BSGD/BCD/SGD variants as written, and Theorem 1's O(ε^-4) conclusion does not formally apply to the method benchmarked in Tables 1-4. The random-reshuffling versus i.i.d. discrepancy noted by the reader is a second, independent gap; fixing that alone would not repair the block-size mismatch.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the cryo-EM orientation determination problem using the least unsquared deviation (LUD) formulation. It proposes a Riemannian subgradient method and three stochastic variants (ReSync-SGD, ReSync-BCD, ReSync-BSGD) that update only a subset of rotations and/or use a subset of common lines. For these methods the paper claims an O(ε^-4) iteration complexity to reach an ε-nearly stationary point measured via the Moreau envelope. The same framework is extended to a low-SNR setting by adding a spectral norm constraint, yielding a ReSync-norm algorithm. Numerical experiments on synthetic and simulated real projection data report accuracy comparable to existing methods with a 5- to 30-fold speedup for ReSync-BSGD.","tokens_in":15098,"tokens_out":5465,"duration_ms":51971,"significance":"If the convergence result held for the implemented algorithms, this would be a useful contribution: a first iteration-complexity bound for block stochastic Riemannian subgradient methods in this application, plus a reproducible practical speedup. The paper's strengths are its open-source code, its experiments across detection rates and SNRs down to 1/128, its explicit comparison with SDR-ADMM, and a self-contained proof strategy using the Moreau-envelope stationarity measure. However, the central theoretical claim is currently proven for an oracle that does not match Algorithm 2, so the formal guarantee does not cover the method that is benchmarked. The empirical claims may be valid, but the theoretical gap is load-bearing and needs to be closed in revision.","major_comments":[{"comment":"The convergence analysis is carried out for an oracle that differs structurally from the implemented algorithm. Appendix A.1 defines m = ρK blocks, each of size 1/ρ, and the approximate subgradient g_i(X_i, ζ) sums f_{i,j} over the block containing i, yielding the bound ||∇g_i|| ≤ B = 1/ρ used in Proposition 1 and in the constant c_2 in (23). Algorithm 2, by contrast, updates a subset D of size ρ_1 K using a data subset S of size ρ_2 K; for ReSync-BSGD, |D| = |S| = ρK and the update for i ∈ D sums over j ∈ S, so with unit-norm common-line vectors the subgradient norm is at most ρK (e.g., 300 when K = 3000 and ρ = 0.1), not 1/ρ = 10. Consequently, Proposition 1's descent inequality and the resulting O(ε^-4) bound in Theorem 1 are not established for the algorithm actually tested in Tables 1-4.","section":"Appendix A.1 and Proposition 1 vs. Section 3.3 and Algorithm 2"},{"comment":"The proof assumes an oracle that generates independent and identically distributed partitions ζ_t ~ U(Ω), but Algorithm 2 and the surrounding text in Section 3.3 describe random reshuffling of {1, ..., K} before each iteration. Random reshuffling induces dependence between successive partitions, so the telescoping sum over ζ_0, ..., ζ_{T-1} in the proof of Theorem 1 is not justified for the algorithm as written. This is a second, independent gap: even after correcting the block-size mismatch, the proof would need a random-reshuffling analysis or the algorithm would need to be changed to sample partitions i.i.d.","section":"Appendix A.1, property (a), and Algorithm 2"},{"comment":"The proof of Theorem 1 relies on the τ-weak convexity inequality stated as Theorem 2, but the paper never verifies that the LUD objective (3) satisfies the required τ-weak convexity condition on Stiefel(3K, 3) with an explicit constant τ. The sentence 'We can verify that the point P_λ f(X) satisfies...' concerns first-order optimality, not weak convexity. Since the entire descent argument depends on this assumption, the authors should either prove the needed weak-convexity property for f or cite a theorem that applies directly to this objective.","section":"Section 4 and Theorem 2"},{"comment":"The surrogate constraint is stated inconsistently and without justification. Since eR ∈ R^{2K×2}, the matrix eR^T eR is 2×2, so writing 'eR^T eR = αK I_3' in problem (11) is dimensionally incoherent. The text also alternates between the spectral norm constraint ||G||_2 ≤ αK on G = eR eR^T and the surrogate eR^T eR = αK I_3; the equivalence between these constraints is asserted but never proved. Because ReSync-norm is presented as a contribution for low-SNR scenarios, this formulation needs to be corrected and justified.","section":"Section 3.4 and problem (11)"}],"minor_comments":[{"comment":"The displayed update in line 7 contains a garbled symbol 'µk e∇f (Rt_i)'; it should be µ_t \\tilde∇ f(R_i^t).","section":"Algorithm 1, line 7"},{"comment":"The phrase 'an averaging 20-fold speedup' should read 'an average 20-fold speedup'.","section":"Abstract and Section 5.1"},{"comment":"The method called LUD-IRLS in Tables 1 and 2 is called LUD-IRLS-PGD in Table 3; please use a consistent name.","section":"Tables 1-3"},{"comment":"For K = 5000 and SNR = 1/32, the Eig row reports MSE 4.19E+00, which is markedly different from the neighboring Eig rows (3.08E-02 at SNR=1/16 and 4.86E+00 at SNR=1/64); please verify this entry and comment on its cause.","section":"Table 2"},{"comment":"The text says 'The third equation uses Lemma 1...', but the displayed chain contains inequalities, not numbered equations; this should be reworded as 'third inequality'.","section":"Appendix A.1, after the long inequality"},{"comment":"The constraint '1 ≤ i ≤ K' under the surrogate eR^T eR = αK I_3 is unclear because eR^T eR is a global quantity, not per-image; the notation should be clarified.","section":"Problem (11)"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the mismatch between the convergence proof and the implemented algorithm; I believe this is fixable within the scope of a revision, either by aligning the algorithm with the analyzed oracle or by extending the analysis to the actual random-reshuffling block-sampling scheme. The empirical results are promising, but the formal claim is currently overstated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper is worth a serious look for the experiments and the ReSync-BSGD combination, but the main theoretical guarantee does not cover what was actually run. The stress-test point is correct. Appendix A.1 constructs blocks of size 1/ρ (so m=ρK blocks) and bounds each block subgradient by B=1/ρ. Algorithm 2 samples D and S of size ρK, so for ReSync-BSGD the update sums ρK terms and the subgradient norm is bounded by ρK, not 1/ρ. Those differ by a factor of K roughly; for ρ=0.1 and K=3000, it is 300 vs 10. Proposition 1 and Theorem 1 use B=1/ρ, so the O(ε^-4) iteration complexity is not established for the method in Tables 1–4. The random reshuffling versus i.i.d. issue is a second, independent gap; fixing it alone would not repair the block-size mismatch.\n\nWhat is actually good: the paper ships a clean algorithmic synthesis—ReSync from Liu et al. 2023 extended to the LUD cryo-EM orientation problem with a block stochastic Riemannian subgradient update. The empirical study is honest in its setup: all methods warm-started equally, stopping criteria reported, and code is available. The 5–30x speedups over PGD/IRLS on synthetic data are plausible and worth checking. The ReSync-norm variant for low SNR is a reasonable practical heuristic, and the clustering plots are informative.\n\nSoft spots beyond the proof gap: 'real data' is actually simulated projections from a density map, which the text does say but should be more explicit. ReSync-norm has no convergence analysis; that is fine if labeled as heuristic, but the paper should say so. The hyperparameter α for the spectral norm is set from prior knowledge, not tuned per experiment, which is acceptable.\n\nBottom line: the empirical contribution is real enough that the paper deserves a serious referee, but only after the theory is either corrected to analyze the actual sampling scheme or explicitly scoped down to the block-of-size-1/ρ oracle. As written, I would not rely on Theorem 1 for the algorithm in the experiments.","headline":"A genuinely useful empirical paper with a real algorithmic synthesis, but the main convergence theorem analyzes a different algorithm than the one benchmarked.","tokens_in":15630,"tokens_out":1871,"would_cite":false,"duration_ms":18035,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","65K05","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A block stochastic Riemannian subgradient method solves the LUD cryo-EM orientation problem with accuracy matching state-of-the-art solvers while running roughly 20 times faster on average.","keywords":["cryo-EM","orientation determination","common-line method","least unsquared deviation (LUD)","Riemannian subgradient method","block stochastic optimization","Stiefel manifold","low signal-to-noise ratio"],"falsifier":"Re-run ReSync-BSGD on one fixed synthetic dataset twice — once with random reshuffling of blocks per pass, once with independent uniform block partitions — and compare the stationarity measure $\\Theta(X_t)$ against the claimed bound $\\mathbb{E}[\\Theta^2(X_t)] \\leq c_1(f_\\lambda(X_0) - \\min f_\\lambda) + c_2/\\sqrt{T+1}$; if the reshuffled run stops tracking the bound as $T$ grows, the $O(\\varepsilon^{-4})$ result covers an oracle the algorithm does not use. A second check is in the paper's own Table 1: at detection rate $p = 0.05$ every method lands at MSE $\\approx 0.3$–$0.45$, so the 'comparable accuracy' claim should be re-tested in exactly that low-$p$ regime before it is generalized.","tokens_in":14553,"feed_emoji":"🔬","tokens_out":8362,"duration_ms":66638,"temperature":0.7,"pith_summary":"The paper sets out to show that the least unsquared deviation (LUD) formulation of cryo-EM orientation determination — a nonconvex, nonsmooth synchronization problem over rotations — can be solved directly by a Riemannian subgradient method, without semidefinite relaxation. The block stochastic variant updates only a small random subset of rotations using a small random subset of common-line measurements, and the paper claims this preserves accuracy while giving an average 20-fold speedup over state-of-the-art methods. It would matter because real cryo-EM datasets contain hundreds of thousands to millions of images, and existing solvers are too slow at that scale. The paper also claims all proposed variants reach an $\\varepsilon$-approximate stationary point in $O(\\varepsilon^{-4})$ iterations, and that a spectral-norm-constrained version keeps accuracy at low signal-to-noise ratios where unconstrained methods fail.","feed_headline":"Cryo-EM orientation solved 20x faster at same accuracy","feed_subtitle":"A block stochastic Riemannian subgradient method matches state-of-the-art orientation accuracy at a fraction of the runtime.","key_machinery":"The load-bearing object is the block stochastic Riemannian subgradient oracle on the Stiefel manifold $\\mathrm{St}(3K, 3)$ treated as a product of $K$ copies of $SO(3)$, where each oracle call draws random subsets $D$ and $S$ of rotations and common lines and returns a partial Euclidean subgradient of the form $\\sum_{j \\in S} (R_i c_{ij} - R_j c_{ji}) c_{ij}^\\top / \\|R_i c_{ij} - R_j c_{ji}\\|_2$. Two tools do the theoretical work: the weak convexity inequality for functions on the Stiefel manifold, imported from Li et al. [2021], which converts one subgradient step into guaranteed descent of the Moreau envelope, and the Moreau-envelope stationarity measure $\\Theta(X) = \\lambda^{-1} \\|P_\\lambda f(X) - X\\|_F$, whose smallness is what the $O(\\varepsilon^{-4})$ bound controls. The QR-based retraction keeps every update feasible, and it is also where the alternating projection for the spectral norm constraint plugs in.","core_discovery":"The central claim is that minimizing $f(R) = \\sum_{i,j} \\|R_i c_{ij} - R_j c_{ji}\\|_2$ over $R_1, \\dots, R_K \\in SO(3)$ — the LUD common-line objective — can be done by repeated Riemannian subgradient steps: compute a Euclidean subgradient, project it onto the tangent space at $R_i$ via $P_{T_{R_i}}(B) = R_i(R_i^\\top B - B^\\top R_i)/2$, and map back onto the manifold with a QR-based retraction. The paper claims that sampling small blocks of rotations and small blocks of common lines each iteration (ReSync-BSGD, with filter ratio $\\rho$) does not sacrifice the $O(\\varepsilon^{-4})$ iteration complexity of the full method, and that in experiments it matches the MSE of semidefinite relaxation and IRLS/PGD solvers while running 5 to 30 times faster. The same machinery, with an added spectral norm constraint enforced by alternating projection, is claimed to prevent viewing directions from clustering at SNR as low as 1/64, and with class-averaging preprocessing even 1/128 becomes tractable.","pith_inferences":["The independence gap is worth probing: the proof assumes i.i.d. uniform block partitions, while the tested algorithm reshuffles once per pass; the empirical speedup may survive, but proving the $O(\\varepsilon^{-4})$ rate for the reshuffled variant is an open task that the paper does not address.","The block structure suggests embarrassingly parallel GPU-scale implementation; the reported 20-fold speedup on a 16-core CPU is likely a lower bound on what the method could achieve on larger parallel hardware.","The accuracy comparisons concentrate on regimes where the solver matters ($p \\geq 0.1$, SNR $\\geq 1/64$); at the hardest settings the tables show all methods failing together, so the practical win at extreme noise appears to come from the denoising preprocessing rather than from the optimization method itself."],"forward_implications":["The LUD formulation, previously solved by expensive semidefinite relaxation, becomes solvable by a direct first-order method, so robustness to misdetected common lines is no longer purchased at the price of scalability.","All four variants — full ReSync, ReSync-SGD, ReSync-BCD, and ReSync-BSGD — inherit the $O(\\varepsilon^{-4})$ complexity bound, since the first three are special cases of the block stochastic method.","Because BSGD updates independent blocks in each iteration, the method parallelizes across the $K$ images, which the paper cites as a reason it should scale to the large datasets of real cryo-EM pipelines.","The spectral-norm-constrained variant (ReSync-norm) keeps orientation accuracy at SNR 1/64 where unconstrained benchmarks diverge, and combined with class averaging it produces usable results at SNR 1/128, a regime the paper says has not previously been documented."],"supporting_citations":[{"why":"Supplies the ReSync Riemannian subgradient framework and the linear-convergence result for robust rotation synchronization that this paper adapts to cryo-EM orientation determination.","marker":"Liu et al. [2023]"},{"why":"Defines the LUD formulation and the spectral norm constraint for low-SNR clustering, and provides the SDR-ADMM baseline.","marker":"Wang et al. [2013]"},{"why":"Provides the weak convexity inequality and the Moreau-envelope stationarity measure on the Stiefel manifold that the convergence proof in Appendix A is built on.","marker":"Li et al. [2021]"},{"why":"Sets the $O(\\varepsilon^{-4})$ complexity benchmark for stochastic model-based minimization of weakly convex functions that the paper matches.","marker":"Davis and Drusvyatskiy [2019]"},{"why":"Supplies the eigenvector relaxation used for initialization in Section 3.1.","marker":"Singer and Shkolnisky [2011]"},{"why":"Provides the LUD-PGD and IRLS baselines that the proposed method is compared against in the efficiency benchmarks.","marker":"Pan et al. [2023]"},{"why":"Motivates the random reshuffling trick used in the stochastic variants, and supplies the dependence structure that the convergence proof's oracle assumption does not cover.","marker":"Safran and Shamir [2020]"}],"fun_headline_variants":["Cryo-EM orientation 20x faster via Riemannian subgradient","Stochastic Riemannian method speeds cryo-EM 20x","Riemannian subgradient solves cryo-EM at low SNR","Cryo-EM orientation 20x faster, accurate at low SNR","Block stochastic subgradient gives 20x cryo-EM speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $O(\\varepsilon^{-4})$ guarantee holds only if each iteration draws its random partition of the rotations independently, but the implemented algorithm reshuffles the block order within each pass, so the proven bound does not formally cover the variant that was benchmarked.","fun_headline_variants_meta":{"raw":{"variants":["Cryo-EM orientation 20x faster via Riemannian subgradient","Stochastic Riemannian method speeds cryo-EM 20x","Riemannian subgradient solves cryo-EM at low SNR","Cryo-EM orientation 20x faster, accurate at low SNR","Block stochastic subgradient gives 20x cryo-EM speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000776,"raw_usage":{"total_tokens":3426,"prompt_tokens":931,"completion_tokens":2495,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":2396}},"tokens_in":547,"tokens_out":2495,"duration_ms":16965,"temperature":1.0,"reasoning_tokens":2396,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:36:36.707650+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run ReSync-BSGD on one fixed synthetic dataset twice — once with random reshuffling of blocks per pass, once with independent uniform block partitions — and compare the stationarity measure $\\Theta(X_t)$ against the claimed bound $\\mathbb{E}[\\Theta^2(X_t)] \\leq c_1(f_\\lambda(X_0) - \\min f_\\lambda) + c_2/\\sqrt{T+1}$; if the reshuffled run stops tracking the bound as $T$ grows, the $O(\\varepsilon^{-4})$ result covers an oracle the algorithm does not use. A second check is in the paper's own Table 1: at detection rate $p = 0.05$ every method lands at MSE $\\approx 0.3$–$0.45$, so the 'comparable accuracy' claim should be re-tested in exactly that low-$p$ regime before it is generalized.","supporting_citations":[{"cited_title":"ReSync: Riemannian Subgradient-based Robust Rotation Synchronization","cited_arxiv_id":"2305.15136","evidence_quote":"Supplies the ReSync Riemannian subgradient framework and the linear-convergence result for robust rotation synchronization that this paper adapts to cryo-EM orientation determination."},{"cited_title":"Orientation determination of cryo-em images using least unsquared deviations","cited_arxiv_id":null,"evidence_quote":"Defines the LUD formulation and the spectral norm constraint for low-SNR clustering, and provides the SDR-ADMM baseline."},{"cited_title":"Three-dimensional structure determination from common lines in cryo-em by eigenvectors and semidefinite programming","cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvector relaxation used for initialization in Section 3.1."},{"cited_title":"Orientation estimation of cryo-em images using projected gradient descent method","cited_arxiv_id":null,"evidence_quote":"Provides the LUD-PGD and IRLS baselines that the proposed method is compared against in the efficiency benchmarks."},{"cited_title":"How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250--3284","cited_arxiv_id":null,"evidence_quote":"Motivates the random reshuffling trick used in the stochastic variants, and supplies the dependence structure that the convergence proof's oracle assumption does not cover."}],"review_version":1}