{"id":"a21976c0-811d-44c1-8d9d-dad833d7cbd7","arxiv_id":"2504.15671","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Minimizing a proven lower bound on the Riemannian distance yields a certified, logarithm-free approximation of the Riemannian barycenter, demonstrated on the Stiefel manifold.","lead":"This paper computes Riemannian barycenters, averages of points on curved spaces, by minimizing a cheaper lower-bound surrogate built from distance inequalities, with a proved error certificate. On the Stiefel manifold the surrogate matches the exact barycenter closely while running more than 100 times faster.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's certificate requires an exact global minimizer of bfν; the reported Y* is only an approximate RGD point, so Table 1's bound may not be a valid certificate.","rationale":"The reader's weakest_assumption concerns the imported bracketing inequalities from [12]. Those bounds are unquestionably load-bearing for the Stiefel experiments, and I would also want them independently checked. However, I judge the most acute internal gap to be the mismatch between Theorem 1's exact-minimizer hypothesis and the approximate surrogate minimization actually performed in Section 5. The reader explicitly noted this mismatch in the rationale ('Theorem 1 assumes an exact global minimizer... while the reported results come from an approximate gradient descent'), but did not list it as the weakest assumption. My proposed test directly checks whether the computed Y* could be a global minimizer of bfν; without that, the numerical certificate in Table 1 is not supported. The theorem itself is elementary and, conditional on the bracketing bounds and exact minimization, correct. Thus the appropriate verdict remains CONDITIONAL rather than ACCEPT or REJECT: the mathematical framework is sound, but the experimental evidence needs either an exact/verified surrogate optimization or a clear statement that the reported bound is heuristic. I keep the reader's verdict unchanged because the reader already conditioned the paper on exactly these reproducibility and approximation issues.","tokens_in":7577,"tokens_out":6613,"duration_ms":63759,"concrete_test":"Instrument the public Julia code to record bfν(Y*) at convergence of (A2) and compare it with bfν evaluated at X* (the (A1) output), at the Euclidean projection of the data mean, and at the best of 50 independent random restarts of (A2). If any of these points has bfν strictly lower than bfν(Y*) beyond the stopping tolerance, then Y* does not satisfy the hypothesis of Theorem 1; Table 1's certificate row must be recomputed with the best-found surrogate point or removed. This directly settles whether the reported bound is a valid certificate for the computed Y*.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 is formally correct, but its hypothesis is that bx* is an exact global minimizer of bfν. In Section 5, algorithm (A2) is Riemannian gradient descent on bfν stopped when |bfν(Y_k)^ν − bfν(Y_{k−1})^ν| ≤ ε bfν(Y_0)^ν. Such a stopping rule guarantees neither global optimality nor even the inequality bfν(Y*) ≤ bfν(x*). The first inequality in chain (6) — and hence the bound (7) — requires exactly that inequality. Table 1 reports [bFν(Y*) − bfν(Y*)] / bfν(Y*) as a bound on the relative error of the returned Y*, but unless Y* is a true global minimizer of bfν, that quantity is not a proven upper bound on [fν(Y*) − fν(x*)] / fν(x*). The concluding statement that (A2) 'benefits from theoretical guarantees (Theorem 1)' therefore overstates what the experiment supports. This does not invalidate the theorem, but it is the critical gap between the theoretical certificate and the central numerical claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript introduces a framework for approximating the Riemannian lν-barycenter by minimizing a surrogate objective built from certified lower and upper bounds on the Riemannian distance. For an exact global minimizer bx* of the lower-bound surrogate bfν, Theorem 1 provides a computable relative-error certificate for fν, and Theorem 2 provides a computable distance upper bound; Theorem 3 gives a lower bound that depends on the unknown optimal value. The method is instantiated on the Stiefel manifold using distance bounds from the authors' prior work [12], and Section 5 compares three algorithms: Riemannian gradient descent on the exact objective, RGD on the lower-bound surrogate, and a lifting-map fixed-point iteration. The experiments report accurate approximations, satisfaction of the bounds, and a speedup exceeding 100× for surrogate-based methods. The central theoretical result is elementary and correct, but the numerical section does not instantiate the exact-global-minimizer hypothesis of Theorem 1.","tokens_in":7747,"tokens_out":8559,"duration_ms":85027,"significance":"If the claimed certificate could be attached to the actual algorithm, the paper would contribute a useful and inexpensive error-controlled alternative to exact Riemannian barycenter computation on manifolds with costly logarithms. Strengths include the generic bracketing-function formulation, the simple and correct proofs of Theorems 1–3, the concrete Stiefel bounds inherited from [12], and the public code. The main limitation is that the implemented Algorithm (A2) does not satisfy the hypothesis of Theorem 1, so the strongest advertised guarantee is not currently supported; this limits the significance until the gap is closed or the claim is appropriately qualified.","major_comments":[{"comment":"Theorem 1 assumes bx* ∈ argmin_{x∈M} bfν(x). The algorithm (A2) minimizes bfν^ν by Riemannian gradient descent and stops when |bfν(Y_k)^ν − bfν(Y_{k−1})^ν| ≤ ε bfν(Y_0)^ν. This stopping rule is a stationarity/fixed-point criterion; it does not imply bfν(Y*) ≤ bfν(x*) and does not imply global optimality. Consequently the first inequality in chain (6), which is needed for the certificate, is not established for the reported Y*. The quantities in Table 1 of the form [bFν(Y*) − bfν(Y*)] / bfν(Y*) are therefore not proven upper bounds on the true relative error [fν(Y*) − fν(x*)] / fν(x*). The concluding sentence that (A2) “benefits from theoretical guarantees (Theorem 1)” should be qualified; the authors should either establish a global optimality property for bfν on St(n,p), add a stationarity-gap correction to the bound, or present the table as a heuristic validation.","section":"Section 5, Eq. (7), Table 1"},{"comment":"The left-hand side [fν(X*) − fν(Y*)] / fν(X*) in Table 1 uses X* produced by A1 as a proxy for the true barycenter x*. A1 is itself only run to a stationarity criterion and its Riemannian logarithm is numerically approximated. Thus the tabulated relative error is an empirical comparison against an approximate reference, not a measured distance to x*. Please state this limitation explicitly and, if possible, report the A1 tolerance and confirm that the conclusions are insensitive to it.","section":"Section 5, Table 1"}],"minor_comments":[{"comment":"Averages over 10 runs are reported without standard deviations or confidence intervals; given that the speed and accuracy claims are central, the variability should be quantified.","section":"Table 1"},{"comment":"The stopping criterion notation should be written with an explicit iteration index, for example |fν(X_k^*)^ν − fν(X_{k−1}^*)^ν| ≤ ε fν(X_0)^ν, to remove the ambiguity in the current “X∗−1” notation.","section":"Section 5"},{"comment":"The formulas for bmβ and cMβ are used with β = 1/2 in the experiments, but the β-metric itself is not defined in this paper; please define it or give a precise pointer to [12, Eq. (2.1)].","section":"Section 3"},{"comment":"The sampling procedures for “spread” and “clustered” datasets are described informally; specify the exact distributions and the injectivity-radius procedure used so the experiments can be reproduced from the text alone.","section":"Section 5"},{"comment":"The running-time comparison reports a speedup larger than 100× but gives no measurement details; please state the hardware, software versions, and use median timings with error bars rather than a single benchmark curve.","section":"Figure 3, bottom"}],"recommendation":"major_revision","confidential_remarks":"The main gap is between Theorem 1 and the numerical experiments; it can be addressed by either providing a convergence or global-optimality guarantee for the surrogate on the Stiefel manifold or by reducing the claim to a numerical heuristic. The dependence on the authors' prior work [12] for the bracketing inequalities is acceptable, and I see no reason to question the novelty disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Simon,\n\nThe theorem is fine; the paper's central numerical claim isn't connected to it. That's the short version.\n\nWhat's new: the paper proposes bounding the Riemannian distance from below and above, then minimizing the lower-bound surrogate, with Theorem 1 giving a computable relative-error certificate. The chain (6) is correct under the stated hypothesis that bx* exactly minimizes bfν. Theorems 2 and 3 are also correct and elementary. As a contribution to manifold statistics, this is a sensible and useful idea, and the Stiefel experiments show that the surrogate (A2) can be over two orders of magnitude faster than exact Riemannian gradient descent (A1). That's worth something.\n\nThe soft spot is the assumption gap. The algorithm actually run for (A2) stops when the relative change in bfν is below 1e-6. That is a stationarity heuristic, not a global optimality certificate. The first inequality in the chain, bfν(Y*) ≤ bfν(x*), only holds if Y* is a true global minimizer of bfν. Without that, the quantity reported in Table 1 as an upper bound on the relative error is not proven to be an upper bound. The paper's conclusion that (A2) 'benefits from theoretical guarantees (Theorem 1)' overstates what the experiment supports. This is the one load-bearing flaw in the numerical narrative, and the paper doesn't acknowledge it.\n\nThe other complaints are minor: no error bars or seeds on the 10 runs, no commit hash for the repository. Those are standard hygiene and easy to fix. The distance bounds from [12] are cited, not re-derived; that's fine, though a reader would want to check [12] for the Stiefel-specific inequalities.\n\nWho is this for? People who compute barycenters on Stiefel or similar manifolds and want a certified surrogate. The idea is good enough that I'd send it out, but the revision has to either prove the surrogate has no spurious local minima (unlikely for a general manifold), switch to a global optimization method that can certify the minimum, or soften the claims to say the bound is heuristic on the returned point. As is, the certificate is real but the algorithm does not earn it.\n\nRecommendation: accept for review with a clear demand to fix the minimizer gap and tighten the numerics. The core math is sound; the packaging needs work.\n\n— [Your name]","headline":"A clean certificate theorem undercut by an unstated gap between the exact-minimizer hypothesis and the approximate-minimizer algorithm.","tokens_in":8340,"tokens_out":3971,"would_cite":true,"duration_ms":35291,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["53-08","53C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"Minimizing a guaranteed lower bound of the Riemannian barycenter objective yields an approximate mean with a computable error certificate and, on the Stiefel manifold, a speedup of over 100 times.","keywords":["Riemannian barycenter","Karcher mean","Fréchet mean","Stiefel manifold","distance bounds","error certificate","Riemannian logarithm","approximate optimization"],"falsifier":"Compute the true geodesic distance for a pair of points on St$(n,p)$ with $n\\ge 2p$ using a reliable numerical Riemannian logarithm and compare it with $\\underline{m}_\\beta$ and $\\overline{M}_\\beta$; a single pair where the lower bound exceeds the true distance or the upper bound falls below it would invalidate the certificate at the root of Theorem 1.","tokens_in":7313,"feed_emoji":"📐","tokens_out":9004,"duration_ms":76757,"temperature":0.7,"pith_summary":"Riemannian barycenters—manifold analogues of the mean—are usually found by gradient descent, which requires a Riemannian logarithm at every step and is intractable on manifolds such as the Stiefel manifold. This paper replaces the exact objective with a guaranteed lower-bound surrogate, minimizes the surrogate, and proves a computable upper bound on the relative error of the result. Experiments on the Stiefel manifold show the surrogate minimizer matches exact Riemannian gradient descent in accuracy while running more than a hundred times faster. The paper's numerical finding is that the certificate, though guaranteed, is much tighter for clustered datasets than for spread ones.","feed_headline":"Approximate Riemannian means get a computable error certificate","feed_subtitle":"On Stiefel manifolds the surrogate runs 100x faster and the error bound is rigorous.","key_machinery":"The machinery is a sandwich: two functions $\\underline{m}_g$ and $\\overline{M}_g$ that bracket the Riemannian distance, $\\underline{m}_g \\le d_g \\le \\overline{M}_g$. Lifting these to the objective gives $\\hat{f}_\\nu \\le f_\\nu \\le \\hat{F}_\\nu$. The key identity is the chain of inequalities in (6)—the surrogate minimizer beats the true minimizer on the surrogate, and the true minimizer beats the surrogate minimizer on the true objective—which yields Theorem 1's computable certificate. On the Stiefel manifold the explicit brackets $\\underline{m}_\\beta \\le d_\\beta \\le \\overline{M}_\\beta$ from [12, Thm. 7.1] are used; because they involve only Euclidean distances, the surrogate can be optimized without computing a single Riemannian logarithm.","core_discovery":"The central claim is Theorem 1: with under- and over-approximations of the Riemannian distance, letting $\\hat{x}_*$ minimize the lower-bound surrogate $\\hat{f}_\\nu$ gives $$\\frac{f_\\nu(\\hat{x}_*)-f_\\nu(x_*)}{f_\\nu(x_*)} \\le \\frac{\\hat{F}_\\nu(\\hat{x}_*)-\\hat{f}_\\nu(\\hat{x}_*)}{\\hat{f}_\\nu(\\hat{x}_*)}.$$ The right-hand side contains only computable quantities, so the surrogate solution carries a rigorous, computable certificate of how far it is from the true barycenter. The paper further shows numerically that on the Stiefel manifold with the $\\beta$-metric this surrogate minimization reaches essentially the same objective value as Riemannian gradient descent on the exact problem, that all computed certificates satisfy the inequality, and that the speedup exceeds a factor of 100 as the dimension grows.","pith_inferences":["Beyond the paper, the certificate could be used as an online stopping rule for surrogate optimization: iterate until the computable bracket gap $\\hat{F}_\\nu(\\hat{x})-\\hat{f}_\\nu(\\hat{x})$ falls below a desired tolerance.","Beyond the paper, any manifold equipped with provable global distance brackets—for example spheres, flag manifolds, or fixed-rank matrices—inherits the same approximate-barycenter scheme and certificate without new algorithmic machinery.","Beyond the paper, one could compare the two surrogate choices directly: minimizing the upper bound $\\hat{F}_\\nu$ rather than $\\hat{f}_\\nu$ minimizes the Theorem 2 distance bound, and may produce smaller geodesic error even though its relative objective certificate is weaker."],"forward_implications":["On any manifold with proven distance brackets, a user can minimize the lower-bound surrogate and obtain a rigorous, computable upper bound on the relative error of the resulting approximate barycenter without computing a Riemannian logarithm.","On the Stiefel manifold with the $\\beta$-metric, the surrogate minimization matches exact Riemannian gradient descent in objective value while running more than 100 times faster; the lifting-map baseline has similar cost but lacks guaranteed behavior on spread datasets, whereas the surrogate carries the Theorem 1 certificate.","The certificate is always satisfied in the reported experiments and is tighter for clustered datasets, where the distance brackets are sharper.","The same sandwich construction yields a computable upper bound on the geodesic distance between the true and approximate barycenters (Theorem 2).","Riemannian gradient descent on the exact objective becomes intractable for large $N,n,p$, while the surrogate approach remains practical, making it a worthwhile alternative."],"supporting_citations":[{"why":"Supplies the global distance brackets $\\underline{m}_\\beta$ and $\\overline{M}_\\beta$ on the Stiefel manifold with $n\\ge 2p$; the whole surrogate construction and Theorem 1 rest on these bounds.","marker":"[12]"},{"why":"Provides the gradient formula for the distance objective and the stationarity condition (4) that defines the exact barycenter used as baseline and target.","marker":"[4]"},{"why":"Establishes existence and uniqueness conditions for the Riemannian $l_\\nu$-barycenter $x_*$, so the comparison chain (6) has a well-defined optimum.","marker":"[3]"},{"why":"Supplies the numerical Riemannian logarithm on the Stiefel manifold used by the exact gradient-descent baseline and for evaluating true distances.","marker":"[17]"},{"why":"Introduces the lifting-map fixed-point iteration used as the third baseline algorithm, whose behavior on spread data is noted as not guaranteed.","marker":"[10]"}],"fun_headline_variants":["Certified Riemannian barycenters with 100x speedup on Stiefel","Approximate barycenter with rigorous error bound, 100x faster","Under- and over-approximations give certifiable Riemannian means","Surrogate minimization yields certified approximate barycenter"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction stands on the proven bracketing inequalities $\\underline{m}_\\beta \\le d_\\beta \\le \\overline{M}_\\beta$ being valid for every pair of points on the Stiefel manifold with $n\\ge 2p$; if any pair violated them, the chain in (6) would break and Theorem 1 would no longer certify the approximation.","fun_headline_variants_meta":{"raw":{"variants":["Certified Riemannian barycenters with 100x speedup on Stiefel","Approximate barycenter with rigorous error bound, 100x faster","Under- and over-approximations give certifiable Riemannian means","Surrogate minimization yields certified approximate barycenter"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000261,"raw_usage":{"total_tokens":1518,"prompt_tokens":798,"completion_tokens":720,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":414,"completion_tokens_details":{"reasoning_tokens":645}},"tokens_in":414,"tokens_out":720,"duration_ms":5985,"temperature":1.0,"reasoning_tokens":645,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:20:38.032267+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the true geodesic distance for a pair of points on St$(n,p)$ with $n\\ge 2p$ using a reliable numerical Riemannian logarithm and compare it with $\\underline{m}_\\beta$ and $\\overline{M}_\\beta$; a single pair where the lower bound exceeds the true distance or the upper bound falls below it would invalidate the certificate at the root of Theorem 1.","supporting_citations":[{"cited_title":"Proceedings of the American Mathematical Society139(2), 655–673 (2011),http: //www.jstor.org/stable/41059320","cited_arxiv_id":null,"evidence_quote":"Establishes existence and uniqueness conditions for the Riemannian $l_\\nu$-barycenter $x_*$, so the comparison chain (6) has a well-defined optimum."},{"cited_title":"IEEE Transactions on Signal Processing61, 883–894 (02 2013), https://doi.org/10.1109/TSP.2012.2226167","cited_arxiv_id":null,"evidence_quote":"Introduces the lifting-map fixed-point iteration used as the third baseline algorithm, whose behavior on spread data is noted as not guaranteed."}],"review_version":1}