On the Equivalence between Herding and Conditional Gradient Algorithms
This work provides theoretical insights into herding's optimization properties, benefiting researchers in machine learning and statistics, but it is incremental as it builds on existing algorithms.
The paper demonstrates that the herding procedure is equivalent to a conditional gradient algorithm for minimizing quadratic moment discrepancy, enabling the use of convex optimization convergence results and faster alternatives for integral approximation in RKHS. Numerical simulations show that while variants improve integral approximation, original herding more often approaches the maximum entropy distribution, revealing its learning bias.
We show that the herding procedure of Welling (2009) takes exactly the form of a standard convex optimization algorithm--namely a conditional gradient algorithm minimizing a quadratic moment discrepancy. This link enables us to invoke convergence results from convex optimization and to consider faster alternatives for the task of approximating integrals in a reproducing kernel Hilbert space. We study the behavior of the different variants through numerical simulations. The experiments indicate that while we can improve over herding on the task of approximating integrals, the original herding algorithm tends to approach more often the maximum entropy distribution, shedding more light on the learning bias behind herding.