# Gaussian Approximation of Convex Sets
by Intersections of Halfspaces

Anindya De University of Pennsylvania. Email<EMAIL_ADDRESS>Shivam
Nadimpalli Columbia University. Email<EMAIL_ADDRESS>Rocco A. Servedio
Columbia University. Email<EMAIL_ADDRESS>
###### Abstract

We study the approximability of general convex sets in $\mathbb{R}^{n}$ by
intersections of halfspaces, where the approximation quality is measured with
respect to the _standard Gaussian distribution_ $N(0,I_{n})$ 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. For example, we show that $2^{\Theta(\sqrt{n})}$ halfspaces are both
necessary and sufficient to approximate the origin-centered $\ell_{2}$ ball of
Gaussian volume 1/2 to any constant accuracy, and that for $1\leq p<2$, the
origin-centered $\ell_{p}$ ball of Gaussian volume 1/2 can be approximated to
any constant accuracy as an intersection of $2^{\tilde{O}(n^{3/4})}$ many
halfspaces. These bounds are quite different from known approximation results
under more commonly studied distance measures.

Our results are proved using techniques from many different areas. These
include classical results on convex polyhedral approximation, Cramér-type
bounds on large deviations 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.

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation
  2. 2 Overview of Results and Techniques
    1. 2.1 Overview of Positive Results
    2. 2.2 Overview of Lower Bounds
    3. 2.3 Discussion
  3. 3 Preliminaries
    1. 3.1 Basic Notation and Terminology
    2. 3.2 The Gaussian and Chi-Squared Distributions
    3. 3.3 Bounds on Gaussian Surface Area
    4. 3.4 Distance Metrics Between Sets
  4. I Upper Bounds
    1. 4 Generic Upper Bounds
      1. 4.1 Warmup: Universal Approximation via Hausdorff Distance Approximation
      2. 4.2 A Relative-Error Sharpening of Theorem 19
    2. 5 Improved Approximation for the $\ell_{2}$ Ball
    3. 6 Improved Approximations for $\ell_{p}$ Balls for $p\in[1,2)$
      1. 6.1 Cramér-Type Large Deviations Bounds and General Setup
      2. 6.2 Proof of Theorem 29
  5. II Lower Bounds
    1. 7 Non-Explicit Average-Case Lower Bounds
    2. 8 Average-Case Lower Bounds via Gaussian Noise Sensitivity
      1. 8.1 Random Zooms, Hypervariance, and Local Hyperconcentration
      2. 8.2 PTFs and Intersections of Halfspaces Collapse Under Random Zooms
      3. 8.3 Gaussian Noise Stability and Expected Variance After Random Zooms
      4. 8.4 Proof of Theorem 49
      5. 8.5 Existence of Convex Sets with High Gaussian Noise Sensitivity at Low Noise
    3. 9 Lower Bounds for the $\ell_{1}$ and $\ell_{2}$ Balls (and More) via Convex Influences
      1. 9.1 Convex Influences
      2. 9.2 Bounds on the Convex Influence of Polytopes
      3. 9.3 Lower Bounds for Approximating Convex Sets with Maximal Influence
    4. A Hermite Analysis over $N(0,I_{n})$

###  1 Introduction

A long line of mathematical research has investigated _convex polyhedral
approximation of convex bodies_ , i.e. the broad question of how to best
approximate general convex bodies using intersections of halfspaces (or
equivalently, convex hulls of finite point sets). Research on questions of
this sort dates back at least to the first half of the twentieth century, see
for example the early works of Sas [Sas39], Fejes Tóth [T4́8] and Macbeath
[Mac51], among others. Contemporary motivation for the study of polyhedral
approximation of convex bodies arises from many areas including discrete and
computational geometry, geometric convexity, the study of finite-dimensional
normed spaces, and optimization. Given this breadth of connections, it is not
surprising that the existing body of work on the subject is vast, as witnessed
by the hundreds of references that appear in multiple surveys (including the
1983 [Gru83] and 1993 [Gru93] surveys of Gruber and the 2008 survey of
Bronstein [Bro08]) on approximation of convex bodies by polyhedra.

In the polyhedral approximation literature to date, a number of different
distance notions have been used to measure the accuracy of convex polyhedral
approximations of convex sets. These include the Hausdorff distance, the
Nikodym metric (volume of the symmetric difference), the Banach-Mazur
distance, distances generated by various $L_{p}$ metrics, and more. (See
[Bro08] for descriptions of each of these metrics and for an extensive
overview of approximability results under each of those distance measures.)

This paper adopts a new perspective, by considering approximation of convex
bodies in $\mathbb{R}^{n}$ using the _(standard) Gaussian volume of the
symmetric difference_ as the distance measure. We refer to this distance
measure simply as the _Gaussian distance_. This is a natural and well-studied
distance measure in theoretical computer science, as witnessed by the many
works that have considered learning, testing, derandomization, and other
problems using it (see e.g. [KOS08, Vem10, MORS10, Kan11, Kan12, Kan14a, KK14,
KNOW14, Kan15, CDS19, DMN19, DKP+21, OSTK21, DMN21, HSSV22, DNS23] and
references therein). Given this body of work, it is perhaps surprising that
Gaussian distance does not appear to have been previously studied in a
systematic way for the convex polyhedral approximation problem.

Let us make our notion of approximation precise:

######  Definition 1.

Given (measurable) sets $K,L\subseteq\mathbb{R}^{n}$, we define the _Gaussian
distance_ between $K$ and $L$ to be

$\mathrm{dist}_{\mathrm{G}}(K,L)\mathrel{\mathop{\mathchar
58\relax}}=\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\boldsymbol{x}\in K\,\triangle\,L\right]}$

where $N(0,I_{n})$ denotes the $n$-dimensional standard Gaussian distribution.

We consider approximators which are intersections of finitely many
$n$-dimensional halfspaces, and we measure the complexity of such an
approximator by the number of halfspaces (facets) that it contains; we refer
to this as its _facet complexity_. Thus, we are concerned with the following
broad question:

> Given a convex set $K$ in $\mathbb{R}^{n}$ and a value $0<\varepsilon<1/2$,
> what is the minimum facet complexity of an intersection of halfspaces $L$
> such that $\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon$?

####  1.1 Motivation

The broad approximation question stated above arises naturally in the context
of contemporary theoretical computer science. As alluded to earlier, an
increasing number of results across different areas of TCS involve convex sets
and the Gaussian distance; taking the next step on various natural problems in
these areas would seem to require an understanding of how well intersections
of halfspaces can approximate convex sets in $\mathbb{R}^{n}$. We give two
specific examples below:

  * •

Testing Convex Sets: A number of researchers have considered the property
testing problem of efficiently determining whether an unknown set
$K\subseteq\mathbb{R}^{n}$ is convex versus far from convex [RV05, CFSS17,
BBB20, BB20, BBH23]. The Gaussian distance provides a clean mathematical
framework for this problem, and one in which a natural analogy emerges between
the well-studied problem of monotonicity testing over the Boolean hypercube
and convexity testing [CDN+23]. Understanding how convex sets can be
approximated by “simpler objects” under the Gaussian distance seems likely to
be helpful in developing algorithms for testing convexity. (In support of this
thesis, we recall that the study of approximating linear threshold functions
by “simpler objects” [Ser07] yielded insights and technical ingredients,
namely the notion of the “critical index,” that played an essential role in
the development of efficient algorithms for testing linear threshold functions
[MORS10].) We also recall that several papers have given testing algorithms
for single halfspaces [MORS10] and intersections of $k$ halfspaces [DMN19,
DMN21] over $\mathbb{R}^{n}$ under the Gaussian distance; combining these
results with results about approximating general convex sets by intersections
of halfspaces offers a potential avenue to developing testers for general
convex sets.

  * •

Properly Learning Convex Sets: It has long been known [BT96] that monotone
Boolean functions over $\\{-1,1\\}^{n}$ can be learned to any constant
accuracy under the uniform distribution in time $2^{\tilde{O}(\sqrt{n})}$, via
the “low-degree” algorithm based on the Fourier decomposition. Similarly, it
has been known for some time [KOS08] that convex sets can be learned to any
constant accuracy under the Gaussian distance, via a “Hermite polynomial”
variant of the low-degree algorithm. However, neither the algorithms of [BT96]
nor [KOS08] are _proper_ : in the monotone case the output hypothesis of the
learning algorithm is not a monotone function, and in the convex setting the
output hypothesis is not a convex set. Exciting recent work [LRV22] has given
a $2^{\tilde{O}(\sqrt{n})}$-time uniform-distribution learning algorithm for
monotone Boolean functions over $\\{-1,1\\}^{n}$ that _is_ proper (even in the
demanding _agnostic learning_ model, see [LV23]); given this, it is a natural
goal to seek a $2^{\tilde{O}(\sqrt{n})}$-time proper learning algorithm for
convex sets under the Gaussian distance. What would the output hypothesis of
such a hoped-for proper learning algorithm look like? It seems quite plausible
that it would be an intersection of halfspaces; this begs the question of
understanding the capabilities and limitations of intersections of halfspaces
as approximators for general convex sets in $\mathbb{R}^{n}$.

We further note that intersections of halfspaces have been intensively studied
in many branches of “concrete complexity theory;” indeed, many of the TCS
results alluded to earlier that involve Gaussian distance are more
specifically about intersections of halfspaces, e.g. [KOS08, Vem10, CDS19,
DMN19, DKP+21, DMN21, HSSV22].

Finally, we note that the suite of tools which turn out to be relevant in our
study link our investigations closely to theoretical computer science. Perhaps
unexpectedly, we will see that there are close connections between the study
of facet complexity of polyhedral convex approximators and a number of
fundamental ingredients and results (such as noise sensitivity, random
restrictions, influence of variables/directions, various extremal
constructions, etc.) in the _analysis of Boolean functions_ over the discrete
domain $\\{-1,1\\}^{n}$. From this perspective, our study can be seen as a
continuation of the broad theme of exploring the emerging analogy between
convex sets in $\mathbb{R}^{n}$ under the Gaussian distribution and monotone
Boolean functions over $\\{-1,1\\}^{n}$ under the uniform distribution (see
e.g. [DS21, DNS21b, DNS22, HSSV22]).

Before turning to an overview of our results and techniques, let us fix some
convenient notation and terminology:

######  Notation 2.

If $L\subseteq\mathbb{R}^{n}$ is an intersection of $N$ halfspaces, then as
stated earlier we say that the _facet complexity_ of $L$ is $N$. Given a
convex set $K\subseteq\mathbb{R}^{n}$ and a value $0\leq\varepsilon<1/2$, we
write $\mathrm{FC}(K,\varepsilon)$ to denote the minimum value $N$ such that
there is a convex set $L$ that is an intersection $N$ halfspaces satisfying
$\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon.$

###  2 Overview of Results and Techniques

Convex Set $K\subseteq\mathbb{R}^{n}$ | $\varepsilon$ | Upper Bound | Lower Bound
---|---|---|---
Arbitrary $K$ with $\mathrm{Vol}(K)=1-\delta$ | $c$ |  | $\frac{1}{\delta}\cdot\left(n\log{\left(\frac{1}{\delta}\right)}\right)^{O(n)}$
---
(Theorem 20)
—
$K=\ell_{2}$-ball with $\mathrm{Vol}(K)=1/2$ | $c$ |  | $2^{O(\sqrt{n})}$
---
(Theorem 27)
| $2^{\Omega(\sqrt{n})}$
---
(Theorem 70)
$K=\ell_{1}$-ball with $\mathrm{Vol}(K)=1/2$ | $c$ |  | $2^{O(n^{3/4})}$
---
(Theorem 29)
| $2^{\Omega(\sqrt{n})}$
---
(Theorem 70)
Non-explicit $K$ |  |  $\frac{1}{2}-\tau$, for
---
$\tau=\omega(n^{-1/2}\log n)$
— |  | $2^{\Omega(\tau\cdot\sqrt{n})}$
---
(Theorem 44)
$K$ s.t. $\mathbf{GNS}_{n^{-c}}(K)\geq\frac{1}{2}-n^{-c}$ | ${\frac{1}{2}-n^{-c}}$ |  — |  | $2^{n^{\Omega(1)}}$
---
(Theorem 49)
Table 1: A summary of some of our bounds on $\mathrm{FC}(K,\varepsilon)$ (see
2) for convex sets $K\subseteq\mathbb{R}^{n}$, where $c$ is any sufficiently
small absolute constant.

A partial summary of some of our main results is presented above in Table 1.

####  2.1 Overview of Positive Results

We start with our positive results on approximability of convex sets under the
Gaussian distance by intersections of halfspaces.

###### Universal Approximation via Hausdorff Distance Approximation.

As a warmup, we begin in Section 4.1 by giving a fairly simple “universal
approximation” result that upper bounds $\mathrm{FC}(K,\varepsilon)$ for any
convex set $K\subseteq\mathbb{R}^{n}$. The key observation (implicit in the
proof of Theorem 19) is that for any convex set $K$, if $L$ is an intersection
of halfspaces which is a high-accuracy _outer_ 111Recall that $L$ is an
_outer_ (respectively _inner_) approximator to $K$ if $K\subseteq L$
(respectively $L\subseteq K$). approximator of $K$ under the Hausdorff
distance measure, then $L$ is also a (slightly lower accuracy)
$\mathrm{dist}_{\mathrm{G}}$-approximator for $K$. (Recall that the Hausdorff
distance between two sets $S,T\subseteq\mathbb{R}^{n}$ is

$\max{\left\\{\sup_{s\in S}\|s-T\|,\sup_{t\in
S}\|t-S\|\right\\}}\quad\text{where}~{}\|x-Y\|=\inf_{y\in Y}\|x-y\|$

and $\|x-y\|$ is the Euclidean distance between $x$ and $y$.) This is easy to
establish by simply integrating Keith Ball’s universal $O(n^{1/4})$ upper
bound [Bal93] on the _Gaussian surface area_ of any convex set (see Theorem
16), using the fact that for any $t>0$ and any convex set $K$, the
“$t$-enlargement” $K_{t}$ of $K$ is also a convex set (see the proof of
Theorem 19).

Combining the above observation with standard Gaussian tail bounds and
classical upper bounds on the facet complexity of an outer Hausdorff
approximator for any convex body with bounded radius, we obtain the following:

######  Theorem 3 (Informal version of Theorem 19).

For any convex set $K$ and any $\varepsilon>0$, we have
$\mathrm{FC}(K,\varepsilon)\leq(n/\varepsilon)^{O(n)}.$

###### A “Relative-Error” Universal Approximation Sharpening of Theorem 3.

Suppose that $K\subseteq\mathbb{R}^{n}$ is a convex set whose Gaussian volume
is very large, i.e. $1-\delta$ where $\delta$ is very small. In this situation
the trivial approximator which is all of $\mathbb{R}^{n}$ already has
$\mathrm{dist}_{\mathrm{G}}(K,\mathbb{R}^{n})=\delta$, so a natural goal for
approximation is to achieve small error _relative to_ the $\delta$ amount of
mass which lies outside of $K$, i.e. to construct an intersection of
halfspaces $L$ for which

$\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon\delta.$

While Theorem 3 shows that $(n/(\varepsilon\delta))^{O(n)}$ halfspaces suffice
for this, in Section 4.2 we give a stronger result which has a significantly
improved dependence on $\delta$:

######  Theorem 4 (Informal version of Theorem 20).

Let $0<\varepsilon,\delta<1$ and let $K\subsetneq\mathbb{R}^{n}$ be a convex
set with $\mathrm{Vol}(K)=1-\delta.$ Then

$\mathrm{FC}(K,\varepsilon\delta)\leq\frac{1}{\delta}\cdot{\left(\frac{n}{\varepsilon}\log{\left(\frac{1}{\delta}\right)}\right)}^{O(n)}.$

(We remark that the strengthening which Theorem 20 achieves over Theorem 19
will be crucial for the construction of our $\ell_{p}$ ball approximators,
discussed below.)

We briefly explain the main idea underlying the construction of the
approximator of Theorem 20. First, we recall a basic property of the
$N(0,I_{n})$ distribution, which is that along any ray
$\\{tv\mathrel{\mathop{\mathchar 58\relax}}t\geq 0\\}$ from the origin in
$\mathbb{R}^{n}$, the distribution of Gaussian mass along that ray follows the
chi-distribution (see Section 3.2). Since $\mathrm{Vol}(K)=1-\delta$, this
means that the “amount of chi-distribution mass” which is “lopped off” by $K$
along direction $v$, averaged over all directions $v$, is $\delta$. The high-
level idea of our construction of the approximator $L$ is to place tangent
hyperplanes on the boundary of $K$ in such a way as to “lop off” at least a
$(1-\varepsilon)$-fraction of the total $\delta$ amount of Gaussian mass that
lies outside the set $K$. We do this via an analysis that proceeds direction
by direction: We can ignore directions in which $K$ “lops off” only a very
small amount (less than $\varepsilon\delta/4$, say) of the chi-distribution’s
mass. For the other directions, we use a bucketing scheme, a suitable net
construction for the points in each bucket, and a mixture of careful geometric
arguments and tail bounds to argue that not too many halfspaces are required
to adequately handle all of the other directions.

###### Sub-Exponential Approximation for Specific Convex Sets.

Going beyond the universal approximation results mentioned above, it is
natural to wonder whether improved approximation bounds can be obtained for
specific interesting convex sets. Perhaps the two most natural convex sets to
consider in this context are the $\ell_{1}$ and $\ell_{2}$ balls of Gaussian
volume $1/2$, which we briefly discuss below.222It is also natural to wonder
about the $\ell_{\infty}$ ball, but the $\ell_{\infty}$ ball
${\left\\{x\in\mathbb{R}^{n}\ \mathrel{\mathop{\mathchar 58\relax}}\
\|x\|_{\infty}\leq r\right\\}}$ is an intersection of $2n$ halfspaces $-r\leq
x_{i}\leq r,i\in[n]$.

The $\ell_{1}$ ball of Gaussian volume $1/2$, also known as the
“spectrahedron” or “cross-polytope,” is the convex set

${\left\\{x\in\mathbb{R}^{n}\ \mathrel{\mathop{\mathchar
58\relax}}\|x\|_{1}\leq cn\right\\}},$

where $c=\sqrt{2/\pi}\pm o_{n}(1)$ (this is an easy consequence of the Berry-
Esseen theorem). This set is an intersection of exactly $2^{n}$ halfspaces,
namely

$b_{1}x_{1}+\cdots+b_{n}x_{n}\leq cn\text{~{}for
all~{}}(b_{1},\dots,b_{n})\in\\{-1,1\\}^{n},$

and it is natural to wonder whether this set can be approximated as an
intersection of significantly fewer than $2^{n}$ halfspaces. (As we will
explain later, it is slightly more convenient for us to work with a slight
rescaling of this ball, namely the set

$B_{1}\mathrel{\mathop{\mathchar 58\relax}}=\\{x\in\mathbb{R}^{n}\
\mathrel{\mathop{\mathchar 58\relax}}\
\|x\|_{1}\leq\sqrt{{\frac{2}{\pi}}}n\\},$

which can easily be shown to have $\mathrm{Vol}(B_{1})=1/2\pm o_{n}(1).$)

The $\ell_{2}$ ball of Gaussian volume $1/2$ is simply the Euclidean ball

${\left\\{x\in\mathbb{R}^{n}\ \mathrel{\mathop{\mathchar
58\relax}}\|x\|^{2}\leq\text{median}(\chi^{2}(n))\right\\}}.$

