提出首个线性收敛的低秩弗兰克-沃尔夫算法，用于大规模矩阵优化。
A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron
- 基于随机化策略改进弗兰克-沃尔夫法，仅需秩一矩阵计算
- 在二次增长与严格互补条件下，期望线性收敛且与维度无关
- 适合处理高维正定矩阵约束的机器学习问题
我们研究在n维谱体（即迹为1的实对称n×n半正定矩阵集合）上最小化光滑凸函数的问题，该问题广泛存在于统计学、机器学习等领域。标准一阶方法常需高秩矩阵计算，在高维时不可行；而经典弗兰克-沃尔夫法虽只需秩一计算，但收敛速度慢。本文提出首个基于弗兰克-沃尔夫的算法，仅使用高效秩一矩阵运算，在假设二次增长和严格互补条件下，经过有限次迭代后，以期望方式实现线性收敛，且不依赖于环境维度。
原文摘要 · Abstract (English)
We consider the problem of minimizing a smooth and convex function over the $n$-dimensional spectrahedron -- the set of real symmetric $n\times n$ positive semidefinite matrices with unit trace, which underlies numerous applications in statistics, machine learning and additional domains. Standard first-order methods often require high-rank matrix computations which are prohibitive when the dimension $n$ is large. The well-known Frank-Wolfe method on the other hand only requires efficient rank-one matrix computations, however, suffers from worst-case slow convergence, even under conditions that enable linear convergence rates for standard methods. In this work we present the first Frank-Wolfe-based algorithm that only applies efficient rank-one matrix computations and, assuming quadratic growth and strict complementarity conditions, is guaranteed, after a finite number of iterations, to converge linearly, in expectation, and independently of the ambient dimension.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。