  A new algorithm is proposed which accelerates the mini-batch k-means
algorithm of Sculley (2010) by using the distance bounding approach of Elkan
(2003). We argue that, when incorporating distance bounds into a mini-batch
algorithm, already used data should preferentially be reused. To this end we
propose using nested mini-batches, whereby data in a mini-batch at iteration t
is automatically reused at iteration t+1.
  Using nested mini-batches presents two difficulties. The first is that
unbalanced use of data can bias estimates, which we resolve by ensuring that
each data sample contributes exactly once to centroids. The second is in
choosing mini-batch sizes, which we address by balancing premature fine-tuning
of centroids with redundancy induced slow-down. Experiments show that the
resulting nmbatch algorithm is very effective, often arriving within 1% of the
empirical minimum 100 times earlier than the standard mini-batch algorithm.
