On the Equivalence between Herding and Conditional Gradient Algorithms

By Francis R. Bach, Simon Lacoste-Julien, Guillaume Obozinski. 2012

179 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, 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 Statistical and Nonlinear Physics

In Optimization & Training

Citations in the corpus

Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, methodology): “We build on the optimization view from Bach et al. (2012) of kernel herding (Chen et al., 2010) to approximate the integrals appearing in the Bayesian ﬁltering recursions.”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “To solve the dual structural SVM problem, in this paper we consider the Frank-Wolfe (1956) algorithm, which has seen a recent surge of interest in machine learning and signal processing (Mangasarian, 1995; Clarkson, 2010; Jaggi, 2011; 2013; Bach et al., 2012), including in the context of binary SVMs”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “Bach et al. (2012) also pointed out that the fast convergence rate is not guaranteed in an infinite dimensional Hilbert space.”
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].”
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “If these constraints are required, kernel herding (Chen et al., 2010; Bach et al., 2012) provides a novel way to select a sequence of points based on the conditional gradient algorithm, but with currently no convergence guarantees improving over O (1 / √ n ) for inﬁnite-dimensional spaces.”
Filtering with State-Observation Examples via Kernel Monte Carlo Filter (2013, methodology): “he distance between m P and the empirical kernel mean m P = 1 ‘ P ‘ i=1 k(;x i). It can be shown that the error E ‘of (9) decreases at a rate at least O(‘ 1=2) under the assumption that kis bounded (Bach et al., 2012). In other words, the herding samples x 1;:::;x ‘provide a convergent approximation”
Optimally-Weighted Herding is Bayesian Quadrature (2012, background): “However, as pointed out by Bach et al. (2012), this fast convergence is not guaranteed in inﬁnite dimensional Hilbert spaces, such as the RKHS corresponding to the Gaussian kernel.”
Introduction to Online Convex Optimization (2016, methodology): “Due to the applicability of the FW algorithm to large-scale constrained problems, it has been a method of choice in recent machine learning applications, to name a few: [61, 69, 60, 39, 50, 58, 98, 16, 104, 46, 47, 18].”
Measuring Sample Quality with Stein's Method (2015, neutral): “As witnessed also in other metrics [31], the herding rate of n−0.”
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): “Below we describe a solution to the problem of computing integrals recently proposed by [2], based on the FW algorithm, that restricts attention to the (bounded) convex hull of {Φ(xi)}i=1.”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, background): “…, 1996), sparse recovery (Mallat & Zhang, 1993), and many learning tasks, where e.g. boosting (Adaboost ), support vector machines (Gärtner & Jaggi, 2009; Clarkson, 2010; Ouyang & Gray, 2010), and density estimation (Li & Barron, 2000; Bach et al., 2012) turn out to be such problem instances.”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, unknown): “, [1–3,7,17–19,23,32,33]) mainly for the following reasons.”
Interpreting Black Box Predictions using Fisher Kernels (2018, methodology): “[Left] 1200 samples on U[1,2] ⇥ U[1,2] with two labels - Green and Red as illustrated.”
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm (2019, methodology): “Instead, we adopt a Frank-Wolfe (FW) procedure to populate the support by incrementally adding new points and updating their weights at each iteration, similarly to kernel herding strategies [5].”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “These fundamental properties are among the main features that contribute to the recent revival and extensions of the Frank-Wolfe algorithm (Clarkson, 2010; Jaggi, 2011) used for instance in large-scale structured prediction (Bojanowski et al., 2014, 2015; Alayrac et al., 2016; Seguin et al., 2016; M”
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018, result): “Our aim is the closest in spirit to Berlinet and Thomas-Agnan [2004], who collected classic results on the use of RKHSs in statistics and probability; these include the results by Kolmogorov [1941], Parzen [1961], Matheron [1962], Kimeldorf and Wahba [1970], Larkin [1972], who made the earliest cont”