text:
# Smoothed Analysis of Renegar’s Condition Number for Linear Programming

## 1 Introduction

In \[ST03b\], Spielman and Teng introduced the smoothed analysis of algorithms as an alternative to worst-case and average-case analyses in the hope that it could provide a measure of the complexity of algorithms that better agrees with practical experience. The smoothed complexity of an algorithm is the maximum over its inputs of the expected running time of the algorithm under slight perturbations of that input. In this paper, we perform a smoothed analysis of Renegar’s condition number for linear programs, and thereby obtain a smoothed analysis of his interior-point algorithm. Interior point algorithms for linear programming are exciting both because they are known to run in polynomial time \[Kar84\] in the worst case and because they have been used to efficiently solve linear programs in practice. In fact, the speed of interior point methods in practice is much better than that proved in their worst-case analyses \[IL94, LMS90, EA96\]. This discrepancy between worst-case analysis and practical experience is our main motivation for studying the smoothed complexity of interior point methods.

Our main result is that the smoothed value of Renegar’s condition number, to be defined in Section 1.2, is $`O(\mathrm{log}(nd/\sigma ))`$. That is, for each $`(\overline{A},\overline{𝒃},\overline{𝒄})`$ and $`\sigma 1/\sqrt{dn}`$,

$$\text{E}_{(A,𝒃,𝒄)𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )}\left[C(A,𝒃,𝒄)\right]=O(\mathrm{log}(nd/\sigma )),$$

where $`𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )`$ is the distribution of Gaussian perturbations of $`(\overline{A},\overline{𝒃},\overline{𝒄})`$ of variance $`\sigma ^2`$, and $`(A,𝒃,𝒄)𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )`$ indicates that $`(A,𝒃,𝒄)`$ is chosen according to this distribution. As Renegar’s algorithm \[Ren95b\] takes $`O\left(\sqrt{n}\mathrm{ln}\left(C(A,𝒃,𝒄)/ϵ\right)\right)`$ iterations to find a solution of relative accuracy $`ϵ`$, we find that the smoothed complexity of Renegar’s algorithm when it is asked for a solution of relative accuracy $`ϵ`$ is $`O(n^3\mathrm{log}(nd/\sigma ϵ))`$.

As explained in \[ST03c\], when one combines this analysis with the smoothed analysis of the finite termination procedure in that paper, one obtains an interior point algorithm that returns the exact answer to the linear program and has smoothed complexity $`O(n^3\mathrm{log}(nd/\sigma ))`$. In comparison, the best-known bound on the worst-case complexity of any linear programming algorithm is Vaidya’s \[Vai90\] bound of $`O((n+d)d^2+(n+d)^{1.5}d)L)`$, and the best known bound for an interior point method is $`O(n^3L)`$, first due to Gonzaga \[Gon88\].

### 1.1 The Complexity of Linear Programming Algorithms

A linear program is typically specified by a matrix $`A`$ together with two vectors $`𝒃`$ and $`𝒄`$. If $`A`$ is an $`n`$ by $`d`$ matrix, then $`𝒃`$ is an $`n`$-vector and $`𝒄`$ is a $`d`$-vector. There are several canonical forms of linear programs specified by $`(A,𝒃,𝒄)`$. The following are four commonly used canonical forms:

$`\mathrm{max}𝒄^T𝒙\text{ s.t. }A𝒙𝒃`$ and its dual $`\mathrm{min}𝒃^T𝒚\text{ s.t }A^T𝒚=𝒄,𝒚\mathrm{𝟎}`$ (1)
$`\mathrm{max}𝒄^T𝒙\text{ s.t. }A𝒙𝒃,𝒙\mathrm{𝟎}`$ and its dual $`\mathrm{min}𝒃^T𝒚\text{ s.t. }A^T𝒚𝒄,𝒚\mathrm{𝟎}`$ (2)
$`\mathrm{max}𝒄^T𝒙\text{ s.t. }A𝒙=𝒃,𝒙\mathrm{𝟎}`$ and its dual $`\mathrm{min}𝒃^T𝒚\text{ s.t. }A^T𝒚𝒄`$ (3)
$`\text{find }𝒙\mathrm{𝟎}\text{ s.t. }A𝒙\mathrm{𝟎}`$ and its dual $`\text{find }𝒚\mathrm{𝟎}\text{ s.t. }A^T𝒚=\mathrm{𝟎},𝒚\mathrm{𝟎}`$ (4)
Without loss of generality, we assume that $`nd`$ for the remainder of the paper. The worst-case complexity of solving linear programs has traditionally been stated in terms of $`n`$, $`d`$, and $`L`$, where $`L`$ is commonly called the “bit-length” of the input linear program, but is rarely defined to actually be the number of bits necessary to specify the linear program. For integer $`A,𝒃,𝒄`$, Khachiyan \[Kha79\] and Karmarkar \[Kar84\] defined $`L`$ to be some constant times

$$\begin{array}{c}\mathrm{log}(\text{largest absolute value of the determinant of any square sub-matrix of }A)\hfill \\ \hfill +\mathrm{log}(𝒄_{\mathrm{}})+\mathrm{log}(𝒃_{\mathrm{}})+\mathrm{log}(n+d).\end{array}$$

In the smoothed model, complexity estimates in terms of $`L`$ are quite pessimistic: even if one perturbs just the least significant digit of each entry of $`A`$, the resulting $`L`$ value is at least some constant times $`d`$ with high probability. Thus, in the smoothed model, our analysis of the complexity of interior point methods the replaces $`L`$, which is typically $`\mathrm{\Omega }(d)`$, with $`\mathrm{log}(nd/\sigma )`$.

### 1.2 Renegar’s Condition Number

In \[Ren95b, Ren95a, Ren94\], Renegar defined the condition number $`C(A,𝒃,𝒄)`$ of a linear program and proved that an interior point algorithm whose complexity was $`O(n^3\mathrm{log}(C(A,𝒃,𝒄)/ϵ))`$ could solve a linear program to relative accuracy $`ϵ`$, or determine that the program was infeasible or unbounded.

For a linear program in the canonical form (1), we follow Renegar \[Ren94, Ren95a, Ren95b\] in defining the primal condition number, $`C_P^{(1)}(A,𝒃)`$, of the program to be the normalized reciprocal of the distance to ill-posedness. A program is ill-posed if the program can be made both feasible and infeasible by arbitrarily small changes to the pair $`(A,𝒃)`$. The distance to ill-posedness of the pair $`(A,𝒃)`$ is the distance to the set of ill-posed programs under the Frobenius norm. We similarly define the dual condition number, $`C_D^{(1)}(A,𝒄)`$, to be the normalized reciprocal of the distance to ill-posedness of the dual program. The condition number, $`C^{(1)}(A,𝒃,𝒄)`$, is the maximum of $`C_P^{(1)}(A,𝒃)`$ and $`C_D^{(1)}(A,𝒄)`$.

We can equivalently define the condition number without introducing the concept of ill-posedness. For programs of form (1), we define $`C_P^{(1)}(A,𝒃)`$ by

###### Definition 1.2.1 (Primal Condition Number).

* if $`A𝒙𝒃`$ is feasible, then

$`C_P^{(1)}(A,𝒃)={\displaystyle \frac{A,𝒃_F}{sup\{\delta :\mathrm{\Delta }A,\mathrm{\Delta }𝒃_F\delta \text{ implies }(A+\mathrm{\Delta }A)𝒙(𝒃+\mathrm{\Delta }𝒃)\text{ is feasible}\}}},`$
* if $`A𝒙𝒃`$ is infeasible, then

$`C_P^{(1)}(A,𝒃)={\displaystyle \frac{A,𝒃_F}{sup\{\delta :\mathrm{\Delta }A,\mathrm{\Delta }𝒃_F\delta \text{ implies }(A+\mathrm{\Delta }A)𝒙(𝒃+\mathrm{\Delta }𝒃)\text{ is infeasible}\}}}.`$

It follows from the definition above that $`C_P^{(1)}(A,𝒃)1`$. We define the dual condition number, $`C_D^{(1)}(A,𝒄)`$, analogously.

To reader familiar with condition numbers in contexts outside of linear programming, the above definition may be surprising: the condition numbers for numerous other problems are defined as the sensitivity of the output to perturbations in the input, and are then often related to the distance to ill-posedness. Renegar inverts this scheme by defining the condition number for linear programming to be the distance to ill-posedness, and then proving that the condition number does bound the sensitivity of the output to perturbations in the input \[Ren94, Ren95a\].

Any linear program may be expressed in form (1); however, transformations among linear programming formulations do not in general (and commonly do not) preserve condition number \[Ren95a\]. We will therefore have to define different condition numbers for each normal form we consider. For linear programs with canonical forms (2), (3), and (4) we define their condition numbers, $`C^{(2)}(A,𝒃,𝒄)`$, $`C^{(3)}(A,𝒃,𝒄)`$ and $`C^{(4)}(A)`$, analogously. We follow the convention that $`\mathrm{𝟎}`$ is not considered a feasible solution to $`(4)`$. Just as for $`C_P^{(1)}(A,𝒃)`$, $`C^{(i)}1`$ for all $`i`$.

For linear programs given in form (2), Renegar \[Ren95b, Ren95a, Ren94\] developed an initialization phase that returns a feasible point with initial optimality gap $`RO(nC(A,𝒃,𝒄))`$ for a linear program $`(A,𝒃,𝒄)`$ or determines that the program is infeasible or unbounded, in $`O(n^3\mathrm{log}(C(A,𝒃,𝒄)))`$ operations. By applying $`O(\sqrt{n}\mathrm{log}(nC(A,𝒃,𝒄))/ϵ)`$ iterations of a primal interior point method, for a total of $`O(n^3\mathrm{log}(nC(A,𝒃,𝒄))/ϵ)`$ arithmetic operations, Renegar proved:

###### Theorem 1.2.2 (Renegar).

For any linear program of form (2) specified by $`(A,𝐛,𝐜)`$ and parameter $`ϵ`$, Renegar’s interior-point algorithm, in $`O(n^3\mathrm{log}(nC(A,𝐛,𝐜)/ϵ))`$ operations, finds a feasible solution $`𝐱`$ with optimality gap $`ϵA,𝐛,𝐜_F`$, or determines that the program is infeasible or unbounded.

Subsequently, algorithms with complexity logarithmic in the condition number were developed by Vera \[Ver96\] for forms (1) and (3) and by Cucker and Peña \[CP01\] for form (4). The complexities of their algorithms are similar to that of Renegar’s. In \[FV00\], Freund and Vera give a unified approach which both efficiently estimates the condition number and solves the linear programs in any of these forms.

### 1.3 Smoothed Analysis of Condition Number: Our Results

In this paper, we consider linear programming problems in which the data is subject to slight Gaussian perturbations. Recall that the probability density function of a Gaussian random variable with mean $`\overline{x}`$ and variance $`\sigma ^2`$ is given by

$$\mu (x)=\frac{1}{\sigma \sqrt{2\pi }}e^{(x\overline{x})^2/(2\sigma ^2)}.$$

A Gaussian perturbation of a vector $`\overline{𝒙}`$ of variance $`\sigma ^2`$ is a vector whose $`i`$th element is a Gaussian random variable of variance $`\sigma ^2`$ and mean $`\overline{x}_i`$, and in which each element is independently chosen. Thus, the probability density function of a $`d`$-dimensional Gaussian perturbation of $`\overline{𝒙}`$ of variance $`\sigma ^2`$ is given by

$$\mu (𝒙)=\frac{1}{(\sigma \sqrt{2\pi })^d}e^{𝒙\overline{𝒙}^2/(2\sigma ^2)}.$$

A Gaussian perturbation of a matrix may be defined similarly.

For each $`(\overline{A},\overline{𝒃},\overline{𝒄})`$ and $`\sigma 0`$, we let $`𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )`$ denote the distribution of Gaussian perturbations of $`(\overline{A},\overline{𝒃},\overline{𝒄})`$ of variance $`\sigma ^2`$, and we let $`(A,𝒃,𝒄)𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )`$ indicate that $`(A,𝒃,𝒄)`$ is drawn from the distribution $`𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )`$.

Our main result, which is proved in Section 4, is

###### Theorem 1.3.1 (Smoothed Complexity of Renegar’s Condition Number).

For every $`n`$-by-$`d`$ matrix $`\overline{A}`$, $`n`$-vector $`\overline{𝐛}`$ and $`d`$-vector $`\overline{𝐜}`$ such that $`\overline{A},\overline{𝐛},\overline{𝐜}_F1`$, every $`\sigma 1/\sqrt{nd}`$, and every $`i\{1,2,3,4\}`$,

$`\text{Pr}_{A,𝒃,𝒄}\left[C^{(i)}(A,𝒃,𝒄)>{\displaystyle \frac{2^{13}(n+1)^2(d+1)^{1.5}}{\delta \sigma ^2}}\left(\mathrm{log}{\displaystyle \frac{2^{10}(n+1)^2(d+1)^{1.5}}{\delta \sigma ^2}}\right)^2\right]`$ $`<`$ $`\delta ,`$
and

$`\text{E}_{(A,𝒃,𝒄)𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )}\left[\mathrm{log}C^{(i)}(A,𝒃,𝒄)\right]`$ $``$ $`15+4.5\mathrm{log}{\displaystyle \frac{nd}{\sigma }}.`$
Theorem 1.3.1 implies a bound on the smoothed complexity of Renegar’s algorithm as well as a bound on the smoothed complexity of the interior point methods that were developed for the other canonical forms. Note that in the statement of Theorem 1.3.1, we abuse the notation $`C^{(4)}(A,𝒃,𝒄)`$ for $`C^{(4)}(A)`$. The first bound of the theorem means that, with high probability, the condition number of a perturbed linear program is polynomial in $`n`$, $`d`$, and $`1/\sigma `$.

The following theorem follows immediately from Renegar’s analysis (Theorem 1.2.2) and the previous theorem.

###### Theorem 1.3.2 (Smoothed Complexity of IPM).

Let $`T((A,𝐛,𝐜),ϵ)`$ be the time complexity of Renegar’s interior point algorithm for finding $`ϵ`$-accurate solutions of the linear program defined by $`(A,𝐛,𝐜)`$ or determining that the program is infeasible or unbounded. For every $`n`$-by-$`d`$ matrix $`\overline{A}`$, $`n`$-vector $`\overline{𝐛}`$ and $`d`$-vector $`\overline{𝐜}`$ such that $`\overline{A},\overline{𝐛},\overline{𝐜}_F1`$ and every $`\sigma 1/\sqrt{nd}`$,

$$\text{E}_{(A,𝒃,𝒄)𝒩((\overline{A},\overline{𝒃},\overline{𝒄}),\sigma )}\left[T((A,𝒃,𝒄),ϵ)\right]=O\left(n^3\mathrm{log}\left(\frac{n}{\sigma ϵ}\right)\right).$$

In order to analyze Renegar’s condition number for the primal and dual of each of the four canonical forms, we found it necessary to develop several extensions to the theory of condition numbers that may be of independent interest. For example, Lemma 2.2.2 generalizes the geometric condition on distance to ill-posedness developed in \[CC01\] by incorporating an arbitrary non-pointed convex cone that is not subject to perturbation, and this generalization is necessary for the application of our techniques. Additionally, Lemmas 2.3.23.3.1, and 3.3.2 all provide geometric conditions on the distance to ill-posedness whose import to us is on par with Lemma 2.2.2.

