Sparser Kernel Herding with Pairwise Conditional Gradients without Swap Steps

Understand

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).