# Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time

Sungyoon Kim and Mert Pilanci
Department of Electrical Engineering
Stanford University
Stanford, CA 94305, USA
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the optimality gap between two-layer ReLU networks
regularized with weight decay and their convex relaxations. We show that when
the training data is random, the relative optimality gap between the original
problem and its relaxation can be bounded by a factor of $O(\sqrt{\log n})$,
where $n$ is the number of training samples. A simple application leads to a
tractable polynomial-time algorithm that is guaranteed to solve the original
non-convex problem up to a logarithmic factor. Moreover, under mild
assumptions, we show that with random initialization on the parameters local
gradient methods almost surely converge to a point that has low training loss.
Our result is an exponential improvement compared to existing results and
sheds new light on understanding why local gradient methods work well.

##  1 Introduction

After the tremendous success of deep learning [1], data-driven approaches have
become a prominent trend in various areas of computer science. Perhaps a
surprising fact is that despite the highly non-convex landscape of deep
learning models [2], local gradient methods such as stochastic gradient
descent (SGD) [3] or ADAM [4] find nearly-global minimizers of the network
extremely well. This mystery has gained wide attention in the learning theory
community, and many have worked on the problem of proving convergence results
of local methods under certain assumptions such as the infinite-width limit
[5], heavy overparametrization [6], [7],[8], [9], and milder width assumptions
[10].

Figure 1: Convex relaxations of different widths. Here, we show the optimal
value of the relaxed problem for different numbers of subsampled hyperplane
arrangement patterns and regularization. Note that $n=300,d=10$, hence there
are $\approx 30^{10}$ variables in the convex reformulation. However, using
$\approx 30$ neurons in the relaxed problem optimizes the objective well.

In contrast to the empirical success of local gradient methods, training a
simple two-layer neural network with ReLU activation is proven to be NP-Hard
[11]. The sharp contrast between existing works on trainability guarantees and
impossibility results occurs as an increase in the width $m$, though it may
seem to make the problem harder, actually makes it easier. Hence, it is a
natural interest to understand the critical width $m^{*}$ that guarantees
polynomial time algorithms where $m\geq m^{*}$, and the corresponding
algorithm.

Recently, it was shown that two-layer and deeper ReLU networks have exact
convex reformulations [12, 13]. However, the number of variables in these
convex problems can be exponentially large. For a critical width $m^{*}\leq
n+1$, when $m\geq m^{*}$, we have an algorithm that exactly solves the non-
convex problem with complexity polynomial in $n$ (the number of data) and
exponential in $r$ (the rank of the dataset). Such an algorithm is given by
considering the convex reformulation of the original problem which has
approximately $(n/r)^{r}$ variables and solving the reformulated problem with
standard interior-point solvers. Due to the exponential factor in $r$, exactly
solving the reformulated problem is intractable, and [12] proposed to solve
the randomly relaxed version of the exact reformulation with $m\ll(n/r)^{r}$
variables, where $m$ is only polynomially large (see Section 2.1 for details).
Though the relaxed problem has polynomial complexity with respect to all
dimensions, and works well in practice (see Figure 1), the optimality gap
between the relaxed and the original problem has remained unknown. In Figure
1, width corresponds to the number of variables that the convex relaxation
has.

In this paper, we study the randomized relaxation of the exact convex
reformulation and find that:

  * •

Under certain assumptions on the input data, the relative optimality gap
between the non-convex problem and the randomized relaxation is bounded by a
logarithmic factor. This shows that the convex relaxations run in polynomial-
time and have strong approximation properties.

  * •

Using results from [14] and [15], we show that with high probability, local
gradient methods with random initialization converges to a stationary point
that has $O(\sqrt{\log n})$ relative training error with respect to the global
minimum.

  * •

We propose a tractable polynomial-time algorithm which is polynomial in all
dimensions that can approximate the global optimum within a logarithmic
factor. We are not aware of any similar result for regularized ReLU networks.

The paper is organized as follows: in Section 1.1, we go through a brief
overview of related works. Section 2 is devoted for a detailed description of
the contributions we made. Section 3 and Section 4 illustrates the overall
proof strategy, novel approximation guarantees, and the geometry behind it: we
first obtain approximation guarantees of an “easier version” of the randomly
relaxed problem, and then solve the relaxed problem using the result. We wrap
the paper with Section 5, presenting possible further discussions.

###  1.1 Prior and Related Work

Convex reformulation of neural networks: Starting from [12], an extensive line
of work have discussed convex reformulation of neural networks. The main idea
that lies in this line of work is that for different neural network
architecture, e.g. for CNNs [16], transformers [17], multi-layer networks
[18], vector outputs [19], etc, we have an exact convex reformulation with a
different regularizer. Hence, neural network architectures can be understood
as imposing different regularization to the convex problem.

Moreover, these convex reformulation have shown to give interesting insights
on the training of neural networks. For example, [14] characterizes all
stationary points of a two-layer neural network via global optimum of
corresponding convex problems, and [20] discusses the intrinsic complexity of
training two-layer networks with the view of convex duality and equivalence
with the MAX-CUT problem.

Training complexity of two-layer neural networks: We use $n$ to denote the
number of data, $d$ the dimension of data, and $m$ to be the width of the
model. Several papers have discussed the theoretical complexity of training
simple ReLU networks, and exact methods to train them. It is proven that for
single-width neural networks, it is NP-Hard to train a two-layer ReLU network
[11], and even approximating the optimal error with
$(nd)^{1/poly(\log\log(nd))}$ is proven to be NP-Hard [21]. [22] gives an
approximate algorithm to solve the single-width neural network problem with
$O(n^{k})$ complexity and $n/k$ approximate error for general input, and
constant error bound in the student-teacher setting.

Some exact algorithms to train two-layer network have been discussed, though
due to the inherent complexity of training two-layer networks, these
algorithms are often intractible in practice. [23] presents an algorithm with
$O(2^{m}n^{dm}poly(n,d,m))$ complexity, where $m$ is the width of the network.
[24] shows that when both the input and weights are constrained on a unit
ball, we can train a two-layer network to have $\epsilon$ \- error bound with
$O((2^{m/\epsilon})^{O(1)}n^{O(1)})$ complexity. Training guarantees in the
student teacher setting have also been widely discussed: [25] discusses
gaussian inputs and in the student teacher setting, we can exactly obtain the
teacher parameters in $poly(n)$ time, and [26] discusses the same problem and
propose an algorithm that works in $poly(n,m,d)$.

Note that the aforementioned complexity results are on training problems
without regularization. When we have an $l_{2}$ regularized problem, the best
exact solution to the problem is presented in [12], where they propose an
algorithm of $O(d^{3}(n/d)^{3d})$ complexity provided that the width of the
network is sufficiently large. Extending the idea, [27] proposes an
approximate method with complexity $O(d^{2}m^{2})$ that works for $m\geq
n/\xi$ for a predetermined error threshold $\xi$. However, their results
require a very wide neural network, and the relative optimal error bound is
unclear.

Trainability in the mild overparametrization regime: In the mild
overparametrization regime where the number of parameters are $\tilde{O}(n)$,
training guarantees are not well estabilished. Some noteworthy works are [28]
that shows when the number of parameters for a single layer exceeds $n$,
differentiable local minima are global, and [10], which shows that for certain
datasets only a polylogarithmic width is enough to provide training
guarantees.

For useful lemmas that will be used throughout the paper, see Appendix A.

##  2 Main Results

###  2.1 Preliminaries

First, we go through a formal description of the optimization problems that we
are interested in. Let the data matrix $X\in\mathbb{R}^{n\times d}$, the label
vector $y\in\mathbb{R}^{n}$, and weight decay regularization $\beta>0$.
Consider the training problem

$p^{*}:=\min_{u_{j},\alpha_{j}}\frac{1}{2}\lVert\sum_{j=1}^{m}(Xu_{j})_{+}\alpha_{j}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{j=1}^{m}(\lVert
u_{j}\rVert_{2}^{2}+\lVert\alpha_{j}\rVert_{2}^{2}).$ (1)

The convex counterpart of problem (1) can be written as in [12]:

$p_{0}^{*}:=\min_{u_{i},v_{i}\in\mathcal{K}_{D_{i}}}\frac{1}{2}\lVert\sum_{D_{i}\in\mathcal{D}}D_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i\in\mathcal{I}}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}).$ (2)

Convex reformulation: Let’s say $[n]=\\{1,2,...,n\\}$ and $D_{i}$ from
$i\in[P]$ denote all possible hyperplane arrangement patterns
$diag(\mathbbm{1}[(Xu)_{+}])$, where $u\in\mathbb{R}^{d}$. Also,
$\mathcal{K}_{D}=\\{u\ |\ (2D-I)Xu\geq 0\\}$ are cones where each optimization
variable are constrained at. When $\mathcal{D}$ is chosen to be
$\mathcal{D}=\\{D_{i}\ |\ i\in[P]\\},\\{u_{i}^{*},v_{i}^{*}\\}_{i=1}^{P}$ are
global minima of problem (2),

$m^{*}=\sum_{i=1}^{P}\mathbbm{1}[u_{i}^{*}\neq 0]+\mathbbm{1}[v_{i}^{*}\neq
0],$

and $m\geq m^{*}$, problems (1) and (2) become equivalent, i.e.
$p^{*}=p_{0}^{*}$ and we can construct an optimal solution of problem (1) with
$\\{u_{i}^{*},v_{i}^{*}\\}_{i=1}^{P}$. This means when $\mathcal{D}=\\{D_{i}\
|\ i\in[P]\\}$, we can exactly solve the original problem
$(\ref{nonconvex_original})$ with its convex reformulation $(\ref{convex1})$
Gaussian Relaxation: From [29], we know that $P=O(r(\frac{n}{r})^{r})$ where
$r=rank(X)$. Therefore, it is computationally intractable to sample all
possible hyperplane arrangement patterns for large $r$. The randomized
Gaussian relaxation of the problem (2) is where

$\mathcal{D}=\\{\tilde{D}_{i}=diag(\mathbbm{1}[Xg_{i}\geq 0])\ |\
g_{i}\sim\mathcal{N}(0,I_{d}),i\in[\tilde{P}]\\},$

i.e. instead of using “every possible” hyperplane arrangement pattern, we
randomly sample $\tilde{P}$ patterns given by a random Gaussian vector. Note
that we are using a very small portion of the set of all hyperplane
arrangement patterns, and it is not trivial that we will get good
approximation guarantees.

Next, we illustrate an assumption on the data distribution for the main
results.

Assumption on Dataset: Throughout the paper, we assume that the data
distribution follows $X_{ij}\sim\mathcal{N}(0,1)$ i.i.d., $n/d=c$, where $c$
is a constant, and denote as (A1). (A1) can be extended to data that are
isotropic and subgaussian, hence a bounded isotropic dataset can have similar
proof strategies and theoretical results as this paper. Here, we assume
Gaussianity for simplicity. Also, the regime $n/d=c$, i.e. $n\asymp d$, is
extensively studied in the literature [30], [31], [32]. The given structure
makes quantitive comparison between the randomized relaxation and the original
problem with the lens of random matrix theory, and provides better bounds than
arbitrary inputs.

###  2.2 Overview of Theoretical Results

We are now ready to state the main results of the paper. The first result is
the optimality bound between the non-convex problem (1) and its Gaussian
relaxation, assuming (A1).

######  Theorem 1.

(Informal) Consider the two-layer ReLU network training problem

$p^{*}:=\min_{u_{j},\alpha_{j}}\frac{1}{2}\lVert\sum_{j=1}^{m}(Xu_{j})_{+}\alpha_{j}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{j=1}^{m}(\lVert
u_{j}\rVert_{2}^{2}+\lVert\alpha_{j}\rVert_{2}^{2}),$

and its convex relaxation

$\tilde{p}^{*}:=\min_{u_{i},v_{i}\in\mathcal{K}_{\tilde{D}_{i}}}\frac{1}{2}\lVert\sum_{\tilde{D}_{i}\in\mathcal{D}}D_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i\in\mathcal{I}}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}).$ (3)

Here, $|\mathcal{D}|=m/2$ and the elements are sampled by the hyperplane
arrangement patterns of random Gaussian vectors. Assume (A1), $d$ is
sufficiently large, and suppose that $m$ satisfies
$m\geq\max\\{m^{*},320(\sqrt{c}+1)^{2}\log(\frac{n}{\delta})\\}$. Then, with
high probability,

$p^{*}\leq\tilde{p}^{*}\leq C\sqrt{\log(2n)}\ p^{*}.$

for some constant $C\geq 1$.

######  Remark.

To the best of our knowledge, the above result provides the first polynomial-
time approximation guarantee for regularized ReLU NNs. Also note that
typically we have $p^{*}\rightarrow 0$ as $\beta\rightarrow 0$, implying
$\tilde{p}^{*}-p^{*}\rightarrow 0$.

For a detailed statement of the theorem, see Appendix D. A few points on
Theorem 1 is worth mentioning. First, it gives a guarantee of the convex
relaxation of the original problem when we sample only
$\max\\{m^{*},O(\log(n))\\}$ hyperplane arrangement patterns. This is an
exponential improvement over existing convex reformulations, and as $m^{*}$ is
much smaller than $n+1$ in practice, the width bound for Theorem 1 is
practical. Also, with such characterization, we obtain a polynomial-time
approximate algorithm that works with guarantees by simply solving the convex
relaxation with standard interior-point solvers [33].

######  Theorem 2.

Assume (A1) and suppose that
$m\geq\max\\{m^{*},320(\sqrt{c}+1)^{2}\log(n/\delta)\\}$. Then, there exists a
randomized algorithm with $O(d^{3}m^{3})$ complexity that solves problem
$(\ref{nonconvex_original})$ within $O(\sqrt{\log(n)})$ relative optimality
bound.

Moreover, with the characterization of stationary points in [14], we can prove
that local gradient methods converge to “nice” stationary points under the
assumption below:

(A2) While local gradient method iterates, only a portion $p<1/2$ of the
initial hyperplane arrangement patterns change until it converges.

Figure 2: Verification of (A2) for gradient descent. The upper figure shows
how many hyperplane arrangement patterns change for random data, and the lower
figure shows how many of them change for MNIST.

(A2) is also considered in [15], where they show that SGD with random
initialization preserves most of the hyperplane arrangement patterns. The
specific lemma, which they refer to as the coupling lemma, is as follows. It
is also verified for gradient descent, both for random data and MNIST in
Figure 2.

######  Lemma 1.

(Coupling lemma, [15]) With high probability over the random initialization
that follows $\mathcal{N}(0,m^{-1}I)$, and suppose the data is generated from
$l$ underlying distributions. For every $\tau>0$, $t=\tilde{O}(\tau/\eta)$, at
least $1-e\tau l/\sigma$ portion of the hyperplane arrangement patterns remain
the same.

The idea is that we can map each stationary point to a global minima of a
convex problem, and as we initialized at random, we can think of the
stationary points as global minimizers of the convex problem with randomized
hyperplane arrangement patterns.

