Source-linked AI summary
On the Equivalence between Herding and Conditional Gradient Algorithms
Francis Bach, Simon Lacoste-Julien, Guillaume Obozinski
TL;DR
The paper addresses how to understand and improve herding for mean and integral approximation. It identifies herding with conditional gradient optimization, uses that link to study faster variants, and finds a trade-off between approximation speed and maximum-entropy behavior.
Problem
The paper asks how herding relates to standard optimization and whether faster integral-approximation methods preserve herding’s tendency toward maximum-entropy distributions.
Method
The paper formulates herding as conditional gradient optimization of quadratic moment discrepancy and compares variants through convergence analysis and numerical experiments.
Results
Herding is equivalent to a conditional gradient algorithm; faster variants improve moment approximation, while herding more often approaches the maximum-entropy distribution.
Takeaways & Limitations
Moment approximation and maximum-entropy approximation are not consistently aligned, so herding’s optimization formulation helps clarify its goals and properties.
Takeaways & Limitations
The linear optimization required by herding can be NP-hard for the graphical-model examples considered, motivating local search or convex relaxation.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper reframes herding as a conditional gradient method for minimizing quadratic moment discrepancy, extending convergence analysis and comparing faster variants with herding’s distributional behavior.
- Herding directly generates deterministic pseudo-samples whose empirical moments asymptotically match the data, avoiding parameter estimation and subsequent sampling.
- Herding updates admit both a learning interpretation as fixed-step subgradient ascent and a moment-matching interpretation based on reducing moment discrepancy.
- The paper shows that herding is equivalent to a specific conditional gradient algorithm for estimating the mean and minimizing an explicit cost function.
- The authors extend herding’s convergence results, including a linear rate for the line-search variant in finite dimensions and a negative result for assumptions in infinite dimensions.
- Although faster variants improve mean estimation, their samples are generally no better than herding’s for approximating a high-entropy distribution.
2. Mean estimation
The paper formulates mean estimation in an RKHS using feature maps and weighted points, connecting moment approximation to bounded function-integration error over the marginal polytope.
- The RKHS setup maps each x to a feature vector Φ(x), allowing functions to be represented through inner products and integrals to be approximated through mean elements.
- The analysis assumes uniformly bounded features, with ∥Φ(x)∥⩽R, so the herding updates are well-defined.
- The marginal polytope M is the convex hull of all feature vectors Φ(x), and the paper notes that its feature images are extreme points in the considered cases.
- A weighted empirical distribution uses points x1,...,xn with positive weights summing to one to construct an approximating mean ˆµ.
- Controlling the difference between the target and approximating means controls expectation error for all finite-norm RKHS functions.
3. Related work
The paper connects herding to integral approximation and conditional-gradient optimization, situating its approach among quadrature, quasi-Monte Carlo, and Frank-Wolfe methods.
- Connections: The paper links integral approximation, herding, and convex optimization through a conditional-gradient interpretation of herding.This provides a convex-optimization perspective on the integral-approximation problem.
- Quadrature and cubature: Quadrature formulas approximate integrals using weighted combinations of function values at selected points.The paper studies this same weighted-point approximation problem.
- Quadrature and cubature: Bayes-Hermite quadrature projects the target mean onto an affine hull, while convex-hull replacement yields nonnegative weights.The convex-hull formulation is used in the paper’s experiments.
- Quasi-Monte Carlo: Quasi-Monte Carlo sequences achieve O(1/n), up to logarithmic terms, for bounded-variation functions, compared with O(1/√n) for random sequences.The simulations use a Sobol sequence as a quasi-random baseline.
- Frank-Wolfe algorithms: Frank-Wolfe algorithms optimize a smooth convex function over a compact convex set using gradient-based linear minimization and segment updates.Conditional-gradient iterations move from the current iterate toward a linear minimizer with stepsize ρt.
- Frank-Wolfe algorithms: The minimum-norm-point variant optimizes over the convex hull of previously visited points and can converge finitely on polytopes, at higher polynomial iteration cost.Figure 2 contrasts conditional-gradient variants, including fixed-step and line-search updates.
4. Herding as a Frank-Wolfe algorithm
The paper proves that herding is a conditional-gradient method for minimizing a quadratic moment discrepancy, then analyzes stepsizes, convergence conditions, and computational limits.
- Equivalence: Herding is exactly equivalent to conditional-gradient minimization after the change of variable gt = µ − wt/t.The selected extreme point corresponds to Φ(xt+1), and the standard herding stepsize is ρt = 1/(t + 1).
- Stepsize variants: With general stepsizes, conditional-gradient iterates produce non-uniform weights that still sum to one; traditional herding is the ρt = 1/(t + 1) case.Line search gives another non-uniform-weight variant.
- Equivalent interpretations: The herding interpretation is consistent with subgradient ascent on the zero-temperature objective because decreasing-step subgradient ascent is equivalent to primal conditional gradient.The squared norm reflects the scaling change between gt and wt.
- Convergence analysis: Without further assumptions, both conditional-gradient variants have O(1/t) convergence, and this rate does not improve integral estimation over random sampling.The available theory also cannot distinguish the variants without additional assumptions.
- Convergence analysis: If µ lies in the relative interior of M, line search has linear convergence, while the standard ρt = 1/(t + 1) method has O(1/t^2) convergence.These faster rates require the stated geometric condition on the marginal polytope.
- Convergence assumptions: The relative-interior condition holds under reasonable finite-dimensional conditions but fails for a broad class of infinite-dimensional Mercer-kernel settings.The paper proves the finite-dimensional case and gives a Mercer-kernel argument for failure in infinite dimensions.
- Computational issues: Integral evaluation requires computing kernel expectations, which is possible for some kernel–distribution pairs but not in general.This computational requirement differs from empirical moment matching, which uses an empirical average.
- Computational issues: The linear minimization required by conditional gradient can be NP-hard for the graphical models considered, motivating local or exhaustive search and possible variational relaxations.This oracle computation is a separate practical bottleneck from convergence.
5. Experiments
The experiments compare herding with conditional-gradient variants for mean estimation and examine whether these procedures approach maximum-entropy distributions. Faster mean-estimation methods generally outperform herding on approximation error, while regular herding more often exhibits maximum-entropy behavior.
- Min-norm-point algorithms always perform best in the mean-estimation comparisons.
- Conditional gradient with line search performs slightly worse than regular herding in the infinite-dimensional setting, where both have theoretical rate O(t^-1).
- The extra projection step always significantly improves performance, sometimes allowing random selection with reprojection to outperform regular herding.
- Regular herding empirically achieves the Sobol sequence’s O(t^-2) rate in one Sobolev-space setting, although existing theory does not explain or support this result.
- On graphical models with 100 binary variables, min-norm-point outperforms regular herding and line search, while line search can be slower than the 1/(t + 1)-rule.
- For independent bits, regular herding approaches maximum entropy for random means but not for rational ratios or rational means; line search never converges to it.
- For graphical models with dependent bits, herding consistently estimates the mean vector but does not converge to the maximum-entropy distribution.
6. Conclusion
The paper identifies herding as conditional gradient descent on quadratic moment error and finds a trade-off between efficient moment approximation and maximum-entropy behavior. Regular herding sometimes approaches maximum entropy, whereas faster alternatives can behave more like minimum-entropy procedures.
- Herding generates successive descent directions for a conditional gradient algorithm minimizing quadratic error on the moment vector.
- Other algorithms outperform herding when assessed solely by their ability to approximate the moment vector.
- Regular herding sometimes approaches a maximum-entropy distribution but fails in other non-pathological cases.
- Algorithms that approximate the moment vector more efficiently fail more clearly to approach maximum entropy and show characteristics suggesting entropy minimization.
- The experiments motivate studying whether efficient mean approximation and maximum-entropy approximation are aligned or involve a trade-off.