论文标题
大规模线性约束凸编程的随机原始二线坐标方法的线性收敛
Linear Convergence of Randomized Primal-Dual Coordinate Method for Large-scale Linear Constrained Convex Programming
论文作者
论文摘要
线性约束凸编程具有许多实际应用，包括支持向量机和机器学习组合问题。我们提出了随机原始偶坐标（RPDC）方法，这是Cohen and Zhu，1984和Zhao and Zhu，2019年的一阶原始二重性方法的随机坐标扩展，以求解线性约束的CONVEX程序。我们根据均匀分布，线性化并将类似Bregman的函数（核心函数）随机选择变量块，以获得简单的并行原始二重分解。然后，我们几乎可以肯定地建立收敛性和预期的O（1/T）收敛速率，并在全球强度度副定制下预期线性收敛。最后，我们讨论了随机原始偶坐标方法的实现详细信息，并在支持向量机和机器学习组合问题上进行了数值实验，以验证线性收敛。
Linear constrained convex programming has many practical applications, including support vector machine and machine learning portfolio problems. We propose the randomized primal-dual coordinate (RPDC) method, a randomized coordinate extension of the first-order primal-dual method by Cohen and Zhu, 1984 and Zhao and Zhu, 2019, to solve linear constrained convex programming. We randomly choose a block of variables based on a uniform distribution, linearize, and apply a Bregman-like function (core function) to the selected block to obtain simple parallel primal-dual decomposition. We then establish almost surely convergence and expected O(1/t) convergence rate, and expected linear convergence under global strong metric subregularity. Finally, we discuss implementation details for the randomized primal-dual coordinate approach and present numerical experiments on support vector machine and machine learning portfolio problems to verify the linear convergence.
