# Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method

Sophie Huiberts<EMAIL_ADDRESS>Columbia University  Yin Tat Lee
<EMAIL_ADDRESS>Microsoft Research  Xinzhi Zhang<EMAIL_ADDRESS>Research supported by NSF grant CCF-1813135, NSF CAREER Award and Packard
Fellowships. Microsoft Research

###### Abstract

The simplex method for linear programming is known to be highly efficient in
practice, and understanding its performance from a theoretical perspective is
an active research topic. The framework of smoothed analysis, first introduced
by Spielman and Teng (JACM ’04) for this purpose, defines the smoothed
complexity of solving a linear program with $d$ variables and $n$ constraints
as the expected running time when Gaussian noise of variance $\sigma^{2}$ is
added to the LP data. We prove that the smoothed complexity of the simplex
method is $O(\sigma^{-3/2}d^{13/4}\log^{7/4}n)$, improving the dependence on
$1/\sigma$ compared to the previous bound of $O(\sigma^{-2}d^{2}\sqrt{\log
n})$. We accomplish this through a new analysis of the _shadow bound_ , key to
earlier analyses as well. Illustrating the power of our new method, we use our
method to prove a nearly tight upper bound on the smoothed complexity of two-
dimensional polygons.

We also establish the first non-trivial lower bound on the smoothed complexity
of the simplex method, proving that the _shadow vertex simplex method_
requires at least
$\Omega\Big{(}\min\big{(}\sigma^{-1/2}d^{-1/2}\log^{-1/4}d,2^{d}\big{)}\Big{)}$
pivot steps with high probability. A key part of our analysis is a new
variation on the extended formulation for the regular $2^{k}$-gon. We end with
a numerical experiment that suggests this analysis could be further improved.

##  1 Introduction

Introduced by Dantzig [Dan47], the simplex method is one of the primary
methods for solving linear programs (LP’s) in practice and is an essential
component in many software packages for combinatorial optimization. It is a
family of local search algorithms which begin by finding a vertex of the set
of feasible solutions and iteratively move to a better neighboring vertex
along the edges of the feasible polyhedron until an optimal solution is
reached. These moves are known as _pivot steps_. Variants of the simplex
method can be differentiated by the choice of _pivot rule_ , which determines
which neighbouring vertex is chosen in each iteration, as well as by the
method for obtaining the initial vertex. Some well-known pivot rules are the
most negative reduced cost rule, the steepest edge rule, and an approximate
steepest edge rule known as the devex rule. In theoretical work, the
parametric objective rule, also known as the shadow vertex rule, plays an
important role.

Empirical evidence suggests that the simplex algorithm typically takes
$O(d+n)$ pivot steps, see [Sha87, And04, Gol94] and the references therein.
However, obtaining a rigorous explanation for this excellent performance has
proven challenging. In contrast to the practical success of the simplex
method, all studied variants are known to have super-polynomial or even
exponential worst-case running times. For deterministic variants, many
published bad inputs are based on _deformed cubes_ , see [KM72, Jer73, AC78,
GS79, Mur80, Gol76] and a unified construction in [AZ98]. For randomized and
history-dependent variants, bad inputs have been constructed based on _Markov
Decision Processes_ [Kal92, MSW96, HZ15, FHZ11, Fri11, DFH22]. The fastest
provable (randomized) simplex algorithm takes $O(2^{\sqrt{d\log n}})$ pivot
steps in expectation [Kal92, MSW96, HZ15].

Average-case analyses of the simplex method have been performed for a variety
of random distributions over linear programs [Bor82, Bor87, Bor99, Sma83,
Hai83, Meg86, AKS87, Tod86, AM85]. While insightful, the results from average-
case analyses might not be fully realistic due to the fact that “random”
linear programs tend to have certain properties that “typical” linear programs
do not.

To better explain why simplex algorithm performs well in practice, while
avoiding some of the pitfalls of average-case analysis, Spielman and Teng
[ST04] introduced the smoothed complexity framework. For any base LP data
$\bar{A}\in\mathbb{R}^{n\times
d},\bar{b}\in\mathbb{R}^{n},c\in\mathbb{R}^{d}\backslash\\{0\\}$ where the
rows of $(\bar{A},\bar{b})$ are normalized to have $\ell_{2}$ norm at most
$1$, they consider the _smoothed LP_ by adding independent Gaussian
perturbations to the constraints:

$\displaystyle\max_{x\in\mathbb{R}^{d}}c^{\top}x\quad\text{subject
to}\quad(\bar{A}+\hat{A})x\leq(\bar{b}+\hat{b}).$

The entries of $\hat{A}$ and $\hat{b}$ are i.i.d. Gaussian random variables
with mean $0$ and variance $\sigma^{2}$. The _smoothed complexity_ of a
simplex algorithm $\mathcal{A}$ is defined to be the maximum (over
$\bar{A},\bar{b},c$) expected number of, i.e.,

$\displaystyle\mathcal{SC}_{\mathcal{A},n,d,\sigma}:=\max_{\begin{subarray}{c}\bar{A}\in\mathbb{R}^{n\times
d},\bar{b}\in\mathbb{R}^{n},c\in\mathbb{R}^{d}\\\
\|[\bar{A},\bar{b}]\|_{\infty,2}\leq
1\end{subarray}}\left(\mathbb{E}_{\hat{A},\hat{b}}\left[T_{\mathcal{A}}(\bar{A}+\hat{A},\bar{b}+\hat{b},c)\right]\right).$

Here $T_{\mathcal{A}}(A,b,c)$ is the number of pivot steps that the algorithm
$\mathcal{A}$ takes to solve the linear program
$\max_{x\in\mathbb{R}^{d}}\\{c^{\top}x:~{}Ax\leq b\\}$. We may note that if
$\sigma\to\infty$ then $\mathcal{SC}_{\mathcal{A},n,d,\sigma}$ approaches the
average-case complexity of $\mathcal{A}$ on independent Gaussian distributed
input data. In constrast, if $\sigma\to 0$ then
$\mathcal{SC}_{\mathcal{A},n,d,\sigma}$ will approach the worst-case
complexity of $\mathcal{A}$. As a result, most interest has been directed at
understanding the dependence on $\sigma$ in the regime where $\sigma\geq
2^{-\Omega(d)}$ but $\sigma\leq 1/\operatorname{poly}(d)$.

The motivation for smoothed analysis lies in the observation that the above-
mentioned worst-case instances are very “brittle” to perturbations, and
computer implementations require great care in handling numerical inaccuracies
to obtain the theorized running times even on problems with a small number of
variables. When implemented with a larger number of variables, the limited
accuracy of floating-point numbers make it impossible to reach the theorized
running times.

An algorithm is said to have polynomial smoothed complexity if under the
perturbation of constraints, it has expected running time
$\operatorname{poly}(n,d,\sigma^{-1})$, and [ST04] proved that the smoothed
complexity of the shadow simplex algorithm (which we will describe next) is at
most $O(d^{55}n^{86}\sigma^{-30}+d^{70}n^{86})$. The best bound available in
the literature is $O(\sigma^{-2}d^{2}\sqrt{\log n})$ pivot steps due to
[DH18], assuming $\sigma\leq 1/\sqrt{d\log n}$. We note that assuming an upper
bound on $\sigma$ can be done without loss of generality; its influence can be
captured as an additive term in the upper bound that does not depend on
$\sigma$.

This work improves the dependence on $\sigma$ of the smoothed complexity,
obtaining an upper bound of $O(\sigma^{-3/2}d^{13/4}\log^{7/4}n)$ for
$\sigma\leq 1/d\sqrt{\log n}$. As a second contribution, we prove the first
non-trivial lower bound on the smoothed complexity of a simplex method,
finding that the shadow vertex simplex method requires
$\Omega(\min(\frac{1}{\sqrt{\sigma d\sqrt{\log n}}},2^{d}))$ pivot steps.

##### Shadow Vertex Simplex Algorithm

One of the most extensively studied simplex algorithms in theory is the shadow
vertex simplex algorithm [GS55, Bor82]. Given an LP

$\displaystyle\max_{x\in\mathbb{R}^{d}}c^{\top}x,~{}~{}Ax\leq b,$

for $A\in\mathbb{R}^{n\times d},b\in\mathbb{R}^{n},c\in\mathbb{R}^{d}$, let
$P=\\{x\in\mathbb{R}^{d}:Ax\leq b\\}$ denote the feasible polyhedron of the
linear program. The algorithm starts from an initial vertex $x_{0}\in P$ that
optimizes an initial objective $c_{0}$111There are many standard methods of
finding such initialization with at most $O(d)$ overhead in running time, so
we can assume that both $x_{0}$ and $c_{0}$ are already given. See the
discussions in [DH18]. During the execution, it maintains an intermediate
objective $c_{\lambda}=\lambda c+(1-\lambda)c_{0}$ and a vertex that optimizes
$c_{\lambda}$. Thus by slowly increasing $\lambda$ from $0$ to $1$ during
different pivot steps, the temporary objective gradually changes from $c_{0}$
to $c$, revealing the desired solution at the end. Since each pivot step
requires $\operatorname{poly}(d,n)$ computational work, theoretical analysis
has focused on analyzing the number of pivot steps.

The algorithm is called shadow vertex simplex method because, after taking
orthogonal projection of the feasible set onto the two-dimensional linear
subspace $W=\mathrm{span}(c_{0},c)$, the vertices visited by the algorithm
project onto the boundary of the projection (“shadow”) $\pi_{W}(P)$. Assuming
certain non-degeneracy conditions, which will hold with probability $1$ for
the distributions we consider, this projection gives an injective relation
between iterations of the method and vertices of the shadow is injective,
meaning that we can upper bound the number of pivot steps in the algorithm by
the number of vertices of the shadow polygon. This characterization makes the
shadow vertex simplex method ideally suited for probabilistic analysis.

To analyze the “shadow size”, the number of vertices of the shadow polygon, we
follow earlier work and reduce to the case that $b=1$ by [Ver09]. In this
case, well-established principles of polyhedral duality show that

$\text{vertices}(\pi_{W}(P))\leq\operatorname{edges}(W\cap\operatorname{conv}(0,a_{1},\dots,a_{n}))\leq\operatorname{edges}(W\cap\operatorname{conv}(a_{1},\dots,a_{n}))+1.$

Here, $P=\\{x\in\mathbb{R}^{d}:Ax\leq\mathbf{1}_{n}\\}$ for any matrix $A$
with rows $a_{1},\dots,a_{n}$.

The smoothed complexity of shadow vertex simplex algorithm can thus be reduced
to the smoothed complexity of a two-dimensional slice of a convex hull. For
this purpose, let us define the maximum smoothed shadow size as

$\displaystyle\mathcal{S}(n,d,\sigma)=\max_{\begin{subarray}{c}\bar{a}_{1},\cdots,\bar{a}_{n}\in\mathbb{R}^{d}\\\
\max_{i\in[n]}\|\bar{a}_{i}\|_{2}\leq 1\\\
W\subset\mathbb{R}^{d}\end{subarray}}\mathbb{E}_{\tilde{a}_{1},\cdots,\tilde{a}_{n}\sim\mathcal{N}(0,\sigma^{2})}\left[\operatorname{edges}\big{(}\operatorname{conv}(\bar{a}_{1}+\tilde{a}_{1},\cdots,\bar{a}_{n}+\tilde{a}_{n})\cap
W\big{)}\right]$ (1)

The following upper bound we take from [DH18], who state that the analysis of
[Ver09] can be strengthened to obtain the claimed bound. This upper bound
should be understood as proving that there exists a shadow vertex rule based
simplex algorithm which satisfies that smoothed complexity bound. The lower
bound is due to [Bor87] and shows that the shadow vertex simplex rule can be
made to follow paths of this length.

######  Theorem 1 (Smoothed Complexity of Shadow Vertex Simplex Algorithm).

Given any $n\geq d\geq 2,\sigma>0$, the smoothed complexity of the shadow
vertex simplex algorithm satisfies

$\displaystyle\mathcal{S}(n,d,\sigma)/4\leq\mathcal{SC}_{\textsc{ShadowSimplex},n,d,\sigma}\leq
2\cdot\mathcal{S}\left(n+d,d,\min(\sigma,\frac{1}{\sqrt{d}\log
d},\frac{1}{\sqrt{d\log n}})\right)+4.$

With this reduction, analyzing the smoothed complexity of the simplex method
comes down to bounding the smoothed shadow size $\mathcal{S}(n,d,\sigma)$. As
such, that will be the focus of the remainder of this paper.

###  1.1 Our Results

The previous best shadow bound is due to [DH18], who prove that
$\mathcal{S}(n,d,\sigma)\leq O(d^{2}\sqrt{\log n}\sigma^{-2})$. We strengthen
this result for small values of $\sigma$.

######  Theorem 2.

For $n\geq d\geq 3$ and $\sigma\leq\frac{1}{8d\sqrt{\log n}}$, the smoothed
shadow size satisfies

$\mathcal{S}(n,d,\sigma)=O\left(\sigma^{-3/2}d^{13/4}\log^{5/4}n\right).$

A full overview of bounds on the smoothed shadow size, including previous
results in the literature, can be found in Table 1.

Second, we prove the first non-trival lower bound on the smoothed shadow size,
establishing that
$\mathcal{S}(4d-15,d,\sigma)\geq\Omega(\min(\frac{1}{\sqrt{\sigma d\sqrt{\log
d}}},2^{d}))$ for $d\geq 5$. This is lower bound is proven by constructing a
polyhedron $P=\\{x\in\mathbb{R}^{d}:Ax\leq\mathbf{1}_{n}\\}$ and a two-
dimensional subspace $W$ such that any small perturbation of $P$, projected
onto $W$, will have many vertices. The construction is based on an extended
formulation similar to those first constructed by [BN01, Gli00].

######  Theorem 3.

For $d\geq 5$ and $\sigma\leq\frac{1}{480d\sqrt{\log(4d)}}$, the smoothed
shadow size satisfies

$\mathcal{S}(4d-15,d,\sigma)=\Omega\left(\min\Big{(}\frac{1}{\sqrt{d\sigma\sqrt{\log
d}}},2^{d}\Big{)}\right).$

We remark that [DGGT16] showed a lower bound of $\Omega(\min(\sqrt{\log
n}+\frac{\sqrt[4]{\log(n\sqrt{\sigma})}}{\sqrt{\sigma}},n))$ expected vertices
for the two-dimensional polygons, obtained by placing
$\bar{a}_{1},\dots,\bar{a}_{n}$ equally spaced on the unit circle. We thus
nearly match their dependence on $\sigma$ for the analogous two-dimensional
question. However, in two-dimensional case, one can only have a lower bound of
$\Omega(n)$ even if there isn’t any perturbation. It is only when we try to
work in higher dimensions that we can show an exponential lower bound of
$\Omega(2^{d})$ any value of $\sigma$.

Also, it is possible that the exponents of $\sigma$ in our bound can be
further optimized. In Section 6.7, we describe numerical experiments which
suggest that the actual shadow size for perturbations of our constructed
polytope might be as high as $\Omega(\min(\sigma^{-3/4},2^{d}))$.

Reference | Smoothed shadow size | Model
---|---|---
[Bor87] | $\Theta(d^{3/2}\sqrt{\log n})$ |  Average-case, Gaussian distribution
[ST04] | $O(\sigma^{-6}d^{3}n+d^{6}n\log^{3}n)$ | Smooth
[DS05] | $O(\sigma^{-2}dn^{2}\log n+d^{2}n^{2}\log^{2}n)$ | Smooth
[Ver09] | $O(\sigma^{-4}d^{3}+d^{5}\log^{2}n)$ | Smooth
[DH18] | $O(\sigma^{-2}d^{2}\sqrt{\log n}+d^{3}\log^{1.5}n)$ | Smooth
This paper | $O(\sigma^{-3/2}d^{13/4}\log^{7/4}n+d^{19/4}\log^{13/4}n)$ | Smooth
This paper | $\Omega(\min(\frac{1}{\sqrt{\sigma d\sqrt{\log d}}},2^{d}))$ | Smooth
Table 1: Bounds of expected number of pivots in previous literature, assuming
$d\geq 3$. Logarithmic factors are simplified. The lower bound of [Bor87]
holds in the smoothed model as well.

##### Two-dimensional polygons

To better understand the smoothed complexity of the intersection polygon
$\operatorname{conv}(a_{1},\dots,a_{n})\cap W$, we also analyze its two-
dimensional analogue. Taking $\bar{a}_{1},\dots,\bar{a}_{n}\in\mathbb{R}^{2}$,
each satisfying $\|a_{i}\|_{2}\leq 1$, we are interested in the number of
edges of the smoothed polygon
$\operatorname{conv}(\bar{a}_{1}+\hat{a}_{1},\dots,\bar{a}_{n}+\hat{a}_{n})$,
where $\hat{a}_{1},\dots,\hat{a}_{n}\sim N(0,\sigma^{2})$ are independent. The
previous best upper bound on the smoothed complexity of this polygon
$O(\sigma^{-1}+\sqrt{\log n})$, due to [DH21]. Their analysis is based on an
adaptation of the shadow bound by [DH18]. In Section 4 we improve this upper
bound, obtaining the following theorem.

######  Theorem 4 (Two-Dimensional Upper Bound).

Let $\bar{a}_{1},\cdots,\bar{a}_{n}\in\mathbb{R}^{2}$ be $n>2$ vectors with
norm at most $1$. For each $i\in[n]$, let $a_{i}$ be independently distributed
as $\mathcal{N}(\bar{a}_{i},\sigma^{2}I_{2\times 2})$. Then

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\right)\right]\leq
O\left(\frac{\sqrt[4]{\log n}}{\sqrt{\sigma}}+\sqrt{\log n}\right).$

Combined with the trivial upper bound of $n$ vertices, this bound nearly
matches the lower bound of $\Omega(\min(\sqrt{\log
n}+\frac{\sqrt[4]{\log(n\sqrt{\sigma})}}{\sqrt{\sigma}},n))$ in [DGGT16]. A
full overview of previous results on the smoothed complexity of the two-
dimensional convex hull can be found in Table 2.

Reference | Smoothed polygon complexity
---|---
[DS04] | $O(\log(n)^{2}+\sigma^{-2}\log n)$
[Sch14] | $O(\log n+\sigma^{-2})$
[DGGT16] | $O(\sqrt{\log n}+\sigma^{-1}\sqrt{\log n})$
[DH21] | $O(\sqrt{\log n}+\sigma^{-1})$
This paper | $O(\sqrt{\log n}+\frac{\sqrt[4]{\log(n)}}{\sqrt{\sigma}})$
[DGGT16] | $\Omega(\min(\sqrt{\log n}+\frac{\sqrt[4]{\log(n\sqrt{\sigma})}}{\sqrt{\sigma}},n))$
Table 2: Bounds on the smoothed complexity of a two-dimensional polygon.

###  1.2 Related work

##### Shadow Vertex Simplex Method

The shadow vertex simplex algorithm has played a key role in many analyses of
simplex and simplex-like algorithms. On well-conditioned polytopes, such as
those of the form $\\{x\in\mathbb{R}^{d}:Ax\leq b\\}$ where $A$ is integral
with subdeterminants bounded by $\Delta$, the shadow vertex method has been
studied by in [DH16, BR13]. The shadow vertex method on polytopes all whose
vertices are integral was studied in [BDKS21, Bla22]

On random polytopes of the form
$\\{x\in\mathbb{R}^{d}:Ax\leq\mathbf{1}_{n}\\}$, assuming the constraint
vectors are independently drawn from any rotationally symmetric distribution,
the expected iteration complexity of the shadow vertex simplex method was
studied by [Bor82, Bor87, Bor99]. In the case when the rows of $A$ arise from
a Poisson distribution on the unit sphere, concentration results and diameter
bounds were proven in [BDGHL22]. The diameter of smoothed polyhedra was
studied by [NSS22], who used the shadow bound of [DH18] to show that most
vertices, according to some measure, are connected by short paths.

A randomized algorithm for solving linear programs in weakly polynomial time,
inspired by the shadow vertex simplex method, was proposed in [KS06]. The
shadow vertex algorithm was recently used as part of the analysis of an
interior point method by [ADLNV22].

##### Extended Formulations

For a polyhedron $P\subset\mathbb{R}^{d}$, an _extended formulation_ is any
polyhedron $Q\subset\mathbb{R}^{d^{\prime}}$, $d^{\prime}\geq d$, such that
$P$ can be obtained as an orthogonal projection of $Q$ to some $d$-dimensional
subspace. Importantly, $Q$ can have much fewer facets than $P$. While there is
a wider literature on extended formulations, here we describe only what is
most relevant to the construction in Section 6.

The construction in our lower bound is based on an adaptation of the extended
formulation by [BN01] of the regular $2^{k}$-gon. They used this construction
to obtain a polyhedral approximiation of the second order cone
$\\{x\in\mathbb{R}^{n+1}:\sum_{i=1}^{n}x_{i}^{2}\leq x_{n+1}^{2}\\}$. A
variant on their construction using fewer variables and inequalities was given
by [Gli00]. A more general construction based on _reflection relations_ is
used to construct extended formulation for the regular $2^{k}$-gon, as well as
other polyhedra, in [KP13]. Extended formulations for regular $n$-gons, when
$n$ is not a power of $2$, can be found in [VGG17].

Approximations of the second order cone based on the work of [BN01, Gli00]
have been used to solve second order conic programs, see, e.g., [BHMPT15].
These approximations were included in the solver SCIP until version 7.0
[Gam+20, Gam+20a].

