Convex optimization over the spectrahedron, i.e., the set of all real $n\times 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 SVD computation on each iteration, which is not scalable to high-dimensional problems. In this work we propose an efficient implementations of MEG, both with 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 which both support our theoretical findings and demonstrate the practical appeal of our methods.
翻译:对光谱优化, 即所有真实的美元时正正的半确定性矩阵的组合, 具有在机器学习、 信号处理和统计方面的重要应用, 主要是对低级矩阵优化问题的一种松绑放松, 也是最突出的例子之一。 在光谱优化第一阶方法理论中, 非欧洲的优化方法可以大大优于欧洲的对等方。 特别是, 理想的选择是基于( 否定的) von Neumann entropy 引发的布雷格曼距离的矩阵指数指数指数指数指数( MEG) 方法。 不幸的是, 实施MEG 需要在每个循环上进行全面的 SVD 计算, 这对高度问题来说是无法伸缩的。 在这项工作中, 我们建议高效地实施MEG, 使用确定性和基于低级的梯度梯度梯度, 并且只使用单一低级的SVD 梯度的指数(MEEG) 方法, 将我们提出的最终的精确的对比性测试方法带到了我们提出的最终的精确的对比。