Dual Randomized Coordinate Descent Method for Solving a Class of Nonconvex Problems
提出一种低计算成本的随机坐标下降方法，用于求解最大化两个凸函数之差的问题，证明了对偶稳定点的子序列收敛性，并在三个主成分分析模型上展示了简单有效的算法。
We consider a nonconvex optimization problem consisting of maximizing the difference of two convex functions. We present a randomized method that requires low computational effort at each iteration. The described method is a randomized coordinate descent method employed on the so-called Toland-dual problem. We prove subsequence convergence to dual stationarity points, a new notion that we introduce and which is shown to be tighter than standard criticality. An almost sure rate of convergence of an optimality measure of the dual sequence is proven. We demonstrate the potential of our results on three principal component analysis models resulting in extremely simple algorithms.