On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization

Dan Garber () and Atara Kaplan ()
Additional contact information
Dan Garber: Technion–Israel Institute of Technology, Haifa 3200003, Israel
Atara Kaplan: Technion–Israel Institute of Technology, Haifa 3200003, Israel

Mathematics of Operations Research, 2023, vol. 48, issue 4, 2094-2128

Abstract: Convex optimization over the spectrahedron, that is, the set of all real n × n positive semidefinite matrices with unit trace, has important applications in machine learning, signal processing, and statistics, mainly as a convex relaxation for optimization problems with low-rank matrices. It is also one of the most prominent examples in the theory of first order methods for convex optimization in which non-Euclidean methods can be significantly preferable to their Euclidean counterparts. In particular, the desirable choice is the matrix exponentiated gradient (MEG) method, which is based on the Bregman distance induced by the (negative) von Neumann entropy. Unfortunately, implementing MEG requires a full singular value decomposition (SVD) computation on each iteration, which is not scalable to high-dimensional problems. In this work, we propose efficient implementations of MEG, with both deterministic and stochastic gradients, which are tailored for optimization with low-rank matrices, and only use a single low-rank SVD computation on each iteration. We also provide efficiently computable certificates for the correct convergence of our methods. Mainly, we prove that, under a strict complementarity condition, the suggested methods converge from a warm-start initialization with similar rates to their full SVD–based counterparts. Finally, we bring empirical experiments that both support our theoretical findings and demonstrate the practical appeal of our methods.

Keywords: Primary: 90C22; 90C06; 68W27; 68W20; matrix exponentiated gradient; low-rank matrix recovery; low-rank optimization; first order methods (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1332 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:4:p:2094-2128

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().