(Of course, writing this set _exactly_ as an intersection of halfspaces
requires infinitely many halfspaces.) Using well-known bounds on the chi-
squared distribution we have that the Euclidean ball of radius ${\sqrt{n}}$,
which we denote $B(\sqrt{n})$, has Gaussian volume $1/2+o_{n}(1)$; it will be
slightly more convenient for us to use this as the $\ell_{2}$ ball that we
seek to approximate.

###### A $2^{O(\sqrt{n})}$-Facet Approximator for the $\ell_{2}$ Ball.

For several standard distance measures, including the Hausdorff distance and
the symmetric-difference measure, the $\ell_{2}$ ball is the “hardest case”
for approximation by intersections of halfspaces, matching or essentially
matching known upper bounds for universal approximation. For example, it is
known [Bro08] that any intersection of halfspaces which is an
$\varepsilon$-approximator to $B(\sqrt{n})$ in Hausdorff distance must have
facet complexity $\Omega((\sqrt{n}/\varepsilon)^{(n-1)/2})$, matching the
universal approximation upper bound for Hausdorff distance to within a
constant factor [AdFM12]. For the symmetric-difference measure, Ludwig, Schütt
and Werner [LSW06] showed that if $L$ is an intersection of $M$ halfspaces for
which

${\frac{\mathrm{Leb}(L\ \triangle\
B(\sqrt{n}))}{\mathrm{Leb}(B(\sqrt{n}))}}\leq c$

(here $\mathrm{Leb}$ denotes volume under the standard Lebesgue measure),
where $c>0$ is some absolute constant, then $M$ must be at least
$2^{\Omega(n)}$.

In contrast, for the Gaussian distance we are able to exploit the rotational
symmetry of the standard Gaussian distribution and tail bounds on the chi-
distribution to get an approximation of the $\ell_{2}$ ball which uses much
fewer than $2^{n}$ facets, and hence is much better than the universal
approximation upper bounds given by Theorem 3 or Theorem 4. For any constant
$\varepsilon$, we give a probabilistic construction of a
$2^{O(\sqrt{n})}$-facet polytope which is an $\varepsilon$-approximator of the
$\ell_{2}$ ball. This construction is analogous to a probabilistic
construction of O’Donnell and Wimmer [OW07], which shows that a variant of a
random monotone CNF construction due to Talagrand [Tal96] gives an
$\varepsilon$-accurate approximator for the Boolean Majority function. We
similarly modify a probabilistic construction of a convex body due to Nazarov
[Naz03], and use it to prove the following in Section 5:

######  Theorem 5 (Informal version of Theorem 27).

Let $B_{2}$ denote the $\ell_{2}$ ball of radius $\sqrt{n}$ in
$\mathbb{R}^{n}$ (so $\mathrm{Vol}(B_{2})=1/2+o_{n}(1)$). Then for any
constant $\varepsilon>0$,

$\mathrm{FC}(B_{2},\varepsilon)\leq 2^{O(\sqrt{n})}.$

###### A $2^{O(n^{3/4})}$-Facet Approximator for the $\ell_{1}$-Ball.

Since the $\ell_{1}$ ball does not enjoy the same level of rotational symmetry
as the $\ell_{2}$ ball, it is natural to wonder whether it can be similarly
approximated with a sub-exponential number of facets. As we now explain,
another motivation for this question comes from considering a result of
O’Donnell and Wimmer on the inability of small CNF formulas to approximate the
“tribes” Boolean DNF formula over $\\{0,1\\}^{n}$, in the context of a
recently-explored analogy between monotone Boolean functions and symmetric
convex sets [DS21, DNS21b, DNS22, HSSV22].

In [OW07] O’Donnell and Wimmer showed that any CNF formula that computes the
$n$-variable DNF tribes function correctly on $(1-\varepsilon)\cdot 2^{n}$
inputs, for $\varepsilon=0.1$, must have $2^{\Omega(n/\log n)}$ clauses. As
detailed in [DS21, DNS22], there is a natural correspondence between
$s$-clause CNF formulas over $\\{0,1\\}^{n}$ and symmetric intersections of
$2s$ halfspaces over $N(0,I_{n})$ (this correspondence is at the heart of the
main lower bound of [DS21] and several of the results of [HSSV22, DNS22]).
Thus, in seeking convex sets that may require $2^{\tilde{\Omega}(n)}$
halfspaces to approximate under $N(0,1)^{n}$, it is natural to look for a
Gaussian space convex analogue of of the DNF tribes function over
$\\{0,1\\}^{n}$. Now,

  * •

The DNF tribes function is the Boolean dual of the CNF Tribes function;

  * •

The Gaussian-space polytope corresponding to the CNF Tribes function is the
$\ell_{\infty}$ ball [DNS22, HSSV22]; and

  * •

The polytope which is dual to the $\ell_{\infty}$ ball is the $\ell_{1}$ ball.

Thus the following question naturally suggests itself:

> Does the $\ell_{1}$ ball $B_{1}$ in $\mathbb{R}^{n}$ require
> $2^{\tilde{\Omega}(n)}$ halfspaces for constant-accuracy approximation,
> analogous to how the DNF Tribes function requires
> $2^{\tilde{\Omega}(n)}$-clause CNFs for constant-accuracy approximation?

While the above conjecture may seem intuitively plausible (and indeed, the
authors initially tried to prove it), it turns out to be false. In Section 6,
we show that the $\ell_{1}$ ball can be approximated to any constant accuracy
as an intersection of sub-exponentially many halfspaces:

######  Theorem 6 (Special case of Theorem 29).

Let $B_{1}$ denote the origin-centered $\ell_{1}$ ball, i.e.

$B_{1}\mathrel{\mathop{\mathchar 58\relax}}=\left\\{x\in\mathbb{R}^{n}\
\mathrel{\mathop{\mathchar 58\relax}}\
\|x\|_{1}\leq\sqrt{{\frac{2}{\pi}}}n\right\\}.$

Then for any constant $\varepsilon$, we have

$\mathrm{FC}({B_{1}},\varepsilon)\leq 2^{O(n^{3/4})}.$

We prove Theorem 6 using a probabilistic construction, but one which is very
different from the probabilistic construction described above in the sketch of
Theorem 5 for the $\ell_{2}$ ball. The high-level intuition is as follows:
Determining whether or not a point $x\in\mathbb{R}^{n}$ lies within $B_{1}$ is
the same as determining whether or not the sum $|x_{1}|+|x_{2}|+\dots+|x_{n}|$
exceeds the threshold value $\sqrt{2/\pi}n$. Given this, the main idea is to
take a probabilistic approach which exploits both _anti-concentration_ and
_sampling_ :

  * •

Anti-concentration tells us that for $\boldsymbol{x}\sim N(0,I_{n})$, only a
small fraction of outcomes of
$|\boldsymbol{x}_{1}|+\cdots+|\boldsymbol{x}_{n}|$ will lie very close to the
boundary value of $\sqrt{2/\pi}n$. Thus, at the cost of a small error, we can
assume that a typical outcome $x$ of $\boldsymbol{x}$ either has
$|x_{1}|+\cdots+|x_{n}|\geq\sqrt{2/\pi}n+\tau$ (call this a “heavy” $x$), or
has $|x_{1}|+\cdots+|x_{n}|\leq\sqrt{2/\pi}n-\tau$ (call this a “light” $x$)
for a suitable margin parameter $\tau$.

  * •

Given this, we can use a sampling-based approach: if we uniformly sample $m$
coordinates $\boldsymbol{i}_{1},\dots,\boldsymbol{i}_{m}$ from $[n]$ and
evaluate $|x_{\boldsymbol{i}_{1}}|+\cdots+|x_{\boldsymbol{i}_{m}}|$, then for
a suitable threshold $\theta_{1}$ there will be a noticeable gap between (i)
the (extremely large) probability that
$|x_{\boldsymbol{i}_{1}}|+\cdots+|x_{\boldsymbol{i}_{m}}|\leq\theta_{1}$ when
$x$ is a typical light point, and (ii) the (still very large, but slightly
smaller) probability that
$|x_{\boldsymbol{i}_{1}}|+\cdots+|x_{\boldsymbol{i}_{m}}|\leq\theta_{1}$ when
$x$ is a typical heavy point.

The above gap means that by ANDing together a carefully chosen number $M$ of
random sets of the form

${\left\\{x\in\mathbb{R}^{n}\ \mathrel{\mathop{\mathchar 58\relax}}\
|x_{\boldsymbol{i}_{1}}|+\cdots+|x_{\boldsymbol{i}_{m}}|\leq\theta_{1}\right\\}},$
(1)

we get an approximator for $B_{1}$ which is accurate on almost all of the
points $x\in\mathbb{R}^{n}$ which are either light or heavy (and, as sketched
above, almost all points drawn from $N(0,I_{n})$ are either light or heavy, by
anti-concentration). The detailed analysis requires sophisticated Cramér-type
bounds which give very tight _multiplicative_ control on tails of sums of
random variables drawn _without_ replacement from a finite population of
values.

Note that each set of the form (1) is an $m$-variable “junta” $\ell_{1}$ ball
over its $m$ relevant coordinates (and is also an intersection of $2^{m}$
halfspaces), so the AND of $M$ such sets is an intersection of $M2^{m}$ many
halfspaces. With careful setting of parameters we get that this is at most
$2^{O(n^{3/4})}$ halfspaces, for any constant-factor approximation.

A $2^{\tilde{O}(n^{3/4})}$-facet approximator for the $\ell_{p}$ ball, $1\leq
p<2.$ Theorem 5 and Theorem 6 give sub-exponential approximators for the
$\ell_{1}$ and $\ell_{2}$ balls using two different sets of techniques. We
generalize the approach of Theorem 6 to give approximators of similar facet
complexity for $\ell_{p}$ balls of volume $1/2\pm o_{n}(1)$, for all $1\leq
p<2$:

######  Theorem 7 (Informal version of Theorem 29).

For $1<p<2$ let $B_{p}$ be the origin-centered $\ell_{p}$ balls in
$\mathbb{R}^{n}$ defined in Equation 30. Then for any constant $\varepsilon$,
we have

$\mathrm{FC}(B_{p},\varepsilon)\leq 2^{\tilde{O}(n^{3/4})}.$

The high-level approach, in its first stage, is similar to the $\ell_{1}$-ball
approximation sketched above. We now employ anticoncentration of the sum
$|\boldsymbol{x}_{1}|^{p}+\cdots+|\boldsymbol{x}_{n}|^{p}$, and now in place
of random sets of the form (1) we use random sets of the form

${\left\\{x\in\mathbb{R}^{n}\ \mathrel{\mathop{\mathchar 58\relax}}\
|x_{\boldsymbol{i}_{1}}|^{p}+\cdots+|x_{\boldsymbol{i}_{m}}|^{p}\leq\theta_{p}\right\\}}$
(2)

for a suitable threshold value $\theta_{p}$. As before, ANDing together a
carefully chosen number $M$ of sets of this form will be a high-accuracy
approximator to the volume-$1/2$ $\ell_{p}$ ball. But while in the $p=1$ case
each set of the form (1) was already an intersection of only $2^{m}$
halfspaces, for $1<p<2$ a set of the form (2) is not an intersection of any
finite number of halfspaces. Instead, we must replace each set of the form (2)
with an intersection of (not too many) halfspaces which is a very high
accuracy approximator for it. Crucially, each set of the form (2) has
extremely high volume; this is exactly the setting in which our efficient
relative-error approximator, Theorem 4, is useful. We apply Theorem 4 to
approximate each of the $M$ sets of the form (2) as an intersection of $N$
halfspaces (where $N$ is not too large), and then ANDing together all of those
approximators we achieve an $MN$-halfspace approximator to the original
$\ell_{p}$ ball $B_{p}$ in $\mathbb{R}^{n}$.

####  2.2 Overview of Lower Bounds

We now turn to a technical overview of our lower bounds.

###### Non-Explicit Average-Case Lower Bounds.

It is well known that standard counting arguments easily yield strong
(average-case) lower bounds on the complexity of approximating (non-explicit)
_Boolean functions_ that map $\\{-1,+1\\}^{n}$ to $\\{-1,+1\\}$. For a range
of different computational models, these lower bounds show that even achieving
approximation error $1/2-o_{n}(1)$ requires any approximator to be
exponentially large.

In our context of approximating convex sets in $\mathbb{R}^{n}$ by
intersections of halfspaces, counting arguments are not quite as
straightforward because there are infinitely many distinct halfspaces over
$\mathbb{R}^{n}$. Nevertheless, counting arguments can be brought to bear to
prove lower bounds. In more detail, [KOS08] used a counting argument to
establish the existence of $N=2^{2^{\Omega(\sqrt{n})}}$ distinct convex sets
$K_{1},\dots,K_{N}$ in $\mathbb{R}^{n}$, each of which is an intersection of
$2^{\Omega(\sqrt{n})}$ many halfspaces, such that
$\mathrm{dist}_{\mathrm{G}}(K_{i},K_{j})\geq 1/44000$ for each $1\leq i\neq
j\leq N.$ Using this result, it is possible to establish the existence of a
convex set $K$ (one of the sets $K_{1},\dots,K_{N}$) such that
$\mathrm{FC}(K,c)\geq 2^{c\sqrt{n}}$, where $c>0$ is a small absolute
constant.

In Section 7 we give a stronger (but still non-explicit) lower bound, which
shows that many halfspaces are required even to achieve error $1/2-o_{n}(1)$;
in other words, we give an _average-case_ lower bound (also known as a
_correlation bound_). Our lower bound trades off the accuracy of the
approximator against the number of halfspaces:

######  Theorem 8 (Informal version of Theorem 44).

For any $\tau=\omega(n^{-1/2}\cdot\log n)$, there exists some convex set
$K\subset\mathbb{R}^{n}$ that has
$\mathrm{FC}(K,\frac{1}{2}-\tau)=2^{\Omega(\tau\cdot\sqrt{n})}$.

For example, taking $\tau=n^{-1/4}$, Theorem 8 implies the existence of an
$n$-dimensional convex set $K$ such that no intersection of $2^{cn^{1/4}}$
many halfspaces can approximate $K$ to accuracy even as large as
$1/2+n^{-1/4}$; taking $\tau$ to be a constant, we recover the non-explicit
$2^{\Omega(\sqrt{n})}$ lower bound mentioned in the previous paragraph.

The proof of Theorem 8 combines classical results from statistical learning
theory with an information theoretic lower bound on _weak_ learning convex
sets under $N(0,I_{n})$ that was established in recent work [DS21]. A high-
level sketch is as follows: If every convex set could be approximated to high
accuracy ($1/2-\tau$) by an intersection of “few” halfspaces, then classical
results from statistical learning theory would imply the existence of
(computationally inefficient but sample-efficient) algorithms to “weakly”
learn any convex set $K$ to error $1/2-\tau/2$. On the other hand, a recent
result of De and Servedio [DS21] gives a strong lower bound on the error that
any sample-efficient weak learning algorithm for convex sets must incur. The
tension between these two bounds can be shown to imply a lower bound on the
number of halfspaces that any $(1/2-\tau)$-approximator must use; see Section
7 for the detailed argument. We remark that the proof of Theorem 8 is the
first result we know of in which an information-theoretic sample complexity
lower bound for learning is used to establish an _inapproximability_ result.

###### Average-Case Lower Bounds via Gaussian Noise Sensitivity.

One drawback of Theorem 8 is that it is non-constructive: not only does it not
exhibit any particular convex set which is hard to approximate, it does not
establish any particular criterion that implies that a convex set is hard to
approximate. Section 8 gives such a criterion. We show that any set with very
high _Gaussian noise sensitivity_ (at least $1/2-1/\mathrm{poly}(n)$) at very
low noise rates (at most $1/\mathrm{poly}(n)$) requires many halfspaces to
approximate to accuracy even $1/2+1/\mathrm{poly}(n)$:

######  Theorem 9 (Informal version of Theorem 49).

If $K\subset\mathbb{R}^{n}$ is any convex set which satisfies
$\mathbf{GNS}_{n^{-c}}(K)\geq{\frac{1}{2}}-n^{-c}$, then
$\mathrm{FC}(K,{\frac{1}{2}}-n^{-c})\geq 2^{n^{\Omega(1)}},$ where $c>0$ is a
suitable absolute constant.

Theorem 9 naturally raises the question of whether there in fact exist
$n$-dimensional convex sets that have Gaussian noise sensitivity as high as
$1/2-1/\mathrm{poly}(n)$ at noise rates that are as low as
$1/\mathrm{poly}(n)$. While natural, this question does not appear [O’D23] to
have been asked or answered prior to the current work. In Section 8.5 we
combine the information-theoretic lower bounds of [DS21] on weak learning
convex sets with the “low-degree algorithm” for learning bounded functions to
show that there do exist $n$-dimensional convex sets $K$ with
$\mathbf{GNS}_{1/\mathrm{poly}(n)}(K)\geq 1/2-1/\mathrm{poly}(n)$ (see Theorem
50). We believe that this result may be of independent interest.

The proof of Theorem 9 combines results from learning theory [KOS08] and the
study of unconditional pseudorandomness [OSTK21] with classical ideas from the
study of correlation bounds for Boolean functions [Hås86b, Cai86]. It employs
a notion of a “random zoom” for a function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\to\mathbb{R}$ which is closely analogous to the well-
studied notion of a “random restriction” of a function from $\\{-1,+1\\}^{n}$
to $\\{-1,+1\\}^{n}$.

Analogous to the well-known phenomenon that low-depth Boolean circuits over
$\\{-1,+1\\}^{n}$ simplify under random restrictions [Hås86b, Cai86], in the
context of developing efficient pseudorandom generators for intersections of
halfspaces it was shown in [OSTK21] that low-degree polynomials over
$N(0,I_{n})$ simplify under random zooms; more precisely, they are very likely
to have very low “hypervariance” after a random zoom (see Section 8.1 for
detailed definitions). Moreover, it was shown in [KOS08] (in the context of
developing efficient agnostic learning algorithms for intersections of
halfspaces) that any intersection of “not too many” halfspaces is close (in a
suitable sense) to a low-degree polynomial. Combining these results, we get
that (1) applying a random zoom to any intersection of few halfspaces, we get
a function that must have very low hypervariance, and hence must be very close
to a constant. But on the other hand, it can be shown that (2) if a set $K$
has very high Gaussian noise stability at very low noise rates, then after a
random zoom it must be very _far_ from a constant function. Similar to
classical correlation bounds for shallow Boolean circuits (which use the fact
that that the parity function is far from a constant function after random
restriction, while shallow Boolean circuits become close-to-constant after
random restrictions), the tension between (1) and (2) can be used to deduce
that any intersection of “not too many” halfspaces must be very far from any
set $K$ that has high Gaussian noise stability at low noise rates.

###### Lower Bounds via Convex Influences.

Neither of the two lower bound techniques discussed thus far yield lower
bounds for any explicit convex sets that we know of. For our final lower
bound, we use the recently introduced notion of convex influences [DNS21b,
DNS22] to prove lower bounds for the $\ell_{1}$ and $\ell_{2}$ balls. In more
detail, in Section 9 we give a general criterion on a convex set
$K\subset\mathbb{R}^{n}$ which suffices to ensure that
$\mathrm{FC}(K,\varepsilon)=2^{\Omega(\sqrt{n})}$, where $\varepsilon$ is a
suitable constant. This criterion is that $K$ is symmetric333Recall that a set
$K\subseteq\mathbb{R}^{n}$ is _symmetric_ if $x\in K$ implies $-x\in K$. and
has maximal _convex influence_ , up to a multiplicative constant factor. Since
both the $\ell_{1}$ ball of Gaussian volume $1/2$ and the $\ell_{2}$ ball of
volume $1/2$ satisfy this condition, we get a $2^{\Omega(\sqrt{n})}$ lower
bound for each of these explicit sets.