###  1.3 Proof Overview

####  1.3.1 Smoothed Complexity Upper Bound

We write the random polytope as $Q=\operatorname{conv}(a_{1},\cdots,a_{d})$
where each $a_{i}$ is sampled independently from
$\mathcal{N}_{d}(\bar{a}_{i},\sigma^{2}I)$ such that $\|\bar{a}_{i}\|\leq 1$.
Our goal is to upper bound the expected number of edges of the polygon $Q\cap
W$ for any two-dimensional plane $W\subset\mathbb{R}^{d}$ and
$\bar{a}_{1},\cdots,\bar{a}_{n}$. This will immediately give us an upper bound
of $\mathcal{S}(n,d,\sigma)$.

A classical result from smoothed analysis [ST04] states that the intersection
polygon $Q\cap W$ is _non-degenerate_ almost surely: Every edge on $Q\cap W$
is uniquely given by the intersection between $W$ and a facet of $Q$ spanned
by exactly $d$ vertices. For any index set $I\in\binom{[n]}{d}$, write $E_{I}$
as the event that $\operatorname{conv}(a_{i}:i\in I)\cap W$ is an edge of
$Q\cap W$. Non-degeneracy implies that every edge of $Q\cap W$ uniquely
corresponds to an index set $I\in\binom{[n]}{d}$ such that $E_{I}$ holds.

Before sketching our proof, we briefly review the approach of [DH18], and then
discuss the main technical obstacles of obtaining a upper bound with better
dependence on $\sigma$.

As a first step, they replace the Gaussian distribution with what they dub a
Laplace-Gaussian distribution. The latter distribution approximates the
probability density of the former, in particular having nearly-equal smoothed
shadow size, while being $O(\sigma^{-1}\sqrt{d\log n})$-log-Lipschitz for any
point on its domain. A probability distribution with probability density
function $\mu$ is $L$-log-Lipschitz for some $L>0$, if for any
$x,y\in\mathbb{R}^{d}$, we have $|\log(\mu(x))-\log(\mu(y))|\leq L\|x-y\|$.

Next, conditional on $E_{I}$, write $\ell_{I}$ as the length of the edge on
$Q\cap W$ that corresponds to $I$. [DH18] first showed that, for any family
$S\subset\binom{[n]}{d}$, the expected number of edges of $Q\cap W$ coming
from $S$ is at most

$\displaystyle\mathbb{E}\left[\sum_{I\in
S}E_{I}\right]\leq\frac{\mathbb{E}[\mathrm{perimeter}(Q\cap W)]}{\min_{I\in
S}\mathbb{E}[\ell_{I}\mid E_{I}]}.$ (2)

Taking $S=\\{I\subset\binom{[n]}{d}:\Pr[E_{I}]\geq\binom{n}{d}^{-1}\\}$, they
find that the expected number of edges of $Q\cap W$ is at most

$\displaystyle\mathbb{E}[\operatorname{edges}(Q\cap W)]\leq
1+\mathbb{E}\left[\sum_{I\in S}E_{I}\right]\leq
1+\frac{\mathbb{E}[\mathrm{perimeter}(Q\cap W)]}{\min_{I\in
S}\mathbb{E}[\ell_{I}\mid E_{I}]}.$ (3)

To upper bound the numerator of (3), they notice that $Q\cap W$ is a convex
polygon contained in the two-dimensional disk centered at $\mathbf{0}$ with
radius $\max_{i\in[n]}\|\pi_{W}(a_{i})\|$. It then follows from convexity that
the perimeter of $Q\cap W$ is at most the perimeter of such disk, i.e.

$\displaystyle\mathbb{E}[\mathrm{perimeter}(Q\cap W)]\leq
2\pi\cdot\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]\leq
2\pi\cdot(1+4\sigma\sqrt{\log n})$ (4)

where the last step comes from Gaussian tail bound. For the denominator of
(3), [DH18] showed for any $I\in\binom{[n]}{d}$ with
$\Pr[E_{I}]\geq\binom{n}{d}^{-1}$ that, conditional on $E_{I}$, the expected
edge length is at least

$\displaystyle\mathbb{E}[\ell_{I}\mid
E_{I}]\geq\Omega(\frac{\sigma^{2}}{d^{2}\sqrt{\log
n}}\cdot\frac{1}{1+\sigma\sqrt{d\log n}})$ (5)

Combining the two parts together, we get an upper bound of
$O(\sigma^{-2}d^{2}\sqrt{\log n}+d^{3}\log^{1.5}n)$.

##### New Strategy of Counting Edges

While [DH18] made the best analysis based of their edge-counting strategy (3),
the strategy itself is sub-optimal in a fairly obvious way. A main drawback is
that using the minimum expected length of edge
$\min_{I\in\binom{[n]}{d}}\mathbb{E}[\ell_{I}\mid E_{I}]$ at the denominator
of (3) is too pessimistic when the edges of $Q\cap W$ are long. Consider the
case where an edge on $Q\cap W$ have length $\Omega(1)$ at the beginning.
After the perturbation, is very likely that the length of this edge is still
$\Omega(1)$, but [DH18] uses a lower-bound of
$\Omega(\frac{\sigma^{2}}{d^{2}\sqrt{\log n}})$.

To improve this, we use a new edge-counting strategy that can handle the long
and short edges separately with two different ways of counting the edges. Take
any index set $I\in\binom{[n]}{d}$; conditional on $E_{I}$, we write $e_{I}$
for its edge $\operatorname{conv}(a_{i}:i\in I)\cap W$. The next edge in
clockwise direction we call $e_{I+}$ and say it has length $\ell_{I^{+}}$. We
say $e_{I^{+}}$ is likely to be long, if $\Pr[\ell_{I^{+}}\geq t\mid
E_{I}]\geq 0.05$ for some parameter $t>0$. In this case, we will upper bound
the number of such edges following a similar strategy as (3), which yields

$\displaystyle\mathbb{E}[\text{number of }e_{I}\text{ s.t. }e_{I^{+}}\text{ is
likely to be long}]\leq\frac{\mathbb{E}[\mathrm{perimeter}(P\cap
W)]}{t}\leq\frac{(2\pi+O(\sigma\sqrt{\log n}))}{t}.$

where the second step uses the exact same upper bound of
$\mathbb{E}[\mathrm{perimeter}(P\cap W)]$ as in (4).

In the other case, $e_{I^{+}}$ is unlikely to be long, i.e.
$\Pr[\ell_{I^{+}}\geq t\mid E_{I}]<0.05$. Now we will upper bound the number
of such edges by claiming that their exterior angles each are large in
expectation. Let $\theta_{I}$ to be the exterior angle at the endpoint of
$\operatorname{conv}(a_{i}:i\in I)\cap W$ that comes last in clockwise order.
Our key observation is that $\sin(\theta_{I})\cdot\ell_{I^{+}}$ equals to the
distance from the second vertex of $e_{I^{+}}$ to the extension line of
$e_{I}$. So when the edge $e_{I^{+}}$ is likely to be short, a lower bound on
this distance will imply a lower bound on $\mathbb{E}[\theta_{I}\mid E_{I}]$.
See Figure 1 for an illustration. More formally, let $p_{I^{+}}$ denote the
next vertex of $Q\cap W$ after $e_{I}$ in clockwise order. suppose that for
any $I\in\binom{n}{d}$,

$\displaystyle\Pr[\operatorname{dist}(p_{I^{+}},\operatorname{affhull}(e_{I}))\geq\gamma\mid
E_{I}]\geq 0.1.$ (6)

Then conditional on $E_{I}$, we have $\sin(\theta_{I})\geq\frac{\gamma}{t}$
with probability at least $0.05$, and the expectation of the exterior angle at
the shared endpoint of $e_{I}$ and $e_{I^{+}}$ is at least
$\frac{\gamma}{20t}$.

$\displaystyle e_{I}$$\displaystyle\ell_{I^{+}}$$\displaystyle
p_{I^{+}}$$\displaystyle\geq\gamma$$\displaystyle\theta_{I}\geq\gamma/\ell_{I}$
Figure 1: Illustration of the case when $e_{I^{+}}$ is short. In purple is the
edge $e_{I}$, and the next edge in clockwise direction has length
$\ell_{I^{+}}$. In red is the edge-to-vertex distance
$\operatorname{dist}(p_{I^{+}},\operatorname{affhull}(e_{I}))$, and in blue is
the angle $\theta_{I}$. Suppose
$\operatorname{dist}(p_{I^{+}},\operatorname{affhull}(e_{I}))\geq\gamma$, then
$\theta_{I}\geq\gamma/\ell_{I^{+}}$.

On the other hand, the sum of exterior angles of a polygon equals to $2\pi$.
Therefore we can upper bound the number of short edges in expectation by at
most

$\displaystyle\mathbb{E}[\text{number of }e_{I}\text{ s.t. }e_{I^{+}}\text{ is
unlikely to be long}]\leq O(\frac{t}{\gamma}).$

Summing up the number of edges in the two cases, we get an upper bound of the
expected edge-count of $Q\cap W$ by at most

$\displaystyle\mathbb{E}[\operatorname{edges}(Q\cap
W)]\leq\frac{2\pi+O\sigma\sqrt{\log
n})}{t}+O\left(\frac{t}{\gamma}\right)=O\left(\sqrt{\frac{1+\sigma\sqrt{\log
n}}{\gamma}}\right)$ (7)

where the final step follows from optimizing $t>0$. We summarize our result in
Theorem 27. For details of the edge-counting strategy, see Section 3.

##### Two-dimensional Upper Bound

In the second part of our proof, we need to show a lower bound of the expected
distance from the affine hull of an edge of $Q\cap W$ to the next vertex in
clockwise order, which is the quantity $\gamma$ mentioned in (6).

As a warm-up, we first introduce our proof in $\mathbb{R}^{2}$, which will be
explained in Section 4 in detail. In this case, $W$ will become the entire
two-dimensional space and will disappear. Therefore, we can focus on lower-
bounding the distance from any edge $e$ of the polygon
$Q=\operatorname{conv}(a_{1},\cdots,a_{n})$ to any other vertices, i.e. it
suffices to show that for any $I\in\binom{[n]}{2}$,

$\displaystyle\Pr[\operatorname{dist}(\operatorname{conv}(a_{j}:j\notin
I),\operatorname{affhull}(e_{I}))\geq\gamma\mid E_{I}]\geq 0.1.$

We can obtain a lower bound on this quantity for any $L$-log-Lipschitz
distribution. Through an appropriate coordinate transformation we prove that,
irrespective of the values of $a_{j},j\notin I$, the distance
$\operatorname{dist}(\operatorname{conv}(a_{j},j\notin
I),\operatorname{affhull}(e_{I}))$, conditional on being non-zero, follows a
$2L$-log-Lipschitz distribution. We can directly calculate that we may choose
$\gamma=\Omega(1/L)$. This result can be applied immediately to our Gaussian
random variables $a_{1},\cdots,a_{n}$, since each
$a_{i}\sim\mathcal{N}(\bar{a}_{i},\sigma I_{2\times 2})$ is
$L=O(\sigma\sqrt{\log n})$-log-Lipschitz with overwhelming probability.
Plugging into (7), we get that in the two-dimensional case,
$\mathbb{E}[\operatorname{edges}(Q)]\leq O(\sqrt[4]{\log
n}/\sqrt{\sigma}+\sqrt{\log n})$ as in Theorem 31.

##### Multi-Dimensional Upper Bound

As in the two-dimensional case, it remains to lower-bound of the edge-to-
vertex distance $\operatorname{dist}(p_{I^{+}},\operatorname{affhull}(e_{I}))$
(see (6)) of $Q\cap W$. Analyzing this, however, becomes more challenging. In
two-dimensional case, each edge is the convex hull of two vertices among
$a_{1},\cdots,a_{n}$ and is independent to the other vertices on $Q\cap W$. In
contrast, if $d\geq 3$ then each edge on $Q\cap W$ will be the intersection
between $W$ and a $(d-1)$-dimensional facet of $Q$ (which is the convex hull
of $d$ vertices), and each vertex will be the intersection between $W$ and a
$(d-2)$-dimensional ridge of $Q$ (which is the convex hull of $d-1$ vertices).
So the distribution of $e_{I}$ and $p_{I^{+}}$ are correlated.

To overcome these difficulties, we proposed a technique that first factors
$\operatorname{dist}(p_{I^{+}},\operatorname{affhull}(e_{I}))$ into the
product of separate parts which are easier to analyze, and then use log-
Lipschitzness of $a_{1},\cdots,a_{n}$ to lower-bound each part with good
probability. Fix without loss of generality
$e=e_{[d]}=\operatorname{conv}(a_{1},\cdots,a_{d})\cap W$, as the potential
edge of interest. Consider the second endpoint $p$ on $e$ in clockwise
direction and let $J\in\binom{[d]}{d-1}$ be the index set such that
$\\{p\\}=\operatorname{conv}(a_{j}:j\in J)\cap W$. Let
$p^{\prime}=\operatorname{conv}(a_{i}:i\in J^{\prime})\cap W$ (with
$J^{\prime}=\binom{[n]}{d-1}$) be the node next to the edge $e$ in clockwise
direction. From the non-degeneracy conditions, we know that $J^{\prime}$ only
differs to $J$ with two vertices almost surely, so we can assume without loss
of generality that $J=\\{a_{2},\cdots,a_{d}\\}$ and
$J^{\prime}=\\{a_{3},\cdots,a_{d}\\}\cap\\{a_{k}\\}$ for some
$k\in\\{d+1,\cdots,n\\}$.

The main idea of our analysis is the observation that if the radius of $Q$ is
bounded above by $O(1)$ (which happens with overwhelming probability due to
Gaussian tail bound), then we can lower bound the two-dimensional edge-to-
vertex distance $\operatorname{dist}(p^{\prime},\operatorname{affhull}(e))$ by
the product of two distances $\Omega(\delta\cdot r)$, where

  * •

$\delta$ is the $d$-dimensional distance from the facet
$\operatorname{affhull}(a_{1},\cdots,a_{d})$ containing $e$, to the vertices
that are not in the facet, i.e.

$\delta=\operatorname{dist}(\operatorname{conv}(a_{d+1},\cdots,a_{n}),\operatorname{affhull}(a_{1},\cdots,a_{d})));$

  * •

$r$ is the distance from the boundary of the ridge
$\partial\operatorname{conv}(a_{2},\cdots,a_{d})$ to the one-dimensional line
$\operatorname{affhull}(e)$, i.e.
$r=\operatorname{dist}(\operatorname{affhull}(e),\partial\operatorname{conv}(a_{2},\cdots,a_{d}))$.

We will give the formal statement of the distance splitting lemma in Lemma 36.

We also remark that after conditioning on a fixed $(d-1)$-dimensional plane
$\operatorname{affhull}(a_{1},\cdots,a_{d})$ such that plane is at the
exterior of $Q$. Then $\delta$ will solely depend on the position of $a_{k}$,
and $r$ will solely depends on the location of $a_{1},\cdots,a_{d}$ on their
affine plane. Therefore we can treat $\delta$ and $r$ as independent variables
after specifying $\operatorname{affhull}(a_{1},\cdots,a_{d})$.

It then remains to show that $r$ and $\delta$ are both unlikely to be too
small. Similar to the two-dimensional case, we will also use log-Lipschitzness
of $a_{1},\cdots,a_{d}$ as our main tool.

  * •

After specifying $\operatorname{affhull}(a_{1},\dots,a_{d})$, the lower bound
on $\delta$ is derived from the remaining randomness in $a_{d+1},\dots,a_{n}$.
Here we use both the $L$-log-Lipschitzness of the distributions of
$a_{d+1},\dots,a_{n}$, as well as the knowledge that we only need to consider
hyperplanes $\operatorname{affhull}(a_{1},\dots,a_{d})$ which are likely to
have all points $a_{d+1},\dots,a_{n}$ on one side. This is made precise in
Section 5.3.

  * •

The lower bound of $r$ resembles the proof of the “distance lemma” of [ST04].
First we show that each vertex of the ridge
$\operatorname{conv}(a_{2},\cdots,a_{d})$ is $\Omega(1/d^{2}L)$-far away from
the plane spanned by its other vertices, after projected onto
$\operatorname{affhull}(e)^{\perp}$. In the second step, we show that suppose
we write $p=\sum_{i\in[d]}\lambda_{i}a_{i}$ as the convex combination, then
with constant probability $\min_{i\in[d]}\lambda_{i}\geq\Omega(1/d^{2}L)$.
Combining the two steps, we get that $r\geq\Omega(1/d^{4}L^{2})$ with good
probability. See Section 5.4 for more details.

We conclude our main result of the edge-to-vertex distance lower bound in
Lemma 35. Readers are referred to Section 5 for detailed discussions.

####  1.3.2 Smoothed Complexity Lower Bound

Our smoothed complexity lower bound (Theorem 47) is based on two geometric
observations using the inner and outer radius of the perturbed polytope. For a
polytope $P$ and a unit norm ball $\mathbb{B}$, its outer radius with center
$x$ is the smallest $R$ such that there exists $P\subset R\cdot\mathbb{B}+x$.
Its inner radius with center $x$ is the largest $r$ such that
$r\cdot\mathbb{B}+x\subset P$.

The first observation is that, if a two-dimensional polygon $T$ has inner
$\ell_{2}$-radius of $r$ and outer $\ell_{2}$-radius of $(1+\varepsilon)\cdot
r$ with respect to the same center, then $T$ has at least
$\Omega(\varepsilon^{-1/2})$ edges (Lemma 56). This comes from the fact that
every edge of $T$ has length at most $O(r\sqrt{\varepsilon})$, whereas the
perimeter of $T$ is at least $2\pi r$.

Second, if two polytopes $Q,\tilde{Q}\subseteq\mathbb{R}^{d}$, each with inner
radius $t$, have Hausdorff distance $\varepsilon<t/2$ to each other, then $Q$
will approximate $\tilde{Q}$ in the way that (Lemma 55)

$(1-2\varepsilon/t)\cdot Q\subseteq\tilde{Q}\subseteq(1+\varepsilon/t)\cdot
Q.$

In particular, for any two-dimensional linear subspace $W$ we have

$(1-O(\varepsilon))\cdot Q\cap W\subseteq\tilde{Q}\cap
W\subseteq(1+O(\varepsilon))\cdot Q\cap W.$ (8)

To prove our lower bound, we construct a polytope
$Q=\operatorname{conv}(\bar{a}_{1},\cdots,\bar{a}_{n})\subset\mathbb{R}^{d}$
and a two-dimensional linear subspace $W$ such that $\Omega(1)B^{d}_{1}\subset
Q\subset B^{d}_{1}$, and where $Q\cap W$ has inner radius
$\frac{r}{(1+4^{-d})}$ and outer radius $r>0$. Perturbing the vertices of $Q$,
we obtain $\tilde{Q}=\operatorname{conv}(a_{1},\cdots,a_{n})$, where
$a_{i}\sim N(\bar{a}_{i},\sigma^{2}I_{d\times d})$ for each $i\in[n]$. Note
that $Q\subset\mathbb{B}_{1}^{d}$ implies that $\bar{a}_{1},\dots,\bar{a}_{n}$
satisfy the normalization requirement in (1). With high probability the
Hausdorff distance in $\ell_{1}$ between $Q$ and $\tilde{Q}$ is bounded by
$\max_{i\in[n]}\|a_{i}-\tilde{a}_{i}\|_{1}\leq O(\sigma d\sqrt{\log n})$.
Using (8), we bound the inner and outer radius of $\tilde{Q}\cap W$. A lower
bound on the number of edges of $\tilde{Q}\cap W$ follows from Lemma 56 as
described above.

We remark that the polytopes
$Q=\operatorname{conv}(a_{1},\dots,a_{n})\subset\mathbb{R}^{d}$ with $n=O(d)$
and two-dimensional subspaces $W$ such that $Q\cap W$ has inner
$\ell_{2}$-radius $\frac{r}{1+4^{-d}}$ and outer $\ell_{2}$-radius $r>0$ were
first obtained by [BN01] as an _extended formulation_ for a regular
$2^{k}$-gon with $O(k)$ variables and $O(k)$ inequalities. Their polytope,
however, has an outer and inner radius that differ by a factor
$2^{\Omega(k)}$, meaning that we cannot apply Lemma 55 for $\sigma>2^{-k}$. We
construct an alternative such extended formulation where the ratio between
inner and outer $\ell_{1}$-radius is only $O(1)$. With an appropriate scaling
to get $Q\subset B_{1}^{d}$, we find that the perturbed polytope $\tilde{Q}$
will have intersection $\tilde{Q}\cap W$ with inner radius
$\frac{r}{1+4^{-d}}(1-\varepsilon)$ and outer radius $(1+\varepsilon)r$, where
$\varepsilon=O(\sigma d\sqrt{\log n})$, and thus has
$\Omega(\min(\frac{1}{\sqrt{\varepsilon}},2^{d}))$ edges, with high
probability.

##  2 Preliminaries

We write $\mathbf{1}_{n}$ for the all-ones vector in $\mathbb{R}^{n}$,
$\mathbf{0}_{n}$ for the all-zeroes vector in $\mathbb{R}^{n}$, and
$I_{n\times n}$ for the $n$ by $n$ identity matrix. The standard basis vectors
are denoted by $e_{1},\dots,e_{n}\in\mathbb{R}^{n}$. For a linear subspace
$W\subset\mathbb{R}^{n}$ we denote the orthogonal projection onto $W$ by
$\pi_{W}$. The subspace of vectors orthogonal to a given vector
$\omega\in\mathbb{R}^{n}$ is denoted $\omega^{\perp}$.

