Randomized Block Frank–Wolfe for Convergent Large-Scale Learning
Randomized Block Frank–Wolfe for Convergent Large-Scale Learning
复制标题
DOI：
10.1109/tsp.2017.2755597
复制
发表时间：
2016-12
影响因子：
5.4
通讯作者：
Liang Zhang;G. Wang;Daniel Romero;G. Giannakis
中科院分区：
文献类型：
--
作者：
Liang Zhang;G. Wang;Daniel Romero;G. Giannakis
由于其低复杂度的迭代，Frank-Wolfe（FW）求解器非常适合各种大规模的学习任务。当存在块可分离约束时，随机化块FW（RB-FW）已被证明通过每次迭代仅更新一部分坐标块来进一步降低复杂性。为了规避现有方法的局限性，本文开发了RB-FW的步长，使每次迭代更新的块的数量的灵活选择，同时确保迭代的收敛性和可行性。为此，RB-FW的收敛速度建立通过计算上的原始次优措施和对偶间隙的界限。新的界限扩展了现有的收敛性分析，这只适用于一个步长序列，一般不会导致可行的迭代。此外，还提出了两类保证迭代可行性的步长序列，以提高选择衰减率的灵活性。新的收敛结果显着扩大，也包括非凸目标，并进一步断言，RB-FW精确线搜索达到一个稳定点的速度$\mathcal{O}（1/\sqrt{t}）$。RB-FW的性能与不同的步长和块的数量证明在两个应用程序中，即电动汽车充电和结构支持向量机。大量的模拟测试表明，RB-FW相对于现有的随机单块FW方法的性能改善。
Owing to their low-complexity iterations, Frank–Wolfe (FW) solvers are well suited for various large-scale learning tasks. When block-separable constraints are present, randomized block FW (RB-FW) has been shown to further reduce complexity by updating only a fraction of coordinate blocks per iteration. To circumvent the limitations of existing methods, this paper develops step sizes for RB-FW that enable a flexible selection of the number of blocks to update per iteration while ensuring convergence and feasibility of the iterates. To this end, convergence rates of RB-FW are established through computational bounds on a primal suboptimality measure and on the duality gap. The novel bounds extend the existing convergence analysis, which only applies to a step-size sequence that does not generally lead to feasible iterates. Furthermore, two classes of step-size sequences that guarantee feasibility of the iterates are also proposed to enhance flexibility in choosing decay rates. The novel convergence results are markedly broadened to also encompass nonconvex objectives, and further assert that RB-FW with exact line-search reaches a stationary point at rate $\mathcal{O}(1/\sqrt{t})$. Performance of RB-FW with different step sizes and number of blocks is demonstrated in two applications, namely charging of electrical vehicles and structural support vector machines. Extensive simulated tests demonstrate the performance improvement of RB-FW relative to existing randomized single-block FW methods.