On the Equivalence between Herding and Conditional Gradient Algorithms

Abstract

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.

Cited by in corpus (28)

• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Measuring Sample Quality with Stein's Method
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
• Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees
• Optimally-Weighted Herding is Bayesian Quadrature
• Optimally-Weighted Herding is Bayesian Quadrature
• Convergence guarantees for kernel-based quadrature rules in misspecified settings
• Conditional Accelerated Lazy Stochastic Gradient Descent
• Splitting Steepest Descent for Growing Neural Architectures
• Projection-Free Optimization on Uniformly Convex Sets
• Kernel Recursive ABC: Point Estimation with Intractable Likelihood
• Learning with Fenchel-Young Losses
• Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings
• Positively Weighted Kernel Quadrature via Subsampling
• A Kernel Mean Embedding Approach to Reducing Conservativeness in Stochastic Programming and Control
• Predicting the Future Behavior of a Time-Varying Probability Distribution
• Worst-Case Risk Quantification under Distributional Ambiguity using Kernel Mean Embedding in Moment Problem
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
• A Statistical Perspective on Coreset Density Estimation
• Kernel quadrature by applying a point-wise gradient descent method to discrete energies
• Herded Gibbs Sampling
• Filtering with State-Observation Examples via Kernel Monte Carlo Filter
• Herding Generalizes Diverse M -Best Solutions
• Bayesian posterior approximation via greedy particle optimization
• RC Circuits based Distributed Conditional Gradient Method