For a vector $x\in\mathbb{R}^{n}$, the $\ell_{1}$ norm is
$\|x\|_{1}=\sum_{i\in[n]}|x_{i}|$, the $\ell_{2}$-norm is
$\|x\|_{2}=\sqrt{\sum_{i\in[n]}x_{i}^{2}}$ and the $\ell_{\infty}$-norm is
$\|x\|_{\infty}=\max_{i\in[n]}|x_{i}|$. A norm without a subscript is always
the $\ell_{2}$-norm. Given $p>0,d\in\mathbb{Z}_{+}$, define
$\mathbb{B}_{p}^{d}=\\{x\in\mathbb{R}^{d}:\|x\|_{p}\leq 1\\}$ as the
$d$-dimensional unit ball of $\ell_{p}$ norm.

We write $[n]:=\\{1,\dots,n\\}$. The convex hull of vectors
$a_{1},\dots,a_{n}$ is denoted
$\operatorname{conv}(a_{1},\dots,a_{n})=\operatorname{conv}(a_{i}:i\in[n])$,
and similarly the affine hull as $\operatorname{affhull}(a_{i}:i\in[n])$.

###  2.1 Polytopes

######  Definition 5 (Polytope).

A convex body $P\subset\mathbb{R}^{d}$ is called a polytope, if it can be
written as $P=\\{x\in\mathbb{R}^{d}:Ax\leq b\\}$, for some
$n\in\mathbb{Z}_{+}$ $A\in\mathbb{R}^{n\times d},b\in\mathbb{R}^{n}$.

######  Definition 6 (Valid Condition and Facet).

Given a polytope $P\subset\mathbb{R}^{d}$, vector $c\in\mathbb{R}^{d}$ and
$d\in\mathbb{R}$, we say the linear condition $x^{\top}c\leq d$ is valid for
$P$ if the condition holds for all $x\in P$.

A subset $F\subset P$ is called a face of $P$, if
$F=P\cap\\{x\in\mathbb{R}^{d}:x^{\top}c=d\\}$, for some valid condition
$x^{\top}c\leq d$. A facet is a $d-1$-dimensional face, a ridge is a
$d-2$-dimensional face, an edge is a $1$-dimensional face and a vertex is a
$0$-dimensional face.

######  Definition 7 (Polar dual of a convex body).

Let $P\subset\mathbb{R}^{d}$ be a convex sets. Define the polar dual of $P$ as

$\displaystyle P^{\circ}=\\{y\in\mathbb{R}^{d}:y^{\top}x\leq 1,\forall x\in
P\\}.$

We state some basic facts from duality theory:

######  Fact 8 (Polar dual of polytope).

Let $P\subset\mathbb{R}^{d}$ be a polytope given by the linear system
$P=\\{x\in\mathbb{R}^{d},Ax\leq\mathbf{1}_{n}\\}\subset\mathbb{R}^{d}$ for
some $A\in\mathbb{R}^{n\times d}$. Then the polar dual of $P$ equals to

$\displaystyle
P^{\circ}:=\mathrm{conv}(\mathbf{0}_{d},a_{1},a_{2},\cdots,a_{n}).$

where $a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$ are the row vectors of $A$.
Moreover, $P^{\circ}$ is bounded iff
$\mathbf{0}_{d}\in\operatorname{int}(\operatorname{conv}(a_{1},\cdots,a_{n}))$.

######  Fact 9.

Let $P,Q\subset\mathbb{R}^{d}$ be two convex sets such that $P\subseteq Q$.
Then $Q^{\circ}\subseteq P^{\circ}$.

######  Fact 10.

Let $P\subset\mathbb{R}^{d}$ be a polytope, and let $W\subset\mathbb{R}^{d}$
be any $k\leq d$-dimensional linear subspace. Then the polar dual of
$\pi_{W}(P)$ within $W$ is equal to $P^{\circ}\cap W$.

###  2.2 Probability Distributions

All probability distributions considered in this paper will admit a
probability density function with respect to the Lebesgue measure.

######  Definition 11 (Gaussian distribution).

The $d$-dimensional Gaussian distribution
$\mathcal{N}_{d}(\bar{a},\sigma^{2}I)$ with support on $\mathbb{R}^{d}$, mean
$\bar{a}\in\mathbb{R}^{d}$, and standard deviation $\sigma$, is defined by
probability density

$\displaystyle(2\pi)^{-d/2}\cdot\exp(-\|s-\bar{a}\|^{2}/2\sigma^{2}).$

at every $s\in\mathbb{R}^{d}$.

A basic property of Gaussian distribution is the strong tail bound:

######  Lemma 12 (Gaussian tail bound).

Let $x\in\mathbb{R}^{d}$ be a random vector sampled from
$\mathcal{N}_{d}(\mathbf{0},\sigma^{2}I)$. For any $t\geq 1$ and any
$\mathbf{\theta}\in\mathbb{S}^{d-1}$, we have

$\displaystyle\Pr[\|x\|\geq t\sigma\sqrt{d}]$
$\displaystyle~{}\leq\exp(-(d/2)(t-1)^{2}).$

From this, one can upper-bound the maximum norm over $n$ independent Gaussian
random vectors with mean $\mathbf{0}_{d}$ and variance $\sigma^{2}$ by
$O(\sigma\sqrt{d\log n})$ with dominating probability.

######  Corollary 13 (Global diameter of Gaussian random variables).

For any $n\geq 2$, let $x_{1},\cdots,x_{n}\in\mathbb{R}^{d}$ be i.i.d. random
variables where each $x_{i}\sim\mathcal{N}_{d}(\mathbf{0}_{d},\sigma^{2}I)$.
Then with probability at least $1-\binom{n}{d}^{-1}$,
$\max_{i\in[n]}\|x_{i}\|\leq 4\sigma\sqrt{d\log n}$.

###### Proof.

From Lemma 12, we have for each $i\in[n]$ that

$\displaystyle\Pr[\|x_{i}\|>4\sigma\sqrt{d\log
n}]\leq\exp(-\frac{d(4\sqrt{\log n}-1)^{2}}{2})\leq\exp(-2d\log
n)\leq\binom{n}{d}^{-1}.$

Then the statement follows from the union bound. ∎

A helpful technical substitute for the Gaussian distribution was introduced by
[DH18]:

######  Definition 14 ($(\sigma,r)$-Laplace-Gaussian distribution).

For any $\sigma,r>0,\bar{a}\in\mathbb{R}^{d}$, define the $d$-dimensional
$(\sigma,r)$-Laplace-Gaussian distribution with mean $\bar{a}$, or
$LG_{d}(\bar{a},\sigma,r)$, if its density function is proportional to

$\displaystyle
f(x)=\begin{cases}\exp\left(-\frac{\|x-\bar{a}\|^{2}}{2\sigma^{2}}\right)&\text{,
if }\|x-\bar{a}\|\leq r\sigma\\\
\exp\left(-\frac{\|x-\bar{a}\|r}{\sigma}+\frac{r^{2}}{2}\right)&\text{, if
}\|x-\bar{a}\|>r\sigma.\end{cases}$ (9)

The Laplace-Gaussian random variables satisfies many desirable properties:
Like Gaussian distribution, the distance to its mean is bounded above with
high probability. Moreover, its probability density is log-Lipschitz
throughout its domain (as a contrast, the probability density of Gaussian
distribution is only log-Lipschitz close to the expectation). The definition
of $L$-log-Lipschitz is as follows:

######  Definition 15 ($L$-log-Lipschitz random variable).

Given $L>0$, we say a random variable $x\in\mathbb{R}^{d}$ with probability
density $\mu$ is $L$-log-Lipschitz (or $\mu$ is $L$-log-Lipschitz), if for all
$x,y\in\mathbb{R}^{d}$, we have

$\displaystyle|\log(\mu(x))-\log(\mu(y))|\leq L\|x-y\|,$

or equivalently, $\mu(x)/\mu(y)\leq\exp(L\|x-y\|)$.

######  Lemma 16 (Properties of Laplace-Gaussian random variables, Lemma 45 of
[DH18]).

Given any $n\geq d$ , $\sigma>0$. Let $a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$ be
independent random variables each sampled form
$LG_{d}(\bar{a},\sigma,4\sigma\sqrt{d\log n})$ (see Definition 14). Then
$a_{1},\cdots,a_{n}$ satisfy the follows:

  1. 1.

(Log-Lipschitzness) For each $i\in[n]$, the probability density of $a_{i}$ is
$(4\sigma^{-1}\sqrt{d\log n})$-log-Lipschitz.

  2. 2.

(Bounded maximum norm) With probability at least $1-\binom{n}{d}^{-1}$,
$\max_{i\in n}\|a_{i}\|\leq 4\sigma\sqrt{d\log n}$.

  3. 3.

(Bounded expected radius of projection) For any $k\leq d$, any fixed
$k$-dimensional linear subspace $H\subset\mathbb{R}^{d}$, we have
$\mathbb{E}[\max_{i\in[n]}\|\pi_{H}(a_{i})\|]\leq 4\sigma\sqrt{k\log n}$.

###  2.3 Change of Variables

We will use the following change of variables, which is a standard tool in
stochastic and integral geometry.

######  Definition 17 (Change of variables).

Let $a_{1},\cdots,a_{d}$ be $d$ affine independent vectors in
$\mathbb{R}^{d}$. Let $\theta\in\mathbb{S}^{d-1},t\in\mathbb{R}$, be such that
$\forall i\in[d],\theta^{\top}a_{i}=t$ and $\theta^{\top}e_{1}>1$.

Let $h$ be a fixed isometric embedding from $\mathbb{R}^{d-1}\to
e_{1}^{\perp}$. Let $\tilde{R}_{\theta}:\mathbb{R}^{d}\to\mathbb{R}^{d}$
denote the rotation that rotates $e_{1}$ to $\theta$ in the two-dimensional
subspace $\mathrm{span}(e_{1},\theta)$, and is the identity transformation on
$\mathrm{span}(e_{1},\theta)^{\perp}$. Define
$R_{\theta}=\tilde{R}_{\theta}\circ h$ to be the resulting isometric embedding
from $\mathbb{R}^{d-1}$, identified with $e_{1}^{\perp}$, to $\theta^{\perp}$.
Now define the transformation $\phi$ from
$\theta\in\mathbb{S}^{d-1},t\in\mathbb{R},b_{1},\cdots,b_{d}\in\mathbb{R}^{d-1}$
to $a_{1},\cdots,a_{d}\in\mathbb{R}^{d}$ as follows:

$\displaystyle\phi(\theta,t,b_{1},\cdots,b_{d})=(R_{\theta}(b_{1})+t\theta,\cdots,R_{\theta}(b_{d})+t\theta)=(a_{1},\cdots,a_{d}).$
(10)

######  Lemma 18 (Jacobian of the inverse isometric transformation, see
Theorem 7.2.7 in [SW08]).

Let $\phi:\mathbb{S}^{d-1}\times\mathbb{R}\times\mathbb{R}^{(d-1)\times
d}\to\mathbb{R}^{d\times d}$ be the transformation defined in Definition 17.
The inverse transformation of $\phi$ is defined almost everywhere and has
Jacobian equal to

$\displaystyle\left|\det\left(\frac{\partial\phi(a)}{\phi(a)}\right)\right|=C_{d}(d-1)!\cdot\operatorname{vol}_{d-1}(\operatorname{conv}(a_{1},\cdots,a_{d}))$

for some constant $C_{d}$ depending only on the dimension. As a consequence,
if $a_{1},\dots,a_{d}$ are points with probability density
$\mu(a_{1},\dots,a_{d})$ and if
$\theta\in\mathbb{S}^{d-1},t\in\mathbb{R},b_{1},\dots,b_{d}\in\mathbb{R}^{d-1}$
have probability density proportional to

$\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\dots,b_{d}))\cdot\mu(t\theta+R_{\theta}(b_{1}),\dots,t\theta+R_{\theta}(b_{d}))$

then
$\mathbb{E}[f(a_{1},\dots,a_{d})]=\mathbb{E}[f(\phi(\theta,t,b_{1},\dots,b_{d}))]$
for any measurable function $f$.

In particular, we will use this transformation to condition on the value of
$\theta$ and consider events in the variables $t,b_{1},\dots,b_{d}$. For this
purpose, we have the following fact.

######  Fact 19 (Log-Lipschitzness of the Position of Affine Hull).

Let $a_{1},\cdots,a_{d}\in\mathbb{R}^{d}$ be $d$ independent $L$-log-Lipschitz
random variables, and let
$(\theta,t,b_{1},\dots,b_{d})=\phi^{-1}(a_{1},\dots,a_{d})$. Then conditional
on the values of $\theta,b_{1},\dots,b_{d}$, the random variable $t$ is
$(dL)$-log-Lipchitz.

###### Proof.

By Lemma 18, the joint probability density of $(a_{1},\cdots,a_{d})$ is
proportional to

$\displaystyle\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\cdots,b_{d}))\cdot\prod_{i=1}^{d}\mu_{i}(R_{\theta}(b_{i})+t\theta)$

where $\mu_{i}$ is the probability density of $a_{i}$. Conditioning on
$b_{1},\dots,b_{d}$, the volume
$\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\cdots,b_{d}))$ is fixed.
The statement then follows from the fact that
$\mu_{i}(R_{\theta}(b_{i})+t\theta)$ is $L$-log-Lipschitz in $t$ for any
$b_{i}$ and for each $i\in[d]$. ∎

###  2.4 Non-Degenerate Conditions

######  Definition 20 (Non-degenerate polytope).

A polytope $Q=\operatorname{conv}(a_{1},\dots,a_{n})\subset\mathbb{R}^{d}$ is
called non-degenerate, if it is simplicial (every facet is a simplex) and if,
for $i\in[n]$, $a_{i}\in\partial Q$ implies that $a_{i}$ is a vertex of $Q$.

######  Definition 21 (Non-degenerate intersection with a 2D-plane).

Let $Q\subset\mathbb{R}^{d}$ be a non-degenerate polytope and let
$W\subset\mathbb{R}^{d}$ be a two-dimensional linear subspace. We say $Q$ has
non-degenerate intersection with $W$, if

  1. 1.

The edges of the two-dimensional polygon $Q\cap W$ have one-to-one
correspondence to the facets of $Q$ that have non-empty intersection with $W$;
and

  2. 2.

The vertices of $Q\cap W$ have one-to-one correspondence to the
$(d-2)$-dimensional faces (ridges) of $Q$ that have non-empty intersection
with $W$

######  Lemma 22 (Non-degenerate conditions of random polytope).

Given any $n\geq d\geq 2$ and any fixed two-dimensional plane
$W\subset\mathbb{R}^{d}$. For $a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$, the
polytope $Q=\operatorname{conv}(a_{1},\cdots,a_{n})$ satisfies the following
properties everywhere except for a set of measure $0$:

  1. 1.

$Q$ is non-degenerate;

  2. 2.

$Q$ has non-degenerate intersection with $W$;

  3. 3.

For every normal vector $v$ to any facet of $Q$, $e_{1}^{\top}v\neq 0$.

Assume the polytope $Q=\operatorname{conv}(a_{1},\dots,a_{n})$ and the two-
dimensional linear subspace $W\subset\mathbb{R}^{d}$ satisfy the conditions in
Lemma 22. Then every edge of the two-dimensional polygon $W\cap Q$ correspond
to a set of $d$ vertices, and every vertex of $W\cap Q$ correspond to a set of
$(d-1)$ vertices. The following lemma quantifies the relationship of such sets
for adjacent vertices and edge:

######  Fact 23 (Properties of neighboring vertices on non-degenerate
intersection polygon).

Let $W\subset\mathbb{R}^{d}$ be a two-dimensional linear subspace,
$Q=\operatorname{conv}(a_{1},\dots,a_{n})\subset\mathbb{R}^{d}$ is simplicial
and has non-degeneracy intersection with $W$. Given
$J_{1},J_{2}\in\binom{[n]}{d-1}$, $I\in\binom{[n]}{d}$, suppose (1)
$V_{J_{1}}=\operatorname{conv}(a_{j}:j\in J_{1})\cap W$ and
$V_{J_{2}}=\operatorname{conv}(a_{j}:j\in J_{2})\cap W$ are two adjacent
vertices of $Q\cap W$, and (2) $\operatorname{conv}(a_{i}:i\in I)\cap W$ is an
edge of $Q\cap W$ that contains $V_{J_{1}}$ but not contains $V_{J_{2}}$. Then
we have $|J_{1}\backslash J_{2}|=|J_{2}\backslash J_{1}|=1$ and $|I\backslash
J_{2}|=2$.

###### Proof.

Let $I^{\prime}=J_{1}\cap J_{2}$. Then
$\operatorname{conv}(V_{J_{1}},V_{J_{2}})=\operatorname{conv}(a_{i}:i\in
I)\cap W$ is an edge of the polygon $Q\cap W$. Since $Q$ has non-degenerate
intersection with $W$, we have that $|I^{\prime}|=d$. Combining with
$|J_{1}|=|J_{2}|=d-1$ gives us that $|J_{1}\backslash J_{2}|=|J_{2}\backslash
J_{1}|=1$.

Next we consider $|I\backslash J_{2}|$. Since $J_{1}\subset I$ and
$|J_{1}\backslash J_{2}|=1$, it could only be the case that $|I\backslash
J_{2}|\in\\{1,2\\}$. If $|I\backslash J_{2}|=1$, then by $|I|=|J_{2}|+1$ we
must have $J_{2}\subset I$, but this contradicts to the fact that
$J_{2}\not\subset I$. Therefore we could only have $|I\backslash J_{2}|=2$. ∎

##  3 Smoothed Complexity Upper Bound

In this section, we establish our key theorem for upper bounding the number of
edges of a random polygon $\operatorname{conv}(a_{1},\dots,a_{n})\cap W$ for
$W$ a fixed $2$-dimensional linear subspace and
$a_{1},\dots,a_{n}\in\mathbb{R}^{d}$. Specifically we show that if for any
edge on the shadow polygon $\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$,
the expected distance between the affine hull of the edge and the next vertex
of the shadow is not too small in expectation, then the expected number of
edges of $\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ will be bounded from
above.

######  Definition 24 (Edge event).

For $I\subset[n]$, we write $F_{I}=\operatorname{conv}(a_{i}:i\in I)$. Define
$E_{I}$ to be the event that both $F_{I}$ is a facet of
$\operatorname{conv}(a_{1},\dots,a_{n})$ and $F_{I}\cap W\neq\emptyset$.

Note that when $d=2$ then $W=\mathbb{R}^{2}$ and the condition $F_{I}\cap
W\neq\emptyset$ is guaranteed to hold.

######  Remark 25.

Any edge $e$ of $\operatorname{conv}(a_{1},\dots,a_{n})\cap W$ can be written
as $e=F_{I}\cap W$ for some $I\subset[n]$ for which $E_{I}$ holds. Assuming
non-degeneracy, this relation between edges and index sets is a one-to-one
correspondence, and moreover every $I\subset[n]$ for which $E_{I}$ holds
satisfies $|I|=d$.

To state the key theorem’s assumption, we require one more definition:

######  Definition 26.

For any given two-dimensional linear subspace $W\subset\mathbb{R}^{d}$ we
denote an arbitrary but fixed rotation as “clockwise”. For the polygon
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ of our interest, let
$p_{1},\dots,p_{k}$ denote its vertices in clockwise order and write
$p_{k+1}=p_{1},p_{k+2}=p_{2}$. Then for any edge $e=[p_{i-1},p_{i}]$, we call
$p_{i}$ its second vertex in clockwise order and we call $p_{i+1}$ the next
vertex after $e$ in clockwise order. The edge $[p_{i},p_{i+1}]$ is the next
edge after $e$ in clockwise order.

Note that the above terms are well-defined in the sense that they depend only
on the polygon and the orientation of the subspace, not on the labels. With
this definition in place, we can now state the theorem itself:

######  Theorem 27 (Smoothed complexity upper bound for continuous
perturbations).

Fix any $n,d\geq 2$, $\sigma\geq 0$, and any two-dimensional linear subspace
$W\subseteq\mathbb{R}^{d}$. Let $a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$ be
independently distributed each according to a continuous probability
distribution.

For any $I\in\binom{n}{d}$, conditional on $E_{I}$, define $y_{I}\in W$ as the
outer unit normal of the edge $F_{I}\cap W$. Suppose for each
$I\in\binom{n}{d}$ such that $\Pr[E_{I}]\geq 10\binom{n}{d}^{-1}$, we have

$\displaystyle\Pr[y_{I}^{\top}p_{2}-y_{I}^{\top}p_{3}\geq\gamma\mid E_{I}]\geq
0.1,$

where we write $[p_{1},p_{2}]=F_{I}\cap W$ and
$p_{3}\in\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ as the next vertex
after $F_{I}\cap W$ in clockwise order. Then we have

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\right)\right]$
$\displaystyle\leq
10+80\pi\sqrt{\frac{\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]}{\gamma}}$
$\displaystyle=O\left(\sqrt{\frac{\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]}{\gamma}}\right).$

Assuming non-degeneracy, $y_{I}$ is well-defined if and only if $E_{I}$
happens. In this case, we are guaranteed that
$y_{I}^{\top}p_{2}-y_{I}^{\top}q_{3}>0$.

