  In this paper, we show that the Away-step Stochastic Frank-Wolfe Algorithm
(ASFW) and Pairwise Stochastic Frank-Wolfe algorithm (PSFW) converge linearly
in expectation. We also show that if an algorithm convergences linearly in
expectation then it converges linearly almost surely. In order to prove these
results, we develop a novel proof technique based on concepts of empirical
processes and concentration inequalities. Such a technique has rarely been used
to derive the convergence rates of stochastic optimization algorithms. In
large-scale numerical experiments, ASFW and PSFW perform as well as or better
than their stochastic competitors in actual CPU time.
