Carath\'eodory Sampling for Stochastic Gradient Descent
  Many problems require to optimize empirical risk functions over large data
sets. Gradient descent methods that calculate the full gradient in every
descent step do not scale to such datasets. Various flavours of Stochastic
Gradient Descent (SGD) replace the expensive summation that computes the full
gradient by approximating it with a small sum over a randomly selected
subsample of the data set that in turn suffers from a high variance. We present
a different approach that is inspired by classical results of Tchakaloff and
Carath\'eodory about measure reduction. These results allow to replace an
empirical measure with another, carefully constructed probability measure that
has a much smaller support, but can preserve certain statistics such as the
expected gradient. To turn this into scalable algorithms we firstly, adaptively
select the descent steps where the measure reduction is carried out; secondly,
we combine this with Block Coordinate Descent so that measure reduction can be
done very cheaply. This makes the resulting methods scalable to
high-dimensional spaces. Finally, we provide an experimental validation and
comparison.