To prove the above theorem, we show that any $I\in\binom{[n]}{d}$ with
$\Pr[E_{I}]\geq\binom{n}{d}^{-1}$ can be charged to either a portion of the
perimeter of the polygon $\operatorname{conv}(a_{1},\dots,a_{n})\cap W$ or to
a portion of its sum $2\pi$ of exterior angles at its vertices.

######  Definition 28 (Exterior angle and length of the next edge).

Given any $I\in\binom{[n]}{d}$, we define two random variables
$\theta_{I},\ell_{I^{+}}\geq 0$. If $E_{I}$ happens, write $v\in F_{I}\cap W$
for the second endpoint of $F_{I}\cap W$ in clockwise order. Let $\theta_{I}$
to be the (two-dimensional) exterior angle of
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ at $v$; If $E_{I}$ doesn’t
happen then let $\theta_{I}=0$.

Let $\ell_{I^{+}}$ denote the following random variable: If $E_{I}$ happens,
then $\ell_{I^{+}}$ equals to the length of the next edge after $F_{I}\cap W$
in clockwise order, i.e., the other edge of
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ containing $v$. If $E_{I}$
doesn’t happen then let $\ell_{I^{+}}=0$.

###### Proof of Theorem 27.

Since we have non-degeneracy with probability $1$, by Lemma 22 and linearity
of expectation we find

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\cap
W\right)\right]=\sum_{I\in\binom{[n]}{d}}\Pr[E_{I}].$

We can give an upper bound of the expected number of edges of
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ by upper-bounding each
$\Pr[E_{I}]$. Fix any $I\in\binom{[n]}{d}$ and let $t>0$ be a parameter to be
determined later. We consider three different possible upper bounds on
$\Pr[E_{I}]$, at least one of which will always hold:

Case 1: $\Pr[E_{I}]\leq 10\binom{n}{d}^{-1}$.

Since $\sum_{I\in\binom{[n]}{d}}10\binom{n}{d}^{-1}=10$, one can immediately
see that the total contribution of edges counted in this case is at most $10$.

Case 2: $\Pr[E_{I}]>10\binom{n}{d}^{-1}$ and $\Pr[\ell_{I^{+}}\geq t\mid
E_{I}]\geq\frac{1}{20}$.

In this case, $\mathbb{E}[\ell_{I^{+}}\mid E_{I}]\geq\frac{t}{20}$, therefore
we have

$\displaystyle\Pr[E_{I}]=\frac{\mathbb{E}[\ell_{I^{+}}\mathbb{I}(E_{I})]}{\mathbb{E}[\ell_{I^{+}}\mid
E_{I}]}\leq\frac{20}{t}\cdot\mathbb{E}[\ell_{I^{+}}\mathbb{I}(E_{I})].$

Case 3: $\Pr[E_{I}]>10\binom{n}{d}^{-1}$ and $\Pr[\ell_{I^{+}}\leq t\mid
E_{I}]\geq\frac{19}{20}$. Conditional on $E_{I}$, without loss of generality
we write $[p_{1},p_{2}]=F_{I}\cap W$ and let $p_{3}$ to denote the next vertex
after $F_{I}\cap W$ in clockwise direction. From the theorem’s assumption we
have
$\Pr[\operatorname{dist}(\operatorname{affhull}(p_{1},p_{2}),p_{3})\geq\gamma\mid
E_{I}]\geq\frac{1}{10}$. Then from the union bound,

$\displaystyle\Pr[(\ell_{I^{+}}\leq t)$
$\displaystyle\wedge(\operatorname{dist}(\operatorname{affhull}(p_{1},p_{2}),p_{3})\geq\gamma)\mid
E_{I}]$ $\displaystyle\geq 1-\Pr[\ell_{I^{+}}>t\mid E_{I}]$
$\displaystyle-\Pr[\operatorname{dist}(\operatorname{affhull}(p_{1},p_{2}),p_{3})<\gamma\mid
E_{I}]\geq\frac{1}{20}.$

Since $\theta_{I}\geq 0$ and

$\displaystyle\theta_{I}\geq\sin(\theta_{I})=\frac{\operatorname{dist}(\operatorname{affhull}(p_{1},p_{2}),p_{3})}{\ell_{I^{+}}}$

we have $\mathbb{E}[\theta_{I}\mid
E_{I}]\geq\frac{1}{20}\cdot\frac{\gamma}{t}$, and therefore we can upper bound
$\Pr[E_{I}]$ by

$\displaystyle\Pr[E_{I}]=\frac{\mathbb{E}[\theta_{I}\mathbb{I}(E_{I})]}{\mathbb{E}[\theta_{I}\mid
E_{I}]}\leq\frac{20t}{\gamma}\cdot\mathbb{E}[\theta_{I}\mathbb{I}(E_{I})].$

Readers are referred to Figure 1 for more illustration of the proof.

Combining the upper bounds for each $\Pr[E_{I}]$ for the above three cases, we
get that

$\displaystyle\mathbb{E}\left[\operatorname{vertices}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\cap
W\right)\right]=\sum_{I\in\binom{[n]}{d}}\Pr[E_{I}]$ $\displaystyle\leq$
$\displaystyle\sum_{I\in\binom{[n]}{d}}\left(10\binom{n}{d}^{-1}+\frac{20}{t}\cdot\mathbb{E}[\ell_{I^{+}}\mathbb{I}(E_{I})]+\frac{20t}{\gamma}\cdot\mathbb{E}[\theta_{I}\mathbb{I}(E_{I})]\right)$
$\displaystyle\leq$ $\displaystyle
10+\frac{20}{t}\cdot\mathbb{E}[\sum_{I\in\binom{[n]}{d}}\ell_{I^{+}}\mathbb{I}(E_{I})]+\frac{20t}{\gamma}\cdot\mathbb{E}[\sum_{I\in\binom{[n]}{d}}\theta_{I}\mathbb{I}(E_{I})]$
(11)

To upper bound the second term of (3), we notice that
$\sum_{I\in\binom{[n]}{d}}\ell_{I^{+}}\mathbb{I}(E_{I})$ exactly equals the
perimeter of $\operatorname{conv}(a_{1},\dots,a_{n})\cap W$. Since the shadow
polygon $\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ is contained in the
two-dimensional disk of radius $\max_{i\in[n]}\|\pi_{W}(a_{i})\|$, by the
monotonicity of surface area for convex sets we have

$\mathbb{E}[\sum_{I\in\binom{[n]}{d}}\ell_{I^{+}}\mathbb{I}(E_{I})]\leq
2\pi\cdot\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|].$

To upper bound the third term of (3), we notice that the sum of exterior
angles for any polygon always equals to $2\pi$. Thus

$\displaystyle\mathbb{E}[\sum_{I\in\binom{[n]}{d}}\theta_{I}\mathbb{I}(E_{I})]=2\pi$
(12)

Finally, we combine (3 \- 12) and minimize over all $t\geq 0$:

$\displaystyle\mathbb{E}\left[\operatorname{vertices}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\cap
W\right)\right]$
$\displaystyle\leq\min_{t>0}\left(10+\frac{40\pi\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]}{t}+\frac{40\pi
t}{\gamma}\right)$ $\displaystyle\leq
10+80\pi\sqrt{\frac{\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]}{\gamma}}.$

where in the final step, we set
$t=\sqrt{\gamma\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]}$. ∎

We will not apply Theorem 27 directly to Gaussian distributed points
$a_{1},\dots,a_{n}$. Instead, we will follow an approach introduced by [DH18].
First, we relate the shadow size for Gaussian distributed vectors to the
shadow size for _Laplace-Gaussian_ distributed vectors. We will then show how
to use Theorem 27 to any log-Lipschitz probability distribution.

######  Lemma 29 (Lemma 46 of [DH18]).

Given any $n\geq d\geq 2,\sigma>0$, any two-dimensional linear subspace
$W\subset\mathbb{R}^{d}$, and any
$\bar{a}_{1},\cdots,\bar{a}_{n}\in\mathbb{R}^{d}$ with
$\max_{i\in[n]}\|\bar{a}_{i}\|\leq 1$. For every $i\in[n]$, let
$a_{i}\sim\mathcal{N}_{d}(\bar{a}_{i},\sigma)$ and $\widehat{a}_{i}\sim
LG_{d}(\bar{a}_{i},\sigma,4\sigma\sqrt{d\log n})$ be independently sampled.
Then the following holds

$\mathbb{E}\left[\operatorname{edges}(\operatorname{conv}(a_{1},\cdots,a_{n})\cap
W)\right]\leq
1+\mathbb{E}\left[\operatorname{edges}(\operatorname{conv}(\widehat{a}_{1},\cdots,\widehat{a}_{n})\cap
W)\right].$

Although [DH18] state this lemma only for $d\geq 3$, their proof applies
without change to the case $d=2$.

##  4 Upper Bound for Two Dimension

In this section, we prove the smoothed complexity upper bound for $d=2$ using
the key lemma. In this case, the shadow plane $W$ is the two-dimensional
Euclidean space. From Theorem 27, it remains to lower bound the distance from
the affine hull of an edge to its neighboring vertex in clockwise order (the
quantity $\gamma$ in Theorem 27), where our polygon
$\operatorname{conv}(a_{1},\cdots,a_{n})$ is under Laplace-Gaussian
perturbation. In fact, we can show a more general result for any $L$-log-
Lipschitz distribution:

######  Lemma 30 (Lower Bound of $\gamma$ in Two Dimension).

Let $a_{1},\cdots,a_{n}\in\mathbb{R}^{2}$ be $n$ independent $L$-log-Lipschitz
random variables. Then for any $I\in\binom{[n]}{2}$, conditional on $E_{I}$
happens, the outer unit normal $y\in W$ of the edge
$\operatorname{conv}(a_{i}:i\in I)$ satisfies

$\Pr[y^{\top}a_{i}-\max_{j\notin I}y^{\top}a_{j}\geq\frac{1}{L}\mid E_{I}]\geq
0.1,$

for any $i\in I$.

Together with Theorem 27 and Lemma 29 from the previous section, Lemma 30
immediately tells us the upper bound for two-dimensional polygons under
Gaussian perturbation:

######  Theorem 31 (Two-Dimensional Upper Bound).

Let $\bar{a}_{1},\cdots,\bar{a}_{n}\in\mathbb{R}^{2}$ be $n>2$ vectors with
norm at most $1$. For each $i\in[n]$, let $a_{i}$ be independently distributed
as $\mathcal{N}_{2}(\bar{a}_{i},\sigma^{2}I)$. Then

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\right)\right]\leq
O\left(\frac{\sqrt[4]{\log n}}{\sqrt{\sigma}}+\sqrt{\log n}\right).$

###### Proof.

For each $i\in[n]$, let $\hat{a}_{i}$ be independently sampled form the
2-dimensional Laplace-Gaussian distribution
$LG_{2}(\bar{a}_{i},\sigma,4\sigma\sqrt{2\log n})$. It follows from Lemma 16
that $\hat{a}_{i}$ is $(4\sigma^{-1}\sqrt{2\log n})$-log-Lipschitz and
$\mathbb{E}[\max_{i\in[n]}\|\hat{a}_{i}\|]\leq 1+4\sigma\sqrt{2\log n}$. We
use Lemma 30 by setting $L=4\sigma^{-1}\sqrt{2\log n}$, and Theorem 27 by
setting $\gamma=\frac{1}{L}=\frac{\sigma}{4\sqrt{2\log n}}$, to find

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(\hat{a}_{1},\cdots,\hat{a}_{n})\right)\right]$
$\displaystyle\leq O\left(\frac{\sqrt[4]{\log n}}{\sqrt{\sigma}}+\sqrt{\log
n}\right).$

And from Lemma 29, we conclude that
$\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\right)\right]\leq
1+O(\frac{\sqrt[4]{\log n}}{\sqrt{\sigma}}+\sqrt{\log n}).$ ∎

###### Proof of Lemma 30.

Fix any set $I=\\{i,i^{\prime}\\}\subset[n]$. Define $z\in\mathbb{S}^{1}$ and
$t$ to satisfy $z^{\top}a_{i}=z^{\top}a_{i^{\prime}}=t$ and $z^{\top}e_{1}>0$.
Both are well-defined with probability $1$.

Note that $E_{I}$ is now equivalent to either having $z^{\top}a_{j}<t$ for all
$j\notin I$ or $z^{\top}a_{j}>t$ for all $j\notin I$. Write $E_{I}^{+}$ for
the former case and $E_{I}^{-}$ for the latter. The vector $z$ is always
defined, assuming non-degeneracy, and is equal to the outer normal unit vector
$y$ if $E_{I}^{+}$ and equal to $-y$ if $E_{I}^{-}$.

Using Fubini’s theorem, we condition on the values of $a_{j},j\notin I$. and
$z$ using Lemma 18. Let $\mu:\mathbb{R}\to\mathbb{R}_{\geq 0}$ denote the
induced density of $t=y^{\top}a_{i}=y^{\top}a_{i^{\prime}}$. Then from 19,
$\mu$ is $(2L)$-log-Lipschitz.

In the first case, for $E_{I}^{+}$, we have, still only considering the
randomness over $t$,

$\displaystyle\Pr[(t-\max_{j\notin I}z^{\top}a_{j}\geq\frac{1}{L})\wedge
E_{I}^{+}]$ $\displaystyle=\int_{\max_{j\notin
I}z^{\top}a_{j}+1/L}^{\infty}\mu(x)\mathrm{d}x$
$\displaystyle=\int_{\max_{j\notin
I}z^{\top}a_{j}}^{\infty}\mu(z+1/L)\mathrm{d}x$
$\displaystyle\geq\int_{\max_{j\notin
I}z^{\top}a_{j}}^{\infty}e^{-2}\mu(z)\mathrm{d}z$ (By $(2L)$-log-Lipschitzness
of $\mu$) $\displaystyle=e^{-2}\Pr[E_{I}^{+}].$

Similarly for the other case, $E_{I}^{-}$, we find

$\Pr[(\min_{j\notin I}z^{\top}a_{j}-t\geq\frac{1}{L})\wedge E_{I}^{-}]\geq
e^{-2}\Pr[E_{I}^{-}].$

Now observe that, for $i\in I$,

$\displaystyle\Pr[y^{\top}a_{i}-\max_{j\notin
I}y^{\top}a_{j}\geq\frac{1}{L}\wedge E_{I}]$
$\displaystyle=\Pr[(t-\max_{j\notin I}z^{\top}a_{j}\geq\frac{1}{L})\wedge
E_{I}^{+}]+\Pr[(\min_{j\notin I}z^{\top}a_{j}-t\geq\frac{1}{L})\wedge
E_{I}^{-}]$ $\displaystyle\geq
e^{-2}\Pr[E_{I}^{+}]+e^{-2}\Pr[E_{I}^{-}]=e^{-2}\Pr[E_{I}],$

finishing the proof since

$\Pr[y^{\top}a_{i}-\max_{j\notin I}y^{\top}a_{j}\geq\frac{1}{L}\mid
E_{I}]=\Pr[y^{\top}a_{i}-\max_{j\notin I}y^{\top}a_{j}\geq\frac{1}{L}\wedge
E_{I}]/\Pr[E_{I}]\geq e^{-2}\geq 0.1.$

∎

##  5 Multi-Dimensional Upper Bound

###  5.1 Notations and roadmap

For the higher-dimensional case, we will establish the upper bound:

######  Theorem 32.

Given any $d>2,n\geq d$, and $\sigma\leq\frac{1}{8d\sqrt{\log n}}$. Let
$\bar{a}_{1},\cdots,\bar{a}_{n}$ be $n$ vectors with
$\max_{i\in[n]}\|\bar{a}_{i}\|\leq 1$. For each $i\in[n]$, let $a_{i}$ be
independently distributed as $\mathcal{N}_{d}(\bar{a}_{i},\sigma^{2}I)$. Then

$\mathbb{E}[\operatorname{edges}(\operatorname{conv}(a_{1},\dots,a_{n})\cap
W)]=O\left(\sigma^{-3/2}d^{13/4}\log^{5/4}n\right).$ (13)

Since we assume that $a_{1},\dots,a_{n}$ each have a continuous probability
density function, we know that with probability $1$ the polytope
$\operatorname{conv}(a_{1},\dots,a_{n})$ is non-degenerate and has a non-
degenerate intersection with $W$. In this case, the edges of the polygon
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ are given by the sets
$F_{I}\cap W$ for which $I\in\binom{[n]}{d}$ and $E_{I}$ holds (where $E_{I}$
is defined in Definition 24). In addition, the vertices of the polygon
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$ are given by the intersection
between $W$ and $(d-2)$-dimensional ridges of
$\operatorname{conv}(a_{1},\cdots,a_{n})$, which are convex hulls of $(d-1)$
vertices of $\operatorname{conv}(a_{1},\cdots,a_{n})$. We define the following
notations of ridge and the corresponding vertex:

######  Definition 33 (Ridge and vertex event).

For any $J\subset[n]$, write $R_{J}=\operatorname{conv}(a_{j}:j\in J)$. Define
$A_{J}$ to be the event that $R_{J}$ is a ridge of
$\operatorname{conv}(a_{1},\cdots,a_{n})$ and $R_{J}\cap W\neq\emptyset$.

######  Remark 34.

Any vertex $v$ of $\operatorname{conv}(a_{1},\dots,a_{n})$ can be written as
$v=R_{J}\cap W$ for some $J\subset[n]$ for which $A_{J}$ holds. Assuming non-
degeneracy, each $J$ for which $A_{J}$ holds satisfies $|J|=d-1$ and the
relation between vertices and index sets $J\in\binom{[n]}{d-1}$ with $A_{J}$
is a one-to-one correspondence.

Our proof follows from a similar structure as the two-dimensional upper bound
(see section 4). Our main technical result is the following lower-bound of the
edge-to-vertex distance on the shadow polygon:

######  Lemma 35 (Edge-to-vertex distance of shadow polygon in multi-
dimension).

Let $a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$ be independent $L$-log-Lipschitz
random variables. For any $I\in\binom{[n]}{d}$ that satisfies $\Pr[E_{I}]\geq
10\binom{n}{d}^{-1},$ (See Definition 24 the definition of $E_{I}$) we have

$\displaystyle\Pr[y^{\top}p-y^{\top}p^{\prime}\geq\Omega(\frac{1}{L^{3}d^{5}\log
n})\mid E_{I}]\geq 0.1,$

where $p$ is any point in $F_{I}\cap W$, and
$p^{\prime}\in\operatorname{conv}(a_{1},\dots,a_{n})\cap W$ is the next vertex
after $F_{I}\cap W$ in clockwise direction. Here $y\in W$ is the outer unit
normal to the edge $F_{I}\cap W$ on
$\operatorname{conv}(a_{1},\cdots,a_{n})\cap W$.

Then we can prove Theorem 32 directly by Lemma 35, and Theorem 27, Lemma 29
from Section 3.

###### Proof of Theorem 32.

For each $i\in[n]$, let $\hat{a}_{i}$ be independently sampled form the
Laplace-Gaussian distribution $LG_{d}(\bar{a}_{i},\sigma,4\sigma\sqrt{2\log
n})$. From Lemma 16, we know that

  1. 1.

Each $\hat{a}_{i}$ is $L=(4\sigma^{-1}\sqrt{d\log n})$-log-Lipschitz;

  2. 2.

$\mathbb{E}[\max_{i\in[n]}]\|\pi_{W}(\hat{a}_{i})\|\leq 1+4\sigma\sqrt{2\log
n}\leq 1.5$.

Also from Lemma 35, we get that for any $p\in F_{I}\cap W$, if $p^{\prime}$ is
the next vertex after the edge $F_{I}\cap W$ in clockwise order, then

$\displaystyle\Pr[y_{I}^{\top}p\geq
y_{I}^{\top}p^{\prime}+\frac{1}{L^{3}d^{5}\log^{2}n}\mid E_{I}]\geq 0.1.$

here $y_{I}\in W$ is the outer unit normal vector of the polygon
$\operatorname{conv}(\hat{a}_{1},\cdots,\hat{a}_{n})\cap W$ on the edge
$F_{I}\cap W$. Then we can use Theorem 27 by setting
$L=4\sigma^{-1}\sqrt{d\log n}$, $\gamma=\Omega(\frac{1}{L^{3}d^{5}\log^{2}n})$
and $\mathbb{E}[\max_{i\in[n]}\|\pi_{W}(a_{i})\|]=1.5$, to find

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(\hat{a}_{1},\cdots,\hat{a}_{n})\right)\right]\leq$
$\displaystyle 10+O(\sqrt{\sigma^{-3}d^{13/2}\log^{5/2}n}).$

Finally, from Lemma 29, we conclude that

$\displaystyle\mathbb{E}\left[\operatorname{edges}\left(\operatorname{conv}(a_{1},\cdots,a_{n})\right)\right]$
$\displaystyle\leq 11+O(\sqrt{\sigma^{-3}d^{13/2}\log^{5/2}n})$
$\displaystyle=O\left(\sigma^{-3/2}d^{13/4}\log^{5/4}n\right).$

∎

The rest of this section will be structured as follows. In section 5.2 we use
a deterministic argument to establish sufficient criteria for the conclusion
of Lemma 35 to hold. In section 5.3 and section 5.4, we prove that these
conditions hold with good probability conditional on $E_{I}$. The proof of
Lemma 35 is then finished in section 5.5.

###  5.2 Deterministic conditions for a good separator

In this subsection, we prove the following lemma:

######  Lemma 36.

