Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size
cs.LG · math.OC · quant-ph
Quick verdict
Proposes projected unit-step RGD for BW barycenters via a new non-expansive clipping lemma; the dimension-free κ^{3/2} rate appears sound but loose.
Summary
This paper closes a theory-practice gap in computing Bures-Wasserstein (BW) barycenters of positive definite matrices. The fixed-point iteration used in practice is unit-step Riemannian gradient descent (RGD), but existing guarantees either carry worst-case κ^d dimension dependence (Chewi et al. 2020) or require small steps η=O(1/κ) with O(κ^(5/2)) complexity (Altschuler et al. 2021). The author proposes Projected BW-GD: each unit-step iteration is followed by eigenvalue clipping into a spectral band [αI, βI] known to contain the optimum. The central technical contribution (Lemma 6) proves that two-sided clipping is the exact BW-metric projection onto this band and is non-expansive, extending the known one-sided result via the data-processing inequality, the Alberti-Uhlmann formula, and operator monotonicity. Because the reference matrices are fixed points of the clip and the projection is free (it reuses the next iteration's eigendecomposition), the projected iteration inherits unit-step descent plus a Polyak-Łojasiewicz inequality on the band, yielding a dimension-independent linear rate (1−κ^(−3/2)) — κ^(3/2)log(1/ε) complexity, polynomially better than κ^(5/2). The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose algorithm is identified as unit-step RGD on a totally geodesic submanifold. Experiments (d up to 64, κ up to 10³) show unit-step converges orders of magnitude faster than small-step, with counts essentially flat in d, and the clip almost never activates. Limitations: the guaranteed rate is far looser than observed behavior, the guarantee strictly covers only the projected algorithm, and experiments are synthetic-only.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 4
● low 0
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Two-sided eigenvalue clipping to [α, β] is the exact BW-metric projection onto [αI, βI] and is non-expansive (1-Lipschitz), a two-sided extension of the known one-sided contraction of ACGS21 that does not follow from convexity (Lemma 6).
- Projected BW-GD at unit step size converges linearly at dimension-independent rate (1−κ^(−3/2)) for both the BW barycenter and the invariant matrix projection problem, giving κ^(3/2)log(1/ε) iteration complexity (Theorem 10), polynomially better than the O(κ^(5/2)) small-step guarantee of ACGS21.
- The well-conditioned set [αI, βI] is not invariant under unprojected unit-step RGD: Example 13 exhibits an instance (d=2, n=3, κ=300) where ensemble, iterate, and barycenter are strictly interior yet two consecutive iterates exit below αI, and the construction extends to all n≥3, d≥2.
- The fixed-point algorithm of Brahmachari-Rubboli-Tomamichel (2025) is exactly unit-step RGD on the submanifold of invariant matrices, which is totally geodesic, so the dimension-free guarantee extends to that setting verbatim (Appendix E).
- The projection is free: eigenvalue clipping reuses the eigendecomposition the next iteration computes in any case, so projected and unprojected iterations cost the same per step (n+1 eigendecompositions).
Strengths
Genuinely new projection lemma with a non-convexity-oblivious proof technique
Lemma 6 proves two-sided eigenvalue clipping is the exact, non-expansive BW projection onto [αI, βI]. Unlike the one-sided case [ACGS21, Prop. 3], this does not follow from convexity; the proof combines the data-processing inequality with pinching for exactness, and the Alberti-Uhlmann variational formula with operator monotonicity of the geometric mean for 1-Lipschitzness.
Resolves a real dichotomy with a polynomially better exponent
Theorem 10 delivers the first dimension-free guarantee at unit step: κ^(3/2)log(1/ε) versus O(κ^(5/2)log(1/ε)) at η=1/(2κ′) of ACGS21. Appendix C's refined interval [α′I, β′I] (Prop. 15) makes the comparison instance-wise, since κ′ ≤ the refined constant of ACGS21.
Zero-overhead algorithm design with a fair comparison protocol
Unified structural analysis with usable by-products
Reproducibility posture and honest scoping
Weaknesses
Guarantee far looser than practice
Theory covers a slightly different algorithm than the one used in practice
Illustrative-only experiments
LLM-derived crux results
Negative result needs adversarial initialization
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- PDF extraction mangles some display math (e.g., '¿ Á ÁÀ' artifacts in Eqs. (73)-(74), and figure-axis digits interleaved into Example 13's weight vector, which is (0.12, 0.827, 0.053)); the content is recoverable and all cited numbers were read from the extraction.
- The provided text ends at the final paragraph of Appendix E ('...maps under π exactly to Eq. (96).'); any closing sentences beyond that point were not available, though Sections 1-6 and the cores of Appendices A-E are all present.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.