Frank-Wolfe with Subsampling Oracle.

TITLE: Frank-Wolfe with Subsampling Oracle.

AUTHORS: Thomas Kerdreux, Fabian Pedregosa and Alexandre d'Aspremont.

ABSTRACT: We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small subset of the original domain. The first algorithm that we propose is a randomized variant of the original FW algorithm and achieves a O(1/t) sublinear convergence rate as in the deterministic counterpart. The second algorithm is a randomized variant of the Away-step FW algorithm, and again as its deterministic counterpart, reaches linear (i.e., exponential) convergence rate making it the first provably convergent randomized variant of Away-step FW. In both cases, while subsampling reduces the convergence rate by a constant factor, the linear minimization step can be a fraction of the cost of that of the deterministic versions, especially when the data is streamed. We illustrate computational gains of the algorithms on regression problems, involving both l_1 and latent group lasso penalties.

STATUS: Preprint.

ArXiv PREPRINT: 1803.07348

PAPER: Frank-Wolfe with Subsampling Oracle in pdf