Let $W\subset\mathbb{R}^{d}$ be a two-dimensional linear subspace,
$Q=\operatorname{conv}(a_{1},\cdots,a_{n})\subset\mathbb{R}^{d}$ be a non-
degenerate polytope with a non-degenerate intersection with $W$ such that
$\max_{i,j\in[n]}\|a_{i}-a_{j}\|\leq 3$ and $W\cap Q\neq\emptyset$. Fix any
facet $F$ of $Q$ such that $F\cap W\neq\emptyset$ and any ridge $R\subset F$
of $F$ such that $W\cap R$ is a singleton set $\\{p\\}$. Let $\delta,r\geq 0$
be such that

  1. 1.

(distance between $F$ and other vertices) $\forall a_{k}\notin
F,\operatorname{dist}(\operatorname{affhull}(F),a_{k})\geq\delta$;

  2. 2.

(Inner radius of $R$) $\operatorname{dist}(F\cap W,\partial R)\geq r$.

Then the outer unit normal vector $\bar{\theta}\in W$ to the edge $F\cap W$
satisfies

$\bar{\theta}^{\top}p-\bar{\theta}^{\top}p^{\prime}\geq\delta r/3$

for any $p\in F\cap W$, here $p^{\prime}\in Q\cap W$ is the next vertex after
$F\cap W$ in clockwise order.

###### Proof.

Write $R^{\prime}$ for the ridge of $Q$ such that
$\\{p^{\prime}\\}=R^{\prime}\cap W$. Since $p^{\prime}\in Q\cap W$ is adjacent
to vertex $p$ and the edge $F\cap W$, by 23 we may relabel the $a_{i}$ such
that $R^{\prime}=\operatorname{conv}(a_{1},\dots,a_{d-1})$,
$R=\operatorname{conv}(a_{2},\dots,a_{d}),$ and
$F=\operatorname{conv}(a_{2},\dots,a_{d+1})$ without loss of generality. Let
$\theta\in\mathbb{S}^{d-1}$ denote the outward unit normal to $F$. This normal
vector satisfies

$\delta\leq\min_{\begin{subarray}{c}i\in[n]\\\ a_{i}\notin
F\end{subarray}}\theta^{T}(p-a_{i})\leq\theta^{\top}(p-a_{1}).$

Let $s\in\mathbb{S}^{d-1}$ be the unit vector indicating the direction of the
(one-dimensional) line $F\cap W$, i.e., for which $F\cap W=s+F\cap W$. This
vector is unique up to sign. Also, let
$\bar{\theta}=\pi_{W}(\theta)/\|\pi_{W}(\theta)\|$ be the outward unit normal
to $F\cap W$ in the two-dimensional plane $W$. Notice that $\theta$ and $s$
form an orthonormal basis of $W$. Therefore we get

$\displaystyle\bar{\theta}^{\top}(p-p^{\prime})=\bar{\theta}^{\top}\pi_{s^{\perp}}(p-p^{\prime})=\|\pi_{s^{\perp}}(p-p^{\prime})\|$
(14)

Here the last equality comes from $(p-p^{\prime})\in
W=\mathrm{span}(\bar{\theta},s)$, thus
$\pi_{s^{\perp}}(p-p^{\prime})=\pi_{\bar{\theta}}(p-p^{\prime})$.

Now we focus on the $(d-1)$-dimensional space $s^{\perp}$, and consider the
projections $\pi_{s^{\perp}}(a_{1}),\cdots,\pi_{s^{\perp}}(a_{d})$. Since the
diameter of $\operatorname{conv}(a_{1},\cdots,a_{d})$ is at most $3$, we have
$\max_{i,j\in[d]}\|\pi_{s^{\perp}}(a_{i})-\pi_{s^{\perp}}(a_{j})\|\leq 3$.
Because $\theta\in s^{\perp}$ and $\theta$ is a unit normal vector of $R$, we
know that $\theta$ is also a unit normal of
$\pi_{s^{\perp}}(R)=\pi_{s^{\perp}}(\operatorname{conv}(a_{2},\cdots,a_{d}))$.
This gives

$\operatorname{dist}(\pi_{s^{\perp}}(a_{1}),\operatorname{affhull}(\pi_{s^{\perp}}(R)))=\theta^{\top}(p-a_{1})\geq\delta.$

Also, since $\operatorname{dist}(F\cap W,\partial R)\geq r$ where $F\cap
W=\\{p+st:t\in R\\}$ is one-dimensional. After the projection to $s^{\perp}$
we have

$\operatorname{dist}(\pi_{s^{\perp}}(p),\partial\pi_{s^{\perp}}(R))=\operatorname{dist}(F\cap
W,\partial R)\geq r.$

Therefore by Lemma 37, we have

$\displaystyle\|\pi_{s^{\perp}}(p)-\pi_{s^{\perp}}(p^{\prime})\|\geq\operatorname{dist}(\pi_{s^{\perp}}(p),\operatorname{affhull}(\pi_{s^{\perp}}(R^{\prime})))\geq
r\delta/3,$

where the first step comes from
$\pi_{s^{\perp}}(p^{\prime})\in\operatorname{affhull}(\pi_{s^{\perp}}(R^{\prime}))$.
The lemma then follows from (14). ∎

######  Lemma 37.

Given $b_{1},\cdots,b_{d}\in\mathbb{R}^{d-1}$ such that
$\operatorname{conv}(b_{1},\cdots,b_{d})$ is non-degenerate. Suppose

  1. 1.

$\forall i,j\in[d]$, $\|b_{i}-b_{j}\|\leq 3$;

  2. 2.

$\operatorname{dist}(b_{1},\operatorname{affhull}(b_{2},\cdots,b_{d}))\geq\delta$;

  3. 3.

There exists $q\in\operatorname{conv}(b_{2},\cdots,b_{d})$ such that
$\operatorname{dist}(q,\partial(\operatorname{conv}(b_{2},\cdots,b_{d})))\geq
r$.

Then we have
$\operatorname{dist}(q,\operatorname{affhull}(b_{1},\cdots,b_{d-1}))\geq
r\delta/3$.

###### Proof.

For simplicity, write $B=\operatorname{conv}(b_{2},\cdots,b_{d})$ and
$B^{\prime}=\operatorname{conv}(b_{1},\cdots,b_{d-1})$. Let
$q^{\prime}=\pi_{B^{\prime}}(q)$ be the point closest to $q$ on
$\operatorname{affhull}(B^{\prime})$.

Let $x=(B\cap B^{\prime})\cap\operatorname{affhull}(b_{1},q,q^{\prime})$ be
its intersection between the two-dimensional plane
$\operatorname{affhull}(b_{1},q,q^{\prime})$ and the $(d-3)$-dimensional ridge
$B\cap B^{\prime}$ (which gives a unique point). (See Figure 2 for an
illustration). Consider the triangle $\operatorname{conv}(b_{1},q,x)$ and
calculate its area in two different ways. On one hand, it has base
$\operatorname{conv}(b_{1},x)$ of length $\|b_{1}-x\|\leq 3$ with height
$\operatorname{dist}(q,\operatorname{affhull}(b_{1},x))=\|q-q^{\prime}\|$,
which gives that the area of the triangle is at most $\frac{3\|q-q\|}{2}$. On
the other hand, this triangle has base $\operatorname{conv}(x,q)$ of length
$\|x-q\|\geq\operatorname{dist}(q,\partial(B))\geq r$ with height
$\operatorname{dist}(b_{1},\operatorname{affhull}(x,q))\geq\operatorname{dist}(b_{1},B)\geq\delta$,
which gives that the area of the triangle is at least $\frac{r\delta}{2}$.

Therefore we have
$\operatorname{dist}(q,\operatorname{affhull}(B^{\prime}))=\|q-q^{\prime}\|\geq\frac{r\delta}{3}$
as desired.

$\displaystyle b_{1}$$\displaystyle B$$\displaystyle B^{\prime}$$\displaystyle
q$$\displaystyle{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}q^{\prime}}$$\displaystyle{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}x}$$\displaystyle
b_{d}$ Figure 2: Illustration of Lemma 37 when $d-1=3$. In gray is the
intersection between the two-dimensional plane
$\operatorname{affhull}(b_{1},q,q^{\prime})$ and
$\operatorname{conv}(b_{1},\cdots,b_{d})$. The red triangle is
$\operatorname{conv}(b_{1},x,q)$. The bottom face is $B$ and the back face is
$B^{\prime}$.

∎

###  5.3 Randomized Lower-Bound for $\delta$: Distance between vertices and
facets

In this section, we show that the affine hull of a given facet $F$ of the
polytope $\operatorname{conv}(a_{1},\cdots,a_{n})$ is $\Omega(\frac{1}{Ld\log
n})$-far away to other vertices with good probability, or in other words, the
distance $\delta$ in Lemma 36 is at least $\Omega(\frac{1}{Ld\log n})$ with
good probability. Our main result of this section is as follows:

######  Lemma 38 (Randomized lower-bound for $\delta$).

Let $a_{1},\dots,a_{n}\in\mathbb{R}^{d}$ be independent $L$-log-Lipshchitz
random vectors. For any $I\in\binom{[n]}{d}$ such that $\Pr[E_{I}]\geq
10\binom{n}{d}^{-1}$, we have

$\Pr[\min_{k\in[n]\backslash
I}\operatorname{dist}(\operatorname{affhull}(F_{I}),a_{k})\geq\frac{1}{10e^{3}dL\log
n})\mid E_{I}]\geq 0.72.$

To show Lemma 38, we fix any $I\in\binom{[n]}{d}$ of consideration. Without
loss of generality, assume $I=[d]$ and write $E=E_{[d]}$. To show Lemma 38, we
define the following event $B_{\varepsilon}$ indicating that the distance from
$F_{[d]}$ to other vertices is at least $\varepsilon$.

######  Definition 39 (Separation by the margin of a facet).

Let $\theta\in\mathbb{S}^{d-1},t\in\mathbb{R}$ be as in Definition 17. For any
$\varepsilon>0$, let $B_{\varepsilon}^{+}$ denote the event that
$\theta^{\top}a_{i}<t-\varepsilon$ for all $i\in[n]\setminus[d]$ and
$B_{\varepsilon}^{-}$ denote the event that $\theta^{\top}a_{i}>t+\varepsilon$
for all $i\in[n]\setminus[d]$. We write
$B_{\varepsilon}=B_{\varepsilon}^{+}\vee B_{\varepsilon}^{-}$.

In the following lemma, we show that for sufficiently small $\varepsilon$,
$\Pr[E\wedge B_{\varepsilon}]$ is a constant fraction of $\Pr[E]$.

######  Lemma 40.

For any $\varepsilon\leq\frac{1}{10e^{3}Ld\log n}$ it holds that

$\Pr[E]\leq\binom{n}{d}^{-1}+\frac{5}{4}\cdot\Pr[E\wedge B_{\varepsilon}].$

###### Proof.

Writing random variables as subscripts to denote which expectation is over
which variables, we start by using Fubini’s theorem to write

$\Pr_{a_{1},\dots,a_{n}}[E]=\mathbb{E}_{a_{1},\dots,a_{d}}[\Pr_{a_{d+1},\dots,a_{n}}[E]].$

Fix any choice of $a_{1},\dots,a_{d}\in\mathbb{R}^{n}$ subject to the non-
degeneracy assumptions in Lemma 22 and
$\operatorname{conv}(a_{1},\dots,a_{d})\cap W\neq\emptyset$. Define
$\theta\in\mathbb{S}^{d-1},t>0$ as described in Definition 17, i.e.
$\theta^{\top}a_{i}=t$ for each $i\in[d]$. Write $s_{i}=\theta^{\top}a_{i}$
for each $i\in[n]\setminus[d]$. We note that $s_{i}$ is an $L$-log-Lipschitz
random variable for all $i\in[n]\backslash[d]$. Moreover, over the remaining
randomness in $a_{d+1},\dots,a_{n}$, we have
$\Pr[E]=\Pr[B_{0}^{+}]+\Pr[B_{0}^{-}]$ and
$\Pr[B_{\varepsilon}]=\Pr[B_{\varepsilon}^{+}]+\Pr[B_{\varepsilon}^{-}]$. We
will prove that
$\Pr[B_{\varepsilon}^{+}]\leq\frac{1}{2\binom{n}{d}}+\frac{5}{4}\Pr[B_{0}^{+}]$,
and the appropriate statement will follow for $B_{\varepsilon}^{-}$
analogously. Putting together this will prove the lemma.

If $\Pr[B_{0}^{+}]\leq\frac{1}{2}\binom{n}{d}^{-1}$ then the desired
inequality holds directly. Otherwise, fix any $i\in[n]\backslash[d]$ and let
$\mu_{i}$ denote the induced probability density function of $s_{i}$. We then
have

$\displaystyle\Pr[s_{i}\geq t-\varepsilon\mid s_{i}\leq t]$
$\displaystyle=\frac{\int_{-\varepsilon}^{0}\mu_{i}(t+s)\mathrm{d}s}{\int_{-\infty}^{0}\mu_{i}(t+s)\mathrm{d}s}$
$\displaystyle=\frac{\varepsilon L\int_{-1/L}^{0}\mu_{i}(t+\varepsilon
Ls)\mathrm{d}s}{\int_{-\infty}^{0}\mu_{i}(t+s)\mathrm{d}s}$ $\displaystyle\leq
e\frac{\varepsilon
L\int_{-1/L}^{0}\mu_{i}(t+s)\mathrm{d}s}{\int_{-\infty}^{0}\mu_{i}(t+s)\mathrm{d}s}$
$\displaystyle=e\frac{\varepsilon
L\int_{0}^{1/L}\mu_{i}(t+s-1/L)\mathrm{d}s}{\int_{-\infty}^{1/L}\mu_{i}(t+s-1/L)\mathrm{d}s}$
$\displaystyle\leq e^{3}\frac{\varepsilon
L\int_{0}^{1/L}\mu_{i}(t+s)\mathrm{d}s}{\int_{-\infty}^{1/L}\mu_{i}(t+s)\mathrm{d}s}$
$\displaystyle=e^{3}\varepsilon L\Pr[s_{i}\geq t\mid s_{i}\leq t+1/L]$
$\displaystyle\leq e^{3}\varepsilon L\Pr[s_{i}\geq t].$ (15)

The first two inequalities above follow from $L$-log-Lipschitzness of
$\mu_{i}$. The third follows from the fact that $s_{i}\geq t+1/L$ implies
$s_{i}\geq t$. As such we can, for fixed $t,\theta,$ upper-bound the
probability over $s_{1},\dots,s_{d}$ that, conditional on $B_{0}^{+}$, there
exists a vertex being $\varepsilon$-close to $\operatorname{affhull}(F_{I})$:

