Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization
Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization
复制标题
DOI：
10.1007/s10589-017-9972-z
复制
发表时间：
2017-02
影响因子：
2.2
通讯作者：
Yangyang Xu;Shuzhong Zhang
中科院分区：
文献类型：
--
作者：
Yangyang Xu;Shuzhong Zhang
块坐标更新（BCU）方法享有低的每次更新的计算复杂度，因为每次只有一个或几个块变量将需要更新中可能大量的块。它们也很容易并行化，因此在解决涉及大规模数据集和/或变量的问题时特别受欢迎。本文提出了一种求解多块变量线性约束凸规划的原-对偶BCU方法。该方法是作者提出的原始-对偶算法的加速版本，它在选择块变量时采用随机化进行更新，并在凸性假设下建立了O（1 /t）的收敛速度。我们证明了如果目标是强凸的，则该速率可以被加速到。此外，如果一个块变量是独立的其他的目标，我们然后表明，该算法可以修改，以实现线性收敛速度。数值实验表明，加速方法执行稳定的一组参数，而原来的方法需要调整不同的数据集的参数，以达到可比的性能水平。
Block coordinate update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal–dual BCU method for solving linearly constrained convex program with multi-block variables. The method is an accelerated version of a primal–dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes anO(1 /t) convergence rate under convexity assumption. We show that the rate can be accelerated toif the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance.