Convergence Results for Neural Networks via Electrodynamics

arXiv:1702.00458v4 [] 21 Nov 2017

Rina Panigrahy
Google Inc.
Mountain View, CA
rinap@google.com

Ali Rahimi
Google Inc.
Mountain View, CA
arahimi@google.com

Sushant Sachdeva∗
University of Toronto
Toronto, Canada
sachdeva@cs.toronto.edu

Qiuyi Zhang†
University of California Berkeley,
Berkeley, CA
10zhangqiuyi@berkeley.edu
November 22, 2017

Abstract
We study whether a depth two neural network can learn another depth two network using
gradient descent. Assuming a linear output node, we show that the question of whether gradient
descent converges to the target function is equivalent to the following question in electrodynamics:
Given k fixed protons in Rd , and k electrons, each moving due to the attractive force from the
protons and repulsive force from the remaining electrons, whether at equilibrium all the electrons
will be matched up with the protons, up to a permutation. Under the standard electrical force,
this follows from the classic Earnshaw’s theorem. In our setting, the force is determined by
the activation function and the input distribution. Building on this equivalence, we prove the
existence of an activation function such that gradient descent learns at least one of the hidden
nodes in the target network. Iterating, we show that gradient descent can be used to learn the
entire network one node at a time.

1

Introduction

Deep learning has resulted in major strides in machine learning applications including speech
recognition, image classification, and ad-matching. The simple idea of using multiple layers of nodes
with a non-linear activation function at each node allows one to express any function. To learn a
certain target function we just use (stochastic) gradient descent to minimize the loss; this approach
has resulted in significantly lower error rates for several real world functions, such as those in the
above applications. Naturally the question remains: how close are we to the optimal values of
the network weight parameters? Are we stuck in some bad local minima? While there are several
recent works [CHM+ 15, DPG+ 14, Kaw16] that have tried to study the presence of local minima,
the picture is far from clear.
There has been some work on studying how well can neural networks learn some synthetic
function classes (e.g. polynomials [APVZ14], decision trees). In this work we study how well can
neural networks learn neural networks with gradient descent? Our focus here, via the framework of
∗
†

This work was done when the author was a Research Scientist at Google, Mountain View, CA.
Part of this work was done when the author was an intern at Google, Mountain View, CA.

1

proper learning, is to understand if a neural network can learn a function from the same class (and
hence achieve vanishing error).
Specifically, if the target function is a neural network with randomly initialized weights, and we
attempt to learn it using a network with the same architecture, then, will gradient descent converge
to the target function?
Experimental simulations (see Figure 1 and Section 5 for further details) show that for depth
2 networks of different widths, with random network weights, stochastic gradient descent of a
hypothesis network with the same architecture converges to a squared `2 error that is a small
percentage of a random network, indicating that SGD can learn these shallow networks with random
weights. Because our activations are sigmoidal from -1 to 1, the training error starts from a value of
about 1 (random guessing) and diminishes quickly to under 0.002. This seems to hold even when
the width, the number of hidden nodes, is substantially increased (even up to 125 nodes), but depth
is held constant at 2.
In this paper, we attempt to understand this phenomenon theoretically. We prove that, under
some assumptions, depth-2 neural networks can learn functions from the same class with vanishingly
small error using gradient descent.

Figure 1: Test Error of Depth 2 Networks of Varying Width.

1.1

Results and Contributions.

We theoretically investigate the question of convergence for networks of depth two. Our main
conceptual contribution is that for depth 2 networks where the top node is a sum node, the question
of whether gradient descent converges to the desired target function is equivalent to the following
question in electrodynamics: Given k fixed protons in Rd , and k moving electrons, with all the
electrons moving under the influence of the electrical force of attraction from the protons and
repulsion from the remaining electrons, at equilibrium, are all the electrons matched up with all the
fixed protons, up to a permutation?

2

In the above, k is the number of hidden units, d is the number of inputs, the positions of each
fixed charge is the input weight vector of a hidden unit in the target network, and the initial positions
of the moving charges are the initial values of the weight vectors for the hidden units in the learning
network. The motion of the charges essentially tracks the change in the network during gradient
descent. The force between a pair of charges is not given by the standard electrical force of 1/r2
(where r is the distance between the charges), but by a function determined by the activation and
the input distribution. Thus the question of convergence in these simplified depth two networks
can be resolved by studying the equivalent electrodynamics question with the corresponding force
function.
Theorem 1.1 (informal statement of Theorem 2.3). Applying gradient descent for learning the
output of a depth two network with k hidden units with activation σ, and a linear output node, under
squared loss, using a network of the same architecture, is equivalent to the motion of k charges in
the presence of k fixed charges where the force between each pair of charges is given by a potential
function that depends on σ and the input distribution.
Based on this correspondence we prove the existence of an activation function such that the
corresponding gradient descent dynamics under standard Gaussian inputs result in learning at least
one of the hidden nodes in the target network. We then show that this allows us to learn the
complete target network one node at a time. For more realistic activation functions, we only obtain
partial results. We assume the sample complexity is close to its infinite limit.
Theorem 1.2 (informal statement of Theorem 4.1). There is an activation function such that
running gradient descent for minimizing the squared loss along with `2 regularization for standard
Gaussian inputs, at convergence, we learn at least one of the hidden weights of the target neural
network.
We prove that the above result can be iterated to learn the entire network node-by-node using
gradient descent (Theorem 4.6). Our algorithm learns a network with the same architecture and
number of hidden nodes as the target network, in contrast with several existing improper learning
results.
In the appendix, we show some weak results for more practical activations. For the sign activation,
we show that for the loss with respect to a single node, the only local minima are at the hidden
target nodes with high probability if the target network has a randomly picked top layer. For the
polynomial activation, we derive a similar result under the assumption that the hidden nodes are
orthonormal.
Name of Activation
Almost λ-harmonic
Sign
Polynomial

Potential (Φ(θ, w))
Complicated (see Lem 4.2)
1 − π2 cos−1 (θT w)
(θT w)m

Convergence?
Yes, Thm 4.6
Yes for d = 2, Lem G.2
Yes, for orthonormal wi . Lem G.3

Table 1: Activation, Potentials, and Convergence Results Summary

1.2

Intuition and Techniques.

Note that for the standard electric potential function given by Φ = 1/r where r is the distance
between the charges, it is known from Earnshaw’s theorem that an electrodynamic system with some
3

