Random convex hulls and kernel quadrature

Thesis

Discretization of probability measures is ubiquitous in the field of applied mathematics, from classical numerical integration to data compression and algorithmic acceleration in machine learning. In this thesis, starting from generalized Tchakaloff-type cubature, we investigate random convex hulls and kernel quadrature.

In the first two chapters after the introduction, we investigate the probability that a given vector θ is contained in the convex hull of independent copies of a random vector X. After deriving a sharp inequality that describes the relationship between the said probability and Tukey’s halfspace depth, we explore the case θ = E[X] by using moments of X and further the case when X enjoys some additional structure, which are of primary interest from the context of cubature.

In the subsequent two chapters, we study kernel quadrature, which is numerical integration where integrands live in a reproducing kernel Hilbert space. By explicitly exploiting the spectral properties of the associated integral operator, we derive convex kernel quadrature with theoretical guarantees described by its eigenvalue decay. We further derive practical variants of the proposed algorithm and discuss their theoretical and computational aspects.

Finally, we briefly discuss the applications and future work of the thesis, including Bayesian numerical methods, in the concluding chapter.

Authors: Hayakawa, S

• DOI: 10.5287/ora-bpm8yvp0q
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: hypercontractivity; nyström approximation; random convex hulls; kernel quadrature; cubature
• Subjects: Machine learning; Mathematics; Probabilities; Numerical analysis; Combinatorial probabilities