######  Theorem 3.

(Informal) Consider the training problem
$\min_{u_{j},\alpha_{j}}\mathcal{L}(u,\alpha),$ where the loss function
$\mathcal{L}$ is given as

$\mathcal{L}(u,\alpha)=\frac{1}{2}\lVert\sum_{j=1}^{m}(Xu_{j})_{+}\alpha_{j}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{j=1}^{m}(\lVert
u_{j}\rVert_{2}^{2}+\alpha_{j}^{2}).$

Assume (A1),(A2) and $d,m$ are sufficiently large. For any random
initialization $\\{u_{i}^{0},\alpha_{i}^{0}\\}_{i=1}^{m}$, suppose local
gradient method converged to a stationary point
$\\{u_{i}^{\prime},\alpha_{i}^{\prime}\\}_{i=1}^{m}$. Then, with high
probability,

$\mathcal{L}(u^{\prime},\alpha^{\prime})\leq
C\sqrt{\log(2n)}\mathcal{L}(u^{*},\alpha^{*}),$

for some $C\geq 1$. Here, $\\{u_{i}^{*},\alpha_{i}^{*}\\}_{i=1}^{m}$ is a
global optimum of $\mathcal{L}(u,\alpha)$.

######  Remark.

The above result shows that there exists many stationary points whose
objective value is a logarithmic approximation of the global optimum.
Therefore, first-order optimizers such as SGD and Adam can approximate the
global optimum even when they converge to stationary points.

Note that our analysis is not based on explicit iteration of local gradient
methods, or does not exploit a NTK - based analysis. Rather, it follows from a
simple yet clear analysis based on the lens of convex optimization.

###  2.3 Notations for the proof

Before discussing the proof strategy, we clarify some frequently used
variables in this section. We use $D_{i}$ for $i\in[P]$ to denote all possible
hyperplane arrangements, $P$ to denote the number of all possible hyperplane
arrangements, $\tilde{D}_{i}$ to denote randomly selected hyperplane
arrangement patterns, and $\tilde{P}$ the number of such subsamples. We also
use $\mathcal{K}_{D}$ as in preliminaries. $\mathcal{M}$ is used to denote

$\mathbb{E}_{g\sim\mathcal{N}(0,I_{d})}[diag[\mathbbm{1}(Xg\geq
0)]XX^{T}diag[\mathbbm{1}(Xg\geq 0)]],$

and $\kappa$, which is analogous to the condition number, to denote

$\frac{\lambda_{max}(XX^{T})}{\lambda_{min}(\mathcal{M})},$

provided that $\mathcal{M}$ is invertible. At last, $m^{*}$ is used to denote
the number of nonzero variables for the optimal solution of the convex
reformulation.

###  2.4 Overall proof strategy

To prove Theorem 1, we first consider the unconstrained problem

$\tilde{p_{1}}^{*}:=\min_{u_{i},v_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{\tilde{D}_{i}\in\mathcal{D}}D_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i\in\mathcal{I}}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}).$ (4)

The convex problem (4) was first introduced in [34], where they first solve
the unconstrained problem and decompose it into cone constraints to solve the
original problem (3). The problem is further equivalent to

$\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{P}D_{i}Xw_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{P}\lVert
w_{i}\rVert_{2},$ (5)

due to triangle inequality. We use a similar strategy that was introduced in
[34]: first, we show that the unconstrained problem enjoys good approximation
guarantees, even though we use only a subsample of the whole possible
hyperplane arrangement patterns. After that, for global optimum
$\\{w_{i}^{*}\\}_{i=1}^{m}$ of problem (5), we find
$u_{i},v_{i}\in\mathcal{K}_{D_{i}}$ that satisfies $u_{i}-v_{i}=w_{i}^{*}$ and
minimal norm sum $\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}$. We find that
this decomposition does not increase the norm up to $O(\sqrt{\log(2n)})$
factor, finally leading to the guarantee to the original problem.

##  3 Guarantees for the Unconstrained Convex Relaxation

Let’s start with the unconstrained optimiization problem Equation 5. Note
$\tilde{p}_{1}^{*}$ to be the optimal value of the random relaxation of the
unconstrained problem, and $p_{1}^{*}$ to be the optimal value of the
unconstrained problem using all possible hyperplane arrangement patterns. We
wish to find constants $C_{1},C_{2}>0$ depending only with the data matrix $X$
that satisfies

$0\leq\tilde{p}_{1}^{*}-p_{1}^{*}\leq C_{1},\quad
p_{1}^{*}\leq\tilde{p}_{1}^{*}\leq C_{2}p_{1}^{*}.$

As a warmup, we first give results when the problem is unregularized. We can
show that $p_{1}^{*}=\tilde{p}_{1}^{*}=0$ with high probability when we sample
sufficiently many hyperplane arrangement patterns. After that, we give
approximation results for a gated ReLU problem with $l_{2}$ regularization and
use them to prove that

$C_{1}=\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}},C_{2}=2\sqrt{2}\sqrt{\frac{\lambda_{\max}(XX^{T})}{\lambda_{\min}(\mathcal{M})}},$

holds with probability at least $1-\delta$, provided that we sample
sufficiently many hyperplanes and the dimension $d$ is sufficiently large. We
defer the proofs to Appendix B.

###  3.1 Warmup: Unconstrained Relaxation Without Regularization

To show that $p_{1}^{*}=0$, we prove that we can approximate any vector with
$2n$ hyperplane arrangement patterns. The proof is consistent with general
overparametrization arguments, which state that when the width of the network
is $m\geq n$, any local minimum becomes the global minimum. Here, we carefully
choose $2n$ hyperplane arrangement patterns where each arrangement pair
$D_{1,i},D_{2,i}$ differ only at the $i$-th diagonal entry. With $n$ such
pairs we can express any vector $y\in\mathbb{R}^{n}$ as a linear combination
of vectors in the column space of
$\\{(D_{1,i}-D_{2,i})u|u\in\mathbb{R}^{n}\\}=\\{ke_{i}|k\in\mathbb{R}\\}$,
proving that there exists $u_{i}$ s satisfying

$\sum_{i=1}^{n}(D_{1,i}-D_{2,i})Xu_{i}=y,$

meaning that if we have all possible hyperplane arrangement patterns we can
express any vector $y$ with zero error. The specific proposition is as
follows.

######  Proposition 1.

Suppose no two rows of $X$ are parallel. There exists hyperplane patterns
$\tilde{D}_{1}$, $\tilde{D}_{2}$, …, $\tilde{D}_{2n}$ such that for any
$y\in\mathbb{R}^{n}$, there exists $u_{1},u_{2},...u_{2n}\in\mathbb{R}^{d}$
satisfying

$\sum_{i=1}^{2n}\tilde{D}_{i}Xu_{i}=y.$

However, we can further prove that using randomly sampled hyperplane
arrangement patterns $\tilde{D}_{i}$, we can fit arbitrary vector $y$ with
probability at least $1-\delta$, provided that we sample sufficiently many
hyperplane arrangement patterns.

######  Proposition 2.

Suppose we sampled $\tilde{P}=2\kappa\log(\frac{n}{\delta})$ hyperplane
arrangement patterns, provided that $\mathcal{M}$ is invertible. Then, with
probability at least $1-\delta$, for any $y\in\mathbb{R}^{n}$ there exists
$u_{1},u_{2},...,u_{\tilde{P}}$ satisfying

$\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}=y.$

Proposition 2 shows that when we sample sufficiently many hyperplane
arrangement patterns, we can fit arbitrary vector with high probability, hence
$\tilde{p}_{1}^{*}=0$. The two propositions lead to the following
approximation result.

######  Corollary 1.

When $\beta=0$ and $\tilde{P}\geq 2\kappa\log(\frac{n}{\delta}),$
$p_{0}^{*}=p_{1}^{*}=0$ with probability at least $1-\delta$.

One natural question is “how large will $\kappa$ be?” Interestingly, when (A1)
is satisfied, we can show that $\kappa=O(n/d)$ holds (see Section 3.5 for
details). Hence, for random data, we use approximately $O(\log n)$ neurons to
fit to $y\in\mathbb{R}^{n}$ with high probability. Note that we need at least
$n/d$ hyperplane arrangement patterns and $n$ parameters to fit to any vector.
This means that for random data, Proposition 2 is optimal up to a logarithmic
factor.

###  3.2 Unconstrained Relaxation with $l_{2}$ Regularization

In the case of $l_{2}$ regularization, we can find that when we sample more
hyperplane arrangement patterns, the optimal value decreases with the same
order as the number of planes with high probability. The proof is rather
straightforward: we solve the linear-constrained quadratic problem, and then
use matrix chernoff bounds to relate the eigenvalues of $\mathcal{M}$ with the
eigenvalue of sample mean of matrices

$\mathcal{M}_{\tilde{P}}=\frac{1}{\tilde{P}}\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i}.$

######  Theorem 4.

Let $p_{2}^{*}$ be the optimal value of the unconstrained relaxed problem with
$l_{2}$ regularization, and suppose $\tilde{P}\geq
12\kappa\log(\frac{2n}{\delta})$. With probability at least $1-\delta$ there
exists scalars $C_{1},C_{2}>0$ that satisfies

$\frac{C_{1}}{\tilde{P}}\leq p_{2}^{*}\leq\frac{C_{2}}{\tilde{P}}.$

An intuitive explanation of Theorem 4 is that when we sample sufficiently many
hyperplane arrangement patterns, we have
$\mathcal{M}_{\tilde{P}}\approx\mathcal{M}$ and the optimal value of the
$l_{2}$ regularized problem concentrates to
$\frac{\beta}{\tilde{P}}y^{T}\mathcal{M}^{-1}y$. This characterization means
that for $l_{2}$ regularization, we cannot have relative optimality gap that
is independent of $P$, the total number of all possible hyperplane arrangement
patterns.

###  3.3 Unconstrained Relaxation With Group $l_{1}$ Regularization

Different from problem the case with $l_{2}$ regularization, when we have
group $l_{1}$ regularization, we can have relative error bounds that are
irrelevant with the total number of hyperplane arrangement patterns. We first
obtain an upper bound of $\tilde{p}_{1}^{*}$ by using surrogate variables
$\kappa_{i}$ and solving the $l_{2}$ regularized problem,

$\min_{\kappa_{i}\in\mathbb{R}}\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}(\kappa_{i}\lVert
u_{i}\rVert_{2}^{2}+\frac{1}{\kappa_{i}}).$ (6)

We cannot exactly solve problem (6). However, we can use the ansatz
$\kappa_{i}=\frac{\kappa}{\tilde{P}}$ and apply matrix concentration to upper
bound the optimal value.

######  Proposition 3.

Let $\tilde{p}_{1}^{*}$ the optimal value of Approx C-GReLU. Suppose we
sampled $\tilde{P}\geq 8\kappa\log(\frac{n}{\delta})$ hyperplane arrangement
patterns. With probability at least $1-\delta$,

$\tilde{p}_{1}^{*}\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}},$

provided that $\mathcal{M}$ is invertible.

Then, we lower bound $p_{1}^{*}$ using the dual problem of 5. As the dual
problem becomes a maximization of the dual objective with respect to a dual
variable $\lambda$, choosing $\lambda$ well can give a meaningful lower bound
on $p_{1}^{*}$. In the proof we choose a scalar multiple of $y$ to obtain a
bound that has a similar scale with $\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}}$.

######  Proposition 4.

Let $p_{1}^{*}$ be the optimal value of Full C-GReLU. When we write
$\mathcal{M}_{i}=D_{i}XX^{T}D_{i}$,

$G\beta\frac{\lVert y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}\leq
p_{1}^{*},$

where

$G=1-\frac{\beta}{2\max_{i\in[P]}\sqrt{y^{T}\mathcal{M}_{i}y}}.$

A direct corollary simplifies the lower bound. Corollary 2 can be used when
$\beta$ is sufficiently smaller than $\lVert
y\rVert\sqrt{\lambda_{\min}(\mathcal{M})}$. As $\lVert y\rVert$ is the scale
of $O(\sqrt{n})$ and $\lambda_{\min}(\mathcal{M})$ grows with $d$ for random
data matrix $X$, it is likely that the value $\lVert
y\rVert\sqrt{\lambda_{\min}(\mathcal{M})}$ is much larger than $\beta$ for
most cases.

######  Corollary 2.

Suppose further that $\lVert
y\rVert\sqrt{\lambda_{\min}(\mathcal{M})}\geq\beta$. Then,

$\frac{\beta}{2}\frac{\lVert y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}\leq
p_{1}^{*}.$

By using Proposition 3 and Proposition 4, we obtain a relative error bound
between $p_{1}^{*}$ and $\tilde{p}_{1}^{*}$.

######  Theorem 5.

Let $p_{1}^{*}$ and $\tilde{p}_{1}^{*}$ be optimal values of problem (5) with
all possible hyperplane arrangements and randomly sampled arrangements,
respectively. Suppose we sampled $\tilde{P}\geq 8\kappa\log(\frac{n}{\delta})$
hyperplane arrangement patterns and $\mathcal{M}$ is invertible. We have

$0\leq\tilde{p}_{1}^{*}-p_{1}^{*}\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}},$

and

$p_{1}^{*}\leq\tilde{p}_{1}^{*}\leq\frac{\sqrt{2\kappa}}{G}p_{1}^{*},$

with probability at least $1-\delta$.

Note that different from the $l_{2}$ regularized case, in this case we have a
relative error bound that is independant of the total number of hyperplane
arrangement patterns.

A better approximation is possible if we take into account two things: one is
that we can use $\max_{i}\sqrt{y^{T}\mathcal{M}_{i}y}/\lVert y\rVert_{2}$
instead of $\lambda_{\max}(XX^{T})$ to bound the relative error with a tighter
bound, and we can also use $\mathcal{M}_{\tilde{P}}$ directly instead of
$\lambda_{\min}(\mathcal{M})$. Hence, the overall bound can be improved to

$p_{0}^{*}\leq
p_{1}^{*}\leq\frac{\sqrt{2}}{G}\frac{\max_{i}\sqrt{y^{T}\mathcal{M}_{i}y}\sqrt{y^{T}\mathcal{M_{\tilde{P}}}^{-1}y}}{\lVert
y\rVert_{2}^{2}}p_{0}^{*},$ (7)

where we sampled sufficiently many hyperplane arrangement patterns to make
$\mathcal{M}_{\tilde{P}}$ invertible.

###  3.4 Connection to the MAX-CUT Problem

There is an interesting connection between the upper bound of the relative
error and the MAX-CUT problem. From bound (7), we can bound

$\max_{i}\sqrt{y^{T}\mathcal{M}_{i}y}\leq\sqrt{\max_{b\in\\{0,1\\}^{n}}b^{T}diag(y)XX^{T}diag(y)b},$

where solving the right hand side is equivalent to solving the max-cut problem
of the graph with adjacency matrix

$\frac{1}{4}\begin{bmatrix}I\\\
1^{T}\end{bmatrix}diag(y)XX^{T}diag(y)\begin{bmatrix}I&1\end{bmatrix}.$