fixed protons and some moving electrons is at equilibrium only when the moving electrons coincide
with the fixed protons. Given our translation above between electrodynamic systems and depth 2
networks (Section 2), this would imply learnability of depth 2 networks under gradient descent under
`2 loss, if the activation function corresponds to the electrostatic potential. However, there exists no
activation function σ corresponding to this Φ.
The proof of Earnshaw’s theorem is based on the fact that the electrostatic potential is harmonic,
i.e, its Laplacian (trace of its Hessian) is identically zero. This ensures that at every critical point,
there is direction of potential reduction (unless the hessian is identically zero). We generalize
these ideas to potential functions that are eigenfunctions of the Laplacians, λ-harmonic potentials
(Section 3). However, these potentials are unbounded. Subsequently, we construct a non-explicit
activation function such that the corresponding potential is bounded and is almost λ-harmonic,
i.e., it is λ-harmonic outside a small sphere (Section 4). For this activation function, we show at
a stable critical point, we must learn at least one of the hidden nodes. Gradient descent (possibly
with some noise, as in the work of Ge et al. [GHJY15]) is believed to converge to stable critical
points. However, for simplicity, we descend along directions of negative curvature to escape saddle
points. Our activation lacks some regularity conditions required in [GHJY15]. We believe the results
in [JGN+ 17] can be adapted to our setting to prove that perturbed gradient descent converges to
stable critical points.
There is still a large gap between theory and practice. However, we believe our work can offer
some theoretical explanations and guidelines for the design of better activation functions for gradientbased training algorithms. For example, better accuracy and training speed were reported when
using the newly discovered exponential linear unit (ELU) activation function in [CUH15, SKS+ 16].
We hope for more theory-backed answers to these and many other questions in deep learning.

1.3

Related Work.

If the activation functions are linear or if some independence assumptions are made, Kawaguchi
shows that the only local minima are the global minima [Kaw16]. Under the spin-glass and other
physical models, some have shown that the loss landscape admits well-behaving local minima that
occur usually when the overall error is small [CHM+ 15, DPG+ 14]. When only training error is
considered, some have shown that a global minima can be achieved if the neural network contains
sufficiently many hidden nodes [SC16]. Recently, Daniely has shown that SGD learns the conjugate
kernel class [Dan17]. Under simplifying assumptions, some results for learning ReLU’s with gradient
descent are given in [Tia17, BG17]. Our research is inspired by [APVZ14], where the authors show
that for polynomial target functions, gradient descent on neural networks with one hidden layer
converges to low error, given a large number of hidden nodes, and under complex perturbations,
there are no robust local minima. Even more recently, similar results about the convergence of SGD
for two-layer neural networks have been established for a polynomial activation function under a
more complex loss function [GLM17]. And in [LY17], they study the same problem as ours with
the RELU activation and where lower layer of the network is close to identity and the upper layer
has weights all one. This corresponds to the case where each electron is close to a distinct proton –
under these assumptions they show that SGD learns the true network.
Under worst case assumptions, there has been hardness results for even simple networks. A neural
network with one hidden unit and sigmoidal activation can admit exponentially many local minima
[AHW96]. Backprogration has been proven to fail in a simple network due to the abundance of bad
local minima [BRS89]. Training a 3-node neural network with one hidden layer is NP-complete
[BR88]. But, these and many similar worst-case hardness results are based on worst case training
data assumptions. However, by using a result in [KS06] that learning a neural network with threshold
4

activation functions is equivalent to learning intersection of halfspaces, several authors showed that
under certain cryptographic assumptions, depth-two neural networks are not efficiently learnable
with smooth activation functions [LSSS14, ZLWJ15, ZLJ16].
Due to the difficulty of analysis of the non convex gradient descent in deep learning, many
have turned to improper learning and the study of non-gradient methods to train neural networks.
Janzamin et. al use tensor decomposition methods to learn the shallow neural network weights,
provided access to the score function of the training data distribution [JSA15]. Eigenvector and
tensor methods are also used to train shallow neural networks with quadratic activation functions in
[LSSS14]. Combinatorial methods that exploit layerwise correlations in sparse networks have also been
analyzed provably in [ABGM14]. Kernel methods, ridge regression, and even boosting were explored
for regularized neural networks with smooth activation functions in [SSSS11, ZLWJ15, ZLJ16].
Non-smooth activation functions, such as the ReLU, can be approximated by polynomials and are
also amenable to kernel methods[GKKT16]. These methods however are very different from the
simple popular SGD.

2
2.1

Deep Learning, Potentials, and Electron-Proton Dynamics
Preliminaries.

We will work in the space M = Rd . We denote the gradient and Hessian as ∇Rd f and ∇2Rd f
respectively. The Laplacian is defined as ∆Rd f = Tr(∇2Rd f ). If f is multivariate with variable xi ,
then let fxi be a restriction of f onto the variable xi with all other variables fixed. Let ∇xi f, ∆xi f
to be the gradient and Laplacian, respectively, of fxi with respect to xi . Lastly, we say x is a critical
point of f if ∇f does not exist or ∇f = 0.
We focus on learning depth two networks with a linear activation on the output node. If the
network takes inputs x ∈ Rd (say from some distribution D), then the network output, denoted f (x) is
d
d
d
a sum over k = poly(d) hidden units with weight vectors
Pkwi ∈ R , activation σ(x, w) : R × R → R,
and output weights bi ∈ R. Thus, we can write f (x) = i=1 bi σ(x, wi ). We denote this concept class
Cσ,k . Our hypothesis concept class is also Cσ,k .
P
Let a = (a1 , ..., ak ) and θ = (θ1 , ..., θk ); similarly for b, w and our guess is fˆ(x) = ki=1 ai σ(x, θi ).
We define Φ, the potential function corresponding to the activation σ, as
Φ(θ, w) = E [σ(X, θ)σ(X, w)].
X∼D

We work directly with the true squared loss error L(a, θ) = Ex∼D [(f − fˆ)2 ]. To simplify L, we
re-parametrize a by −a and expand.

!2 
k
k
X
X
L(a, θ) = E 
ai σ(X, θi ) +
bi σ(X, wi ) 
X∼D

=

k X
k
X

i=1

i=1

ai aj Φ(θi , θj ) + 2ai bj Φ(θi , wj ) + bi bj Φ(wi , wj ),

(1)

i=1 j=1

Given D, the activation function σ, and the loss L, we attempt to show that we can use some variant
of gradient descent to learn, with high probability, an -approximation of wj for some (or all) j.
Note that our loss is jointly convex, though it is quadratic in a.
In this paper, we restrict our attention to translationally invariant activations and potentials.
Specifically, we may write Φ = h(θ − w) for some function h(x). Furthermore, a translationally
invariant function Φ(r) is radial if it is a function of r = kx − yk.
5

Remark: Translationally symmetric potentials satisfy Φ(θ, θ) is a positive constant. We normalize
Φ(θ, θ) = 1 for the rest of the paper.
We assume that our input distribution D = N (0, Id×d ) is fixed as the standard Gaussian in Rd .
This assumption is not critical and a simpler distribution might lead to better bounds. However, for
arbitrary distributions, there are hardness results for PAC-learning halfspaces [KS06].
We call a potential function realizable if it corresponds to some activation σ. The following
theorem characterizes realizable translationally invariant potentials under standard Gaussian inputs.
Proofs and a similar characterization for rotationally invariant potentials can be found in Appendix B
.
Theorem 2.1. Let M = Rd and Φ is square-integrable and F(Φ) is integrable. Then, Φ is
realizable under standardpGaussian inputs if F(Φ)(ω) ≥ 0 and the corresponding activation is
T
σ(x) = (2π)d/4 ex x/4 F−1 ( F(Φ))(x), where F is the generalized Fourier transform in Rd .

2.2

Electron-Proton Dynamics

By interpreting the pairwise potentials as electrostatic attraction potentials, we notice that our
dynamics is similar to electron-proton type dynamics under potential Φ, where wi are fixed point
charges in Rd and θi are moving point charges in Rd that are trying to find wi . The total force on
each charge is the sum of the pairwise forces, determined by the gradient of Φ. We note that standard
dynamics interprets the force between particles as an acceleration vector. In gradient descent, it is
interpreted as a velocity vector.
Definition 2.2. Given a potential Φ and particle locations θ1 , ..., θk ∈ Rd along with their respective
charges a1 , ..., ak ∈ R. We define Electron-Proton Dynamics under Φ with some subset S ⊆ [k]
of fixed particles to be the solution (θ1 (t), ..., θk (t)) to the following system of differential equations:
For each pair (θi , θj ), there is a force from θj exerted on θi that is given by Fi (θj ) = ai aj ∇θi Φ(θi , θj )
and
dθi X
−
=
Fi (θj )
dt
j6=i

for all i 6∈ S, with θi (0) = θi . For i ∈ S, θi (t) = θi .
For the following theorem, we assume that θ is fixed.
Theorem 2.3. Let Φ be a symmetric potential and L be as in (1). Running continuous gradient
descent on 12 L with respect to θ, initialized at (θ1 , ..., θk ) produces the same dynamics as ElectronProton Dynamics under 2Φ with fixed particles at w1 , ..., wk with respective charges b1 , .., bk and
moving particles at θ1 , ..., θk with respective charges a1 , ..., ak .

3

Earnshaw’s Theorem and Harmonic Potentials

When running gradient descent on a non-convex loss, we often can and do get stuck at a local minima.
In this section, we use second-order information to deduce that for certain classes of potentials, there
are no spurious local minima. The potentials In this section are often unbounded and un-realizable.
However, in the next section, we apply insights developed here to derive similar convergence results
for approximations of these potentials.
Earnshaw’s theorem in electrodynamics shows that there is no stable local minima for electronproton dynamics. This hinges on the property that the electric potential Φ(θ, w) = kθ − wk2−d , d 6= 2
is harmonic, with d = 3 in natural setting. If d = 2, we instead have Φ(θ, w) = − ln(kθ − wk). First,
6

we notice that this is a symmetric loss, and our usual loss in (1) has constant terms that can be
dropped to further simplify.
L(a, θ) = 2

k X
X

ai aj Φ(θi , θj ) + 2

i=1 i<j

k X
k
X

ai bj Φ(θi , wj )

(2)

i=1 j=1

Definition 3.1. Φ(θ, w) is a harmonic potential on Ω if ∆θ Φ(θ, w) = 0 for all θ ∈ Ω, except
possibly at θ = w.
Definition 3.2. Let Ω ⊆ Rd and consider a function f : Ω → R. A critical point x∗ ∈ Ω is a local
minimum if there exists  > 0 such that f (x∗ + v) ≥ f (x∗ ) for all kvk ≤ . It is a strict local
minimum if the inequality is strict for all kvk ≤ .
Fact 3.3. Let x∗ be a critical point of a function f : Ω → R such that f is twice differentiable at x∗ .
Then, if x∗ is a local minimum then λmin (∇2 f (x∗ )) ≥ 0. Moreover, if λmin (∇2 f (x∗ )) > 0, then x∗
is a strict local minimum.
Note that if λmin (∇2 f (x∗ )) < 0 then moving along the direction of the corresponding eigenvector
decreases f locally. If Φ is harmonic then it can be shown the trace of its Hessian is 0 so if there is
any non zero eigenvalue then at least one eigenvalue is negative. This idea results in the following
known theorem (see full proof in supplementary material) that is applicable to the electric potential
function 1/r in 3-dimensions since is harmonic. It implies that a configuration of n electrons and n
protons cannot be in a strict local minimum even if one of the mobile charges is isolated (however
note that this potential function goes to ∞ at r = 0 and may not be realizable).
Theorem 3.4. (Earnshaw’s Theorem. See [AKN85]) Let M = Rd and let Φ be harmonic and L be
as in (2). Then, L admits no differentiable strict local minima.
Note that the Hessian of a harmonic potential can be identically zero. To avoid this possibility
we generalize harmonic potentials.

3.1

λ-Harmonic Potentials

In order to relate our loss function with its Laplacian, we consider potentials that are non-negative
eigenfunctions of the Laplacian operator. Since the zero eigenvalue case simply gives rise to harmonic
potentials, we restrict our attention to positive eigenfunctions.
Definition 3.5. A potential Φ is λ-harmonic on Ω if there exists λ > 0 such that for every θ ∈ Ω,
∆θ Φ(θ, w) = λΦ(θ, w), except possibly at θ = w.
Note that there are realizable versions of these potentials; for example Φ(a, b) = e−ka−bk1 in R1 .
In the next section, we construct realizable potentials that are λ-harmonic almost everywhere except
when θ and w are very close.
Theorem 3.6. Let Φ be λ-harmonic and L be as in (1). Then, L admits no local minima (a, θ),
except when L(a, θ) = L(0, θ) or θi = wj for some i, j.
Proof. Let (a, θ) be a critical point of L. On the contrary, we assume that θi 6= wj for all i, j.
WLOG, we can partition [k] into S1 , ..., Sr such that for all u ∈ Si , v ∈ Sj , we have θu = θv
iff i = j. Let S1 = {θ1 , . . . , θl }. We consider changing all θ1 , . . . , θl by the same v and define
H(a, v) = L(a, θ1 + v, ..., θl + v, θl+1 . . . , θk ).
7

P
P
∂L
The optimality conditions on a are 0 = ∂a
= 2 j aj Φ(θi , θj ) + 2 kj=1 bj Φ(θi , wj ). Thus, by the
i
definition of λ-harmonic potentials, we may differentiate as θi 6= wj and compute the Laplacian as


l
k
k
X
X
X
∆v H = λ
ai 2
bj Φ(θi , wj ) + 2
aj Φ(θi , θj )
i=1

=λ

l
X
i=1

j=1


ai −2

l
X

j=l+1


aj Φ(θi , θj ) = −2λ

j=1

l
X
i=1


ai 

l
X


aj  = −2λ

j=1

l
X

!2
ai

i=1

Pl
If
i=1 ai 6= 0, then we conclude that the Laplacian is strictly
P negative, so we are not at a
local minimum. Similarly, we can conclude that for each Si , u∈Si au = 0. In this case, since
Pk
i=1 ai σ(θi , x) = 0, L(a, θ) = L(0, θ).

4

Realizable Potentials with Convergence Guarantees

In this section, we derive convergence guarantees for realizable potentials that are almost λ-harmonic,
specifically, they are λ-harmonic outside of a small neighborhood around the origin. First, we prove
the existence of activation functions such that the corresponding potentials are almost λ-harmonic.
Then, we reason about the Laplacian of our loss, as in the previous section, to derive our guarantees.
We show that at a stable minima, each of the θi is close to some wj in the target network. We may
end up with a many to one mapping of the learned hidden weights to the true hidden weights, instead
of a bijection. To make sure that kak remains controlled throughout the optimization process, we
add a quadratic regularization term to L and instead optimize G = L + kak2 .
Our optimization procedure is a slightly altered version of gradient descent, where we incorportate
a second-order method (which we call Hessian descent as in Algorithm 1) that is used when the
gradient is small and progress is slow. The descent algorithm (Algorithm 2) allows us to converge to
points with small gradient and small negative curvature. Namely, for smooth functions, in poly(1/)
iterations, we reach a point in MG, , where
n
o
MG, = x ∈ M k∇G(x)k ≤  and λmin (∇2 G(x)) ≥ −
We show that if (a, θ) is in MG, for  small, then θi is close to wj for some j. Finally, we show how
to initialize (a(0) , θ (0) ) and run second-order GD to converge to MG, , proving our main theorem.
Algorithm 1 x = HD(L, x0 , T, α)
Input: L : M → R; x0 ∈ M; T ∈ N; α ∈ R
Initialize x ← x0
for i = 1 to T do
Find unit eigenvector vmin corresponding to λmin (∇2 f (x))
β ← −αλmin (∇2 f (x))sign(∇f (x)T vmin )
x ← x + βvmin
Theorem 4.1. Let M = Rd for d ≡ 3 mod 4 and k = poly(d). For all  ∈ (0, 1), we can construct
an activation σ such that if w1 , ..., wk ∈ Rd with wi randomly chosen from wi ∼ N (0, O(d log d)Id×d )
and b1 , ..., bk be randomly chosen at uniform from [−1, 1], then with high probability, we can choose an
initial point (a(0) , θ (0) ) such that after running SecondGD (Algorithm 2) on the regularized objective
G(a, θ) for at most (d/)O(d) iterations, there exists an i, j such that kθi − wj k < .
8

We start by stating a lemma concerning the construction of an almost λ-harmonic function on
The construction is given in Appendix B and uses a linear combination of realizable potentials
that correspond to an activation function of the indicator function of a n-sphere. By using Fourier
analysis and Theorem 2.1, we can finish the construction of our almost λ-harmonic potential.
Rd .

Lemma 4.2. Let M = Rd for d ≡ 3 mod 4. Then, for any  ∈ (0, 1), we can construct a radial
activation σ (r) such that the corresponding radial potential Φ (r) is λ-harmonic for r ≥ .
Furthermore, we have Φ (d−1) (r) ≥ 0 for all r > 0, Φ (k) (r) ≥ 0, and Φ (k+1) (r) ≤ 0 for all r > 0
and d − 3 ≥ k ≥ 0 even.
(k)
When λ = 1, |Φ (r)| ≤ O((d/)2d ) for all 0 ≤ k ≤ d−1. And when r ≥ , Ω(e−r r2−d (d/)−2d ) ≤
Φ (r) ≤ O((1 + r)d e1−r (r)2−d ) and Ω(e−r r1−d (d/)−2d ) ≤ |Φ0 (r)| ≤ O((d + r)(1 + r)d e1−r r1−d )
Our next lemma use the almost λ-harmonic properties to show that at an almost stationary
point of G, we must have converged close to some wj as long as our charges ai are not too small.
The proof is similar to Theorem 3.6. Then, the following lemma relates the magnitude of the charges
ai to the progress made in the objective function.
Lemma 4.3. Let M = Rd for d ≡ 3 mod 4 and let G be the regularized loss corresponding to the
activation σ given by Lemma 4.2 with λ = 1. For any  ∈ (0, 1) and δ ∈ (0, 1), if (a, θ) ∈ MG,δ ,
then for all i, either 1) there exists j such that kθi − wj k < k or 2) a2i < 2kdδ.
p
p
Lemma 4.4. Assume the conditions of Lemma 4.3. If G(a, θ) ≤ G(0, 0) − δ and (a, θ) ∈
MG,δ2 /(2k3 d) , then there exists some i, j such that kθi − wj k < k.
Finally, we guarantee that our initialization substantially decreases our objective function.
Together with our previous lemmas, it will imply that we must be close to some wj upon convergence.
This is the overview of the proof of Theorem 4.1, presented below.
of Theorem 4.1 and Lemma 4.3. With high probability, we can
Lemma 4.5. Assume the conditions
q
p
(0)
(0)
initialize (a , θ ) such that G(a(0) , θ (0) ) ≤ G(0, 0) − δ with δ = (d/)−O(d) .
Proof of Theorem 4.1. Let our potential Φ/k be the one as constructed in Lemma 4.2 that is 1harmonic for all r ≥ q
/k and as always, k = poly(d). First, by Lemma 4.5, we can initialize
p
(a(0) , θ (0) ) such that G(a(0) , θ (0) ) ≤ G(0, 0) − δ for δ = (d/)−O(d) . If we set α = (d/)−O(d)
and η = γ = δ 2 /(2k 3 d), then running Algorithm 2 will terminate and return some (a, θ) in at most
(d/)O(d) iterations. This is because our algorithm ensures that our objective function decreases by at
least min(αη 2 /2, α2 γ 3 /2) at each iteration, G(0, 0) is bounded by O(k), and G ≥ 0 is non-negative.
Let θ = (θ1 , ...θk ). If there exists θi , wj such that kθi − wj k < , then we are done. Otherwise, we
claim that (a, θ) ∈ MG,δ2 /(2k3 d) . For the sake of contradiction, assume otherwise. By our algorithm
termination conditions, then it must be that after one step of gradient or Hessian descent from
(a, θ), we reach some (a0 , θ 0 ) and G(a0 , θ 0 ) > G(a, θ) − min(αη 2 /2, α2 γ 3 /2).
Algorithm 2 x = SecondGD(L, x0 , T, α, η, γ)
Input: L : M → R; x0 ∈ M; T ∈ N; α, η, γ ∈ R
for i = 1 to T do
if k∇L(xi−1 )k ≥ η then xi ← xi−1 − α∇L(xi−1 )
else xi ← HD(L, xi−1 , 1, α)
if L(xi ) ≥ L(xi−1 ) − min(αη 2 /2, α2 γ 3 /2) then return xi−1
9

Algorithm 3 Node-wise Descent Algorithm
Input: (a, θ) = (a1 , ..., ak , θ1 , ..., θk ), ai ∈ R, θi ∈ M; T ∈ N; L; α, η, γ ∈ R;
for i = 1 to k do
Initialize (ai , θi )
(ai , θi ) = SecondGD (Lai ,θi , (ai , θi ), T, α, η, γ)
return a = (a1 , ..., ak ), θ = (θ1 , ..., θk )
Now, Lemma 4.2 ensures all first three derivatives of Φ/k are bounded by O((dk/)2d ), except
at w1 , ..., wk . Furthermore, since there do not exist θi , wj such that kθi − wj k < , G is three-times
continuously differentiable within a α(dk/)2d = (d/)−O(d) neighborhood of θ. Therefore, by
Lemma D.1 and D.2 in the appendix , we must have G(a0 , θ 0 ) ≤ G(a, θ) − min(αη 2 /2, α2 γ 3 /2), a
contradiction.
p
pLastly, since our algorithm maintains that our objective function is decreasing, so
G(a, θ) ≤ G(0, 0) − δ. Finally, we conclude by Lemma 4.4.

4.1

Node-by-Node Analysis

We cannot easily analyze the convergence of gradient descent to the global minima when all θi are
simultaneously moving since the pairwise interaction terms between the θi present complications,
even with added regularization. Instead, we run a greedy node-wise descent (Algorithm 3) to learn
the hidden weights, i.e. we run a descent algorithm with respect to (ai , θi ) sequentially. The main
idea is that after running SGD with respect to θ1 , θ1 should be close to some wj for some j. Then,
we can carefully induct and show that θ2 must be some other wk for k 6= j and so on.
Let L1 (a1 , θ1 ) be the objective L restricted to a1 , θ1 being variable, and a2 , ..., ak = 0 are fixed.
The tighter control on the movements of θ1 allows us to remove our regularization. While our
previous guarantees before allow us to reach a -neighborhood of wj when running SGD on L1 , we
will strengthen our guarantees to reach a (d/)−O(d) -neighborhood of wj , by reasoning about the
first derivatives of our potential in an -neighborhood of wj . By similar argumentation as before, we
will be able to derive the following convergence guarantees for node-wise training.
Theorem 4.6. Let M = Rd and d ≡ 3 mod 4 and let L be as in 1 and k = poly(d). For all
 ∈ (0, 1), we can construct an activation σ such that if w1 , ..., wk ∈ Rd with wi randomly chosen
from wi ∼ N (0, O(d log d)Id×d ) and b1 , ..., bk be randomly chosen at uniform from [−1, 1], then with
high probability, after running nodewise descent (Algorithm 3) on the objective L for at most (d/)O(d)
iterations, (a, θ) is in a (d/)−O(d) neighborhood of the global minima.

5

Experiments

For our experiments, our training data is given by (xi , f (xi )), where xi are randomly chosen from a
standard Gaussian in Rd and f is a randomly generated neural network with weights chosen from
a standard Gaussian. We run gradient descent (Algorithm 4) on the empirical loss, with stepsize
around α = 10−5 , for T = 106 iterations. The nonlinearity used at each node is sigmoid from -1 to 1,
including the output node, unlike the assumptions in the theoretical analysis. A random guess for
the network will result in a mean squared error of around 1. Our experiments (see Fig 1) show that
for depth-2 neural networks, even with non-linear outputs, the training error diminishes quickly to
under 0.002. This seems to hold even when the width, the number of hidden nodes, is substantially
increased (even up to 125 nodes), but depth is held constant; although as the number of nodes

10

Depth
Depth
Depth
Depth
Depth

Width 5
0.0015
0.0033
0.0036
0.0085
0.0845

2
3
5
9
17

Width 10
0.0017
0.0264
0.0579
0.1662
0.3862

Width 20
0.0018
0.1503
0.2400
0.4171
0.4934

Width 40
0.0019
0.2362
0.4397
0.6071
0.5777

Table 2: Test Error of Learning Neural Networks of Various Depth and Width

increases, the rate of decrease is slower. This substantiates our claim that depth-2 neural networks
are learnable.
However, it seems that for depth greater than 2, the test error becomes significant when width
is high (see Fig 2). Even for depth 3 networks, the increase in depth impedes the learnability of
the neural network and the training error does not get close enough to 0. It seems that for neural
networks with greater depth, positive convergence results in practice are elusive. We note that we
are using training error as a measure of success, so it’s possible that the true underlying parameters
are not learned.

Figure 2: Test Error of Varying-Depth Networks vs. Width

References
[ABGM14] Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. Provable bounds for learning some
deep representations. In ICML, pages 584–592, 2014.
[AHW96]

Peter Auer, Mark Herbster, and Manfred K Warmuth. Exponentially many local minima for
single neurons. pages 316–322, 1996.

11

[AKN85]

Vladimir I Arnold, Valery V Kozlov, and Anatoly I Neishtadt. Mathematical aspects of classical
and celestial mechanics. Encyclopaedia Math. Sci, 3:1–291, 1985.

[APVZ14] Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning polynomials with
neural networks. In International Conference on Machine Learning, pages 1908–1916, 2014.
[BG17]

Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian
inputs. arXiv preprint arXiv:1702.07966, 2017.

[BR88]

Avrim Blum and Ronald L. Rivest. Training a 3-node neural network is np-complete. pages 9–18,
1988.

[BRS89]

Martin L Brady, Raghu Raghavan, and Joseph Slawny. Back propagation fails to separate where
perceptrons succeed. IEEE Transactions on Circuits and Systems, 36(5):665–674, 1989.

[CHM+ 15] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The
loss surfaces of multilayer networks. In AISTATS, 2015.
[CUH15]

Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network
learning by exponential linear units (elus). CoRR, abs/1511.07289, 2015.

[Dan17]

Amit Daniely. Sgd learns the conjugate kernel class of the network.
arXiv:1702.08503, 2017.

[DFS16]

Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks:
The power of initialization and a dual view on expressivity. In Advances In Neural Information
Processing Systems, pages 2253–2261, 2016.

arXiv preprint

[DPG+ 14] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua
Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex
optimization. In Advances in neural information processing systems, pages 2933–2941, 2014.
[GHJY15] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic
gradient for tensor decomposition. In COLT, pages 797–842, 2015.
[GKKT16] Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in
polynomial time. arXiv preprint arXiv:1611.10258, 2016.
[GLM17]

Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape
design. arXiv preprint arXiv:1711.00501, 2017.

[JGN+ 17] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape
saddle points efficiently. arXiv preprint arXiv:1703.00887, 2017.
[JSA15]

Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity:
Guaranteed training of neural networks using tensor methods. CoRR, abs/1506.08473, 2015.

[Kaw16]

Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information
Processing Systems, pages 586–594, 2016.

[KS06]

Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections
of halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science
(FOCS’06), pages 553–562. IEEE, 2006.

[LSSS14]

Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training
neural networks. In Advances in Neural Information Processing Systems, pages 855–863, 2014.

[LY17]

Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation.
arXiv preprint arXiv:1705.09886, 2017.

[SC16]

Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees
for multilayer neural networks. CoRR, abs/1605.08361, 2016.

12

[SKS+ 16]

Anish Shah, Eashan Kadam, Hena Shah, Sameer Shinde, and Sandip Shingade. Deep residual
networks with exponential linear unit. In Proceedings of the Third International Symposium on
Computer Vision and the Internet, pages 59–65. ACM, 2016.

[SSSS11]

Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan. Learning kernel-based halfspaces
with the 0-1 loss. SIAM Journal on Computing, 40(6):1623–1646, 2011.

[Tia17]

Yuandong Tian. An analytical formula of population gradient for two-layered relu network and
its applications in convergence and critical point analysis. arXiv preprint arXiv:1703.00560, 2017.

[ZLJ16]

Yuchen Zhang, Jason D Lee, and Michael I Jordan. l1-regularized neural networks are improperly
learnable in polynomial time. In International Conference on Machine Learning, pages 993–1001,
2016.

[ZLWJ15] Yuchen Zhang, Jason D. Lee, Martin J. Wainwright, and Michael I. Jordan. Learning halfspaces
and neural networks with random initialization. CoRR, abs/1511.07948, 2015.

13

A

Electron-Proton Dynamics

Theorem 2.3. Let Φ be a symmetric potential and L be as in (1). Running continuous gradient
descent on 12 L with respect to θ, initialized at (θ1 , ..., θk ) produces the same dynamics as ElectronProton Dynamics under 2Φ with fixed particles at w1 , ..., wk with respective charges b1 , .., bk and
moving particles at θ1 , ..., θk with respective charges a1 , ..., ak .
Proof. The initial values are the same. Notice that continuous gradient descent on L(a, θ) with
i (t)
respect to θ produces dynamics given by dθdt
= −∇θi L(a, θ). Therefore,
k

X
X
dθi (t)
= −2
ai aj ∇θi Φ(θi , θj ) − 2
ai bj ∇θi Φ(θi , wj )
dt
j=1

j6=i

And gradient descent does not move wi . By definition, the dynamics corresponds to Electron-Proton
Dynamics as claimed.

B
B.1

Realizable Potentials
Activation-Potential Calculations

First define the dual of a function f : R → R is defined to be
fb(ρ) =

[f (X)f (Y )],

E

X,Y ∼N (ρ)

where N (ρ) is the bivariate normal distribution with X, Y unit variance and ρ covariance. This is as
in [DFS16].
b is the corresponding potential
Lemma B.1. Let M = S d−1 and σ be our activation function, then σ
function.
Proof. If u, v have norm 1 and if X is a standard Gaussian in Rd , then note that X1 = uT X and
X2 = v T X are both standard Gaussian variables in R1 and the covariance is E[X1 X2 ] = uT v.
Therefore, the dual function of the activation gives us the potential function.
E[σ(uT X)σ(v T X)] =

X

E

X,Y ∼N (uT v)

[σ(X)σ(Y )]

=σ
b(uT v).

By Lemma B.1, the calculations of the activation-potential for the sign, ReLU, Hermite, exponential functions are given in [DFS16]. For the Gaussian and Bessel activation functions, we can
calculate directly. In both case, we notice that we may write the integral as a product of integrals in
each dimension. Therefore, it suffices to check the following 1-dimensional identities.
Z ∞√
1
2
2√
2
2
2
2ex /4 e−(x−θ) 2ex /4 e−(x−w) √ e−x /2 dx
2π
−∞
r Z ∞
2
2
2
2
=
e−(x−θ) e−(x−w) dx = e−(θ−w) /2
π −∞
14

Z

∞

2
1
2
2
( )3/2 ex /2 K0 (|x − θ|)K0 (|x − w|) √ e−x /2 dx
2π
−∞ π
Z ∞
2
=
K (|x − θ|)K0 (|x − w|) dx = e−|θ−w|
2 0
−∞ π

The last equality follows
uniqueness and taking the Fourier transform of both sides,
p by Fourier
2
−1
which are both equality 2/π(ω + 1) .

B.2

Characterization Theorems

Theorem 2.1. Let M = Rd and Φ is square-integrable and F(Φ) is integrable. Then, Φ is
realizable under standardpGaussian inputs if F(Φ)(ω) ≥ 0 and the corresponding activation is
T
σ(x) = (2π)d/4 ex x/4 F−1 ( F(Φ))(x), where F is the generalized Fourier transform in Rd .
p
Proof. Since Φ is square-integrable, its Fourier transform exists. Let h(x) = F−1 ( F(Φ))(x) and
this is well-defined
since the Fourier transform was non-negative everywhere and the Fourier inverse
p
2
exists since F(Φ)(x) is square-integrable. Now, let σ(x, w) = (2π)1/4 ex /4 h(x − w). Realizability
follows by the Fourier inversion theorem:
Z
E [σ(X, w)σ(X, θ)] =
h(x − w)h(x − θ) dx
X∼N
n
R
Z
=
h(x)h(x − (θ − w)) dx
Rn
−1

=F

(F(h ∗ h)(θ − w))

= F−1 (F(h)2 (θ − w))
= F−1 (F(Φ)(θ − w))
= Φ(θ − w)
Note that ∗ denotes function convolution.
When our relevant space is M = S d−1 , we let ΠM be the projection operator on M. The
simplest way to define the gradident on S d−1 is ∇S d−1 f (x) = ∇Rd f (x/kxk), where k · k denotes the
l2 norm and x ∈ S d−1 . The Hessian and Laplacian are analogously defined and the subscripts are
usually dropped where clear from context.
We say that a potential Φ on M = S d−1 is rotationally invariant if for all θ, w ∈ S d−1 , we have
Φ = h(θT w).
Theorem B.2. Let M = S d−1 and Φ(θ, w) = f (θT w). Then, Φ is P
realizable if f has non-negative
√
Taylor coefficients, ci ≥ 0 , and the corresponding activation σ(x) = ∞
i=1 ci hi (x) converges almost
everywhere, where hi (x) is the i-th Hermite polynomial.
P
Proof. By B.1 and due to the orthogonality of hermite polynomials, if f = i ai hi , where hi (x) is
the i-th Hermite polynomial, then
X
fb(ρ) =
a2i ρi
i

Therefore, any function with non-negative taylor coefficients is a valid potential function, with
the corresponding activation function determined by the sum of hermite polynomials, and the sum
is bounded almost everywhere by assumption.

15

B.3

Further Characterizations

To apply Theorem 2.1, we need to check that the Fourier transform of our function is non-negative.
Not only is this is not straightforward to check, many of our desired potentials do not satisfy this
criterion. In this section, we would like to have a stronger characterization of realizable potentials,
allowing us to construct realizable potentials that approximates our desired potential.
Definition B.3. Let Φ be a positive semidefinite function if for all x1 , ..., xn , the matrix Aij =
Φ(xi − xj ) is positive semidefinite.
Lemma B.4. Let M = Rd and Φ(θ, w) = f (θ − w) is is realizable, then it is positive semidefinite.
Proof. If Φ is realizable, then there exists σ such that Φ(θ, w) = EX∼N [σ(X, w)σ(X, θ)]. For
x1 , ..., xn , we note that the quadratic form:

!2 
X
X
X
Φ(xi , xj )vi vj =
E [σ(X, xi )σ(X, xj )]vi vj = E 
vi σ(X, xi )  ≥ 0
i,j

i,j

X∼N

X∼N

i

Since Φ is translationally symmetric, we conclude that Φ is positive semidefinite.
Definition B.5. A potential Φ is F-integrable if it is square-integrable and F(Φ(ω)) is integrable,
where F is the standard Fourier transform.
Rb
Lemma B.6. Let w(x) ≥ 0 be a positive weighting function such that a w(x) dx is bounded. If
Rb
Φx is a parametrized family of F-integrable realizable potentials, then, a w(x)Φx is F-integrable
realizable.
Rb
Rb
Proof. Let Φ = a w(x)Φx . From linearity of the Fourier transform and a w(x) dx is bounded, we
know that Φ is F-integrable. Since Φx are realizable, they are positive definite by Lemma B.4 and
by Bochner’s theorem, their Fourier transforms are non-negative. And since w(x) ≥ 0, we conclude
by linearity and continuity of the Fourier transform that F(Φ) ≥ 0. By Theorem 2.1, we conclude
that Φ is realizable.
Lemma B.7. Let M = Rd for d ≡ 3 mod 4. Then, for any , t > 0, there exists a F-integrable
realizable Φ such that for t ≥ r > , Φ(d−1) (r) = t − r and for r ≤ , Φ(d−1) (r) = t−
 r. Furthermore,
Φ(k) (r) = 0 for r > t for all 0 ≤ k ≤ d.
Proof. Our construction is based on the radial activation function ht (x, θ) = 1kθ−xk≤t/2 , which is
the indicator in the disk of radius t/2. This function, when re-weighted correctly as σt (x, θ) =
2
(2π)1/4 ex /4 ht (x, θ) gives rise to a radial potential function that is simply the convolution of ht with
itself, measuring the volume of the intersection of two spheres of radius t centered at θ and w.
( R t/2
C kθ−wk/2 ((t/2)2 − x2 )(d−1)/2 dx kθ − wk ≤ t
Φt (θ, w) = E[σt (X, θ)σt (X, w)] =
X
0
otherwise.
R t/2

2
2 (d−1)/2 dx
r/2 ((t/2) − x )
and Φ0t (r) = −C 0 ((t/2)2 − (r/2)2 )(d−1)/2 . Since d ≡ 3 mod 4, we notice that Φ0t has a positive
coefficient in the leading rd−1 term and since it is a function of r2 , it has a zero rd−2 term. Therefore,

Therefore, as a function of r = kθ − wk, we see that when r ≤ t, Φt (r) = C

we can scale Φt such that
(
r r≤t
(d−1)
Φt
(r) =
0 otherwise.
16

Φt is clearly realizable and now we claim that it is F-integrable. First, Φt is bounded on a
compact set so it is square-integrable. Now, since Φt = ht ∗ ht can be written as a convolution,
F(Φt ) = F(ht )2 . Since ht is square integrable, then by Parseval’s, F(ht ) is square integrable, allowing
us to conclude that Φt is F-integrable.
Now, for any  > 0, let us construct our desired Φ by taking a positive sum of Φt and then
appealing to Lemma B.6. Consider
Z t
1
Φ(r) =
Φ (r) dx
2 x
 x
Rt
First, note that the total weight  x12 is bounded. Then, when r ≥ t, since Φx (r) = 0 for
x ≤ t, we conclude that Φ(k) (r) = 0 for any k. Otherwise, for  < r < t, we can apply dominated
convergence theorem to get
Z t
Z t
Z r
1 (d−1)
r
1 (d−1)
(d−1)
Φx
(r) dx +
Φx
(r) dx = 0 +
dx = 1 − r/t
Φ
(r) =
2
2
2
r x
r x
 x
Scaling by t gives our desired claim. For r ≤ , we integrate similarly and scale by t to
conclude.
Lemma B.8. Let M = Rd for d ≡ 3 mod 4 and let Φ(r) be a radial potential. Also, Φ(k) (r) ≥ 0
and Φ(k+1) (r) ≤ 0 for all r > 0 and k ≥ 0 even, and limr→∞ Φ(k) (r) = 0 for all 0 ≤ k ≤ d.
(k)
Then, for any  > 0, there exists a F-integrable realizable potential Φ such that Φ (r) = Φ(k) (r)
(d−1)
(k)
for all 0 ≤ k ≤ d − 1 and r ≥ . Furthermore, we have Φ
(r) ≥ 0 for all r > 0 and Φ (r) ≥ 0
(k+1)
and Φ
(r) ≤ 0 for all r > 0 and d − 3 ≥ k ≥ 0 even.
k−j+1
P
(d−1−k)
(d−j) ()|
Lastly, for r <  and 0 ≤ k ≤ d − 1, |Φ
(r)| ≤ |Φ(d−1−k) ()| + kj=1 (−r)
(k−j+1)! |Φ
Proof. By Lemma B.7, we can find Φt such that

t−

  r
(d−1)
Φt
= t−r


0

0≤r≤
<r≤t
r>t

(k)

Furthermore, Φt (r) = 0 for r > t for all 0 ≤ k ≤ d. Therefore, we consider
Z ∞
Φ(r) =
Φ(d+1) (x)Φx (r) dx


R∞

Note that this is a positive sum with  Φ(d+1) (x) dx = −Φ(d) () < ∞. By the non-negativity
of our summands, we can apply dominated convergence theorem and Fubini’s theorem to get
Z ∞
(d−1)
Φ
(r) =
Φ(d+1) (x)(Φ(d−1)
(r)) dx
x

Z ∞
=
Φ(d+1) (x)(Φx(d−1) (r)) dx
Zr ∞
Z x
(d+1)
=
Φ
(x)
1 dy dx
r
Zr ∞ Z ∞
Z ∞
(d+1)
=
Φ
(x) dx dy =
−Φ(d) (y) dy
r
y
(d−1)

=Φ

r

(r)
17

(d−1)

(k)

Now, since Φ
(r) = Φ(d−1) (r) for r ≥  and limr→∞ Φ (r) = limr→∞ Φ(k) (r) = 0 for
0 ≤ k ≤ d − 1, repeated integration gives us our claim.
Finally, for the second claim, notice that for r ≤ , we get
Z ∞
Z ∞
x−
(d−1)
(d+1)
(d−1)
Φ(d+1) (x)
Φ
(x)(Φx
(r)) dx = r
Φ
(r) =
dx = Cr



Note that our constant C ≥ 0 since the summands are non-negative. Therefore, we conclude
(d−1)
(k)
that Φ
(r) ≥ 0 for all r > 0. Repeated integration and noting that limr→∞ Φ (r) = 0 for
0 ≤ k ≤ d − 1 gives us our claim.
Lastly, we prove the last claim of the theorem with induction on k. This holds trivially for k = 0
(d−1)
(d−1)
since Φ
(r) ≤ Φ
() = Φ(d−1) () for r ≤ . Then, assume we have the inequality for k < d − 1.
By integration, we have
Z 
(d−k−2)
(d−k−2)
(d−1−k)
|Φ
|Φ
(r)| ≤ |Φ
()| +
(y)| dy
r
Z 
(d−k−2)
(d−1−k)
|Φ
()| +
()| dy
≤ |Φ
r

Z X
k
( − y)k−j+1 (d−j)
+
|Φ
()| dy
(k − j + 1)!
r
j=1

≤ |Φ

(d−k−2)

()| +

k+1
X
( − y)k−j+2
j=1

(k − j + 2)!

|Φ(d−j) ()|

Therefore, we conclude with induction.
Lemma 4.2. Let M = Rd for d ≡ 3 mod 4. Then, for any  ∈ (0, 1), we can construct a radial
activation σ (r) such that the corresponding radial potential Φ (r) is λ-harmonic for r ≥ .
Furthermore, we have Φ (d−1) (r) ≥ 0 for all r > 0, Φ (k) (r) ≥ 0, and Φ (k+1) (r) ≤ 0 for all r > 0
and d − 3 ≥ k ≥ 0 even.
(k)
When λ = 1, |Φ (r)| ≤ O((d/)2d ) for all 0 ≤ k ≤ d−1. And when r ≥ , Ω(e−r r2−d (d/)−2d ) ≤
d
Φ (r) ≤ O((1 + r) e1−r (r)2−d ) and Ω(e−r r1−d (d/)−2d ) ≤ |Φ0 (r)| ≤ O((d + r)(1 + r)d e1−r r1−d )
Proof. This is a special case of the following lemma.
Lemma B.9. Let M = Rd for d ≡ 3 mod 4. Then, for any 1 >  > 0, we can construct a radial
activation σ (r) with corresponding normalized radial potential Φ (r) that is λ-harmonic when r ≥ .
Furthermore, we have Φ (d−1) (r) ≥ 0 for all r > 0 and Φ (k) (r) ≥ 0 and Φ (k+1) (r) ≤ 0 for all
r > 0 and d − 3 ≥ k ≥ 0 even.
√
√
√
(k)
λ for all 0 ≤ k ≤ d − 1. And for r ≥ , e− λr r 2−d (2d +
Also, |Φ (r)| ≤ 3(2d + λ)2d −2d
e
√
√ −2d 2d
√ d √λ(1−r) 2−d
√
λ)  /3 ≤ Φ (r) ≤ (1 + r √
λ) e
(r) . Also for r ≥ , e− λr r1−d (2d + λ)−2d 2d /3 ≤
√
√
|Φ0 (r)| ≤ (d + λr)(1 + r λ)d e λ(1−r) r1−d
√

Proof. Consider a potential of the form Φ(r) = p(r)e− λr /rd−2 . We claim that there exists a
polynomial p of degree k = (d − 3)/2 with non-negative coefficients and p(0)
√ = 1 such that Φ is
λ-harmonic. Furthermore, we will also show along√the way that p(r) ≤ (1 + λr)d .
When d = 3, it is easy to check that Φ(r) = e(− λ)r /r is our desired potential. Otherwise, by our
formula for the radial Laplacian in d dimensions, we want to solve the following differential equation:
∆Φ =

1
rd−1

∂ d−1 ∂Φ
(r
) = λΦ
∂r
∂r
18

Solving this gives us the following second-order differential equation on p
√
√
rp00 − (d − 3 + 2 λr)p0 + λ(d − 3)p = 0
P
Let us write p(r) = ki=0 ai ri . Then, substituting into our differential equation gives us the
following equations by setting each √
coefficient of ri to zero:
i
r : ai+1 (i + 1)(i − (d − 3)) = ai λ(2i − (d − 3))
rk : (−2k + d − 3)ak = 0
The last equation explains why we chose k = (d − 3)/2, so that it is automatically zero. Thus,
setting a0 = 1 and running the recurrence gives us our desired polynomial. Note that the recurrence
is valid and produces positive coefficients since i√< k = (d
√ − 3)/2. Our claim follows and
√ Φ is
λ-harmonic. And furthermore, notice that ai+1 ≤ λai ≤ ( λ)i+1 . Therefore, p(r) ≤ (1 + r λ)d .
Lastly, we assert that Φ(j) (r) is non-negative for j even and non-positive for √
j odd. To prove our
−
assertion, we note that it suffices to show that if Φ is of the form Φ(r) √
= p(r)e λr /rl for some p of
degree k < l and p has non-negative coefficients, then Φ0 (r) = −q(r)e− λr /rl+1 for some q of degree
k + 1 with non-negative coefficients.
Differentiating Φ gives:
√
e−r
Φ0 = l+1 (rp0 (r) − (l + λr)p(r))
r
√
It is clear that if p has degree k, then q(r) = (l + λr)p(r) − rp0 (r) has degree k + 1, so it
suffices to show that it has non-negative coefficients. Let p0 , ..., pk be the non-negative coefficients of
p. Then, by our formula, we see that
q0 = lp0
√
√
qi = lpi √
− ipi + λpi−1 = (l − i)pi + λpi−1
qk+1 = λpk
Since i ≤ k < l, we conclude that q has non-negative coefficients. Finally, our assertion follows
with induction since Φ(0) (r) is non-negative and has our desired form with k = (d − 3)/2 < d − 2.
By Lemma B.8, our primary theorem follows, we can construct a realizable radial potential Φ (r)
that is λ-harmonic when r ≥  and has alternating-signed derivatives.
(k)
(k)
Lastly, we prove the following preliminary bound on Φ (r) when k ≤ d: |Φ (r)| ≤ 3(2d +
√ 2d −2d
(k)
 λ) 
for all 0 ≤ k ≤ d − 1. First, notice that by the results of Lemma B.8, Φ (r) is monotone
(k)
(k)
and limr→∞ Φ (r)
= 0. So, it follows that we just have to bound |Φ (0)|. From our construction,
√
(k)
Φ () = pk ()e− λ 2−d−k , for some
√ polynomial pk . Furthermore, from our construction, we have
the recurrence pk () = (d − 2 + k + λ)pk−1 () − p0k−1 (). Therefore, we conclude that for k ≤ d,
√
√
√
√
pk () ≤ (2d + λ)k p0 () ≤ (2d + λ)k (1 + λ)d ≤ (2d + λ)2d .
√
(k)
Therefore, we can bound |Φ ()| ≤ (2d + λ)2d −2d . Finally, by Lemma B.8,
|Φ(d−1−k)
(0)| ≤ |Φ(d−1−k) ()| +


k
X
()k−j+1
|Φ(d−j) ()|
(k − j + 1)!
j=1

√

k
X

k−j+1
)
(k − j + 1)!
j=1
√ 2d −2d 
√
≤ (2d + λ)  e ≤ 3(2d + λ)2d −2d
≤ (2d +

λ)2d −2d (1 +

√
√
√
− λr
And for r ≥ , we see that |Φ (r)| = |Φ(r)| ≤ |p(r)| erd−2 = (1 + r λ)d e− λr r2−d . And
√
√
√
√
e− λr
0
0
|Φ (r)| = |Φ (r)| ≤ |p1 (r)| rd−1 ≤ (d + λr)(1 + r λ)d e− λr r1−d .

19

e  = Φ /Φ (0). Note that since Φ is monotonically
Finally, we consider the normalized potential: Φ
√
decreasing, we can lower bound Φ (0) ≥√Φ () ≥ e− λ . Therefore, we can derive √the following upper
√ 2d −2d λ
√
e (k)
e  (r)| ≤ (1 + r λ)d e λ(1−r) r2−d and its
bounds: |Φ
e and for r ≥ , |√Φ
 (r)| ≤ 3(2d + λ) 
√
√
e 0 (r)| ≤ (d + λr)(1 + r λ)d e λ(1−r) r1−d .
derivative is bounded by |Φ

e  and the first derivative when r ≥ , by using the
And lastly, we derive some lower bounds on
√
√ Φ−2d
√
e  (r) ≥ Φ (r)(2d + λ) 2d /3 ≥ e− λr r2−d (2d + λ)−2d 2d /3. For the
upper bound on Φ (0): Φ
√
√
e 0 (r)| ≥ e− λr r1−d (2d + λ)−2d 2d /3.
derivative, we get |Φ
Lemma B.10. The λ-harmonic radial potential Φ(r) = e−r /r in 3-dimensions is realizable by the
activation σ(r) = K1 (r)/r.
Proof. The activation is obtained from the potential function by first taking its Fourier transform,
then taking its square root, and then taking the inverse fourier transform. Since the functions in
consideration are radially symmetric
F (y) of f (x) (and inverse) are obtained by
R ∞ the Fourier transform
√
the Hankel Transfom yF (y) = 0 xf (x)J1/2 (xy) xydx. Plugging f (x) = e−x /x, from the Hankel
2
2
tranform tables we get yF
we wish to find the inverse
p(y) = cy/(1 + y ) giving F (y) = cy/(1 + y ). SoR ∞
√
2
Fourier transform for 1/ 1 + y . The inverse f (x) is given by xf (x) = 0 yF (y)J1/2 (xy) xydy =
cK1 (x). So σ(r) = K1 (r)/r.

C

Earnshaw’s Theorem

Theorem 3.4. (Earnshaw’s Theorem. See [AKN85]) Let M = Rd and let Φ be harmonic and L be
as in (2). Then, L admits no differentiable strict local minima.
Proof. If (a, θ) is a differentiable strict local minima, then for any i, we must have
∇θi L = 0, and Tr(∇2θi L) > 0.
Since Φ is harmonic, we also have
Tr(∇2θi L(θ1 , ..., θn ))

= ∆θi L = 2

X

ai aj ∆θi Φ(θi , θj ) + 2

k
X

ai bj ∆θi Φ(θi , wj ) = 0,

j=1

j6=i

which is a contradiction. In the first line, there is a factor of 2 by symmetry.

D

Descent Lemmas and Iteration Bounds

Algorithm 4 x = GD(L, x0 , T, α)
Input: L : M → R; x0 ∈ M; T ∈ N; α ∈ R
Initialize x = x0
for i = 1 to T do
x = x − α∇L(x)
x = ΠM x
Lemma D.1. Let f : Ω → R be a thrice differentiable function such that |f (y)| ≤ B0 , k∇f (y)k ≤
B1 , k∇2 f (y)k ≤ B2 , k∇2 f (z) − ∇2 L(y)k ≤ B3 kz − yk for all y, z in a (αB1 )-neighborhood of x. If
k∇f (x)k ≥ η and x0 is reached after one iteration of gradient descent (Algorithm 4) with stepsize
α ≤ B12 , then kx0 − xk ≤ αB1 and f (x0 ) ≤ f (x) − αη 2 /2.
20

Proof. The gradient descent step is given by x0 = x − α∇f (x). The bound on kx0 − xk is clear since
k∇f (x)k ≤ B1 .
f (x0 ) ≤ f (x) − α∇f (x)T ∇f (x)T + α2
≤ f (x) − (α − α2
For 0 ≤ α ≤

1
B2 ,

B2
k∇f (x)k2
2

B2 2
)η
2

we have α − α2 B2 /2 ≥ α/2, and our lemma follows.

Lemma D.2. Let f : Ω → R be a thrice differentiable function such that |f (y)| ≤ B0 , k∇f (y)k ≤
B1 , k∇2 f (y)k ≤ B2 , k∇2 f (z) − ∇2 L(y)k ≤ B3 kz − yk for all y, z in a (αB2 )-neighborhood of x. If
λmin (∇2 f (x)) ≤ −γ and x0 is reached after one iteration of Hessian descent (Algorithm 1) with
stepsize α ≤ B13 , then kx0 − xk ≤ αB2 and f (x0 ) ≤ f (x) − α2 γ 3 /2.
Proof. The gradient descent step is given by x0 = x + βvmin , where vmin is the unit eigenvector
corresponding to λmin (∇2 f (x)) and β = −αλmin (∇2 f (x))sgn(∇f (x)T vmin ). Our bound on kx0 − xk
is clear since |λmin (∇2 f (x))| ≤ B2 .
T
f (x0 ) ≤ f (x) + β∇f (x)T vmin + β 2 vmin
∇2 f (x)vmin +

B3 3
|β| kvmin k3
6

B3 3
|β|
6

≤ f (x) − |β|2 γ +

The last inequality holds since the sign of β is chosen so that β∇f (x)T vmin ≤ 0. Now, since
|β| = αγ ≤ Bγ3 , −|β|2 γ + B63 |β|3 ≤ −α2 γ 3 /2.

E

Convergence of Almost λ-Harmonic Potentials

Lemma 4.3. Let M = Rd for d ≡ 3 mod 4 and let G be the regularized loss corresponding to the
activation σ given by Lemma 4.2 with λ = 1. For any  ∈ (0, 1) and δ ∈ (0, 1), if (a, θ) ∈ MG,δ ,
then for all i, either 1) there exists j such that kθi − wj k < k or 2) a2i < 2kdδ.
Proof. The proof is similar to Theorem 3.6. Let Φ be the realizable potential in 4.2 such that Φ (r)
is λ-harmonic when r ≥  with λ = 1. Note that Φ (0) = 1 is normalized. And let (a, θ) ∈ MG,δ .
WLOG, consider θ1 and a initial set S0 = {θ1 } containing it. For a finite set of points S and
a point x, define d(x, S) = miny∈S kx − yk. Then, we consider the following set growing process.
If there exists θi , wi 6∈ Sj such that d(θi , Sj ) <  or d(wi , Sj ) < , add θi , wi to Sj to form Sj+1 .
Otherwise, we stop the process. We grow S0 to until the process terminates and we have the grown
set S.
If there is some wj ∈ S, then it must be the case that there exists j1 , · · · jq such that kθ1 −θj1 k < 
and kθji − θji+1 k < , and kθjq − wj k <  for some wj . So, there exists j, such that kθ1 − wj k < k.
Otherwise, notice that for each θi ∈ S, kwj − θi k ≥  for all j, and kθi − θj k ≥  for all θj 6∈ S.
WLOG, let S = {θ1 , . . . , θl }.
We consider changing all θ1 , . . . , θl by the same v and define
H(a, v) = G(a, θ1 + v, ..., θl + v, θl+1 . . . , θk ).
The optimality conditions on a are
k

X
X
∂H
= |4ai + 2
aj Φ (θi , θj ) + 2
bj Φ (θi , wj )| ≤ δ
∂ai
j=1

j6=i

21

Next, since Φ (r) is λ-harmonic for r ≥ , we may calculate the Laplacian of H as


l
k
k
X
X
X
∆v H =
λ 2
ai bj Φ (θi , wj ) + 2
ai aj Φ (θi , θj )
i=1

≤

l
X

j=1

j=l+1


λ −4a2i − 2

i=1

l
X


ai aj Φ (θi , θj ) + δ

= −2λ E 

l
X

!2 
ai σ(θi , X)

λ|ai |

i=1

j=1,j6=i



l
X

 − 2λ

i=1

l
X
i=1

a2i + δλ

l
X

|ai |

i=1

The second line follows from our optimality conditions and the third
Pl line2 follows from completing the
square. Since (a, θ)√∈√
MG,δ , we have ∆v H ≥ −2kdδ. Let S = i=1 ai . Then, by √
Cauchy-Schwarz,
√
we have −2λS + δλ k S ≥ −2kdδ. When S ≥ δ 2 k, we see that −λS ≥ −2λS + δλ k S ≥ −2kdδ.
Therefore, S ≤ 2kdδ/λ.
We conclude that S ≤ max(δ 2 k, 2kdδ/λ) ≤ 2kdδ/λ since δ ≤ 1 ≤ 2d/λ and λ = 1. Therefore,
2
ai ≤ 2kdδ.
p
p
Lemma 4.4. Assume the conditions of Lemma 4.3. If G(a, θ) ≤ G(0, 0) − δ and (a, θ) ∈
MG,δ2 /(2k3 d) , then there exists some i, j such that kθi − wj k < k.
Proof. If there does not exists i, j such that kθi − wj k < k, p
then by Lemma 4.3, this implies
2 for all i. Now, for a integrable function f (x), kf k =
a2i < δ 2 /kP
EX [f (X)2 ] is a norm. Therefore,
X
if f (x) = i bi σ(wi , x) be our true target function, we conclude that by triangle inequality
k
X
p
G(a, θ) ≥
ai σ(θi , x) − f (x)
i=1

≥ kf (x)kX −

k
X

kai σ(θi , x)kX ≥

p
G(0, 0) − δ

i=1

X

This gives a contradiction, so we conclude that there must exist i, j such that θi is in a k neighborhood
of wj .
Lemma 4.5. Assume the conditions
of Theorem 4.1 and Lemma 4.3. With high probability, we can
q
p
(0)
(0)
initialize (a , θ ) such that G(a(0) , θ (0) ) ≤ G(0, 0) − δ with δ = (d/)−O(d) .
Proof. Consider choosing θ1 = 0 and then optimizing a1 . Given θ1 , the loss decrease is:
G(a1 , 0) − G(0, 0) = min 2a21 + 2
a1

k
X
j=1


2
k
X
1
a1 bj Φ (0, wj ) = − 
bj Φ (0, wj )
2
j=1

Because wj are random Gaussians with variance O(d log d), we have kwj k ≤ O(d log d) with
high probability for all j. By Lemma 4.2, our potential satisfies Φ (0, wj ) ≥ (d/)−O(d) . And since
bj are uniformly chosen in [−1, 1], we conclude that with high probability over the choices of bj ,
2
P
k
b
Φ(θ
,
w
)
≥ (d/)−O(d) by appealing to Chebyshev’s inequality on the squared term.
− 21
1
j
j=1 j
Therefore, we conclude that with high probability, G(a1 , 0) ≤ G(0, 0) − 12 (d/)−O(d) . Let
p
p
G(a1 , 0) = G(0, 0) − ∆ ≥ 0. Squaring and rearranging gives ∆ ≥ √ 1
(d/)−O(d) . Since
4

G(0, 0) ≤ O(k) = O(poly(d)), we are done.
22

G(0,0)

E.1

Node by Node Analysis

The first few lemmas are similar to the ones proven before in the simultaneous case. The proof
are presented for completeness because the regularization terms are removed. Note that our loss
function is quadratic in a. Therefore, let a∗1 (θ1 ) denote the optimal value of a1 to minimize our loss.
Lemma E.1. Let M = Rd for d ≡ 3 mod 4 and let L1 be the loss restricted to (a1 , θ1 ) corresponding
to the activation function σ given by Lemma 4.2 with λ = 1. For any  ∈ (0, 1) and δ ∈ (0, 1),
we can construct σ such that if (a1 , θ1 ) ∈ ML1 ,δ , then for all i, either 1) there exists j such that
kθ1 − wj k <  or 2) a21 < 2dδ.
Proof. The proof is similar to Lemma 4.3. Let Φ be the realizable potential in 4.2 such that Φ (r)
is λ-harmonic when r ≥ . Note that Φ (0) = 1 is normalized. And let (a1 , θ1 ) ∈ ML1 ,δ . Assume
that there does exist wj such that kθ1 − wj k < .
The optimality condition on a1 is
k

X
∂L
= |2a1 + 2
bj Φ (θ1 , wj )| ≤ δ
∂a1
j=1

Next, since Φ (r) is λ-harmonic for r ≥ , we may calculate the Laplacian of L as


k
X
∆θ1 L = λ 2
a1 bj Φ (θ1 , wj ) ≤ −2λa21 + δλ|a1 |
j=1

The inequality follows from our optimality conditions. Since (a1 , θ1 ) ∈ ML,δ , we have ∆θ1 L ≥ −2dδ.
When a21 ≥ δ 2 , we see that −λa21 ≥ −2λa21 + δλ|a1 | ≥ −2dδ. Therefore, a21 ≤ 2dδ/λ. We conclude
that a21 ≤ max(δ 2 , 2dδ/λ) ≤ 2dδ/λ for δ ≤ 2d ≤ 2d/λ since λ = 1. Therefore, a21 ≤ 2dδ.
p
p
Lemma E.2. Assume the conditions of Lemma E.1. If L1 (a1 , θ1 ) ≤ L1 (0, 0) − δ and (a1 , θ1 ) ∈
MG,δ2 /(2d) , then there exists some j such that kθ1 − wj k < .
Proof. The proof follows similarly from Lemma 4.4.
Now, our main observation is below, showing that in a neighborhood around wj , descending
along the gradient direction will move θ1 closer to wj . Our tighter control of the gradient of Φ
around wj will eventually allow us to show that θ1 converges to a small neighborhood around wj .
Lemma E.3. Assume the conditions of Theorem E.5 and Lemma E.1. If kθ1 − wj k ≤ d and
|bj | ≥ 1/poly(d) and |a1 − a∗1 (θ1 )| ≤ (d/)−O(d) is almost optimal and for i, kwi − wj k ≥ Ω(d log d),
w −θ
1
(d/)−8d and ξ ≤ (d/)−O(d) .
then −∇θ1 L1 = ζ kθ1j−w1j k + ξ with ζ ≥ poly(d)
Proof. Through the proof, we assume k = poly(d). Now, our gradient with respect to θ1 is
∇θ1 L1 = 2a1 bj Φ0 (kθ1 − wj k)

X
θ 1 − wj
θ 1 − wi
+2
a1 bi Φ0 (kθ1 − wi k)
kθ1 − wj k
kθ1 − wi k
i6=j

√
√
Since kθ1 − wj k ≤ d, we may lower bound |Φ0 (kθ1 − wj k)| ≥ e− λd d1−d (2d + λ)−2d 2d /3 ≥
Ω((d/)−4d ). Similarly, Φ (kθ1 − wj k) ≥ Ω((d/)−4d ). On the other hand since kwi − wj k ≥ Ω(d log d)
for all i =
6 j, we may upper bound |Φ (kθ1 − wi k)| ≤ (d/)−O(d) and |Φ0 (kθ1 − wi k)| ≤ (d/)−O(d) .
θ −w
Together, we conclude that ∇θ1 L1 = 2a1 bj Φ0 (kθ1 − wj k) kθ11 −wjj k + 2a1 ξ, where kξk ≤ (d/)−O(d) .

23

By assumption, |a1 − a∗1 (θ1 )| ≤ (d/)−O(d) , so
X
∂L1
= |2a1 + 2bj Φ (kθ1 − wj k) + 2
bi Φ (kθ1 − wi k)| ≤ (d/)−O(d)
∂a1
i6=j

By a similar argument as on the derivative, we see that a1 = −bj Φ (kθ1 − wj k) + (d/)−O(d) .
Therefore, the direction of −∇θ1 L1 is moving θ1 closer to wj since
−∇θ1 L1 = b2j Φ (kθ1 − wj k)Φ0 (kθ1 − wj k)

θ 1 − wj
+ (d/)−O(d)
kθ1 − wj k

and we know Φ > 0 and Φ0 < 0, thereby −b2j Φ (kθ1 − wj k)Φ0 (kθ1 − wj k) ≥ 1/poly(d)(d/)−8d .
Lemma E.4 (Node-wise Initialization). Assume the conditions
q of Theorem E.5pand Lemma E.1.
(0) (0)
(0) (0)
With high probability, we can initialize (a1 , θ1 ) such that L(a1 , θ1 ) ≤ L(0, 0) − δ with
1
δ = poly(d)
(d/)−18d in time log(d)O(d) .
Proof. By our conditions, there must exist some |bj | such that |bj | ≥ 1/poly(d) and for all i,
kwi − wj k ≥ Ω(d log d). Note that if we randomly sample points in a ball of radius O(d log d), we
will land in a d-neighborhood of wj with probability log(d)−O(d) since kwj k ≤ O(d log d).
Let θ1 be such that kθ1 − wj k ≤ d and then we can solve for a1 = a∗1 (θ1 ) since we are
simply minimizing a quadratic in one variable. Then, by Lemma E.3, we see that k∇θ1 L1 k ≥
1/poly(d)(d/)−8d . Finally, by Lemma 4.2, we know that the Hessian is bounded by poly(d)(d/)2d .
1
So, by Lemma D.1, we conclude by taking a stepsize of α = poly(d)
(d/)−2d to reach (a01 , θ10 ), we can
guarantee that L1 (a01 , θ10 ) ≤ L1 (a∗1 (θ1 ), θ1 ) −

1
−18d .
poly(d) (d/)
conclude that L1 (a01 , θ10 )

1
But since L1 (a∗1 (θ1 ), θ1 ) ≤ L1 (0, 0), we
≤ L1 (0, 0) − poly(d)
(d/)−18d . Let
p
p
1
−18d .
L1 (a01 , θ10 ) = L1 (0, 0) − ∆ ≥ 0. Squaring and rearranging gives ∆ ≥ √ 1
poly(d) (d/)
4

L1 (0,0)

Since L1 (0, 0) ≤ O(k) = O(poly(d)), we are done.
Lemma E.5. Assume the conditions of Lemma E.1. Also, assume b1 , ..., bk are any numbers in
[−1, 1] and w1 , ..., wk ∈ Rd satisfy kwi k ≤ O(d log d) for all i and there exists some |bj | ≥ 1/poly(d)
with kwi − wj k ≥ Ω(d log d) for all i.
(0) (0)
Then with high probability, we can choose an initial point (a1 , θ1 ) such that after running
SecondGD (Algorithm 2) on the restricted regularized objective L1 (a1 , θ1 ) for at most (d/)O(d)
iterations, there exists some wj such that kθ1 − wj k < . Furthermore, if |bj | ≥ 1/poly(d) and
kwi − wj k ≥ Ω(d log d) for all i, then kθ1 − wj k < (d/)−O(d) and |a + bj | < (d/)−O(d) .
q
p
(0) (0)
(0) (0)
Proof. First, by Lemma E.4, we can initialize (a1 , θ1 ) such that L1 (a1 , θ1 ) ≤ L1 (0, 0) − δ
1
for δ = poly(d)
(d/)−18d . If we set α = (d/)−O(d) and η = γ = λδ 2 /(2d), then running Algorithm 2
will terminate and return some (a1 , θ1 ) in at most (d/)O(d) iterations. This is because our algorithm
ensures that our objective function decreases by at least min(αη 2 /2, α2 γ 3 /2) at each iteration and
G(0, 0) is bounded by O(k) and G ≥ 0 is non-negative.
Assume there does not exist wj such that kθ1 − wj k < (d/)−O(d) . Then, we claim that
(a1 , θ1 ) ∈ ML,λδ2 /(2d) . For the sake of contradiction, assume otherwise. By our algorithm termination
conditions, then it must be that after one step of gradient or Hessian descent from (a1 , θ1 ), we reach
24

some (a0 , θ0 ) and L1 (a0 , θ0 ) > L1 (a1 , θ1 ) − min(αη 2 /2, α2 γ 3 /2). Now, Lemma 4.2 ensures all first
three derivatives of Φ are bounded by (d/)2d , except at w1 , ..., wk . Furthermore, since there does
not exists wj such that kθ1 − wj k < (d/)−O(d) , L1 is three-times continuously differentiable within
a α(d/)2d = (d/)−O(d) neighborhood of θ1 . Therefore, by Lemma D.1 and D.2, we know that
L(a0 , θ0 ) ≤ L1 (a0 , θ0 ) ≤ L1 (a1 , θ1 ) − min(αη 2 /2, α2 γ 3 /2), a contradiction.
So, it must be (a1 , θ1 ) ∈ ML,λδ2 /(2d) . Since our algorithm maintains that our objective function
p
p
is decreasing, so L1 (a1 , θ1 ) ≤ L1 (0, 0) − δ. So, by Lemma E.2, there must be some wj such that
kθ − wj k ≤ .
Now, if |bj | ≥ 1/poly(d) and kwi − wj k ≥ Ω(d log d) for all i, then since (a, θ) ∈ ML,λδ2 /(2d) and
kθ − wj k ≤ , by Lemma E.3, we have k∇θ1 L1 k ≥ 1/poly(d)(d/)−8d > δ 2 /(2d), a contradiction.
Therefore, we must conclude that our original assumption was false and kθ − wj k < (d/)−O(d) for
some wj .
Finally, we see that the charges also converge since a = −2bj Φ (kθ − wj k) + O(d/)−O(d) and
kθ − wj k = (d/)−O(d) . By noting that Φ (0) = 1 and Φ is O((d/)2d )-Lipschitz, we conclude.
Finally, we have our final theorem.
Theorem 4.6. Let M = Rd and d ≡ 3 mod 4 and let L be as in 1 and k = poly(d). For all
 ∈ (0, 1), we can construct an activation σ such that if w1 , ..., wk ∈ Rd with wi randomly chosen
from wi ∼ N (0, O(d log d)Id×d ) and b1 , ..., bk be randomly chosen at uniform from [−1, 1], then with
high probability, after running nodewise descent (Algorithm 3) on the objective L for at most (d/)O(d)
iterations, (a, θ) is in a (d/)−O(d) neighborhood of the global minima.
Proof. Let our potential Φ be the one as constructed in Lemma 4.2 that is λ-harmonic for all
r ≥  with λ = 1. Let (ai , θi ) be the i-th node that is initialized and applied second order gradient
descent onto. We want to show that the nodes (ai , θi ) will converge, in a node-wise fashion, to some
permutation of {(b1 , w1 ), ..., (bk , wk )}.
First, with high probability we know that 1 − 1/poly(d) ≥ |bj | ≥ 1/poly(d) and kwi k ≤ O(d log d)
and kwi − wj k ≥ Ω(d log d) for all i, j. By Lemma E.5, we know that with high probability (a1 , θ1 )
will converge to some (d/)−O(d) neighborhood of (bπ(1) , wπ(1) ) for some function π : [k] → [k]. Now,
we treat a1 , θ1 as one of the fixed charges and note that |a1 | ≤ 1 and kθ1 k ≤ O(d log d) and as long
as k > 1 (if k = 1, we are done), then there exists |bj | ≥ 1/poly(d) with kwi − wj k ≥ Ω(d log d) for
all i and kθ1 − wj k ≥ Ω(d log d).
q
p
(0) (0)
(0) (0)
Then, by Lemma E.4, we can initialize (a2 , θ2 ) such that L2 (a2 , θ2 ) ≤ L2 (0, 0) − δ,
with δ = 1/poly(d)(d/)−18d . Then, by Lemma E.5, we know that (a2 , θ2 ) will converge to some
wπ(2) such that kθ2 − wπ(2) k <  (or kθ2 − θ1 k <  but θ2 is still -close to wπ(1) ). We claim that
π(1) 6= π(2).
By optimality conditions on a2 , we see that
X
a∗2 (θ2 ) = a1 Φ (kθ2 − θ1 k) + bj Φ (kθ1 − wj k) +
bi Φ (kθ1 − wi k)
i6=j

P
If wπ(1) = wπ(2) , then note that kθ1 − wi k ≥ Ω(d log d) for all i 6= π(1). Therefore, 2 i6=j bi Φ (kθ1 −
wi k) = (d/)−O(d) . And by our convergence guarantees and the (d/)2d -Lipschitzness of Φ ,
a1 Φ (kθ2 − θ1 k) + bj Φ (kθ1 − wj k) ≤ (d/)−O(d) . Therefore, a∗2 (θ2 ) ≤ (d/)−O(d) .
However, we see that L2 (a2 , θ2 ) ≥ L2 (a∗2 (θ2 ), θ2 ) = L2 (0, 0) − 12 a∗2 (θ2 )2 ≥ L2 (0, 0) − (d/)−O(d) .
But since L2 is non-increasing, this contradicts our initialization and therefore π(1) 6= π(2). Therefore,
our claim is done and by Lemma E.5, we see that since |bπ(2) | ≥ 1/poly(d) and for all i, kwi −wπ(2) k ≥
25

Ω(d log d) and kθ1 − wπ(2) k ≥ Ω(d log d), we conclude that (a2 , θ2 ) is in a (d/)−O(d) neighborhood
of (bπ(2) , θπ(2) ). Finally, we induct and by similar reasoning, π is a permutation. Now, our theorem
follows.

F

Convergence of Almost Strictly Subharmonic Potentials

Definition F.1. Φ(θ, w) is a strictly subharmonic potential on Ω if it is differentiable and
∆θ Φ(θ, w) > 0 for all θ ∈ Ω, except possibly at θ = w.
An example of such a potential is Φ(θ, w) = kθ − wk2−d− for any  > 0. Although this potential
is unbounded at θ = w for most d, we remark that it is bounded when d = 1. Furthermore, the
sign of the output weights ai , bi matter in determining the sign of the Laplacian of our loss function.
Therefore, we need to make suitable assumptions in this framework.
Under Assumption 1, we are working with an even simpler loss function:
L(θ) = 2

k X
X

Φ(θi , θj ) − 2

i=1 i<j

k X
k
X

Φ(θi , wj )

(3)

i=1 j=1

Theorem F.2. Let Φ be a symmetric strictly subharmonic potential on M with Φ(θ, θ) = ∞. Let
Assumption 1 hold and let L be as in (3). Then, L admits no local minima, except when θi = wj for
some i, j.
Proof. First, let Φ be translationally invariant and M = Rd . Let θ be a critical point. Assume, for
sake of contradiction, that for all i, j, θi 6= wj . If θi are not distinct, separating them shows that we
are not at a local minima since Φ(θi , θj ) = ∞ and finite elsewhere.
The main technical detail is to remove interaction terms between pairwise θi by considering a
correlated movement, where each θi are moved along the same direction v. In this case, notice that
our objective, as a function of v, is simply
H(v) = L(θ1 + v, θ2 + v, ..., θk + v)
=2

k X
X

Φ(θi + v, θj + v) − 2

i=1 i<j

k X
k
X

Φ(θi + v, wj )

i=1 j=1

Note that the first term is constant as a function of v, by translational invariance. Therefore,
∇2v H = −2

k
k X
X

∇2 Φ(θi , wj )

i=1 j=1

P P
By the subharmonic condition, Tr(∇2v H) = −2 ki=1 kj=1 ∆θi Φ(θi , wj ) < 0. Therefore, we conclude
that θ is not a local minima of H and L. We conclude that θi = wj for some i, j.
The above technique generalizes to Φ being rotationally invariant case by working in spherical
coordinates and correlated translations are simply rotations. Note that we can change to spherical
coordinates (without the radius parameter) and let θe1 , ..., θek be the standard spherical representation
of θ1 , ..., θk .
We will consider a correlated translation in the spherical coordinate space, which are simply
rotations on the sphere. Let v be a vector in Rd−1 and our objective is simply
H(v) = L(θe1 + v, ..., θek + v)
26

Then, we apply the same proof since Φ(θei + v, θej + v) is constant as a function of v by rotationally
invariance.
Corollary F.3. Assume the conditions of Theorem F.2 and Φ(θ, θ) < ∞. Then, L admits no local
minima, except at the global minima.
Proof. From the same proof from theorem F.2, we conclude that there must exists i, j such that
θi = wj . Then, since Φ(θ, θ) < ∞, notice that θi , wj cancels each other out and by drop θi , wj from
the loss function, we have a new loss function L with k − 1 variables. Then, using induction, we see
that θi = wπ(i) at the local minima for some permutation π.
For concreteness, we will focus on a specific potential function with this property: the Gaussian
kernel Φ(θ, w) = exp(−kθ − wk2 /2). In Rd , the Laplacian is ∆Φ = (kθ − wk2 − d) exp(−kθ − wk2 /2),
which
becomes positive when kθ − wk2 ≥ d. Thus, Φ√is strictly subharmonic outside a ball of radius
√
d. This informally implies that θ1 converges to a d-ball around some wj .
For concreteness, we will focus on a specific potential function with this property: the Gaussian
kernel Φ(θ, w) = exp(−ckθ − wk2 /2), which corresponds to a Gaussian activation. In Rd , the
Laplacian is ∆Φ = (ckθ − wk2 − d) exp(−ckθ − wk2 /2),p
which becomes positive when kθ − wk2 ≥ d/c.
Thus, Φ is strictly subharmonic outside a ball of radius d/c. Note that Gaussian potential restricted
to S d−1 gives rise to the exponential activation function, so we can show convergence similarly.
2

Theorem F.4. Let M = Rd and Φ(θ, w) = e−ckθ−wk /2 and Assumption 1 holds. Let L be as in
(3) and kwk ≤ poly(d).
If c = O(d/) and (a, θ) ∈ Me−poly(d,1/) , then there exists i, j such that kθi − wj k2 ≤ .
Proof. Consider again a correlated movement, where each θi are moved along the same direction
v. As before, this drops the pairwise θi terms. If for all i, j kθi − wj k2 ≤ , then we see that
∆θi Φ = (ckθ − wk2 − d) exp(−ckθ − wk2 /2) > e−poly(d,1/) .
2

Tr(∇ L) = −2

k X
k
X

∆θi Φ(θi , wj ) < −e−poly(d,1/)

i=1 j=1

Therefore, ∇2 L must admit a strictly negative eigenvalue that is less than e−c3 d , which implies
our claim (we drop the poly(d, k) terms).

G

Common Activations

First, we consider the sign activation function. Under restrictions on the size of the input dimension
or the number of hidden units, we can prove convergence results under the sign activation function,
as it gives rise to a harmonic potential.
Assumption 1. All output weights bi = 1 and therefore the output weights ai = −bi = −1 are fixed
throughout the learning algorithm.
Lemma G.1. Let M = S 1 and let Assumption 1 hold. Let L be as in (2) and σ is the sign activation
function. Then L admits no strict local minima, except at the global minima.

27

We cannot simply analyze the convergence of GD on all θi simultaneously since as before, the
pairwise interaction terms between the θi present complications. Therefore, we now only consider
the convergence guarantee of gradient descent on the first node, θ1 , to some wj , while the other
nodes are inactive (i.e. a2 , ..., ak = 0). In essence, we are working with the following simplified loss
function.
k
X
L(a1 , θ1 ) = a21 Φ(θ1 , θ1 ) + 2
a1 bj Φ(θ1 , wj )
(4)
j=1

Lemma G.2. Let M = S 1 and L be as in (4) and σ is the sign activation function. Then, almost
surely over random choices of b1 , ..., bk , all local minima of L are at ±wj .
For the polynomial activation and potential functions, we also can show convergence under
orthogonality assumptions on wj . Note that the realizability of polynomial potentials is guaranteed
in Section B.
Theorem G.3. Let M = S d−1 . Let w1 , ..., wk be orthonormal vectors in Rd and Φ is of the form
Φ(θ, w) = (θT w)l for some fixed integer l ≥ 3. Let L be as in (4). Then, all critical points of L are
not local minima, except when θ1 = wj for some j.

G.1

Convergence of Sign Activation

Lemma G.1. Let M = S 1 and let Assumption 1 hold. Let L be as in (2) and σ is the sign activation
function. Then L admits no strict local minima, except at the global minima.
Proof. We will first argue that unless all the electrons and protons have matched up as a permutation
it cannot be a strict local minimum and then argue that the global minimum is a strict local
minimum.
First note that if some electron and proton have merged, we can remove such pairs and argue
about the remaining configuration of charges. So WLOG we assume there are no such overlapping
electron and proton.
First consider the case when there is an isolated electron e and there is no charge diagonally
opposite to it. In this case look at the two semicircles on the left and the right half of the circle
around the isolated electron – let q1 and q2 be the net charges in the left and the right semi-circles.
Note that q1 =
6 q2 since they are integers and q1 + q2 = +1 which is odd. So by moving the electron
slightly to the side with the larger charge you decrease the potential.
If there is a proton opposite the isolated electron the argument becomes simpler as the proton
benefits the motion of the electron in either the left or right direction. So the only way the electron
does not benefit by moving in either direction is that q1 = −1 and q2 = −1 which is impossible.
If there is an electron opposite the isolated electron then the combination of these two diagonally
opposing electrons have a zero effect on every other charge. So it is possible rotate this pair jointly
keeping them opposed in any way and not change the potential. So this is not a strict local minimum.
Next if there is a clump of isolated electrons with no charge on the diagonally opposite point
then again as before if q1 6= q2 we are done. If q1 = q2 then the the electrons in the clump locally
are unaffected by the remaining charges. So now by splitting the clump into two groups and moving
them apart infinitesimally we will decrease the potential.
Now if there is only protons in the diagonally opposite position an isolated electron again we are
done as in the case when there is one electron diagonally opposite one proton.
Finally if there is only electrons diagonally opposite a clump of electrons again we are done as
we have found at least one pair of opposing electrons that can be jointly rotated in any way.
28

Next we will argue that a permutation matching up is a strict local minumum. For this we will
assume that no two protons are diagonally opposite each other (as they can be removed without
affecting the function). Now given a perfect matching up of electrons and protons, if we perturb the
electrons in any way infinitesimally, then any isolated clump of electrons can be moved slightly to
the left or right to improve the potential.
Lemma G.2. Let M = S 1 and L be as in (4) and σ is the sign activation function. Then, almost
surely over random choices of b1 , ..., bk , all local minima of L are at ±wj .
Proof. In S 1 , notice that the pairwise potential function is Φ(θ, w) = 1 − 2 cos−1 (θT w)/π = 1 − 2α/π,
where α is the angle between θ, w. So, let us parameterize in polar coordinates, calling our true
parameters as w
f1 , ..., w
fk ∈ [0, 2π] and rewriting our loss as a function of θe ∈ [0, 2π].
Since Φ is a linear function of the angle between θ, wj , each wj exerts a constant gradient on θe
towards w
fj , with discontinuities at w
fj , π + w
fj . Almost surely over b1 , .., bk , the gradient is non-zero
almost everywhere, except at the discontinuities, which are at w
fj , π + w
fj for some j.

G.2

Convergence of Polynomial Potentials

Theorem G.3. Let M = S d−1 . Let w1 , ..., wk be orthonormal vectors in Rd and Φ is of the form
Φ(θ, w) = (θT w)l for some fixed integer l ≥ 3. Let L be as in (4). Then, all critical points of L are
not local minima, except when θ1 = wj for some j.
Proof. WLOG, we can consider w1 , ..., wd to be the basis vectors e1 , ..., ed . Note that this is a
manifold optimization problem, so our optimality conditions are given by introducing a Lagrange
multiplier λ, as in [GHJY15].
d
X
∂L
=2
abi (θi )l + 2a = 0
∂a
i=1

(∇θ L)i = 2abi l(θi )l−1 − 2λθi = 0
where λ is chosen that minimizes
λ = arg min
λ

X

(abi l(θi )l−1 − λθi )2 =

X

abi l(θi )l

i

Therefore, either θi = 0 or bi (θi )l−2 = λ/(al). From [GHJY15], we consider the constrained Hessian,
which is a diagonal matrix with diagonal entry:
(∇2 L)ii = 2abi l(l − 1)(θi )l−2 − 2λ
Assume that there exists θi , θj 6= 0, then we claim that θ is not a local minima. First, our optimality
conditions imply bi (θi )l−2 = bj (θj )l−2 = λ/(al). So,
(∇2 L)ii = (∇2 L)jj = 2abi l(l − 1)(θi )l−2 − 2λ
= 2(l − 2)λ = −2(l − 2)la2
Now, there must exist a vector v ∈ S d−1 such that vk = 0 for k 6= i, j and v T θ = 0, so v is in the
tangent space at θ. Finally, v T (∇2 L)v = −2(l − 2)la2 < 0, implying θ is not a local minima when
a 6= 0. Note that a = 0 occurs with probability 0 since our objective function is non-increasing
throughout the gradient descent algorithm and is almost surely initialized to be negative with a
optimized upon initialization, as by observed before.
29

Under a node-wise descent algorithm, we can show polynomial-time convergence to global minima
under orthogonality assumptions on wj for these polynomial activations/potentials. We will not
include the proof but it follows from similar techniques presented for nodewise convergence in
Section E.

H

Proof of Sign Uniqueness

For the sign activation function, we can show a related result.
Theorem H.1. Let M = S d−1 and σ be the sign activation function and b2 , ...,
√ bk = 0. If the loss
(1) at (a, θ) is less than O(1), then there must exist θi such that w1T θi > Ω(1/ k).
Proof. WLOG let w1 = e1 . Notice that our loss can be bounded below by Jensen’s:

!2 
k
X
E
ai σ(θiT X) − σ(X1 ) 
X

i=1


≥ E
X1

" k
X

E

X2 ...Xd

!2 
ai σ(θiT X) − σ(X1 )  ,
#

i=1

where X is a standard Gaussian in Rd .


" k
#
k
X
X
X
EX2 ,..,Xd
ai σ(θiT X) =
ai EX2 ,...Xd σ(θi1 X1 +
θij Xj )
i=1

i=1

j>1



k
q
X
2
=
EY σ(θi1 X1 + 1 − θi1 Y )
=

i=1
k
X


ai EY

σ( √ θi1



2
1−θi1

i=1

X1 + Y ) ,

where Y is an independent standard Gaussian and for any small δ, if p(y) is the standard Gaussian
density,
Z δ
EY [σ(δ + Y )] =
p(y) dy = 2p(0)δ + O(δ 2 )
−δ

If w1T θi = θi1 <  for all i, then notice that with high probability on X1 (say condition on
|X1 | ≤ 1),


θ
i1
E σ( √ 2 X1 + Y ) = 2p(0) √ θi1 2 X1 + O(2 X12 )
1−θi1

Y

1−θi1

√
Therefore, since  < O(1/ k),
" k
#
k
X
X
T
E
ai σ(θi X) = X1
2p(0)ai √ θi1
X2 ,..,Xd

i=1

i=1

= cX1 + O(1)

30

2
1−θi1

+ O(k2 X12 )

Finally, our error bound is now

E

X1

"
E

X2 ...Xd

≥

k
X

#
ai σ(θiT X) − σ(X1 )

!2 


i=1

E [(cX1 + O(1) − σ(X1 ))2 ]

|X1 |≤1

And the final expression is always larger than some constant, regardless of c.

31