The notion of convex influence was recently introduced in the paper [DNS22] as
an analogue of the classical notion of influence from Boolean function
analysis over the discrete cube [KKL88, O’D14]. In particular, for any unit
vector $v$ and convex set $K$, $\mathbf{I}_{v}[K]$ is meant to capture how $K$
varies just in the direction $v$ (while averaging out every other direction) —
see Definition 65 for the precise formulation. An attractive feature of this
notion of influence is that for any orthonormal basis of $\mathbb{R}^{n}$, say
$\\{v_{1},\ldots,v_{n}\\}$, the sum $\sum_{i=1}^{n}\mathbf{I}_{v_{i}}[K]$ is
independent of the choice of the basis and depends only on the set $K$. This
leads us to the notion of total influence of a set $K$, denoted by
$\mathbf{I}[K]=\sum_{i=1}^{n}\mathbf{I}_{v_{i}}[K]$ (where
$\\{v_{1},\ldots,v_{n}\\}$ is any orthonormal basis of $\mathbb{R}^{n}$).

[DNS22] proved several structural properties of both influence and total
influence. In particular, Proposition 19 of [DNS22] established that the total
influence of any convex set $K$ is $O(\sqrt{n})$; furthermore, this bound is
tight, as exhibited by $K=B(\sqrt{n})$, which is shown in [DNS22] to be the
convex set of maximal total influence.

In this paper, we show that any symmetric set $K$ with maximal total influence
(up to a constant factor) requires any approximator to have high facet
complexity. In particular, we prove the following theorem:

######  Theorem 10 (Informal version of Theorem 70).

If $K$ is symmetric and $\mathbf{I}[K]=\Omega(\sqrt{n})$, then for a suitable
constant $\varepsilon>0$ we have that
$\mathrm{FC}(K,\varepsilon)=2^{\Omega(\sqrt{n})}.$

The main idea in the proof of the above theorem is a new structural result
establishing that if $L$ is a convex set which is an intersection of $s$
halfspaces, then $\mathbf{I}[L]=O(\log s)$ (Proposition 69). Coupled with the
fact that $\mathbf{I}[K]$ can be expressed in terms of the degree-$2$ Hermite
coefficients of $K$, a fairly simple argument using Parseval’s identity and
Cantelli’s inequality leads to Theorem 10.

Once again, we observe that there is an analogy here with the Boolean setting.
Namely, Boppana [Bop97] showed that for any $s$-clause CNF formula, its total
influence (as defined over the Boolean cube) is bounded by $O(\log s)$. We
note that despite the syntactic analogy with Proposition 69, the underlying
techniques are completely different; while Proposition 69 is an inherently
geometric argument, the proof of Boppana relies on the method of random
restrictions [Hås86b].

####  2.3 Discussion

The current paper takes the first steps in studying polytopal approximations
of convex sets under Gaussian measure. Several tantalizing questions emerge
from our work; we highlight a few of these now.

Perhaps the most natural question is to close the gap between the worst case
upper and lower bounds on $\mathrm{FC}(K,\varepsilon)$ in the
constant-$\varepsilon$ regime. In particular, both Theorem 70 and Theorem 44
guarantee the existence of convex sets $K$ such that
$\mathrm{FC}(K,\varepsilon)=2^{\Omega(\sqrt{n})}$ for some constant
$\varepsilon>0$. On the other hand, Theorems 19 and 20 show that for any
constant $\varepsilon>0$, $\mathrm{FC}(K,\varepsilon)=n^{O(n)}$. Can we close
this gap?

In a related vein, it would also be interesting to obtain tighter upper and
lower bounds on $\mathrm{FC}(K,\varepsilon)$ when $K$ is the $\ell_{p}$ ball
of Gaussian volume $1/2$. In particular, for $p>2$, we do not have an upper
bound on the facet complexity (when the error $\varepsilon$ is a constant)
that is better than $n^{O(n)}$. Is it possible to obtain polytopal
approximations for the $\ell_{p}$ ball with $2^{n^{1-c}}$ facets for constant
$c>0$ in the constant error regime?

Finally, looking ahead, it would be interesting to study Gaussian-distance
polytopal approximation of convex sets via approximators with small _vertex
complexity_. Very little seems to be known here and indeed, the vertex
complexity analogues of many questions considered in the current paper seem to
be wide open. For example, Section 5 gets a $2^{O(\sqrt{n})}$-facet
approximator for the $\ell_{2}$ ball. Can we obtain a similar approximator for
the $\ell_{2}$ ball which has subexponential vertex complexity?

###  3 Preliminaries

Section 3.1 recalls basic background and sets up notation, Section 3.2 gives
standard facts about the Gaussian and chi-squared distributions, Section 3.3
recalls known bounds on Gaussian surface area, and finally Section 3.4 defines
the various distance metrics between convex sets that we will use.

####  3.1 Basic Notation and Terminology

We use boldfaced letters such as
$\boldsymbol{x},\boldsymbol{f},\boldsymbol{A}$, etc. to denote random
variables (which may be real-valued, vector-valued, function-valued, or set-
valued; the intended type will be clear from the context). We write
$\boldsymbol{x}\sim\mathcal{D}$ to indicate that the random variable
$\boldsymbol{x}$ is distributed according to probability distribution
$\mathcal{D}$. We will frequently identify a set $K\subseteq\mathbb{R}^{n}$
with its $0/1$-valued indicator function.

######  Notation 11 (Multiplicative approximation).

We use the following notation to denote that two nonzero reals $a,b$ are
multiplicatively close: For $\nu\geq 0$,

$a\approx_{\nu}b\quad\iff\quad e^{-\nu}\leq a/b\leq e^{\nu}$

(note that this condition is symmetric in $a$ and $b$).

###### Geometry.

We write $e_{i}\in\mathbb{R}^{n}$ to denote the $i^{\text{th}}$ standard basis
vector. For $r>0$, we write $\mathbb{S}^{n-1}(r)$ to denote the origin-
centered sphere of radius $r$ in $\mathbb{R}^{n}$ and $B(r)$ to denote the
origin-centered ball of radius $r$ in $\mathbb{R}^{n}$, i.e.,

$\mathbb{S}^{n-1}(r)=\big{\\{}x\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar
58\relax}}\|x\|=r\big{\\}}\quad\text{and}\quad
B(r)=\big{\\{}x\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar 58\relax}}\|x\|\leq
r\big{\\}},$

where $\|x\|$ denotes the $\ell_{2}$ norm $\|\cdot\|_{2}$ of
$x\in\mathbb{R}^{n}$. We also write $\mathbb{S}^{n-1}$ for the unit sphere
$\mathbb{S}^{n-1}(1)$.

###### Convex Sets and Convex Bodies.

A set $K\subseteq\mathbb{R}^{n}$ is _convex_ if $x,y\in K$ implies
$\alpha\hskip 0.85355ptx+(1-\alpha)y\in K$ for all $\alpha\in[0,1]$. We recall
(see e.g. [Lan86]) that all convex sets are Lebesgue measurable.

A convex _body_ in $\mathbb{R}^{n}$ is a compact convex set with non-empty
interior. Our results will hold for general convex sets (not only bodies), but
since we are working with Gaussian distance, it is easy to see that it
suffices to consider only convex bodies. (If a convex set has empty interior
then its Gaussian volume is 0; the Gaussian volume of the closure of a convex
set is the same as the Gaussian volume of the set; and if a convex set $A$ is
unbounded, we can “truncate” it by intersecting it with a sufficiently large
ball to obtain a bounded convex set $A^{\prime}\subset A$ with
$\mathrm{dist}_{\mathrm{G}}(A,A^{\prime})\leq\varepsilon/2$.)

Finally, for sets $K,L\subseteq\mathbb{R}^{n}$, we write $K+L$ to denote the
Minkowski sum $\\{x+y\mathrel{\mathop{\mathchar 58\relax}}x\in K\ \text{and}\
y\in L\\}.$ For a set $K\subseteq\mathbb{R}^{n}$ and $r>0$ we write $rK$ to
denote the set $\\{rx\mathrel{\mathop{\mathchar 58\relax}}x\in K\\}$.

###### Intersections of Halfspaces and Approximation.

For the sake of readability we will mostly state our results in a self-
contained way, but the following notation will sometimes be useful:

  * •

We write $\mathrm{Facet}(n,M)$ to denote the class of all convex sets which
are intersections of $M$ halfspaces in $\mathbb{R}^{n}$, i.e. the class of all
$M$-facet convex sets.

  * •

For a convex set $K\subseteq\mathbb{R}^{n}$ and a value $0<\varepsilon<1$, we
write $\mathrm{FC}(K,\varepsilon)$ to denote the minimum value $M$ such that
there is some intersection of $M$ halfspaces $L\in\mathrm{Facet}(n,M)$ such
that $\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon$, i.e.
$\mathrm{FC}(K,\varepsilon)$ is the minimum “facet complexity” of any
$\varepsilon$-approximator of $K$.

####  3.2 The Gaussian and Chi-Squared Distributions

We write $N(0,I_{n})$ to denote the $n$-dimensional standard Gaussian
distribution, and denote its density function by $\varphi_{n}$, i.e.

$\varphi_{n}(x)=(2\pi)^{-n/2}e^{-\|x\|^{2}/2}.$

When the dimension is clear from context, we may simply write $\varphi$
instead of $\varphi_{n}$. We write $\mathrm{Vol}(K)$ to denote the Gaussian
measure of a (Lebesgue measurable) set $K\subseteq\mathbb{R}^{n}$, that is

$\mathrm{Vol}(K)\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim N(0,I_{n})}[\boldsymbol{x}\in K].$

We recall the following standard tail bound on Gaussian random variables:

######  Proposition 12 (Theorem 1.2.6 of [Dur19] or Equation 2.58 of [Wai]).

Suppose $\boldsymbol{g}\sim N(0,1)$ is a one-dimensional Gaussian random
variable. Then for all $r>0$,

$\varphi_{1}(r)\left({\frac{1}{r}}-{\frac{1}{r^{3}}}\right)\leq\mathop{{\bf
Pr}\/}_{\boldsymbol{g}\sim N(0,1)}[\boldsymbol{g}\geq
r]\leq\varphi_{1}(r)\left({\frac{1}{r}}-{\frac{1}{r^{3}}}+{\frac{3}{r^{5}}}\right)$

where $\varphi_{1}$ is the one-dimensional Gaussian density.

We will also make use of the Berry-Esseen central limit theorem [Ber41, Ess42]
(alternatively, see Section 11.5 of [O’D14]):

######  Theorem 13.

Let $\boldsymbol{X}_{1},\ldots,\boldsymbol{X}_{n}$ be independent random
variables with $\mathop{{\bf E}\/}{\left[\boldsymbol{X}_{i}\right]}=0$ and
$\mathop{{\bf Var}\/}{\left[\boldsymbol{X}_{i}\right]}=\sigma_{i}^{2}$, and
assume $\sum_{i=1}^{n}\sigma_{i}^{2}=1$. Let
$\boldsymbol{S}=\sum_{i=1}^{n}\boldsymbol{X}_{i}$ and let $\boldsymbol{Z}\sim
N(0,1)$ be a standard univariate Gaussian. Then for all $u\in\mathbb{R}$,

${\left|\mathop{{\bf Pr}\/}{\left[\boldsymbol{S}\leq u\right]}-\mathop{{\bf
Pr}\/}{\left[\boldsymbol{Z}\leq u\right]}\right|}\leq c\gamma$

where

$\gamma=\sum_{i=1}^{n}\mathop{{\bf
E}\/}{\left[|\boldsymbol{X}_{i}|^{3}\right]}$

and $c\leq 0.56$ is a universal constant.

Recall that the norm of an $n$-dimensional Gaussian random vector is
distributed according to the chi-squared distribution with $n$ degrees of
freedom, i.e. if $\boldsymbol{x}\sim N(0,I_{n})$ then
$\|\boldsymbol{x}\|^{2}\sim\chi^{2}(n)$. It is well known (see e.g. [Wik23])
that the mean of the $\chi^{2}(n)$ distribution is $n$, the median is
$n{\left(1-\Theta(1/n)\right)}$, and for $n\geq 2$ the pdf is everywhere at
most 1. We note that an easy consequence of these facts is that the origin-
centered ball $B(\sqrt{n})$ of radius $\sqrt{n}$ in $\mathbb{R}^{n}$ has
$\mathrm{Vol}(B(\sqrt{n}))=1/2+o_{n}(1).$

We will require the following tail bound on $\chi^{2}(n)$ random variables:

######  Proposition 14 (Section 4.1 of [LM00]).

Suppose $\boldsymbol{y}\sim\chi^{2}(n)$. Then for any $t>0$, we have

$\displaystyle\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\chi^{2}(n)}{\left[\boldsymbol{y}\geq
n+2\sqrt{nt}+2t\right]}\leq\exp{\left(-t\right)},$ $\displaystyle\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\chi^{2}(n)}{\left[\boldsymbol{y}\leq
n-2\sqrt{nt}\right]}\leq\exp{\left(-t\right)}.$

####  3.3 Bounds on Gaussian Surface Area

Given a measurable set $K\subseteq\mathbb{R}^{n}$, recall that the _Gaussian
surface area of $K$_—which we will denote as $\mathbf{GSA}(K)$—is given by

$\mathbf{GSA}(K)\mathrel{\mathop{\mathchar 58\relax}}=\lim_{\delta\to
0}\frac{\mathrm{Vol}{\left(K+B(\delta)\right)}-\mathrm{Vol}(K)}{\delta}.$

For convex sets (more generally, for sets which are sufficiently regular, e.g.
have smooth boundary except at a set of measure zero), we have

$\mathbf{GSA}(K)=\int_{\partial K}\varphi(x)\,d\sigma(x)$ (3)

See [Naz03] or Definition 2 of [KOS08] for further discussion on this point.
The following upper bound on the Gaussian surface area of an intersection of
halfspaces was obtained by Nazarov; see [KOS08, Kan14b].

######  Theorem 15 (Nazarov’s bound).

Suppose $K\subseteq\mathbb{R}^{n}$ is an intersection of $s$ halfspaces. Then
we have

$\mathbf{GSA}(K)\leq\sqrt{2\ln s}+2.$

We will also require the following upper bound on the Gaussian surface area of
an arbitrary convex set in $\mathbb{R}^{n}$, which was obtained by Ball
[Bal93]:

######  Theorem 16 (Ball’s theorem).

Suppose $K\subseteq\mathbb{R}^{n}$ is a convex set. Then we have

$\mathbf{GSA}(K)\leq O(n^{1/4}).$

Finally, we recall the Gaussian isoperimetric inequality [ST78, Bor75]:

######  Theorem 17.

Suppose $K\subseteq\mathbb{R}^{n}$. Let $H\subseteq\mathbb{R}^{n}$ be a
halfspace (i.e. $H=\\{x\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar
58\relax}}\langle x,v\rangle\leq\theta\\}$ for $v\in\mathbb{S}^{n-1}$ and
$\theta\in\mathbb{R}$) such that $\mathrm{Vol}(H)=\mathrm{Vol}(K)$. Then

$\mathbf{GSA}(K)\geq\mathbf{GSA}(H)=\varphi_{1}(\theta)$

where $\varphi_{1}$ denotes the univariate Gaussian p.d.f.

####  3.4 Distance Metrics Between Sets

The primary distance metric we will use throughout this paper is the
following: Given two measurable sets $K,L\subseteq\mathbb{R}^{n}$, we define

$\mathrm{dist}_{\mathrm{G}}(K,L)\mathrel{\mathop{\mathchar
58\relax}}=\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[K(\boldsymbol{x})\neq L(\boldsymbol{x}).\right]}$

In other words,
$\mathrm{dist}_{\mathrm{G}}(K,L)=\mathrm{Vol}(K\,\triangle\,L)$, i.e. the
Gaussian measure of the symmetric difference of the sets $K$ and $L$.

We also recall the _Hausdorff distance_ between two sets
$K,L\subseteq\mathbb{R}^{n}$, which is defined as

$\mathrm{dist}_{\mathrm{H}}(K,L)\mathrel{\mathop{\mathchar
58\relax}}=\max{\left\\{\sup_{x\in
K}\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{y\in L}d(x,y),\,\sup_{y\in
L}\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{x\in K}d(x,y)\right\\}}$

where $d(x,y)\mathrel{\mathop{\mathchar 58\relax}}=\|x-y\|_{2}$ denotes the
usual Euclidean $\ell_{2}$ distance between the points $x$ and $y$. We will
rely on bounds on polytope approximation under the Hausdorff distance in
Section 4.1.

## Part I: Upper Bounds

We start by giving generic upper bounds on the number of halfspaces needed to
approximate arbitrary $n$-dimensional convex sets under the Gaussian distance.
In Section 4.1, we show that

${\left(\widetilde{O}(n^{5/4}/\varepsilon)\right)}^{(n-1)/2}$

halfspaces suffice to $\varepsilon$-approximate any convex set under the
Gaussian distance metric, where the $\widetilde{O}$ hides a logarithmic factor
in $1/\varepsilon$. In Section 4.2, we sharpen the bound from Section 4.1 for
sets of large-enough volume. In particular, we show that if
$K\subsetneq\mathbb{R}^{n}$ is a convex set with $\mathrm{Vol}(K)=1-\delta$,
then

$\frac{1}{\delta}\cdot{\left(\frac{n}{\varepsilon}\log{\left(\frac{1}{\delta}\right)}\right)}^{O(n)}$

halfspaces suffice to $\varepsilon\delta$-approximate $K$ under the Gaussian
distance metric.

In Sections 5 and 6, we show that the above exponential-in-$n$ bounds on the
facet complexity of convex sets can be significantly sharpened for specific
convex sets. We show in Section 5 that $\exp(O(\sqrt{n}))$ halfspaces suffice
to approximate the $\ell_{2}$ ball of Gaussian volume $1/2$ to constant
accuracy. In Section 6, we give an entirely different construction from that
in Section 5 to show that for $1\leq p<2$, $\exp(\widetilde{\Theta}(n^{3/4}))$
halfspaces suffice to approximate $\ell_{p}$ balls of Gaussian volume $1/2$ to
constant accuracy. Crucially, our construction in Section 6 will make use of
the improved generic upper bound from Section 4.2.

###  4 Generic Upper Bounds

We first give upper bounds on the facet complexity of arbitrary convex sets in
$\mathbb{R}^{n}$ under the Gaussian distance metric.

####  4.1 Warmup: Universal Approximation via Hausdorff Distance Approximation

The following upper bound on the facet complexity of polytope approximators
under the _Hausdorff distance_ (cf. Section 3.4) was independently obtained by
Dudley [Dud74] and by Bronstein and Ivanov [BI75]; see also Section 4.1 of
[Bro08].

######  Theorem 18 ([BI75]).

Suppose $K\subseteq\mathbb{R}^{n}$ is a compact convex set with non-empty
interior that is contained in the unit ball in $\mathbb{R}^{n}$, i.e.

$K\subseteq B(1).$

For $0<\varepsilon<10^{-3}$, there exists a convex body $L$ which is the
intersection of

$3\sqrt{n}{\left(\frac{9}{\varepsilon}\right)}^{(n-1)/2}~{}\text{halfspaces}$