Hence, in special cases where $X$ is orthogonally separable or when $X$ has
negative correlation, we may further bound the relative error. The connection
with MAX-CUT shows that the relative error, or the possibility of
approximation, in intrinsically related to the structure of the dataset and
its clusterization properties.

###  3.5 Scale of $\kappa$ for Random Data

In this subsection we show that under (A1), we can show that $\kappa\leq O(c)$
holds with high probability for sufficiently large $d$. This means that for
random data, as long as $d$ grows with $n$, we only need to sample $O(\log n)$
hyperplane arrangement patterns to obtain a constant factor approximation of
the unconstrained relaxation. This bound is more practical compared to most
bounds that require networks of width at least $n$.

To prove the identity, we first use the non-asymptotic inequality deduced from
Gordon’s minimax comparison

$\lambda_{max}(XX^{T})\leq 2(\sqrt{n}+\sqrt{d})^{2},$

which holds with high probability. To upper bound $\kappa$, finding a lower
bound of $\lambda_{\min}(\mathcal{M})$ is enough.

In order to lower bound $\lambda_{\min}(\mathcal{M})$, we find a closed form
expression of $\mathcal{M}_{ij}$ and use Lemma 6 to approximate $\mathcal{M}$
via linearization. We need $d$ to be sufficiently large in order to apply
concentration inequalities on $\lVert x_{i}\rVert_{2}$, the norm of rows of
$X$.

######  Theorem 6.

Assume (A1) and suppose $c\geq 1,\delta>0$. There exists $d_{1}$ such that if
$d\geq d_{1}$, with probability at least $1-\delta-\frac{1}{(2n)^{8}}$, we
have

$\lambda_{min}(\mathcal{M})\geq\frac{d}{10}.$

Hence, $\kappa$ is indeed upper bounded with a constant factor when $d$ is
sufficiently large. Using the fact directly leads to the following corollary.

######  Corollary 3.

When the conditions of Theorem 6 holds, with probability at least
$1-\delta-\frac{1}{(2n)^{8}}$, we have

$\kappa\leq 10\sqrt{2}(\sqrt{c}+1)^{2}.$

Moreover, when we sample $\tilde{P}\geq
160(\sqrt{c}+1)^{2}\log(\frac{n}{\delta^{\prime}})$ hyperplane arrangement
patterns, we have

$p_{1}^{*}\leq\tilde{p}_{1}^{*}\leq\frac{2\sqrt{10}}{G}(\sqrt{c}+1)p_{1}^{*}$

with probability at least $1-\delta-\delta^{\prime}-\frac{1}{(2n)^{8}}.$

##  4 Extension to the Constrained Problem

In this section, we move a step further by discussing the relative error
between the optimal value of the convex reformulation and its random
relaxation. Let ${w_{i}^{*}}_{i=1}^{m}$ be the solution of the unconstrained
relaxation of the original problem and let
$u_{i}^{*},v_{i}^{*}\in\mathcal{K}_{D_{i}}$ satisfying
$w_{i}^{*}=u_{i}^{*}-v_{i}^{*}$ with minimal $\lVert
u_{i}^{*}\rVert_{2}+\lVert v_{i}^{*}\rVert_{2}$.

Although there is no universal constant $C$ that satisfies

$\lVert u_{i}^{*}\rVert_{2}+\lVert v_{i}^{*}\rVert_{2}\leq C\lVert
w_{i}^{*}\rVert_{2},$

for any cone $\mathcal{K}$ [34], we can show that for random data $X$, it is
likely that there exists reasonably large $\mathcal{C}$ that satisfies

$\lVert u_{i}^{*}\rVert_{2}+\lVert v_{i}^{*}\rVert_{2}\leq\mathcal{C}\lVert
w_{i}^{*}\rVert_{2},$

for all $\mathcal{K}_{\tilde{D}_{i}}$ and $w_{i}^{*}$ with high probability.
In 2 dimensions, $\mathcal{C}$ is directly related with the angle between two
rays of the convex cone make. Hence, $\mathcal{C}$ is analogous to the
‘sharpness of each cone $\mathcal{K}_{\tilde{D}_{i}}$’. We defer the proofs to
Appendix C.

###  4.1 Cone sharpness $\mathcal{C}$

We start from defining the cone sharpness constant
$\mathcal{C}(\mathcal{K},z)$ for a given convex cone $\mathcal{K}$.

######  Definition 1.

For a cone $\mathcal{K}$ and unit vector $z$, the sharpness with respect to
$z$ is defined as

$C(\mathcal{K},z)=\min_{u,v\in\mathcal{K},u-v=z}\lVert u\rVert_{2}+\lVert
v\rVert_{2}.$

We can upper bound the unconstrained relaxation with the constrained
relaxation using the cone sharpness.

######  Proposition 5.

Let $\tilde{p}_{0}^{*}$ and $\tilde{p}_{1}^{*}$ be optimal values of the
Gaussian relaxation of the convex reformulation and its unconstrained version,
respectively. Suppose the unconstrained problem has solutions $w_{i}^{*}$ for
$i\in[\tilde{P}]$, and let

$C=\max_{i\in[\tilde{P}]}\mathcal{C}(\mathcal{K}_{\tilde{D}_{i}},\frac{w_{i}^{*}}{\lVert
w_{i}^{*}\rVert_{2}}).$

Then, $\tilde{p}_{0}^{*}\leq C\tilde{p}_{1}^{*}$ holds.

Now, we introduce a strategy to upper bound
$\mathcal{C}(\mathcal{K}_{\tilde{D}_{i}},z)$. An interesting fact is that for
when (A1) is satisfied, the cone sharpness constant is not large with high
probability, and can be bounded by $O(\sqrt{\log n})$ factor. The intuition
here is that when $n\asymp d$, we have approximately $O((n/d)^{d})$ many cones
- which is only exponential in $d$ when $n/d=c$. Hence, in $d$ dimensions, the
number of cone constraints are not that many, and we can have reasonable upper
bounds on the sharpness.

We first start with a simple proposition that upper bounds
$C(\mathcal{K}_{\tilde{D}_{i}},z)$. The idea is similar to Chebyshev centers
of a polyhedron [35].

######  Proposition 6.

Take any unit vector $z$, and suppose $\mathcal{K}=\\{u|(2D-I)Xu\geq 0\\}$. If
there exists vector $u$ that satisfies

$\lVert u\rVert_{2}\leq 1,\quad(2D-I)Xu\geq\epsilon\cdot|(2D-I)Xz|,$

we know that

$C(\mathcal{K},z)\leq 1+\frac{1}{\epsilon}.$

When (A1) is satisfied, with the rotational invariance of $X$, we can rotate
the cone to contain $e_{1}$ and the distribution of other elements on $X$ will
not change. Therefore, without loss of generality, we may assume that
$\mathcal{K}=\\{u\ |\ \tilde{X}u\geq 0\\},$ where the first column of
$\tilde{X}$ is the absolute value sampled from $\mathcal{N}(0,1)$ and the
other columns are sampled from $\mathcal{N}(0,1)$.

What we wish to do is to construct a vector $u$ that satisfies the conditions
in Proposition 6. We find such vector using a novel property of $n\times n$
Gaussian random matrices. An application of Gordon’s minimax theorem leads to
the following proposition.

######  Lemma 2.

Suppose $X$ is a $d\times d$ random matrix with entries i.i.d. and sampled
from $\mathcal{N}(0,1)$. Also, suppose $b$ is an arbitrary vector that
satisfies $\lVert b\rVert_{2}\leq 2\sqrt{n}$ and $n/d=c$. Then, for some
$B>0$, with probability at least $1-8\exp(-Bn)$, there exists a vector that
satisfies $\lVert\lambda\rVert_{2}\leq 5c$ and $X\lambda\geq b$.

By using the $\lambda$ in Lemma 2, we can construct $u$ for the rotated cone
$\mathcal{K}=\\{u\ |\ \tilde{X}u\geq 0\\}$. Eventually, we can bound
$\mathcal{C}(\mathcal{K},z)$ with a logarithmic factor.

######  Theorem 7.

Let $p_{c}$ to be the probability that the $0.75d-th$ absolute value of $n$
samples sampled uniformly at random from $\mathcal{N}(0,1)$ is less than
$d/2n=1/2c$. Also, suppose $d\geq d_{2}$, where $d_{2}$ is the threshold that
we can guarantee the existence of such $\lambda\in\mathbb{R}^{d_{2}}$ from
Lemma 2 with probability at least $1-\delta^{\prime\prime}$.

Then, with probability at least $1-p_{c}-2/(2n)^{9}-\delta^{\prime\prime}$, we
know that

$C(\mathcal{K}_{\tilde{D}_{i}},z)\leq 1+80c^{2}\sqrt{\log(2n)}.$

A direct corollary is that we can approximate the convex reformulation with
its unconstrained version, having $O(\sqrt{\log n})$ scale relative bound
(Corollary 7).

###  4.2 Proof of the main results

After the bound on the cone sharpness, the proof of the main theorems follow
almost immediately. By considering the convex reformulation of the original
problem (1), and first upper bounding it with the unconstrained problem, then
upper bounding it again with the unconstrained problem with random relaxation,
we can find relative optimality gap between the original problem and its
convex relaxation. It is clear that we immediately get a tractable polynomial-
time randomized algorithm by solving the randomly relaxed convex problem. At
last, by identifying stationary points of the original problem as global
minimum of randomly subsampled convex problems, we obtain Theorem 3. See
Appendix D for a detailed proof.

##  5 Conclusion

In this paper, we provided guarantees of approximating the equivalent convex
program given in [12] with a much smaller random subprogram. With assumptions
on $X$ and the dimension $d$, we proved that the optimal value of the
subsampled convex program approximates the full convex program up to a
logarithmic factor. Using the approximation results we discuss novel insights
on training two-layer neural networks, by showing that under mild assumptions
local gradient methods converge to stationary points with optimality
guarantees, and propose a practical algorithm to train neural networks with
guarantees.

We hope to improve the work in two ways: First, removing the logarithmic
factor of the approximation would be an important problem to tackle. Also,
extending the theorems to different architectures, i.e. CNNs, transformers,
multi-layer networks would be meaningful.

##  6 Acknowledgements

This work was supported in part by the National Science Foundation (NSF) under
Grant DMS-2134248; in part by the NSF CAREER Award under Grant CCF-2236829; in
part by the U.S. Army Research Office Early Career Award under Grant
W911NF-21-1-0242; in part by the Precourt Institute for Energy and the SystemX
Alliance at Stanford University.

## References

  * [1] Yann LeCun, Yoshua Bengio and Geoffrey Hinton  “Deep learning”  In _nature_ 521.7553 Nature Publishing Group UK London, 2015, pp. 436–444
  * [2] Hao Li et al.  “Visualizing the loss landscape of neural nets”  In _Advances in neural information processing systems_ 31, 2018
  * [3] Léon Bottou  “Large-scale machine learning with stochastic gradient descent”  In _Proceedings of COMPSTAT’2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers_ , 2010, pp. 177–186  Springer
  * [4] Diederik P Kingma and Jimmy Ba  “Adam: A method for stochastic optimization”  In _arXiv preprint arXiv:1412.6980_ , 2014
  * [5] Arthur Jacot, Franck Gabriel and Clément Hongler  “Neural tangent kernel: Convergence and generalization in neural networks”  In _Advances in neural information processing systems_ 31, 2018
  * [6] Simon Du et al.  “Gradient descent finds global minima of deep neural networks”  In _International conference on machine learning_ , 2019, pp. 1675–1685  PMLR
  * [7] Sanjeev Arora et al.  “Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks”  In _International Conference on Machine Learning_ , 2019, pp. 322–332  PMLR
  * [8] Difan Zou, Yuan Cao, Dongruo Zhou and Quanquan Gu  “Gradient descent optimizes over-parameterized deep ReLU networks”  In _Machine learning_ 109 Springer, 2020, pp. 467–492
  * [9] Difan Zou, Yuan Cao, Dongruo Zhou and Quanquan Gu  “Stochastic gradient descent optimizes over-parameterized deep relu networks”  In _arXiv preprint arXiv:1811.08888_ , 2018
  * [10] Ziwei Ji and Matus Telgarsky  “Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks”  In _arXiv preprint arXiv:1909.12292_ , 2019
  * [11] Digvijay Boob, Santanu S Dey and Guanghui Lan  “Complexity of training relu neural network”  In _Discrete Optimization_ 44 Elsevier, 2022, pp. 100620
  * [12] Mert Pilanci and Tolga Ergen  “Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks”  In _International Conference on Machine Learning_ , 2020, pp. 7695–7705  PMLR
  * [13] Yifei Wang, Tolga Ergen and Mert Pilanci  “Parallel Deep Neural Networks Have Zero Duality Gap”  In _The Eleventh International Conference on Learning Representations_ , 2022
  * [14] Yifei Wang, Jonathan Lacotte and Mert Pilanci  “The hidden convex optimization landscape of regularized two-layer relu networks: an exact characterization of optimal solutions”  In _International Conference on Learning Representations_ , 2021
  * [15] Yuanzhi Li and Yingyu Liang  “Learning overparameterized neural networks via stochastic gradient descent on structured data”  In _Advances in neural information processing systems_ 31, 2018
  * [16] Tolga Ergen and Mert Pilanci  “Implicit convex regularizers of cnn architectures: Convex optimization of two-and three-layer networks in polynomial time”  In _arXiv preprint arXiv:2006.14798_ , 2020
  * [17] Arda Sahiner et al.  “Unraveling attention via convex duality: Analysis and interpretations of vision transformers”  In _International Conference on Machine Learning_ , 2022, pp. 19050–19088  PMLR
  * [18] Tolga Ergen and Mert Pilanci  “Global optimality beyond two layers: Training deep relu networks via convex programs”  In _International Conference on Machine Learning_ , 2021, pp. 2993–3003  PMLR
  * [19] Arda Sahiner, Tolga Ergen, John Pauly and Mert Pilanci  “Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms”  In _arXiv preprint arXiv:2012.13329_ , 2020
  * [20] Yifei Wang and Mert Pilanci  “Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes”  In _arXiv preprint arXiv:2311.10972_ , 2023
  * [21] Surbhi Goel, Adam Klivans, Pasin Manurangsi and Daniel Reichman  “Tight hardness results for training depth-2 ReLU networks”  In _arXiv preprint arXiv:2011.13550_ , 2020
  * [22] Santanu S Dey, Guanyi Wang and Yao Xie  “Approximation algorithms for training one-node ReLU neural networks”  In _IEEE Transactions on Signal Processing_ 68 IEEE, 2020, pp. 6696–6706
  * [23] Raman Arora, Amitabh Basu, Poorya Mianjy and Anirbit Mukherjee  “Understanding deep neural networks with rectified linear units”  In _arXiv preprint arXiv:1611.01491_ , 2016
  * [24] Pasin Manurangsi and Daniel Reichman  “The computational complexity of training relu (s)”  In _arXiv preprint arXiv:1810.04207_ , 2018
  * [25] Ainesh Bakshi, Rajesh Jayaram and David P Woodruff  “Learning two layer rectified neural networks in polynomial time”  In _Conference on Learning Theory_ , 2019, pp. 195–268  PMLR
  * [26] Pranjal Awasthi, Alex Tang and Aravindan Vijayaraghavan  “Efficient algorithms for learning depth-2 neural networks with general relu activations”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 13485–13496
  * [27] Yatong Bai, Tanmay Gautam and Somayeh Sojoudi  “Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training”  In _SIAM Journal on Mathematics of Data Science_ 5.2 SIAM, 2023, pp. 446–474
  * [28] Daniel Soudry and Yair Carmon  “No bad local minima: Data independent training error guarantees for multilayer neural networks”  In _arXiv preprint arXiv:1605.08361_ , 2016
  * [29] Thomas M. Cover  “Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition”  In _IEEE Transactions on Electronic Computers_ EC-14.3, 1965, pp. 326–334  DOI: 10.1109/PGEC.1965.264137
  * [30] Andrea Montanari, Feng Ruan, Youngtak Sohn and Jun Yan  “The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime”  In _arXiv preprint arXiv:1911.01544_ , 2019
  * [31] Michael Celentano, Chen Cheng and Andrea Montanari  “The high-dimensional asymptotics of first order methods with random data”  In _arXiv preprint arXiv:2112.07572_ , 2021
  * [32] Michael Celentano and Andrea Montanari  “Fundamental barriers to high-dimensional regression with convex penalties”  In _The Annals of Statistics_ 50.1 Institute of Mathematical Statistics, 2022, pp. 170–196
  * [33] Florian A Potra and Stephen J Wright  “Interior-point methods”  In _Journal of computational and applied mathematics_ 124.1-2 Elsevier, 2000, pp. 281–302
  * [34] Aaron Mishkin, Arda Sahiner and Mert Pilanci  “Fast convex optimization for two-layer relu networks: Equivalent model classes and cone decompositions”  In _International Conference on Machine Learning_ , 2022, pp. 15770–15816  PMLR
  * [35] Stephen P Boyd and Lieven Vandenberghe  “Convex optimization”  Cambridge university press, 2004
  * [36] Joel A Tropp  “An introduction to matrix concentration inequalities”  In _Foundations and Trends® in Machine Learning_ 8.1-2 Now Publishers, Inc., 2015, pp. 1–230
  * [37] Nick Harvey  “Lecture 2: Matrix Chernoff bounds”
  * [38] Christos Thrampoulidis, Samet Oymak and Babak Hassibi  “The Gaussian min-max theorem in the presence of convexity”  In _arXiv preprint arXiv:1408.4837_ , 2014
  * [39] Noureddine El Karoui  “The spectrum of kernel random matrices”, 2010