$\displaystyle\Pr[\neg B_{\varepsilon}^{+}\mid B_{0}^{+}]$
$\displaystyle=\Pr[\exists i\in[n]\setminus[d]:s_{i}\geq t-\varepsilon\mid
B_{0}^{+}]$ (By union bound)
$\displaystyle\leq\sum_{i\in[n]\setminus[d]}\Pr[s_{i}\geq t-\varepsilon\mid
B_{0}^{+}]$ $\displaystyle\leq\sum_{i\in[n]\setminus[d]}e^{3}\varepsilon
L\Pr[s_{i}\geq t\mid B_{0}^{+}]$ $\displaystyle=e^{3}\varepsilon
L\;\mathbb{E}[\\#\\{i\in[n]\setminus[d]:s_{i}\geq t\\}\mid B_{0}^{+}]$
$\displaystyle=e^{3}\varepsilon
L\;\mathbb{E}[\\#\\{i\in[n]\setminus[d]:s_{i}\geq t\\}].$ (16)

To interpret the last equality above, we observe that
$\\#\\{i\in[n]\setminus[d]:s_{i}\geq t\\}=0$ if and only if $B_{0}^{+}$
happens. The upper bound
$\Pr[B_{0}^{+}]\leq\frac{5}{4}\Pr[B_{\varepsilon}^{+}]$ will follow from (16)
together with 41 and our choice of $\varepsilon$. ∎

######  Claim 41.

Conditional on $\theta,t$, if $\Pr[B_{0}^{+}]\geq n^{-d}$ then
$\mathbb{E}[\\#\\{i\in[n]\setminus[d]:s_{i}\geq t\\}]\leq 2d\log n$. If
$\Pr[B_{0}^{-}\mid\theta,t]\geq n^{d}$ then
$\mathbb{E}[\\#\\{i\in[n]\setminus[d]:s_{i}\leq t\\}]\leq 2d\log n$.

###### Proof.

We prove the first implication, and the second follows analogously. For each
$i\in[n]\setminus[d]$, let $X_{i}\in\\{0,1\\}$ have value $1$ if and only if
$s_{i}\geq t$. Since $\theta,t$ are fixed and depend only on
$a_{1},\dots,a_{d}$, the random variables $X_{d+1},\dots,X_{n}$ are
independent. Write $X=\sum_{i=d+1}^{n}X_{i}$. The Chernoff bound gives

$\Pr[X=0]\leq\exp\left(-\frac{\mathbb{E}[X]}{2}\right).$

As such, $\mathbb{E}[X]>2d\log n$ would imply $\Pr[X=0]<n^{-d}$, contradicting
the original assumption that $\Pr[X=0]\geq n^{-d}.$ It follows that
$\mathbb{E}[X]\leq 2d\log n$. ∎

Now we can prove Lemma 38 using Lemma 40.

###### Proof of Lemma 38.

Fix any $I\in\binom{[n]}{d}$. By Lemma 40, we have that
$\Pr[E_{I}]\leq\binom{n}{d}^{-1}+\frac{5}{4}\cdot\Pr[E_{I}\wedge(\delta\geq\varepsilon)]$
for $\varepsilon=\frac{1}{10e^{3}Ld\log n}$. This gives that

$\displaystyle\frac{\Pr[E_{I}\wedge(\delta\geq\varepsilon)]}{\Pr[E_{I}]}\geq\frac{4}{5}-\binom{n}{d}^{-1}\cdot\frac{4}{5\Pr[E_{I}]}$

Moreover, since $\Pr[E_{I}]\geq 10\binom{n}{d}^{-1}$, we have

$\displaystyle\Pr[(\delta\geq\varepsilon)\mid E_{I}]$
$\displaystyle=\frac{\Pr[E_{I}\wedge(\delta\geq\varepsilon)]}{\Pr[E_{I}]}$
$\displaystyle\geq\frac{4}{5}-\binom{n}{d}^{-1}\cdot\frac{4}{5\Pr[E_{I}]}\geq
0.72,$

as desired. ∎

###  5.4 Randomized Lower-Bound for $r$: Inner Radius of a Ridge Projected
onto $(d-1)$-Dimensional Space

The remaining lemma, which has no analogue when $d=2$, will require more
technical effort. Its proof is similar to Lemma 4.1.1 (Distance bound) in
[ST04].

######  Lemma 42 (Randomized Lower-bound for $r$).

Let $a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$ be independent $L$-log-Lipschitz
random vectors. Let $D$ denote the event that $\forall
i,j\in[n],\|a_{i}-a_{j}\|\leq 3$. Fix any $I\in\binom{[n]}{d}$ and any
$J\in\binom{I}{d-1}$, we have

$\Pr[\operatorname{dist}(W\cap\operatorname{affhull}(a_{i}:i\in
I),\partial\operatorname{conv}(a_{j}:j\in J))\leq\frac{1}{19200d^{4}L^{2}}\mid
E_{I}\wedge A_{J}]\leq 0.1+\Pr[\neg D\mid E_{I}\wedge A_{J}].$

###### Proof.

We may assume without loss of generality that $I=[d]$ and $J=[d-1]$. Apply the
change of variables $\phi$ as in Definition 17 to $\\{a_{i}:i\in[d]\\}$ and
obtain

$\displaystyle\phi(\theta,t,b_{1},\cdots,b_{d})=(a_{1},\cdots,a_{d}).$

where
$\theta\in\mathbb{S}^{d-1},t\in\mathbb{R},b_{1},\cdots,b_{d}\in\mathbb{R}^{d-1}$.
For any $i\in[n]$, let $\mu_{i}$ denote the probability density function of
$a_{i}$. Writing the conditioning as part of the pdf, we find that the joint
probability density of $t,\theta,b_{1},\cdots,b_{d},a_{d+1},\dots,a_{n}$ is
proportional to

$\displaystyle\operatorname{vol}_{d-1}(b_{1},\cdots,b_{d})\cdot\prod_{i=1}^{d}\bar{\mu}_{i}(t,\theta,b_{i})\cdot\prod_{i=d+1}^{n}\mu_{i}(a_{i})\cdot
1[E_{[d]}\wedge A_{[d-1]}],$ (17)

where $\operatorname{vol}_{d-1}(\cdot)$ is the volume function of the
$(d-1)$-dimensional simplex, and
$\bar{\mu}_{i}(t,\theta,b_{i})=\mu_{i}(t\theta+R_{\theta}(b_{i}))$ is the
induced probability density of $b_{i}$, which is $L$-log-Lipschitz, and
$1[\cdot]$ denotes the indicator function. Write $S$ for the event that

$\operatorname{dist}(W\cap\operatorname{affhull}(a_{i}:i\in
I),\partial\operatorname{conv}(a_{j}:j\in J))\leq\frac{1}{19200d^{4}L^{2}}.$

In this language, our goal is to prove that $\Pr[S]\leq 0.1+\Pr[\neg D]$.

Let $D^{\prime}$ denote the event that $\|b_{i}-b_{j}\|\leq 3$ for all
$i,j\in[d]$. Each of the events $E_{I},A_{J},S,D^{\prime},D$ are functions of
the random variables $\theta,t,b_{1},\dots,b_{d},a_{d+1},\dots,a_{n}$. We then
use Fubini’s theorem to write

$\displaystyle\Pr_{\theta,t,b_{1},\dots,b_{d},a_{d+1},\dots,a_{n}}[S]$
$\displaystyle=\mathbb{E}_{\theta,t,a_{d+1},\dots,a_{n}}[\Pr_{b_{1},\dots,b_{d}}[S]]$

With probability $1$ over the choice of $\theta,t,a_{d+1},\dots,a_{n}$, the
inner term satisfies all the conditions of Lemma 43. Specifically, since the
value of $1[E_{[d]}]$ is already fixed, the intersection
$\ell=(t\theta+\theta^{\perp})\cap W$ is a line, the event $A_{[d-1]}$ is
equivalent to $\ell\cap\operatorname{conv}(b_{1},\dots,b_{d-1})\neq\emptyset$.
From Lemma 18, the joint probability distribution of $b_{1},\dots,b_{d}$ is
thus proportional to

$\displaystyle\operatorname{vol}_{d-1}(b_{1},\cdots,b_{d})\cdot\prod_{i=1}^{d}\bar{\mu}_{i}(b_{i})\cdot
1[\ell\cap\operatorname{conv}(b_{1},\dots,b_{d-1}\neq\emptyset]$

Applying Lemma 43 to the term $\Pr_{b_{1},\dots,b_{d}}[S]$ we find

$\displaystyle\mathbb{E}_{\theta,t,a_{d+1},\dots,a_{n}}\big{[}\Pr_{b_{1},\dots,b_{d}}[S]\big{]}$
$\displaystyle\leq\mathbb{E}_{\theta,t,a_{d+1},\dots,a_{n}}\big{[}0.1+\Pr_{b_{1},\dots,b_{d}}[\neg
D^{\prime}]\big{]}$ $\displaystyle=0.1+\Pr[\neg D^{\prime}]\leq 0.1+\Pr[\neg
D],$

using Fubini’s theorem for the equality and the fact that $\neg D^{\prime}$
implies $\neg D$ for the final inequality. ∎

######  Lemma 43 (Randomized lower bound for $r$ after change of variables).

Let $b_{1},\dots,b_{d}\in\mathbb{R}^{d-1}$ be random vectors with joint
probability density proportional to

$\displaystyle\operatorname{vol}_{d-1}(b_{1},\cdots,b_{d})\cdot\prod_{i=1}^{d}\bar{\mu}_{i}(b_{i})$

where $\bar{\mu}_{i}$ is $L$-log-Lipschitz for each $i\in[d]$. Let
$D^{\prime}$ denote the event that the set $\\{b_{1},\dots,b_{d}\\}$ has
Euclidean diameter of at most $3$. Given any fixed one-dimensional line
$\ell\subset\mathbb{R}^{d-1}$, we have that

$\displaystyle\Pr$
$\displaystyle\left[\left(\operatorname{dist}\big{(}\ell,\partial\operatorname{conv}(b_{1},\dots,b_{d-1})\big{)}<\frac{1}{19200d^{4}L^{2}}\right)\mid\ell\cap\operatorname{conv}(b_{1},\dots,b_{d-1})\neq\emptyset\right]$
$\displaystyle\leq
0.1+\Pr[D^{\prime}\mid\ell\cap\operatorname{conv}(b_{1},\dots,b_{d-1})\neq\emptyset].$

###### Proof.

We can write the distance from $\ell$ to
$\partial\operatorname{conv}(b_{1},\dots,b_{d-1})$ as

$\displaystyle\operatorname{dist}\big{(}\ell,\partial\operatorname{conv}(b_{1},\dots,b_{d-1})\big{)}$
$\displaystyle=$
$\displaystyle\min_{i\in[d-1]}\lambda_{i}\cdot\operatorname{dist}(\pi_{w^{\perp}}(b_{i}),\operatorname{affhull}(\pi_{w^{\perp}}(b_{j}):j\in[d-1],j\neq
i))$ $\displaystyle\geq$
$\displaystyle\min_{i\in[d-1]}\lambda_{i}\cdot\min_{k\in[d-1]}\operatorname{dist}(\pi_{w^{\perp}}(b_{k}),\operatorname{affhull}(\pi_{w^{\perp}}(b_{j}):j\in[d-1],j\neq
k))$

Abbreviate, for $k\in[d-1]$,

$r_{k}=\operatorname{dist}(\pi_{w^{\perp}}(b_{k}),\operatorname{affhull}(\pi_{w^{\perp}}(b_{j}):j\in[d-1],j\neq
k)).$

Let $T$ denote the event that
$\ell\cap\operatorname{conv}(b_{1},\dots,b_{d-1})\neq\emptyset$. We now find
using the union bound, for $\alpha,\beta>0$,

$\displaystyle\Pr[\operatorname{dist}(\ell,\partial\operatorname{conv}(b_{1},\dots,b_{d-1}))<\alpha\beta\mid
T]$ $\displaystyle\leq\Pr[\min_{i\in[d-1]}\lambda_{i}<\alpha\mid
T]+\Pr[\min_{k\in[d-1]}r_{k}<\beta\mid T]$
$\displaystyle\leq\Pr[\min_{i\in[d-1]}\lambda_{i}<\alpha\mid D^{\prime}\wedge
T]+\Pr[D^{\prime}\mid T]+\Pr[\min_{k\in[d-1]}r_{k}<\beta\mid T]$

By Lemma 44 we know that $\Pr[\min_{i\in[d-1]}\lambda_{i}<\alpha\mid
D^{\prime}\wedge T]\leq 0.05$ for $\alpha=\frac{1}{120d^{2}L}$. By Lemma 45,
we know that $\Pr[\min_{k\in[d-1]}r_{k}<\beta\mid
T]\leq\sum_{k\in[d-1]}\Pr[r_{k}<\beta\mid T]\leq 0.05$ for
$\beta=\frac{1}{160d^{2}L}$. This proves the lemma. ∎

The following two Lemmas are the key to prove Lemma 43. Let
$\lambda\in\mathbb{R}^{d-1}_{\geq 0}$ be the unique solution to
$\sum_{i=1}^{d-1}\lambda_{i}b_{i}=\ell\cap\operatorname{conv}(b_{1},\cdots,b_{d-1})$
and $\sum_{i=1}^{d-1}\lambda_{i}=1$. First, we use Lemma 44 to show that the
every convex parameter $\lambda_{i}$ is at least $\Omega(1/d^{2}L)$ with
constant probability.

######  Lemma 44 (Lower-bound for Convex Parameters of Vertices on the Ridge).

Let $b_{1},\cdots,b_{d}\in\mathbb{R}^{d-1}$ be random vectors with joint
probability density proportional to

$\operatorname{vol}_{d-1}(b_{1},\cdots,b_{d})\cdot\prod_{i=1}^{d}\bar{\mu}_{i}(b_{i})$

where each $\bar{\mu}_{i}:\mathbb{R}^{d-1}\to\mathbb{R}_{+}$ is $L$-log-
Lipschitz. Given any one-dimensional line $\ell\subset\mathbb{R}^{d-1}$ and
conditional on $\ell\cap\operatorname{conv}(b_{i}:i\in[d-1])\neq\emptyset$.
Let $\lambda\in\mathbb{R}^{d-1}_{+}$ be the unique solution to
$\sum_{i=1}^{d-1}\lambda_{i}b_{i}\in\ell\cap\operatorname{conv}(b_{i}:i\in[d-1])$.
Let $D^{\prime}$ denote the event that $\forall i,j\in[d]$,
$\|b_{i}-b_{j}\|\leq 3$. Then we have

$\Pr\left[\forall
i\in[d-1]:\lambda_{i}\geq\frac{1}{120d^{2}L}\middle|D^{\prime}\wedge\ell\cap\operatorname{conv}(b_{i}:i\in[d-1])\neq\emptyset\right]\geq
0.95.$

###### Proof.

By using the union bound, it suffices to prove for each $i\in[d-1]$ that

$\Pr[\lambda_{i}<\frac{1}{120d^{2}L}\mid
D^{\prime}\wedge\ell\cap\operatorname{conv}(b_{j}:j\in[d-1])\neq\emptyset]\leq\frac{1}{20d}.$

Fix any $i\in[d-1]$, without loss of generality $i=1$. We can assume
$\ell=w\mathbb{R}$ for a non-zero $w\in\mathbb{R}^{d-1}$. Thus $\lambda$ is
defined to satisfy $\sum_{j=1}^{d-1}\lambda_{j}\pi_{w^{\perp}}(b_{j})=0$.

For any given values of $b_{1}-b_{j}$, $j\in[d]$, which determine the shape of
the simplex $\operatorname{conv}(b_{j}:j\in[d])$, we prove the result using
the randomness in $\pi_{w^{\perp}}(b_{1})$, the position of the simplex in the
space $w^{\perp}$. For the remainder of this proof, we can consider all
$b_{j},j\in[d]$ to be functions of $b_{1}$. If we furthermore fix any value
for $w^{\top}b_{1}$ then
$\operatorname{vol}(\operatorname{conv}(b_{j}:j\in[d])$ is fixed, hence
$\pi_{w^{\perp}}(b_{1})$ has probability density
$\mu^{\prime}(\pi_{w^{\perp}}(b_{1}))\propto\prod_{j=1}^{d}\mu_{j}(b_{j})$,
which is $dL$-log-Lipschitz in $\pi_{w^{\perp}}(b_{1})$ with respect to the
$d-2$-dimensional Lebesgue measure on $w^{\perp}$.

Write $M=\operatorname{conv}(\pi_{w^{\perp}}(b_{1}-b_{j}):j\in[d-1])\subset
w^{\perp}$, for which we can see that $\pi_{w^{\perp}}(b_{1})\in M$ if and
only if $\lambda\geq 0$. It then remains to show that

$\displaystyle\Pr[\lambda_{1}<\frac{1}{120d^{2}L}\mid
D^{\prime}\wedge\pi_{w^{\perp}}(b_{1})\in M]<\frac{1}{20d}.$ (18)

For any $j\in[d-1]$, let $l_{j}:M\to[0,1]$ be the function sending any point
to its $j$’th convex coefficient, i.e., the functions satisfy
$\sum_{j=1}^{d-1}l_{j}(x)=1$ and
$\sum_{j=1}^{d-1}l_{j}(x)\cdot\pi_{w^{\perp}}(b_{1}-b_{j})=x$ for every $x\in
M$. For any $1\geq\alpha\geq 0$, observe that $l_{1}$ takes values in the
interval $[\alpha,1]$ on the set $(1-\alpha)M$. Hence we get

$\displaystyle\Pr[\lambda_{1}\geq\alpha\mid\pi_{w^{\perp}}(b_{1})\in M]$
$\displaystyle=\frac{\int_{M}\mu^{\prime}(x)\mathbf{1}[l_{1}(x)\geq\alpha]\mathrm{d}x}{\int_{M}\mu^{\prime}(x)\mathrm{d}x}$
$\displaystyle\geq\frac{\int_{(1-\alpha)M}\mu^{\prime}(x)\mathrm{d}x}{\int_{M}\mu^{\prime}(x)\mathrm{d}x}$
($\forall x\in(1-\alpha)M$, $l_{1}(x)\geq\alpha$)
$\displaystyle=\frac{(1-\alpha)^{d-2}\int_{M}\mu^{\prime}((1-\alpha)x)\mathrm{d}x}{\int_{M}\mu^{\prime}(x)\mathrm{d}x}$
$\displaystyle\geq(1-\alpha)^{d-2}\max_{x\in M}e^{-dL\|\alpha x\|}.$ (By
$d$-log-Lipschitzness of $\mu^{\prime}$)

By definition of $D^{\prime}$, we know that $M$ has Euclidean diameter at most
$3$. Thus we can bound $\|\alpha x\|\leq 3\alpha$ for any $x\in M$. Now take
$\alpha=\frac{1}{120d^{2}L}$, we find

$\displaystyle\Pr[(\lambda_{i}<\frac{1}{120d^{2}L})\mid
D^{\prime}\wedge\pi_{w^{\perp}}(b_{i})\in M]$ $\displaystyle\leq
1-\Pr[\lambda_{i}\geq\frac{1}{120d^{2}L}\mid
D^{\prime}\wedge\pi_{w^{\perp}}(b_{i})\in M]$ $\displaystyle\leq
1-(1-\frac{1}{120d^{2}L})^{d-2}e^{-1/40d}\leq 1/20d,$

where the last line comes from $L\geq 1$. Thus (18) holds as desired. ∎

In the second part, we lower bound the distance between each vertex $b_{j}$
(where $j\in[d-1]$) and the $(d-3)$-dimensional hyperplane spanned by the
other vertices $\operatorname{affhull}(b_{j}:j\in[d-1],j\neq i)$. We show the
following lemma:

######  Lemma 45.

Let $b_{1},\cdots,b_{d}\in\mathbb{R}^{d-1}$ be random vectors with joint
probability density proportional to

$\operatorname{vol}_{d-1}(b_{1},\cdots,b_{d})\cdot\prod_{i=1}^{d}\bar{\mu}_{i}(b_{i})$

where each $\bar{\mu}_{i}:\mathbb{R}^{d-1}\to[0,1]$ is $L$-log-Lipschitz.
Given any one-dimensional line $\ell\subset\mathbb{R}^{d-1}$, and let
$w\in\mathbb{S}^{d-2}$ be any unit direction of $\ell$. For any $i\in[d-1]$ we
have

$\displaystyle\Pr\Big{[}\operatorname{dist}\left(\pi_{w^{\perp}}(b_{i}),\operatorname{affhull}(\pi_{w^{\perp}}(b_{j}):j\in[d-1],j\neq
i)\right)\geq\frac{1}{160d^{2}L}~{}\Big{|}~{}$
$\displaystyle\ell\cap\operatorname{conv}(b_{i}:i\in[d-1])\neq\emptyset\Big{]}\geq
1-\frac{1}{20d}.$

###### Proof.

In the following arguments, we condition on
$\ell\cap\operatorname{conv}(b_{i}:i\in[d-1])\neq\emptyset$. Without loss of
generality, set $i=d-1$ and assume that $\ell$ is a linear subspace, i.e.,
$\pi(\ell)=0$.

We start with a coordinate transformation. Let $\phi\in
w^{\perp}\cap\mathbb{S}^{d-2}$ denote the unit vector satisfying
$\phi^{\top}b_{1}=\phi^{\top}b_{j}>0$ for all $j=1,\dots,d-2$. Note that
$\phi$ is uniquely defined almost surely: $w^{\perp}$ is a $(d-2)$-dimensional
linear space and we impose $(d-3)$ linear constraints
$\\{\phi^{\top}a_{1}=\phi^{\top}a_{j},\forall j\in[d-2]\\}$. Almost surely,
these give an one-dimensional linear subspace which, after adding the unit
norm and $b_{1}^{\top}\phi>0$ constraint, leaves a unique choice of $\phi$.

Now define $h\in\mathbb{R}$ by $h=\phi^{\top}b_{1}$ and define
$\alpha\in\mathbb{R}$ by $\alpha h=-\phi^{\top}b_{d-1}$. Since
$0\in\operatorname{conv}(\pi(b_{i}):i\in[d-1])$ but $\phi^{\top}b_{i}>0$ for
all $i\in[d-2]$, we must have $\alpha\geq 0$ for otherwise $\phi$ would
separate $\operatorname{conv}(\pi(b_{i}):i\in[d-1])$ from $0$. Again from
almost-sure non-degeneracy we get $\alpha>0$ and $h\neq 0$. We define the
following coordinate transformation:

$\displaystyle b_{j}$ $\displaystyle=h\phi+c_{j},\quad\forall j\in[d-2]$
$\displaystyle b_{d-1}$ $\displaystyle=-\alpha h\phi+c_{d-1}$

where for each $j\in[d-1]$, $c_{j}\in\phi^{\perp}\cap H$ has $(d-3)$ degrees
of freedom. From here on out, we consider the vertices
$(b_{1},\cdots,b_{d-1})$ to be a function of
$(h,\alpha,\phi,c_{1},\dots,c_{d-1})$. Again by Lemma 18, the induced joint
probability density on the random variables
$(h,\alpha,\phi,c_{1},\dots,c_{d-1},b_{d})$, is proportional to

$\displaystyle\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\dots,b_{d}))\cdot\operatorname{vol}_{d-3}(\operatorname{conv}(c_{1},\cdots,c_{d-2}))\cdot\prod_{j=1}^{d}\bar{\mu}_{j}(b_{j})$
$\displaystyle\propto~{}$
$\displaystyle\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\dots,b_{d}))\cdot\operatorname{vol}_{d-3}(\operatorname{conv}(\pi_{w^{\perp}}(c_{1}),\dots,\pi_{w^{\perp}}(c_{d-2})))\cdot\prod_{j=1}^{d}\bar{\mu}_{j}(b_{j}).$

Condition on the exact values of $(\alpha,\phi,c_{1},\dots,c_{d-1},b_{d})$.
Note that the event $0\in\operatorname{conv}(\pi(b_{i}):i\in[d-1])$ depends
only on these variables and not on $h$, and the same is true for
$\operatorname{vol}_{d-3}(\operatorname{conv}(\pi_{w^{\perp}}(c_{1}),\dots,\pi_{w^{\perp}}(c_{d-2})))$.
By Lemma 18, the induced probability density on $h$ is now proportional to

$\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\dots,b_{d}))\cdot\prod_{j=1}^{d-1}\tilde{\mu}_{j}(h),$

where $\tilde{\mu}_{j}(h):=\bar{\mu}_{j}(h\phi+c_{j}),j\in[d-2]$ and
$\tilde{\mu}_{d-1}(h):=\bar{\mu}_{d-1}(\alpha h\phi+c_{d-1})$. Since each
$\bar{\mu}_{j}$ is $L$-log-Lipschitz, it follows that the product
$\prod_{j=1}^{d-1}\tilde{\mu}_{j}(h)$ is $(d-2+\alpha)L\leq d(1+\alpha)L$-log-
Lipschitz in $h$.

Next, consider the volume term. We can write
$\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\dots,b_{d}))$ as a
constant depending on $d$ times the absolute value of the determinant of
matrix

$\begin{bmatrix}(b_{1}-b_{d})^{\top}\\\ \vdots\\\
(b_{d-1}-b_{d})^{\top}\end{bmatrix}=\begin{bmatrix}(t\phi+c_{1}-b_{d})^{\top}\\\
\vdots\\\ (t\phi+c_{d-2}-b_{d})^{\top}\\\ (-\alpha
t\phi+c_{d-1}-b_{d})^{\top}\end{bmatrix}=\begin{bmatrix}(c_{1}-b_{d})^{\top}\\\
\vdots\\\ (c_{d-2}-b_{d})^{\top}\\\
(c_{d-1}-b_{d})^{\top}\end{bmatrix}+h\cdot\begin{bmatrix}1\\\ \vdots\\\ 1\\\
-\alpha\end{bmatrix}\phi^{\top}.$

where $\theta\in\mathbb{S}^{d-1}$ denotes a normal vector to $H$. Define

$\displaystyle B:=\begin{bmatrix}(c_{1}-b_{d})^{\top}\\\ \vdots\\\
(c_{d-2}-b_{d})^{\top}\\\ (c_{d-1}-b_{d})^{\top}\\\
\theta^{\top}\end{bmatrix},v:=\begin{bmatrix}1\\\ \vdots\\\ 1\\\ -\alpha\\\
0\end{bmatrix}.$

Then by the matrix determinant lemma, we can write the volume as the absolute
value of an affine function of $t$ (which is a convex function):

$\displaystyle\operatorname{vol}_{d-1}(\operatorname{conv}(b_{1},\cdots,b_{d}))$
$\displaystyle=\left|\det(B)+hv\phi^{\top}\right|$
$\displaystyle=\left|\det(B)(1+\phi^{\top}B^{-1}v\cdot h)\right|$

Hence, we have found a convex function $k:\mathbb{R}\to\mathbb{R}_{\geq 0}$
and a $d(1+\alpha)L$-log-Lipschitz function $\nu:\mathbb{R}\to\mathbb{R}_{\geq
0}$ such that $h$ has probability density proportional to $k(h)\cdot\nu(h)$.

To finalize the argument, we write
$\operatorname{dist}(\pi(b_{i}),\operatorname{affhull}(\pi(b_{j}):j\in[d-1],j\neq
i))=|(1+\alpha)h|$. It follows that the signed distance $(1+\alpha)h$ has a
probability density function proportional to the product of a $dL$-log-
Lipschitz function and a convex function. The result follows from Lemma 46 by
plugging in the signed distance $(1+\alpha)h$ and
$K=dL,\varepsilon=\frac{1}{160d^{2}L}$. ∎

######  Lemma 46.

Assume that $h:\mathbb{R}\to\mathbb{R}_{\geq 0}$ is a $K$-log-Lipschitz
function and $g:\mathbb{R}\to\mathbb{R}_{\geq 0}$ is a convex function such
that $\int_{-\infty}^{\infty}g(x)\cdot h(x)\mathrm{d}x=1$. Suppose that
$X\in\mathbb{R}$ is distributed with probability density $g(X)\cdot h(X)$. For
any $\varepsilon>0$ we have $\Pr[X\in[-\varepsilon,\varepsilon]]\leq
8\varepsilon K$.