### 1.4 Organization of the Paper

In our analysis, we divide the eight condition numbers $`C_P^{(i)}`$ and $`C_D^{(i)}`$, for $`i\{1,2,3,4\}`$, into two groups. The first group includes $`C_P^{(1)}`$, $`C_P^{(2)}`$, $`C_D^{(2)}`$, $`C_D^{(3)}`$, and with some additional work, $`C_P^{(4)}`$. The remaining condition numbers belong to the second group. We will refer to a condition number from the first group as a primal condition number and a condition number from the second group as a dual condition number.

Section 2 is devoted to establishing a smoothed bound on the primal condition number. We remark that the techniques used in Section 2 do not critically depend upon $`A`$, $`𝒃`$ and $`𝒄`$ being Gaussian distributed, and similar theorems could be proved using slight modifications of our techniques if these were smoothly distributed within spheres or cubes. It follows from the result of Section 2 alone that Theorem 1.3.1 holds for linear program given in Form (2).

In Section 3, we establish the smoothed bound on the dual condition number. Our bounds in this section do critically make use of the Gaussian distribution on $`A`$, $`𝒃`$ and $`𝒄`$.

In Section 4, we prove Theorem 1.3.1 using the smoothed bounds of the previous two sections. We conclude the paper in Section 5 with some open questions.

In the remainder of this Section, we review some of the previous work on smoothed analysis, some earlier results on the average-case analysis of interior-point algorithms, and lower bounds on the complexity of interior-point algorithms.

### 1.5 Prior Smoothed Analyses of Linear Programming Algorithms

In their paper introducing Smoothed Analysis \[ST03b\], Spielman and Teng proved that the smoothed complexity of a two-phase shadow vertex simplex method was polynomial in $`n`$, $`d`$ and $`1/\sigma `$. Shortly thereafter, Blum and Dunagan \[BD02\] performed a smoothed analysis of the perceptron algorithm for linear programming. They showed that the probability the perceptron algorithm would take more than a polynomial in the input size times $`k`$ steps was inversely proportional to $`\sqrt{k}`$. Their analysis had the advantage of being significantly simpler than that of \[ST03b\], and it is their analysis that we build upon in this work. Blum and Dunagan’s analysis used the fact that the number of steps taken by the perceptron algorithm can be bounded by the reciprocal of the “wiggle room” in its input, and the bulk of their analysis was a bound on the probability that this “wiggle room” was small. The “wiggle room” turns out to be a condition number of the input to the perceptron algorithm.

### 1.6 Prior Average-Case Analyses of Interior Point Algorithms

There has been an enormous body of work on interior point algorithms, some of which has addressed their average-case complexity. Anstreicher, Ji, Potra and Ye \[AJPY93, AJPY99\], have shown that under Todd’s degenerate model for random linear programs \[Tod91\], a homogeneous self-dual interior point method runs in $`O(\sqrt{n}\mathrm{log}n)`$ expected iterations. Borgwardt and Huhn \[HB02\] have obtained similar results under any spherically symmetric distribution. The performance of other interior point methods on random inputs has been heuristically analyzed through “one-step analyses”, but it is not clear that these analyses can be made rigorous \[Nem88, GT92, MTY93\].

### 1.7 Lower Bounds for Interior Point Algorithms

The best known lower bound on the complexity of interior point methods is $`\mathrm{\Omega }(n^{1/3})`$ iterations due to Todd \[Tod94\] and Todd and Ye \[TY96\]. However, the programs for which these lower bounds hold are very ill-conditioned. There are no known bounds of the form $`\mathrm{\Omega }(n^ϵ)`$ for well-conditioned linear programs. It would be interesting to know whether such a lower bound can be proved for a well-conditioned program, or whether interior point algorithms always require fewer iterations when their input is well-conditioned.

### 1.8 Notation and Basic Geometric Definitions

Throughout this paper we use the following notational conventions. The material up to this point has obeyed these conventions.

* lower case letters such as $`a`$ and $`\alpha `$ denote scalars,
* bold lower case letters such as $`𝒂`$ and $`𝒃`$ denote vectors, and for a vector $`𝒂`$, $`a_i`$ denotes the $`i`$th entry of $`𝒂`$.
* capital letters such as $`A`$ denote matrices, and
* bold capital letters such as $`𝑪`$ denote convex sets.

If $`𝒂_1,\mathrm{},𝒂_n`$ are vectors, we let $`[𝒂_1,\mathrm{},𝒂_n]`$ denote the matrix whose rows are the $`𝒂_i`$s. For a vector $`𝒂`$, we let $`𝒂`$ denote the standard Euclidean norm of the vector. We will make frequent use of the Frobenius norm of a matrix, $`A_F`$, which is the square root of the sum of squares of the entries in the matrix. We extend this notation to let $`A,𝒙_1,\mathrm{},𝒙_k_F`$ denote the square root of the sum of squares of the entries in $`A`$ and in $`𝒙_1,\mathrm{},𝒙_k`$. Different choices of norm are possible; we use the Frobenius norm throughout this paper. The following proposition relates several common choices of norm:

###### Proposition 1.8.1 (Choice of norm).

For an $`n`$-by-$`d`$ matrix $`A`$,

$`{\displaystyle \frac{A_F}{\sqrt{dn}}}`$ $`A_{\mathrm{}}`$ $`A_F,\text{ and}`$
$`{\displaystyle \frac{A_F}{\sqrt{d}}}`$ $`A_{OP}`$ $`A_F,`$
where $`A_{OP}`$ denotes the operator norm of $`A`$, $`\mathrm{max}_{x0}\frac{Ax}{x}`$.

We let $`\mathrm{log}`$ denote the logarithm to base 2 and $`\mathrm{ln}`$ denote the logarithm to base $`e`$.

We also make use of the following geometric definitions:

###### Definition 1.8.2 (Ray).

For a vector $`𝐩`$, let $`\text{Ray}\left(𝐩\right)`$ denote $`\{\alpha 𝐩:\alpha >0\}`$.

###### Definition 1.8.3 (Non-pointed convex cone).

A non-pointed convex cone is a convex set $`𝐂`$ such that for all $`𝐱𝐂`$ and all $`\alpha >0`$, $`\alpha 𝐱𝐂`$, and there exists a vector $`𝐭`$ such that $`𝐭^T𝐱<0`$ for all $`𝐱𝐂`$.

###### Definition 1.8.4 (Positive half-space).

For a vector $`𝐚`$ we let $`(𝐚)`$ denote the half-space of points with non-negative inner product with $`𝐚`$.

For example, $`\mathrm{IR}^d`$ and $`(𝒙)`$ are not non-pointed convex cones, while $`\{𝒙:𝒙_0>0\}`$ and $`\text{Ray}\left(𝒑\right)`$ are non-pointed convex cones. Note that a non-pointed convex cone cannot contain the origin. All of the cones that we introduce through the process of homogenization are non-pointed convex cones.

These definitions enable us to express the feasible $`𝒙`$ for the linear program

$$A𝒙\mathrm{𝟎}\text{ and }𝒙𝑪$$

as

$$𝒙𝑪\underset{i=1}{\overset{n}{}}(𝒂_i),$$

where $`𝒂_1,\mathrm{},𝒂_n`$ are the rows of $`A`$. Throughout this paper, we will call a set *feasible* if it is non-empty, and *infeasible* if it is empty. Thus, we say that the set $`𝑪_{i=1}^n(𝒂_i)`$ is feasible if the corresponding linear program is feasible.

## 2 Primal Condition Number

In this section we show that the smoothed value of the primal condition numbers is polynomial in $`n`$, $`d`$, and $`1/\sigma `$ with polynomially high probability. As in the work of Peña \[Peñ00\], we unify this study by transforming each canonical form to conic form.

The primal program of form (1) can be put into conic form with the introduction of the homogenizing variable $`x_0`$. Setting $`𝑪=\{(𝒙,x_0):x_0>0\}`$, the homogenized primal program of form (1) is

$$[A,𝒃](𝒙,x_0)\mathrm{𝟎},(𝒙,x_0)𝑪.$$

By setting $`𝑪=\{(𝒙,x_0):x_0>0and𝒙\mathrm{𝟎}\}`$, one can similarly homogenize the primal program of form (2). The dual programs of form (2) and form (3) can be homogenized by setting $`𝑪=\{(𝒚,y_0):y_0>0\}`$ and $`𝑪=\{(𝒚,y_0):y_0>0and𝒚\mathrm{𝟎}\}`$, respectively, and considering the program

$$[A^T,𝒄](𝒚,y_0)\mathrm{𝟎},(𝒚,y_0)𝑪.$$

We will comment on $`C_P^{(4)}`$ below. Note that in each of these homogenized programs, the variables lie in a non-pointed convex cone.

Peña \[Peñ00\] proves:

###### Fact 2.0.1 (Preserving feasibility).

Each of the homogenized programs is feasible if and only if its original program is feasible.

In Section 2.1, we extend the notion of distance to ill-posedness and condition number to conic linear programs and note that the transformation by homogenization does not alter the distance to ill-posedness. The rest of the section will be devoted to analyzing the condition number of the conic program, and this will imply the bound on the condition number of the original program.

### 2.1 Linear Programs in Conic Form and Basic Convex Probability Theory

The feasibility problem for a conic linear program can be written:

$$\text{find }𝒙\text{ such that }A𝒙\mathrm{𝟎},𝒙𝑪,$$

where $`𝑪`$ is a non-pointed convex cone in $`\mathrm{IR}^d`$ and $`A`$ is an $`n`$-by-$`d`$ matrix. Note that because $`𝑪`$ is a non-pointed convex cone, $`\mathrm{𝟎}`$ cannot be a feasible solution of this program. The following definition generalizes distance to ill-posedness by explicitly taking into account the non-pointed convex cone, $`𝑪`$.

###### Definition 2.1.1 (Generalized distance to ill-posedness).

For a non-pointed convex cone, $`𝐂`$, that is not subject to perturbation, and a matrix, $`A`$, we define $`\rho (A,𝐂)`$ by

* if $`A𝒙\mathrm{𝟎},𝒙C`$ is feasible, then

$$\rho (A,𝑪)=sup\{ϵ:\mathrm{\Delta }A_F<ϵ\text{ implies }(A+\mathrm{\Delta }A)𝒙\mathrm{𝟎},𝒙𝑪\text{ is feasible}\};$$
* if $`A𝒙\mathrm{𝟎},𝒙C`$ is infeasible, then

$$\rho (A,𝑪)=sup\{ϵ:\mathrm{\Delta }A_F<ϵ\text{ implies }(A+\mathrm{\Delta }A)𝒙\mathrm{𝟎},𝒙𝑪\text{ is infeasible}\}.$$

We note that this definition makes sense even when $`A`$ is a row vector. In this case, $`\rho (𝒂,𝑪)`$ measures the distance to ill-posedness when we only allow perturbation to $`𝒂`$. Even though transformations among linear programming formulations in general do not preserve condition number, Peña \[Peñ00\] has proved that homogenization does not alter the distance to ill-posedness. For convenience, we will state the lemma for form (1), and note that similar statements hold for $`C_P^{(2)}`$, $`C_D^{(2)}`$, and $`C_D^{(3)}`$.

###### Lemma 2.1.2 (Preserving the condition number).

Let

$$\mathrm{max}𝒄^T𝒙s.t.A𝒙𝒃$$

be a linear program. Let $`𝐂=\{(𝐱,x_0):x_0>0\}`$. Then, $`C_P^{(1)}(A,𝐛)=A,𝐛_F/\rho ([A,𝐛],𝐂)`$.

The primal program of form (4) is not quite in conic form; to handle it, we need the following definition.

###### Definition 2.1.3 (Pointed generalized primal distance to ill-posedness).

For a convex cone that is not non-pointed, $`𝐂`$, and a matrix, $`A`$, we define $`\rho (A,𝐂)`$ by

* if $`A𝒙0,𝒙\mathrm{𝟎},𝒙C`$ is feasible, then

$$\rho (A,𝑪)=sup\{ϵ:\mathrm{\Delta }A_F<ϵ\text{ implies }(A+\mathrm{\Delta }A)𝒙\mathrm{𝟎},𝒙\mathrm{𝟎},𝒙𝑪\text{ is feasible}\}$$
* if $`A𝒙0,𝒙\mathrm{𝟎},𝒙C`$ is infeasible, then

$$\rho (A,𝑪)=sup\{ϵ:\mathrm{\Delta }A_F<ϵ\text{ implies }(A+\mathrm{\Delta }A)𝒙\mathrm{𝟎},𝒙\mathrm{𝟎},𝒙𝑪\text{ is infeasible}\}$$

This definition would allow us to prove the analogs of Lemmas 2.1.4 and 2.1.5 for primal programs of form (4). We omit the details of this variation on the arguments in the interest of simplicity.

The following two Lemmas are the main result of this section. To see how they may be applied, we note that a simple union bound over $`C_P^{(2)}`$ and $`C_D^{(2)}`$ using Lemma 2.1.4 yields Theorem 1.3.1 for form (2).

###### Lemma 2.1.4 (Condition number is likely polynomial).

For any non-pointed convex cone $`𝐂`$ and a matrix $`\overline{A}`$ satisfying $`\overline{A}_F1`$, for $`\sigma 1/\sqrt{nd}`$,

$`\text{Pr}_{A𝒩(\overline{A},\sigma )}\left[{\displaystyle \frac{A_F}{\rho (A,𝑪)}}{\displaystyle \frac{2^{12}n^2d^{1.5}}{\delta \sigma ^2}}\mathrm{log}^2\left({\displaystyle \frac{2^9n^2d^{1.5}}{\delta \sigma ^2}}\right)\right]`$ $``$ $`\delta .`$
###### Lemma 2.1.5 (Smoothed analysis of log of primal condition number).

For any non-pointed convex cone $`𝐂`$ and a matrix $`\overline{A}`$ satisfying $`\overline{A}_F1`$, for $`\sigma 1/\sqrt{nd}`$,

$`\text{E}_{A𝒩(\overline{A},\sigma )}\left[\mathrm{log}{\displaystyle \frac{A_F}{\rho (A,𝑪)}}\right]14+4.5\mathrm{log}{\displaystyle \frac{nd}{\sigma }}.`$
We will prove Lemma 2.1.4 by separately considering the cases in which the program is feasible and infeasible. In Section 2.2, we show that it is unlikely that a program is feasible and yet can be made infeasible by a small change to its constraints (Lemma 2.2.1). In Section 2.3, we show that it is unlikely that a program is infeasible and yet can be made feasible by a small change to its constraints (Lemma 2.3.1). In Section 2.4, we combine these results to show that the primal condition number is polynomial with high probability (Lemma 2.1.4). In Section 2.5 we prove Lemma 2.1.5.

The thread of argument in these sections consists of a geometric characterization of those programs with poor condition number, followed by a probabilistic argument demonstrating that this characterization is rarely satisfied. Throughout the proofs in this section, $`𝑪`$ will always refer to the original non-pointed cone, and a subscripted $`𝑪`$ (e.g., $`𝑪_0`$) will refer to a modification of this cone.

The key probabilistic tool used in the analysis is Lemma 2.1.7, which we will derive from the following result of \[Bal93\]. A slightly weaker version of this lemma was proved in \[BD02\], and also in \[BR76\].

