# Sparse solutions of the kernel herding algorithm by improved gradient approximation

arXiv: https://arxiv.org/abs/2105.07900 · HTML: https://mlsanity.com/paper/2105.07900/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 50 references that are in the map.
- First posted on arXiv 17 May 2021.

## Builds on (most cited first, 12 of 12)

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Probabilistic Integration: A Role in Statistical Computation?](https://mlsanity.com/paper/1512.00933/) (2015)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings](https://mlsanity.com/paper/1709.00147/) (2017)
- [Optimal quantisation of probability measures using maximum mean discrepancy](https://mlsanity.com/paper/2010.07064/) (2020)
- [Boosting Frank-Wolfe by Chasing Gradients](https://mlsanity.com/paper/2003.06369/) (2020)
- [On the Sampling Problem for Kernel Quadrature](https://mlsanity.com/paper/1706.03369/) (2017)
- [Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy](https://mlsanity.com/paper/2101.07564/) (2021)
- [Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees](https://mlsanity.com/paper/1705.11041/) (2017)

## Built on by (most cited first, 2 of 2)

- [Bayesian Quadrature](https://mlsanity.com/paper/2602.16218/) (2026)
- [Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature](https://mlsanity.com/paper/2605.05705/) (2026)

## Abstract (arXiv)

The kernel herding algorithm is used to construct quadrature rules in a reproducing kernel Hilbert space (RKHS). While the computational efficiency of the algorithm and stability of the output quadrature formulas are advantages of this method, the convergence speed of the integration error for a given number of nodes is slow compared to that of other quadrature methods. In this paper, we propose a modified kernel herding algorithm whose framework was introduced in a previous study and aim to obtain sparser solutions while preserving the advantages of standard kernel herding. In the proposed algorithm, the negative gradient is approximated by several vertex directions, and the current solution is updated by moving in the approximate descent direction in each iteration. We show that the convergence speed of the integration error is directly determined by the cosine of the angle between the negative gradient and approximate gradient. Based on this, we propose new gradient approximation algorithms and analyze them theoretically, including through convergence analysis. In numerical experiments, we confirm the effectiveness of the proposed algorithms in terms of sparsity of nodes and computational efficiency. Moreover, we provide a new theoretical analysis of the kernel quadrature rules with fully-corrective weights, which realizes faster convergence speeds than those of previous studies.