  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
\emph{subset} of the original domain. The first algorithm that we propose is a
randomized variant of the original FW algorithm and achieves a
$\mathcal{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 $\ell_1$ and latent group lasso penalties.
