English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the approximability of general convex sets in $\mathbb{R}^n$ byintersections of halfspaces, where the approximation quality is measured withrespect to the standard Gaussian distribution $N(0,I_n)$ and the complexity ofan approximation is the number of halfspaces used. While a large body ofresearch has considered the approximation of convex sets by intersections ofhalfspaces under distance metrics such as the Lebesgue measure and Hausdorffdistance, prior to our work there has not been a systematic study of convexapproximation under the Gaussian distribution.  We establish a range of upper and lower bounds, both for general convex setsand for specific natural convex sets that are of particular interest. Ourresults demonstrate that the landscape of approximation is intriguinglydifferent under the Gaussian distribution versus previously studied distancemeasures. For example, we show that $2^{\Theta(\sqrt{n})}$ halfspaces are bothnecessary and sufficient to approximate the origin-centered $\ell_2$ ball ofGaussian volume 1/2 to any constant accuracy, and that for $1 \leq p < 2$, theorigin-centered $\ell_p$ ball of Gaussian volume 1/2 can be approximated to anyconstant accuracy as an intersection of $2^{\widetilde{O}(n^{3/4})}$ manyhalfspaces. These bounds are quite different from known approximation resultsunder more commonly studied distance measures.  Our results are proved using techniques from many different areas. Theseinclude classical results on convex polyhedral approximation, Cram\'er-typebounds on large deviations from probability theory, and -- perhaps surprisingly-- a range of topics from computational complexity, including computationallearning theory, unconditional pseudorandomness, and the study of influencesand noise sensitivity in the analysis of Boolean functions.

Gaussian Approximation of Convex Sets by Intersections of Halfspaces