such that $K\subseteq L$ and $\mathrm{dist}_{\mathrm{H}}(K,L)\leq\varepsilon.$

We remark that the original results due to [Dud74, BI75] consider the _vertex
complexity_ (i.e. number of vertices) of approximators instead of the facet
complexity and furthermore only consider inner approximators to $K$ (i.e.
$L\subseteq K$ in the above); their arguments, however, can be easily modified
to obtain the above [AAdFM18]. Finally, we note that the bound in Theorem 18
is known to be close to tight: any outer (or inner) approximation to the unit
ball $B(1)$ in $\mathbb{R}^{n}$ requires $\Omega(1/\varepsilon^{(n-1)/2})$
halfspaces [AdFM12, Bro08].

Theorem 18 and Ball’s universal bound on the Gaussian surface area of any
convex set (Theorem 16) imply the following upper bound for approximating
generic convex sets in $\mathbb{R}^{n}$ under the Gaussian distance:

######  Theorem 19 (Universal approximation of convex sets.).

Let $0<\varepsilon<10^{-3}$. For every convex set $K\subseteq\mathbb{R}^{n}$,
there exists a convex set $L$ which is an intersection of

$O{\left(\frac{n^{5/4}+{2n^{3/4}}\sqrt{{\ln}(2/\varepsilon)}}{\varepsilon}\right)}^{(n-1)/2}~{}\text{halfspaces}$

such that $\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon$, i.e. we have
$\mathrm{FC}(K,\varepsilon)\leq
O{\left(\frac{n^{5/4}+{2n^{3/4}}\sqrt{{\ln}(2/\varepsilon)}}{\varepsilon}\right)}^{(n-1)/2}.$

###### Proof.

For the rest of the argument, set

$r^{\ast}\mathrel{\mathop{\mathchar
58\relax}}=\sqrt{n}+2\sqrt{{\ln}{\left(\frac{2}{\varepsilon}\right)}}\qquad\text{and}\qquad\varepsilon^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=\Theta{\left(\frac{\varepsilon}{n^{1/4}}\right)}.$

Recalling that the squared norm of a Gaussian vector is distributed according
to a $\chi^{2}(n)$ distribution, we have by Proposition 14 that

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\|\boldsymbol{x}\|^{2}>{r^{\ast}}^{2}\right]}\leq\mathop{{\bf
Pr}\/}_{\|\boldsymbol{x}\|^{2}\sim\chi^{2}(n)}{\left[\|\boldsymbol{x}\|^{2}\geq
n+2\sqrt{n{\ln}{\left(\frac{2}{\varepsilon}\right)}}+2{\ln}{\left(\frac{2}{\varepsilon}\right)}\right]}\leq\frac{\varepsilon}{2}.$
(4)

It thus suffices to $(\varepsilon/2)$-approximate
$K^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=K\cap B(r^{\ast})$ under the
Gaussian distance metric.

It is easy to see by definition of the Hausdorff distance that

$\mathrm{dist}_{\mathrm{H}}(K,L)\leq\delta\quad\text{is equivalent
to}\quad\mathrm{dist}_{\mathrm{H}}(tK,tL)\leq t\delta.$

In particular, consider the convex set $({1}/{r^{\ast}})K^{\prime}\subseteq
B(1)$, and let $L\subseteq\mathbb{R}^{n}$ be the polytope guaranteed to exist
by Theorem 18 such that $K\subseteq L$ and

$\mathrm{dist}_{\mathrm{H}}{\left(\frac{1}{r^{\ast}}K^{\prime},\frac{1}{r^{\ast}}L\right)}\leq\frac{\varepsilon^{\prime}}{2r^{\ast}},\qquad\text{which
implies
that}\qquad\mathrm{dist}_{\mathrm{H}}(K^{\prime},L)\leq\frac{\varepsilon^{\prime}}{2}.$

Recalling our choice of $\varepsilon^{\prime}$, note that Theorem 18
guarantees that $L$ is an intersection of

$O{\left(\frac{18\sqrt{n}r^{\ast}}{\varepsilon^{\prime}}\right)}^{(n-1)/2}=O{\left(\frac{n^{5/4}+{2n^{3/4}}\sqrt{{\ln}(2/\varepsilon)}}{\varepsilon}\right)}^{(n-1)/2}~{}\text{halfspaces.}$

We will show that $L$ is in fact an $(\varepsilon/2)$-approximator for
$K^{\prime}$ under the Gaussian distance, which would complete the proof as

$\mathrm{dist}_{\mathrm{G}}(K,L)\leq\mathrm{dist}_{\mathrm{G}}(K,K^{\prime})+\mathrm{dist}_{\mathrm{G}}(K^{\prime},L)\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\frac{\varepsilon}{2}.$
(5)

Indeed, by definition of the Hausdorff distance we have that

$K^{\prime}\subseteq L\subseteq
K^{\prime}_{\varepsilon^{\prime}}\qquad\text{where}~{}K^{\prime}_{\varepsilon^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}={\left\\{x\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar
58\relax}}\inf_{y\in K}d(x,y)\leq\varepsilon^{\prime}\right\\}}.$ (6)

Consequently, the Gaussian distance between the sets $K^{\prime}$ and $L$ is

$\displaystyle\mathrm{dist}_{\mathrm{G}}(K^{\prime},L)$
$\displaystyle=\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[K^{\prime}(\boldsymbol{x})\neq L(\boldsymbol{x})\right]}$
$\displaystyle=\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\boldsymbol{x}\in L\setminus K^{\prime}\right]}$
$\displaystyle\leq\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\boldsymbol{x}\in K^{\prime}_{\varepsilon^{\prime}}\setminus
K^{\prime}\right]}$
$\displaystyle=\int_{t=0}^{\varepsilon^{\prime}}\int_{x\in\partial
K_{t}}\varphi(x)\,dx\,dt$
$\displaystyle=\int_{t=0}^{\varepsilon^{\prime}}\mathbf{GSA}(K_{t})\,dt$
$\displaystyle\leq\varepsilon^{\prime}\cdot O(n^{1/4})$ (7)
$\displaystyle=\frac{\varepsilon}{2}.$ (8)

Here, $K_{t}$ is defined as in Equation 6; it is easy to see that if $K$ is a
convex, then so is $K_{t}$ for all $t\geq 0$. Note that we used Keith Ball’s
bound on the Gaussian surface area of convex sets (Theorem 16) to obtain
Equation 7. The theorem now follows from Equations 5 and 8. ∎

####  4.2 A Relative-Error Sharpening of Theorem 19

We now establish a sharpening of Theorem 19 that gives a much better bound in
the regime where $K$ has volume very close to 1:

######  Theorem 20.

Let $0<\delta<1.$ Suppose $K\subseteq\mathbb{R}^{n}$ is a closed convex set
with

$\mathrm{Vol}(K)=1-\delta.$

Then for all $\varepsilon>0$, there exists a convex set $L$ which is the
intersection of

$\frac{1}{\delta}\cdot{\left(\frac{n}{\varepsilon}\log{\left(\frac{1}{\delta}\right)}\right)}^{O(n)}$

halfspaces such that $\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon\delta$;
i.e.,
$\mathrm{FC}(K,\varepsilon\delta)\leq\frac{1}{\delta}\cdot{\left(\frac{n}{\varepsilon}\log{\left(\frac{1}{\delta}\right)}\right)}^{O(n)}$.

We mention that in the most interesting regime, when $\delta$ is smaller than
some absolute constant (which can be taken to be 1/10), our proof of Theorem
20 is self-contained and does not rely on the result of Bronstein–Ivanov
(Theorem 18).

To contrast Theorem 20 with Theorem 19, note that Theorem 19 would give an
$\varepsilon\delta$-approximation to $K$ using

${\left(\widetilde{O}(n^{5/4}/\varepsilon\delta)\right)}^{(n-1)/2}~{}\text{halfspaces}$

where the $\widetilde{O}$ hides a logarithmic factor in
$\log(1/\varepsilon\delta)$. The crucial difference between Theorem 20 and
Theorem 19 is that the dependence of Theorem 20 on $\delta$ is only
${\frac{1}{\delta}}\cdot\log(1/\delta)^{O(n)}$ rather than
$(1/\delta)^{O(n)}$. This can make a major difference if $\delta$ is very
small; for example, if $\delta=1/2^{\sqrt{n}}$ and $\varepsilon=0.01$ (observe
that with these parameters, the desired approximator of $K$ must correctly
“lop off” at least 99% of the $1/2^{\sqrt{n}}$ amount of mass that lies
outside of $K$), then Theorem 19 would only give a bound of
$2^{\tilde{O}(n^{3/2})}$ halfspaces whereas Theorem 20 gives a bound of
$2^{\tilde{O}(n)}$ halfspaces. Indeed, our $2^{\tilde{O}(n^{3/4})}$-halfspaces
approximation of $\ell_{p}$ balls for $p\in(1,2)$, given in Section 6, will
crucially rely on a savings of this sort that comes from the sharper
parameters provided by Theorem 20.

#####  4.2.1 Proof Overview

We set up some useful notation and give a high-level proof overview of Theorem
20. Throughout this section as well as the next, let
$K\subseteq\mathbb{R}^{n}$ be a fixed convex set with volume $1-\delta$ as in
the statement of Theorem 20. We may assume without loss of generality that $K$
is closed, since $\mathrm{Vol}(K)$ is the same as the volume of the closure of
$K$ for any convex set $K$.

We first remark that if $\delta\geq 1/10$ then the claimed bound is an
immediate consequence of Theorem 19, so we henceforth suppose that
$\delta<1/10.$

As in the proof of Theorem 19, we may assume that $K$ is contained in a ball
of sufficiently large radius, namely

$K\subseteq B{\left(R\right)}\qquad\text{where}~{}R\mathrel{\mathop{\mathchar
58\relax}}=\sqrt{n}+2\sqrt{\ln{\left(\frac{2}{\varepsilon\delta}\right)}},\qquad\text{so}~{}\mathrm{Vol}(R)\geq
1-{\frac{\varepsilon\delta}{2}},$

and that the goal is to obtain an $(\varepsilon\delta/2)$-approximation to
$K$.444In particular, we may intersect $K$ with $B(R)$ to obtain a convex set
$K^{\prime}$ and aim for an $(\varepsilon\delta/2)$-approximation to
$K^{\prime}$ as in Section 4.1; for notational simplicity, however, we do not
introduce the new set $K^{\prime}$ in this section.

######  Definition 21 (“Length” function).

Given a vector $v\in\mathbb{S}^{n-1}$, we define the function
$\ell\mathrel{\mathop{\mathchar 58\relax}}\mathbb{S}^{n-1}\to\mathbb{R}$ as

$\ell(v)\mathrel{\mathop{\mathchar 58\relax}}=\sup_{x\in K}{\left\langle
x,v\right\rangle}.$

In other words, $\ell(v)$ is the “length” of the set $K$ along the direction
$v$ from the origin. We remark that since $\mathrm{Vol}(K)>0.9>1/2$, the set
$K$ must contain the origin. We further remark that the function
$\ell\mathrel{\mathop{\mathchar 58\relax}}\mathbb{S}^{n-1}\to\mathbb{R}$ is
sometimes called the _Minkowski_ or _support functional_ of the set $K$
[Tko18].

######  Notation 22.

We write $m(t)$ for

$m(t)\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
Pr}\/}_{\boldsymbol{y}\sim\chi^{2}(n)}{\left[\boldsymbol{y}\geq
t^{2}\right]}.$

Note that $m(t)$ is simply the tail mass of the $\chi^{2}(n)$ distribution
beyond the point $t^{2}$. We can also view it as the probability that a
Gaussian draw $\boldsymbol{x}\sim N(0,I_{n})$ has $\|\boldsymbol{x}\|^{2}\geq
t$, even conditioned on $\boldsymbol{x}$ lying on any particular ray
$\\{rv\mathrel{\mathop{\mathchar 58\relax}}r\in\mathbb{R}_{\geq 0}\\}$ for any
fixed $v\in\mathbb{S}^{n-1}.$ See Figure 1 for a schematic of the setup thus
far.

$B(R)$$B(1)$$v$$\ell(v)$$K$ Figure 1: Setup for the proof of Theorem 20. The
length of the solid line is $\ell(v)$, and the conditional Gaussian mass on
the dashed ray (conditioned on the Gaussian lying on the ray from the origin
in direction $v$) corresponds to $m(\ell(v))$. The cross-hatched region
corresponds to the (at most) $\varepsilon\delta/2$ approximation error
incurred by intersecting $K$ with $B(R)$.

From Definition 21, 22, and the definition of the set $K$ in Theorem 20, we
have that

$\mathop{{\bf
E}\/}_{\boldsymbol{v}\sim\mathbb{S}^{n-1}}{\left[m{\left(\ell(\boldsymbol{v})\right)}\right]}=\delta$

since $\mathrm{Vol}(K)=1-\delta$. Note that this uses the convexity of the set
$K$ and the fact that $K$ contains the origin.

Finally, since $\mathrm{Vol}(K)=1-\delta\geq 0.9$, we have that $B(1)\subseteq
K$. To see this, note that if there exists $x\in B(1)$ such that $x\notin K$,
then the separating hyperplane through $x$ for $K$ “lops off” at least
$1-\Phi(1)>0.1$ of the Gaussian mass, and hence $\mathrm{Vol}(K)<0.9$, which
is a contradiction. We record this fact for convenience:

######  Fact 23.

We have that $B(1)\subseteq K$.

We now turn to a high-level description of the approximator $L$. As in the
proof of Theorem 19, $L$ will be an outer approximator to the set $K$ (i.e.
$K\subseteq L$). We will construct $L$ by placing tangent hyperplanes to
$\partial K$ that “lop off” at least a $(1-\varepsilon)$-fraction of the total
$\delta$ amount of Gaussian mass that lies outside the set $K$. In more
detail, call a direction $v\in\mathbb{S}^{n-1}$ “good” if
$m(\ell(v))\leq(\varepsilon\delta/4)$, and “bad” otherwise.

  * •

For all “good” directions, we will not worry about lopping off mass. Indeed,
even if we failed to lop any probability mass off in all such directions, the
total contribution to our overall error would be at most
$(\varepsilon\delta/4)$.

  * •

In order to handle “bad” directions, we first bucket them according to the
value of $m(\ell(v))$ (which, as stated earlier, is proportional to the amount
of Gaussian mass along $v$ outside of $K$). We will obtain an appropriate
covering of the points in each bucket, and we will place tangent hyperplanes
to $K$ at the points in our covering. A geometric argument (which will make
use of the fact that $B(1)\subseteq K$), together with suitable tail bounds,
will then give that the total error incurred from all “bad” directions is at
most $(\varepsilon\delta/4)$.

Putting everything together, we will obtain an
$(\varepsilon\delta/2)$-approximation to the set $K$; since we assumed
$K\subseteq B(R)$, we already incurred $(\varepsilon\delta/2)$-error, which
overall gives

$\mathrm{dist}_{\mathrm{G}}(K,L)\leq\varepsilon\delta.$

#####  4.2.2 Proof of Theorem 20

As mentioned earlier, we may suppose that $\delta\leq 1/10.$ We start by
describing the bucketing alluded to in the proof overview.

######  Definition 24 (Bucketing $\mathbb{S}^{n-1}$).

Let $\tau>0$ be a parameter that we will fix later. For $k\in\mathbb{N}$, we
define

$\mathrm{buck}(k)\mathrel{\mathop{\mathchar
58\relax}}={\left\\{v\in\mathbb{S}^{n-1}\mathrel{\mathop{\mathchar
58\relax}}m(\ell(v))\in\left((1+\tau)^{-k},(1+\tau)^{-k+1}\right]\right\\}}.$

We will fix $\tau$ (which will be a small quantity between $0$ and $1$) later
in the course of the proof. Informally, $\mathrm{buck}(k)$ is the set of
directions for which the probability that a Gaussian vector in that direction
lies outside $K$ is roughly $(1+\tau)^{-k}$.

For large enough $k$, the amount of mass outside $K$ along the directions in
$\mathrm{buck}(K)$ will be small, and so intuitively we should be able to
ignore such directions. (We called such directions “good” in the proof
overview.) To make this precise, set a parameter $k^{\ast}$ to be

$k^{\ast}\mathrel{\mathop{\mathchar
58\relax}}={\frac{1}{\tau}\ln{\left(\frac{4}{\varepsilon\delta}\right)}}.$

We then have for all $v\in\mathrm{buck}(k)$ with $k>k^{\ast}$ that

$m(\ell(v))\leq{\left(1+\tau\right)}^{-k+1}\leq\exp(-\tau
k^{\ast})\leq\frac{\varepsilon\delta}{4}.$

As discussed previously, we will only have to worry about the “bad” directions
corresponding to

$\bigsqcup_{k=1}^{k^{\ast}}\mathrm{buck}(k)$ (9)

and ignore the “good” directions; this will incur at most
$\varepsilon\delta/4$ error. We will use the following lemma to separately
handle each bucket $\mathrm{buck}(k)$ for $k\leq k^{\ast}$.

######  Lemma 25.

Suppose $A\subseteq\mathbb{S}^{n-1}$ and $\theta\in(0,\pi/2)$. There exists a
set $S_{A}(\theta)\subseteq A$ consisting of at most ${(12/\theta)^{n}}$
points such that for all $x\in A$, there exists a point $y\in S_{A}(\theta)$
such that

$\angle(x,y)=\arccos{\left\langle x,y\right\rangle}\leq\theta.$

###### Proof.

Note that $\angle(x,y)\leq\theta$ for $x,y\in\mathbb{S}^{n-1}$ if and only if
$\|x-y\|=2\sin(\theta/2)$. It thus suffices to construct a
$2\sin(\theta/2)$-net (cf. Section 4.2 of [Ver18]) of $A$. From Exercise
4.2.10 of [Ver18], the size of such a net is upper bounded by the size of a
$\sin(\theta/2)$-net for $\mathbb{S}^{n-1}$, which in turn is at most

${\left(\frac{3}{\sin{\left(\theta/2\right)}}\right)}^{n}.$

This bound is standard; see, for example, Corollary 4.2.13 of [Ver18].
Finally, since $\sin(\cdot)$ is concave on the interval $[0,\pi/2]$, we have
that

$\sin{\left(\frac{\theta}{2}\right)}\geq\frac{\theta}{4},$

and so we have that the desired net consists of at most

${\left(\frac{12}{\theta}\right)}^{n}~{}\text{points},$

which completes the proof. ∎

We will construct the approximator $L$ by placing tangent hyperplanes to $K$
at the points in $S$ where we define

$S\mathrel{\mathop{\mathchar
58\relax}}=\bigsqcup_{k=1}^{k^{\ast}}S_{\mathrm{buck}(k)}(\theta^{\ast})$

where $S_{\mathrm{buck}(k)}(\theta^{\ast})$ is as in Lemma 25 for an
appropriate choice of $\theta^{\ast}$. It follows that the total number of
halfspaces in our approximator $L$ is at most

$|S|\leq
k^{\ast}\cdot{{\left(\frac{12}{\theta^{\ast}}\right)}^{n}}=\frac{1}{\tau}\log{\left(\frac{4}{\varepsilon\delta}\right)}\cdot{{\left(\frac{12}{\theta^{\ast}}\right)}^{n}},$
(10)

where $\tau$ and $\theta^{\ast}$ are parameters that we will set below.

###### Setting Parameters.

Setting the parameters $\tau$ and $\theta^{\ast}$ fixes our approximator $L$.
We will take

