Randomized Block Frank-Wolfe for Convergent Large-Scale Learning

Liang Zhang, Gang Wang, Daniel Romero, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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 O(1/√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.

Original languageEnglish (US)
Article number8047993
Pages (from-to)6448-6461
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume65
Issue number24
DOIs
StatePublished - Dec 15 2017

Bibliographical note

Funding Information:
Manuscript received December 26, 2016; revised May 27, 2017 and September 7, 2017; accepted September 15, 2017. Date of publication September 21, 2017; date of current version October 20, 2017. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Marco Moretti. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by the National Science Foundation Grants 1423316, 1442686, 1508993, and 1509040. The work of D. Romero was supported in part by the PETROMAKS Smart-Rig Grant 244205/E30 and in part by the TOPPFORSK WISECART Grant 250910/F20 from the Research Council of Norway. (Corresponding author: Georgios B. Giannakis.) L. Zhang and G. B. Giannakis are with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA (e-mail: zhan3523@umn.edu; georgios@ umn.edu).

Keywords

  • Conditional gradient descent
  • block coordinate
  • nonconvex optimization
  • parallel optimization

Fingerprint Dive into the research topics of 'Randomized Block Frank-Wolfe for Convergent Large-Scale Learning'. Together they form a unique fingerprint.

Cite this