An Apocalypse-Free First-Order Low-Rank Optimization Algorithm with at Most One Rank Reduction Attempt per Iteration

We consider the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on the real determinantal variety and present a first-order algorithm designed to find a stationary point of that problem. This algorithm applies steps of a retraction-free descent method proposed by Schneider and Uschmajew [SIAM J. Optim., 25 (2015), pp. 622–646], while taking the numerical rank into account to attempt rank reductions. We prove that this algorithm produces a sequence of iterates whose accumulation points are stationary and therefore does not follow the so-called apocalypses described by Levin, Kileel, and Boumal [Math. Program., 199 (2023), pp. 831–864]. Moreover, the rank reduction mechanism of this algorithm requires at most one rank reduction attempt per iteration, in contrast with the one of the algorithm introduced by Olikier, Gallivan, and Absil [An Apocalypse-Free First-Order Low-Rank Optimization Algorithm, Technical report UCL-INMA-2022.01, https://arxiv.org/abs/2201.03962, 2022], which can require a number of rank reduction attempts equal to the rank of the iterate in the worst-case scenario.