Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering

By Simon Lacoste-Julien, Fredrik Lindsten, Francis R. Bach. 2015

87 citations recorded by the source corpus.

Recently, the Frank-Wolfe optimization algorithm was suggested as a procedure to obtain adaptive quadrature rules for integrals of functions in a reproducing kernel Hilbert space (RKHS) with a potentially faster rate of convergence than Monte Carlo integration (and "kernel herding" was shown to be a special case of this procedure). In this paper, we propose to replace the random sampling step in a particle filter by Frank-Wolfe optimization. By optimizing the position of the particles, we can obtain better accuracy than random or quasi-Monte Carlo sampling. In applications where the evaluation of the emission probabilities is expensive (such as in robot localization), the additional computational cost to generate the particles through optimization can be justified. Experiments on standard synthetic examples as well as on a robot localization task indicate indeed an improvement of accuracy over random and quasi-Monte Carlo sampling.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “…et al. 2014; Alayrac et al. 2016; Seguin et al. 2016; Peyre et al. 2017; Miech x k +1 = (1 − γ t ) x k + γ k v k ⊲ Convex update 5: end for et al. 2018; Lacoste-Julien et al. 2015b; Courty et al. 2016; Paty et al. 2019; Luise et al. 2019]; however, many open questions remain in designing such…”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “Lacoste-Julien et al. (2015) takes this interpretation and proposes the Frank-Wolfe optimization algorithm for particle filtering.”
Consistent Kernel Mean Estimation for Functions of Random Variables (2016, methodology): “Various approaches, such as kernel herding (Chen et al., 2010; Lacoste-Julien et al., 2015), attempt to produce a better KME estimator by actively generating pseudo-samples that are not i.i.d. from the underlying distribution.”
Convergence guarantees for kernel-based quadrature rules in misspecified settings (2016, background): “Because of this nice property, kernel quadratures have been studied extensively in recent years [7, 3, 5, 2, 17] and have started to find applications in machine learning and statistics [23, 14, 12, 6].”
Control functionals for Monte Carlo integration (2014, background): “n 100 separate occasions, based on both (i) and (ii); standard errors are shown as dashed lines. Results indicate that the careful selection of design points can signicantly reduce estimation error. Lacoste-Julien et al., 2015). However, as in the previous section, open problems with these methods i”
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm (2019, methodology): “2 is that the support of the candidate barycenter is updated incrementally by adding at most one point at each iteration, a procedure similar in flavor to the kernel herding strategy in [5, 31] and conditional gradient for sparse inverse problem [8, 9].”
Measuring Sample Quality with Diffusions (2016, methodology): “sampling from P , Quasi-Monte Carlo (QMC) sampling using a deterministic quasirandom number generator, Frank-Wolfe (FW) kernel herding [13, 3], and fully-corrective Frank-Wolfe (FCFW) kernel herding [50].”
Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees (2015, methodology): “To facilitate the experiments in this paper we followed [1, 2, 11, 18] and employed an exponentiatedquadratic (EQ) kernel k(x, x′) := λ(2) exp(−1/2σ2‖x − x‖(2)2).”
Control Functionals for Quasi-Monte Carlo Integration (2015, background): “Challenging integration problems are common in contemporary statistics, for example when computing expectations, marginal probability densities or normalising constants, and QMC methods are therefore gaining importance in statistical applications [12, 17, 35].”