###### Theorem 2.1.6 (Ball \[Bal93\]).

Let $`𝐊`$ be a convex body in $`\mathrm{IR}^d`$ and let $`\mu `$ be the density function of a $`𝒩(\mathrm{𝟎},\sigma )`$ Gaussian random variable. Then,

$$_𝑲\mu 4d^{1/4}.$$

###### Lemma 2.1.7 ($`ϵ`$-Boundaries are likely to be missed).

Let $`𝐊`$ be an arbitrary convex body in $`\mathrm{IR}^d`$, and let $`\text{bdry}(𝐊,ϵ)`$ denote the $`ϵ`$-boundary of $`𝐊`$; that is,

$$\text{bdry}(𝑲,ϵ)=\{𝒙:𝒙^{}𝑲,𝒙𝒙^{}ϵ\}$$

For any $`\overline{𝐱}\mathrm{IR}^d`$,

$`\text{Pr}_{𝒙𝒩(\overline{𝒙},\sigma )}\left[𝒙\text{bdry}(𝑲,ϵ)𝑲\right]{\displaystyle \frac{4ϵd^{1/4}}{\sigma }},`$ (outside boundary)
$`\text{Pr}_{𝒙𝒩(\overline{𝒙},\sigma )}\left[𝒙\text{bdry}(𝑲,ϵ)𝑲\right]{\displaystyle \frac{4ϵd^{1/4}}{\sigma }}`$ (inside boundary)
###### Proof.

We derive the result assuming $`\sigma =1`$. The result for general $`\sigma `$ follows by scaling.

Let $`\mu `$ denote the density according to which $`𝒙`$ is distributed. To derive the first inequality, we let $`𝑲_ϵ`$ denote the points of distance at most $`ϵ`$ from $`𝑲`$, and observe that $`𝑲_ϵ`$ is convex.

Integrating by shells, we obtain

$`\text{Pr}\left[𝒙\text{bdry}(𝑲,ϵ)𝑲\right]`$ $`{\displaystyle _{t=0}^ϵ}{\displaystyle _{𝑲_t}}\mu `$
$`ϵ4d^{1/4},`$
by Theorem 2.1.6.

We similarly derive the second inequality by defining $`𝑲^ϵ`$ to be the set of points inside $`𝑲`$ of distance at least $`ϵ`$ from the boundary of $`𝑲`$ and observing that $`𝑲^ϵ`$ is convex for any $`ϵ`$. ∎

In this section and the next, we use the following consequence of Lemma 2.1.7 repeatedly.

###### Lemma 2.1.8 (Feasible likely quite feasible, single constraint).

Let $`𝐂_0`$ be any convex cone in $`\mathrm{IR}^d`$ and, for any $`\overline{𝐚}\mathrm{IR}^d`$, let $`𝐚`$ be a Gaussian perturbation of $`\overline{𝐚}`$ of variance $`\sigma ^2`$. Then,

$`\text{Pr}_𝒂\left[𝑪_0(𝒂)\text{ is feasible and }\rho (𝒂,𝑪_0)ϵ\right]`$ $`{\displaystyle \frac{4ϵd^{1/4}}{\sigma }},\text{ and}`$
$`\text{Pr}_𝒂\left[𝑪_0(𝒂)\text{ is infeasible and }\rho (𝒂,𝑪_0)ϵ\right]`$ $`{\displaystyle \frac{4ϵd^{1/4}}{\sigma }}.`$
###### Proof.

Let $`𝑲`$ be the set of $`𝒂`$ for which $`𝑪_0(𝒂)`$ is infeasible. Observe that $`\rho (𝒂,𝑪_0)`$ is exactly the distance from $`𝒂`$ to the boundary of $`𝑲`$. Since $`𝑲`$ is a convex cone, the first inequality follows from the first inequality (the outside boundary inequality) of Lemma 2.1.7, which tells us that the probability that $`𝒂`$ has distance at most $`ϵ`$ to the boundary of $`𝑲`$ and is outside $`𝑲`$ is at most $`\frac{4ϵd^{1/4}}{\sigma }`$. The second inequality similarly follows from the second inequality (the inside boundary inequality) of Lemma 2.1.7. ∎

### 2.2 Primal condition number, feasible case

In this subsection, we analyze the primal condition number in the feasible case and prove:

###### Lemma 2.2.1 (Feasible is likely quite feasible, all constraints).

Let $`𝐂`$ be a non-pointed convex cone in $`\mathrm{IR}^d`$ and let $`\overline{A}`$ be any $`n`$-by-$`d`$ matrix. Then for any $`\sigma 0`$,

$$\text{Pr}_{A𝒩(\overline{A},\sigma )}\left[\left(A𝒙\mathrm{𝟎},𝒙𝑪\text{ is feasible}\right)\text{ and }\left(\rho (A,𝑪)ϵ\right)\right]\frac{4ϵnd^{5/4}}{\sigma }.$$

To prove Lemma 2.2.1, we first establish a necessary geometric condition for $`\rho `$ to be small. This condition is stated and proved in Lemma 2.2.2. In Lemma 2.2.6, we apply Helly’s Theorem \[LDK63\] to simplify this geometric condition, expressing it in terms of the minimum of $`\rho `$ over individual constraints. This allows us to use Lemma 2.1.8 to establish Lemma 2.2.9, which shows that this geometric condition is unlikely to be met. Lemma 2.2.1 is then a corollary of Lemmas 2.2.9 and 2.2.2.

We remark that a result similar to Lemma 2.2.2 appears in \[CC01\].

###### Lemma 2.2.2 (Bounding $`\rho `$ by a max of min of inner products).

Let $`𝐂`$ be a non-pointed convex cone and let $`𝐚_1,\mathrm{},𝐚_n`$ be vectors in $`\mathrm{IR}^d`$ for which $`𝐂_i(𝐚_i)`$ is feasible. Then

$$\rho ([𝒂_1,\mathrm{},𝒂_n],𝑪)\underset{\begin{array}{c}𝒑𝑪_{i=1}^n(𝒂_i)\\ 𝒑=1\end{array}}{\mathrm{max}}\underset{i}{\mathrm{min}}𝒂_i^T𝒑.$$

###### Proof.

Lemma 2.2.2 follows directly from Lemmas 2.2.5, 2.2.3, and 2.2.4 below. These three lemmas develop a characterization of $`\rho `$, the distance to ill-posedness, in the feasible case. ∎

###### Lemma 2.2.3 (Lower bounding $`\rho `$ by rays).

Under the conditions of Lemma 2.2.2,

$$\rho ([𝒂_1,\mathrm{},𝒂_n],𝑪)\underset{𝒑𝑪_i(𝒂_i)}{\mathrm{max}}\rho ([𝒂_1,\mathrm{},𝒂_n],\text{Ray}\left(𝒑\right)).$$

###### Proof.

Let $`\mathrm{\Delta }𝒂_1,\mathrm{},\mathrm{\Delta }𝒂_n`$ be such that $`𝑪_i(\mathrm{\Delta }𝒂_i+𝒂_i)`$ is infeasible. Then, for all $`𝒑𝑪_i(𝒂_i)`$, $`\text{Ray}\left(𝒑\right)_i(\mathrm{\Delta }𝒂_i+𝒂_i)`$ is also infeasible. ∎

###### Lemma 2.2.4 ($`\rho `$ of a ray as a min over constraints).

For every set of vectors $`𝐚_1,\mathrm{},𝐚_n`$ and $`𝐩`$ such that $`\text{Ray}\left(𝐩\right)_i(𝐚_i)`$ is feasible,

$$\rho ([𝒂_1,\mathrm{},𝒂_n],\text{Ray}\left(𝒑\right))=\underset{i}{\mathrm{min}}\rho (𝒂_i,\text{Ray}\left(𝒑\right)).$$

###### Proof.

Observe that $`\text{Ray}\left(𝒑\right)_i(𝒂_i+\mathrm{\Delta }𝒂_i)`$ is feasible if and only if $`\text{Ray}\left(𝒑\right)(𝒂_i+\mathrm{\Delta }𝒂_i)`$ is feasible for all $`i`$. ∎

###### Lemma 2.2.5 ($`\rho `$ of a ray and single constraint as an inner product).

For every vector $`𝐚`$ and every unit vector $`𝐩`$,

$$\rho (𝒂,\text{Ray}\left(𝒑\right))=\left|𝒂^T𝒑\right|$$

###### Proof.

If $`𝒂^T𝒑=0`$, then $`\rho (𝒂,\text{Ray}\left(𝒑\right))=0`$. If $`𝒂^T𝒑0`$, then $`\text{Ray}\left(𝒑\right)(𝒂)`$ is feasible if and only if $`\text{Ray}\left(𝒑\right)(𝒂)`$ is infeasible; so, it suffices to consider the case where $`\text{Ray}\left(𝒑\right)(𝒂)`$ is feasible. So, we assume $`𝒂^T𝒑>0`$, in which case $`\text{Ray}\left(𝒑\right)(𝒂)`$ is feasible. We first prove that $`\rho (𝒂,\text{Ray}\left(𝒑\right))𝒂^T𝒑`$. For every vector $`\mathrm{\Delta }𝒂`$ of norm at most $`𝒂^T𝒑`$, we have

$$(𝒂+\mathrm{\Delta }𝒂)^T𝒑=𝒂^T𝒑+\mathrm{\Delta }𝒂^T𝒑𝒂^T𝒑\mathrm{\Delta }𝒂0.$$

That is, $`𝒑(𝒂+\mathrm{\Delta }𝒂)`$. As this holds for every $`\mathrm{\Delta }𝒂`$ of norm at most $`𝒂^T𝒑`$, we have $`\rho (𝒂,\text{Ray}\left(𝒑\right))𝒂^T𝒑`$.

To show that $`\rho (𝒂,\text{Ray}\left(𝒑\right))𝒂^T𝒑`$, note that setting $`\mathrm{\Delta }𝒂=(ϵ+𝒂^T𝒑)𝒑`$, for any $`ϵ>0`$, yields

$$(𝒂+\mathrm{\Delta }𝒂)^T𝒑=𝒂^T𝒑+\mathrm{\Delta }𝒂^T𝒑=𝒂^T𝒑(ϵ+𝒂^T𝒑)𝒑^T𝒑=𝒂^T𝒑(ϵ+𝒂^T𝒑)=ϵ;$$

so, $`\text{Ray}\left(𝒑\right)(𝒂+\mathrm{\Delta }𝒂)`$ is infeasible. As this holds for every $`ϵ>0`$, $`\rho (𝒂,\text{Ray}\left(𝒑\right))𝒂^T𝒑`$. ∎

###### Lemma 2.2.6 (Bounding the max of min of inner products).

Let $`𝐂`$ be a non-pointed convex cone and let $`𝐚_1,\mathrm{},𝐚_n`$ be vectors in $`\mathrm{IR}^d`$ for which $`𝐂_i(𝐚_i)`$ is feasible. Then

$$\underset{\begin{array}{c}𝒑𝑪_{i=1}^n(𝒂_i)\\ 𝒑=1\end{array}}{\mathrm{max}}\underset{i}{\mathrm{min}}𝒂_i^T𝒑\underset{i}{\mathrm{min}}\rho (𝒂_i,𝑪\underset{ji}{}(𝒂_j))/d.$$

We will derive Lemma 2.2.6 from Lemmas 2.2.7 and 2.2.8, which we now state and prove.

###### Lemma 2.2.7 (Quite feasible region implies quite feasible point, single constraint).

For every $`𝐚`$ and every non-pointed convex cone $`𝐂_0`$ for which $`𝐂_0(𝐚)`$ is feasible,

$$\rho (𝒂,𝑪_0)=\underset{\begin{array}{c}𝒑𝑪_0(𝒂)\\ 𝒑=1\end{array}}{\mathrm{max}}𝒂^T𝒑.$$

###### Proof.

The “$``$” direction follows from Lemmas 2.2.3 and 2.2.5; so, we concentrate on showing

$$\rho (𝒂,𝑪_0)\underset{\begin{array}{c}𝒑𝑪_0(𝒂)\\ 𝒑=1\end{array}}{\mathrm{max}}𝒂^T𝒑.$$

We recall that, as $`𝑪_0`$ is non-pointed, there exists a vector $`𝒕`$ such that $`𝒕^T𝒙<0`$ for all $`𝒙𝑪_0`$. We now divide the proof into two cases depending on whether $`𝒂𝑪_0`$.

If $`𝒂𝑪_0`$, then we let $`𝒑=𝒂/𝒂`$. It is easy to verify that

$$𝒂^T𝒑=𝒂=\underset{𝒑=1}{\mathrm{max}}𝒂^T𝒑=\underset{\begin{array}{c}𝒑𝑪_0(𝒂)\\ 𝒑=1\end{array}}{\mathrm{max}}𝒂^T𝒑.$$

Moreover, $`𝑪_0(𝒂(𝒂+ϵ𝒕))`$ is infeasible for every $`ϵ>0`$. So, $`\rho (𝒂,𝑪_0)𝒂`$.

If $`𝒂𝑪_0`$, let $`𝒒`$ be the point of $`𝑪_0`$ that is closest to $`𝒂`$. As $`𝑪_0(𝒂)`$ is feasible, $`𝒒`$ lies inside $`(𝒂)`$ and is not the origin. Let $`𝒑=𝒒/𝒒`$. As $`𝑪_0`$ is a cone, $`𝒒`$ is perpendicular to $`𝒂𝒒`$. Thus, the distance from $`𝒂`$ to $`𝒒`$ is $`\sqrt{𝒂^2𝒒^2}=\sqrt{𝒂^2(𝒂^T𝒑)^2}`$, as $`𝒂^T𝒑=𝒒`$. Conversely, for any unit vector $`𝒓𝑪_0`$, the distance from $`\text{Ray}\left(𝒓\right)`$ to $`𝒂`$ is $`\sqrt{𝒂^2(𝒂^T𝒓)^2}`$. Thus, the unit vector $`𝒓𝑪_0`$ maximizing $`𝒂^T𝒓`$ must be $`𝒑`$.

As $`𝑪_0`$ is convex, there is a plane through $`𝒒`$ separating $`𝑪_0`$ from $`𝒂`$ and perpendicular to the line segment $`𝒂𝒒`$, and thus $`\rho (𝒂,𝑪_0)𝒒=𝒂^T𝒑`$.

###### Lemma 2.2.8 (Quite feasible individually implies quite feasible collectively).

Let $`𝐂_0`$ be a non-pointed convex cone and let $`𝐚_1,\mathrm{},𝐚_n`$ be vectors in $`\mathrm{IR}^d`$. If there exist unit vectors $`𝐩_1,\mathrm{},𝐩_n𝐂_0`$, such that

$`𝒂_i^T𝒑_i`$ $``$ $`ϵ,\text{ for all }i\text{, and}`$
$`𝒂_i^T𝒑_j`$ $``$ $`0,\text{ for all }i\text{ and }j\text{,}`$
then there exists a unit vector $`𝐩𝐂_0`$ such that

$$𝒂_i^T𝒑ϵ/d,\text{ for all }i\text{.}$$

###### Proof.

We prove this using Helly’s Theorem \[LDK63\] which says that if a collection of convex sets in $`\mathrm{IR}^d`$ has the property that every subcollection of $`d+1`$ of the sets has a common point, then the entire collection has a common point. Let