###### Proof.

We can assume that $\varepsilon<1/(8K)$, for otherwise the bound is trivial.
First, we use the rudimentary upper bound

$\Pr\big{[}X\in[-\varepsilon,\varepsilon]\big{]}\leq\Pr\big{[}X\in[-\varepsilon,\varepsilon]\mid
X\in[-1/K,1/K]\big{]}=\frac{\int_{-\varepsilon}^{\varepsilon}g(x)\cdot
h(x)\mathrm{d}x}{\int_{-1/K}^{1/K}g(x)\cdot h(x)\mathrm{d}x}.$

Log-Lipschitzness implies that for any $\gamma>0$ we have

$e^{-\gamma
K}h(0)\int_{-\gamma}^{\gamma}g(x)\mathrm{d}x\leq\int_{-\gamma}^{\gamma}g(x)\cdot
h(x)\mathrm{d}x\leq e^{\gamma K}h(0)\int_{-\gamma}^{\gamma}g(x)\mathrm{d}x,$

and hence we get

$\Pr[X\in[-\varepsilon,\varepsilon]]\leq e^{1+\varepsilon
K}\frac{\int_{-\varepsilon}^{\varepsilon}g(x)\mathrm{d}x}{\int_{-1/K}^{1/K}g(x)\mathrm{d}x}\leq
e^{1+\varepsilon
K}\frac{2\varepsilon\max_{x\in[-\varepsilon,\varepsilon]}g(x)}{\int_{-1/K}^{1/K}g(x)\mathrm{d}x}$

Since $g(x)$ is convex, at least one of

$\displaystyle\max_{x\in[-\varepsilon,\varepsilon]}g(x)\leq\min_{x\in[-1/K,-\varepsilon]}g(x)\quad\text{or}\quad\max_{x\in[-\varepsilon,\varepsilon]}g(x)\leq\min_{x\in[\varepsilon,1/K]}g(x)$

holds. Without loss of generality, assume the second case holds. Then we bound

$\frac{\max_{x\in[-\varepsilon,\varepsilon]}g(x)}{\int_{-1/K}^{1/K}g(x)\mathrm{d}x}\leq\frac{\max_{x\in[-\varepsilon,\varepsilon]}g(x)}{\int_{\varepsilon}^{1/K}g(x)\mathrm{d}x}\leq\frac{1}{1/K-\varepsilon}.$

To summarize, we find $\Pr[X\in[-\varepsilon,\varepsilon]]\leq
e^{1+\varepsilon K}\cdot\frac{2\varepsilon}{1/K-\varepsilon}$. Since
$\varepsilon<1/(8K)$ this implies

$\Pr[X\in[-\varepsilon,\varepsilon]]\leq
2e^{8/7}\cdot\frac{7}{6}\cdot\varepsilon K\leq 8\varepsilon K.$

∎

###  5.5 Combining Together and Proof of Lemma 35

In this section, we combine the deterministic argument in Lemma 36, and the
randomized arguments in Lemma 38 and Lemma 42. We can finally show the main
technical lemma (Lemma 35).

###### Proof of Lemma 35.

Without loss of generality, let $I=[d]$ and write $E=E_{I}$. Suppose
$p^{\prime}=A_{J}=\operatorname{conv}(a_{j}:j\in J)\cap W$ is the next vertex
after the edge $F_{I}\cap W$. Here $J\in\binom{[n]}{d-1}$ and $R_{J}$ is the
$(d-2)$-dimensional ridge. With probability $1$, the polytope
$\operatorname{conv}(a_{1},\dots,a_{n})$ is non-degenerate and $W\cap
R^{\prime}$ is a single point for any ridge $R^{\prime}$ of
$\operatorname{conv}(a_{1},\dots,a_{n})$ that intersects with $W$. We will
show that conditional on $E$, each of the following conditions in the
deterministic argument (Lemma 36) is satisfied with good probability:

  1. 1.

(Bounded diameter) $\forall i,j\in[n]$, $\|a_{i}-a_{j}\|\leq 3$;

  2. 2.

(Lower bound of $\delta$) $\min_{k\in[n]\backslash
I}\operatorname{dist}(\operatorname{affhull}(F_{I}),a_{k})\geq\Omega(\frac{1}{Ld\log
n})$;

  3. 3.

(Lower bound of $r$) $\forall J\in\binom{I}{d-1}$ for which the ridge
$R_{J}=\operatorname{conv}(a_{j}:j\in J)$ has nonempty intersection with $W$,
we have $\operatorname{dist}(F_{I}\cap W,\partial
R_{J})\geq\Omega(\frac{1}{d^{4}L^{2}})$.

Note for the last point that Lemma 36 only requires this for the set $J$ which
indexes the second vertex of $F_{I}\cap W$ in clockwise direction, but we
prove it for both of the sets $J$ for which $R_{J}\cap W\neq\emptyset$.

First, we write $D$ as the event that $\forall i,j\in[n]$ for which
$\|a_{i}-a_{j}\|\leq 3$. From Lemma 16, for any
$\sigma\leq\frac{1}{8\sqrt{d\log n}}$, with probability at least
$1-\binom{n}{d}^{-1}$, we have $\max_{i\in[n]}\|\hat{a}_{i}\|\leq
1+4\sigma\sqrt{d\log n}\leq\frac{3}{2}$, i.e. $\Pr[D]\geq
1-\binom{n}{d}^{-1}$. Then we have

$\Pr[D\mid E]=\Pr[D\wedge E]/\Pr[E]\leq\frac{\Pr[D]}{\Pr[E]}\geq 0.9,$

using the assumption that $\Pr[E_{I}]\geq 10\binom{n}{d}^{-1}$.

Next, we consider
$\delta:=\operatorname{dist}(\operatorname{affhull}(a_{1},\dots,a_{d}),\\{a_{d+1},\dots,a_{n}\\})$.
Using Lemma 38, we have $\Pr[\delta\geq\frac{1}{10e^{3}Ld\log n}\mid E]\geq
0.72$.

Finally, we consider
$r:=\max_{J}\operatorname{dist}(\operatorname{affhull}(a_{1},\cdots,a_{d})\cap
W,\partial R_{J})$ subject to all $J\in\binom{I}{d-1}$ such that $A_{J}$
happens (in other words, $R_{J}=\operatorname{conv}(a_{j}:j\in J)$ is a ridge
of $F_{I}$ such that $R_{J}\cap W\neq\emptyset$). By union bound,

$\displaystyle\Pr\left[\exists\big{(}J\in\binom{I}{d-1},A_{J}\big{)},\operatorname{dist}(\operatorname{affhull}(F\cap
W),\partial R_{J}\geq\frac{1}{19200d^{4}L^{2}}\mid E\right]$
$\displaystyle\geq$ $\displaystyle
1-\sum_{J\in\binom{I}{d-1}}\Pr[A_{J}\wedge\operatorname{dist}(\operatorname{affhull}(F\cap
W),\partial R_{J}<\frac{1}{19200d^{4}L^{2}}\mid E]$ $\displaystyle=$
$\displaystyle
1-\sum_{J\in\binom{I}{d-1}}\Pr[\operatorname{dist}(\operatorname{affhull}(F\cap
W),\partial R_{J}<\frac{1}{19200d^{4}L^{2}}\mid E\wedge A_{J}]\Pr[A_{J}\mid
E].$ (19)

From Lemma 42, for each $J\in\binom{I}{d-1}$, we know that

$\Pr[\operatorname{dist}(\operatorname{affhull}(F\cap W),\partial
R_{J}<\frac{1}{19200d^{4}L^{2}}\mid E\wedge A_{J}]\leq 0.1+\Pr[\neg D\mid
E\wedge A_{J}],$

Notice that when $E$ happens, there are exactly two distinct ridges
$R_{J},R_{J^{\prime}}$ that has nonempty intersection with $W$ (or $A_{J}$
happens), thus $\sum_{J\in\binom{I}{d-1}}\Pr[A_{J}\mid E]=2$. Then (5.5)
becomes

$\displaystyle\Pr\left[\exists\big{(}J\in\binom{I}{d-1},A_{J}\big{)},\operatorname{dist}(\operatorname{affhull}(F\cap
W),\partial R_{J}\geq\frac{1}{19200d^{4}L^{2}}\mid E\right]$
$\displaystyle\geq$ $\displaystyle 1-\sum_{J\in\binom{I}{d-1}}(0.1+\Pr[\neg
D\mid E\wedge A_{J}])\Pr[A_{J}\mid E]$ $\displaystyle\geq$ $\displaystyle
1-0.1\cdot 2-2\cdot\Pr[\neg D\mid E]\geq 0.6$

Therefore by union bound, the three conditions hold with probability at least
$1-(1-0.9)-(1-0.72)-(1-0.6)\geq 0.1$, and the lemma directly follows from
Lemma 36. ∎

##  6 Smoothed Complexity Lower Bound

In this section, we present the lower bound of the smoothed complexity by
studying the intersection between the smoothed dual polytope
$Q=\operatorname{conv}(a_{1},\cdots,a_{n})\subset\mathbb{R}^{d}$ (where each
$a_{i}$ is under Gaussian perturbation), and the two-dimensional shadow plane
$W\subset\mathbb{R}^{d}$. Our main result is as follows:

######  Theorem 47.

For any $d\geq 5,n=4d-15,\sigma\leq\frac{1}{360d\sqrt{\log n}}$, there exists
a two-dimensional linear subspace $W\subset\mathbb{R}^{d}$ and vectors
$\bar{a}_{1},\cdots,\bar{a}_{n}\in\mathbb{R}^{d}$, $\max_{i\in
n}\|\bar{a}_{i}\|_{1}\leq 1$ such that the following holds. Let
$a_{1},\cdots,a_{n}$ be independent Gaussian random variables where each
$a_{i}\sim\mathcal{N}_{d}(\bar{a}_{i},\sigma^{2}I)$, then with probability at
least $1-\binom{n}{d}^{-1}$, we have

$\displaystyle\operatorname{edges}(\operatorname{conv}(a_{1},\cdots,a_{n})\cap
W)\geq\Omega\left(\min\Big{(}\frac{1}{\sqrt{d\sigma\sqrt{\log
n}}},2^{d}\Big{)}\right).$

Theorem 47 is the direct consequence of the next theorem, which is a lower
bound with the more general adversarial perturbations of bounded magnitude:

######  Theorem 48.

For any $d\geq 5,n=4d-15$, there exists a two-dimensional linear subspace
$W\subset\mathbb{R}^{d}$ and vectors
$\bar{a}_{1},\cdots,\bar{a}_{n}\in\mathbb{R}^{d}$, $\max_{i\in
n}\|\bar{a}_{i}\|_{1}\leq 1$ such that the following holds. Assume
$a_{1},\cdots,a_{n}\in\mathbb{R}^{d}$ satisfy
$\|a_{i}-\bar{a}_{i}\|_{1}\leq\varepsilon$ for all $i\in[n]$ with
$\varepsilon<\frac{1}{90}$, then

$\displaystyle\operatorname{edges}(\operatorname{conv}(a_{1},\cdots,a_{n})\cap
W)\geq\Omega\left(\min\Big{(}\frac{1}{\sqrt{\varepsilon}},2^{d}\Big{)}\right).$

The rest of this section is organized as follows: In Section 6.1, we construct
a polytope $P$ represented by a system of inequalities, and a two-dimensional
shadow plane $W$. An informal intuition behind these inequalities is described
in Section 6.2 In Section 6.3, we show that $\pi_{W}(P)$ approximates the unit
disk $\mathbb{B}_{2}^{2}$. In Section 6.4, we analyze the largest
$\ell_{\infty}$ ball contained in $P$ and the smallest $\ell_{\infty}$ ball
containing $P$. Section 6.5 investigates the polar polytope $Q=(P-x)^{\circ}$
of a shift of $P$ and derives bounds on the radius of its largest contained
$\ell_{1}$ ball and smallest containing $\ell_{1}$ ball. Finally, Section 6.6
shows that the small ratio between these radii imply that any perturbation
$\tilde{Q}$ still has $\tilde{Q}\cap W$ approximates the unit disk
$\mathbb{B}_{2}^{2}$ well and uses this fact to prove Theorem 47.

###  6.1 Construction of the Primal Polytope

In this subsection, we first construct the primal polytope and the two-
dimensional plane $W$. For $k\in\mathbb{N}$, we construct a
$(k+5)$-dimensional polytope. We will use the following vectors in the
definition:

  * •

Define $e_{1}=\begin{bmatrix}1\\\ 0\end{bmatrix}\in\mathbb{R}^{2}$ and
$e_{2}=\begin{bmatrix}0\\\ 1\end{bmatrix}$.

  * •

For every $i\in[k]$, define the pair of orthogonal unit vectors
$w_{i}=\begin{bmatrix}\cos(\pi/2^{i+2})\\\
\sin(\pi/2^{i+2})\end{bmatrix}\in\mathbb{R}^{2}$ and
$v_{i}=\begin{bmatrix}\sin(\pi/2^{i+2})\\\
-\cos(\pi/2^{i+2})\end{bmatrix}\in\mathbb{R}^{2}$.

With these definitions in mind, let $P^{\prime}\subset\mathbb{R}^{3k+5}$
denote the set of points $(x,y,p_{0},\dots,p_{k},t,s)$, where
$x,y,p_{0},p_{1},\cdots,p_{k}\in\mathbb{R}^{2},t\in\mathbb{R}^{k},s\in\mathbb{R}$,
satisfying the following system of linear inequalities:

$\displaystyle e_{1}^{\top}p_{0}$
$\displaystyle\geq|x|,e_{2}^{\top}p_{0}\geq|y|$ (20) $\displaystyle
w_{i}^{\top}p_{i}$ $\displaystyle=w_{i}^{\top}p_{i-1},~{}\forall i\in[k]$ (21)
$\displaystyle t_{i}+is=v_{i}^{\top}p_{i}$
$\displaystyle\geq|v_{i}^{\top}p_{i-1}|,~{}\forall i\in[k]$ (22)
$\displaystyle e_{1}^{\top}p_{k}$ $\displaystyle\leq 1$ (23)
$\displaystyle\mathbf{0}_{k}\preceq t$ $\displaystyle\preceq\mathbf{1}_{k}$
(24) $\displaystyle 0\leq s$ $\displaystyle\leq 1.$ (25)

We remark that $p_{0},t,s$ uniquely define the values of
$p_{1},p_{2},\cdots,p_{k}$ via (21) and (22). As such, define the polytope
$P\subset\mathbb{R}^{k+5}$ as:

$P=\\{(x,y,p_{0},t,s):\exists~{}p_{1},\cdots,p_{k}\mbox{, s.t.
}(x,y,p_{0},\cdots,p_{k},t,s)\in P^{\prime}\\}.$ (26)

The plane $W$ of interest is that spanned by the unit vectors in the $x$ and
$y$ directions.

An plot of the vertices of the projected polytope $\pi_{W}(P)$ can be found in
Figure 3 for $k=4$. Note that the figure appears to depict a regular polygon
with $2^{k+1}$ vertices.

Figure 3: Vertices of the projected primal polytope $\pi_{W}(P)$ (see (26))
without perturbation for $k=4$.

###  6.2 Intuition of the Construction

To explain the intuition behind the equations (20 \- 25), let us consider the
simpler system of inequalities in variables
$r_{0},\dots,r_{k}\in\mathbb{R}^{2}$:

$\displaystyle e_{1}^{\top}r_{0}$
$\displaystyle\geq|x|,e_{2}^{\top}r_{0}\geq|y|$ (27) $\displaystyle
w_{i}^{\top}r_{i}$ $\displaystyle\geq w_{i}^{\top}r_{i-1},~{}\forall i\in[k]$
(28) $\displaystyle v_{i}^{\top}r_{i}$
$\displaystyle\geq|v_{i}^{\top}r_{i-1}|,~{}\forall i\in[k]$ (29)
$\displaystyle e_{1}^{\top}r_{k}$ $\displaystyle\leq 1$ (30) $\displaystyle
e_{2}^{\top}r_{i}$ $\displaystyle\geq 0,~{}\forall i\in[k]$ (31)

Let $R\subset\mathbb{R}^{2k+2}$ denote the set of vectors
$(r_{0},\dots,r_{k})$ satisfying the above inequalities. For each
$i=0,\dots,k$, write $R_{i}=\\{r_{i}:\exists
r_{0},\dots,r_{i-1},r_{i+1},\dots,r_{k}\text{ s.t. }(r_{0},\dots,r_{k})\in
R\\}\subset\mathbb{R}^{2}$ for the projections of $R$ onto the two-dimensional
coordinate subspace of $r_{i}$. Also, let $W$ be the two-dimensional plane
spanned by the $x$ and $y$ directions, so that $\pi_{W}(R)=\\{(x,y):\exists
r_{0}\in R_{0},r_{0}\geq(|x|,|y|)^{\top}\\}$. The vertices of these sets are
depicted in Figure 4.

For these sets, we have the following observations. We will skip the proof
since they only give illustrations of our analysis and will not be functional
to the proof of Theorem 47.

  1. 1.

The set $R_{k}$ can be described by the inequalities $e_{2}^{\top}r_{k}\geq
0,e_{1}^{\top}r_{k}\leq 1,v_{i}^{\top}r_{i}\geq 0$. These inequalities
describe a small slice of the regular $2^{k+1}$-gon.

  2. 2.

For each $i=0,\dots,k-1$, the set $R_{i}$ is obtained by taking the union of
$R_{i+1}$ and its mirror image in the line spanned by $w_{i}$.

  3. 3.

For each $i=1,\dots,k$, the set $R_{i}$ can be described as the restriction of
a regular $2^{k+1}$-gon intersected with the set
$\\{r_{i}:e_{2}^{\top}r_{i}\geq 0,v_{i}^{\top}r_{i}\geq 0\\}$.

  4. 4.

The set $R_{0}$ can be described as the restriction of a regular $2^{k+1}$-gon
intersected with the non-negative orthant.

  5. 5.

The set $R=\\{(x,y):\exists r_{0}\in R_{0},r_{0}\geq(|x|,|y|)^{\top}\\}$ is a
regular $2^{k+1}$-gon.

More careful inspection allows for the following additional observations,
which we also state without proof:

  1. 1.

Turning (28) from an inequality to an equality constraint does not change any
of the sets $R_{0},\dots,R_{k}$.

  2. 2.

Removing the constraint (31) does not change $R_{0}$.

  3. 3.

Adding upper bounds $v_{i}^{\top}r_{i}\leq 2$ does not change $R_{0}$.

Each of the above-mentioned changes either serves to increase the size of the
largest ball (in the affine hull of $R$) contained in the relative interior of
$R$ or to decrease the size of the smallest ball containing $R$. The addition
of the variable $s$ in the construction of $P$ serves to further increase the
size of the largest ball contained in $P$ without increasing the size of the
smallest ball containing $P$.

|
---|---
|
Figure 4: Vertices of $\pi_{H}(R),R_{0},R_{1},R_{2}$ for $k=2$.

###  6.3 Projected Primal Polytope Approximates Two-Dimensional Unit Disk

In this subsection, we will show that the polytope $P$ we constructed in (26)
has a projection $\pi_{W}(P)$ which approximates the two-dimensional unit disk
$\mathbb{B}_{2}^{2}=\\{x,y\in\mathbb{R}:x^{2}+y^{2}\leq 1\\}$ within
exponentially small error:

######  Lemma 49 (Projected primal polytope approximates the two-dimensional
disk).

For any $k\in\mathbb{N}$, let $P\subset\mathbb{R}^{k+5}$ be the polytope
defined by the linear system (26) with variables
$x,y,s\in\mathbb{R},p_{0}\in\mathbb{R}^{2},t\in\mathbb{R}^{k}$. Let $W$ be the
two-dimensional subspace spanned by the directions of $x$ and $y$. Then we
have

$\mathbb{B}_{2}^{2}\subset\pi_{W}(P)\subset(1+4^{-k-2})\mathbb{B}_{2}^{2}.$

Lemma 49 directly follows from the next two lemmas. First, we show that the
two-dimensional unit disk is contained in $\pi_{W}(P)$:

######  Lemma 50 (Inner radius of the projected primal polytope).

For every $x,y\in\mathbb{R}$ with $x^{2}+y^{2}\leq 1$ there exist
$p_{0}\in\mathbb{R}^{2}$, $t\in\mathbb{R}^{k}$ and $s\in\mathbb{R}$ such that
$(x,y,p_{0},t,s)\in P$.

###### Proof.

Given such $x,y$, set $s=0$ and set $p_{0},t$ such that (20) and (22) are
satisfied with equality. This will result in
$\sqrt{x^{2}+y^{2}}=\|p_{0}\|=\|p_{i}\|$ for every $i\in[k]$. Since
$t=|v_{i}^{\top}p_{i-1}|\leq\|v_{i}\|\cdot\|p_{i-1}\|\leq 1$, we know that
(24) is satisfied. Furthermore, we have
$e_{1}^{\top}p_{k}\leq\|e_{1}\|\cdot\|p_{k}\|=\|e_{1}\|\cdot\sqrt{x^{2}+y^{2}}\leq
1$ which ensures that (23) is satisfied. ∎

In the next lemma, we will show that $\pi_{W}(P)$ is contained in scaled the
two-dimensional disk $(1+4^{-k-2})\mathbb{B}_{2}^{2}$:

######  Lemma 51 (Outer radius of the projected primal polytope).

For every $x,y\in\mathbb{R}$ with $\sqrt{x^{2}+y^{2}}\geq 1+4^{-k-2}$ there
exist no $p_{0}\in\mathbb{R}^{2},t\in\mathbb{R}^{k}$ and $s\in\mathbb{R}$ such
that $(x,y,p_{0},t,s)\in P$.

###### Proof.

Fix any $(x,y)\in\mathbb{R}^{2}$ and $p_{0}\in\mathbb{R}^{2}$, such that
$x^{2}+y^{2}>1+4^{-k-2}$ and
$p_{0}\succeq\begin{bmatrix}|x|,|y|\end{bmatrix}^{\top}$. Also fix any
$p_{1},\cdots,p_{k}\in\mathbb{R}^{2}$ satisfying (21) and (22). We will show
that such $p_{1},\cdots,p_{k}$ would violate (23), i.e. $e_{1}^{\top}p_{k}>1$.
To simplify our notation, for all $i\in\\{0,1,\cdots,k\\}$, let
$(p_{i})_{v}=v_{i}^{\top}p_{i}\in\mathbb{R}$ and
$(p_{i})_{w}=w_{i}^{\top}p_{i}\in\mathbb{R}$. Then
$p_{i}=(p_{i})_{v}v_{i}+(p_{i})_{w}w_{i}$.

Notice that for all $i\in[k]$, the increment of the first coordinate from
$p_{i-1}$ to $p_{i}$ is

$\displaystyle e_{1}^{\top}p_{i}-e_{1}^{\top}p_{i-1}$
$\displaystyle=e_{1}^{\top}\left((p_{i})_{w}w_{i}+(p_{i})_{v}v_{i}-(w_{i}^{\top}p_{i-1})w_{i}-(v_{i}^{\top}p_{i-1})v_{i}\right)$
$\displaystyle=e_{1}^{\top}\left((p_{i})_{v}v_{i}-(v_{i}^{\top}p_{i-1})v_{i}\right)$
$\displaystyle(\text{By \eqref{cons:w}})$ $\displaystyle\geq
e_{1}^{\top}v_{i}\left(|v_{i}^{\top}p_{i-1}|-v_{i}^{\top}p_{i-1}\right)$
$\displaystyle(\text{By $e_{1}^{\top}v_{i}>0$ and \eqref{cons:v}})$ (32)
$\displaystyle\geq 0$

where the inequality in (6.3) is tight when
$v_{i}^{\top}p_{i}=|v_{i}^{\top}p_{i-1}|$. Let
$p_{0}^{*},p_{1}^{*},\cdots,p_{k}^{*}\in\mathbb{R}^{2}$ be the (unique)
sequence defined by

$\displaystyle p_{0}^{*}$ $\displaystyle=p_{0}$ $\displaystyle
w_{i}^{\top}p_{i}^{*}$ $\displaystyle=w_{i}^{\top}p_{i-1}^{*},$
$\displaystyle\forall i\in[k]$ (Tight for (21)) $\displaystyle
v_{i}^{\top}p_{i}^{*}$ $\displaystyle=|v_{i}^{\top}p_{i-1}^{*}|,$
$\displaystyle\forall i\in[k]$ (Tight for (22))

Then $e_{1}^{\top}p_{i}-e_{1}^{\top}p_{i-1}\geq
e_{1}^{\top}p_{i}^{*}-e_{1}^{\top}p_{i-1}^{*}$ for each $i\in[k]$. Also,
notice that $e_{1}^{\top}p_{0}=e_{1}^{\top}p_{0}^{*}$, therefore for each
$i\in[k]$, $e_{1}^{\top}p_{i}\geq e_{1}^{\top}p_{i}^{*}$.

It remains to show that $e_{1}^{\top}p_{k}^{*}\geq 1$. For all
$i\in\\{0,1,\cdots,k\\}$, let $\theta_{i}\in[-\pi,\pi]$ denote the angle
between $p_{i}^{*}\in\mathbb{R}^{2}$ and $e_{1}$. Then since
$e_{1}^{\top}p_{0}\geq 0$ and $e_{2}^{\top}p_{0}\geq 0$, we have
$0\leq\theta_{0}\leq\frac{\pi}{2}$. For any $i\in[k]$, notice that $p_{i}^{*}$
equals to $p_{i-1}^{*}$ (if $\theta_{i-1}\leq\frac{\pi}{2^{i+2}}$), or equals
to the mirror of $p_{i-1}^{*}$ with respect to the line spanned by $w_{i}$ (if
$\theta_{i-1}\geq\frac{\pi}{2^{i+2}}$). By induction, this gives

$\displaystyle\|p_{i}^{*}\|_{2}=\|p_{i-1}^{*}\|_{2}=\cdots=\|p_{0}^{*}\|_{2}=\|p_{0}\|_{2},$

and

$\displaystyle\theta_{i}=\frac{\pi}{2^{i+2}}-|\theta_{i-1}-\frac{\pi}{2^{i+2}}|\leq\frac{\pi}{2^{i+2}}.$

Therefore, we get

$\displaystyle
e_{1}^{\top}p_{k}^{*}=\|p_{k}^{*}\|\cdot\cos(\theta_{k})\geq\|p_{0}\|\cdot\cos\left(\frac{\pi}{2^{k+2}}\right)\geq(1+4^{-k-2})\cdot(1-\frac{1}{2\cdot
4^{k+2}})>1.$

Thus we have shown $x^{2}+y^{2}>1+4^{-k-2}$ implies that
$e_{1}^{\top}p_{k}\geq e_{1}^{\top}p_{k}^{*}>1$ as desired. ∎

###  6.4 Inner and Outer Radius of the Primal Polytope

In this subsection, we will show that the primal polytope $P$ has large inner
radius and small outer radius.

######  Lemma 52 (Inner radius of the primal polytope).

For $k\in\mathbb{N}$, let $P\subset\mathbb{R}^{k+5}$ be the polytope defined
by the linear system (26). Then there exists a point
$(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})$ such that

$\frac{1}{30}\cdot\mathbb{B}_{\infty}^{k+5}\subset
P-(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})\subset\frac{3}{2}\mathbb{B}_{\infty}^{k+5}.$

###### Proof.

In Lemma 53 we find a point $(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})$
such that$\frac{1}{30}\mathbb{B}_{\infty}^{k+5}\subset
P-(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})$.

