The Cyclic Block Conditional Gradient Method for Convex Optimization Problems

By Amir Beck, Edouard Pauwels, Shoham Sabach. 2015

46 citations recorded by the source corpus.

In this paper we study the convex problem of optimizing the sum of a smooth function and a compactly supported nonsmooth term with a specific separable form. We analyze the block version of the generalized conditional gradient method when the blocks are chosen in a cyclic order. A global sublinear rate of convergence is established for two different stepsize strategies commonly used in this class of methods. Numerical comparisons of the proposed method to both the classical conditional gradient algorithm and its random block version demonstrate the effectiveness of the cyclic block update rule.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, background): “Their FASOLE algorithm also contains a version of gap sampling in the form of variable shrinking: if a block gap becomes small enough, the block is not visited again, until all the counters are reset.”
Linearly Convergent Frank-Wolfe with Backtracking Line-Search. (2018, methodology): “In this ﬁ gure we also show the performance of FW, Away-steps FW (AFW) and Pairwise FW (PFW), all of them using the step-size � � , as well as the back-tracking variants of Dunn (1980) and (Beck et al., 2015), which we denote D-FW and B-FW respectively.”