$$\mathrm{SS}_i=\{𝒙𝑪_0:𝒂_i^T𝒙/𝒙ϵ/d\}.$$

We begin by proving that every $`d`$ of the $`\mathrm{SS}_i`$s contain a point in common. Without loss of generality, we consider $`\mathrm{SS}_1,\mathrm{},\mathrm{SS}_d`$. Let $`𝒑=_{i=1}^d𝒑_i/d`$. Then, for each $`1jd`$,

$$𝒂_j^T𝒑=𝒂_j^T\left(\underset{i=1}{\overset{d}{}}𝒑_i/d\right)𝒂_j^T\left(𝒑_j/d\right)ϵ/d.$$

As $`𝒑`$ has norm at most one, $`𝒂_j^T𝒑/𝒑𝒂_j^T𝒑`$, so $`𝒑`$ is contained in each of $`S_1,\mathrm{},S_d`$.

As $`𝑪_0`$ is non-pointed, there exists $`𝒕`$ such that $`𝒕^T𝒙<0,𝒙𝑪_0`$. Let $`\mathrm{SS}_i^{}=\mathrm{SS}_i\{𝒙:𝒕^T𝒙=1\}`$. Then, $`𝒙\mathrm{SS}_i`$ implies $`𝒙/𝒕^T𝒙\mathrm{SS}_i^{}`$. So, every $`d`$ of the $`\mathrm{SS}_i^{}`$ have a point in common. As these are convex sets lying in a $`d1`$ dimensional space, Helly’s Theorem tells us that there exists a point $`𝒑`$ that lies within all of the $`\mathrm{SS}_i^{}`$s. As $`\mathrm{SS}_i^{}\mathrm{SS}_i`$, this point lies inside all the $`\mathrm{SS}_i`$s. ∎

###### Proof of Lemma 2.2.6.

For each $`i`$, we apply Lemma 2.2.7, to the vector $`𝒂_i`$ and the cone $`𝑪_{ji}(𝒂_j)`$ to find a unit vector $`𝒑_i𝑪_{j=1}^n(𝒂_j)`$ such that

$$𝒑_i^T𝒂_i=\rho (𝒂_i,𝑪\underset{ji}{}(𝒂_j)).$$

As $`𝒑_i𝑪_j(𝒂_j)`$, we also have

$$𝒑_i^T𝒂_j0$$

for all $`j`$. Applying Lemma 2.2.8, we find a unit vector $`𝒑𝑪_{j=1}^n(𝒂_j)`$ satisfying

$$𝒂_i^T𝒑\underset{i}{\mathrm{min}}\rho (𝒂_i,𝑪\underset{ji}{}(𝒂_j))/d,$$

for all $`i`$. ∎

###### Lemma 2.2.9 (Max of min of inner products is likely large).

Let $`𝐂`$ be a non-pointed convex cone in $`\mathrm{IR}^d`$ and let $`\overline{𝐚}_1,\mathrm{},\overline{𝐚}_n`$ be vectors in $`\mathrm{IR}^d`$. Let $`𝐚_1,\mathrm{},𝐚_n`$ be Gaussian perturbations of $`\overline{𝐚}_1,\mathrm{},\overline{𝐚}_n`$ of variance $`\sigma ^2`$. Then,

$$\text{Pr}\left[C\underset{i}{}(𝒂_i)\text{ is feasible and }\underset{\begin{array}{c}𝒑𝑪_{i=1}^n(𝒂_i)\\ 𝒑=1\end{array}}{\mathrm{max}}\underset{i}{\mathrm{min}}𝒂_i^T𝒑<ϵ\right]\frac{4ϵnd^{5/4}}{\sigma }.$$

###### Proof.

By Lemma 2.2.6,

$$\begin{array}{c}\text{Pr}\left[C\underset{i}{}(𝒂_i)\text{ is feasible and }\underset{\begin{array}{c}𝒑𝑪_{i=1}^n(𝒂_i)\\ 𝒑=1\end{array}}{\mathrm{max}}\underset{i}{\mathrm{min}}𝒂_i^T𝒑<ϵ\right]\hfill \\ \hfill \text{Pr}\left[C\underset{i}{}(𝒂_i)\text{ is feasible and }\underset{i}{\mathrm{min}}\rho (𝒂_i,𝑪\underset{ji}{}(𝒂_j))<dϵ\right].\end{array}$$

Applying a union bound over $`i`$ and then Lemma 2.1.8, we find this probability is at most

$`{\displaystyle \underset{i=1}{\overset{n}{}}}\text{Pr}\left[C{\displaystyle \underset{j}{}}(𝒂_j)\text{ is feasible and }\rho (𝒂_i,𝑪{\displaystyle \underset{ji}{}}(𝒂_j))<dϵ\right]`$ $`{\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \frac{4(ϵd)d^{1/4}}{\sigma }}={\displaystyle \frac{4nϵd^{5/4}}{\sigma }}.`$
###### Proof of Lemma 2.2.1.

Follows immediately from Lemmas 2.2.2 and 2.2.9. ∎

This concludes the analysis that it is unlikely that the primal program is both feasible and has small distance to ill-posedness. Next, we show that it is unlikely that the primal program is both infeasible and has small distance to ill-posedness.

### 2.3 Primal number, infeasible case

The main result of this subsection is:

###### Lemma 2.3.1 (Infeasible is likely quite infeasible).

Let $`𝐂`$ be a non-pointed convex cone in $`\mathrm{IR}^d`$ and let $`\overline{A}`$ be any $`n`$-by-$`d`$ matrix such that $`\overline{A}_F1`$. Then, for any $`0<\sigma 1/\sqrt{d}`$ and $`ϵ<1/2`$,

$`\text{Pr}_{A𝒩(\overline{A},\sigma )}\left[\left(A𝒙0,𝒙𝑪\text{ is infeasible}\right)\text{ and }\left(\rho (A,𝑪)ϵ\right)\right]`$ $``$ $`{\displaystyle \frac{361ϵn^2d^{1.5}\mathrm{log}^{1.5}(1/ϵ)}{\sigma ^2}}.`$
To prove Lemma 2.3.1, we consider adding the constraints one at a time. If the program is infeasible in the end, then there must be some constraint, which we call the critical constraint, that takes it from being feasible to being infeasible. Lemma 2.3.2 gives a sufficient geometric condition for the program to be quite infeasible when the critical constraint is added. We then prove Lemma 2.3.1 by showing that this condition is met with good probability. The geometric condition is that the program is quite feasible before the critical constraint is added and that every previously feasible point is far from being feasible for the critical constraint.

###### Lemma 2.3.2 (The feasible-to-infeasible transition).

Let $`𝐂`$ be a non-pointed convex cone in $`\mathrm{IR}^d`$, $`𝐩𝐂`$ be a unit vector, and $`𝐚_1,\mathrm{},𝐚_{k+1}`$ be vectors in $`\mathrm{IR}^d`$ such that

$`𝒂_i^T𝒑\alpha ,`$ for $`1ik`$, and
$`𝒂_{k+1}^T𝒙\beta ,`$ $`\text{for all }𝒙𝑪_{i=1}^k(𝒂_i),𝒙=1.`$
Then,

$$\rho ([𝒂_1,\mathrm{},𝒂_{k+1}],𝑪)\mathrm{min}\{\frac{\alpha }{2},\frac{\alpha \beta }{4\alpha +2𝒂_{k+1}}\}.$$

We will derive Lemma 2.3.2 from the following geometric lemma.

###### Lemma 2.3.3 ($`\rho `$ bound on inner product).

Let $`𝐂`$ be a non-pointed convex cone and let $`𝐚`$ be a vector for which $`𝐂(𝐚)`$ is infeasible. Then,

$$\underset{𝒑𝑪,𝒑=1}{\mathrm{max}}𝒑^T𝒂\rho (𝒂,𝑪).$$

###### Proof.

Let $`𝒑`$ be the unit vector in $`𝑪`$ maximizing $`𝒑^T𝒂`$. If we set

$$\mathrm{\Delta }𝒂=\left(ϵ𝒑^T𝒂\right)𝒑,$$

for any $`ϵ>0`$, then we can see that $`𝑪(𝒂+\mathrm{\Delta }𝒂)`$ is feasible from

$`𝒑^T(𝒂+\mathrm{\Delta }𝒂)`$ $`=𝒑^T𝒂+\left(ϵ𝒑^T𝒂\right)𝒑^T𝒑`$
$`=𝒑^T𝒂+\left(ϵ𝒑^T𝒂\right)`$
$`=ϵ.`$
So, we may conclude $`\rho (𝒂,𝑪)\left|𝒑^T𝒂\right|`$. ∎

###### Proof of Lemma 2.3.2.

The conditions of the lemma imply that $`𝑪_{i=1}^{k+1}(𝒂_i)`$ is infeasible. So, we may prove the lemma by demonstrating that for all $`ϵ`$ satisfying

$`ϵ`$ $``$ $`\alpha /2,\text{ and}`$ (5)
$`ϵ`$ $`<`$ $`{\displaystyle \frac{\beta }{4+2𝒂_{k+1}/\alpha }},`$ (6)
and all $`\{\mathrm{\Delta }𝒂_1,\mathrm{},\mathrm{\Delta }𝒂_{k+1}\}`$ satisfying $`\mathrm{\Delta }𝒂_i<ϵ`$ for $`1ik+1`$, we have

$$𝑪\underset{i=1}{\overset{k+1}{}}(𝒂_i+\mathrm{\Delta }𝒂_i)\text{ is infeasible.}$$

Assume by way of contradiction that

$$𝑪\underset{i=1}{\overset{k+1}{}}(𝒂_i+\mathrm{\Delta }𝒂_i)\text{ is feasible.}$$

Then, there exists a unit vector $`𝒙^{}𝑪_{i=1}^{k+1}(𝒂_i+\mathrm{\Delta }𝒂_i)`$. We first show that

$$𝒙^{}+\frac{ϵ}{\alpha }𝒑𝑪\underset{i=1}{\overset{k}{}}(𝒂_i).$$
(7)
To see this, consider any $`ik`$ and note that $`(𝒂_i+\mathrm{\Delta }𝒂_i)^T𝒙^{}0`$ implies

$$𝒂_i^T𝒙^{}\mathrm{\Delta }𝒂_i^T𝒙^{}\mathrm{\Delta }𝒂_i𝒙^{}ϵ.$$

Thus,

$$𝒂_i^T\left(𝒙^{}+\frac{ϵ}{\alpha }𝒑\right)=𝒂_i^T𝒙^{}+𝒂_i^T\frac{ϵ}{\alpha }𝒑ϵ+\frac{ϵ}{\alpha }\alpha 0.$$

To finish our proof of (7), we observe that $`𝒙^{}𝑪`$ and $`𝒑𝑪`$ imply $`𝒙^{}+\frac{ϵ}{\alpha }𝒑𝑪`$.

Let $`𝒙=𝒙^{}+\frac{ϵ}{\alpha }𝒑`$. Then $`𝒙𝑪_{i=1}^k(𝒂_i)`$ and $`𝒙`$ has norm at most $`1+ϵ/\alpha `$ and at least $`1ϵ/\alpha `$. To derive a contradiction, we now compute

$`(𝒂_{k+1}+\mathrm{\Delta }𝒂_{k+1})^T𝒙^{}`$ $`=`$ $`(𝒂_{k+1}+\mathrm{\Delta }𝒂_{k+1})^T(𝒙(ϵ/\alpha )𝒑)`$
$`=`$ $`𝒂_{k+1}^T𝒙+\mathrm{\Delta }𝒂_{k+1}^T𝒙(ϵ/\alpha )𝒂_{k+1}^T𝒑(ϵ/\alpha )\mathrm{\Delta }𝒂_{k+1}^T𝒑`$
$``$ $`\beta 𝒙+\mathrm{\Delta }𝒂_{k+1}𝒙+(ϵ/\alpha )𝒂_{k+1}+(ϵ/\alpha )\mathrm{\Delta }𝒂_{k+1}`$
$``$ $`\beta (1ϵ/\alpha )+ϵ(1+ϵ/\alpha )+(ϵ/\alpha )𝒂_{k+1}+(ϵ^2/\alpha )`$
$`=`$ $`\beta (1ϵ/\alpha )+ϵ\left((1+ϵ/\alpha )+𝒂_{k+1}/\alpha +ϵ/\alpha \right)`$
$``$ $`\beta /2+ϵ\left(2+𝒂_{k+1}/\alpha \right),\text{ by (}\text{5}\text{)}`$
$`<`$ $`0\text{ by (}\text{6}\text{)},`$
which contradicts $`𝒙^{}𝑪_{i=1}^{k+1}(𝒂_i+\mathrm{\Delta }𝒂_i)`$. ∎

We now prove that the geometric condition of Lemma 2.3.2 holds with high probability. First, we establish two basic statements.

###### Proposition 2.3.4.

For positive $`\alpha `$, $`\beta `$ and any vector $`𝐚_{k+1}`$,

$$\frac{\alpha \beta }{2\alpha +𝒂_{k+1}}\mathrm{min}\{\frac{\alpha \beta }{2+𝒂_{k+1}},\frac{\beta }{2+𝒂_{k+1}}\}.$$

###### Proof.

For $`\alpha 1`$, we have

$$\frac{\alpha \beta }{2\alpha +𝒂_{k+1}}=\frac{\beta }{2+𝒂_{k+1}/\alpha }\frac{\beta }{2+𝒂_{k+1}},$$

while for $`\alpha 1`$ we have

$$\frac{\alpha \beta }{2\alpha +𝒂_{k+1}}\frac{\alpha \beta }{2+𝒂_{k+1}}.$$

###### Proposition 2.3.5.

If $`𝐂_{i=1}^k(𝐚_i)`$ is infeasible, then

$$\rho ([𝒂_1,\mathrm{},𝒂_k],𝑪)\rho ([𝒂_1,\mathrm{},𝒂_n],𝑪).$$

###### Proof.

Adding constraints cannot make it easier to change the program to make it feasible. ∎

###### Proof of Lemma 2.3.1.

Let $`𝒂_1,\mathrm{},𝒂_n`$ be the rows of $`A`$, and let

$$𝑪_0=𝑪\text{and}𝑪_k=𝑪\underset{i=1}{\overset{k}{}}(𝒂_k).$$

Note that $`𝑪_n`$ is the final program. Let $`E_k`$ denote the event that $`𝑪_{k1}`$ is feasible and $`𝑪_k`$ is infeasible. Using Proposition 2.3.5 and the fact that $`𝑪_n`$ infeasible implies that $`E_k`$ must hold for some $`k`$, we obtain

$`\text{Pr}\left[𝑪_n\text{ is infeasible and }\rho ([𝒂_1,\mathrm{},𝒂_n],𝑪)ϵ\right]`$
$`{\displaystyle \underset{k=0}{\overset{n1}{}}}\text{Pr}\left[E_{k+1}\text{ and }\rho ([𝒂_1,\mathrm{},𝒂_n],𝑪)ϵ\right]`$
$`{\displaystyle \underset{k=0}{\overset{n1}{}}}\text{Pr}\left[E_{k+1}\text{ and }\rho ([𝒂_1,\mathrm{},𝒂_{k+1}],𝑪)ϵ\right].`$ (8)
If $`E_{k+1}`$ occurs, then $`𝑪_k`$ is feasible, and we may define

