pith. sign in

arxiv: 2503.04523 · v2 · pith:EOVKVYAWnew · submitted 2025-03-06 · 🧮 math.OC · cs.NA· math.AG· math.NA

First-order methods on bounded-rank tensors converging to stationary points

Bin Gao , Renfeng Peng , Ya-Xiang Yuan This is my paper

Pith reviewed 2026-05-23 01:11 UTC · model grok-4.3

classification 🧮 math.OC cs.NAmath.AGmath.NA
keywords bounded-rank tensorsfirst-order methodsstationary pointsnormal conestensor completionvariational geometryrank-decreasing mechanismsapproximate projections
0
0 comments X

The pith

Two first-order methods converge to stationary points on bounded-rank tensors by characterizing normal cones and using rank-decreasing steps.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses the open problem of finding stationary points on the non-smooth set of bounded-rank tensors. It revisits the variational geometry of this set and gives explicit normal cone characterizations. Two new first-order methods are introduced that combine gradient-related vectors from tangent cones, line search along approximate projections, and rank-decreasing mechanisms near rank-deficient points. These ingredients produce descent directions even when some but not all modes are full rank. Experiments on tensor completion show the methods reach stationary points for different rank choices.

Core claim

By explicitly characterizing the normal cones of bounded-rank tensors, gradient-related approximate projection methods can be constructed that converge to stationary points; the key components are gradient-related vectors drawn from tangent cones, line search along approximate projections, and rank-decreasing mechanisms applied near rank-deficient points.

What carries the argument

Gradient-related approximate projection methods that use explicit normal-cone information and rank-decreasing steps at rank-deficient points.

If this is right

  • The methods guarantee convergence to stationary points on bounded-rank tensors where some modes may be rank-deficient.
  • Line search along approximate projections combined with rank-decreasing steps produces sufficient descent at every iteration.
  • The same framework applies to tensor completion problems across varying rank parameters.
  • Convergence holds for both proposed first-order schemes once the normal cones are available.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The normal-cone approach could be tested on other non-smooth manifold constraints such as fixed-rank matrix or tensor varieties.
  • The explicit characterizations might support the design of accelerated or second-order variants for the same problem class.
  • Practical performance on large-scale tensor problems could be compared against existing heuristic rank-adaptive schemes.

Load-bearing premise

The variational geometry of bounded-rank tensors admits explicit normal-cone characterizations that allow construction of descent directions even at rank-deficient points.

What would settle it

A concrete bounded-rank tensor instance on which one of the proposed methods terminates at a point whose gradient does not lie in the normal cone of the set.

read the original abstract

Provably finding stationary points on bounded-rank tensors turns out to be an open problem [E. Levin, J. Kileel, and N. Boumal, Math. Program., 199 (2023), pp. 831--864] due to the inherent non-smoothness of the set of bounded-rank tensors. In contrast with bounded-rank matrices, tensors where some but not all modes are of full rank render essential difficulties in developing provable first-order methods. We resolve this problem by proposing two first-order methods with guaranteed convergence to stationary points. Specifically, we revisit the variational geometry of bounded-rank tensors and explicitly characterize its normal cones. Moreover, we propose gradient-related approximate projection methods that are provable to find stationary points, where the decisive ingredients are gradient-related vectors from tangent cones, line search along approximate projections, and rank-decreasing mechanisms near rank-deficient points. Numerical experiments on tensor completion validate that the proposed methods converge to stationary points across various rank parameters.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript addresses the open problem of provably locating stationary points on the non-smooth set of bounded-rank tensors. It revisits the variational geometry to give explicit normal-cone characterizations, then introduces two first-order methods (gradient-related approximate projection schemes) that combine tangent-cone gradient-related directions, line search on approximate projections, and rank-decreasing steps near rank-deficient points to guarantee convergence to stationary points. Numerical validation on tensor-completion instances is reported.

Significance. If the convergence claims hold, the work supplies the first provable first-order algorithms for this setting, closing the gap left open by Levin-Kileel-Boumal (2023) and extending the matrix case to tensors. The explicit normal-cone description is a reusable geometric contribution that could support further algorithmic development on tensor varieties.

