Performance analysis of greedy algorithms for minimising a maximum mean discrepancy

DOI10.1007/S11222-022-10184-1MaRDI QIDQ2104022zbMATH OpenOpenAlexFDO

Authors Luc Pronzato

Publication date 9 December 2022

Published in Statistics and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.07564

zbMATH Keywords

computer experimentsgreedy algorithmspace-filling designmaximum mean discrepancyquantisationkernel herdingsequential Bayesian quadrature

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08)

Abstract: We analyse the performance of several iterative algorithms for the quantisation of a probability measure $mu$, based on the minimisation of a Maximum Mean Discrepancy (MMD). Our analysis includes kernel herding, greedy MMD minimisation and Sequential Bayesian Quadrature (SBQ). We show that the finite-sample-size approximation error, measured by the MMD, decreases as $1/n$ for SBQ and also for kernel herding and greedy MMD minimisation when using a suitable step-size sequence. The upper bound on the approximation error is slightly better for SBQ, but the other methods are significantly faster, with a computational cost that increases only linearly with the number of points selected. This is illustrated by two numerical examples, with the target measure $mu$ being uniform (a space-filling design application) and with $mu$ a Gaussian mixture. They suggest that the bounds derived in the paper are overly pessimistic, in particular for SBQ. The sources of this pessimism are identified but seem difficult to counter.

Recommendations

• Bayesian quadrature, energy minimization, and space-filling design
• Optimal approximation and quantisation
• New approach to greedy vector quantization
• Sampling based approximation of linear functionals in reproducing kernel Hilbert spaces
• Greedy vector quantization

Cites work

• scientific article; zbMATH DE number 3526459 (Why is no real title available?)
• scientific article; zbMATH DE number 2231192 (Why is no real title available?)
• A generalized discrepancy and quadrature error bound
• An asymptotically optimal gradient algorithm for quadratic optimization with low computational cost
• Approximation Theorems of Mathematical Statistics
• Bayesian quadrature, energy minimization, and space-filling design
• Conditional gradient algorithms with open loop step size rules
• Control functionals for Monte Carlo integration
• Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
• Coordinate descent algorithms
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Design of computer experiments: space filling and beyond
• Design of experiments in nonlinear models. Asymptotic normality, optimality criteria and small-sample properties
• Energy statistics: a class of statistics based on distances
• Equivalence of distance-based and RKHS-based statistics in hypothesis testing
• Finding the nearest point in A polytope
• Foundations of quantization for probability distributions
• Hilbert space embeddings and metrics on probability measures
• Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
• Maximum projection designs for computer experiments
• Measuring sample quality with diffusions
• Minimax and maximin space-filling designs: some properties and methods for construction
• Minimum-energy measures for singular kernels
• On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids
• On energy, discrepancy and group invariant measures on measurable subsets of Euclidean space
• On the positivity and magnitudes of Bayesian quadrature weights
• Probabilistic integration: a role in statistical computation?
• Sequences converging to D-optimal designs of experiments
• Support points
• The Sequential Generation of D-Optimum Experimental Designs

Cited in

(2)

• Sparse solutions of the kernel herding algorithm by improved gradient approximation
• BLUE against OLSE in the location model: energy minimization and asymptotic considerations

Describes a project that uses

Uses Software

• energy

This page was built for publication: Performance analysis of greedy algorithms for minimising a maximum mean discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104022)