$$\kappa (𝒂_1,\mathrm{},𝒂_k)=\underset{\begin{array}{c}𝒑𝑪_k\\ 𝒑=1\end{array}}{\mathrm{max}}\underset{1ik}{\mathrm{min}}𝒂_i^T𝒑.$$

Then, $`E_{k+1}`$ implies

$`𝒂_i^T𝒑`$ $`\kappa (𝒂_1,\mathrm{},𝒂_k),\text{ for }1ik\text{, and}`$
Lemma 2.3.3 implies
$`𝒂_{k+1}^T𝒙`$ $`\rho (𝒂_{k+1},𝑪_k)\text{ for all }𝒙𝑪_k\text{}𝒙=1.`$
So, we may apply Lemma 2.3.2 and Proposition 2.3.4 to show that $`E_{k+1}`$ implies

$`\rho ([𝒂_1,\mathrm{},𝒂_{k+1}],𝑪)`$ $`\mathrm{min}\{{\displaystyle \frac{\kappa (𝒂_1,\mathrm{},𝒂_k)}{2}},{\displaystyle \frac{\kappa (𝒂_1,\mathrm{},𝒂_k)\rho (𝒂_{k+1},𝑪_k)}{4+2𝒂_{k+1}}},{\displaystyle \frac{\rho (𝒂_{k+1},𝑪_k)}{4+2𝒂_{k+1}}}\}`$
$`{\displaystyle \frac{\mathrm{min}\{\kappa (𝒂_1,\mathrm{},𝒂_k),\kappa (𝒂_1,\mathrm{},𝒂_k)\rho (𝒂_{k+1},𝑪_k),\rho (𝒂_{k+1},𝑪_k)\}}{4+2𝒂_{k+1}}}`$ (9)
We now proceed to bound the probability that the numerator of this fraction is small.

We first note that

$$\kappa (𝒂_1,\mathrm{},𝒂_k)\rho (𝒂_{k+1},𝑪_k)\lambda $$

implies that either $`\kappa (𝒂_1,\mathrm{},𝒂_k)\lambda `$, $`\rho (𝒂_{k+1},𝑪_k)\lambda `$, or there exists an $`l`$ between 1 and $`\mathrm{log}(1/\lambda )`$ for which

$$\kappa (𝒂_1,\mathrm{},𝒂_k)2^{l+1}\text{ and }\rho (𝒂_{k+1},𝑪_k)2^l\lambda .$$

We apply Lemma 2.1.8 to bound

$$\text{Pr}_{𝒂_{k+1}}\left[E_{k+1}\text{ and }\rho (𝒂_{k+1},𝑪_k)\lambda \right]\frac{4\lambda d^{1/4}}{\sigma },$$
(10)
and Lemma 2.2.9 to bound

$$\text{Pr}_{𝒂_1,\mathrm{},𝒂_k}\left[𝑪_k\text{ is feasible and }\kappa (𝒂_1,\mathrm{},𝒂_k)\lambda \right]\frac{4\lambda nd^{5/4}}{\sigma }.$$
(11)
So, for $`1l\mathrm{log}(1/\lambda )`$, we obtain

$`\text{Pr}_{𝒂_1,\mathrm{},𝒂_{k+1}}\left[E_{k+1}\text{ and }\kappa (𝒂_1,\mathrm{},𝒂_k)2^{l+1}\text{ and }\rho (𝒂_{k+1},𝑪_k)2^l\lambda \right]`$
$`=`$ $`\text{Pr}_{𝒂_1,\mathrm{},𝒂_k}[𝑪_k\mathrm{}\text{ and }\kappa (𝒂_1,\mathrm{},𝒂_k)2^{l+1}]`$
$`\text{Pr}_{𝒂_{k+1}}\left[\text{ }𝑪_{k+1}=\mathrm{}\text{ and }\rho (𝒂_{k+1},𝑪_k)2^l\lambda |𝑪_k\mathrm{}\text{ and }\kappa (𝒂_1,\mathrm{},𝒂_k)2^{l+1}\right]`$
$``$ $`\text{Pr}_{𝒂_1,\mathrm{},𝒂_k}\left[𝑪_k\mathrm{}\text{ and }\kappa (𝒂_1,\mathrm{},𝒂_k)2^{l+1}\right]{\displaystyle \frac{2^l4\lambda d^{1/4}}{\sigma }},\text{ by (}\text{10}\text{)}`$
$``$ $`{\displaystyle \frac{2^{l+1}4nd^{5/4}}{\sigma }}{\displaystyle \frac{2^l4\lambda d^{1/4}}{\sigma }},\text{ by (}\text{11}\text{),}`$
$`=`$ $`{\displaystyle \frac{32\lambda nd^{1.5}}{\sigma ^2}}.`$
Summing over the choices for $`l`$, we obtain

$`\text{Pr}\left[E_{k+1}\text{ and }\mathrm{min}\{\kappa (𝒂_1,\mathrm{},𝒂_k),\kappa (𝒂_1,\mathrm{},𝒂_k)\rho (𝒂_{k+1},𝑪_k),\rho (𝒂_{k+1},𝑪_k)\}<\lambda \right]`$ (12)
$``$ $`{\displaystyle \frac{4\lambda nd^{5/4}}{\sigma }}+{\displaystyle \frac{4\lambda d^{1/4}}{\sigma }}+\mathrm{log}(1/\lambda ){\displaystyle \frac{32\lambda nd^{1.5}}{\sigma ^2}}`$
$``$ $`\lambda \left({\displaystyle \frac{4nd^{3/4}+4+32\mathrm{log}(1/\lambda )nd^{1.5}}{\sigma ^2}}\right),\text{ by }\sigma 1/\sqrt{d},`$
$``$ $`\lambda \left({\displaystyle \frac{(32\mathrm{log}(1/\lambda )+8)nd^{1.5}}{\sigma ^2}}\right).`$
This concludes our analysis of the numerator of (9). We can bound the probability that the denominator of (9) is small by observing that $`𝒂_{k+1}`$ is a Gaussian centered at a point $`\overline{𝒂}_{k+1}`$ of norm at most 1; so, Corollary A.0.3 implies

$$\text{Pr}\left[4+2𝒂_{k+1}6+2\sigma \sqrt{2d\mathrm{ln}(e/ϵ)}\right]ϵ.$$
(13)
We now set $`\lambda =ϵ(6+2\sigma \sqrt{2d\mathrm{ln}(e/ϵ)})`$ and observe that if we had

$$\frac{\mathrm{min}\{\kappa (𝒂_1,\mathrm{},𝒂_k),\kappa (𝒂_1,\mathrm{},𝒂_k)\rho (𝒂_{k+1},𝑪_k),\rho (𝒂_{k+1},𝑪_k)\}}{4+2𝒂_{k+1}}ϵ$$

this would imply

$`\mathrm{min}\{\kappa (𝒂_1,\mathrm{},𝒂_k),\kappa (𝒂_1,\mathrm{},𝒂_k)\rho (𝒂_{k+1},𝑪_k),\rho (𝒂_{k+1},𝑪_k)\}`$ $`<\lambda ,\text{ or}`$
$`4+2𝒂_{k+1}`$ $`6+2\sigma \sqrt{2d\mathrm{ln}(e/ϵ)}.`$
So, we may apply (12) and (13) to obtain

$`\text{Pr}\left[E_{k+1}\text{ and }\rho ([𝒂_1,\mathrm{},𝒂_{k+1}],𝑪)ϵ\right]`$
$`ϵ+ϵ\left(6+2\sigma \sqrt{2d\mathrm{ln}(e/ϵ)}\right)\left({\displaystyle \frac{(32\mathrm{log}(1/ϵ(6+2\sigma \sqrt{d\mathrm{log}(e/ϵ)}))+8)nd^{1.5}}{\sigma ^2}}\right)`$
$`ϵ+ϵ\left(6+3\sqrt{\mathrm{ln}(e/ϵ)}\right)\left({\displaystyle \frac{(32\mathrm{log}(1/(6ϵ))+8)nd^{1.5}}{\sigma ^2}}\right),\text{ using }\sigma 1/\sqrt{d}\text{ in the first term}`$
$`ϵ+ϵ\left(9\sqrt{\mathrm{ln}(e/ϵ)}\right)\left({\displaystyle \frac{(32\mathrm{log}(1/(6ϵ))+8)nd^{1.5}}{\sigma ^2}}\right)`$
$`ϵ+ϵ\left({\displaystyle \frac{360\mathrm{log}^{1.5}(1/ϵ)nd^{1.5}}{\sigma ^2}}\right),`$
since $`(\sqrt{\mathrm{ln}(e/ϵ)})(\mathrm{log}(1/6ϵ)+1/4)\mathrm{log}^{1.5}(1/ϵ)`$ for $`ϵ<1/361`$,
$`ϵ\left({\displaystyle \frac{361\mathrm{log}^{1.5}(1/ϵ)nd^{1.5}}{\sigma ^2}}\right)`$
Plugging this in to (8), we get

$`\text{Pr}\left[𝑪_0\text{ is infeasible and }\rho ([𝒂_1,\mathrm{},𝒂_n],𝑪)ϵ\right]`$ $``$ $`{\displaystyle \frac{361ϵn^2d^{1.5}\mathrm{log}^{1.5}(1/ϵ)}{\sigma ^2}}.`$
### 2.4 Primal condition number, putting the feasible and infeasible cases together

We combine the results of Sections 2.2 and 2.3 to prove Lemma 2.1.4, which says that the primal condition number is probably low.

###### Proof of Lemma 2.1.4.

In Lemma 2.2.1, we show that

$$\text{Pr}\left[\left(A𝒙0,𝒙𝑪\text{ is feasible}\right)\text{ and }\left(\rho (A,𝑪)ϵ\right)\right]\frac{4ϵnd^{5/4}}{\sigma },$$

while in Lemma 2.3.1, we show

$`\text{Pr}\left[\left(A𝒙0,𝒙𝑪\text{ is infeasible}\right)\text{ and }\left(\rho (A,𝑪)ϵ\right)\right]`$ $``$ $`{\displaystyle \frac{361ϵ\mathrm{log}^{1.5}(1/ϵ)n^2d^{1.5}}{\sigma ^2}}.`$
Thus,

$`\text{Pr}\left[\rho (A,𝑪)ϵ\right]`$ $`=`$ $`\text{Pr}\left[\left(A𝒙0,𝒙𝑪\text{ is feasible}\right)\text{ and }\left(\rho (A,𝑪)ϵ\right)\right]`$ (14)
$`+\text{Pr}\left[\left(A𝒙0,𝒙𝑪\text{ is infeasible}\right)\text{ and }\left(\rho (A,𝑪)ϵ\right)\right]`$
$``$ $`{\displaystyle \frac{4ϵnd^{5/4}}{\sigma }}+{\displaystyle \frac{361ϵ\mathrm{log}^{1.5}(1/ϵ)n^2d^{1.5}}{\sigma ^2}}`$
$``$ $`{\displaystyle \frac{365ϵ\mathrm{log}^{1.5}(1/ϵ)n^2d^{1.5}}{\sigma ^2}}`$
Setting $`ϵ=\delta /(3\alpha \mathrm{log}^{1.5}(\alpha /\delta ))`$ where $`\alpha =365\frac{n^2d^{1.5}}{\sigma ^2}`$ (note that this satisfies $`ϵ<1/2`$), we obtain

$`\text{Pr}\left[{\displaystyle \frac{1}{\rho (A,𝑪)}}{\displaystyle \frac{1100n^2d^{1.5}}{\delta \sigma ^2}}\mathrm{log}^{1.5}\left({\displaystyle \frac{365n^2d^{1.5}}{\delta \sigma ^2}}\right)\right]`$ $``$ $`{\displaystyle \frac{\alpha \delta \mathrm{log}^{1.5}\left(\frac{3\alpha }{\delta }\mathrm{log}^{1.5}\left(\frac{\alpha }{\delta }\right)\right)}{3\alpha \mathrm{log}^{1.5}(\frac{\alpha }{\delta })}}`$ (15)
$``$ $`0.74\delta ,`$
as $`\alpha /\delta 365`$.

At the same time, Corollary A.0.3 tells us that

$$\text{Pr}\left[A_F1+\sigma \sqrt{nd2\mathrm{ln}(4e/\delta )}\right]\delta /4.$$

The lemma now follows by applying this bound, $`\sigma 1/\sqrt{nd}`$, and (15), to get

$`\text{Pr}\left[{\displaystyle \frac{A_F}{\rho (A,𝑪)}}{\displaystyle \frac{(1+\sqrt{2\mathrm{ln}(4e/\delta )})1100n^2d^{1.5}}{\delta \sigma ^2}}\mathrm{log}^{1.5}\left({\displaystyle \frac{365n^2d^{1.5}}{\delta \sigma ^2}}\right)\right](0.74+0.25)\delta <\delta `$
To derive the lemma as stated, we note

$$\frac{(1+\sqrt{2\mathrm{ln}(4e/\delta )})1100n^2d^{1.5}}{\delta \sigma ^2}\mathrm{log}^{1.5}\left(\frac{365n^2d^{1.5}}{\delta \sigma ^2}\right)\frac{2^{12}n^2d^{1.5}}{\delta \sigma ^2}\mathrm{log}^2\left(\frac{2^9n^2d^{1.5}}{\delta \sigma ^2}\right).$$

### 2.5 Log of the Primal Condition Number

In this section, we prove we prove Lemma 2.1.5.

###### Proof of Lemma 2.1.5.

First notice that

$`\text{E}\left[\mathrm{log}{\displaystyle \frac{A_F}{\rho (A,𝑪)}}\right]=\text{E}\left[\mathrm{log}A_F+\mathrm{log}{\displaystyle \frac{1}{\rho (A,𝑪)}}\right].`$
We first focus on $`\text{E}\left[\mathrm{log}A_F\right]`$. Because logarithm is a convex function, we have

$$\text{E}\left[\mathrm{log}A_F\right]\mathrm{log}(\text{E}\left[A_F\right])\mathrm{log}\sqrt{\text{E}\left[A_F^2\right]}.$$

As $`A_F^2`$ is a $`dn`$-dimensional non-central $`\chi ^2`$ random variable with non-centrality parameter $`\overline{A}_F`$, its expectation is $`nd+\overline{A}_F`$ \[AS70, 26.4.37\]. Therefore,

$$\text{E}\left[\mathrm{log}A_F\right]\mathrm{log}\sqrt{nd+1}.$$

We will use the following simple fact which is easy to verify numerically:

###### Fact 2.5.1.

For all $`\alpha 100`$ and $`x2\mathrm{log}\alpha `$, $`x1.5\mathrm{log}xx/2`$.

Let

$$\alpha =\frac{365n^2d^{1.5}}{\sigma ^2},$$

as before. By Equation (14) in the proof of Lemma 2.1.4,

$$\text{Pr}\left[\frac{1}{\rho (A,𝑪)}x\right]\frac{\alpha \mathrm{log}^{1.5}x}{x}.$$

Therefore,