$\tau\mathrel{\mathop{\mathchar
58\relax}}=\frac{\varepsilon\delta}{8}\qquad\text{and}\qquad\theta^{\ast}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\varepsilon^{2}}{64}{\left(R{\left(2+\frac{16}{\varepsilon}\right)}{\left(2R^{2}{\left(2+\frac{16}{\varepsilon}\right)}-\frac{n}{4}\right)}\right)}^{-1}.$
(11)

Our choices above are dictated by the error analysis below; we note that it
follows from Equations 11 and 10 that $L$ has the desired number of
halfspaces. Before proceeding, we introduce the following notation:

######  Notation 26.

For $k\in[k^{\ast}]$, we define

$\ell(k)_{\max}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{v\in\mathrm{buck}(k)}\ell(v)\qquad\text{and}\qquad\ell(k)_{\min}\mathrel{\mathop{\mathchar
58\relax}}=\inf_{v\in\mathrm{buck}(k)}\ell(v).$

###### Error Analysis.

We will analyze the error in approximating $K$ by $L$ on a direction-by-
direction basis; recall that we only need to worry about the “bad” directions
(Equation 9). Fix a “bad” direction $v\in\mathbb{S}^{n-1}$, and suppose
$v\in\mathrm{buck}(k)$ (where $k\leq k^{\ast}$). Consider the two-dimensional
setup (corresponding to the two-dimensional plane $\mathrm{span}\\{O,U,W\\}$)
as in Figure 2:

  * •

Let $O$ denote the origin $0^{n}$;

  * •

Let $V\in\partial K$ be the point of intersection of the ray
$\\{tv\mathrel{\mathop{\mathchar 58\relax}}t\geq 0\\}$ and $\partial K$;

  * •

Let $U\in\partial K$, $U\in S_{\mathrm{buck}(k)}(\theta^{\ast})$ be a point in
$\mathrm{buck}(k)$ such that $\theta\mathrel{\mathop{\mathchar
58\relax}}=\angle(\vec{OL},\vec{ON})\leq\theta^{\ast}$; and

  * •

By construction, we put down a halfspace tangent to $K$ at $U$; let $W$ be the
point of intersection of this halfspace with the ray
$\\{tv\mathrel{\mathop{\mathchar 58\relax}}t\geq 0\\}$.

$\theta$$\kappa$$O$$U$$W$$V$$B(1)$$B(R)$$K$ Figure 2: A two-dimensional setup
to analyze the error of our approximator. Here $V\in\mathrm{buck}(k)$ and
$U\in S_{\mathrm{buck}(k)}(\theta^{\ast})$ and so
$\angle(\vec{OV},\vec{OU}){=\theta}\leq\theta^{\ast}$

With this setup in hand, note that the error incurred along direction $v$ is
given by

$\mathrm{error}(v)\mathrel{\mathop{\mathchar
58\relax}}=m{\left(\|V\|\right)}-m{\left(\|W\|\right)}.$

We will next establish that this quantity is at most $\varepsilon\delta/4$,
which will imply that the total error incurred from all the “bad” directions
is at most $\varepsilon\delta/4$. Note that

$\displaystyle\mathrm{error}(v)$
$\displaystyle=m{\left(\|V\|\right)}-m{\left(\|W\|\right)}$ $\displaystyle\leq
m{\left(\ell(k)_{\min}\right)}-m{\left(\|W\|\right)}$
$\displaystyle={\left(m{\left(\ell(k)_{\min}\right)}-m{\left(\ell(k)_{\max}\right)}\right)}+{\left(m{\left(\ell(k)_{\max}\right)}-m{\left(\|W\|\right)}\right)}.$
(12)

It suffices to show that Equation 12 is upper bounded by
$\varepsilon\delta/4$. Indeed, recall that we incurred (a)
$\varepsilon\delta/2$ error from “capping” the set $K$ by intersecting it with
$B(R)$; (b) $\varepsilon\delta/4$ error from the “bad” directions from
$\mathrm{buck}(k)$ for $k>k^{\ast}$; and finally (c) $\varepsilon\delta/4$
error from all of the “good” directions from Equation 12 (as we will establish
in the remainder of the argument); this will complete the proof of Theorem 20.

We will bound each term in Equation 12 separately. By definition of the
buckets (Definition 24), we have that

$m{\left(\ell(k)_{\min}\right)}-m{\left(\ell(k)_{\max}\right)}\leq\tau(1+\tau)^{-k}\leq\tau=\frac{\varepsilon\delta}{8}.$
(13)

In order to bound the second term in Equation 12, recall that by Brahmagupta’s
formula (cf. Figure 2), we have

$\frac{\sin(\pi-\kappa)}{\|W\|}=\frac{\sin(\kappa-\theta)}{\|U\|}.$

This can be rewritten as

$\|W\|=\frac{\sin\kappa}{\sin(\kappa-\theta)}\cdot\|U\|\leq\frac{\sin\kappa}{\sin(\kappa-\theta)}\cdot\ell(k)_{\max}.$
(14)

Recalling 23, since $B(1)\subseteq K\subseteq B(R)$, we have that

$\displaystyle\tan\kappa=\frac{\mathrm{dist}{\left(O,\overleftrightarrow{UW}\right)}}{\mathrm{dist}{\left(U,O\perp\overleftrightarrow{UW}\right)}}\geq\frac{1}{R}$

where we write $\mathrm{dist}(O,\overleftrightarrow{UW})$ to mean the distance
between the origin and the line $\overleftrightarrow{UW}$, which is guaranteed
to be at least $1$ thanks to the convexity of $K$ and the fact that
$B(1)\subseteq K$; and $\mathrm{dist}(U,O\perp\overleftrightarrow{UW})$ is the
distance between $U$ and the point on the line $\overleftrightarrow{UW}$
closest to $O$, which must be at most $\mathrm{dist}(O,U)$ (since the
hypotenuse is the longest side in a right triangle), which in turn is at most
$R$ by out setup. (See Figure 2.) Returning to Equation 14, the above lower
bound on $\tan\kappa$ implies that

$\frac{\sin\kappa}{\sin(\kappa-\theta)}=\frac{\sin\kappa}{\sin\kappa\cos\theta-\cos\kappa\sin\theta}=\frac{1}{\cos\theta-\frac{\sin\theta}{\tan\kappa}}\leq\frac{1}{\cos\theta-R\sin\theta}.$

For $\theta\geq 0$, recalling the standard trigonometric inequalities

$\sin\theta\leq\theta\qquad\text{and}\qquad\cos\theta\geq
1-\frac{\theta^{2}}{2},$

we thus get that

$\frac{\sin\kappa}{\sin(\kappa-\theta)}\leq\frac{1}{\cos\theta-R\sin\theta}\leq\frac{1}{1-R\theta-\frac{\theta^{2}}{2}}\leq
1+2R\theta\leq 1+2R\theta^{\ast}$

where the penultimate inequality can be readily verified from the definitions
of $R$ and $\theta$, and the final inequality relies on the fact that
$\theta\leq\theta^{\ast}$ since $U\in S_{\mathrm{buck}(k)}(\theta^{\ast})$ and
$V\in\mathrm{buck}(k)$.

Plugging the above bound back into Equation 14, we get that

$\|W\|\leq\ell(k)_{\max}{\left(1+2R\theta^{\ast}\right)}.$

As $m$ (cf. 22) is a decreasing function, we have that

$\displaystyle m{\left(\ell(k)_{\max}\right)}-m{\left(\|W\|\right)}$
$\displaystyle\leq
m{\left(\ell(k)_{\max}\right)}-m{\left(\ell(k)_{\max}{\left(1+2R\theta^{\ast}\right)}\right)}$
$\displaystyle=m{\left(\ell(k)_{\max}\right)}{\left(1-\frac{m{\left(\ell(k)_{\max}{\left(1+2R\theta^{\ast}\right)}\right)}}{m{\left(\ell(k)_{\max}\right)}}\right)}$
$\displaystyle\leq\delta\cdot{\left(1-\frac{m{\left(\ell(k)_{\max}{\left(1+2R\theta^{\ast}\right)}\right)}}{m{\left(\ell(k)_{\max}\right)}}\right)}$
(15)

where Equation 15 relies on the observation that $m(\ell(v))\leq\delta$ for
any direction $v\in\mathbb{S}^{n-1}$. To see this, note that if $tv\in\partial
K$ is such that $m(t)>\delta$, then the supporting hyperplane tangent to $K$
at $tv$ will “lop off” strictly greater than $\delta$ mass. Consequently,
$\mathrm{Vol}(K)<1-\delta$, which is a contradiction.

Now, note that it suffices to show that

$\frac{m{\left(\ell(k)_{\max}{\left(1+2R\theta^{\ast}\right)}\right)}}{m{\left(\ell(k)_{\max}\right)}}\geq
1-{\frac{\varepsilon}{8}}$ (16)

in order to complete the proof. The remainder of the proof establishes
Equation 16. We split into two cases depending on $\ell(k)_{\max}$:

###### Case 1: $\ell(k)_{\max}\geq{\sqrt{n-1}}$.

. Let $\Delta>0$ be a parameter that we will set later. We have

$\frac{m{\left(\ell(k)_{\max}(1+2R\theta^{*})\right)}}{m(\ell(k)_{\max})}\geq\frac{m{\left(\ell(k)_{\max}(1+2R\theta^{*})\right)}-m{\left(\ell(k)_{\max}(1+(2+\Delta)R\theta^{*})\right)}}{m(\ell(k)_{\max})-m{\left(\ell(k)_{\max}(1+(2+\Delta)R\theta^{*})\right)}}.$
(17)

Note that the right hand side of the above equation is

R.H.S. of (17)
$\displaystyle={\left(\int_{\ell(k)_{\max}(1+2R\theta^{\ast})}^{\ell(k)_{\max}(1+(2+\Delta)R\theta^{\ast})}\mathrm{pdf}_{\chi(n)}(x)\,dx\right)}{\left(\int_{\ell(k)_{\max}}^{\ell(k)_{\max}(1+(2+\Delta)R\theta^{\ast})}\mathrm{pdf}_{\chi(n)}(x)\,dx\right)}^{-1}$
$\displaystyle\geq\frac{\ell(k)_{\max}\Delta
R\theta^{\ast}\cdot\mathrm{pdf}_{\chi(n)}{\left(\ell(k)_{\max}(1+(2+\Delta)R\theta^{\ast})\right)}}{\ell(k)_{\max}(2+\Delta)R\theta^{\ast}\cdot\mathrm{pdf}_{\chi(n)}(\ell(k)_{\max})}$
(18)
$\displaystyle={\left(\frac{\Delta}{2+\Delta}\right)}\frac{\mathrm{pdf}_{\chi(n)}{\left(\ell(k)_{\max}(1+(2+\Delta)R\theta^{\ast})\right)}}{\mathrm{pdf}_{\chi(n)}(\ell(k)_{\max})}$
$\displaystyle\geq{\left(\frac{\Delta}{2+\Delta}\right)}\underbrace{{\left((1+(2+\Delta)R\theta^{\ast})^{n-1}\exp{\left(\frac{-R^{2}}{2}{\left(2(2+\Delta)R\theta^{\ast}+(2+\Delta)^{2}R^{2}{\theta^{\ast}}^{2}\right)}\right)}\right)}}_{=\mathrel{\mathop{\mathchar
58\relax}}\Upsilon(n,R,\theta^{\ast})},$ (19)

where (18) used the fact that the $\mathrm{pdf}_{\chi(n)}(x)$ is decreasing in
$x$ for $x\geq\sqrt{n-1}$ and (19) used the formula for the density function
of the $\chi(n)$-distribution, which is given by

$\mathrm{pdf}_{\chi(n)}(x)=\begin{cases}\frac{1}{2^{n/2-1}\Gamma(n/2)}x^{n-1}\exp{\left(-\frac{x^{2}}{2}\right)}&\mathrm{if}~{}x\geq
0\\\ 0&\mathrm{if}~{}x<0\end{cases},$

and the fact that $\ell(k)_{\max}\leq R$. (This is because we truncated $K$ by
intersecting it with $B(R)$.)

We will take

$\Delta\mathrel{\mathop{\mathchar 58\relax}}=\frac{16}{\varepsilon},$

as a consequence of which, Equation 16 follows from showing that

$\Upsilon(n,R,\theta^{\ast})\geq 1-\frac{\varepsilon^{2}}{64}.$

In particular, using the inequality $1+x\leq e^{x}$, it suffices to show that

$\Upsilon(n,R,\theta^{\ast})\geq\exp{\left(-\frac{\varepsilon^{2}}{64}\right)}.$

We have that

$\displaystyle\Upsilon(n,R,\theta^{\ast})$
$\displaystyle\geq{\left((1+(2+\Delta)R\theta^{\ast})^{n-1}\exp{\left(-2R^{3}\theta^{\ast}(2+\Delta)^{2}\right)}\right)}$
$\displaystyle\geq\exp{\left(\theta^{\ast}{\left({\left(\frac{2+\Delta}{4}\right)}nR-2R^{3}(2+\Delta)^{2}\right)}\right)}$
$\displaystyle=\exp{\left(-\frac{\varepsilon^{2}}{64}\right)},$

where the first inequality uses $R\theta^{\ast}\ll 1$, the second inequality
uses $1+x\geq e^{x/2}$ for $x\in[0,1]$, and the third inequality uses the
choice of $\theta^{\ast}$, which we recall was

$\theta^{\ast}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\varepsilon^{2}}{64}{\left(R{\left(2+\frac{16}{\varepsilon}\right)}{\left(2R^{2}{\left(2+\frac{16}{\varepsilon}\right)}-\frac{n}{4}\right)}\right)}^{-1}.$

###### Case 2: $\ell(k)_{\max}<{\sqrt{n-1}}$.

First, note that $\mathrm{pdf}_{\chi(n)}(x)$ is at most $1$ for all $x$. It
follows that

$\int_{\ell(k)_{\max}}^{\ell(k)_{\max}(1+2R\theta^{\ast})}\mathrm{pdf}_{\chi(n)}(x)\,dx\leq
2\ell(k)_{\max}R\theta^{\ast}\leq 2R\theta^{\ast}\sqrt{n}.$ (20)

Furthermore, since $\ell(k)_{\max}\leq{\sqrt{n-1}}$ which is the mode of the
$\chi(n)$-distribution it follows that

$m(\ell(k)_{\max})\geq\frac{1}{2}.$

This, together with Equation 20, lets us write

$\displaystyle\frac{m{\left(\ell(k)_{\max}{\left(1+2R\theta^{\ast}\right)}\right)}}{m{\left(\ell(k)_{\max}\right)}}$
$\displaystyle\geq\frac{m{\left(\ell(k)_{\max}\right)}-2R\theta^{\ast}\sqrt{n}}{m{\left(\ell(k)_{\max}\right)}}$
$\displaystyle\geq 1-4R\theta^{\ast}\sqrt{n}$ $\displaystyle\geq
1-\frac{\varepsilon}{8},$

establishing Equation 16 (the final inequality above is straightforward to
verify from our choice of $\theta^{\ast}$).

Putting both cases together completes the proof of the theorem. ∎

###  5 Improved Approximation for the $\ell_{2}$ Ball

For the Hausdorff and Lebesgue distance metrics (cf. Section 3.4), the
$\ell_{2}$ ball is often an extremal example for known upper bounds on the
vertex or facet complexity of polyhedral approximators [Dud74, BI76, B+97,
LSW06]. In this section, we show that—perhaps surprisingly—the
$\sqrt{n}$-radius $\ell_{2}$ ball $B(\sqrt{n})$, which has Gaussian volume
$1/2+o_{n}(1)$, can be approximated to within any constant error by an
intersection of only $2^{O(\sqrt{n})}$ many halfspaces. This is a substantial
improvement on the exponential-in-$n$ approximation upper bounds obtained in
Section 4 for general convex bodies.

Throughout this section, we will write ${B_{2}}\mathrel{\mathop{\mathchar
58\relax}}=B(\sqrt{n})$ for ease of notation (the “2” subscript is because we
are dealing with the $\ell_{2}$ ball).

######  Theorem 27.

Let $0<\varepsilon<c$ for some sufficiently small absolute constant $c$. Then
there exists a polytope $K$ which is the intersection of

$s=\exp{\left(\Theta{\left(\sqrt{n}\cdot\frac{1}{\varepsilon}\log{\left(\frac{1}{\varepsilon}\right)}\right)}\right)}~{}\text{halfspaces}$

such that $\mathrm{dist}_{\mathrm{G}}(B_{2},K)\leq\varepsilon.$

Theorem 27 is inspired by Theorem 2.1 of O’Donnell and Wimmer [OW07], which
shows that the $n$-bit majority function
$\mathrm{Maj}_{n}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\to\\{0,1\\}$, defined as

$\mathrm{Maj}_{n}(x)\mathrel{\mathop{\mathchar
58\relax}}=\mathbf{1}{\left\\{\sum_{i=1}^{n}x_{i}\geq n/2\right\\}},$

can be approximated by a monotone CNF formula of size $2^{O(\sqrt{n})}$.
O’Donnell and Wimmer’s construction is probabilistic and bears a close
resemblance to Talagrand’s random CNF [Tal96]. Our approach for approximating
$B$ employs a modification of a probabilistic construction of a convex body
due to Nazarov [Naz03]. Looking ahead, in Section 9 we will show that Theorem
27 is tight for constant $\varepsilon$; more precisely, we will show that any
$\varepsilon$-approximation to $B_{2}$ must have $2^{\Omega(\sqrt{n})}$ facets
for a suitable small constant $\varepsilon>0$.

To prove Theorem 27, we begin by defining a suitable distribution over
intersections of randomly chosen halfspaces:

######  Definition 28.

For $w,s>0$, we write $\mathrm{Naz}(w,s)$ to be the distribution over
$s$-facet polytopes in $\mathbb{R}^{n}$ where draw from $\mathrm{Naz}(w,s)$ is
obtained as follows:

  1. 1.

For $i\in[s]$, draw i.i.d. $\boldsymbol{g}^{(i)}\sim N(0,I_{n})$ and let
$\boldsymbol{H}_{i}$ denote the halfspace

$\boldsymbol{H}_{i}\mathrel{\mathop{\mathchar
58\relax}}={\left\\{x\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar
58\relax}}\langle x,\boldsymbol{g}^{(i)}\rangle\leq w\right\\}}.$

  2. 2.

Output the convex set $\mathbf{K}\mathrel{\mathop{\mathchar
58\relax}}=\bigcap_{i=1}^{s}\boldsymbol{H}_{i}$.

$\sqrt{n}$$\approx n^{1/4}$ Figure 3: A cartoon of how a polytope drawn from
$\mathrm{Naz}(w,s)$, for suitable $s=2^{\Theta(\sqrt{n})}$, $w\approx
n^{3/4}$, approximates the radius-$\sqrt{n}$ ball in $\mathbb{R}^{n}$. Our
depiction of ${B_{2}}=B(\sqrt{n})$ is inspired by Milman’s “hyperbolic”
drawings of high-dimensional convex sets [Mil98].

With Definition 28 in hand, we turn to the proof of Theorem 27:

###### Proof of Theorem 27.

We will show that there exists an outcome $K$ in the support of
$\mathrm{Naz}(w,s)$ for an appropriate choice of parameters $w$ and $s$ that
has the desired properties.

To show this, it suffices to show that

$\mathop{{\bf E}\/}_{\mathbf{K}\sim\mathrm{Naz}(w,s)}{\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim N(0,I_{n})}{\left[\mathbf{K}(\boldsymbol{x})\neq
B_{2}(\boldsymbol{x})\right]}\right]}\leq\varepsilon,$

