Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Bokun Wang;Shiqian Ma;Lingzhou Xue
中科院分区：
文献类型：
--
作者：
Bokun Wang;Shiqian Ma;Lingzhou Xue
黎曼最优化因其在实际中的广泛应用而引起人们的广泛关注。黎曼随机一阶算法已经在文献中研究，以解决黎曼流形上的大规模机器学习问题。然而，现有的大多数黎曼随机算法要求目标函数是可微的，并且它们不适用于目标函数是非光滑的情况。本文给出了Stiefel流形上极小化非光滑函数的两种黎曼随机邻近梯度方法。这两种方法，称为R-ProxSGD和R-ProxSPB，是近端SGD和近端SpiderBoost在欧几里得设置到黎曼设置的推广。分析了算法的增量一阶预言（IFO）复杂度。具体来说，R-ProxSPB算法在在线情况下找到$\mathcal{O}（\sqrt {n}\sqrt ^{-3}）$IFO的$\mathcal $-稳定点，在有限和情况下找到$\mathcal{O}（n+\sqrt{n}\sqrt ^{-3}）$IFO，其中$n$是目标中的被加数。在线稀疏PCA和鲁棒低秩矩阵完成的实验结果表明，我们提出的方法显着优于现有的方法，使用黎曼次梯度信息。
Riemannian optimization has drawn a lot of attention due to its wide applications in practice. Riemannian stochastic first-order algorithms have been studied in the literature to solve large-scale machine learning problems over Riemannian manifolds. However, most of the existing Riemannian stochastic algorithms require the objective function to be differentiable, and they do not apply to the case where the objective function is nonsmooth. In this paper, we present two Riemannian stochastic proximal gradient methods for minimizing nonsmooth function over the Stiefel manifold. The two methods, named R-ProxSGD and R-ProxSPB, are generalizations of proximal SGD and proximal SpiderBoost in Euclidean setting to the Riemannian setting. Analysis on the incremental first-order oracle (IFO) complexity of the proposed algorithms is provided. Specifically, the R-ProxSPB algorithm finds an $\epsilon$-stationary point with $\mathcal{O}(\epsilon^{-3})$ IFOs in the online case, and $\mathcal{O}(n+\sqrt{n}\epsilon^{-3})$ IFOs in the finite-sum case with $n$ being the number of summands in the objective. Experimental results on online sparse PCA and robust low-rank matrix completion show that our proposed methods significantly outperform the existing methods that uses Riemannian subgradient information.