$`\text{E}\left[\mathrm{log}{\displaystyle \frac{1}{\rho (A,𝑪)}}\right]`$ $`=`$ $`{\displaystyle _0^{\mathrm{}}}\text{Pr}\left[\mathrm{log}{\displaystyle \frac{1}{\rho (A,𝑪)}}>x\right]𝑑x`$
$`=`$ $`{\displaystyle _0^{\mathrm{}}}\text{Pr}\left[{\displaystyle \frac{1}{\rho (A,𝑪)}}>e^x\right]𝑑x`$
$``$ $`{\displaystyle _0^{\mathrm{}}}\mathrm{min}(1,{\displaystyle \frac{\alpha x^{1.5}}{e^x}})𝑑x`$
$``$ $`{\displaystyle _0^{2\mathrm{log}\alpha }}𝑑x+{\displaystyle _{2\mathrm{log}\alpha }^{\mathrm{}}}{\displaystyle \frac{\alpha x^{1.5}}{e^x}}𝑑x`$
$`=`$ $`2\mathrm{log}\alpha +\alpha {\displaystyle _{2\mathrm{log}\alpha }^{\mathrm{}}}e^{x+1.5\mathrm{log}x}𝑑x`$
$``$ $`2\mathrm{log}\alpha +\alpha {\displaystyle _{2\mathrm{log}\alpha }^{\mathrm{}}}e^{x/2}𝑑x`$
$``$ $`2\mathrm{log}\alpha +2,`$
where the second-to-last inequality follows from Fact 2.5.1.

Thus,

$`\text{E}\left[\mathrm{log}{\displaystyle \frac{A_F}{\rho (A,𝑪)}}\right]`$ $`=`$ $`\text{E}\left[\mathrm{log}A_F+\mathrm{log}{\displaystyle \frac{1}{\rho (A,𝑪)}}\right]\mathrm{log}\sqrt{nd+1}+2\mathrm{log}\alpha +2`$
$``$ $`14+4.5\mathrm{log}{\displaystyle \frac{nd}{\sigma }}.`$
## 3 Dual Condition Number

In this section, we consider linear programs of the form

$$A^T𝒚=𝒄,𝒚\mathrm{𝟎}.$$

The dual program of form (1) and the primal program of form (3) are both of this type. The dual program of form (4) can be handled using a slightly different argument than the one we present. As in section 2, we omit the details of the modifications necessary for form (4). We begin by defining distance to ill-posedness appropriately for the form of linear program considered in this section:

###### Definition 3.0.1 (Dual distance to ill-posedness).

For a matrix, $`A`$, and a vector $`𝐜`$, we define $`\rho (A,𝐜)`$ by

* if $`A^T𝒚=𝒄,𝒚\mathrm{𝟎}`$ is feasible, then $`\rho (A,𝒄)=`$

$`sup\{ϵ:\mathrm{\Delta }A_F+\mathrm{\Delta }𝒄_F<ϵ\text{ implies }(A+\mathrm{\Delta }A)^T𝒚=𝒄+\mathrm{\Delta }𝒄,𝒚\mathrm{𝟎}\text{ is feasible}\}`$
* if $`A^T𝒚=𝒄,𝒚\mathrm{𝟎}`$ is infeasible, then $`\rho (A,𝒄)=`$

$`sup\{ϵ:\mathrm{\Delta }A_F+\mathrm{\Delta }𝒄_F<ϵ\text{ implies }(A+\mathrm{\Delta }A)^T𝒚=𝒄+\mathrm{\Delta }𝒄,𝒚\mathrm{𝟎}\text{ is infeasible}\}`$

The main result of this section is:

###### Lemma 3.0.2 (Dual condition number is likely low).

Let $`\overline{A}`$ be an $`n`$-by-$`d`$ matrix and $`𝐜`$ be a vector in $`\mathrm{IR}^d`$ such that $`\overline{A}_F1`$ and $`\overline{𝐜}1`$. Then for any $`\sigma 1/\sqrt{nd}`$,

$`\text{Pr}_{(A,𝒄)𝒩((\overline{A},\overline{𝒄}),\sigma )}\left[{\displaystyle \frac{A,𝒄_F}{\rho (A,𝒄)}}>{\displaystyle \frac{50000d^{1/4}n^{1/2}}{ϵ\sigma ^2}}\mathrm{log}^2\left({\displaystyle \frac{200d^{1/4}n^{1/2}}{ϵ\sigma ^2}}\right)\right]`$ $``$ $`ϵ.`$
In addition,

$`\text{E}_{(A,𝒄)𝒩((\overline{A},\overline{𝒄}),\sigma )}\left[\mathrm{log}{\displaystyle \frac{A,𝒄_F}{\rho (A,𝒄)}}\right]14+4\mathrm{log}{\displaystyle \frac{nd}{\sigma }}.`$
We begin by giving several common definitions that will be useful in our analysis of the dual condition number (Section 3.1). We define a change of variables (Section 3.2), and we then develop a sufficient geometric condition for the dual condition number to be low (Section 3.3). In Section 3.4, we use Lemma 3.2.3 to prove Lemma 3.0.2, thereby establishing that this geometric condition is met with good probability.

### 3.1 Geometric Basics

###### Definition 3.1.1 (Cone).

For a set of vectors $`𝐚_1,\mathrm{},𝐚_n`$, let $`\text{Cone}(𝐚_1,\mathrm{},𝐚_n)`$ denote
$`\{𝐱:𝐱=_i\lambda _i𝐚_i,\lambda _i0\}.`$

###### Definition 3.1.2 (Hull).

For a set of vectors $`𝐚_1,\mathrm{},𝐚_n`$, let $`\text{Hull}(𝐚_1,\mathrm{},𝐚_n)`$ denote
$`\{𝐱:𝐱=_i\lambda _i𝐚_i,\lambda _i0,_i\lambda _i=1\}.`$

###### Definition 3.1.3 (Boundary of a set).

For a convex set $`\mathrm{SS}`$, let $`\text{bdry}(\mathrm{SS})`$ denote the boundary of $`\mathrm{SS}`$, i.e., $`\{𝐱:ϵ>0,𝐞,𝐞ϵ,s.t.𝐱+𝐞\mathrm{SS},𝐱𝐞\mathrm{SS}\}.`$

###### Definition 3.1.4 (Point-to-set distance).

Let $`\text{dist}(𝐱,\mathrm{SS})`$ denote the distance of $`𝐱`$ to $`\mathrm{SS}`$, i.e.,
$`\mathrm{min}\{ϵ:𝐞,𝐞ϵ,s.t.𝐱+𝐞\mathrm{SS}\}.`$

Note that $`\text{Cone}(𝒂_1,\mathrm{},𝒂_n)`$ is *not* a non-pointed convex cone, while $`\text{Hull}(𝒂_1,\mathrm{},𝒂_n)`$ is the standard convex hull of $`\{𝒂_1,\mathrm{},𝒂_n\}`$.

### 3.2 Change of variables

We observe that there exists a solution to the system $`A^T𝒚=𝒄,𝒚\mathrm{𝟎}`$ if and only if

$$𝒄\text{Cone}(𝒂_1,\mathrm{},𝒂_n),$$

and that for $`𝒄\mathrm{𝟎},`$ this holds if and only if

$$\text{Ray}\left(𝒄\right)\text{ intersects }\text{Hull}(𝒂_1,\mathrm{},𝒂_n).$$

In this Section, we need one technique beyond those used in Section 2—a change of variables. We set

$`𝒛`$ $`=`$ $`(1/n){\displaystyle \underset{i=1}{\overset{n}{}}}𝒂_i,\text{ and}`$
$`𝒙_i`$ $`=`$ $`𝒂_i𝒛,\text{ for }i=1\text{ to }n1.`$
For notational convenience, we let $`𝒙_n=𝒂_n𝒛`$, although $`𝒙_n`$ is not independent of $`\{𝒛,𝒙_1,\mathrm{},𝒙_{n1}\}`$.

We can restate the condition for the linear program to be ill-posed in these new variables:

###### Lemma 3.2.1 (Ill-posedness in new variables).

$$A^T𝒚=𝒄,𝒚\mathrm{𝟎},𝒄\mathrm{𝟎}\text{ is ill-posed if and only if }𝒛\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)).$$

###### Proof.

We observe

$`A^T𝒚=𝒄,𝒚\mathrm{𝟎}\text{ is feasible}`$ $``$ $`\text{Ray}\left(𝒄\right)\text{ intersects }\text{Hull}(𝒂_1,\mathrm{},𝒂_n)`$
$``$ $`\text{Ray}\left(𝒄\right)\text{ intersects }𝒛+\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$
$``$ $`𝒛\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n).`$
For $`𝒄\mathrm{𝟎}`$, $`\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$ is a continuous mapping from $`𝒄,𝒙_1,\mathrm{},𝒙_n`$ to subsets of Euclidean space, and so for $`𝒛`$ in the set and not on the boundary, a sufficiently small change to all the variables simultaneously will always leave $`𝒛`$ in the set, and similarly for $`𝒛`$ not in the set and not on the boundary.

To establish the other direction, we observe that if $`𝒛`$ is on the boundary, then can perturb $`𝒛`$ to bring it in or out of the set. Although $`𝒛,𝒙_1,\mathrm{},𝒙_n`$ are determined by the $`𝒂_1,\mathrm{},𝒂_n`$, we can perturb the $`𝒂_1,\mathrm{},𝒂_n`$ so as to change the value of $`𝒛`$ without changing the values of any of the $`𝒙_1,\mathrm{},𝒙_n`$. This can be done because each $`𝒙_i`$ is a relative offset from the average $`𝒛`$, while each $`𝒂_i`$ is an absolute offset from the origin; the proof of lemma 3.2.2 below establishes formally that the change of variables permits this.

The lemma is also true for $`𝒄=\mathrm{𝟎}`$, but we will not need this fact. ∎

Note that $`\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$ is a convex set. The following lemma will allow us to apply lemma 2.1.7 to determine the probability that $`𝒛`$ is near the boundary of this convex set.

###### Lemma 3.2.2 (Independence of mean among new variables).

Let $`\overline{𝐚}_1,\mathrm{},\overline{𝐚}_n`$ be $`n`$ vectors in $`\mathrm{IR}^d`$. Let $`𝐚_1,\mathrm{},𝐚_n`$ be a Gaussian perturbation of $`\overline{𝐚}_1,\mathrm{},\overline{𝐚}_n`$ of variance $`\sigma ^2`$. Let

$$𝒛=\frac{1}{n}\underset{i}{}𝒂_i\text{ and }𝒙_i=𝒂_i𝒛,\text{ for }1in.$$

Then, $`𝐳`$ is a Gaussian perturbation of

$$\overline{𝒛}=\frac{1}{n}\underset{i}{}\overline{𝒂}_i,$$

of variance $`\sigma ^2/n`$ and is independent of $`𝐱_1,\mathrm{},𝐱_n`$.

###### Proof.

As $`𝒛`$ is the average of Gaussian perturbations of variance $`\sigma ^2`$ of $`n`$ vectors $`\overline{𝒂}_1,\mathrm{},\overline{𝒂}_n`$, it is a Gaussian perturbation of variance $`\sigma ^2/n`$ of the average of these $`n`$ vectors, that is, of

$$\overline{𝒛}=\frac{1}{n}\underset{i}{}\overline{𝒂}_i.$$

The vector $`𝒛`$ is independent of $`𝒙_1,\mathrm{},𝒙_n`$ because the linear combination of $`𝒂_1,\mathrm{},𝒂_n`$ used to obtain $`𝒛`$ is orthogonal to the linear combinations of $`𝒂_1,\mathrm{},𝒂_n`$ used to obtain the $`𝒙_i`$s. ∎

###### Lemma 3.2.3 (Mean is likely far from ill-posedness).

Let $`\overline{𝐚}_1,\mathrm{},\overline{𝐚}_n`$ be $`n`$ vectors in $`\mathrm{IR}^d`$ and $`\overline{𝐜}`$ be a vector in $`\mathrm{IR}^d`$. Let $`𝐚_1,\mathrm{},𝐚_n`$ be a Gaussian perturbation of $`\overline{𝐚}_1,\mathrm{},\overline{𝐚}_n`$ of variance $`\sigma ^2`$ and let $`𝐜`$ be a Gaussian perturbation of $`\overline{𝐜}`$ of variance $`\sigma ^2`$. Let

$$𝒛=\frac{1}{n}\underset{i}{}𝒂_i\text{ and }𝒙_i=𝒂_i𝒛,\text{ for }1in.$$

Then, for all $`𝐜`$ and $`𝐱_1,\mathrm{},𝐱_n`$,

$$\text{Pr}_𝒛\left[\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))ϵ\right]\frac{8ϵd^{1/4}n^{1/2}}{\sigma }.$$

###### Proof.

Let $`𝒄`$ be arbitrary. By Lemma 3.2.2, we can choose $`𝒙_1,\mathrm{},𝒙_n`$ and then choose $`𝒛`$ independently. Having chosen $`𝒙_1,\mathrm{},𝒙_n`$, we fix the convex body $`\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$ and apply Lemma 2.1.7 twice: once for the inside $`ϵ`$-boundary, and once for the outside $`ϵ`$-boundary. ∎

### 3.3 A geometric characterization of dual condition number

We now give a geometric characterization of the dual condition number that uses both the original and the new variables. In the next section, we will use this characterization to prove Lemma 3.0.2.

###### Lemma 3.3.1 (Reciprocal of distance to ill-posedness).

Let $`𝐜`$ and $`𝐚_1,\mathrm{},𝐚_n`$ be vectors in $`\mathrm{IR}^d`$. Let

$$𝒛=\frac{1}{n}\underset{i}{}𝒂_i\text{ and }𝒙_i=𝒂_i𝒛,\text{ for }1in.$$

$$k_1=\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))$$

$$k_2=𝒄$$

Then

$$\frac{1}{\rho (A,𝒄)}\mathrm{max}\{\frac{8}{k_1},\frac{4}{k_2},\frac{24\mathrm{max}_i𝒂_i}{k_1k_2}\}.$$

###### Proof.

By the definition of $`k_1`$ and $`k_2`$ and Lemma 3.3.2, we can tolerate any change of magnitude up to $`k_1/4`$ in $`𝒛`$, and $`𝒙_1,\mathrm{},𝒙_n`$, and any change of up to $`\frac{k_1k_2}{2k_1+4(𝒛+\mathrm{max}𝒙_i)}`$ in $`𝒄`$ without the program becoming ill-posed. We show that this means we can tolerate any change of up to $`k_1/8`$ in $`𝒂_i`$ without the program becoming ill-posed. Formally, we need to show that if $`\mathrm{\Delta }𝒂_ik_1/8`$ for all $`i`$, then $`\mathrm{\Delta }𝒛k_1/4`$ and $`\mathrm{\Delta }𝒙_ik_1/4`$. Since $`\mathrm{\Delta }𝒛=(1/n)\mathrm{\Delta }𝒂_i`$, $`\mathrm{\Delta }𝒛k_1/8`$. Since $`\mathrm{\Delta }𝒙_i=\mathrm{\Delta }𝒂_i\mathrm{\Delta }𝒛`$, $`\mathrm{\Delta }𝒙_ik_1/8+k_1/8=k_1/4`$. Thus

$$\rho (A,𝒄)\mathrm{min}\{\frac{k_1}{8},\frac{k_1k_2}{2k_1+4(𝒛+\mathrm{max}𝒙_i)}\}$$

which implies