##  Appendix A Useful Lemmas

######  Lemma 3.

(Matrix Chernoff [36], [37] ) Let $X_{1},X_{2},...,X_{k}$ be independent,
random, symmetric real $n\times n$ matrix with $0\preccurlyeq
X_{i}\preccurlyeq RI$. Let
$\mu_{min}I\preccurlyeq\sum_{i=1}^{k}\mathbb{E}[X_{i}]\preccurlyeq\mu_{max}I$.
Then, for all $\delta\in[0,1]$,

$\mathbb{P}(\lambda_{max}(\sum_{i=1}^{k}X_{i})\geq(1+\delta)\mu_{max})\leq
ne^{-\delta^{2}\mu_{max}/3R}$

and

$\mathbb{P}(\lambda_{min}(\sum_{i=1}^{k}X_{i})\leq(1-\delta)\mu_{min})\leq
ne^{-\delta^{2}\mu_{min}/2R}$

holds.

######  Lemma 4.

(Gordon’s minimax theorem [38]) Let $\Phi(X)$ be

$\Phi(X)=\min_{x\in S_{x}}\max_{y\in S_{y}}y^{T}Xx+\psi(x,y),$

where $X$ is a random matrix with i.i.d. Gaussian entries, and $\phi(g,h)$ be

$\phi(g,h)=\min_{x\in S_{x}}\max_{y\in S_{y}}\lVert x\rVert_{2}g^{T}y+\lVert
y\rVert_{2}h^{T}x+\psi(x,y),$

where entries of $g,h$ are i.i.d. and sampled from $\mathcal{N}(0,1)$. Then,
we have

$\mathbb{P}(\Phi(X)\leq M)\leq 2\mathbb{P}(\phi(g,h)\leq M).$

######  Lemma 5.

(Weyl’s theorem on eigenvalues) Suppose $A,B\in\mathbb{R}^{n\times n}$ are
symmetric. Then, the below estimates on the minimum eigenvalue of $A,B$ hold.

$\lambda_{min}(A)\geq\lambda_{min}(B)-\lVert A-B\rVert_{F},$ (8)
$\lambda_{min}(A+B)\geq\lambda_{min}(A)+\lambda_{min}(B).$ (9)

Here, $\rho(A)$ denotes the spectral radius of $A$, and $\lVert A\rVert_{F}$
is the Frobenius norm of $A$.

######  Lemma 6.

(Spectrum of kernel random matrices [39]) Suppose we obtain $n$ i.i.d. vectors
$x_{i}$ from $\mathcal{N}(0,I_{d})$. Let’s consider the kernel matrix

$K_{i,j}=f(\frac{x_{i}\cdot x_{j}}{d}).$

We assume that:
(a) $n/d,d/n$ are bounded as $d\rightarrow\infty$.
(b) $f$ is a $C^{1}$ function in a neighborhood of 1, and a $C^{3}$ function
in a neighborhood of 0.
Under the assumptions, the kernel matrix $M$ can (in probability) be
approximated consistently in operator norm, when $d,n\rightarrow\infty$, by
the matrix $K^{\prime}$, where

$K^{\prime}=(f(0)+\frac{f^{\prime\prime}(0)}{2d})11^{T}+\frac{f^{\prime}(0)}{d}XX^{T}+(f(1)-f(0)-f^{\prime}(0))I_{n}.$

##  Appendix B Proofs in Section 3.

######  Proposition 7.

(Proposition 3.1. of the paper) Suppose no two rows of $X$ are parallel. There
exists hyperplane patterns $\tilde{D}_{1}$, $\tilde{D}_{2}$, …,
$\tilde{D}_{2n}$ such that for all $y\in\mathbb{R}^{n}$, there exists
$u_{1},u_{2},...u_{2n}\in\mathbb{R}^{d}$ satisfying

$\sum_{i=1}^{2n}\tilde{D}_{i}Xu_{i}=y.$

###### Proof.

Let’s begin with a simple observation: for any $i\in[n]$, there exists two
different hyperplane pattern $D_{1,i}$ and $D_{2,i}$ satisfying

$|D_{1,i}-D_{2,i}|=diag(e_{i}).$

The construction is intuitive when thought geometrically, passing through only
the $i$th plane. A rigorous construction is as below: First, choose a point
$c\in\mathbb{R}^{d}$ satisfying

$c\cdot X_{i}=0,\quad c\cdot X_{j}\neq 0\quad for\ all\quad j\neq i,$

where $X_{1},X_{2},...,X_{n}$ are rows of $X$. We can choose such point
because the set $\\{u|u\cdot X_{i}=0\\}\cap\\{u|u\cdot X_{j}=0\\}$ has measure
0 in $\\{u|u\cdot X_{i}=0\\}$, provided no two rows of $X$ are parellel. Now,
we choose $\epsilon$ to be small such that

$\epsilon=\min_{j\neq i,X_{j}\cdot X_{i}\neq 0}\frac{|c\cdot
X_{j}|}{2|X_{i}\cdot X_{j}|}\ >0.$

and take two points $c+\epsilon X_{i}$, $c-\epsilon X_{i}$. Now, for the $i$th
hyperplane,

$(c+\epsilon X_{i})\cdot X_{i}>0,\quad(c-\epsilon X_{i})\cdot X_{i}<0,$

and for all other hyperplanes $j\neq i$,

$\epsilon|X_{i}\cdot X_{j}|\leq\frac{1}{2}|c\cdot X_{j}|,$

thus the sign of $(c+\epsilon X_{i})\cdot X_{j},c\cdot X_{j},(c-\epsilon
X_{i})\cdot X_{j}$ are identical. This means the hyperplane patterns of
$c+\epsilon X_{i}$ and $c-\epsilon X_{i}$ differ only for the $i$th plane,
meaning we have found two planes $D_{1,i},D_{2,i}$ such that
$|D_{1,i}-D_{2,i}|=diag(e_{i}).$ Now, define
$\tilde{D}_{2i-1}=D_{1,i},\tilde{D}_{2i}=D_{2,i}$ for $i\in[n]$, and choose
$u_{i}$ vectors such that

$(Xu_{i})[i,1]=y[i,1]$

where the notation $A[i,j]$ denotes the $i$th row, $j$th column of $A$. We can
always choose such a vector, as we can choose arbitrary vector $v$ and scale
$c_{i}$ until it matches $c_{i}(Xv)[i,1]=y[i,1]$. Hence, we have found such
$\tilde{D}$s that we proposed earlier. ∎

######  Proposition 8.

(Proposition 3.2. of the paper) Suppose we sampled

$\tilde{P}=2\kappa\log(\frac{n}{\delta})$

hyperplane arrangement patterns, provided that $\mathcal{M}$ is invertible.
Then, with probability at least $1-\delta$, there exists
$u_{1},u_{2},...,u_{\tilde{P}}$ satisfying

$\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}=y.$

###### Proof.

Think of $X_{i}=\tilde{D}_{i}XX^{T}\tilde{D}_{i}$ as a random independent
series of symmetric real $n\times n$ matrices. Also, we know that for any
vector $u\in\mathbb{R}^{n}$,

$\sqrt{u^{T}X_{i}u}\leq\lambda_{max}(XX^{T})\lVert\tilde{D}_{i}u\rVert_{2}\leq\lambda_{max}(XX^{T})\lVert
u\rVert_{2},$

hence we know that for all $X_{i}$s,
$X_{i}\preccurlyeq\lambda_{max}(XX^{T})I$. Now, from Lemma 3, take $\delta=1$.
Then, we obtain

$\mathbb{P}(\lambda_{min}(\sum_{i=1}^{\tilde{P}}X_{i})\leq 0)\leq
ne^{-\mu_{min}/2\lambda_{max}(XX^{T})}$

where $\mu_{min}=\tilde{P}\lambda_{min}(\mathcal{M})$. Hence, when we plug in

$\tilde{P}=2\kappa\log(\frac{n}{\delta}),$

we can see that
$\mathbb{P}(\lambda_{min}(\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})\leq
0)\leq\delta$, and $\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i}$ is
invertible with probability $1-\delta$.

At last, consider the augmented matrix
$\mathcal{X}=[\tilde{D}_{1}X|\tilde{D}_{2}X|...|\tilde{D}_{\tilde{P}}X]$,
which is a $n\times\tilde{P}d$ matrix. As
$\mathcal{X}\mathcal{X}^{T}=\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i}$
is invertible, we can see that $\mathcal{X}$ has $n$ nonzero singular values,
hence has rank $n$. This means that the column space of
$[\tilde{D}_{1}X|\tilde{D}_{2}X|...|\tilde{D}_{\tilde{P}}X]$ also has rank
$n$, and we can find vectors $u_{1},u_{2},...,u_{\tilde{P}}$ that satisfies

$\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}=y$

for any given $y\in\mathbb{R}^{n}$. ∎

The two propositions directly lead to the following corollary.

######  Corollary 4.

(Corollary 3.3. of the paper) Suppose $p_{0}^{*}$ and $p_{1}^{*}$ are
solutions to the unconstrained problem that uses all possible hyperplane
arrangement patterns and its randomized relaxation, respectively, and the
regularization $\beta=0$. Also, suppose $\tilde{P}\geq
2\kappa\log(\frac{n}{\delta})$. Then, $p_{0}^{*}=p_{1}^{*}=0$ with probability
at least $1-\delta$.

###### Proof.

From Proposition 1, we can find $v_{1},v_{2},...,v_{2n}$ that satisfies

$\sum_{i=1}^{2n}D^{\prime}_{i}Xv_{i}=y$

for specific $D^{\prime}_{i}$s. Hence, for the unconstrained problem with all
possible hyperplane arrangements, we can choose $u_{i}$s to be $u_{i}=v_{i}$
if $D_{i}=D^{\prime}_{i}$, $u_{i}=0$ otherwise to perfectly fit a given vector
$y\in\mathbb{R}^{n}$. Also, from Proposition 2, we can fit a given vector $y$
with probabillity at least $1-\delta$ when we sample hyperplane arrangement
patterns more than $2\kappa\log(\frac{n}{\delta})$ times. Hence, with
probability at least $1-\delta$, we know that $p_{1}^{*}=0$. ∎

######  Theorem 8.

(Theorem 3.4. of the paper) Suppose

$p^{*}=\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2}^{2}.$ (10)

Then, with probability at least $1-\delta$ there exists scalars
$C_{1},C_{2}>0$ that satisfies

$\frac{C_{1}}{\tilde{P}}\leq p^{*}\leq\frac{C_{2}}{\tilde{P}},$

provided that $\tilde{P}\geq 12\kappa\log(\frac{2n}{\delta})$ and
$\mathcal{M}$ is invertible.

###### Proof.

Solving the $L_{2}$ regularized problem (10) is equivalent to solving

$\min_{u_{i}\in\mathbb{R}^{d},w}\frac{1}{2}\lVert
w-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2}^{2}.$ (11)

subject to

$w=\sum_{i=1}^{\tilde{P}}D_{i}Xu_{i}.$

The lagrangian of problem (11) becomes

$L(u,w,\lambda)=\frac{1}{2}\lVert
w-y\rVert_{2}^{2}+\lambda^{T}(w-\sum_{i=1}^{\tilde{P}}D_{i}Xu_{i})+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2}^{2}.$

As the constraint is linear equality and the objective is convex with respect
to the arguments, strong duality holds and

$p^{*}=\min_{u_{i}\in\mathbb{R}^{d},w\in\mathbb{R}^{n}}\max_{\lambda\in\mathbb{R}^{n}}L(u_{i},w,\lambda)=\max_{\lambda\in\mathbb{R}^{n}}\min_{u_{i}\in\mathbb{R}^{d},w\in\mathbb{R}^{n}}L(u_{i},w,\lambda).$

For a given $\lambda$, we can optimize for $u_{i}$ and $w$ to minimize
$L(u_{i},w,\lambda)$, where we get $w=y-\lambda$ and
$u_{i}=\frac{1}{\beta}X^{T}\tilde{D}_{i}\lambda$. Substituting leads to

$p^{*}=\max_{\lambda\in\mathbb{R}^{n}}-\frac{1}{2}\lVert\lambda\rVert_{2}^{2}+\lambda^{T}y-\frac{1}{2\beta}\lambda^{T}\big{(}\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i}\big{)}\lambda.$