which, by commuting the order of integration, is equivalent to showing that

$\mathop{{\bf E}\/}_{\boldsymbol{x}\sim N(0,I_{n})}{\left[\mathop{{\bf
Pr}\/}_{\mathbf{K}\sim\mathrm{Naz}(w,s)}{\left[\mathbf{K}(\boldsymbol{x})\neq
B_{2}(\boldsymbol{x})\right]}\right]}\leq\varepsilon.$ (21)

Equation 21 allows us to control the error on an “$x$-by-$x$ basis.” We set
parameters

$d_{\mathrm{in}}\mathrel{\mathop{\mathchar
58\relax}}=\sqrt{n}-\frac{\varepsilon}{4}\qquad\text{and}\qquad
d_{\mathrm{out}}\mathrel{\mathop{\mathchar
58\relax}}=\sqrt{n}+\frac{\varepsilon}{4}.$ (22)

We will show that when $\|x\|\leq d_{\mathrm{in}}$ or $\|x\|\geq
d_{\mathrm{out}}$,

$\mathop{{\bf Pr}\/}_{\mathbf{K}\sim\mathrm{Naz}(w,s)}{\left[\mathbf{K}(x)\neq
B_{2}(x)\right]}\leq\frac{\varepsilon}{2}.$ (23)

Since the Gaussian volume of the annulus
$\\{y\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar
58\relax}}d_{\mathrm{in}}\leq\|y\|\leq d_{\mathrm{out}}\\}$ is at most
$\frac{\varepsilon}{2}$ (this is an easy consequence of the standard fact that
for $n>1$, the pdf of the $\chi^{2}(n)$-distribution is everywhere at most 1),
this establishes Equation 21 which in turn completes the proof.

Note that by construction (Definition 28), for any fixed $x\in\mathbb{R}^{n}$
we have that

$\mathop{{\bf
Pr}\/}_{\mathbf{K}\sim\mathrm{Naz}(w,s)}{\left[x\in\mathbf{K}\right]}=\Phi{\left(\frac{w}{\|x\|}\right)}^{s}$

where $\Phi\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}\to[0,1]$ denotes
the cumulative density function of the univariate Gaussian distribution
$N(0,1)$. To see this, note that

$\langle
x,\boldsymbol{g}^{(j)}\rangle=\sum_{i=1}^{n}x_{i}\boldsymbol{g}^{(j)}_{i}\sim
N(0,\|x\|^{2})\quad\text{and so}\quad\mathop{{\bf
Pr}\/}_{\boldsymbol{g}^{(1)},\ldots,\boldsymbol{g}^{(s)}}{\left[\langle
x,\boldsymbol{g}^{(j)}\rangle\leq w~{}\text{for
all}~{}j\in[s]\right]}=\Phi{\left(\frac{w}{\|x\|}\right)}^{s}$

due to independence.

This observation informs our setting of the parameters $w$ and $s$. We take
$w$ to satisfy the equation

$\frac{1-\Phi(w/d_{\mathrm{out}})}{1-\Phi(w/d_{\mathrm{in}})}=\frac{4}{\varepsilon}\,{\ln}{\left(\frac{4}{\varepsilon}\right)}$
(24)

and take $s$ to be

$s\mathrel{\mathop{\mathchar
58\relax}}=\frac{\varepsilon}{4}{\left(1-\Phi{\left(\frac{w}{d_{\mathrm{in}}}\right)}\right)}^{-1}.$
(25)

(We will argue that there is a valid solution to Equation 24 later on in the
proof.) Given Equations 24 and 25,

  * •

For $x\in\mathbb{R}^{n}$ with $\|x\|\leq d_{\mathrm{in}}$, we have

$\mathop{{\bf
Pr}\/}_{\mathbf{K}\sim\mathrm{Naz}(w,s)}{\left[x\in\mathbf{K}\right]}=\Phi{\left(\frac{w}{\|x\|}\right)}^{s}\geq\Phi{\left(\frac{w}{d_{\mathrm{in}}}\right)}^{s}={\left(1-\frac{\varepsilon}{4s}\right)}^{s}\geq
1-\frac{\varepsilon}{4}$

where the first inequality relies on the fact that $\Phi(\cdot)$ is an
increasing function, the following equality relies on our choice of $s$ in
Equation 25, and the final inequality makes use of the fact that
$(1-a)^{b}\geq 1-ab$. As $\|x\|\leq d_{\mathrm{in}}$ implies that $x\in
B_{2}$, we pick up at most $\varepsilon/4$ error on such points.

  * •

For $x\in\mathbb{R}^{n}$ with $\|x\|\geq d_{\mathrm{out}}$, we have

$\displaystyle\mathop{{\bf
Pr}\/}_{\mathbf{K}\sim\mathrm{Naz}(w,s)}{\left[x\in\mathbf{K}\right]}=\Phi{\left(\frac{w}{\|x\|}\right)}^{s}$
$\displaystyle\leq\Phi{\left(\frac{w}{d_{\mathrm{out}}}\right)}^{s}={\left(1-\frac{4}{\varepsilon}{\left(1-\Phi{\left(\frac{w}{d_{\mathrm{in}}}\right)}\right)}{\ln}{\left(\frac{4}{\varepsilon}\right)}\right)}^{s}$
$\displaystyle={\left(1-\frac{1}{s}\,{\ln}{\left(\frac{4}{\varepsilon}\right)}\right)}^{s}$
$\displaystyle\leq\frac{\varepsilon}{4}$

where we once again used the fact that $\Phi(\cdot)$ is increasing in the
first inequality. The following equalities follow from rearranging Equations
24 and 25, and the final inequality is due to the fact that
$(1+x)\leq\exp(x)$. As $x\geq d_{\mathrm{out}}$ implies that $x\notin B_{2}$,
we pick up at most $\varepsilon/4$ error on such points as well.

In particular, the above establishes Equation 23, which in turn establishes
Equation 21 and so there exists a set $K$ in the support of
$\mathrm{Naz}(w,s)$ that $\varepsilon$-approximates $B_{2}$.

It remains to argue that there exists a valid solution to Equation 24, and to
bound the number of facets of $K$ (i.e. the parameter $s$); we start with the
former. Using standard Gaussian tail bounds (Proposition 12), provided that
$w/{d_{\mathrm{in}}},w/{d_{\mathrm{out}}}=\Omega(1)$ (which holds with room to
spare; below we will see that these quantities are $\Omega(n^{1/4})$), we can
write Equation 24 as

$\exp{\left(\frac{w^{2}}{2}{\left(\frac{1}{d_{\mathrm{in}}^{2}}-\frac{1}{d_{\mathrm{out}}^{2}}\right)}\right)}\cdot\Theta(1)=\frac{4}{\varepsilon}\,{\ln}{\left(\frac{4}{\varepsilon}\right)}.$

Taking logarithms on both sides, for $\varepsilon$ at most some sufficiently
small constant we get that

$w^{2}=\Theta{\left({\ln}{\left(\frac{4}{\varepsilon}\right)}+{\ln\ln}{\left(\frac{4}{\varepsilon}\right)}\right)}\cdot\frac{(d_{\mathrm{in}}d_{\mathrm{out}})^{2}}{d_{\mathrm{out}}^{2}-d_{\mathrm{in}}^{2}}.$

Recalling our choices of $d_{\mathrm{out}}$ and $d_{\mathrm{in}}$, we have

$\frac{(d_{\mathrm{in}}d_{\mathrm{out}})^{2}}{d_{\mathrm{out}}^{2}-d_{\mathrm{in}}^{2}}=\frac{{\left(n-\varepsilon^{2}/16\right)}^{2}}{\varepsilon\sqrt{n}}=\Theta{\left(\frac{n^{3/2}}{\varepsilon}\right)}.$

Plugging this back into the previous expression and taking square roots on
both sides gives

$w\mathrel{\mathop{\mathchar
58\relax}}=\Theta{\left({n^{3/4}}\sqrt{\frac{1}{\varepsilon}{\left({\ln}{\left(\frac{4}{\varepsilon}\right)}+{\ln\ln}{\left(\frac{4}{\varepsilon}\right)}\right)}}\right)}.$
(26)

This lets us bound $s$, which is the number of facets of $K$. From Equation 25
and once again using standard tail bounds (Proposition 12), we have

$\displaystyle
s=\frac{\varepsilon}{4}{\left(1-\Phi{\left(\frac{w}{d_{\mathrm{in}}}\right)}\right)}^{-1}$
$\displaystyle{\leq}\frac{\varepsilon}{4}\exp{\left(\frac{w^{2}}{2d_{\mathrm{in}}^{2}}\right)}{\left(\frac{d_{\mathrm{in}}}{w}-\frac{d_{\mathrm{in}}^{3}}{w^{3}}\right)}$
$\displaystyle\leq\exp{\left(\Theta{\left(\frac{w^{2}}{d_{\mathrm{in}}^{2}}\right)}\right)}.$

From Equations 22 and 26 we get that

$\frac{w}{d_{\mathrm{in}}}=\Theta{\left(n^{1/4}\sqrt{\frac{1}{\varepsilon}{\left(\log{\left(\frac{4}{\varepsilon}\right)}+\log\log{\left(\frac{4}{\varepsilon}\right)}\right)}}\right)},$

from which the claimed bound on $s$ is immediate. ∎

###  6 Improved Approximations for $\ell_{p}$ Balls for $p\in[1,2)$

The main result of this section is a proof of the existence of approximators
with a sub-exponential number of facets for the $\ell_{p}$ balls $B_{p}$,
where $1\leq p<2$:

######  Theorem 29.

For $1\leq p<2$, let $B_{p}$ denote the origin-centered $\ell_{p}$ ball in
$\mathbb{R}^{n}$ defined in Equation 30 below, which has
$\mathrm{Vol}(B_{p})={\frac{1}{2}}\pm o_{n}(1).$ Let $\frac{1}{\sqrt{\log
n}}\leq\varepsilon<\tau$ where $\tau\in(0,1)$ is some absolute constant. Then
for $1\leq p<2$, there exists a polytope $K_{p}$ which is the intersection of

${s=\exp{\left(\Theta{\left({\left({\frac{\log^{9/4}(1/\varepsilon)}{\varepsilon^{4}}}\right)}\cdot\log{\left({\frac{n}{\varepsilon}}\right)}\cdot
n^{3/4}\right)}\right)}~{}\text{halfspaces}}$ (27)

such that $\mathrm{dist}_{\mathrm{G}}(B_{p},K_{p})\leq\varepsilon.$ In the
special case of $p=1$, we have a slightly improved bound of

$s=\exp{\left(\Theta{\left({\left(\frac{\log(1/\varepsilon)}{\varepsilon}\right)}^{3/2}n^{3/4}\right)}\right)}~{}\text{halfspaces}$
(28)

(see Remark 38).

We remark that the approximation results of Theorem 29 can be extended to the
$\ell_{p}$ balls of volume exactly $1/2$; we work with $B_{p}$ instead because
it is more convenient. In Section 6.1 we give some basic setup and recall some
Cramér-type tail bounds on sums of random variables which we will use; the key
property of these bounds which we will exploit is that they give tight
_multiplicative_ control on the relevant tails. We will then prove Theorem 29
in Section 6.2.

####  6.1 Cramér-Type Large Deviations Bounds and General Setup

Roughly speaking, “Cramér-type” tail bounds are results which state that under
suitable conditions, a sum $\boldsymbol{S}$ of random variables for which
$\operatorname{{\bf E}}[\boldsymbol{S}]=0$ and $\operatorname{{\bf
Var}}[\boldsymbol{S}]=1$ will have tail probabilities $\operatorname{{\bf
Pr}}[\boldsymbol{S}\geq x]$ which are _multiplicatively_ close to the
corresponding Gaussian tail bound $\operatorname{{\bf Pr}}_{\boldsymbol{g}\sim
N(0,1)}[\boldsymbol{g}\geq x].$ The most standard results of this type are for
sums of _independent_ random variables, as in the following theorem:

######  Theorem 30 (Theorem 1 from Chapter VIII of [Pet12]).

Let $\boldsymbol{X}_{1},\ldots,\boldsymbol{X}_{n}$ be i.i.d. random variables
that satisfy Cramér’s condition, i.e., there exists constant $H>0$ such that
$\mathbf{E}[e^{H\boldsymbol{X}_{1}}]<\infty$.

Let us assume that the variables $\boldsymbol{X}_{i}$ are centered — i.e.
$\mathbf{E}[\boldsymbol{X}_{1}]=0$ and $\operatorname{{\bf
Var}}[\boldsymbol{X}_{1}]=\sigma^{2}$. Let
$\boldsymbol{S}_{n}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=1}^{n}\boldsymbol{X}_{i}$ and define
$F_{n}(x)\mathrel{\mathop{\mathchar 58\relax}}=\operatorname{{\bf
Pr}}[\boldsymbol{S}_{n}\leq x\sigma\sqrt{n}]$. If $x>0$ and $x=o(\sqrt{n})$,
then

$\frac{1-F_{n}(x)}{1-\Phi(x)}=\exp\bigg{(}\frac{x^{3}}{\sqrt{n}}\cdot\lambda\bigg{(}\frac{x}{\sqrt{n}}\bigg{)}\bigg{)}\cdot\bigg{(}1+O\bigg{(}\frac{x+1}{\sqrt{n}}\bigg{)}\bigg{)}.$

Here $\lambda(t)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{k=0}^{\infty}a_{k}t^{k}$ is a power series whose coefficients
$\\{a_{k}\\}$ depend only on the cumulants of the random variable
$\boldsymbol{X}_{1}$. Furthermore, the disc of convergence of this series has
a positive radius.

We will also require a Cramér-type bound, due to [HRW07], for when the sum is
a sum of randomly chosen values that are drawn _without_ replacement from a
finite population. In more detail, let
$\boldsymbol{X}_{1},\ldots,\boldsymbol{X}_{m}$ be a random sample drawn
without replacement from a finite population $\\{a_{1},\ldots,a_{n}\\}$ with

$\sum_{i=1}^{n}a_{i}=0\qquad\text{and}\qquad\sum_{i=1}^{n}a_{i}^{2}=n,$

where $m<n$. We will write

$\boldsymbol{S}_{m}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=1}^{m}\boldsymbol{X}_{i},\quad p\mathrel{\mathop{\mathchar
58\relax}}=\frac{m}{n},\quad q\mathrel{\mathop{\mathchar
58\relax}}=1-p,\quad\text{and}\quad\omega_{n}^{2}\mathrel{\mathop{\mathchar
58\relax}}=npq.$

######  Theorem 31 (Theorem 1.2 of [HRW07]).

There exists an absolute constant $A>0$ such that

${\mathop{{\bf Pr}\/}{\left[\boldsymbol{S}_{m}\geq
t\omega_{n}\right]}={\left(1-\Phi(t)\right)}{\left(1+O(1)(1+t)^{3}\frac{\beta_{3n}}{\omega_{n}}\right)}}$

for $0\leq
t\leq{{\frac{1}{A}}\cdot}\min{\left\\{\frac{\omega_{n}}{\max_{k}|a_{k}|},{\left(\frac{\omega_{n}}{\beta_{3n}}\right)}^{1/3}\right\\}}$,
where $\beta_{3n}\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
E}\/}{\left[|\boldsymbol{X}_{1}|^{3}\right]}$.

###### The $\ell_{p}$ Balls $B_{p}$.

For $1\leq p\leq 2$, let $\mathcal{A}_{p}$ denote the $p$-absolute moment of a
standard univariate Gaussian random variable,

$\mathcal{A}_{p}\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
E}\/}_{\boldsymbol{g}\sim N(0,1)}{\left[|\boldsymbol{g}|^{p}\right]},$

so e.g. $\mathcal{A}_{1}=\sqrt{\frac{2}{\pi}},\mathcal{A}_{2}=1$, and in
general we have

$\mathcal{A}_{p}=\sqrt{\frac{2^{p}}{\pi}}\Gamma{\left(\frac{p+1}{2}\right)}.$
(29)

(See, for example, Equation 18 of [Win12].) We define the ball
$B_{p}\subset\mathbb{R}^{n}$ to be

$B_{p}\mathrel{\mathop{\mathchar 58\relax}}={\left\\{x\in\mathbb{R}^{n}\
\mathrel{\mathop{\mathchar 58\relax}}\
\sum_{i=1}^{n}|x_{i}|^{p}=n\mathcal{A}_{p}\right\\}},\quad\text{i.e.}\quad
B_{p}\mathrel{\mathop{\mathchar 58\relax}}={\left\\{x\in\mathbb{R}^{n}\
\mathrel{\mathop{\mathchar 58\relax}}\
\|x\|_{p}=n^{1/p}\mathcal{A}_{p}^{1/p}\right\\}}.$ (30)

(Note that this agrees with our definition of $B_{2}=B(\sqrt{n})$ from Section
5.) It follows from the Berry–Esseen theorem [Ber41, Ess42] that for each
value of $1\leq p\leq 2$ we have $\mathrm{Vol}(B_{p})={1/2}\pm o_{n}(1)$.

####  6.2 Proof of Theorem 29

The proof will proceed in three steps:

  * •

First, we show (Theorem 32) that $B_{p}$ can be $\varepsilon$-approximated by
an intersection of $m$-dimensional “juntas” that each have very large volume.
As in our earlier construction of an approximator for the $\ell_{2}$ ball, the
construction will be probabilistic, but it is a very different probabilistic
construction from the $\ell_{2}$ ball construction of Theorem 27 (in
particular, it makes essential use of the Cramér-type bound (Theorem 31) for
sums of independent random variables drawn without replacement from a finite
population).

  * •

Next (Theorem 39) we get a high-accuracy estimate of the Gaussian volume
$1-\delta$ of each of these juntas, by determining the value of $\delta$ up to
a small multiplicative factor. This argument uses Petrov’s Cramér-type bound
(Theorem 30) for sums of i.i.d random variables.

  * •

Finally, we combine our high-accuracy estimate of $\delta$ with our “relative-
error” universal approximation bound (Theorem 20) for sets of volume
$1-\delta$ to show that each of the juntas can be approximated by an
intersection of not-too-many halfspaces.

The theorem then follows immediately. We note that for the special case when
$p=1$, the second and third steps are not required to obtain a
$2^{O_{\varepsilon}(n^{3/4})}$-facet approximator for the cross-polytope; this
is because the juntas used in the approximator themselves are polytopes, and
hence do not need to be approximated by a polytope using the universal
“relative-error” bound. (See Remark 38 for more on this.)

#####  6.2.1 Approximating $B_{p}$ by an Intersection of Juntas

Let us say that a set $S\subseteq\mathbb{R}^{n}$ is an _$m$ -junta_ if $S$
depends on at most $m$ directions in $\mathbb{R}^{n}$. More precisely, “$S$ is
an $m$-junta” means that there are $m$ orthogonal directions
$v_{1},\dots,v_{m}\in\mathbb{R}^{m}$ such that for every
$x,y\in\mathbb{R}^{n}$, if $v_{i}\cdot x=v_{i}\cdot y$ for all $i\in[m]$ then
$S(x)=S(y).$

The main result of this section is a proof that the set $B_{p}$ is close to an
intersection of “not too many” $m$-juntas, where $m$ is “not too large” (and
moreover, all of the directions for all of the $m$-juntas belong to
$\\{e_{1},\dots,e_{m}\\}$):

######  Theorem 32 (Approximating $B_{p}$ by an intersection of $m$-juntas).

