  We propose two novel conditional gradient-based methods for solving
structured stochastic convex optimization problems with a large number of
linear constraints. Instances of this template naturally arise from
SDP-relaxations of combinatorial problems, which involve a number of
constraints that is polynomial in the problem dimension. The most important
feature of our framework is that only a subset of the constraints is processed
at each iteration, thus gaining a computational advantage over prior works that
require full passes. Our algorithms rely on variance reduction and smoothing
used in conjunction with conditional gradient steps, and are accompanied by
rigorous convergence guarantees. Preliminary numerical experiments are provided
for illustrating the practical performance of the methods.