Now, let’s write
$\frac{1}{\tilde{P}}\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i}=\mathcal{M}_{\tilde{P}}$.
Then, the dual problem can be simplified as

$p^{*}=\max_{\lambda\in\mathbb{R}^{n}}-\frac{1}{2\beta}\lambda^{T}(\beta
I+\tilde{P}\mathcal{M}_{\tilde{P}})\lambda+\lambda^{T}y$

and the optimum $p^{*}$ is given as

$p^{*}=\frac{\beta}{2}y^{T}(\beta I+\tilde{P}\mathcal{M}_{\tilde{P}})^{-1}y.$

When $\tilde{P}\geq 12\kappa\log(\frac{2n}{\delta})$, by Lemma 3 we can see
that

$\mathbb{P}\bigg{(}\lambda_{min}(\mathcal{M}_{\tilde{P}})\geq\frac{\lambda_{min}(\mathcal{M})}{2}\bigg{)}\geq
1-\frac{\delta}{2}$

and

$\mathbb{P}\bigg{(}\lambda_{max}(\mathcal{M}_{\tilde{P}})\leq\frac{3\lambda_{max}(\mathcal{M})}{2}\bigg{)}\geq
1-\frac{\delta}{2}.$

Hence, with probability at least $1-\delta$, we can see that

$(\beta+\frac{\tilde{P}}{2}\lambda_{\min}(\mathcal{M}))I\preccurlyeq\tilde{P}\mathcal{M}_{\tilde{P}}+\beta
I\preccurlyeq(\beta+\frac{3\tilde{P}}{2}\lambda_{\max}(\mathcal{M}))I$

and we can find $\mathcal{R}_{1},\mathcal{R}_{2}>0$ that satisfies

$\mathcal{R}_{1}\tilde{P}I\preccurlyeq\tilde{P}\mathcal{M}_{\tilde{P}}+\beta
I\preccurlyeq\mathcal{R}_{2}\tilde{P}I.$

An example is $\mathcal{R}_{1}=\frac{\lambda_{\min}(\mathcal{M})}{2}$,
$\mathcal{R}_{2}=\frac{3\lambda_{\min}(\mathcal{M})}{2}+1$, provided that
$\tilde{P}$ is larger than $\beta$. This means that

$\frac{\beta\lVert y\rVert_{2}^{2}}{2\mathcal{R}_{2}\tilde{P}}\leq
p^{*}\leq\frac{\beta\lVert y\rVert_{2}^{2}}{2\mathcal{R}_{1}\tilde{P}},$

and take $C_{1}=\frac{\beta\lVert
y\rVert_{2}^{2}}{2\mathcal{R}_{2}},C_{2}=\frac{\beta\lVert
y\rVert_{2}^{2}}{2\mathcal{R}_{1}}$ to finish the proof. ∎

######  Proposition 9.

(Proposition 3.5. of the paper) Suppose

$p_{1}^{*}=\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2},$

and $\tilde{P}\geq 8\kappa\log(\frac{n}{\delta})$. Then with probability at
least $1-\delta$,

$p_{1}^{*}\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}},$

provided that $\mathcal{M}$ is invertible.

###### Proof.

We know that

$\displaystyle p_{1}^{*}$
$\displaystyle=\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2}$
$\displaystyle=\min_{\kappa_{i}\in\mathbb{R},u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}(\kappa_{i}\lVert
u_{i}\rVert_{2}^{2}+\frac{1}{\kappa_{i}})$
$\displaystyle=\min_{\kappa_{i}\in\mathbb{R}}\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}(\kappa_{i}\lVert
u_{i}\rVert_{2}^{2}+\frac{1}{\kappa_{i}}).$

With the same idea from the proof of Equation 10, we can see that when
$\kappa_{i}$s are given, the dual problem becomes

$\max_{\lambda\in\mathbb{R}^{n}}-\frac{1}{2\beta}\lambda^{T}(\beta
I+\sum_{i=1}^{\tilde{P}}\frac{1}{\kappa_{i}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})\lambda+\lambda
y,$

and the inner minimization problem has the minimum

$\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}(\kappa_{i}\lVert
u_{i}\rVert_{2}^{2}+\frac{1}{\kappa_{i}})=\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}\frac{1}{\kappa_{i}}+\frac{\beta}{2}y^{T}(\beta
I+\sum_{i=1}^{\tilde{P}}\frac{1}{\kappa_{i}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})^{-1}y.$

Hence, we can see that

$\displaystyle p_{1}^{*}$
$\displaystyle=\min_{\kappa_{i}\in\mathbb{R}}\frac{\beta}{2}\sum_{i=1}^{\tilde{P}}\frac{1}{\kappa_{i}}+\frac{\beta}{2}y^{T}(\beta
I+\sum_{i=1}^{\tilde{P}}\frac{1}{\kappa_{i}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})^{-1}y$
$\displaystyle\leq\frac{\beta}{2}\min_{\kappa\in\mathbb{R}}y^{T}(\beta
I+\frac{\kappa}{\tilde{P}}\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})^{-1}y+\kappa$
$\displaystyle\leq\frac{\beta}{2}\min_{\kappa\in\mathbb{R}}\frac{y^{T}(\frac{1}{\tilde{P}}\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})^{-1}y}{\kappa}+\kappa$
$\displaystyle\leq\beta\sqrt{y^{T}(\frac{1}{\tilde{P}}\sum_{i=1}^{\tilde{P}}D_{i}XX^{T}D_{i})^{-1}y}$
$\displaystyle\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\lambda_{\min}(\mathcal{M})}$

Where the last inequality follows from matrix Chernoff that with probability
at least $1-\delta$, the minimum eigenvalue

$\lambda_{\min}(\frac{1}{\tilde{P}}\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}XX^{T}\tilde{D}_{i})\geq\frac{\lambda_{\min}(\mathcal{M})}{2}.$

∎

######  Proposition 10.

(Proposition 3.6. of the paper) Suppose

$p_{0}^{*}=\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{P}D_{i}Xu_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{P}\lVert
u_{i}\rVert_{2}.$

Here $D_{i}$s are all possible hyperplane arrangement patterns. Also, write
$\mathcal{M}_{i}=D_{i}XX^{T}D_{i}$. Then,

$G\beta\frac{\lVert y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}\leq
p_{0}^{*},$

where

$G=1-\frac{\beta}{2\max_{i\in[P]}\sqrt{y^{T}\mathcal{M}_{i}y}}$

###### Proof.

Let’s think of the dual problem of the original optimization problem. The
lagrangian $L(u_{i},w,\lambda)$ is given as

$L(u_{i},w,\lambda)=\frac{1}{2}\lVert
w-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2}+\lambda^{T}(w-\sum_{i=1}^{\tilde{P}}D_{i}Xu_{i}),$

and the dual problem is $\max_{\lambda}\min_{u_{i},w}L(u_{i},w,\lambda)$. As
there is only a linear equality constraint and strong duality holds, we can
see that

$p_{0}^{*}=\max_{\lambda}\min_{u_{i},w}\frac{1}{2}\lVert
w-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}\lVert
u_{i}\rVert_{2}+\lambda^{T}(w-\sum_{i=1}^{\tilde{P}}D_{i}Xu_{i}).$

When $\lambda$ is fixed, the inner minimization problem can be solved as:

i) If $\lVert X^{T}D_{i}\lambda\rVert_{2}>\beta$ for some $i$: Take
$u_{i}=CX^{T}D_{i}\lambda$ and send $C$ to infinity to obtain $-\infty$ as the
solution to the inner minimization problem.

ii) If $\lVert X^{T}D_{i}\lambda\rVert_{2}\leq\beta$ for all $i$: Each
$u_{i}=0$ when the inner minimization problem is solved, due to Cauchy-
Schwartz and

$\beta\lVert u_{i}\rVert_{2}\geq\lVert X^{T}D_{i}\lambda\rVert_{2}\lVert
u_{i}\rVert_{2}\geq\lambda^{T}D_{i}Xu_{i}$

holds for all $u_{i}\in\mathbb{R}^{d}$. Also, $w=y-\lambda$ should hold, and
the objective becomes maximizing
$-\frac{1}{2}\lVert\lambda\rVert_{2}^{2}+\lambda^{T}y$.

From i), ii), we can see that the dual problem becomes

$\max_{\lambda}-\frac{1}{2}\lVert\lambda\rVert_{2}^{2}+\lambda^{T}y$

subject to

$\lVert X^{T}D_{i}\lambda\rVert_{2}\leq\beta\quad\forall i\in[P].$

Now, let’s find the maximal scaling coefficient $k$ and the corresponding
$\lambda_{k}=ky$ that meets all the constraints. For that $\lambda$, it is
clear that
$p_{0}^{*}\geq-\frac{1}{2}\lVert\lambda_{k}\rVert_{2}^{2}+\lambda_{k}^{T}y$.
When we substitute $ky$ to $\lambda$, we get the constraint of $k$ for each
$i$:

$k\lVert X^{T}D_{i}y\rVert_{2}\leq\beta,\quad
k\leq\frac{\beta}{\sqrt{y^{T}D_{i}XX^{T}D_{i}y}}$

must hold. When we write $D_{i}XX^{T}D_{i}=\mathcal{M}_{i}$, $k$ should
satisfy

$k\leq\frac{\beta}{\sqrt{y^{T}\mathcal{M}_{i}y}}$

for all $i\in[\tilde{P}]$. Choose
$k=\frac{\beta}{\max_{i}\sqrt{y^{T}\mathcal{M}_{i}y}}$. Substituting $ky$ to
the dual problem leads

$p_{0}^{*}\geq-\frac{\beta^{2}\lVert
y\rVert_{2}^{2}}{2\max_{i}\\{y^{T}\mathcal{M}_{i}y\\}}+\frac{\beta\lVert
y\rVert_{2}^{2}}{\max_{i}\\{\sqrt{y^{T}\mathcal{M}_{i}y}\\}}=G\frac{\beta\lVert
y\rVert_{2}^{2}}{\max_{i}\\{\sqrt{y^{T}\mathcal{M}_{i}y}\\}}.$

At last, we know that $\mathcal{M}_{i}\preccurlyeq\lambda_{\max}(XX^{T})I$ for
all $i\in[P]$. Hence, $y^{T}\mathcal{M}_{i}y\leq\lambda_{\max}(XX^{T})\lVert
y\rVert_{2}^{2}$ for all $i\in[P]$ and

$p_{0}^{*}\geq G\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}.$

∎

######  Corollary 5.

(Corollary 3.7. of the paper) Suppose further that $\lVert
y\rVert_{2}\sqrt{\lambda_{\min}(\mathcal{M})}\geq\beta$. Then,

$\frac{\beta}{2}\frac{\lVert y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}\leq
p_{1}^{*}.$

###### Proof.

We know that
$G=1-\frac{\beta}{2\max_{i\in[P]}\sqrt{y^{T}\mathcal{M}_{i}y}}\geq
1-\frac{\beta}{2\lVert
y\rVert_{2}\sqrt{\lambda_{\min}(\mathcal{M})}}\geq\frac{1}{2}.$ ∎

######  Theorem 9.

(Theorem 3.8. of the paper) Suppose $p_{0}^{*}$ and $p_{1}^{*}$ are solutions
to the unconstrained problem that uses all possible hyperplane arrangement
patterns and its randomized relaxation, respectively. Suppose further that
$\tilde{P}\geq 8\kappa\log(\frac{n}{\delta})$ and $\mathcal{M}$ is invertible.
We have

$0\leq p_{1}^{*}-p_{0}^{*}\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}}$

and

$p_{0}^{*}\leq p_{1}^{*}\leq\frac{\sqrt{2\kappa}}{G}p_{0}^{*}$

with probability at least $1-\delta$.

###### Proof.

The two inequalities directly follow from Proposition 3 and Proposition 4 ∎

######  Proposition 11.

$\mathcal{M}_{ij}=\\{\frac{1}{2}-\frac{1}{2\pi}\arccos(\frac{x_{i}\cdot
x_{j}}{\lVert x_{i}\rVert_{2}\lVert x_{j}\rVert_{2}})\\}(x_{i}\cdot x_{j})$
for all $i,j\in[n]$. Here, $x\cdot y$ denotes the innter product between $x$
and $y$.

###### Proof.

First, recall that $\mathcal{M}=\mathbb{E}_{g\sim
N(0,I_{d})}[diag[\mathbbm{1}(Xg\geq 0)]XX^{T}diag[\mathbbm{1}(Xg\geq 0)]]$.
Hence, $\mathcal{M}_{ij}$ has the expression

$\mathcal{M}_{ij}=\mathbb{P}(x_{i}\cdot g\geq 0)\mathbb{P}(x_{j}\cdot g\geq
0)(x_{i}\cdot x_{j}).$

We know that for fixed $x_{i},x_{j}$, the orthant probability is given as

$\mathbb{P}(x_{i}\cdot g\geq 0)\mathbb{P}(x_{j}\cdot g\geq
0)=\frac{1}{2}-\frac{1}{2\pi}\arccos(\frac{x_{i}\cdot x_{j}}{\lVert
x_{i}\rVert_{2}\lVert x_{j}\rVert_{2}}),$

where $g\sim\mathcal{N}(0,I_{d})$. This directly implies the claim. ∎

######  Theorem 10.

(Theorem 3.9. of the paper) Let each row $x_{i}$ of $X$ is sampled i.i.d. from
$N(0,I_{d})$. Furthermore, suppose $c,\delta>0$ are given and $n/d=c$ is
fixed. There exists $d_{1}$ such that if $d\geq d_{1}$, with probability at
least $1-\delta-\frac{1}{(2n)^{8}}$, we have

$\lambda_{min}(\mathcal{M})\geq\frac{d}{10}.$

###### Proof.

Note that $f(t)=(\frac{1}{2}-\frac{1}{2\pi}\arccos(t))t$ is not differentiable
at a neighborhood around $t=1$. Hence, we need $\tilde{f}_{\epsilon}$, a
$C^{1}$ approximator of $f$, defined as

$\tilde{f}_{\epsilon}(x)=\begin{cases}f(x)\quad when\quad x\leq 1-\epsilon\\\
f^{\prime}(1-\epsilon)x+f(1-\epsilon)-(1-\epsilon)f^{\prime}(1-\epsilon)\quad
when\quad x\geq 1-\epsilon.\end{cases}$

Let $\tilde{M}$ be a matrix that satisfies

$[\tilde{M}]_{ij}=\tilde{f}_{\epsilon_{0}}(\frac{x_{i}\cdot x_{j}}{d}),$

where $\epsilon_{0}=\frac{1}{100c}\leq\frac{1}{100}$. From Lemma 6, there
exists $d_{2}$ such that for every $d\geq d_{2}$,

$\lambda_{min}(\tilde{M})\geq\lambda_{min}(\tilde{M}^{\prime})-\epsilon_{0}.$

Now, there exists $d_{3}$ such that when $d\geq d_{3}$, we can decompose
$\frac{\mathcal{M}}{d}$ as