$$\frac{1}{\rho (A,𝒄)}\mathrm{max}\{\frac{8}{k_1},\frac{4}{k_2},\frac{8(𝒛+\mathrm{max}𝒙_i)}{k_1k_2}\},$$

as

$$\frac{2k_1+4(𝒛+\mathrm{max}𝒙_i)}{k_1k_2}\{\begin{array}{cc}\frac{4}{k_2}\hfill & \text{ if }k_14(𝒛+\mathrm{max}𝒙_i)\text{, and}\hfill \\ \frac{8(𝒛+\mathrm{max}𝒙_i)}{k_1k_2}\hfill & \text{otherwise}.\hfill \end{array}$$

Since $`𝒛=(1/n)𝒂_i`$ implies $`𝒛\mathrm{max}𝒂_i`$, and $`𝒙_i=𝒂_i𝒛`$ implies $`𝒙_i𝒂_i+𝒛2\mathrm{max}𝒂_i`$, we have

$$\frac{1}{\rho (A,𝒄)}\mathrm{max}\{\frac{8}{k_1},\frac{4}{k_2},\frac{24\mathrm{max}𝒂_i}{k_1k_2}\}.$$

###### Lemma 3.3.2.

(Geometric condition to be far from ill-posedness in new variables.) If

$`\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))>\alpha `$ (16)
and

$`\mathrm{\Delta }𝒙_i`$ $``$ $`\alpha /4,`$
$`\mathrm{\Delta }𝒛`$ $``$ $`\alpha /4,`$
$`\mathrm{\Delta }𝒄`$ $``$ $`{\displaystyle \frac{\alpha 𝒄}{2\alpha +4(𝒛+\mathrm{max}_i𝒙_i)}},`$
then

$$𝒛+\mathrm{\Delta }𝒛\text{bdry}(\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n))$$

###### Proof.

Assume by way of contradiction that

$$𝒛+\mathrm{\Delta }𝒛\text{bdry}(\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n)).$$

We first consider the case that $`𝒛\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$. In this case, we will show that $`\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))\alpha `$, contradicting assumption (16). Since $`𝒛+\mathrm{\Delta }𝒛\text{bdry}(\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n))`$,

$$𝒛+\mathrm{\Delta }𝒛=\lambda (𝒄+\mathrm{\Delta }𝒄)\underset{i}{}\gamma _i(𝒙_i+\mathrm{\Delta }𝒙_i),$$

for some $`\lambda 0`$ and $`\gamma _1,\mathrm{},\gamma _n0,_i\gamma _i=1`$. We establish an upper bound on $`\lambda `$ by noting that

$$\lambda =\frac{𝒛+\mathrm{\Delta }𝒛+_i\gamma _i(𝒙_i+\mathrm{\Delta }𝒙_i)}{𝒄+\mathrm{\Delta }𝒄}.$$
(17)
We lower bound the denominator of (17) by $`𝒄/2`$ by

$$\mathrm{\Delta }𝒄\frac{\alpha 𝒄}{2\alpha +4(𝒛+\mathrm{max}_i𝒙_i)}𝒄/2.$$

We upper bound the numerator of (17) by

$`𝒛+\mathrm{\Delta }𝒛+{\displaystyle \underset{i}{}}\gamma _i(𝒙_i+\mathrm{\Delta }𝒙_i)`$ $``$ $`𝒛+\alpha /4+{\displaystyle \underset{i}{}}\gamma _i(𝒙_i+\mathrm{\Delta }𝒙_i)`$
$``$ $`𝒛+\alpha /4+\underset{i}{\mathrm{max}}𝒙_i+\alpha /4`$
$`=`$ $`𝒛+\underset{i}{\mathrm{max}}𝒙_i+\alpha /2.`$
Thus,

$$\lambda \frac{𝒛+\mathrm{max}_i𝒙_i+\alpha /2}{𝒄/2}$$

Since

$$\left(𝒛+\mathrm{\Delta }𝒛\lambda \mathrm{\Delta }𝒄+\underset{i}{}\gamma _i\mathrm{\Delta }𝒙_i\right)=\left(\lambda 𝒄\underset{i}{}\gamma _i𝒙_i\right)\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n),$$

we find that

$`\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))`$
$``$ $`\mathrm{\Delta }𝒛\lambda \mathrm{\Delta }𝒄+{\displaystyle \underset{i}{}}\gamma _i\mathrm{\Delta }𝒙_i`$
$``$ $`\mathrm{\Delta }𝒛+\lambda \mathrm{\Delta }𝒄+{\displaystyle \underset{i}{}}\gamma _i\mathrm{\Delta }𝒙_i`$
$``$ $`{\displaystyle \frac{\alpha }{4}}+\left({\displaystyle \frac{𝒛+\mathrm{max}_i𝒙_i+\alpha /2}{𝒄/2}}\right)\left({\displaystyle \frac{\alpha 𝒄}{2\alpha +4(𝒛+\mathrm{max}_i𝒙_i)}}\right)+{\displaystyle \frac{\alpha }{4}}`$
$`=`$ $`\alpha ,`$
contradicting assumption (16).

We now consider the case that $`𝒛\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$. Since

$$𝒛+\mathrm{\Delta }𝒛\text{bdry}(\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n)),$$

