Gaussian Polytope Approximators

We study the approximability of general convex sets in  by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution and the complexity of an approximation is the number of halfspaces used. While a large body of research has considered the approximation of convex sets by intersections of halfspaces under distance metrics such as the Lebesgue measure and Hausdorff distance, prior to our work there has not been a systematic study of convex approximation under the Gaussian distribution.

We establish a range of upper and lower bounds, both for general convex sets and for specific natural convex sets that are of particular interest. Our results demonstrate that the landscape of approximation is intriguingly different under the Gaussian distribution versus previously studied distance measures. We establish our bounds using techniques from many different areas, including classical results from convex geometry, Cramér-type bounds from probability theory, and—perhaps surprisingly—a range of topics from computational complexity, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions.

Based on joint work with Anindya De and Rocco Servedio. Preprint available here: https://arxiv.org/abs/2311.08575.