$\frac{\mathcal{M}}{d}=\tilde{M}+diag(\frac{\lVert
x_{i}\rVert_{2}^{2}}{2d}-\tilde{f}_{\epsilon_{0}}(\frac{\lVert
x_{i}\rVert_{2}^{2}}{d}))+\mathcal{M}_{e},$

where

$[\mathcal{M}_{e}]_{ij}=\begin{cases}0\quad if\quad i=j\\\
\frac{1}{2\pi}(-\arccos({\frac{x_{i}\cdot x_{j}}{\lVert x_{i}\rVert_{2}\lVert
x_{j}\rVert_{2}}})+\arccos(\frac{x_{i}\cdot x_{j}}{d}))\frac{x_{i}\cdot
x_{j}}{d}\quad if\quad i\neq j.\end{cases}$

with probability at least $1-\delta/2$. Such $d_{3}$ exists as for each $i\neq
j$, $\frac{x_{i}\cdot x_{j}}{d}\sim\mathcal{N}(0,\frac{1}{d})$ and

$\mathbb{P}(\frac{|x_{i}\cdot x_{j}|}{d}\geq\frac{1}{2})\leq
2\exp(-\frac{d}{8}),$

meaning that for all $i\neq j$,

$\mathbb{P}(\max_{i\neq j}{\frac{|x_{i}\cdot x_{j}|}{d}}\leq\frac{1}{2})\geq
1-2n^{2}\exp(-\frac{d}{8})=1-2c^{2}d^{2}\exp(-\frac{d}{8}),$

and choose $d_{3}$ large enough so that
$2c^{2}d^{2}\exp(-\frac{d}{8})\leq\frac{\delta}{2}$. This means with
probability at least $1-\delta/2$, $f(\frac{x_{i}\cdot
x_{j}}{d})=\tilde{f}_{\epsilon_{0}}(\frac{x_{i}\cdot x_{j}}{d})$ for all
$i\neq j$, meaning that the off-diagonal entries of $\frac{\mathcal{M}}{d}$
can be decomposed to $\tilde{M}$ and $\mathcal{M}_{e}$. Now, Weyl’s inequality
leads to

$\displaystyle\frac{\lambda_{\min}(\mathcal{M})}{d}\geq\lambda_{\min}(\tilde{\mathcal{M}})+\min(\frac{\lVert
x_{i}\rVert_{2}^{2}}{2d})-\max(\tilde{f}_{\epsilon_{0}}(\frac{\lVert
x_{i}\rVert_{2}^{2}}{d}))-\lVert\mathcal{M}_{e}\rVert_{F}.$ (12)

Then, from the concentration inequality of Chi-square random variables, we
know that there exists $d_{4}$ such that for all $d\geq d_{4}$,

$(1-\epsilon_{0})d\leq(1-\frac{\epsilon_{0}}{\log 2n})d\leq\lVert
x_{i}\rVert_{2}^{2}\leq(1+\frac{\epsilon_{0}}{\log
2n})d\leq(1+\epsilon_{0})d,\quad\forall\quad i\in[n],$ (13)

with probability at least $1-\delta/2$. Hence, when
$d\geq\max\\{d_{2},d_{3},d_{4}\\},$ both inequalities (12) and (13) satisfy
with probability at least $1-\delta$. Use (12) and (13) to get

$\displaystyle\frac{\lambda_{\min}(\mathcal{M})}{d}$
$\displaystyle\geq\lambda_{\min}(\tilde{\mathcal{M}})+\min(\frac{\lVert
x_{i}\rVert_{2}^{2}}{2d})-\max(\tilde{f}_{\epsilon_{0}}(\frac{\lVert
x_{i}\rVert_{2}^{2}}{d}))-\lVert\mathcal{M}_{e}\rVert_{F}$
$\displaystyle\geq\lambda_{\min}(\tilde{\mathcal{M}})+\frac{1}{2}(1-\epsilon_{0})-\tilde{f}_{\epsilon_{0}}(1+\epsilon_{0})-\lVert\mathcal{M}_{e}\rVert_{F}$
$\displaystyle\geq\lambda_{\min}(\tilde{\mathcal{M}^{\prime}})-\epsilon_{0}+\frac{1}{2}(1-\epsilon_{0})-\tilde{f}_{\epsilon_{0}}(1+\epsilon_{0})-\lVert\mathcal{M}_{e}\rVert_{F}.$

The last inequality follows from the fact that $d\geq d_{2}$. We also know
that

$\lambda_{\min}(\tilde{M}^{\prime})\geq(\tilde{f}_{\epsilon_{0}}(1)-\tilde{f}_{\epsilon_{0}}(0)-\tilde{f}_{\epsilon_{0}}^{\prime}(0)),$

as both $11^{T},XX^{T}$ are not invertible. Moreover,
$\tilde{f}_{\epsilon_{0}}(0)=f(0)=0$,
$\tilde{f}_{\epsilon_{0}}^{\prime}(0)=f^{\prime}(0)=1/4$. Substitute to get

$\displaystyle\frac{\lambda_{\min}(\mathcal{M})}{d}$
$\displaystyle\geq\tilde{f}_{\epsilon_{0}}(1)-\frac{1}{4}-\epsilon_{0}+\frac{1}{2}(1-\epsilon_{0})-\tilde{f}_{\epsilon_{0}}(1+\epsilon_{0})-\lVert\mathcal{M}_{e}\rVert_{F}.$
$\displaystyle\geq\frac{1}{4}-\frac{3}{2}\epsilon_{0}-\epsilon_{0}f^{\prime}(1-\epsilon_{0})-\lVert\mathcal{M}_{e}\rVert_{F}$
$\displaystyle\geq 0.209-\lVert\mathcal{M}_{e}\rVert_{F}.$

At last, upper bounding $\lVert\mathcal{M}_{e}\rVert_{F}$ would be enough to
prove the claim. First, we know that when $|u|,|v|\leq\frac{2}{3}$, we know
that

$|\arccos(u)-\arccos(v)|\leq|\arccos^{\prime}(2/3)||u-v|\leq 2|u-v|.$

This leads to

$\displaystyle\lVert\mathcal{M}_{e}\rVert_{F}$
$\displaystyle\leq\frac{1}{2\pi}\sqrt{\sum_{i=1}^{n}\sum_{j\neq
i}|-\arccos({\frac{x_{i}\cdot x_{j}}{\lVert x_{i}\rVert_{2}\lVert
x_{j}\rVert_{2}}})+\arccos(\frac{x_{i}\cdot x_{j}}{d})|^{2}|\frac{x_{i}\cdot
x_{j}}{d}|^{2}}$
$\displaystyle\leq\frac{2}{2\pi}\sqrt{\sum_{i=1}^{n}\sum_{j\neq
i}|-{\frac{x_{i}\cdot x_{j}}{\lVert x_{i}\rVert_{2}\lVert
x_{j}\rVert_{2}}}+\frac{x_{i}\cdot x_{j}}{d}|^{2}|\frac{x_{i}\cdot
x_{j}}{d}|^{2}}$
$\displaystyle\leq\frac{\epsilon_{0}}{\pi(1-\epsilon_{0})\log(2n)}\sqrt{\sum_{i=1}^{n}\sum_{j\neq
i}|\frac{x_{i}\cdot x_{j}}{d}|^{4}}$

with probability at least $1-\delta$. We know from the concentration
inequality of maximum of absolute values that

$\mathbb{P}(\max_{i\leq j}|x_{i}\cdot x_{j}|\leq 4\sqrt{2\log(2n)}\lVert
x_{i}\rVert_{2})\geq 1-\frac{2}{(2n)^{9}},\quad\forall\quad i\in[n].$ (14)

Hence, with probability at least $1-\delta-\frac{1}{(2n)^{8}},$ we know that
both (13) and

$\max_{i\leq j}|x_{i}\cdot x_{j}|\leq 4\sqrt{2\log(2n)\cdot(1+\epsilon_{0})d}$

holds. Hence,

$\displaystyle\lVert\mathcal{M}_{e}\rVert_{F}$
$\displaystyle\leq\frac{\epsilon_{0}}{\pi(1-\epsilon_{0})\log(2n)}\sqrt{\sum_{i=1}^{n}\sum_{j\neq
i}|\frac{x_{i}\cdot x_{j}}{d}|^{4}}$
$\displaystyle\leq\frac{\epsilon_{0}}{\pi(1-\epsilon_{0})d^{2}\log(2n)}\sqrt{\sum_{i=1}^{n}\sum_{j\neq
i}|x_{i}\cdot x_{j}|^{4}}$
$\displaystyle\leq\frac{\epsilon_{0}n}{\pi(1-\epsilon_{0})d^{2}\log(2n)}\cdot
32\log(2n)(1+\epsilon_{0})d$
$\displaystyle\leq\frac{32\epsilon_{0}(1+\epsilon_{0})c}{\pi(1-\epsilon_{0})}$
$\displaystyle\leq\frac{32}{100\pi}\frac{101}{99}\leq 0.104$

Hence, we know that with probability at least $1-\delta-\frac{1}{(2n)^{8}}$,

$\lambda_{\min}(\mathcal{M})\geq\frac{d}{10}$

holds, provided that $d\geq d_{2},d_{3},d_{4}$. Choose
$d_{1}=\max\\{d_{2},d_{3},d_{4}\\}$. ∎

######  Corollary 6.

(Corollary 3.10. of the paper) When the conditions of Theorem 6 holds, with
probability at least $1-\delta-\frac{1}{(2n)^{8}}$, we have

$\kappa\leq 20(\sqrt{c}+1)^{2}.$

Moreover, when we sample $\tilde{P}\geq
160(\sqrt{c}+1)^{2}\log(\frac{n}{\delta^{\prime}})$ hyperplane arrangement
patterns, we have

$p_{1}^{*}\leq\tilde{p}_{1}^{*}\leq\frac{2\sqrt{10}}{G}(\sqrt{c}+1)p_{1}^{*}$

with probability at least $1-\delta-\delta^{\prime}-\frac{1}{(2n)^{8}}.$

###### Proof.

We know that

$\sqrt{\lambda_{max}(XX^{T})}\leq\sqrt{2}(\sqrt{c}+1)\sqrt{d},$

holds with high probability. Also, from Theorem 6, we know that

$\sqrt{\lambda_{min}(\mathcal{M})}\geq\frac{1}{\sqrt{10}}\sqrt{d}.$

with probability at least $1-\delta-\frac{1}{(2n)^{8}}$. Combine the two
results to obtain the wanted upper bound on $\kappa$. Also, we know that with
probability at least $1-\delta^{\prime}$,

$p_{1}^{*}\leq\tilde{p}_{1}^{*}\leq\frac{\sqrt{2\kappa}}{G}p_{1}^{*},$

from Theorem 5. Directly using the upper bound on $\kappa$ leads to the
following result. ∎

##  Appendix C Proofs in Section 4.

######  Proposition 12.

(Proposition 4.2. of the paper) For subsampled hyperplane arrangement patterns
$\tilde{D}_{1},\tilde{D}_{2},...,\tilde{D}_{\tilde{P}}$, let

$p_{0}^{*}=\min_{u_{i},v_{i}\in\mathcal{K}_{\tilde{D}_{i}}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}),$ (15)
$p_{1}^{*}=\min_{w_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xw_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}\lVert
w_{i}\rVert_{2},$ (16)

and $\mathcal{K}_{\tilde{D}_{i}}=\\{u|(2\tilde{D}_{i}-I)Xu\geq 0\\}$. Suppose
problem (16) has solutions $w_{i}^{*}$ for $i\in[\tilde{P}]$, and let

$C=\max_{i\in[\tilde{P}]}C(\mathcal{K}_{\tilde{D}_{i}},\frac{w_{i}^{*}}{\lVert
w_{i}^{*}\rVert_{2}}).$

Then, $p_{0}^{*}\leq Cp_{1}^{*}$ holds.

###### Proof.

For the optimum $w_{i}^{*}$ of problem (16), decompose $w_{i}^{*}$ into
$u_{i}^{*},v_{i}^{*}$ such that $\lVert u_{i}^{*}\rVert_{2}+\lVert
v_{i}^{*}\rVert_{2}$ is minimal, $u_{i}^{*},v_{i}^{*}\in K_{i}$ and
$u_{i}^{*}-v_{i}^{*}=w_{i}^{*}$. Then,

$\frac{\lVert u_{i}^{*}\rVert_{2}+\lVert v_{i}^{*}\rVert_{2}}{\lVert
w_{i}^{*}\rVert_{2}}\leq C(\mathcal{K}_{\tilde{D}_{i}},\frac{w_{i}^{*}}{\lVert
w_{i}^{*}\rVert_{2}})\leq C$

and when we substitute $u_{i}^{*},v_{i}^{*}$ in (2), we can see that the
result would not be greater than $Cp_{1}^{*}$, as the regression loss is
identical and the regularization loss does not blow up $C$ times. Hence, we
may conclude that $p_{0}^{*}\leq Cp_{1}^{*}$. ∎

######  Proposition 13.

(Proposition 4.3. in the paper) Take any unit vector $z$ and a cone
$\mathcal{K}=\\{u|(2D-I)Xu\geq 0\\}$. If there exists a vector $u$ that
satisfies

$\lVert u\rVert_{2}\leq 1,\quad(2D-I)Xu\geq\epsilon\cdot|(2D-I)Xz|,$

we know that

$C(\mathcal{K},z)\leq 1+\frac{1}{\epsilon}.$

###### Proof.

As $(2D-I)Xu\geq\epsilon\cdot|(2D-I)Xz|\geq(2D-I)X(\pm\epsilon z),$ we know
that the vectors $u+\epsilon z,u-\epsilon z\in\mathcal{K}$. Then, the two
vectors

$v_{1}=\frac{1}{2}(\frac{u}{\epsilon}+z),\ \
v_{2}=\frac{1}{2}(\frac{u}{\epsilon}-z).$

become two vectors in $\mathcal{K}$ that satisfy $v_{1}-v_{2}=z$. Hence, the
cone sharpness

$C(\mathcal{K},z)\leq\lVert v_{1}\rVert_{2}+\lVert v_{2}\rVert_{2}\leq
1+\frac{1}{\epsilon}\lVert u\rVert_{2}\leq 1+\frac{1}{\epsilon}.$

where the first inequality follows from the definition of $C(\mathcal{K},z)$,
the second inequality follows from triangular inequality, and the last follows
from the fact that $u$ has norm no greater than 1. ∎

######  Lemma 7.

(Lemma 4.4. in the paper) Suppose $X$ is a $d\times d$ random matrix with
entries i.i.d. and sampled from $\mathcal{N}(0,1)$. Also, suppose
$b\in\mathbb{R}^{d}$ is an arbitrary vector that satisfies $\lVert
b\rVert_{2}\leq 2\sqrt{n},$ and $n/d=c$. Then, there exists a $B>0$ such that
with probability at least $1-8\exp(-Bd)$, there exists a vector that satisfies
$\lVert\lambda\rVert_{2}\leq 5c$ and $X\lambda\geq b$.