On the other hand, we claim that $P\subset 2\cdot\mathbb{B}_{\infty}^{k+5}$.
Suppose $(x,y,p_{0},t,s)\in P$. From Lemma 51 we know that
$\|(x,y)\|_{\infty}\leq\sqrt{x^{2}+y^{2}}\leq\|p_{0}\|_{2}\leq 1+4^{-k-2}$.
Since $\mathbf{0}_{k}\leq t\leq\mathbf{1}_{k}$ we get $\|t\|_{\infty}\leq 1$,
and lastly we have $0\leq s\leq 1$. Put together, we find that
$\|(x,y,p_{0},t,s)\|_{\infty}\leq 1+4^{-k-2}$. By the triangle inequality we
find that
$P-(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})\subset(1+4^{-k-2}+\|(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})\|_{\infty})\cdot\mathbb{B}_{\infty}^{k+5}$
and we know $\|(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})\|_{\infty}=1/3$.
∎

######  Lemma 53 (Inner Radius of the Polytope).

For
$\bar{x}=\bar{y}=0,\bar{p}_{0}=(1/6,1/6)^{\top},\bar{t}=\mathbf{1}_{k}/30,\bar{s}=\frac{1}{3}$,
we have
$(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})+r\cdot\mathbb{B}_{\infty}^{k+5}\subseteq
P$ for $r=\frac{1}{30}$.

###### Proof.

Fix any $(x,y,p_{0},t,s)\in\mathbb{R}^{k+5}$ such that
$\|(x-\bar{x},y-\bar{y},p_{0}-\bar{p}_{0},t-\bar{t},s-\bar{s})\|_{\infty}\leq
r$. Let $p_{1},\cdots,p_{k}\in\mathbb{R}^{2}$ be uniquely defined by
$w_{i}^{\top}p_{i}=w_{i}^{\top}p_{i-1}$ and $t_{i}+is=v_{i}^{\top}p_{i}$ with
our fixed $p_{0},s$ and $t$. We will show that $(x,y,p_{0},t)\in P$ by
verifying (20 \- 25). To simplify our notation, we let
$(p_{i})_{v}=v_{i}^{\top}p_{i}\in\mathbb{R}$ and
$(p_{i})_{w}=w_{i}^{\top}p_{i}\in\mathbb{R}$ for all $i\in\\{0,1,\cdots,k\\}$.
Then $p_{i}=(p_{i})_{v}v_{i}+(p_{i})_{w}w_{i}$.

First, observe that $e_{1}^{\top}p_{0}\geq\frac{1}{6}-r\geq r\geq|x|$ and
$e_{2}^{\top}p_{0}\geq\frac{1}{6}-r\geq r\geq|y|$, confirming that (20) holds.
Also, notice that $t_{i}\in[\bar{t}_{i}-r,\bar{t_{i}}+r]\subset[0,1]$ , and
$s\in[\bar{s}-r,\bar{s}+r]\subset[0,1]$. thus (24) and (25) hold. The equality
constraint (21) holds by definition of $p_{1},\cdots,p_{k}$.

To aid in the remaining steps of the proof, we show $w_{i}^{\top}p_{i}\geq 0$
for all $i\in\\{0,1,\cdots,k\\}$. Notice that $w_{0}^{\top}p_{0}\geq
w_{0}^{\top}\bar{p}_{0}-\|w_{0}\|\cdot\|p_{0}-\bar{p}_{0}\|\geq\frac{\sqrt{2}}{6}-\sqrt{2}r\geq
0$. Also, for all $i\in[k]$,

$\displaystyle w_{i}^{\top}p_{i}$ $\displaystyle=w_{i}^{\top}p_{i-1}$
$\displaystyle=w_{i}^{\top}\left((p_{i-1})_{w}w_{i-1}+(p_{i-1})_{v}v_{i-1}\right)$
$\displaystyle=(p_{i-1})_{w}\cdot\cos(\frac{\pi}{2^{i+2}})+(p_{i-1})_{v}\cdot\sin(\frac{\pi}{2^{i+2}})$
(33) $\displaystyle\geq(p_{i-1})_{w}\cdot\cos(\frac{\pi}{2^{i+2}}).$

It then follows by induction that $(p_{i})_{w}\geq 0$ for all
$i\in\\{0,1,\cdots,k\\}$.

Next, we verify the inequality listed in (22) i.e.
$v_{i}^{\top}p_{i}\geq|v_{i}^{\top}p_{i-1}|$ for all $i\in[k]$. Notice that
for all $i\in[k]$,

$\displaystyle|v_{i}^{\top}p_{i-1}|$
$\displaystyle=\left|v_{i}^{\top}((p_{i-1})_{v}v_{i-1}+(p_{i-1})_{w}w_{i-1})\right|$
$\displaystyle\leq|(p_{i-1})_{v}|v_{i}^{\top}v_{i-1}+|(p_{i-1})_{w}|\cdot|v_{i}^{\top}w_{i-1}|$
(Triangle inequality)
$\displaystyle=(t_{i-1}+(i-1)s)\cdot\cos(\frac{\pi}{2^{i+2}})+(p_{i-1})_{w}\cdot\sin(\frac{\pi}{2^{i+2}})$
(By (22) and $(p_{i-1})_{w}\geq 0$) (34)

We require an upper bound on $(p_{i-1})_{w}$. For all $i\in[k]$, from (33)

$\displaystyle(p_{i})_{w}$
$\displaystyle=(p_{i-1})_{w}\cdot\cos(\frac{\pi}{2^{i+2}})+(p_{i-1})_{v}\cdot\sin(\frac{\pi}{2^{i+2}})$
$\displaystyle\leq(p_{i-1})_{w}+(t_{i-1}+(i-1)s)\cdot\sin(\frac{\pi}{2^{i+2}})$
(By $(p_{i-1})_{w}\geq 0$ and (22))

Let $t_{0}=v_{0}^{\top}p_{0}$ and $\bar{t}_{0}=v_{0}^{\top}\bar{p}_{0}=0$. We
have that for all $i\in[k]$,

$\displaystyle(p_{i})_{w}$ $\displaystyle\leq
w_{0}^{\top}p_{0}+\sum_{j=0}^{i-1}(t_{j}+js)\cdot\sin(\frac{\pi}{2^{j+3}})$
$\displaystyle\leq
w_{0}^{\top}p_{0}+\sum_{j=0}^{i-1}(t_{j}+js)\cdot\sin(\frac{\pi}{8})\cdot
1.9^{-j}$ $\displaystyle\leq
w_{0}^{\top}p_{0}+\sum_{j=0}^{i-1}(\bar{t}_{j}+r+js)\cdot\sin(\frac{\pi}{8})\cdot
1.9^{-j}$
$\displaystyle\leq(\frac{\sqrt{2}}{6}+\sqrt{2}r)+\sin(\frac{\pi}{8})\sum_{j=0}^{i-1}(\frac{1}{30}+r+js)\cdot
1.9^{-j}$ $\displaystyle\leq 0.263+2.226r+0.898s.$ (35)

Plugging (35) back into (6.4), we have for all $i\in[k]$,

$\displaystyle|v_{i}^{\top}p_{i-1}|$
$\displaystyle\leq(t_{i-1}+(i-1)s)\cdot\cos(\frac{\pi}{2^{i+2}})+(0.263+2.226r+0.898s)\cdot\sin(\frac{\pi}{2^{i+2}})$
$\displaystyle\leq(\frac{1}{30}+r+(i-1)s)+(0.263+2.226r+0.898s)\cdot\sin(\frac{\pi}{8})$
(By $\bar{t}_{i-1}=\frac{1}{30}$ and $i\geq 1$) $\displaystyle\leq
0.134+1.852r+(i-0.656)s$ $\displaystyle\leq 0.134+1.852r+is-0.656(\bar{s}-r)$
$\displaystyle\leq is$ (By $\bar{s}=\frac{1}{3},r\leq\frac{1}{30}$)
$\displaystyle\leq(p_{i})_{v}.$

Therefore, $v_{i}^{\top}p_{i}\geq|v_{i}^{\top}p_{i-1}|$ for all $i\in[k]$ and
(22) holds.

Finally, we verify (23). The increment of the first coordinate from $p_{i-1}$
to $p_{i}$ is

$\displaystyle e_{1}^{\top}p_{i}-e_{1}^{\top}p_{i-1}$
$\displaystyle=e_{1}^{\top}\left((p_{i})_{v}v_{i}-(v_{i}^{\top}p_{i-1})v_{i}\right)$
$\displaystyle=\sin(\frac{\pi}{2^{i+2}})\cdot(t_{i}+is-v_{i}^{\top}p_{i-1})$
$\displaystyle=\sin(\frac{\pi}{2^{i+2}})\cdot\left(t_{i}+is-
v_{i}^{\top}((p_{i-1})_{w}w_{i-1}+(p_{i-1})_{v}v_{i-1})\right)$
$\displaystyle=\sin(\frac{\pi}{2^{i+2}})\cdot\left(t_{i}+is+(p_{i-1})_{w}\cdot\sin(\frac{\pi}{2^{i+2}})-(t_{i-1}+(i-1)s)\cdot\cos(\frac{\pi}{2^{i+2}})\right)$
(36)

where the last step comes from $v_{i}^{\top}v_{i-1}=\cos(\frac{\pi}{2^{i+2}})$
and $v_{i}^{\top}w_{i-1}=-\sin(\frac{\pi}{2^{i+2}})$. For all $i\geq 2$, we
can show that in (36), the third term in the brackets is at most the fourth
term:

$\displaystyle(p_{i-1})_{w}\cdot\sin(\frac{\pi}{2^{i+2}})$
$\displaystyle\leq(0.263+2.226r+0.898s)\cdot\sin(\frac{\pi}{2^{i+2}})$ (By
(35))
$\displaystyle\leq(0.263+2.226r+0.898s)\cdot\tan(\frac{\pi}{8})\cdot\cos(\frac{\pi}{2^{i+2}})$
(By $\frac{\pi}{2^{i+2}}\leq\frac{\pi}{8}$)
$\displaystyle\leq(0.338+0.898\cdot\frac{11}{30})\cdot\tan(\frac{\pi}{8})\cdot\cos(\frac{\pi}{2^{i+2}})$
(By $r\leq\frac{1}{30}$ and $s\leq\bar{s}+r=\frac{11}{30}$) $\displaystyle\leq
0.277\cdot\cos(\frac{\pi}{2^{i+2}})$
$\displaystyle\leq(\bar{t}_{i-1}-r+(i-1)s)\cdot\cos(\frac{\pi}{2^{i+2}})$ (By
$\bar{t}_{i-1}-r=0$ and $s\geq\bar{s}-r=0.3$)
$\displaystyle\leq(t_{i-1}+(i-1)s)\cdot\cos(\frac{\pi}{2^{i+2}}).$

Plugging back into (36), we have

$\displaystyle e_{1}^{\top}p_{i}-e_{1}^{\top}p_{i-1}$
$\displaystyle\leq\sin(\frac{\pi}{2^{i+2}})\cdot(t_{i}+is)$
$\displaystyle\leq\sin(\frac{\pi}{2^{i+2}})\cdot(\bar{t}_{i}+i\bar{s}+(i+1)r)$
$\displaystyle\leq\sin(\frac{\pi}{8})\cdot
1.9^{-(i-1)}\cdot(\frac{1}{30}+\frac{i}{3}+(i+1)r)$ (By
$\sin(\frac{\pi}{2^{i+2}})\leq\sin(\frac{\pi}{8})\cdot 1.9^{-(i-1)}$)

Therefore,

$\displaystyle e_{1}^{\top}p_{k}$ $\displaystyle\leq
e_{1}^{\top}p_{0}+\sum_{i=1}^{k}(e_{1}^{\top}p_{i}-e_{1}^{\top}p_{i-1})$
$\displaystyle\leq(\frac{1}{6}+r)+\sin(\frac{\pi}{8})\cdot\sum_{i=1}^{k}1.9^{-(i-1)}\cdot(\frac{1}{30}+\frac{i}{3}+(i+1)r)$
$\displaystyle\leq 0.562+3.514r\leq 1.$

where the last inequality holds for any $r\leq\frac{1}{30}$. Therefore (23)
holds, and $(x,y,p_{0},t)\in P$. ∎

###  6.5 Properties of the Dual Polytope

In this section, we will analyze the scaled polar dual polytope
$Q=\frac{1}{30}(P-(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s}))^{\circ}$.
From well-known duality properties, we will find that $Q$ satisfies the
following desirable properties:

  1. 1.

$Q\cap W$ approximates a two-dimensional disk;

  2. 2.

The inner radius of $Q$ is at least $\frac{1}{45}$ when centered at
$\mathbf{0}$;

  3. 3.

The outer radius of $Q$ is at most $1$ when centered at $\mathbf{0}$.

######  Lemma 54.

For any $k\in\mathbb{N}$, there exists a two-dimensional linear subspace
$W\subset\mathbb{R}^{k+5}$ and $n=4k+5$ points
$a_{1},\cdots,a_{n}\in\mathbb{B}_{1}^{k+5}$ such that
$Q:=\operatorname{conv}(a_{1},\cdots,a_{n})$ satisfies

$\frac{1}{30(1+4^{-k})}\cdot\mathbb{B}_{2}^{k+5}\cap W\subset Q\cap
W\subset\frac{1}{30}\cdot\mathbb{B}_{2}^{k+5}\cap W$

and

$\frac{1}{45}\cdot\mathbb{B}_{1}^{k+5}\subset Q\subset\mathbb{B}_{1}^{k+5}$

###### Proof.

Let $P\subset\mathbb{R}^{k+5}$ be the polytope defined by the linear system
in(26), and let

$\displaystyle\tilde{P}=P-(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})$

denote the polytope obtained from shifting its center
$(\bar{x},\bar{y},\bar{p}_{0},\bar{t},\bar{s})$ to $\mathbf{0}_{d}$. Here

$\displaystyle\bar{x}=\bar{y}=0,\bar{p}_{0}=(1/6,1/6)^{\top},\bar{t}=\mathbf{1}_{k}/30,\bar{s}=\frac{1}{3}.$

Applying basic operations from linear algebra, we transform the constraints
(20 \- 25) into a matrix $A\in\mathbb{R}^{(4k+5)\times(k+5)}$ such that

$\tilde{P}=\\{z\in\mathbb{R}^{k+5}:Az\leq 1\\}.$

Let $\tilde{Q}=(\tilde{P})^{\circ}\subset\mathbb{R}^{d}$ denote the polar body
of $\tilde{P}$. Since $\tilde{P}$ is bounded, $\tilde{Q}$ is the convex hull
of the rows of the matrix $A$, i.e.

$\tilde{Q}=\\{A^{\top}\lambda:\lambda\in[0,1]^{4k+5}\;\mbox{s.t.}\sum_{i=1}^{4k+5}\lambda_{i}=1\\}.$

Then by Lemma 52 and 9, the inner and outer ball of $\tilde{Q}$ satisfy

$\frac{2}{3}\cdot\mathbb{B}_{1}^{k+5}\subset\tilde{Q}\subset
30\cdot\mathbb{B}_{1}^{k+5}.$

Also, by Lemma 49, 10 and 9, the inner and outer ball of $\tilde{Q}\cap W$
satisfy

$\frac{1}{1+4^{-k-2}}\cdot\mathbb{B}_{2}^{k+5}\cap W\subset\tilde{Q}\cap