minor comments (2)
  1. [Abstract] Abstract and introduction refer to 'two first-order methods' without immediately naming or distinguishing them; adding a short sentence or subsection label would improve readability.
  2. The claim that the normal-cone characterizations are 'explicit' should be cross-referenced to the precise statement (e.g., the theorem or proposition that lists the cone generators) so readers can locate the formulas without searching.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of its contributions, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper cites an external open problem from Levin, Kileel, and Boumal (distinct authors) and resolves it via new explicit normal-cone characterizations of bounded-rank tensors plus convergence proofs for two first-order methods. No equations reduce claimed convergence to a self-referential fit or definition; no load-bearing self-citations appear; the geometry and descent arguments are presented as independent contributions. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the claimed advance rests on standard variational geometry and the new algorithmic mechanisms described at a high level.

pith-pipeline@v0.9.0 · 5706 in / 1070 out tokens · 53101 ms · 2026-05-23T01:11:03.859047+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Absil, R

    P.-A. Absil, R. Mahony, and R. Sepulchre , Optimization algorithms on matrix manifolds , in Optimization Algorithms on Matrix Manifolds, Princeton University Press, 2009

    work page 2009

  2. [2]

    Boumal, An introduction to optimization on smooth manifolds, Cambridge University Press, 2023

    N. Boumal, An introduction to optimization on smooth manifolds, Cambridge University Press, 2023

    work page 2023

  3. [3]

    Boumal, P.-A

    N. Boumal, P.-A. Absil, and C. Cartis , Global rates of convergence for nonconvex optimiza- tion on manifolds , IMA Journal of Numerical Analysis, 39 (2019), pp. 1–33

    work page 2019

  4. [4]

    De Lathauwer, B

    L. De Lathauwer, B. De Moor, and J. V andewalle , A multilinear singular value decom- position, SIAM journal on Matrix Analysis and Applications, 21 (2000), pp. 1253–1278

    work page 2000

  5. [5]

    De Silva and L.-H

    V. De Silva and L.-H. Lim , Tensor rank and the ill-posedness of the best low-rank approxi- mation problem, SIAM Journal on Matrix Analysis and Applications, 30 (2008), pp. 1084– 1127

    work page 2008

  6. [6]

    S. Dong, B. Gao, Y. Guan, and F. Glineur , New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition , SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 840–866

    work page 2022

  7. [7]

    B. Gao, R. Peng, and Y.-x. Yuan , Optimization on product manifolds under a preconditioned metric, arXiv preprint arXiv:2306.08873, (2023)

    work page arXiv 2023

  8. [8]

    B. Gao, R. Peng, and Y.-x. Yuan , Desingularization of bounded-rank tensor sets , arXiv preprint arXiv:2411.14093, (2024)

    work page arXiv 2024

  9. [9]

    B. Gao, R. Peng, and Y.-x. Yuan , Riemannian preconditioned algorithms for tensor com- pletion via tensor ring decomposition , Computational Optimization and Applications, 88 (2024), pp. 443–468

    work page 2024

  10. [10]

    B. Gao, R. Peng, and Y.-x. Yuan , Low-rank optimization on Tucker tensor varieties , Math- ematical Programming, (2025), pp. 1–51

    work page 2025

  11. [11]

    Grasedyck , Hierarchical singular value decomposition of tensors , SIAM journal on matrix analysis and applications, 31 (2010), pp

    L. Grasedyck , Hierarchical singular value decomposition of tensors , SIAM journal on matrix analysis and applications, 31 (2010), pp. 2029–2054

    work page 2010

  12. [12]

    W. Ha, H. Liu, and R. F. Barber , An equivalence between critical points for rank constraints versus low-rank factorizations , SIAM Journal on Optimization, 30 (2020), pp. 2927–2955

    work page 2020

  13. [13]

    C. J. Hillar and L.-H. Lim , Most tensor problems are NP-hard, Journal of the ACM (JACM), 60 (2013), pp. 1–39

    work page 2013

  14. [14]

    P. Jain, A. Tewari, and P. Kar , On iterative hard thresholding methods for high-dimensional m-estimation, in Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, eds., vol. 27, Curran Associates, Inc., 2014

    work page 2014

  15. [15]

    Kasai and B

    H. Kasai and B. Mishra , Low-rank tensor completion: a Riemannian manifold precondition- ing approach, in Proceedings of The 33rd International Conference on Machine Learning, M. F. Balcan and K. Q. Weinberger, eds., vol. 48 of Proceedings of Machine Learning Research, New York, New York, USA, 6 2016, PMLR, pp. 1012–1021

    work page 2016

  16. [16]

    Koch and C

    O. Koch and C. Lubich , Dynamical tensor approximation, SIAM Journal on Matrix Analysis and Applications, 31 (2010), pp. 2360–2375

    work page 2010

  17. [17]

    T. G. Kolda and B. W. Bader , Tensor decompositions and applications , SIAM review, 51 (2009), pp. 455–500

    work page 2009

  18. [18]

    Kressner, M

    D. Kressner, M. Steinlechner, and B. V andereycken , Low-rank tensor completion by Riemannian optimization, BIT Numerical Mathematics, 54 (2014), pp. 447–468

    work page 2014

  19. [19]

    Levin, J

    E. Levin, J. Kileel, and N. Boumal , Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy , Mathematical Programming, 199 (2023), pp. 831– 864

    work page 2023

  20. [20]

    Levin, J

    E. Levin, J. Kileel, and N. Boumal , The effect of smooth parametrizations on nonconvex optimization landscapes, Mathematical Programming, (2024), pp. 1–49

    work page 2024

  21. [21]

    Olikier and P.-A

    G. Olikier and P.-A. Absil , An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration , SIAM Journal on Matrix Analysis and Applications, 44 (2023), pp. 1421–1435

    work page 2023

  22. [22]

    Olikier, K

    G. Olikier, K. A. Gallivan, and P.-A. Absil , First-order optimization on stratified sets , arXiv preprint arXiv:2303.16040, (2023)

    work page arXiv 2023

  23. [23]

    Olikier, K

    G. Olikier, K. A. Gallivan, and P.-A. Absil , Low-rank optimization methods based on projected-projected gradient descent that accumulate at Bouligand stationary points, arXiv preprint arXiv:2201.03962, (2024)

    work page arXiv 2024

  24. [24]

    Olikier and I

    G. Olikier and I. W aldspurger , Projected gradient descent accumulates at Bouligand sta- tionary points, arXiv preprint arXiv:2403.02530, (2024)

    work page arXiv 2024

  25. [25]

    Rebjock and N

    Q. Rebjock and N. Boumal , Optimization over bounded-rank matrices through a desingular- ization enables joint global and local guarantees , arXiv preprint arXiv:2406.14211, (2024). 26 B. GAO, R. PENG, AND Y.-X. YUAN

    work page arXiv 2024

  26. [26]

    Schneider and A

    R. Schneider and A. Uschmajew , Convergence results for projected line-search methods on varieties of low-rank matrices via lojasiewicz inequality , SIAM Journal on Optimization, 25 (2015), pp. 622–646

    work page 2015

  27. [27]

    Shalit, D

    U. Shalit, D. Weinshall, and G. Chechik , Online learning in the embedded manifold of low-rank matrices, Journal of Machine Learning Research, 13 (2012)

    work page 2012

  28. [28]

    Steinlechner , Riemannian optimization for high-dimensional tensor completion , SIAM Journal on Scientific Computing, 38 (2016), pp

    M. Steinlechner , Riemannian optimization for high-dimensional tensor completion , SIAM Journal on Scientific Computing, 38 (2016), pp. S461–S484

    work page 2016

  29. [29]

    L. R. Tucker , Some mathematical notes on three-mode factor analysis , Psychometrika, 31 (1966), pp. 279–311

    work page 1966

  30. [30]

    L. R. Tucker et al. , The extension of factor analysis to three-dimensional matrices , Contri- butions to mathematical psychology, 110119 (1964)

    work page 1964

  31. [31]

    Uschmajew and B

    A. Uschmajew and B. V andereycken, The geometry of algorithms using hierarchical tensors, Linear Algebra and its Applications, 439 (2013), pp. 133–166

    work page 2013

  32. [32]

    Uschmajew and B

    A. Uschmajew and B. V andereycken , Geometric methods on low-rank matrix and tensor manifolds, in Handbook of variational methods for nonlinear geometric data, Springer, 2020, pp. 261–313

    work page 2020

  33. [33]

    V andereycken, Low-rank matrix completion by Riemannian optimization , SIAM Journal on Optimization, 23 (2013), pp

    B. V andereycken, Low-rank matrix completion by Riemannian optimization , SIAM Journal on Optimization, 23 (2013), pp. 1214–1236

    work page 2013

  34. [34]

    M. A. O. V asilescu and D. Terzopoulos , Multilinear subspace analysis of image ensembles , in 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,

    work page 2003

  35. [35]

    2, IEEE, 2003, pp

    Proceedings., vol. 2, IEEE, 2003, pp. II–93

    work page 2003