###### Proof.

Showing that $\min_{\lambda\in\mathbb{R}^{d}}\ \lVert\lambda\rVert_{2}$
subject to $X\lambda\geq b$ is no larger than $5c$ with high probability is
enough to show the theorem. Also, suppose $\lVert b\rVert_{2}\geq\sqrt{n}$, as
when we prove for $\lVert b\rVert_{2}\geq\sqrt{n}$, the case when $\lVert
b\rVert_{2}\leq\sqrt{n}$ is automatically proved. Denote the optimal
$\lVert\lambda\rVert_{2}=p_{0}$. Then, we know that

$p_{0}=\min_{\lambda\in\mathbb{R}^{d}}\max_{\nu\in\mathbb{R}_{-}^{d}}\lVert\lambda\rVert_{2}+\nu^{T}(X\lambda-b),$

by simply writing the Lagrangian of the problem. Hence, when we write

$\displaystyle\Phi_{0}(X)$
$\displaystyle=\min_{\lambda\in\mathbb{R}^{d}}\max_{\nu\in\mathbb{R}_{-}^{d}}\lVert\lambda\rVert_{2}+\nu^{T}(X\lambda-b)$
$\displaystyle=\max_{\nu\in\mathbb{R}_{-}^{d}}\min_{\lambda\in\mathbb{R}^{d}}\lVert\lambda\rVert_{2}+\nu^{T}(X\lambda-b)$
$\displaystyle=-\min_{\nu\in\mathbb{R}_{-}^{d}}\max_{\lambda\in\mathbb{R}^{d}}-\lVert\lambda\rVert_{2}-\nu^{T}(X\lambda-b)$
$\displaystyle=-\min_{\nu\in\mathbb{R}_{+}^{d}}\max_{\lambda\in\mathbb{R}^{d}}-\lVert\lambda\rVert_{2}+\nu^{T}(X\lambda-b),$

and write

$\Phi(X)=\min_{\nu\in\mathbb{R}_{+}^{d}}\max_{\lambda\in\mathbb{R}^{d}}-\lVert\lambda\rVert_{2}+\nu^{T}(X\lambda-b),$

we know that when

$\phi(g,h)=\min_{\nu\in\mathbb{R}_{+}^{d}}\max_{\lambda\in\mathbb{R}^{d}}\lVert\nu\rVert_{2}g^{T}\lambda+\lVert\lambda\rVert_{2}h^{T}\nu-\lVert\lambda\rVert_{2}-\nu^{T}b,$
$\mathbb{P}(\Phi_{0}(X)\leq-M)=\mathbb{P}(\Phi(X)\geq
M)=1-\mathbb{P}(\Phi(X)\leq M)\geq 1-2\mathbb{P}(\phi(g,h)\leq M)$

from Gordon’s minimax theorem. Here, $g,h\in\mathbb{R}^{d}$ and entries of
$g,h\sim\mathcal{N}(0,1)$.

Hence, finding an almost sure lower bound of $\phi(g,h)$ and negating it gives
an almost sure upper bound of $\Phi_{0}(X)$.

Now, let’s solve $\phi(g,h)$. We can rewrite the formula of $\phi(g,h)$ as

$\phi(g,h)=\min_{\nu\in\mathbb{R}_{+}^{d}}\max_{\lambda\in\mathbb{R}^{d}}(h^{T}\nu-1)\lVert\lambda\rVert_{2}+\lVert\nu\rVert_{2}g^{T}\lambda-\nu^{T}\mathbf{1},$

and when $h^{T}\nu-1\leq-\lVert g\rVert_{2}\lVert\nu\rVert_{2}$, the
maximization over $\lambda$ is 0, where otherwise it is $\infty$. Hence, we
can write $\phi(g,h)$ as

$\phi(g,h)=\min_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{d}\\\
h^{T}\nu+\lVert g\rVert_{2}\lVert\nu\rVert_{2}\leq
1\end{subarray}}-\nu^{T}b=-\max_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{d}\\\
h^{T}\nu+\lVert g\rVert_{2}\lVert\nu\rVert_{2}\leq 1\end{subarray}}\nu^{T}b.$

Hence, finding an almost sure upper bound of

$\max_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{d}\\\ h^{T}\nu+\lVert
g\rVert_{2}\lVert\nu\rVert_{2}\leq 1\end{subarray}}\nu^{T}b$

gives an almost sure upper bound of $\Phi_{0}(X)$. Now, we know that

$\displaystyle\max_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{d}\\\
h^{T}\nu+\lVert g\rVert_{2}\lVert\nu\rVert_{2}\leq 1\end{subarray}}\nu^{T}b$
$\displaystyle=-\min_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{d}\\\
h^{T}\nu+\lVert g\rVert_{2}\lVert\nu\rVert_{2}\leq 1\end{subarray}}-\nu^{T}b$
$\displaystyle=-\min_{\nu\in\mathbb{R}^{d}}\max_{\begin{subarray}{c}\lambda_{1}\in\mathbb{R}_{+}^{d}\\\
\mu_{1}\geq
0\end{subarray}}-\nu^{T}b-\lambda_{1}^{T}\nu+\mu_{1}(h^{T}\nu+\lVert
g\rVert_{2}\lVert\nu\rVert_{2}-1)$
$\displaystyle=-\min_{\nu\in\mathbb{R}^{d}}\max_{\begin{subarray}{c}\lambda_{1}\in\mathbb{R}_{+}^{d}\\\
\mu_{1}\geq 0\end{subarray}}(\mu_{1}h-\lambda_{1}-b)^{T}\nu+\mu_{1}\lVert
g\rVert_{2}\lVert\nu\rVert_{2}-\mu_{1}$
$\displaystyle=-\max_{\begin{subarray}{c}\lambda_{1}\in\mathbb{R}_{+}^{d}\\\
\mu_{1}\geq
0\end{subarray}}\min_{\nu\in\mathbb{R}^{d}}(\mu_{1}h-\lambda_{1}-b)^{T}\nu+\mu_{1}\lVert
g\rVert_{2}\lVert\nu\rVert_{2}-\mu_{1}$
$\displaystyle=-\max_{\begin{subarray}{c}\lambda_{1}\in\mathbb{R}_{+}^{d},\mu_{1}\geq
0\\\ \mu_{1}\lVert
g\rVert_{2}\geq\lVert\mu_{1}h-\lambda_{1}-b\rVert_{2}\end{subarray}}-\mu_{1}.$

Hence, for any pair $\mu_{0}\geq 0,\lambda_{0}\in\mathbb{R}_{+}^{d}$ that
satisfies $\mu_{0}\lVert
g\rVert_{2}\geq\lVert\mu_{0}h-\lambda_{0}-b\rVert_{2}$, we know that

$\max_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{d}\\\ h^{T}\nu+\lVert
g\rVert_{2}\lVert\nu\rVert_{2}\leq 1\end{subarray}}\nu^{T}b\leq\mu_{0}.$

Choose entries of $\lambda_{0}$ as

$\lambda_{0,i}=\begin{cases}c\quad if\quad h_{i}>0\\\ 0\quad if\quad
h_{i}<0\end{cases},$

and choose

$\mu_{0}=\frac{\lVert\lambda_{0}+b\rVert_{2}^{2}}{(\lambda_{0}+b)^{T}h}.$

Then, from Hoeffding’s inequality, we have a constant $A_{1}>0$ that satisfies
with probability at least $1-\exp(-A_{1}d)$,

$0.4c^{2}d\leq\lVert\lambda_{0}\rVert_{2}^{2}\leq 0.6c^{2}d,\quad
0.3cd\leq(\sqrt{\frac{2}{\pi}}\frac{1}{2}-0.1)cd\leq\lambda_{0}^{T}h\leq(\sqrt{\frac{2}{\pi}}\frac{1}{2}+0.1)cd\leq
0.5cd.$

The two inequalities hold with high probability as they are concentration
inequalities of $Ber(\frac{1}{2})$ and absolute of normal, respectively. Also,
we know that there is a constant $A_{2}>0$ that satisfies with probability at
least $1-\exp(-A_{2}d)$,

$-0.1cn\leq b^{T}\lambda_{0}\leq 0.1cn,\quad-0.1n\leq b^{T}h\leq 0.1n,$

since $\lVert b\rVert_{2}\leq 2\sqrt{n}$ and $h,\lambda_{0}$ are independent
with $b$. At last, we have $n\leq\lVert b\rVert_{2}^{2}\leq 4n$. Combining
these inequalities, with probability at least $1-\exp(-A_{1}d)-\exp(-A_{2}d)$,
we have

$(0.2c+1)n\leq\lVert\lambda_{0}+b\rVert_{2}^{2}\leq(0.8c+4)n,\quad
0.2n\leq(\lambda_{0}+b)^{T}h\leq 0.6n.$

This means $\frac{c}{3}\leq\mu_{0}\leq 5c$ with probability at least
$1-\exp(-A_{1}d)-\exp(-A_{2}d)$.

Also, the chosen $\mu_{0},\lambda_{0}$ are both positive. At last, we know
that from the concentration inequality of chi-square distributions,

$\mathbb{P}(d-\epsilon d\leq\lVert g\rVert_{2}^{2}\leq d+\epsilon d)\geq
1-2\exp(-\frac{\epsilon^{2}}{4}d),\quad\mathbb{P}(d-\epsilon d\leq\lVert
h\rVert_{2}^{2}\leq d+\epsilon d)\geq 1-2\exp(-\frac{\epsilon^{2}}{4}d).$

Hence, with probability at least $1-4\exp(-\frac{\epsilon^{2}}{4}d)$, $\lVert
h\rVert_{2}^{2}-\lVert g\rVert_{2}^{2}\leq 2\epsilon d$. Now,

$\displaystyle\mu_{0}\lVert
g\rVert_{2}\geq\lVert\mu_{0}h-\lambda_{0}-b\rVert_{2}$
$\displaystyle\iff(\lVert g\rVert_{2}^{2}-\lVert
h\rVert_{2}^{2})\mu_{0}^{2}+2(\lambda_{0}+b)^{T}h\mu_{0}-\lVert\lambda_{0}+b\rVert_{2}^{2}\geq
0$ $\displaystyle\iff(\lVert g\rVert_{2}^{2}-\lVert
h\rVert_{2}^{2})\mu_{0}^{2}+\lVert\lambda_{0}+b\rVert_{2}^{2}\geq 0.$

Use $\mu_{0}\leq 5c$, $\lVert\lambda_{0}+b\rVert_{2}^{2}\geq(0.2c+1)n$ to
obtain that if $(\lVert h\rVert_{2}^{2}-\lVert
g\rVert_{2}^{2})\leq\frac{1}{125}d$, $\mu_{0}\lVert
g\rVert_{2}\geq\lVert\mu_{0}h-\lambda_{0}-b\rVert_{2}$ holds. Take
$\epsilon=\frac{1}{250}$ to find $A_{3}>0$ that with probability at least
$1-\exp(-A_{3}d)$, $\mu_{0},\lambda_{0}$ are pairs that satisfy $\mu_{0}\lVert
g\rVert_{2}\geq\lVert\mu_{0}h-\lambda_{0}-b\rVert_{2}$, which means

$\max_{\begin{subarray}{c}\nu\in\mathbb{R}_{+}^{n}\\\ h^{T}\nu+\lVert
g\rVert_{2}\lVert\nu\rVert_{2}\leq 1\end{subarray}}\nu^{T}b\leq 5c,$

with probability at least $1-\exp(-A_{1}d)-\exp(-A_{2}d)-\exp(-A_{3}d)$. This
result along with

$\mathbb{P}(\Phi_{0}(X)\leq-M)=\mathbb{P}(\Phi(X)\geq
M)=1-\mathbb{P}(\Phi(X)\leq M)\geq 1-2\mathbb{P}(\phi(g,h)\leq M)$

when $M=-5c$ yields the proposed theorem. ∎

######  Theorem 11.

(Theorem 4.5. of the paper) Let $p_{c}$ be the probability that the $0.75d-th$
absolute value of $n$ samples sampled uniformly at random from
$\mathcal{N}(0,1)$ is less than $d/2n=1/2c$. Also, let $p_{n}$ be the
probability that $\lVert\tilde{X}z\rVert_{2}\leq 2\sqrt{n}$ and $d\geq d_{2}$,
where $d_{2}$ is the threshold that we can guarantee the existence of such
$\lambda\in\mathbb{R}^{d_{2}}$ from Lemma 2 with probability at least
$1-\delta^{\prime\prime}$.

Then, with probability at least
$1-p_{c}-p_{n}-2/(2n)^{9}-\delta^{\prime\prime}$, we know that

$C(\mathcal{K},z)\leq 1+80c^{2}\sqrt{\log(2n)},$

Here $\mathcal{K}$ is the rotated cone $\\{u|\tilde{X}u\geq 0\\}$, and all
elements of the first column of $\tilde{X}$ are positive.

###### Proof.

Before proving, we can see that both $p_{c}$ and $p_{n}$ approaches zero as
$n,d\rightarrow\infty$. The first property holds from the cumulative
distribution of Gaussian, and the second property holds from Marchenko-
Pasteur. Also, let’s rearrange the rows of $\tilde{X}$ so that the rows of
$\tilde{X}$ satisfies the following:

1) For the $i$-th row $\tilde{X}_{i}$, if $|\tilde{X}_{i}\cdot z|\geq
4\sqrt{c}$, put it on the first $d/4$ rows. We know that there are at most
$d/4$ such rows, as $\lVert Xz\rVert_{2}\leq 2\sqrt{n}$.
2) Then, sort the rows with the first column. Note that if $i\geq d$,
$\tilde{X}[i,1]\geq 1/2c$ with high probability.

To prove the theorem, we will find appropriate $u$, $\epsilon$ for Proposition
6 to prove the theorem. First, from Lemma 2, we can choose a vector
$\lambda_{0}\in\mathbb{R}^{d-1}$ that satisfies

$\lVert\lambda_{0}\rVert_{2}\leq
5c,\quad\tilde{X}[1,(d-1);2,d]\lambda_{0}\geq|\tilde{X}[1:d-1;1:d]z|,$

as $\lVert\tilde{X}[1:d-1;1:d]z\rVert_{2}\leq\lVert\tilde{X}z\rVert_{2}\leq
2\sqrt{n}$. Here, $X[a,b;c,d]$ denotes the submatrix of row $a$ to $b$, column
$c$ to $d$. For that $\lambda_{0}$, take

$u=(1-\frac{1}{256c^{2}\log(2n)})\cdot
e_{1}+\frac{1}{16c\sqrt{\log(2n)}}\cdot\frac{1}{5c}\cdot\begin{bmatrix}0\\\
\lambda_{0}\end{bmatrix}.$

At last, take $\epsilon=\frac{1}{80c^{2}\sqrt{\log(2n)}}$. We want to see that
with high probability, the chosen $u,\epsilon$ satisfies the conditions for
Proposition 6. First, it is clear that $\lVert u\rVert_{2}\leq 1$, as