there exists a hyperplane $`H`$ passing through $`𝒛+\mathrm{\Delta }𝒛`$ and tangent to the convex set
$`\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n)`$. By the assumption that
$`\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))>\alpha `$, there is some $`\delta _0>0`$ such that, for every $`\delta (0,\delta _0)`$, every point within $`\alpha +\delta `$ of $`𝒛`$ lies within $`\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$. Choose $`\delta (0,\delta _0)`$ that also satisfies $`\delta 𝒛+\mathrm{max}_i𝒙_i`$. Let $`𝒒`$ be a point at distance $`\frac{3\alpha }{4}+\delta `$ from $`𝒛+\mathrm{\Delta }𝒛`$ in the direction perpendicular to $`H`$. Since $`\text{dist}(𝒛,𝒛+\mathrm{\Delta }𝒛)\frac{\alpha }{4}`$, and $`\text{dist}(𝒛+\mathrm{\Delta }𝒛,𝒒)=\frac{3\alpha }{4}+\delta `$,

$$𝒒\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)$$

At the same time,

$$\text{dist}(𝒒,\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n))>\frac{3\alpha }{4}.$$
(18)
Because $`𝒒\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)`$, there exist $`\lambda 0`$ and $`\gamma _1,\mathrm{},\gamma _n0,_i\gamma _i=1`$ such that

$$𝒒=\lambda 𝒄\underset{i}{}\gamma _i𝒙_i.$$

We upper bound $`\lambda `$ as before,

$$\lambda =\frac{𝒒+_i\gamma _i𝒙_i}{𝒄}\frac{𝒛+\alpha +\delta +\mathrm{max}_i𝒙_i}{𝒄}\frac{𝒛+\mathrm{max}_i𝒙_i+\alpha /2}{𝒄/2}$$

Hence,

$$𝒒+\lambda \mathrm{\Delta }𝒄\underset{i}{}\gamma _i\mathrm{\Delta }𝒙_i=\lambda (𝒄+\mathrm{\Delta }𝒄)\underset{i}{}\gamma _i(𝒙_i+\mathrm{\Delta }𝒙_i)$$

$$\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n),$$

and thus

$`\text{dist}(𝒒,\text{Ray}\left(𝒄+\mathrm{\Delta }𝒄\right)\text{Hull}(𝒙_1+\mathrm{\Delta }𝒙_1,\mathrm{},𝒙_n+\mathrm{\Delta }𝒙_n))`$ $``$ $`\lambda \mathrm{\Delta }𝒄{\displaystyle \underset{i}{}}\gamma _i\mathrm{\Delta }𝒙_i`$
$``$ $`\lambda \mathrm{\Delta }𝒄+\underset{i}{\mathrm{max}}\mathrm{\Delta }𝒙_i`$
$``$ $`\alpha /2+\alpha /4`$
$``$ $`3\alpha /4,`$
which contradicts (18). ∎

### 3.4 Dual condition number is likely low

###### Proof of Lemma 3.0.2.

Let

$$𝒛=\frac{1}{n}\underset{i}{}𝒂_i\text{ and }𝒙_i=𝒂_i𝒛,\text{ for }1in,$$

$$k_1=\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))\text{ and }k_2=𝒄.$$

We will apply the bound of Lemma 3.3.1. We first lower bound $`\mathrm{min}\{k_1,k_2,k_1k_2\}`$. We begin by observing that if

$$\mathrm{min}\{k_1,k_2,k_1k_2\}<ϵ,$$

then either

$`\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))<ϵ,`$ (19)
or

$`𝒄<ϵ,`$ (20)
or there exists some integer $`l`$, $`1l\mathrm{log}\frac{1}{ϵ}`$, for which

$`\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))<2^lϵ\text{ and }𝒄2^{l+1}.`$ (21)
The probabilities of events (19) and (20) will also be bounded in our analysis of event (21). By Proposition A.0.4, for $`d2`$, we have

$$\text{Pr}\left[𝒄ϵ\right]\frac{eϵ}{\sigma },$$

which translates to

$$\text{Pr}\left[𝒄2^{l+1}\right]\frac{e2^{l+1}}{\sigma },$$

while Lemma 3.2.3 implies

$$\text{Pr}_𝒛\left[\text{dist}(𝒛,\text{bdry}(\text{Ray}\left(𝒄\right)\text{Hull}(𝒙_1,\mathrm{},𝒙_n)))<2^lϵ\right]\frac{82^lϵd^{1/4}n^{1/2}}{\sigma }.$$

Thus, we compute

$`\text{Pr}\left[\mathrm{min}\{k_1,k_2,k_1k_2\}<ϵ\right]`$ $``$ $`{\displaystyle \frac{8ϵd^{1/4}n^{1/2}}{\sigma }}+{\displaystyle \frac{eϵ}{\sigma }}+{\displaystyle \underset{l=1}{\overset{\mathrm{log}\frac{1}{ϵ}}{}}}{\displaystyle \frac{e2^{l+1}}{\sigma }}{\displaystyle \frac{82^lϵd^{1/4}n^{1/2}}{\sigma }}`$
$`=`$ $`{\displaystyle \frac{8ϵd^{1/4}n^{1/2}}{\sigma }}+{\displaystyle \frac{eϵ}{\sigma }}+{\displaystyle \frac{16eϵd^{1/4}n^{1/2}}{\sigma ^2}}\mathrm{log}\left({\displaystyle \frac{1}{ϵ}}\right)`$
$``$ $`{\displaystyle \frac{55ϵd^{1/4}n^{1/2}}{\sigma ^2}}\mathrm{log}\left({\displaystyle \frac{1}{ϵ}}\right).`$
Setting

$$ϵ=\frac{\delta }{200d^{1/4}n^{1/2}\mathrm{log}\left(\frac{200d^{1/4}n^{1/2}}{\sigma ^2\delta }\right)/\sigma ^2},$$

we find that

$$\frac{55ϵd^{1/4}n^{1/2}}{\sigma ^2}\mathrm{log}\left(\frac{1}{ϵ}\right)\delta /2,$$

for $`\delta 1`$. So, we obtain

$$\text{Pr}\left[\mathrm{min}\{k_1,k_2,k_1k_2\}<\frac{\delta }{200d^{1/4}n^{1/2}\mathrm{log}\left(\frac{200d^{1/4}n^{1/2}}{\sigma ^2\delta }\right)/\sigma ^2}\right]<\delta /2,$$

which we re-write this as

$`\text{Pr}\left[\mathrm{max}\{{\displaystyle \frac{1}{k_1}},{\displaystyle \frac{1}{k_2}},{\displaystyle \frac{1}{k_1k_2}}\}>{\displaystyle \frac{200d^{1/4}n^{1/2}}{\delta \sigma ^2}}\mathrm{log}\left({\displaystyle \frac{200d^{1/4}n^{1/2}}{\delta \sigma ^2}}\right)\right]<{\displaystyle \frac{\delta }{2}}.`$ (22)
By Lemma 3.3.1, we have

$`{\displaystyle \frac{1}{\rho (A,𝒄)}}`$ $``$ $`\mathrm{max}\{{\displaystyle \frac{8}{k_1}},{\displaystyle \frac{4}{k_2}},{\displaystyle \frac{24\mathrm{max}_i𝒂_i}{k_1k_2}}\}`$
$``$ $`24\mathrm{max}(\underset{i}{\mathrm{max}}𝒂_i,1)\mathrm{max}\{{\displaystyle \frac{1}{k_1}},{\displaystyle \frac{1}{k_2}},{\displaystyle \frac{1}{k_1k_2}}\}.`$
By Corollary A.0.3, we have

$`\text{Pr}[\mathrm{max}(A,𝒄_F,1)>3+\sigma \sqrt{(d+1)n2\mathrm{ln}(4e/\delta )}]<{\displaystyle \frac{\delta }{4}},`$ (23)
and $`\mathrm{max}(A,𝒄_F,1)\mathrm{max}(\mathrm{max}_i𝒂_i,1)`$.

From a union bound of inequalities 22 and 23, we obtain

$`\text{Pr}\left[{\displaystyle \frac{A,𝒄_F}{\rho (A,𝒄)}}>{\displaystyle \frac{24200d^{1/4}n^{1/2}}{\delta \sigma ^2}}\mathrm{log}\left({\displaystyle \frac{200d^{1/4}n^{1/2}}{\delta \sigma ^2}}\right)(3+\sigma \sqrt{(d+1)n2\mathrm{ln}(2e/\delta )})^2\right]`$ $``$ $`\delta .`$
The proof of the first part of the lemma now follows by computing

$$\frac{24200d^{1/4}n^{1/2}}{\delta \sigma ^2}\mathrm{log}\left(\frac{200d^{1/4}n^{1/2}}{\delta \sigma ^2}\right)(3+\sigma \sqrt{(d+1)n2\mathrm{ln}(2e/\delta )})^2$$

$$\frac{50000d^{1/4}n^{1/2}}{\delta \sigma ^2}\mathrm{log}^2\left(\frac{200d^{1/4}n^{1/2}}{\delta \sigma ^2}\right),$$

where we used the assumption $`\sigma 1/\sqrt{dn}`$.

We now establish the smoothed bound on the log of expectation. Note that

$`\text{E}\left[\mathrm{log}{\displaystyle \frac{A,𝒄_F}{\rho (A,𝒄)}}\right]`$ $`=`$ $`\text{E}[\mathrm{log}A,𝒄_F]+\text{E}\left[\mathrm{log}{\displaystyle \frac{1}{\rho (A,𝒄)}}\right]`$
$``$ $`\text{E}[\mathrm{log}A,𝒄_F]+\text{E}\left[\mathrm{log}\mathrm{max}\{{\displaystyle \frac{1}{k_1}},{\displaystyle \frac{1}{k_2}},{\displaystyle \frac{1}{k_1k_2}}\}\right]+\text{E}\left[\mathrm{log}(24\mathrm{max}(\underset{i}{\mathrm{max}}𝒂_i,1))\right]`$
$``$ $`\text{E}\left[\mathrm{log}\mathrm{max}(A,𝒄_F,1)\right]+\text{E}\left[\mathrm{log}\mathrm{max}\{{\displaystyle \frac{1}{k_1}},{\displaystyle \frac{1}{k_2}},{\displaystyle \frac{1}{k_1k_2}}\}\right]+\text{E}\left[24\mathrm{log}\mathrm{max}(A_F,1)\right]`$
$``$ $`\mathrm{log}\sqrt{n(d+1)+1}+2\mathrm{log}{\displaystyle \frac{55d^{1/4}n^{1/2}}{\sigma ^2}}+2+\mathrm{log}24+\mathrm{log}\sqrt{nd+1}`$
$``$ $`14+4\mathrm{log}{\displaystyle \frac{nd}{\sigma }},`$
where the bound is derived using the same argument as in the proof of Lemma 2.1.5.

## 4 Combining the Primal and Dual Analyses

###### Proof-of-theorem 1.3.1.

Note that the transformation of each canonical form into the conic form leaves the Frobenius norm unchanged. Also, a random Gaussian perturbation in the original form maps to a random Gaussian perturbation in the conic form. Therefore, by Lemma 2.1.2, the smoothed bounds on the primal and dual condition numbers of the conic forms imply smoothed bounds on each of the condition numbers $`C_P^{(1)}`$, $`C_P^{(2)}`$, $`C_D^{(2)}`$, $`C_D^{(3)}`$.

By Lemmas 2.1.4 and Lemma 3.0.2, we have that for all $`\overline{A}`$, $`\overline{𝒃}`$ and $`\overline{𝒄}`$ satisfying $`\overline{A},\overline{𝒃},\overline{𝒄}_F1`$ and $`\sigma 1/\sqrt{nd}`$,

$`\text{Pr}_{A,𝒃,𝒄}\left[C^{(i)}(A,𝒃,𝒄)>{\displaystyle \frac{2^{13}(n+1)^2(d+1)^{1.5}}{\delta \sigma ^2}}\left(\mathrm{log}{\displaystyle \frac{2^{10}(n+1)^2(d+1)^{1.5}}{\delta \sigma ^2}}\right)^2\right]`$
$`\text{Pr}_{A,𝒃,𝒄}\left[C_P^{(i)}(A,𝒃)>{\displaystyle \frac{2^{12}n^2(d+1)^{1.5}}{(\delta /2)\sigma ^2}}\left(\mathrm{log}{\displaystyle \frac{2^9n^2(d+1)^{1.5}}{(\delta /2)\sigma ^2}}\right)^2\right]`$
$`+\text{Pr}_{A,𝒃,𝒄}\left[C_D^{(i)}(A,𝒄)>{\displaystyle \frac{2^{12}(n+1)^2d^{1.5}}{(\delta /2)\sigma ^2}}\left(\mathrm{log}{\displaystyle \frac{2^9(n+1)^2d^{1.5}}{(\delta /2)\sigma ^2}}\right)^2\right]`$
$`\delta /2+\delta /2=\delta .`$
To bound the log of the condition number, we use Lemmas 2.1.5 and Lemma 3.0.2 to show

$`\text{E}_{A,𝒃,𝒄}\left[\mathrm{log}C^{(i)}(A,𝒃,𝒄)\right]`$
$`\text{E}_{A,𝒃,𝒄}\left[\mathrm{log}\left(C_P^{(i)}(A,𝒃)+C_D^{(i)}(A,𝒄)\right)\right]`$
$`\mathrm{max}(\text{E}_{A,𝒃,𝒄}\left[\mathrm{log}\left(2C_P^{(i)}(A,𝒃)\right)\right],\text{E}_{A,𝒃,𝒄}\left[\mathrm{log}\left(2C_D^{(i)}(A,𝒄)\right)\right])`$
$`15+4.5\mathrm{log}\left({\displaystyle \frac{nd}{\sigma }}\right),`$
where in the second-to-last inequality used that fact that for positive random variables $`\beta `$ and $`\gamma `$,

$$\text{E}\left[\mathrm{log}(\beta +\gamma )\right]\mathrm{max}(\text{E}\left[\mathrm{log}(2\beta )\right],\text{E}\left[\mathrm{log}(2\gamma )\right]).$$

## 5 Open Problems and Conclusion

The best way to strengthen the results in this paper would be to prove that they hold under more restrictive models of perturbation. For example, we ask whether similar results can be proved if one perturbs the linear program subject to maintaining feasibility or infeasibility. This would be an example of a property-preserving perturbation, as defined in \[ST03a\].

A related question is whether these results can be proved under zero-preserving perturbations in which only non-zero entries of $`A`$ are subject to perturbations. Unfortunately, the following example shows that in this model of zero-preserving perturbations, it is not possible to bound the condition number by $`poly(n,d,\frac{1}{\sigma })`$ with probability at least $`1/2`$. Therefore, if such a result were to hold in the model of zero-preserving perturbations, it would not be because of a polynomial bound on the condition number.

Let $`A`$ be a zero preserving Gaussian perturbation of $`\overline{A}`$ with variance $`\sigma ^2`$. For ease of exposition, we will normalize $`\overline{A}_F`$ to be 1 at the end of formulation. Define the matrix

$$\overline{A}=\left[\begin{array}{cccc}1& ϵ& & \\ & 1& ϵ& \\ & & \mathrm{}\\ & & 1& ϵ\end{array}\right]$$

where $`ϵ`$ is a parameter to be chosen later, and consider the linear program $`A𝒙\mathrm{𝟎},𝒙𝑪`$ where $`𝑪=\{𝒙:𝒙>\mathrm{𝟎}\}`$. The $`i^{th}`$ constraint of $`\overline{A}𝒙\mathrm{𝟎}`$ is exactly

$$ϵx_{i+1}x_i$$

We apply fact A.0.2 with $`c=\delta ^2/\sigma ^2`$ assumed to be at least 6 (so that $`(1c+\mathrm{ln}c)c/2`$). This yields

$`\mathrm{Pr}[|a_{i,i}1|\delta ]e^{\frac{1}{2}(1\frac{\delta ^2}{\sigma ^2}+\mathrm{ln}\frac{\delta ^2}{\sigma ^2})}e^{\frac{\delta ^2}{4\sigma ^2}}`$ (24)
$`\mathrm{Pr}[|a_{i,i+1}ϵ|\delta ]e^{\frac{1}{2}(1\frac{\delta ^2}{\sigma ^2}+\mathrm{ln}\frac{\delta ^2}{\sigma ^2})}e^{\frac{\delta ^2}{4\sigma ^2}}`$ (25)
Setting $`\delta =\sigma \sqrt{8\mathrm{log}n}`$ yields that, with probability at least $`1/2`$, none of the events (24), (25) happen for any $`i`$. Assuming that none of the events (24), (25) occur, and that $`ϵ>\delta `$ (which we will ensure later), we have that $`A𝒙\mathrm{𝟎},𝒙𝑪`$ is feasible, and

$$𝒙=[\left(\frac{ϵ\delta }{1+\delta }\right)^n,\left(\frac{ϵ\delta }{1+\delta }\right)^{n1},\mathrm{},1]$$

is one such feasible solution. We also have that $`(ϵ+\delta )x_{i+1}(1\delta )x_i`$ for every $`i`$. Define

$$\mathrm{\Delta }A=\left[\begin{array}{cccc}0& \mathrm{}& 0& (\frac{ϵ+\delta }{1\delta })^{n2}\\ 0& \mathrm{}& 0& 0\\ & \mathrm{}\\ 0& \mathrm{}& 0& 0\end{array}\right].$$

We now show that $`(A+\mathrm{\Delta }A)𝒙\mathrm{𝟎},𝒙𝑪`$ is infeasible, and hence $`\rho (A,𝑪)\mathrm{\Delta }A_F=(\frac{ϵ+\delta }{1\delta })^{n2}`$. To see infeasibility, note that the constraint given by the top row of $`(A+\mathrm{\Delta }A)`$ is

$$x_1+ϵx_2\left(\frac{ϵ+\delta }{1\delta }\right)^{n2}x_n0$$

while we simultaneously have that $`x_2(\frac{ϵ+\delta }{1\delta })^{n2}x_n`$. Assuming $`ϵ1`$ (which we ensure later), this constraint is impossible to satisfy for $`𝒙𝑪`$.

Letting $`ϵ=\frac{1}{n}`$ and $`\sigma =\frac{1}{n^2}`$ (and hence $`\delta =\frac{\sqrt{8\mathrm{log}n}}{n^2}`$) yields $`\rho (A,𝑪)=(\frac{ϵ+\delta }{1\delta })^{n2}=(\frac{O(1)}{n})^{n2}`$, which is exponentially small and also satisfies the requirements on $`ϵ`$. We can upper bound $`A_F`$ by $`A_F\sqrt{n(1+\delta )^2+n(ϵ+\delta )^2}2\sqrt{n}`$. Thus the condition number, which is equal to $`A_F/\rho (A,𝑪)`$, is at least $`\mathrm{\Omega }(n)^{n3}`$.

If we had normalized $`\overline{A}_F=1`$ at the beginning of the proof, the corresponding normalization would have been $`ϵ\frac{1}{n\sqrt{n}}`$, $`\sigma \frac{1}{n^2\sqrt{n}}`$, which still shows the negative result. This analysis also shows the impossibility of a theorem like theorem 1.3.1 for another natural model of perturbation, relative perturbation, that is also zero-preserving: multiplying each entry of $`\overline{A}`$ by an $`N(1,\sigma ^2)`$ Gaussian random variable. This concludes our discussion of impossibility results for smoothed analysis.

We would like to point out that condition numbers appear throughout Numerical Analysis and that condition numbers may be defined for many non-linear problems. The speed of algorithms for optimizing linear functions over convex bodies (including semidefinite programming) has been related to their condition numbers \[Fre02, FV00\], and it seems that one might be able to extend our results to these algorithms as well. Condition numbers have also been defined for non-linear programming problems, and one could attempt to perform a smoothed analysis of non-linear optimization algorithms by relating their performance to the condition numbers of their inputs, and then performing a smoothed analysis of their condition numbers.

The approach of proving smoothed complexity bounds by relating the performance of an algorithm to some property of its input, such as a condition number, and the performing a smoothed analysis of this quantity has also been recently used in \[ST03a, SST02\]. Finally, we hope that this work illuminates some of the shared interests of the Numerical Analysis, Operations Research, and Theoretical Computer Science communities.

## Appendix A Gaussian random variables

We now derive particular versions of well-known bounds on the Chi-Squared distribution. These bounds are used in the body of the paper, and bounds of this form are well-known. We thank DasGupta and Gupta \[DG99\] for this particular derivation.

###### Fact A.0.1 (Sum of gaussians).

Let $`X_1,\mathrm{},X_d`$ be independent $`N(0,\sigma )`$ random variables. Then

$$\mathrm{Pr}[\underset{i=1}{\overset{d}{}}X_i^2\kappa ^2]e^{\frac{d}{2}(1\frac{\kappa ^2}{d\sigma ^2}+\mathrm{ln}\frac{\kappa ^2}{d\sigma ^2})}$$

###### Proof.

For simplicity, we begin with $`Y_iN(0,1)`$. A simple integration shows that if $`YN(0,1)`$ then $`E[e^{tY^2}]=\frac{1}{\sqrt{12t}}(t<\frac{1}{2})`$. We proceed with

$`\mathrm{Pr}[{\displaystyle \underset{i=1}{\overset{d}{}}}Y_i^2k]`$ $`=`$
$`\mathrm{Pr}[{\displaystyle \underset{i=1}{\overset{d}{}}}Y_i^2k0]`$ $`=`$ $`(\text{for }t>0)`$
$`\mathrm{Pr}[e^{t(_{i=1}^dY_i^2k)}1]`$ $``$ $`(\text{by Markov’s Ineq.})`$
$`\text{E}\left[e^{t(_{i=1}^dY_i^2k)}\right]`$ $`=`$
$`\left({\displaystyle \frac{1}{12t}}\right)^{d/2}e^{kt}`$ $``$ $`(\text{letting }t={\displaystyle \frac{1}{2}}{\displaystyle \frac{d}{2k}})`$
$`\left({\displaystyle \frac{k}{d}}\right)^{d/2}e^{\frac{k}{2}+\frac{d}{2}}`$ $`=`$ $`e^{\frac{d}{2}(1\frac{k}{d}+\mathrm{ln}\frac{k}{d})}`$
Since

$$\mathrm{Pr}[\underset{i=1}{\overset{d}{}}Y_i^2k]=\mathrm{Pr}[\underset{i=1}{\overset{d}{}}X_i^2\sigma ^2k]$$

we set $`k=\frac{\kappa ^2}{\sigma ^2}`$ and obtain $`e^{\frac{d}{2}(1\frac{k}{d}+\mathrm{ln}\frac{k}{d})}=e^{\frac{d}{2}(1\frac{\kappa ^2}{d\sigma ^2}+\mathrm{ln}\frac{\kappa ^2}{d\sigma ^2})}`$ which was our desired bound. ∎

In particular, this implies:

###### Fact A.0.2 (Alternative sum of gaussians).

Let $`X_1,\mathrm{},X_d`$ be independent $`N(0,\sigma )`$ random variables. Then for $`c1`$,

$$\mathrm{Pr}[\underset{i=1}{\overset{d}{}}X_i^2cd\sigma ^2]e^{\frac{d}{2}(1c+\mathrm{ln}c)}.$$

###### Corollary A.0.3.

Let $`𝐱`$ be a $`d`$-dimensional Gaussian random vector of variance $`\sigma ^2`$ centered at the origin. Then, for $`d2`$ and $`ϵ1/e^2`$,

$$\text{Pr}\left[𝒙\sigma \sqrt{d(1+2\mathrm{ln}(1/ϵ)}\right]ϵ$$

###### Proof.

Set $`c=1+2\mathrm{ln}(1/ϵ)`$ in fact A.0.2. We then compute

$$e^{\frac{d}{2}(1c+\mathrm{ln}c)}e^{1c+\mathrm{ln}c}e^{2\mathrm{ln}\frac{1}{ϵ}+\mathrm{ln}(1+2\mathrm{ln}\frac{1}{ϵ})}=ϵe^{\mathrm{ln}\frac{1}{ϵ}+\mathrm{ln}(1+2\mathrm{ln}\frac{1}{ϵ})}$$

We now seek to show

$`e^{\mathrm{ln}\frac{1}{ϵ}+\mathrm{ln}(1+2\mathrm{ln}\frac{1}{ϵ})}`$ $``$ $`1`$
$`\mathrm{ln}{\displaystyle \frac{1}{ϵ}}+\mathrm{ln}(1+2\mathrm{ln}{\displaystyle \frac{1}{ϵ}})`$ $``$ $`0`$
$`1+2\mathrm{ln}{\displaystyle \frac{1}{ϵ}}`$ $``$ $`{\displaystyle \frac{1}{ϵ}}`$
For $`ϵ=1/e^2`$, the left-hand side of the last inequality is 5, while the right-hand side is greater than 7. Taking derivatives with respect to $`1/ϵ`$, we see that the right-hand side grows faster as we increase $`1/ϵ`$ (decrease $`ϵ`$), and therefore will always be greater. ∎

We also use the following easy-to-prove fact, a proof of which may be found in \[ST03b, Proposition 2.4.7\]

###### Proposition A.0.4.

Let $`𝐱`$ be a $`d`$-dimensional Gaussian random vector of variance $`\sigma ^2`$ centered at the origin. Then,

$$\text{Pr}\left[𝒙ϵ\right]\left(\frac{ϵ}{\sigma }\right)^d.$$