Let $1\leq p<2$ and let $\varepsilon$ be as in Theorem 29. There is an
intersection $L=\bigcap_{j=1}^{M}C_{j}$ of $M$ many $m$-juntas in the support
of the distribution $\mathcal{D}(M,m,\theta)$ defined in Definition 33 below
which has $\mathrm{dist}_{\mathrm{G}}(L,B_{p})\leq O(\varepsilon)$, where $M$
is as given in Equation 44 and $m$ is as given in Equation 51.

In the rest of this section we prove Theorem 32. Fix a value $1\leq p<2.$ We
start by introducing the following distribution over convex sets in
$\mathbb{R}^{n}$:

######  Definition 33.

Let $M,m\geq 0$ be integers and let $\theta\geq 0$. We define
$\mathcal{D}(M,m,\theta)$ to be the distribution over convex sets in
$\mathbb{R}^{n}$ where a draw $\boldsymbol{L}\sim\mathcal{D}(M,m,\theta)$ is
obtained as follows:

  1. 1.

Draw $M$ $m$-tuples from $[n]$ without replacement, i.e. draw

${\left(\boldsymbol{i}^{(j)}_{1},\ldots,\boldsymbol{i}^{(j)}_{m}\right)}\in{[n]\choose
m}\quad\text{for}~{}1\leq j\leq M.$

  2. 2.

For $j\in[M]$, define the convex set

$\boldsymbol{C}_{j}\mathrel{\mathop{\mathchar
58\relax}}={\left\\{x\in\mathbb{R}^{n}\mathrel{\mathop{\mathchar
58\relax}}\sum_{k=1}^{m}|x_{\boldsymbol{i}^{(j)}_{k}}|^{p}\leq\theta\right\\}}.$

  3. 3.

Output the convex set

$\boldsymbol{L}\mathrel{\mathop{\mathchar
58\relax}}=\bigcap_{j=1}^{M}\boldsymbol{C}_{j}.$

As in the proof of Theorem 27, the existence of a set $L$ in the support of
the distribution ${\mathcal{D}(M,m,\theta)}$ that
$O(\varepsilon)$-approximates $B_{p}$ follows from

$~{}\mathop{{\bf
E}\/}_{\boldsymbol{L}\sim\mathcal{D}(M,m,\theta)}{\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\boldsymbol{L}(\boldsymbol{x})\neq
B_{p}(\boldsymbol{x})\right]}\right]}\leq O(\varepsilon),$ (31)

which, by commuting the order of integration, is equivalent to showing that

$\mathop{{\bf E}\/}_{\boldsymbol{x}\sim N(0,I_{n})}{\left[\mathop{{\bf
Pr}\/}_{\boldsymbol{L}\sim\mathcal{D}(M,m,\theta)}{\left[\boldsymbol{L}(\boldsymbol{x})\neq
B_{p}(\boldsymbol{x})\right]}\right]}\leq O(\varepsilon).$ (32)

As in the earlier argument, Equation 32 allows us to analyze the error
incurred by our approximator on an “$x$-by-$x$ basis.” For convenience, we
define

$\mu_{p}\mathrel{\mathop{\mathchar 58\relax}}=\mathop{{\bf
E}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\|\boldsymbol{x}\|_{p}^{p}\right]}=n\mathcal{A}_{p}\qquad\text{and}\qquad\sigma_{p}^{2}\mathrel{\mathop{\mathchar
58\relax}}=\mathop{{\bf Var}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\|\boldsymbol{x}\|_{p}^{p}\right]}=n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}.$
(33)

By the Berry-Esseen central limit theorem, we have that for
$\boldsymbol{x}\sim N(0,I_{n})$,

$d_{\mathrm{CDF}}{\left(\|\boldsymbol{x}\|_{p}^{p},N{\left(\mu_{p},\sigma_{p}^{2}\right)}\right)}=O{\left(\frac{1}{\sqrt{n}}\right)}$

where $d_{\mathrm{CDF}}$ denotes Kolmogorov or CDF distance. This observation
in turn motivates the following parameter definitions:

$~{}d_{\mathrm{in}}\mathrel{\mathop{\mathchar
58\relax}}=\mu_{p}-\varepsilon\sigma_{p}\qquad\text{and}\qquad
d_{\mathrm{out}}\mathrel{\mathop{\mathchar
58\relax}}=\mu_{p}+\varepsilon\sigma_{p}.$ (34)

By the Berry–Esseen theorem, for $\varepsilon$ as in the statement of Theorem
29, we have that

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[d_{\mathrm{in}}\leq\|\boldsymbol{x}\|_{p}^{p}\leq
d_{\mathrm{out}}\right]}=O(\varepsilon).$ (35)

Intuitively, we will “give up” on points $x$ with
$d_{\mathrm{in}}\leq\|x\|_{p}^{p}\leq d_{\mathrm{out}}$, and in the rest of
the argument our focus will be on achieving high accuracy on most other
points. Towards this end, the following definition will be useful:

######  Definition 34.

Let $x\in\mathbb{R}^{n}$ be a point with
$\|x\|^{p}_{p}\notin(d_{\mathrm{in}},d_{\mathrm{out}})$. If $\|x\|_{p}^{p}\leq
d_{\mathrm{in}}$, let $z=sx$ be the point with $\|z\|_{p}^{p}=d_{\mathrm{in}}$
(so $s\geq 1$ in this case), and if $\|x\|_{p}\geq d_{\mathrm{out}}$, let
$z=sx$ be the point with $\|z\|_{p}^{p}=d_{\mathrm{out}}$ (so $s\leq 1$ in
this case). We say that $x$ is _good_ if $z$ satisfies the following:

  1. 1.

$\|z\|_{2p}^{2p}-\frac{\|z\|_{p}^{2p}}{n}\in{\left[n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1-\frac{O(1)}{n^{5/12}}\right)},n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1+\frac{O(1)}{n^{5/12}}\right)}\right]}$;

  2. 2.

$\max_{i\in[n]}|z_{i}|^{p}={\left(\Theta(\log n)\right)}^{p/2}$; and

  3. 3.

$n^{-1}\sum_{i=1}^{n}|z_{i}|^{3p}=\Theta(1)$.

If $x$ is not good (this includes the possibility that
$\|x\|_{p}^{p}\in(d_{\mathrm{in}},d_{\mathrm{out}})$), we say that it is
_bad_.

We claim that with probability at least $1-O(\varepsilon)$, a draw from
$N(0,I_{n})$ is good:

######  Claim 35.

For $\boldsymbol{x}\sim N(0,I_{n})$, $\mathop{{\bf
Pr}\/}{\left[\boldsymbol{x}~{}\text{is bad}\right]}=O(\varepsilon).$

###### Proof.

Let $\boldsymbol{x}\sim N(0,I_{n})$ and let $\boldsymbol{s}^{\prime}>0$ be the
rescaling factor such that $\boldsymbol{z}\mathrel{\mathop{\mathchar
58\relax}}=\boldsymbol{s}^{\prime}\boldsymbol{x}$ has
$\|\boldsymbol{z}\|^{p}_{p}={\mu_{p}}$. The Berry-Esseen theorem, together
with standard tail bounds on the $N(\mu_{p},\sigma_{p}^{2})$ Gaussian
distribution (recall Equation 33), implies that with probability
$1-O(\varepsilon)$,

$\boldsymbol{s}^{\prime}={\left(1\pm{\frac{O(1)}{n^{5/12}}}\right)}.$

Since both $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are within a
multiplicative $(1\pm O({\frac{1}{\sqrt{n}}}))$-factor of $\mu_{p}$, it
suffices to show that each of Items 1, 2, and 3 from Definition 34 hold with
$\boldsymbol{x}$ rather than $\boldsymbol{z}=\boldsymbol{s}\boldsymbol{x}$ in
the relevant expression on the left-hand side, with probability
$1-O(\varepsilon)$; we do this below.

For Item 1, note that by Chebyshev’s inequality, with probability at least
$1-\varepsilon$,

$\|\boldsymbol{x}\|_{p}^{p}\in{\left[\mu_{p}-\frac{\sigma_{p}}{\sqrt{\varepsilon}},\mu_{p}+\frac{\sigma_{p}}{\sqrt{\varepsilon}}\right]}.$

In particular, it follows that with probability at least $1-2\varepsilon$, we
have

$\displaystyle\|{\boldsymbol{x}}\|_{2p}^{2p}-\frac{\|{\boldsymbol{x}}\|_{p}^{2p}}{n}$
$\displaystyle\in{\left[\mu_{2p}-\frac{\mu_{p}^{2}}{n}-\frac{\sigma_{p}^{2}}{n\varepsilon}\pm{\left(\frac{n\sigma_{2p}+2\mu_{p}\sigma_{p}}{n\sqrt{\varepsilon}}\right)}\right]}.$
Recalling the expressions for $\mu_{p}$ and $\sigma^{2}_{2p}$ in terms of
$\mathcal{A}_{p}$ and $\mathcal{A}_{2p}$ (cf. Equation 33), we have
$\displaystyle\|{\boldsymbol{x}}\|_{2p}^{2p}-\frac{\|{\boldsymbol{x}}\|_{p}^{2p}}{n}$
$\displaystyle\in{\left[n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}-\frac{(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2})}{\varepsilon}\pm\frac{\Theta_{p}(\sigma_{2p})}{\sqrt{\varepsilon}}\right]}$
$\displaystyle={\left[n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1\pm\frac{\Theta_{p}(1)}{\sqrt{n}{\varepsilon}}\right)}\right]}$
$\displaystyle\subseteq{\left[n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1\pm\frac{\Theta_{p}(1)}{n^{5/12}}\right)}\right]}$

where the final containment is due to our lower bound on $\varepsilon$ in the
statement of Theorem 29.

For Item 2, by a standard Gaussian tail bound (Proposition 12) we have that

$\operatorname{{\bf Pr}}{\left[|\boldsymbol{x}_{i}|^{p}>{\left(2\sqrt{(\ln
n)}\right)}^{p}\right]}=\operatorname{{\bf
Pr}}{\left[|\boldsymbol{x}_{i}|>2\sqrt{\ln n}\right]}<\frac{1}{n^{2}}$

for each $i\in[n],$ so a union bound over all $i\in[n]$ gives that

$\operatorname{{\bf
Pr}}{\left[\max_{i\in[n]}|\boldsymbol{x}_{i}|^{p}\leq{\left(2\sqrt{(\ln
n)}\right)}^{p}\right]}>1-{\frac{1}{n}},$

which is at least $1-\varepsilon$.

Turning to Item 3, note that

$\mathop{{\bf E}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\sum_{i=1}^{n}|\boldsymbol{x}_{i}|^{3p}\right]}=n\mathcal{A}_{3p}\qquad\text{and}\qquad\mathop{{\bf
Var}\/}_{\boldsymbol{x}\sim
N(0,I_{n})}{\left[\sum_{i=1}^{n}|\boldsymbol{x}_{i}|^{3}\right]}\leq
n\mathcal{A}_{6p}.$

Consequently, by Chebyshev’s inequality we have that with probability at least
$1-\varepsilon$ over the draw of $\boldsymbol{x}\sim N(0,I_{n})$, the
following holds:

$\mathcal{A}_{3p}-\frac{{\sqrt{\mathcal{A}_{6p}}}}{\sqrt{\varepsilon
n}}\leq\frac{1}{n}\sum_{i=1}^{n}|\boldsymbol{x}_{i}|^{3}\leq\mathcal{A}_{3p}+\frac{{\sqrt{\mathcal{A}_{6p}}}}{\sqrt{\varepsilon
n}}.$

Since $p\in[1,2)$, we have that both ${\cal M}_{3p}$ and ${\cal M}_{6p}$ are
$\Theta(1)$ (cf. Equation 29). Recalling the lower bound on $\varepsilon$ then
immediately implies Item 3. ∎

We will show that for an appropriate choice of parameters $M,m,$ and $\theta$,
we have that whenever $\|x\|_{1}\notin(d_{\mathrm{in}},d_{\mathrm{out}})$ and
$x$ is good,

$\mathop{{\bf
Pr}\/}_{\boldsymbol{L}\sim\mathcal{D}(M,m,\theta)}{\left[\boldsymbol{L}(x)\neq
B_{1}(x)\right]}\leq O(\varepsilon).$ (36)

Equations 36 and 35, together with 35, immediately imply Equation 32, which
completes the proof of Theorem 29.

###### Case 1: $\|x\|_{p}^{p}\leq d_{\mathrm{in}}$ and $x$ is good.

In this case, note that $B_{p}(x)=1$, and so it suffices to show that for any
fixed $j\in[M]$, we have

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\in\boldsymbol{C}_{j}\right]}\geq
1-\frac{O(1)\cdot\varepsilon}{M},$ (37)

since this immediately implies that

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\in\bigcap_{j=1}^{M}\boldsymbol{C}_{j}\right]}\geq{\left(1-\frac{O(1)\cdot\varepsilon}{M}\right)}^{M}\geq
1-O(\varepsilon),$

as desired.

We will require the following monotonicity claim, which allows us to consider
points with maximal $\ell_{p}$ norm. (This claim is why the definition of a
“good” point $x$, Definition 34 above, used the rescaled point $z=sx$.)

######  Claim 36.

Let $x\in\mathbb{R}^{n}$ have $\|x\|_{p}^{p}\leq d_{\mathrm{in}}$. Let $z=sx$
for $s\geq 1$ be such that $\|z\|_{p}^{p}=d_{\mathrm{in}}$. Then

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{n}|z_{\boldsymbol{i}^{(j)}_{k}}|^{p}\geq\theta\right]}\geq\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{n}|x_{\boldsymbol{i}^{(j)}_{k}}|^{p}\geq\theta\right]}.$

###### Proof.

The claim is immediate from the fact that the map

$|x_{\boldsymbol{i}^{(j)}_{k}}|^{p}\mapsto
s^{p}|x_{\boldsymbol{i}^{(j)}_{k}}|^{p}=|z_{\boldsymbol{i}^{(j)}_{k}}|^{p}$

gives a monotone coupling between the two random variables, and hence
$|z_{\boldsymbol{i}^{(j)}_{k}}|^{p}$ stochastically dominates
$|x_{\boldsymbol{i}^{(j)}_{k}}|^{p}$ (cf. Theorem 4.2.3 of [Roc23]). ∎

As in 36, let $z=sx$ for $s\geq 1$ be such that
$\|z\|_{p}^{p}=d_{\mathrm{in}}$. Let $z^{p}$ denote the vector

$z^{(p)}\mathrel{\mathop{\mathchar
58\relax}}={\left(|z_{1}|^{p},\ldots,|z_{n}|^{p}\right)}.$

In particular, note that $\|z^{{(p)}}\|_{1}=\|z\|_{p}^{p}$. We observe that
since $x$ is good, the point $z$ satisfies Items 1 through 3 of Definition 34.

We will make use of the Cramér-type bound given by Theorem 31 to prove
Equation 37. In order to apply Theorem 31, let

$v\mathrel{\mathop{\mathchar
58\relax}}=z^{(p)}-\frac{\|z\|_{p}^{p}(1,\ldots,1)}{n}\qquad\text{and
so}\qquad\sum_{i=1}^{n}v_{i}=0.$

Note that

$\displaystyle\sum_{i=1}^{n}v_{i}^{2}$
$\displaystyle=\|z\|_{2p}^{2p}-\sum_{i=1}^{n}{\left(\frac{2|z_{i}|^{p}\|z\|_{p}^{p}}{n}-\frac{\|z\|_{p}^{2p}}{n^{2}}\right)}$
$\displaystyle=\|z\|_{2p}^{2p}-\frac{\|z\|_{p}^{p}}{n}{\left(\sum_{i=1}^{n}2|z_{i}|^{p}-\frac{\|z\|_{p}^{p}}{n}\right)}$
$\displaystyle=\|z\|_{2p}^{2p}-\frac{\|z\|_{p}^{2p}}{n}$
$\displaystyle\in{\left[n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1\pm\frac{\Theta_{p}(1)}{n^{5/12}}\right)}\right]}$

by Item 1 of Definition 34. In particular, let $c_{x}$ be such that

$\sum_{i=1}^{n}v_{i}^{2}=c_{x}n,\quad\text{i.e.}\quad
c_{x}={\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1\pm\frac{\Theta_{p}(1)}{n^{5/12}}\right)}.$

For notational convenience, we define

$c\mathrel{\mathop{\mathchar
58\relax}}={\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}\qquad\text{and
so}\qquad c_{x}=c{\left(1\pm\frac{\Theta_{p}(1)}{n^{5/12}}\right)}.$ (38)

We will apply Theorem 31 to the finite population $\\{a_{i}\\}_{i\in[n]}$,
where

$a_{i}\mathrel{\mathop{\mathchar 58\relax}}=\frac{v_{i}}{\sqrt{c_{x}}}.$

It is immediate that $\sum_{i=1}^{n}a_{i}=0$ and that
$\sum_{i=1}^{n}a_{i}^{2}=n$, as required by Theorem 31. Furthermore, we have

$~{}\omega_{n}^{2}=m{\left(1-\frac{m}{n}\right)}.$ (39)

Since $x$ is good, by Item 2 of Definition 34 we have that
$\max_{k}|a_{k}|={\left(\Theta(\log n)\right)}^{p/2}$, and by Item 3 of
Definition 34 we have that $\beta_{3n}=\Theta(1)$. It follows from Theorem 31
that for any fixed $j\in[M],$ with $\boldsymbol{C}_{j}$ as in Definition 33,
we have

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[a_{\boldsymbol{i}^{(j)}_{1}}+\ldots+a_{\boldsymbol{i}^{(j)}_{m}}\geq{t\omega_{n}}\right]}={\left(1-\Phi(t)\right)}{\left(1+\frac{O(1)(1+t)^{3}}{\sqrt{m}}\right)}$
(40)

for $t\leq O{\left(\min{\left\\{\sqrt{m/(\log
n)^{p}},m^{1/6}\right\\}}\right)}=O(m^{1/6})$, where we used
$\omega_{n}^{2}=\Theta(m)$ which holds given our ultimate choice of $m$, see
Equation 51, using the lower bound

$\frac{1}{\sqrt{\log n}}\leq\varepsilon$

from the theorem statement.

Let us relate the probability in the L.H.S. of Equation 40 to our goal
probability, which is the L.H.S. of Equation 37. Recalling that

$a_{i}=c_{x}^{-1/2}{\left(z^{(p)}_{i}-\frac{\|z\|_{p}^{p}}{n}\right)},$

the event
$a_{\boldsymbol{i}^{(j)}_{1}}+\ldots+a_{\boldsymbol{i}^{(j)}_{m}}\geq{t\omega_{n}}$
is the same as the event

$\frac{1}{\sqrt{c_{x}}}\sum_{k=1}^{m}{\left(z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}-\frac{\|z\|_{p}^{p}}{n}\right)}\geq{t\omega_{n}},\qquad\text{or
equivalently}\qquad\sum_{k=1}^{m}z_{\boldsymbol{i}^{(j)}_{k}}^{(p)}\geq\|{z}\|_{p}^{p}\frac{m}{n}+\sqrt{c_{x}}{t\omega_{n}}.$

This motivates our choice of $\theta$, which corresponds to the RHS of the
second inequality above (but with $c$ in place of $c_{x}$, since the
definition of $\theta$ cannot depend on the specific point $x$), where we fix

$t\mathrel{\mathop{\mathchar
58\relax}}=c_{1}m^{1/6},\quad\quad\text{where~{}}c_{1}\mathrel{\mathop{\mathchar
58\relax}}=c_{1}(\varepsilon)={c_{2}\cdot{\frac{\varepsilon^{2}}{\ln(1/\varepsilon)}}}$
(41)