$\lVert
u\rVert_{2}^{2}=(1-\frac{1}{256c^{2}\log(2n)})^{2}+\frac{1}{256c^{2}\log(2n)}(\frac{1}{5c}\lVert\lambda_{0}\rVert_{2})^{2}\leq(1-\frac{1}{256c^{2}\log(2n)})^{2}+\frac{1}{256c^{2}\log(2n)}\leq
1.$

The last inequality follows from $256c^{2}\log(2n)\geq 1$. By verifying the
last condition, the second condition follows. Now, let’s divide the problem
into cases.

If $i<d$, for the $i-th$ row $\tilde{X}_{i}$ of $\tilde{X}$,

$\tilde{X}_{i}\cdot
u\geq(1-\frac{1}{256c^{2}\log(2n)})\tilde{X}[i,1]+\frac{1}{80c^{2}\sqrt{\log(2n)}}\tilde{X}[i;2,d]\cdot\lambda_{0}\geq\frac{1}{80c^{2}\sqrt{\log(2n)}}|\tilde{X}_{i}\cdot
z|,$

which follows directly from the construction of $\lambda_{0}$.

If $i\geq d$, we obtain

$\displaystyle\tilde{X}_{i}\cdot u$
$\displaystyle\geq(1-\frac{1}{256c^{2}\log(2n)})\tilde{X}[i,1]+\frac{1}{80c^{2}\sqrt{\log(2n)}}\tilde{X}[i;2,d]\cdot\lambda_{0}$
$\displaystyle\geq(1-\frac{1}{256c^{2}\log(2n)})\frac{1}{2c}+\frac{1}{80c^{2}\sqrt{\log(2n)}}\tilde{X}[i;2,d]\cdot\lambda_{0},$

with probability $1-p_{c}$. Also, we know that the inner product between a
unit vector and a random normal vector follows $\mathcal{N}(0,1)$, hence for
$i\geq d$, the variables $\tilde{X}[i;2,d]\cdot\lambda_{0}$ can be understood
as i.i.d. random variables sampled from
$\mathcal{N}(0,\lVert\lambda_{0}\rVert_{2}^{2})$. From the concentration
inequality of the maximum of absolute values, we know that

$\mathbb{P}[\max_{i\geq d}|\tilde{X}[i;2,d]\cdot\lambda_{0}|\geq
20c\sqrt{2\log(2n)}]\leq 2\cdot\frac{1}{(2n)^{9}}.$

Hence, with probability at least $1-p_{c}-\frac{2}{(2n)^{9}}$, we can see that

$\displaystyle\tilde{X}_{i}\cdot u$
$\displaystyle\geq(1-\frac{1}{256c^{2}\log(2n)})\frac{1}{2c}+\frac{1}{80c^{2}\sqrt{\log(2n)}}\tilde{X}[i;2,d]\cdot\lambda_{0}$
$\displaystyle\geq(1-\frac{1}{256c^{2}\log(2n)})\frac{1}{2c}-\frac{1}{4c}$
$\displaystyle\geq\frac{255}{512c}-\frac{1}{4c}\approx\frac{0.249}{c}\geq\frac{1}{17c\sqrt{c}}|X_{i}\cdot
z|,$

for all $i\geq d$. The last inequality follows from rearrangement of the rows
of $\tilde{X}$, and for $i\geq d$, $|\tilde{X}_{i}\cdot z|\leq 4\sqrt{c}$.
This means that for all $i\in[n]$,

$\tilde{X}_{i}\cdot u\geq\frac{1}{80c^{2}\sqrt{\log(2n)}}|\tilde{X}_{i}\cdot
z|$

holds, and $\tilde{X}u\geq\epsilon|\tilde{X}_{i}\cdot z|$. This shows that the
chosen $u,\epsilon$ satisfy the last condition for Proposition 6, and the
second condition. The result directly follows from Proposition 6. ∎

######  Corollary 7.

For subsampled hyperplane arrangement patterns
$\tilde{D}_{1},\tilde{D}_{2},...,\tilde{D}_{\tilde{P}}$, let

$p_{0}^{*}=\min_{u_{i},v_{i}\in\mathcal{K}_{\tilde{D}_{i}}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}),$ (17)
$p_{1}^{*}=\min_{w_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{\tilde{P}}\tilde{D}_{i}Xw_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{\tilde{P}}\lVert
w_{i}\rVert_{2}.$ (18)

Furthermore, assume (A1) and $d\geq d_{2}$ as defined in Theorem 11. Then, we
have $p_{1}^{*}\leq p_{0}^{*}\leq(1+80c^{2}\sqrt{\log 2n})p_{1}^{*}$ with
probability at least $1-p_{c}-p_{n}-2/(2n)^{9}-\delta^{\prime\prime}$.

###### Proof.

The first inequality follows from triangular inequality, and the second from
Proposition 5. ∎

##  Appendix D Proof of the Main Theorems

######  Theorem 12.

(Theorem 2.1. of the paper) Let the optimal value of the 2-layer ReLU network
as

$p^{*}=\min_{u,\alpha}\frac{1}{2}\lVert\sum_{j=1}^{2m}(Xu_{j})_{+}\alpha_{j}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{j=1}^{2m}(\lVert
u_{j}\rVert_{2}^{2}+\lVert\alpha_{j}\rVert_{2}^{2}),$

and the convex optimization problem with random hyperplane arrangement
patterns as

$\tilde{p}^{*}=\min_{u_{i},v_{i}\in\mathcal{K}_{\tilde{D}_{i}}}\frac{1}{2}\lVert\sum_{i=1}^{m/2}\tilde{D}_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i=1}^{m/2}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}).$

Suppose that $m\geq\max\\{m^{*},320(\sqrt{c}+1)^{2}\log(\frac{n}{\delta})\\}$,
where $m^{*}$ defined as in Section 2.3. Moreover, assume $n/d=c$ is fixed and
the entries of $X$ are i.i.d. $\sim\mathcal{N}(0,1)$. At last, let $d\geq
d_{3}$ so that both Corollary 7 and Proposition 3 holds with probability at
least $1-\delta-\delta^{\prime}$ and $G<1/2$. Then,

$p^{*}\leq\tilde{p}^{*}\leq 2\sqrt{20}(\sqrt{c}+1)(1+80c^{2}\sqrt{\log(2n)})\
p^{*},$

holds with probability at least $1-\delta-\delta^{\prime}$.

###### Proof.

Let’s denote

$p_{2}^{*}=\min_{u_{i},v_{i}\in\mathcal{K}_{\tilde{D}_{i}}}\frac{1}{2}\lVert\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i=1}^{P}(\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}),$
$p_{3}^{*}=\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{P}D_{i}Xu_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{P}\lVert
u_{i}\rVert_{2},$

where $D_{1},D_{2},...,D_{P}$ are all possible hyperplane arrangement
patterns, and

$p_{4}^{*}=\min_{u_{i}\in\mathbb{R}^{d}}\frac{1}{2}\lVert\sum_{i=1}^{m/2}\tilde{D}_{i}Xu_{i}-y\rVert_{2}^{2}+\beta\sum_{i=1}^{m/2}\lVert
u_{i}\rVert_{2},$

where $\tilde{D}_{1},\tilde{D}_{2},...,\tilde{D}_{m/2}$ are randomly sampled
hyperplane arrangement patterns. First, from preliminaries, we know that
$p^{*}=p_{2}^{*}$. It is clear that $p_{2}^{*}\leq\tilde{p}^{*}$, as we use
less hyperplane arrangement patterns during approximation. Moreover, we know
that $p_{3}^{*}\leq p_{2}^{*}$, as $\lVert u_{i}-v_{i}\rVert_{2}\leq\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}$ and $u_{i}-v_{i}$ can represent
arbitrary vector in $\mathbb{R}^{d}$ even with the constraint
$u_{i},v_{i}\in\mathcal{K}_{\tilde{D}_{i}}$. To wrap up, we know that

$p_{3}^{*}\leq p_{2}^{*}=p^{*}\leq\tilde{p}^{*}.$

From Corollary 7 we know that $\tilde{p}^{*}\leq(1+80c^{2}\sqrt{\log 2n})\
p_{4}^{*}$, and we also know from Proposition 4 that $p_{3}^{*}\geq
G\beta\frac{\lVert y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}$. At last, from
Proposition 3, we know that $p_{4}^{*}\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}}$. Hence, we know that

$\displaystyle G\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{\max}(XX^{T})}}\leq p_{3}^{*}\leq
p_{2}^{*}=p^{*}\leq\tilde{p}^{*}$ $\displaystyle\leq(1+80c^{2}\sqrt{\log 2n})\
p_{4}^{*}$ $\displaystyle\leq\sqrt{2}\beta\frac{\lVert
y\rVert_{2}}{\sqrt{\lambda_{min}(\mathcal{M})}}\cdot(1+80c^{2}\sqrt{\log 2n})$
$\displaystyle\leq\frac{\sqrt{2}}{G}\sqrt{\frac{\lambda_{\max}(XX^{T})}{\lambda_{\min}(\mathcal{M})}}\cdot(1+80c^{2}\sqrt{\log
2n})\ p^{*}$
$\displaystyle\leq\frac{\sqrt{20}}{G}(\sqrt{c}+1)(1+80c^{2}\sqrt{\log 2n})\
p^{*},$

which finishes the proof that

$p^{*}\leq\tilde{p}^{*}\leq 2\sqrt{20}(\sqrt{c}+1)(1+80c^{2}\sqrt{\log(2n)})\
p^{*}.$

∎

######  Theorem 13.

(Theorem 2.3. of the paper) Assume (A1) and suppose that
$m\geq\max\\{m^{*},320(\sqrt{c}+1)^{2}\log(n/\delta)\\}$. Then, there exists a
randomized algorithm with $O(d^{3}m^{3})$ complexity that solves problem
$(\ref{nonconvex_original})$ within $O(\sqrt{\log(n)})$ relative optimality
bound.

###### Proof.

Consider the Gaussian relaxation of the convex reformulation with $[m/2]$
hyperplane arrangement patterns. As there are $O(dm)$ variables, we can solve
the problem with $O(d^{3}m^{3})$ complexity using standard interior point
solvers. Moreover, we have the approximation bound of Theorem 1, which leads
to the fact that the solved global minima has $O(\sqrt{\log(2n)})$ guarantees.
At last, we can map the solution $\\{(u_{i}^{*},v_{i}^{*})\\}_{i=1}^{[m/2]}$
to the parameter space of two-layer neural networks with the mapping

$u_{i}^{*}\rightarrow(\frac{u_{i}^{*}}{\sqrt{\lVert
u_{i}^{*}\rVert_{2}}},\sqrt{\lVert
u_{i}^{*}\rVert_{2}}),v_{i}^{*}\rightarrow(\frac{v_{i}^{*}}{\sqrt{\lVert
v_{i}^{*}\rVert_{2}}},-\sqrt{\lVert v_{i}^{*}\rVert_{2}}),$

to find the parameters of the two-layer neural network that has the same loss
function value as the optimal value of the convex problem. Hence, we can find
parameters of two-layer neural network that has $O(\sqrt{\log(n)})$ relative
optimality bound in $O(d^{3}m^{3})$ time. ∎

######  Theorem 14.

(Theorem 2.5. of the paper) Consider the training problem
$\min_{u_{j},\alpha_{j}}\mathcal{L}(u,\alpha),$ where the loss function
$\mathcal{L}$ is given as

$\mathcal{L}(u,\alpha)=\frac{1}{2}\lVert\sum_{j=1}^{m}(Xu_{j})_{+}\alpha_{j}-y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{j=1}^{m}(\lVert
u_{j}\rVert_{2}^{2}+\alpha_{j}^{2}).$

Assume (A1),(A2) and $d\geq d_{3}$ so that Corollary 7 holds with probability
$1-\delta$, and
$m\geq\max{m^{*},320(\sqrt{c}+1)^{2}\log(\frac{n}{\delta^{\prime}})}$. For any
random initialization $\\{u_{i}^{0},\alpha_{i}^{0}\\}_{i=1}^{m}$, suppose
local gradient method converged to a stationary point
$\\{u_{i}^{\prime},\alpha_{i}^{\prime}\\}_{i=1}^{m}$. Then, with probability
at least $1-\delta-\delta^{\prime}$,

$\mathcal{L}(u^{\prime},\alpha^{\prime})\leq
C\sqrt{\log(2n)}\mathcal{L}(u^{*},\alpha^{*}),$

for some $C\geq 1$. Here, $\\{u_{i}^{*},\alpha_{i}^{*}\\}_{i=1}^{m}$ is a
global optimum of $\mathcal{L}(u,\alpha)$.

###### Proof.

We know that for the stationary point
$\\{u_{i}^{\prime},\alpha_{i}^{\prime}\\}_{i=1}^{m}$, we have a corresponding
convex optimization problem

$p^{*}:=\frac{1}{2}\lVert\sum_{i=1}^{m}\tilde{D}_{i}(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i=1}^{m}\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2},$ (19)

where $\tilde{D}_{i}=\mathbbm{1}(Xu_{i}^{\prime}\geq 0)$ and the solution
mapping of the optimal solution $\\{(u_{i}^{*},v_{i}^{*})\\}_{i=1}^{m}$ of the
convex problem and the stationary point given as

$\alpha_{i}^{\prime}=sign(\alpha_{i}^{\prime})\sqrt{\lVert
u_{i}^{*}\rVert_{2}},\quad u_{i}^{\prime}=\frac{u_{i}^{*}}{\sqrt{\lVert
u_{i}^{*}\rVert_{2}}}\mathbbm{1}(\alpha_{i}^{\prime}\geq
0)+\frac{v_{i}^{*}}{\sqrt{\lVert
v_{i}^{*}\rVert_{2}}}\mathbbm{1}(\alpha_{i}^{\prime}<0).$

By (A2), we know that at least half of the hyperplane arrangement patterns are
preserved from $\mathbbm{1}(Xu_{0}\geq 0)$. Let the hyperplane arrangement
patterns be $\tilde{D}_{1},\tilde{D}_{2},...,\tilde{D}_{m/2}$ without loss of
generality. Now, we know that the optimal solution of the problem

$p^{\prime}:=\frac{1}{2}\lVert\sum_{i=1}^{m/2}\tilde{D}_{i}(u_{i}-v_{i})-y\rVert_{2}^{2}+\beta\sum_{i=1}^{m/2}\lVert
u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}$

has $O(\sqrt{\log 2n})$ approximation guarantee with probability at least
$1-\delta-\delta^{\prime}$, and as it is using less hyperplane arrangement
patterns, we know that $p^{*}\leq p^{\prime}$. At last, we know that
$p^{*}=\mathcal{L}(u^{\prime},\alpha^{\prime})$ from solution mapping.
Plugging in $\mathcal{L}(u^{\prime},\alpha^{\prime})$ at $p^{*}$ and using
Theorem 1 on $p^{\prime}$ yields the wanted result. ∎