  We propose a semi-stochastic Frank-Wolfe algorithm with away-steps for
regularized empirical risk minimization and extend it to problems with
block-coordinate structure. Our algorithms use adaptive step-size and we show
that they converge linearly in expectation. The proposed algorithms can be
applied to many important problems in statistics and machine learning including
regularized generalized linear models, support vector machines and many others.
In preliminary numerical tests on structural SVM and graph-guided fused LASSO,
our algorithms outperform other competing algorithms in both iteration cost and
total number of data passes.
