Paper ID sheet UCLINMA2022.07
 Title

An apocalypsefree firstorder lowrank optimization algorithm with at most one rank reduction attempt per iteration
 Authors
 Guillaume Olikier, P.A. Absil
 Abstract

We consider the problem of minimizing a differentiable function with locally Lipschitz continuous gradient over the real determinantal variety, and present a firstorder algorithm designed to find stationary points of that problem. This algorithm applies steps of a retractionfree descent method proposed by Schneider and Uschmajew (2015), while taking the numerical rank into account to attempt rank reductions. We prove that this algorithm produces a sequence of iterates the accumulation points of which are stationary, and therefore does not follow the socalled apocalypses described by Levin, Kileel, and Boumal (2022). Moreover, the rank reduction mechanism of this algorithm requires at most one rank reduction attempt per iteration, in contrast with the one of the P2GDR algorithm introduced by Olikier, Gallivan, and Absil (2022) which can require a number of rank reduction attempts equal to the rank of the iterate in the worstcase scenario.
 Key words
 Convergence analysis; Stationarity; Lowrank optimization; Determinantal variety; Firstorder method; Steepest descent; Tangent cones; QR factorization; Singular value decomposition
 Status
 Submitted
 Download

[Home]