for an absolute constant $c_{2}>0$. In more detail, recalling that
$\|z\|_{p}^{p}=d_{\mathrm{in}}$, we take

$\theta\mathrel{\mathop{\mathchar
58\relax}}=d_{\mathrm{in}}\frac{m}{n}+{\sqrt{c}c_{1}m^{1/6}\omega_{n}},$ (42)

and we take $M$ to be

$M\mathrel{\mathop{\mathchar 58\relax}}={\frac{\varepsilon}{1-\Phi(t)}}.$ (43)

Note that by a standard Gaussian tail bound and our choice of $t$, we have

$M=\varepsilon\cdot\exp(\Theta(c_{1}^{2}m^{1/3}))=\varepsilon\cdot\exp{\left(\Theta{\left({\frac{\varepsilon^{4}}{\ln^{2}(1/\varepsilon)}}m^{1/3}\right)}\right)}.$
(44)

With these choices, we have

$\displaystyle\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\notin\boldsymbol{C}_{j}\right]}$
$\displaystyle\leq\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[z\notin\boldsymbol{C}_{j}\right]}$
$\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{m}z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}\geq\theta\right]}$
$\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{m}z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}\geq\|z\|_{p}^{p}{\frac{m}{n}}+\sqrt{c_{x}}c_{1}m^{1/6}\omega_{n}+{\left(\sqrt{c}-\sqrt{c_{x}}\right)}c_{1}m^{1/6}\omega_{n}\right]}$
$\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[{\frac{1}{\sqrt{c_{x}}}}\sum_{k=1}^{m}{\left(z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}-{\frac{\|z\|_{p}^{p}}{n}}\right)}\geq
t\omega_{n}+{\left({\frac{\sqrt{c}}{\sqrt{c_{x}}}}-1\right)}t\omega_{n}\right]}$
(Definition of $t$) $\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{m}a_{\boldsymbol{i}^{(j)}_{k}}\geq
t^{\prime}\omega_{n}\right]},$ (45)

where $t^{\prime}={{\left(1\pm{\frac{O(1)}{n^{5/12}}}\right)}}\cdot t$ by
Equation 38.

To bound Equation 45, we observe that applying Equation 40 with $t^{\prime}$
in place of $t$ throughout, and recalling our choice of $t$, we have that

$(\ref{eq:happy})=\Theta(1)\cdot{\left(1-\Phi(t^{\prime})\right)}.$

Since $t\leq m^{1/6}$ and we will ensure that $m<n$, we have $t<n^{1/6}$, so
$O(1)/n^{5/12}=o(1/t)$. Hence since
$t^{\prime}={{\left(1\pm{\frac{O(1)}{n^{5/12}}}\right)}}\cdot t$, we have that
$1-\Phi(t^{\prime})=\Theta(1-\Phi(t))$. So

$(\ref{eq:happy})=\Theta(1)\cdot(1-\Phi(t))=\Theta{\left({\frac{\varepsilon}{M}}\right)},$

recalling the definition of $M$ from Equation 43; in other words, we have that

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\notin\boldsymbol{C}_{j}\right]}\leq{\frac{O(\varepsilon)}{M}}$

as desired (cf. Equation 37).

###### Case 2: $\|x\|_{p}^{p}\geq d_{\mathrm{out}}$ and $x$ is good.

In this case, we will show that for any fixed $j\in[M]$, we have

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\in\boldsymbol{C}_{j}\right]}\leq
1-\frac{\ln(1/\varepsilon)}{M}.$ (46)

Indeed, if Equation 46 holds, then we have that

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\in\bigcap_{j=1}^{M}\boldsymbol{C}_{j}\right]}\leq{\left(1-\frac{\ln(1/\varepsilon)}{M}\right)}^{M}\leq\varepsilon$

as desired, completing the proof.

We will use the following analogue of 36:

######  Claim 37.

Let $x\in\mathbb{R}^{n}$ have $\|x\|_{p}^{p}\geq d_{\mathrm{out}}$. Let $z=sx$
for $s\leq 1$ be such that $\|z\|_{p}^{p}=d_{\mathrm{out}}$. Then

$\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{n}|x_{\boldsymbol{i}^{(j)}_{k}}|^{p}\geq\theta\right]}\geq\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{n}|z_{\boldsymbol{i}^{(j)}_{k}}|^{p}\geq\theta\right]}.$

As in 37, let $z=sx$ for $s\leq 1$ be such that
$\|z\|_{p}^{p}=d_{\mathrm{out}}$. As before, let

$z^{(p)}=(|z_{1}|^{p},\ldots,|z_{n}|^{p}).$

We observe that since $x$ is good, $z$ satisfies items (1)-(3) of Definition
34. Similar to Case 1, we let

$v\mathrel{\mathop{\mathchar
58\relax}}={z}^{(p)}-\frac{\|{z}\|_{1}(1,\ldots,1)}{n}.$

Consequently, we have

$\sum_{i=1}^{n}v_{i}=0,\qquad\text{and}\qquad\sum_{i=1}^{n}{\left(v_{i}\right)}^{2}=\|z\|_{2p}^{2p}-\frac{\|z\|_{p}^{2p}}{n}\in{\left[n{\left(\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}\right)}{\left(1\pm\frac{\Theta_{p}(1)}{n^{5/12}}\right)}\right]}.$

As before, let $c_{x}$ be such that

$\sum_{i=1}^{n}v_{i}^{2}=c_{x}n,$

and so $c_{x}=c\cdot{\left(1\pm{\frac{\Theta_{p}(1)}{n^{5/12}}}\right)}$ where
$c=\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}$ as in Case 1. As before, we will
apply Theorem 31 to the finite population $\\{a_{i}\\}_{i\in[n]}$, where

$a_{i}\mathrel{\mathop{\mathchar 58\relax}}=\frac{v_{{i}}}{\sqrt{c_{x}}}.$

As before we have $\sum_{i=1}^{n}a_{i}=0$ and $\sum_{i=1}^{n}a_{i}^{2}=n$, as
required by Theorem 31, and as before we have
$\omega_{n}^{2}=m{\left(1-{\frac{m}{n}}\right)}$. This lets us write

$\displaystyle\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[x\notin\boldsymbol{C}_{j}\right]}$
$\displaystyle\geq\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[z\notin\boldsymbol{C}_{j}\right]}$
$\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{m}z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}\geq\theta\right]}$
$\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{m}z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}\geq\|z\|_{p}^{p}{\frac{m}{n}}+\sqrt{c_{x}}c_{1}m^{1/6}\omega_{n}+{\left(\sqrt{c}-\sqrt{c_{x}}\right)}c_{1}m^{1/6}\omega_{n}-{\frac{2m\varepsilon}{\sqrt{n}}}\right]}$
$\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[{\frac{1}{\sqrt{c_{x}}}}\sum_{k=1}^{m}{\left(z^{(p)}_{\boldsymbol{i}^{(j)}_{k}}-{\frac{\|z\|_{p}^{p}}{n}}\right)}\geq
t\omega_{n}+{\left({\frac{\sqrt{c}}{\sqrt{c_{x}}}}-1\right)}t\omega_{n}-{\frac{2m\varepsilon}{\sqrt{c_{x}}{\sqrt{n}}}}\right]}$
(Definition of $t$) $\displaystyle=\mathop{{\bf
Pr}\/}_{\mathcal{D}(M,m,\theta)}{\left[\sum_{k=1}^{m}a_{\boldsymbol{i}^{(j)}_{k}}\geq
t^{\prime}\omega_{n}\right]},$ (47)

where

$t^{\prime}=t{\left(1\pm{\frac{O(1)}{n^{5/12}}-{\frac{2m\varepsilon}{\sqrt{c_{x}}{\sqrt{n}}t\omega_{n}}}}\right)},$
(48)

using
${\left({\frac{\sqrt{c}}{\sqrt{c_{x}}}}-1\right)}=\pm{\frac{O(1)}{n^{5/12}}}.$
Let us rewrite this as

$t^{\prime}=t{\left(1-\Delta\right)},\quad\text{where}\quad\Delta\mathrel{\mathop{\mathchar
58\relax}}={\frac{2m\varepsilon}{\sqrt{c_{x}}{\sqrt{n}}t\omega_{n}}}\pm{\frac{O(1)}{n^{5/12}}}={\frac{\Theta(\varepsilon\sqrt{m})}{\sqrt{n}t}}\pm{\frac{O(1)}{n^{5/12}}},$
(49)

where the last equality is because $\omega_{n}=\Theta(\sqrt{m})$. We observe
that because we will ultimately take

$m=\Theta{\left({\frac{(\log(1/\varepsilon))^{9/4}}{{\varepsilon^{4}}}}\cdot
n^{3/4}\right)}$

and we have $t=c_{1}m^{1/6}$ and $\frac{1}{\sqrt{\log n}}\leq\varepsilon$, we
have ${\frac{\Theta(\varepsilon\sqrt{m})}{\sqrt{n}t}}=\omega(1)/n^{5/12}$, so
$\Delta$ is simply equal to ${\frac{\Theta(\varepsilon\sqrt{m})}{\sqrt{n}t}}$.
Now we apply Theorem 31 (equivalently, Equation 40 with $t^{\prime}$ in place
of $t$ throughout). We get that

$(\ref{eq:happyout})=\Theta(1)\cdot(1-\Phi(t^{\prime})).$

By Equation 49,

$\displaystyle(\ref{eq:happyout})=\Theta(1)\cdot{\left(1-\Phi(t^{\prime})\right)}$
$\displaystyle=\Theta(1)\cdot(1-\Phi(t))\cdot\exp(t^{2}\Delta-t^{2}\Delta^{2}/2)$
$\displaystyle=\Theta(1)\cdot{\frac{\varepsilon}{M}}\exp{\left(\Theta{\left({\frac{\varepsilon\sqrt{m}t}{\sqrt{n}}}\right)}-\Theta{\left({\frac{\varepsilon^{2}m}{n}}\right)}\right)},$
(50)

where the last equality uses $(1-\Phi(t))={\frac{\varepsilon}{M}}$ and
$\Delta={\frac{\Theta(\varepsilon\sqrt{m})}{\sqrt{n}t}}$. Now we choose

$m\mathrel{\mathop{\mathchar
58\relax}}=c_{3}\cdot{\frac{(\log(1/\varepsilon))^{9/4}}{{\varepsilon^{4}}}}\cdot
n^{3/4}\quad\text{for a suitable positive constant $c_{3}$}$ (51)

(note that by the bound on $\varepsilon$ in the statement of the theorem we
have $m\leq n/2$), and using $t=c_{1}m^{1/6}$ we get that
$(\ref{eq:happy2})\geq{\frac{\ln(1/\varepsilon)}{M}}$, as required to
establish Equation 46.

In particular, it follows from Equations 36, 37 and 46 that there exists a set
$L$ in the support of the distribution ${\mathcal{D}(M,m,\theta)}$ that
$O(\varepsilon)$-approximates $B_{p}$. This concludes the proof of Theorem 32.

######  Remark 38.

Note that the above argument already establishes the special case of Theorem
29 when $p=1$ (i.e. the existence of a polytopal $O(\varepsilon)$-approximator
to the $\ell_{1}$-ball $B_{1}$) with the weaker bound of

$M\cdot
2^{m}={\exp{\left(\Theta{\left(\frac{(\log(1/\varepsilon))^{9/4}}{{\varepsilon^{4}}}n^{3/4}\right)}\right)}}~{}\text{halfspaces}.$

This is simply because when $p=1$, each $m$-junta $\boldsymbol{C}_{j}$ is
itself a $2^{m}$-facet polytope.

The stronger bound claimed in Equation 28 can be achieved by a slight
adjustment of the parameters used in this section. For the case $1<p<2$ we
need the arguments in Section 6.2.2, and those arguments demand that we set
$m$ and $t$ as in Equation 51 and Equation 41; but for the $p=1$ case, where
we only require Theorem 32, it can be verified that it suffices to take
$m=\Theta{\left({\left(\frac{\log(1/\varepsilon)}{\varepsilon}\right)}^{3/2}n^{3/4}\right)}$
and $t$ to be $\Theta(m^{1/6})$.

#####  6.2.2 Bounds on $\mathrm{Vol}(\boldsymbol{C}_{j})$

We observe that for every outcome of the random set $\boldsymbol{C}_{j}$ from
Definition 33, the volume is the same. So let us fix $C_{j}$ to be any outcome
of $\boldsymbol{C}_{j}$. The goal of this section is to prove the following
rather tight estimate on $\mathrm{Vol}(C_{j})$:

######  Theorem 39 (Upper and lower bounds on $\mathrm{Vol}(C_{j})$).

For $C_{j}$ as defined above,

$1-\frac{\ln M}{M}\leq\mathrm{Vol}(C_{j})\leq 1-\frac{1}{3M}.$

One direction of this bound is easy to prove. In particular, we have the
following simple claim.

######  Claim 40.

$\mathrm{Vol}(C_{j})\leq 1-1/(3M)$.

###### Proof.

Towards contradiction, if $\mathrm{Vol}(C_{j})>1-1/(3M)$, then for
$\mathrm{Vol}(L)=\mathrm{Vol}(\cap_{j=1}^{M}C_{j})\geq 2/3$ (by a union
bound). This contradicts (31), thus proving the claim. ∎

The remainder of this section is devoted to proving the following claim (which
will complete the proof of Theorem 39).

######  Claim 41.

$\mathrm{Vol}(C_{j})\geq 1-(\ln M)/M$.

The main workhorse in proving this claim will be Theorem 30. To apply this
theorem, we begin with a simple and easy to verify fact.

######  Fact 42.

Let $p\leq 2$. Then, for $\boldsymbol{g}\sim N(0,1)$ and
$\boldsymbol{y}\mathrel{\mathop{\mathchar 58\relax}}=|\boldsymbol{g}|^{p}$,
there exists $H>0$ such that $\mathbf{E}[e^{H\boldsymbol{y}}]<\infty$. In
fact, for $p<2$, this is true for any $H>0$.

Note that the parameters $\mathcal{A}_{p}$ and $\mathcal{A}_{2p}$ (following
(32)) are set so that

$\mathop{{\bf E}\/}_{\boldsymbol{x}\sim
N(0,1)}{\left[|\boldsymbol{x}|^{p}\right]}=\mathcal{A}_{p}\qquad\text{and}\qquad\mathop{{\bf
Var}\/}_{\boldsymbol{x}\sim
N(0,1)}{\left[|\boldsymbol{x}|^{p}\right]}=\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}.$

By definition, for any $j$,

$~{}\mathrm{Vol}(C_{j})=\mathop{{\bf Pr}\/}_{\boldsymbol{g}\sim
N(0,I_{m})}{\left[\sum_{j=1}^{m}|\boldsymbol{g}_{j}|^{p}\leq\theta\right]}.$
(52)

To analyze (52), our principal tool will be Theorem 30. In particular, for
each $1\leq j\leq m$, define

$\boldsymbol{X}_{j}=|\boldsymbol{g}_{j}|^{p}-\mathcal{A}_{p}.$

From 42, it follows that each random variable $\boldsymbol{X}_{j}$ satisfies
Cramér’s condition. Further, note that $\mathop{{\bf
E}\/}[\boldsymbol{X}_{j}]=0$ and $\sigma^{2}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\sigma_{p}^{2}}{n}=\operatorname{{\bf
Var}}(\boldsymbol{X}_{j})=\mathcal{A}_{2p}-\mathcal{A}_{p}^{2}=c$. We now note
that

$\mathrm{Vol}(C_{j})=\operatorname{{\bf
Pr}}\big{[}\sum_{j=1}^{m}|\boldsymbol{g}_{j}|^{p}\leq\theta\big{]}=\operatorname{{\bf
Pr}}\big{[}\sum_{j=1}^{m}\boldsymbol{X}_{j}\leq\theta-m\cdot\mathcal{A}_{p}\big{]}$

Defining $\mathbf{S}_{m}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{j=1}^{m}\boldsymbol{X}_{j}$, we get that

$\mathrm{Vol}(C_{j})=\operatorname{{\bf Pr}}[\mathbf{S}_{m}\leq
z\cdot\sigma\cdot\sqrt{m}],$

where $z$ is defined as

$\displaystyle
z=\frac{\theta-m\cdot\mathcal{A}_{p}}{\sigma\cdot\sqrt{m}}=\frac{d_{\mathrm{in}}\frac{m}{n}+{\sqrt{c}c_{1}m^{1/6}\omega_{n}}-m\cdot\mathcal{A}_{p}}{\sigma\cdot\sqrt{m}}=\frac{(n\mathcal{A}_{p}-\varepsilon\cdot\sigma_{p})\frac{m}{n}+{\sqrt{c}c_{1}m^{1/6}\omega_{n}}-m\cdot\mathcal{A}_{p}}{\sigma\cdot\sqrt{m}}.$

Here the first expression uses (42) and second expression uses the definition
of $d_{\mathrm{in}}$ (34). The last expression in the above equation
simplifies to

$\frac{{\sqrt{c}t\omega_{n}}-\varepsilon\cdot\sigma_{p}\frac{m}{n}}{\sigma\cdot\sqrt{m}}=\frac{{\sqrt{c}t\omega_{n}}-\frac{\varepsilon\cdot\sigma\cdot
m}{\sqrt{n}}}{\sigma\cdot\sqrt{m}}$

where we plug in the expression for $t$ (41). As $c=\sigma^{2}$, plugging in
the value of $\omega_{n}$ from (39), we get that

$z=t\cdot\sqrt{1-\frac{m}{n}}-\varepsilon\cdot\sqrt{\frac{m}{n}}.$

As $t=\Theta(\varepsilon\cdot m^{1/6}/\sqrt{\log(1/\varepsilon)})$ (41) and
$\varepsilon\leq 1$, it means that $z=O(m^{1/6})$. Thus, we can apply Theorem
30 to get that

$~{}\frac{1-\mathrm{Vol}(C_{j})}{1-\Phi(z)}=\frac{1-\operatorname{{\bf
Pr}}[\mathbf{S}_{m}\leq
z\cdot\sigma\cdot\sqrt{m}]}{1-\Phi(z)}=\exp\bigg{(}\frac{z^{3}}{\sqrt{m}}\cdot\lambda\bigg{(}\frac{z}{\sqrt{m}}\bigg{)}\bigg{)}\cdot\bigg{(}1+O\bigg{(}\frac{z+1}{\sqrt{m}}\bigg{)}\bigg{)}.$
(53)

As $z=O(m^{1/6})$, it follows that the right hand side of (53) is $\Theta(1)$.
Note that we are using here that $\lambda(\cdot)$ is a power series with a
positive radius of convergence. Thus, we have that

$\frac{1-\mathrm{Vol}(C_{j})}{1-\Phi(z)}=\Theta(1).$ (54)

Next, we record the following simple fact.

######  Fact 43.

Suppose $a$, $b$ and $\eta$ are parameters such that $a>b>\ln(1/\eta)>2$ and
$a-b\leq\frac{\ln(1/\eta)}{a}$. Then,

$\frac{1-\Phi(b)}{1-\Phi(a)}=O(1/\eta).$

###### Proof.

Since $1-\Phi(x)$ is a decreasing function, it suffices to prove this for
$b=a-\frac{\ln(1/\eta)}{a}$. Consider the function $g(x)=\ln(1-\Phi(x))$.
Then, $g^{\prime}(x)=\frac{-1}{1-\Phi(x)}\cdot\varphi(x)$, where $\varphi(x)$