  The Pairwise Conditional Gradients (PCG) algorithm is a powerful extension of
the Frank-Wolfe algorithm leading to particularly sparse solutions, which makes
PCG very appealing for problems such as sparse signal recovery, sparse
regression, and kernel herding. Unfortunately, PCG exhibits so-called swap
steps that might not provide sufficient primal progress. The number of these
bad steps is bounded by a function in the dimension and as such known
guarantees do not generalize to the infinite-dimensional case, which would be
needed for kernel herding. We propose a new variant of PCG, the so-called
Blended Pairwise Conditional Gradients (BPCG). This new algorithm does not
exhibit any swap steps, is very easy to implement, and does not require any
internal gradient alignment procedures. The convergence rate of BPCG is
basically that of PCG if no drop steps would occur and as such is no worse than
PCG but improves and provides new rates in many cases. Moreover, we observe in
the numerical experiments that BPCG's solutions are much sparser than those of
PCG. We apply BPCG to the kernel herding setting, where we derive nice
quadrature rules and provide numerical results demonstrating the performance of
our method.
