Deep Hyperspherical Learning

Weiyang Liu1 , Yan-Ming Zhang2 , Xingguo Li3,1 , Zhiding Yu4 , Bo Dai1 , Tuo Zhao1 , Le Song1

Georgia Institute of Technology 2 Institute of Automation, Chinese Academy of Sciences
3
University of Minnesota 4 Carnegie Mellon University
{wyliu,tourzhao}@gatech.edu, ymzhang@nlpr.ia.ac.cn, lsong@cc.gatech.edu

arXiv:1711.03189v5 [cs.LG] 30 Jan 2018

1

Abstract
Convolution as inner product has been the founding basis of convolutional neural
networks (CNNs) and the key to end-to-end visual representation learning. Benefiting from deeper architectures, recent CNNs have demonstrated increasingly
strong representation abilities. Despite such improvement, the increased depth and
larger parameter space have also led to challenges in properly training a network.
In light of such challenges, we propose hyperspherical convolution (SphereConv),
a novel learning framework that gives angular representations on hyperspheres.
We introduce SphereNet, deep hyperspherical convolution networks that are distinct from conventional inner product based convolutional networks. In particular,
SphereNet adopts SphereConv as its basic convolution operator and is supervised
by generalized angular softmax loss - a natural loss formulation under SphereConv.
We show that SphereNet can effectively encode discriminative representation and
alleviate training difficulty, leading to easier optimization, faster convergence and
comparable (even better) classification accuracy over convolutional counterparts.
We also provide some theoretical insights for the advantages of learning on hyperspheres. In addition, we introduce the learnable SphereConv, i.e., a natural
improvement over prefixed SphereConv, and SphereNorm, i.e., hyperspherical
learning as a normalization method. Experiments have verified our conclusions.

1

Introduction

Recently, deep convolutional neural networks have led to significant breakthroughs on many vision
problems such as image classification [9, 18, 19, 6], segmentation [3, 13, 1], object detection [3, 16],
etc. While showing stronger representation power over many conventional hand-crafted features,
CNNs often require a large amount of training data and face certain training difficulties such as
overfitting, vanishing/exploding gradient, covariate shift, etc. The increasing depth of recently
proposed CNN architectures have further aggravated the problems.
To address the challenges, regularization techniques such as dropout [9] and orthogonality parameter
constraints [21] have been proposed. Batch normalization [8] can also be viewed as an implicit
regularization to the network, by normalizing each layer’s output distribution. Recently, deep
residual learning [6] emerged as a promising way to overcome vanishing gradients in deep networks.
However, [20] pointed out that residual networks (ResNets) are essentially an exponential ensembles
of shallow networks where they avoid the vanishing/exploding gradient problem but do not provide
direct solutions. As a result, training an ultra-deep network still remains an open problem. Besides
vanishing/exploding gradient, network optimization is also very sensitive to initialization. Finding
better initializations is thus widely studied [5, 14, 4]. In general, having a large parameter space is
double-edged considering the benefit of representation power and the associated training difficulties.
Therefore, proposing better learning frameworks to overcome such challenges remains important.
In this paper, we introduce a novel convolutional learning framework that can effectively alleviate
training difficulties, while giving better performance over dot product based convolution. Our idea
31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.

w θ(w,x) x
g(θ(w,x) ) SphereConv

SphereConv
Operator

Operator

...

w3

...

x

x

...

SphereConv
Operator

x

...

w1

x

SphereConv
Operator

x

...
...

x

w2

Cross-entropy

w4

Softmax

x

x

x

Hyperspherical Convolutions

Generalized Angular
Softmax Loss

Figure 1: Deep hyperspherical convolutional network architecture.

is to project parameter learning onto unit hyperspheres, where layer activations only depend on
the geodesic distance between kernels and input signals1 instead of their inner products. To this
end, we propose the SphereConv operator as the basic module for our network layers. We also
propose softmax losses accordingly under such representation framework. Specifically, the proposed
softmax losses supervise network learning by also taking the SphereConv activations from the last
layer instead of inner products. Note that the geodesic distances on a unit hypersphere is the angles
between inputs and kernels. Therefore, the learning objective is essentially a function of the input
angles and we call it generalized angular softmax loss in this paper. The resulting architecture is the
hyperspherical convolutional network (SphereNet), which is shown in Fig. 1.
Our key motivation to propose SphereNet is that angular information matters in convolutional
representation learning. We argue this motivation from several aspects: training stability, training
efficiency, and generalization power. SphereNet can also be viewed as an implicit regularization to
the network by normalizing the activation distributions. The weight norm is no longer important since
the entire network operates only on angles. And as a result, the `2 weight decay is also no longer
needed in SphereNet. SphereConv to some extent also alleviates the covariate shift problem [8]. The
output of SphereConv operators are bounded from −1 to 1 (0 to 1 if considering ReLU), which makes
the variance of each output also bounded.
Our second intuition is that angles preserve the most abundant discriminative information in convolutional learning. We gain such intuition from 2D Fourier transform, where an image is decomposed by
the combination of a set of templates with magnitude and phase information in 2D frequency domain.
If one reconstructs an image with original magnitudes and random phases, the resulting images
are generally not recognizable. However, if one reconstructs the image with random magnitudes
and original phases. The resulting images are still recognizable. It shows that the most important
structural information in an image for visual recognition is encoded by phases. This fact inspires us
to project the network learning into angular space. In terms of low-level information, SphereConv is
able to preserve the shape, edge, texture and relative color. SphereConv can learn to selectively drop
the color depth but preserve the RGB ratio. Thus the semantic information of an image is preserved.
SphereNet can also be viewed as a non-trivial generalization of [11, 12]. By proposing a loss that
discriminatively supervises the network on a hypersphere, [12] achieves state-of-the-art performance
on face recognition. However, the rest of the network remains a conventional convolution network.
In contrast, SphereNet not only generalizes the hyperspherical constraint to every layer, but also
to different nonlinearity functions of input angles. Specifically, we propose three instances of
SphereConv operators: linear, cosine and sigmoid. The sigmoid SphereConv is the most flexible one
with a parameter controlling the shape of the angular function. As a simple extension to the sigmoid
SphereConv, we also present a learnable SphereConv operator. Moreover, the proposed generalized
angular softmax (GA-Softmax) loss naturaly generalizes the angular supervision in [12] using the
SphereConv operators. Additionally, the SphereConv can serve as a normalization method that is
comparable to batch normalization, leading to an extension to spherical normalization (SphereNorm).
SphereNet can be easily applied to other network architectures such as GoogLeNet [19], VGG [18]
and ResNet [6]. One simply needs to replace the convolutional operators and the loss functions with
the proposed SphereConv operators and hyperspherical loss functions. In summary, SphereConv can
be viewed as an alternative to the original convolution operators, and serves as a new measure of
correlation. SphereNet may open up an interesting direction to explore the neural networks. We ask
the question whether inner product based convolution operator is an optimal correlation measure for
all tasks? Our answer to this question is likely to be “no”.
1

Without loss of generality, we study CNNs here, but our method is generalizable to any other neural nets.

2

2
2.1

Hyperspherical Convolutional Operator
Definition

The convolutional operator in CNNs is simply a linear matrix multiplication, written as F(w, x) =
w> x + bF where w is a convolutional filter, x denotes a local patch from the bottom feature map
and bF is the bias. The matrix multiplication here essentially computes the similarity between the
local patch and the filter. Thus the standard convolution layer can be viewed as patch-wise matrix
multiplication. Different from the standard convolutional operator, the hyperspherical convolutional
(SphereConv) operator computes the similarity on a hypersphere and is defined as:
Fs (w, x) = g(θ(w,x) ) + bFs ,

(1)

where θ(w,x) is the angle between the kernel parameter w and the local patch x. g(θ(w,x) ) indicates
a function of θ(w,x) (usually a monotonically decreasing function), and bFs is the bias. To simplify
analysis and discussion, the bias terms are usually left out. The angle θ(w,x) can be interpreted
as the geodesic distance (arc length) between w and x on a unit hypersphere. In contrast to the
convolutional operator that works in the entire space, SphereConv only focuses on the angles between
local patches and the filters, and therefore operates on the hypersphere space. In this paper, we present
three specific instances of the SphereConv Operator. To facilitate the computation, we constrain the
output of SphereConv operators to [−1, 1] (although it is not a necessary requirement).
Linear SphereConv. In linear SphereConv operator, g is a linear function of θ(w,x) , with the form:
g(θ(w,x) ) = aθ(w,x) + b,

(2)

where a and b are parameters for the linear SphereConv operator. In order to constrain the output
range to [0, 1] while θ(w,x) ∈ [0, π], we use a = − π2 and b = 1 (not necessarily optimal design).
Cosine SphereConv. The cosine SphereConv operator is a nonlinear function of θ(w,x) , with its g being the form of

1

(3)

0.5

w x
which can be reformulated as kwk
. Therefore, it can be
2 kxk2
viewed as a doubly normalized convolutional operator, which
bridges the SphereConv operator and convolutional operator.

0

g(θ(w,x) ) = cos(θ(w,x) ),
T

Sigmoid SphereConv. The Sigmoid SphereConv operator is
derived from the Sigmoid function and its g can be written as
g(θ(w,x) ) =

1+
1−

π
exp(− 2k
)
π
exp(− 2k
)

·

1 − exp
1 + exp

θ(w,x)
k
θ(w,x)
k

Cosine
Linear
Sigmoid (k=0.1)
Sigmoid (k=0.3)
Sigmoid (k=0.7)

-0.5
-1

0

0.5

1

1.5

2

2.5

3

Figure 2: SphereConv operators.
−

π
2k

−

π
2k


,

(4)

where k > 0 is the parameter that controls the curvature of the function. While k is close to 0,
g(θ(w,x) ) will approximate the step function. While k becomes larger, g(θ(w,x) ) is more like a linear
function, i.e., the linear SphereConv operator. Sigmoid SphereConv is one instance of the parametric
SphereConv family. With more parameters being introduced, the parametric SphereConv can have
richer representation power. To increase the flexibility of the parametric SphereConv, we will discuss
the case where these parameters can be jointly learned via back-prop later in the paper.
2.2

Optimization

The optimization of the SphereConv operators is nearly the same as the convolutional operator
and also follows the standard back-propagation. Using the chain rule, we have the gradient of the
SphereConv with respect to the weights and the feature input:
∂g(θ(w,x) )
∂g(θ(w,x) ) ∂θ(w,x)
=
·
,
∂w
∂θ(w,x)
∂w

For different SphereConv operators, both
lies in the

∂g(θ(w,x) )
∂θ(w,x)

part. For

∂θ(w,x)
∂w ,

∂g(θ(w,x) )
∂g(θ(w,x) ) ∂θ(w,x)
=
·
.
∂x
∂θ(w,x)
∂x

∂θ(w,x)
∂w

we have

wT x

and

∂θ(w,x)
∂x

(5)

are the same, so the only difference
T



w x
∂ arccos kwk
∂θ(w,x)
2 kxk2
=
,
∂x
∂x

∂ arccos kwk2 kxk2
∂θ(w,x)
=
,
∂w
∂w

∂g(θ

(6)
)

(w,x)
which are straightforward to compute and therefore neglected here. Because ∂θ(w,x)
for the
linear SphereConv, the cosine SphereConv and the Sigmoid SphereConv are a, − sin(θ(w,x) ) and

−2 exp(θ(w,x) /k−π/2k)
k(1+exp(θ(w,x) /k−π/2k))2

respectively, all these partial gradients can be easily computed.
3

2.3

Theoretical Insights

We provide a fundamental analysis for the cosine SphereConv operator in the case of linear neural
network to justify that the SphereConv operator can improve the conditioning of the problem. In
specific, we consider one layer of linear neural network, where the observation is F = U ∗ V ∗>
(ignore the bias), U ∗ ∈ Rn×k is the weight, and V ∗ ∈ Rm×k is the input that embeds weights from
previous layers. Without loss of generality, we assume the columns satisfying kUi,: k2 = kVj,: k2 = 1
for all i = 1, . . . , n and j = 1, . . . , m, and consider
min

U ∈Rn×k ,V ∈Rm×k

G(U , V ) = 21 kF − U V > k2F .

(7)

This is closely related with the matrix factorization and (7) can be also viewed as the expected version
for the matrix sensing problem [10]. The following lemma demonstrates a critical scaling issue of (7)
for U and V that significantly deteriorate the conditioning without changing the objective of (7).
Lemma 1. Consider a pair of global optimal points U , V satisfying F = U V > and Tr(V > V ⊗
e = cU and Ve = V /c, then we have
In ) ≤ Tr(U > U ⊗ Im ). For any real c > 1, let U
λ
2
2
2
max
e , Ve )) = Ω(c κ(∇ G(U , V ))), where κ =
κ(∇ G(U
λmin is the restricted condition number with
λmax being the largest eigenvalue and λmin being the smallest nonzero eigenvalue.
Lemma 1 implies that the conditioning of the problem (7) at a unbalanced global optimum scaled by
a constant c is Ω(c2 ) times larger than the conditioning of the problem at a balanced global optimum.
Note that λmin = 0 may happen, thus we consider the restricted condition here. Similar results hold
beyond global optima. This is an undesired geometric structure, which further leads to slow and
unstable optimization procedures, e.g., using stochastic gradient descent (SGD). This motivates us to
consider the SphereConv operator discussed above, which is equivalent to projecting data onto the
hypersphere and leads to a better conditioned problem.
Next, we consider our proposed cosine SphereConv operator for one-layer of the linear neural
network. Based on our previous discussion on SphereConv, we consider an equivalent problem:
min

U ∈Rn×k ,V ∈Rm×k

1

1

GS (U , V ) = 21 kF − DU U V > DV k2F ,



n×n

(8)
1

1



where DU = diag kU1,: k2 , . . . , kUn,: k2 ∈ R
and DV = diag kV1,: k2 , . . . , kVm,: k2 ∈
m×m
R
are diagonal matrices. We provide an analogous result to Lemma 1 for (8) .
e , Ve )) =
e = cU and Ve = V /c, then we have λi (∇2 GS (U
Lemma 2. For any real c > 1, let U
2
2
e
λi (∇ GS (U , V )) for all i ∈ [(n + m)k] = {1, 2, . . . , (n + m)k} and κ(∇ G(U , Ve )) =
κ(∇2 G(U , V )), where κ is defined as in Lemma 1.
We have from Lemma 2 that the issue of increasing condition caused by the scaling is eliminated by
the SphereConv operator in the entire parameter space. This enhances the geometric structure over
(7), which further results in improved convergence of optimization procedures. If we extend the result
from one layer to multiple layers, the scaling issue propagates. Roughly speaking, when we train N
layers, in the worst case, the conditioning of the problem can be cN times worse with a scaling factor
c > 1. The analysis is similar to the one layer case, but the computation of the Hessian matrix and
associated eigenvalues are much more complicated. Though our analysis is elementary, we provide
an important insight and a straightforward illustration of the advantage for using the SphereConv
operator. The extension to more general cases, e..g, using nonlinear activation function (e.g., ReLU),
requires much more sophisticated analysis to bound the eigenvalues of Hessian for objectives, which
is deferred to future investigation.
2.4

Discussion

Comparison to convolutional operators. Convolutional operators compute the inner product between the kernels and the local patches, while the SphereConv operators compute a function of the
angle between the kernels and local patches. If we normalize the convolutional operator in terms of
both w and x, then the normalized convolutional operator is equivalent to the cosine SphereConv
operator. Essentially, they use different metric spaces. Interestingly, SphereConv operators can also
be interpreted as a function of the Geodesic distance on a unit hypersphere.
Extension to fully connected layers. Because the fully connected layers can be viewed as a special
convolution layer with the kernel size equal to the input feature map, the SphereConv operators could
be easily generalized to the fully connected layers. It also indicates that SphereConv operators could
be used not only to deep CNNs, but also to linear models like logistic regression, SVM, etc.
4

Network Regularization. Because the norm of weights is no longer crucial, we stop using the `2
weight decay to regularize the network. SphereNets are learned on hyperspheres, so we regularize the
network based on angles instead of norms. To avoid redundant kernels, we want the kernels uniformly
spaced around the hypersphere, but it is difficult to formulate such constraints. As a tradeoff, we
encourage the orthogonality. Given a set of kernels W where the i-th column Wi is the weights of
the i-th kernel, the network will also minimize kW > W − Ik2F where I is an identity matrix.
Determining the optimal SphereConv. In practice, we could treat different types of SphereConv as
a hyperparameter and use the cross validation to determine which SphereConv is the most suitable
one. For sigmoid SphereConv, we could also use the cross validation to determine its hyperparameter
k. In general, we need to specify a SphereConv operator before using it, but prefixing a SphereConv
may not be an optimal choice (even using cross validation). What if we treat the hyperparameter k in
sigmoid SphereConv as a learnable parameter and use the back-prop to learn it? Following this idea,
we further extend sigmoid SphereConv to a learnable SphereConv in the next subsection.
SphereConv as normalization. Because SphereConv could partially address the covariate shift, it
could also serve as a normalization method similar to batch normalization. Differently, SphereConv
normalizes the network in terms of feature map and kernel weights, while batch normalization is for
the mini-batches. Thus they do not contradict with each other and can be used simultaneously.
2.5 Extension: Learnable SphereConv and SphereNorm
Learnable SphereConv. It is a natrual idea to replace the current prefixed SphereConv with a
learnable one. There will be plenty of parametrization choices for the SphereConv to be learnable,
and we present a very simple learnable SphereConv operator based on the sigmoid SphereConv.
Because the sigmoid SphereConv has a hyperparameter k, we could treat it as a learnable parameter
that can be updated by back-prop. In back-prop, k is updated using k t+1 = k t + η ∂L
∂k where t denotes
∂L
the current iteration index and ∂k can be easily computed by the chain rule. Usually, we also require
k to be positive. The learning of k is in fact similar to the parameter learning in PReLU [5].
SphereNorm: hyperspherical learning as a normalization method. Similar to batch normalization (BatchNorm), we note that the hyperspherical learning can also be viewed as a way of
normalization, because SphereConv constrain the output value in [−1, 1] ([0, 1] after ReLU). Different from BatchNorm, SphereNorm normalizes the network based on spatial information and the
weights, so it has nothing to do with the mini-batch statistic. Because SphereNorm normalize both
the input and weights, it could avoid covariate shift due to large weights and large inputs while
BatchNorm could only prevent covariate shift caused by the inputs. In such sense, it will work better
than BatchNorm when the batch size is small. Besides, SphereConv is more flexible in terms of
design choices (e.g. linear, cosine, and sigmoid) and each may lead to different advantages.
Similar to BatchNorm, we could use a rescaling strategy for the SphereNorm. Specifically, we rescale
the output of SphereConv via βFs (w, x) + γ where β and γ are learned by back-prop (similar to
BatchNorm, the rescaling parameters can be either learned or prefixed). In fact, SphereNorm does not
contradict with the BatchNorm at all and can be used simultaneously with BatchNorm. Interestingly,
we find using both is empirically better than using either one alone.

3

Learning Objective on Hyperspheres

For learning on hyperspheres, we can either use the conventional loss function such as softmax loss,
or use some loss functions that are tailored for the SphereConv operators. We present some possible
choices for these tailored loss functions.
Weight-normalized Softmax Loss. The input feature and its label are denoted as xi and yi , respec
P
P
fy
tively. The original softmax loss can be written as L = N1 i Li = N1 i − log Pe eifj where N
j

is the number of training samples and fj is the score of the j-th class (j ∈ [1, K], K is the number of
classes). The class score vector f is usually the output of a fully connected layer W , so we have
fj = Wj> xi + bj and fyi = Wy>i xi + byi in which xi , Wj , and Wyi are the i-th training sample, the
j-th and yi -th column of W respectively. We can rewrite Li as

Li = − log

Wy> xi +byi

e
P

j

i

e

Wj> xi +bj




= − log

ekWyi kkxi k cos(θyi ,i )+byi
P kW kkx k cos(θ )+b
j
i
j,i
j
je


,

(9)

where θj,i (0 ≤ θj,i ≤ π) is the angle between vector Wj and xi . The decision boundary of the
original softmax loss is determined by the vector f . Specifically in the binary-class case, the
5

decision boundary of the softmax loss is W1> x + b1 = W2> x + b2 . Considering the intuition of the
SphereConv operators, we want to make the decision boundary only depend on the angles. To this
end, we normalize the weights (kWj k = 1) and zero out the biases (bj = 0), following the intuition in
[12] (sometimes we could keep the biases while data is imbalanced). The decision boundary becomes
kxk cos(θ1 ) = kxk cos(θ2 ). Similar to SphereConv, we could generalize the decision boundary to
kxkg(θ1 ) = kxkg(θ2 ), so the weight-normalized softmax (W-Softmax) loss can be written as

Li = − log


ekxi kg(θyi ,i )
P kx kg(θ ) ,
i
j,i
je

(10)

where g(·) can take the form of linear SphereConv, cosine SphereConv, or sigmoid SphereConv.
Thus we also term these three difference weight-normalized loss functions as linear W-Softmax loss,
cosine W-Softmax loss, and sigmoid W-Softmax loss, respectively.
Generalized Angular Softmax Loss. Inspired by [12], we use a multiplicative parameter m to impose margins on hyperspheres. We propose a generalized angular softmax (GA-Softmax) loss which
extends the W-Softmax loss to a loss function that favors large angular margin feature distribution. In
general, the GA-Softmax loss is formulated as

Li = − log


ekxi kg(mθyi ,i )
,
P
ekxi kg(mθyi ,i ) + j6=yi ekxi kg(θj,i )

(11)

where g(·) could also have the linear, cosine and sigmoid form, similar to the W-Softmax loss. We can
see A-Softmax loss [12] is exactly the cosine GA-Softmax loss and W-Softmax loss is the special case
π
], because cos(θj,i ) is only
(m = 1) of GA-Sofmtax loss. Note that we usually require θj,i ∈ [0, m
monotonically decreasing in [0, π]. To address this, [11, 12] construct a monotonically decreasing
π
function recursively using the [0, m
] part of cos(mθj,i ). Although it indeed partially addressed the
issue, it may introduce a number of saddle points (w.r.t. W ) in the loss surfaces. Originally, ∂g
∂θ will
be close to 0 only when θ is close to 0 and π. However, in L-Softmax [11] or A-Softmax (cosine
kθ
GA-Softmax), it is not the case. ∂g
∂θ will be 0 when θ = m , k = 0, · · · , m. It will possibly cause
instability in training. The sigmoid GA-Softmax loss also has similar issues. However, if we use
the linear GA-Softmax loss, this problem will be automatically solved and the training will possibly
become more stable in practice. There will also be a lot of choices of g(·) to design a specific
GA-Sofmtax loss, and each one has different optimization dynamics. The optimal one may depend
on the task itself (e.g. cosine GA-Softmax has been shown effective in deep face recognition [12]).
Discussion of Sphere-normalized Softmax Loss. We have also considered the sphere-normalized
softmax loss (S-Softmax), which simultaneously normalizes the weights (Wj ) and the feature x.
It seems to be a more natural choice than W-Softmax for the proposed SphereConv and makes the
entire framework more unified. In fact, we have tried this and the empirical results are not that good,
because the optimization seems to become very difficult. If we use the S-Softmax loss to train a
network from scratch, we can not get reasonable results without using extra tricks, which is the reason
we do not use it in this paper. For completeness, we give some discussions here. Normally, it is very
difficult to make the S-Softmax loss value to be small enough, because we normalize the features to
unit hypersphere. To make this loss work, we need to either normalize the feature to a value much
larger than 1 (hypersphere with large radius) and then tune the learning rate or first train the network
with the softmax loss from scratch and then use the S-Softmax loss for finetuning.

4
4.1

Experiments and Results
Experimental Settings

We will first perform comprehensive ablation study and exploratory experiments for the proposed
SphereNets, and then evaluate the SphereNets on image classification. For the image classification
task, we perform experiments on CIFAR10 (only with random left-right flipping), CIFAR10+ (with
full data augmentation), CIFAR100 and large-scale Imagenet 2012 datasets [17].
General Settings. For CIFAR10, CIFAR10+ and CIFAR100, we follow the same settings from
[7, 11]. For Imagenet 2012 dataset, we mostly follow the settings in [9]. We attach more details in
Appendix B. For fairness, batch normalization and ReLU are used in all methods if not specified. All
the comparisons are made to be fair. Compared CNNs have the same architecture with SphereNets.
Training. Appendix A gives the network details. For CIFAR-10 and CIFAR-100, we use the ADAM,
starting with the learning rate 0.001. The batch size is 128 if not specified. The learning rate is divided
by 10 at 34K, 54K iterations and the training stops at 64K. For both A-Softmax and GA-Softmax loss,
6

we use m = 4. For Imagenet-2012, we use the SGD with momentum 0.9. The learning rate starts
with 0.1, and is divided by 10 at 200K and 375K iterations. The training stops at 550K iteration.
4.2

Ablation Study and Exploratory Experiments

We perform comprehensive Ablation and exploratory study on the SphereNet and evaluate every
component individually in order to analyze its advantages. We use the 9-layer CNN as default (if not
specified) and perform the image classification on CIFAR-10 without any data augmentation.
SphereConv
Operator / Loss

Original
Softmax

Sigmoid (0.1)
W-Softmax

Sigmoid (0.3)
W-Softmax

Sigmoid (0.7)
W-Softmax

Linear
W-Softmax

Cosine
W-Softmax

A-Softmax
(m=4)

GA-Softmax
(m=4)

Sigmoid (0.1)
Sigmoid (0.3)
Sigmoid (0.7)
Linear
Cosine
Original Conv

90.97
91.08
91.05
91.10
90.89
90.58

90.91
91.44
91.16
90.93
90.88
90.58

90.89
91.37
91.47
91.42
91.08
90.73

90.88
91.21
91.07
90.96
91.22
90.78

91.07
91.34
90.99
90.95
91.17
91.08

91.13
91.28
91.18
91.24
90.99
90.68

91.87
92.13
92.22
92.21
91.94
91.78

91.99
92.38
92.36
92.32
92.19
91.80

Table 1: Classification accuracy (%) with different loss functions.

Comparison of different loss functions. We first evaluate all the SphereConv operators with
different loss functions. All the compared SphereConv operators use the 9-layer CNN architecture
in the experiment. From the results in Table 1, one can observe that the SphereConv operators
consistently outperforms the original convolutional operator. For the compared loss functions except
A-Softmax and GA-Softmax, the effect on accuracy seems to less crucial than the SphereConv
operators, but sigmoid W-Softmax is more flexible and thus works slightly better than the others.
The sigmoid SphereConv operators with a suitably chosen parameter also works better than the
others. Note that, W-Softmax loss is in fact comparable to the original softmax loss, because our
SphereNet optimizes angles and the W-Softmax is derived from the original softmax loss. Therefore,
it is fair to compare the SphereNet with W-Softmax and CNN with softmax loss. From Table 1,
we can see SphereConv operators are consistently better than the covolutional operators. While
we use a large-margin loss function like the A-Softmax [12] and the proposed GA-Softmax, the
accuracy can be further boosted. One may notice that A-Softmax is actually cosine GA-Softmax. The
superior performance of A-Softmax with SphereNet shows that our architecture is more suitable for
the learning of angular loss. Moreover, our proposed large-margin loss (linear GA-Softmax) performs
the best among all these compared loss functions.
Comparison of different network architectures. We are also interested in how our SphereConv
operators work in different architectures. We evaluate all the proposed SphereConv operators with
the same architecture of different layers and a totally different architecture (ResNet). Our baseline
CNN architecture follows the design of VGG network [18] only with different convolutional layers.
For fair comparison, we use cosine W-Softmax for all SphereConv operators and original softmax
for original convolution operators. From the results in Table 2, one can see that SphereNets greatly
outperforms the CNN baselines, usually with more than 1% improvement. While applied to ResNet,
our SphereConv operators also work better than the baseline. Note that, we use the similar ResNet
architecture from the CIFAR-10 experiment in [6]. We do not use data augmentation for CIFAR-10
in this experiment, so the ResNet accuracy is much lower than the reported one in [6]. Our results on
different network architectures show consistent and significant improvement over CNNs.
SphereConv Operator

CNN-3

CNN-9

CNN-18

CNN-45

CNN-60

ResNet-32

SphereConv Operator

Acc. (%)

Sigmoid (0.1)
Sigmoid (0.3)
Sigmoid (0.7)
Linear
Cosine
Original Conv

82.08
81.92
82.4
82.31
82.23
81.19

91.13
91.28
91.18
91.15
90.99
90.68

91.43
91.55
91.69
91.24
91.23
90.62

89.34
89.73
89.85
90.15
90.05
88.23

87.67
87.85
88.42
89.91
89.28
88.15

90.94
91.7
91.19
91.25
91.38
90.40

Sigmoid (0.1)
Sigmoid (0.3)
Sigmoid (0.7)
Linear
Cosine
CNN w/o ReLU

86.29
85.67
85.51
85.34
85.25
80.73

Table 2: Classification accuracy (%) with different network architectures.

Table 3: Acc. w/o ReLU.

Comparison of different width (number of filters). We evaluate the SphereNet with different
number of filters. Fig. 3(c) shows the convergence of different width of SphereNets. 16/32/48 means
conv1.x, conv2.x and conv3.x have 16, 32 and 48 filters, respectively. One could observe that while
the number of filters are small, SphereNet performs similarly to CNNs (slightly worse). However,
while we increase the number of filters, the final accuracy will surpass the CNN baseline even faster
and more stable convergence performance. With large width, we find that SphereNets perform
consistently better than CNN baselines, showing that SphereNets can make better use of the width.
Learning without ReLU. We notice that SphereConv operators are no longer a matrix multiplication,
so it is essentially a non-linear function. Because the SphereConv operators already introduce certain
7

1
0.9

0.6
0.5
0.4
0.3

ResNet baseline on CIFAR10
ResNet baseline on CIFAR10+
SphereResNet (Sigmoid 0.3) on CIFAR10
SphereResNet (Sigmoid 0.3) on CIFAR10+

0.2
0.1
0

0

1

2

3

4

Iteration

5

6

(a) ResNet vs. SphereResNet
on CIFAR-10/10+

7
x104

0.7

Testing Accuracy

0.7

0.6
0.5

CNN Baseline
SphereNet (cosine) w/o orth.
SphereNet (cosine) w/ orth.
SphereNet (linear) w/ orth.
SphereNet (Sigmoid 0.3) w/ orth.

0.4
0.3
0.2
0.1

0

1

2

3

4

Iteration

5

6

(b) CNN vs. SphereNet (orth.)
on CIFAR-10

0.915

0.7

0.91

0.9

0.5

5.5

6

CNN 16/32/48
SphereNet 16/32/48
CNN 64/96/128
SphereNet 64/96/128
CNN 128/192/256
SphereNet 128/192/256
CNN 256/384/512
SphereNet 256/384/512

0.4
0.3

0.1

0.7

0.905

0.6

0.2
7
x10 4

69-layer CNN
69-layer SphereNet

0.8

0.8

0.8

Testing Accuracy

Testing Accuracy

0.8

0.9

0.9

0

1

2

3

Iteration

4

5

6.5
4
x10

Testing Accuracy

1
0.9

0.6
0.5
0.4
0.3
0.2
0.1

6

0
x10 4

(c) Different width of SphereNet
on CIFAR-10

0

0.5

1

1.5

2

Iteration

2.5

3

3.5

(d) Deep CNN vs. SphereNet
on CIFAR-10

4
x10 4

Figure 3: Testing accuracy over iterations. (a) ResNet vs. SphereResNet. (b) Plain CNN vs. plain SphereNet. (c)
Different width of SphereNet. (d) Ultra-deep plain CNN vs. ultra-deep plain SphereNet.

non-linearity to the network, we evaluate how much gain will such non-linearity bring. Therefore, we
remove the ReLU activation and compare our SphereNet with the CNNs without ReLU. The results
are given in Table 3. All the compared methods use 18-layer CNNs (with BatchNorm). Although
removing ReLU greatly reduces the classification accuracy, our SphereNet still outperforms the CNN
without ReLU by a significant margin, showing its rich non-linearity and representation power.
Convergence. One of the most significant advantages of SphereNet is its training stability and
convergence speed. We evaluate the convergence with two different architectures: CNN-9 and
ResNet-32. For fair comparison, we use the original softmax loss for all compared methods (including
SphereNets). ADAM is used for the stochastic optimization and the learning rate is the same for all
networks. From Fig. 3(a), the SphereResNet converges significantly faster than the original ResNet
baseline in both CIFAR-10 and CIFAR-10+ and the final accuracy are also higher than the baselines.
In Fig. 3(b), we evaluate the SphereNet with and without orthogonality constraints on kernel weights.
With the same network architecture, SphereNet also converges much faster and performs better
than the baselines. The orthogonality constraints also can bring performance gains in some cases.
Generally from Fig. 3, one could also observe that the SphereNet converges fast and very stably in
every case while the CNN baseline fluctuates in a relative wide range.
Optimizing ultra-deep networks. Partially because of the alleviation of the covariate shift problem
and the improvement of conditioning, our SphereNet is able to optimize ultra-deep neural networks
without using residual units or any form of shortcuts. For SphereNets, we use the cosine SphereConv
operator with the cosine W-Softmax loss. We directly optimize a very deep plain network with 69
stacked convolutional layers. From Fig. 3(d), one can see that the convergence of SphereNet is much
easier than the CNN baseline and the SphereNet is able to achieve nearly 90% final accuracy.

Frequency

4.3 Preliminary Study towards Learnable SphereConv
Although the learnable SphereConv is not a main theme of this
paper, we still run some preliminary evaluations on it. For the
0.3
proposed learnable sigmoid SphereConv, we learn the parameter
conv1.1
conv2.1
k independently for each filter. It is also trivial to learn it in a
conv3.1
0.2
layer-shared or network-shared fashsion. With the same 9-layer
architecture used in Section 4.2, the learnable SphereConv (with
0.1
cosine W-Softmax loss) achieves 91.64% on CIFAR-10 (without
0
full data augmentation), while the best sigmoid SphereConv (with
0
0.2
0.4
0.6
0.8
1
The value of k
cosine W-Softmax loss) achieves 91.22%. In Fig. 4, we also plot
the frequency histogram of k in Conv1.1 (64 filters), Conv2.1 (96 Figure 4: Frequency histogram of k.
filters) and Conv3.1 (128 filters) of the final learned SphereNet.
From Fig. 4, we observe that each layer learns different distribution of k. The first convolutional
layer (Conv1.1) tends to uniformly distribute k into a large range of values from 0 to 1, potentially
extracting information from all levels of angular similarity. The fourth convolutional layer (Conv2.1)
tends to learn more concentrated distribution of k than Conv1.1, while the seventh convolutional
layer (Conv3.1) learns highly concentrated distribution of k which is centered around 0.8. Note that,
we initialize all k with a constant 0.5 and learn them with the back-prop.
4.4 Evaluation of SphereNorm
From Section 4.2, we could clearly see the convergence advantage of SphereNets. In general, we can
view the SphereConv as a normalization method (comparable to batch normalization) that can be
applied to all kinds of networks. This section evaluates the challenging scenarios where the minibatch size is small (results under 128 batch size could be found in Section 4.2) and we use the same
8

0.8

0.7

BatchNorm
SphereNorm
Rescaled SphereNorm
SphereNorm w/ Orth.
SphereNorm+BatchNorm

0.4

BatchNorm
SphereNorm
SphereNorm+BatchNorm

0.3
0.2
0

1

2

3

Iteration

4

5

(a) Mini-Batch Size = 4

6
x10 4

0.3
0.2
0.1

0.8

0.7

0.7

0.6

0.5

0.4

0.9

0.8

Testing Accuracy

Testing Accuracy

0.6

0.5

0.1

Testing Accuracy

0.7

0.6

0.9

Testing Accuracy

0.9

0.8

0

1

2

3

Iteration

4

5

(b) Mini-Batch Size = 8

0.6

0.5
0.4
0.3
0.2
0.1

6
x10 4

0.5

BatchNorm
SphereNorm
Rescaled SphereNorm
SphereNorm w/ Orth.
SphereNorm+BatchNorm
0

1

2

3

Iteration

4

5

(c) Mini-Batch Size = 16

BatchNorm
SphereNorm
Rescaled SphereNorm
SphereNorm w/ Orth.
SphereNorm+BatchNorm

0.4
0.3
0.2
0.1

6
x10 4

0

1

2

3

Iteration

4

5

(d) Mini-Batch Size = 32

6
x10 4

Figure 5: Convergence under different mini-batch size on CIFAR-10 dataset (Same setting as Section 4.2).

9-layer CNN as in Section 4.2. To be simple, we use the cosine SphereConv as SphereNorm. The
softmax loss is used in both CNNs and SphereNets. From Fig. 5, we could observe that SphereNorm
achieves the final accuracy similar to BatchNorm, but SphereNorm converges faster and more stably.
SphereNorm plus the orthogonal constraint helps convergence a little bit and rescaled SphereNorm
does not seem to work well. While BatchNorm and SphereNorm are used together, we obtain the
fastest convergence and the highest final accuracy, showing excellent compatibility of SphereNorm.
4.5 Image Classification on CIFAR-10+ and CIFAR-100
We first evaluate the SphereNet in a classic image
classification task. We use the CIFAR-10+ and CIMethod
CIFAR-10+
CIFAR-100
ELU [2]
94.16
72.34
FAR100 datasets and perform random flip (both horiFitResNet (LSUV) [14]
93.45
65.72
zontal and vertical) and random crop as data augmentaResNet-1001 [7]
95.38
77.29
tion (CIFAR-10 with full data augmentation is denoted
Baseline ResNet-32 (softmax)
93.26
72.85
SphereResNet-32 (S-SW)
94.47
76.02
as CIFAR-10+). We use the ResNet-32 as a baseline arSphereResNet-32 (L-LW)
94.33
75.62
SphereResNet-32 (C-CW)
94.64
74.92
chitecture. For the SphereNet of the same architecture,
SphereResNet-32 (S-G)
95.01
76.39
we evaluate sigmoid SphereConv operator (k = 0.3)
with sigmoid W-Softmax (k = 0.3) loss (S-SW), lin- Table 4: Acc. (%) on CIFAR-10+ & CIFAR-100.
ear SphereConv operator with linear W-Softmax loss
(L-LW), cosine SphereConv operator with cosine W-Softmax loss (C-CW) and sigmoid SphereConv
operator (k = 0.3) with GA-Softmax loss (S-G). In Table 4, we could see the SphereNet outperforms
a lot of current state-of-the-art methods and is even comparable to the ResNet-1001 which is far
deeper than ours. This experiment further validates our idea that learning on a hyperspheres constrains
the parameter space to a more semantic and label-related one.

Top5 Error Rate

Top1 Error Rate

4.6 Large-scale Image Classification on Imagenet-2012
We evaluate SphereNets on large-scale Imagenet0.9
0.7
2012 dataset. We only use the minimum data
ResNet-18
ResNet-18
SphereResNet-18-v1
SphereResNet-18-v1
0.8
0.6
augmentation strategy in the experiment (details
SphereResNet-18-v2
SphereResNet-18-v2
0.7
0.5
are in Appendix B). For the ResNet-18 baseline
0.6
0.4
and SphereResNet-18, we use the same filter numbers in each layer. We develop two types of
0.5
0.3
SphereResNet-18, termed as v1 and v2 respec0.4
0.2
tively. In SphereResNet-18-v2, we do not use
0.3
0.1
0
1
2
3
4
5
0
1
2
3
4
5
SphereConv in the 1 × 1 shortcut convolutions
Iteration
x10
Iteration
x10
which are used to match the number of channels.
Figure 6: Validation error (%) on ImageNet.
In SphereResNet-18-v1, we use SphereConv in
the 1 × 1 shortcut convolutions. Fig. 6 shows the single crop validation error over iterations. One could
observe that both SphereResNets converge much faster than the ResNet baseline, while SphereResNet18-v1 converges the fastest but yields a slightly worse yet comparable accuracy. SphereResNet-18-v2
not only converges faster than ResNet-18, but it also shows slightly better accuracy.
5

5

5

Limitations and Future Work

Our work still has some limitations: (1) SphereNets have large performance gain while the network
is wide enough. If the network is not wide enough, SphereNets still converge much faster but yield
slightly worse (still comparable) recognition accuracy. (2) The computation complexity of each
neuron is slightly higher than the CNNs. (3) SphereConvs are still mostly prefixed. Possible future
work includes designing/learning a better SphereConv, efficiently computing the angles to reduce
computation complexity, applications to the tasks that require fast convergence (e.g. reinforcement
learning and recurrent neural networks), better angular regularization to replace orthogonality, etc.
9

Acknowledgements
We thank Zhen Liu (Georgia Tech) for helping with the experiments and providing suggestions. This
project was supported in part by NSF IIS-1218749, NIH BIGDATA 1R01GM108341, NSF CAREER
IIS-1350983, NSF IIS-1639792 EAGER, NSF CNS-1704701, ONR N00014-15-1-2340, Intel ISTC,
NVIDIA and Amazon AWS. Xingguo Li is supported by doctoral dissertation fellowship from
University of Minnesota. Yan-Ming Zhang is supported by the National Natural Science Foundation
of China under Grant 61773376.

References
[1] L-C. Chen, G. Papandreou, I. Kokkinos, K. Murphy, and A. L. Yuille. Semantic image
segmentation with deep convolutional nets and fully connected crfs. In ICLR, 2015.
[2] Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network
learning by exponential linear units (elus). arXiv:1511.07289, 2015.
[3] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for
accurate object detection and semantic segmentation. In CVPR, 2014.
[4] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward
neural networks. In Aistats, 2010.
[5] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers:
Surpassing human-level performance on imagenet classification. In ICCV, 2015.
[6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image
recognition. In CVPR, 2016.
[7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual
networks. arXiv:1603.05027, 2016.
[8] Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training
by reducing internal covariate shift. In ICML, 2015.
[9] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep
convolutional neural networks. In NIPS, 2012.
[10] Xingguo Li, Zhaoran Wang, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, and Tuo
Zhao. Symmetry, saddle points, and global geometry of nonconvex matrix factorization.
arXiv:1612.09296, 2016.
[11] Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang. Large-margin softmax loss for
convolutional neural networks. In ICML, 2016.
[12] Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface:
Deep hypersphere embedding for face recognition. In CVPR, 2017.
[13] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic
segmentation. In CVPR, 2015.
[14] Dmytro Mishkin and Jiri Matas. All you need is a good init. arXiv:1511.06422, 2015.
[15] Yuji Nakatsukasa. Eigenvalue perturbation bounds for hermitian block tridiagonal matrices.
Applied Numerical Mathematics, 62(1):67–78, 2012.
[16] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time
object detection with region proposal networks. In Advances in neural information processing
systems, pages 91–99, 2015.
[17] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng
Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual
recognition challenge. IJCV, pages 1–42, 2014.
10

[18] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale
image recognition. arXiv:1409.1556, 2014.
[19] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov,
Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions.
In CVPR, 2015.
[20] Andreas Veit, Michael J Wilber, and Serge Belongie. Residual networks behave like ensembles
of relatively shallow networks. In NIPS, 2016.
[21] Di Xie, Jiang Xiong, and Shiliang Pu. All you need is beyond a good init: Exploring better
solution for training extremely deep convolutional neural networks with orthonormality and
modulation. arXiv:1703.01827, 2017.

11

A

Network Architectures
Layer

CNN-3

CNN-9

Conv1.x
Pool1
Conv2.x
Pool2
Conv3.x
Pool3
Fully Connected

[3×3, 64]×1

[3×3, 64]×3

[3×3, 96]×1

[3×3, 96]×3

[3×3, 128]×1

[3×3, 128]×3

256

256

CNN-18

CNN-45

[3×3, 64]×6
[3×3, 64]×15
2×2 Max Pooling, Stride 2
[3×3, 96]×6
[3×3, 96]×15
2×2 Max Pooling, Stride 2
[3×3, 128]×6
[3×3, 128]×15
2×2 Max Pooling, Stride 2
256
256

CNN-60

CNN-69

[3×3, 64]×20

[3×3, 64]×23

[3×3, 96]×20

[3×3, 96]×23

[3×3, 128]×20

[3×3, 128]×23

256

256

Table 5: Our plain CNN architectures with different convolutional layers. Conv1.x, Conv2.x and Conv3.x
denote convolution units that may contain multiple convolution layers. E.g., [3×3, 64]×3 denotes 3 cascaded
convolution layers with 64 filters of size 3×3.
Layer

ResNet-32 for Section 4.2

ResNet-32 for Section 4.3

Conv0.x

N/A

N/A

" [3×3, 64]×1
#
3 × 3, 64
×5
3 × 3, 64
"
#
3 × 3, 96
×5
3 × 3, 96
#
"
3 × 3, 128
×5
3 × 3, 128

" [3×3, 96]×1
#
3 × 3, 96
×5
3 × 3, 96
"
#
3 × 3, 192
×5
3 × 3, 192
#
"
3 × 3, 384
×5
3 × 3, 384

Conv1.x

Conv2.x
Conv3.x
Conv4.x

N/A

N/A

ResNet-18 for Section 4.6
[7×7, 256], Stride 2
3×3, Max Pooling, Stride 2
"
#
3 × 3, 256
×2
3 × 3, 256
"
#
3 × 3, 512
×2
3 × 3, 512
#
"
3 × 3, 768
×2
3 × 3, 768
"
#
3 × 3, 1024
×2
3 × 3, 1024

Average Pooling

Table 6: Our ResNet architectures with different convolutional layers. Conv0.x, Conv1.x, Conv2.x, Conv3.x
and Conv4.x denote convolution units that may contain multiple convolutional layers, and residual units are
shown in double-column brackets. Conv1.x, Conv2.x and Conv3.x usually operate on different size feature
maps. These networks are essentially the same as [6], but some may have different number of filters in each
layer. The downsampling is performed by convolutions with a stride of 2. E.g., [3×3, 64]×4 denotes 4 cascaded
convolution layers with 64 filters of size 3×3, and S2 denotes stride 2.

B

Experimental Details for Imagenet-2012

For the input data of the Imagenet-2012 experiment, we only use the minimum data augmentation.
Specifically, we first resize the images to 256 × 256 resolution and then randomly crop patches of
size 224 × 224 from the resized images. Besides that, we also randomly flip the image horizontally.
For SphereResNet-18-v1, we use the cosine SphereConv and the cosine W-Softmax loss. For
SphereResNet-18-v2, we use the cosine SphereConv and the softmax loss. Generally, we find that the
standard softmax loss and all kinds of W-Softmax loss usually have similar empirical performance.
Note that, we could obtain better performance by using the other SphereConvs (sigmoid SphereConv
with k = 0.3 is a good choice), but it requires more GPU memory. Due to the width of our
architecture and the limitation of GPU memory, the mini-batch size is set to 40 for all methods in the
Imagenet-2012 experiment.

C

More Discussions for Sphere-normalized Softmax Loss

The sphere-normalized softmax (S-Softmax) loss is essentially applying the SphereConv to the fully
connected layer in the softmax loss2 . However, simply applying the SphereConv can not make such
loss work, because this loss function is difficult to converge in practice. To address this, we rescale
the logit output of the S-Softmax loss with a scaling factor s. Therefore, the output range is changed
from [−1, 1] to [−s, s]. Typically, setting s from 10 to 70 works pretty well in practice. We could
also use the cross-validation strategy to set the hyperparameter s.

2

The softmax loss is defined as the combination of the last fully connected layer, the softmax function and
the cross-entropy loss.

12

D
D.1

Proofs of Lemmas
Proof of Lemma 1

The gradient is

∇G(U , V ) =

∇U G(U , V )
∇V G(U , V )




=

(U V > − F )V
(V U > − F > )U



The Hessian matrix is


∇2U G(U , V ) ∇2U ,V G(U , V )
2
∇ G(U , V ) =
∇2V ,U G(U , V ) ∇2V G(U , V )


V > V ⊗ In
(U V > − F ) ⊗ Ik + U  V
=
,
(V U > − F > ) ⊗ Ik + V  U
U > U ⊗ Im

(12)

where In is an n × n identity matrix for any integer n, given matrices A ∈ Rn×r and B ∈ Rm×k
with A:,i denoting the i-th column of A, A  B ∈ Rnk×mr is defined as


>
>
>
A:,1 B:,1
A:,2 B:,1
· · · A:,r B:,1
>
>
> 
 A:,1 B:,2
A:,2 B:,2
· · · A:,r B:,2


AB =
.
..
..
..
..


.
.
.
.
>
A:,1 B:,k

>
A:,2 B:,k

···

>
A:,r B:,k

e = cU and
At a global optimum, we have U V > = F . Then it is easy to see that for any real c, if U
Ve = V /c, then we have
 1 >

V ⊗ In
U V
2V
2
e
e
c
∇ G(U , V ) =
V U
c2 U > U ⊗ Im
We have that at a global optimal point, ∇2 G(U , V ) is a positive semidefinite matrix with the smallest
eigenvalue equal to 0. Specifically, due to the existence of the invariance, i.e., U V > = U R(V R)>
for any orthogonal matrix R ∈ Rr×r , there are r(r − 1)/2 number of eigenvectors of ∇2 G(U , V )
at U V > = F corresponding to 0 eigenvalue [10]. Then for any c > 1, we have
e , Ve )) = 1 Tr(V > V ⊗ In ) + c2 Tr(U > U ⊗ Im )
Tr(∇2 G(U
c2
 c2
c2
≥
Tr(V > V ⊗ In ) + Tr(U > U ⊗ Im ) = Tr(∇2 G(U , V )).
2
2
2
e , Ve ) is on the order of Θ(c2 ) times the largest
This indicates that the largest eigenvalue of ∇ G(U
2
eigenvalue of ∇ G(U , V ) following the perturbation bound analysis [15] and U and V are balanced.
e , Ve ) is no greater than the smallest
Using a similar idea, the smallest nonzero eigenvalue of ∇2 G(U
nonzero eigenvalue of ∇2 G(U , V ), which results in our claim on the restricted condition number.
D.2

Proof of Lemma 2

The gradient of GS (U , V ) is


∇U GS (U , V )
∇GS (U , V ) =
with
∇V GS (U , V )
3
∇U GS (U , V ) = DU (DU U V > DV − F )DV V − DU
(DU U V > DV − F ) ~k (U V > DV )
>

>

∇V GS (U , V ) = DV (DV V U DU − F )DU U −

DV3

>

>

>



U,



V,

(DV V U DU − F ) ~k (V U DU )

Note that after each iteration of SGD, we perform the entry-wise normalization for both U and V ,
which means DU = In and DV = Im . Then the gradient of GS (U , V ) is

 


(U V > − F )V − (U V > − F ) ~k (U V > )  U
∇U GS (U , V )
∇GS (U , V ) =
=
,
∇V GS (U , V )
(V U > − F > )U − (V U > − F > ) ~k (V U > )
V
13

where given matrices A, B ∈ Rn×m with A:,i denoting the i-th column of A, A B ∈ Rn×m is
the Hadamard (pointwise) product, and the operation A ~k B ∈ Rn×k is defined as


>
A1,: B1,:
> 
 A2,: B2,:


A ~k B = 
 11×k ,
..


.
>
An,: Bn,:
where 11×k is a 1 × k vector with all entries equal to 1.
Consequently, the Hessian matrix is


∇2U GS (U , V ) ∇2U ,V GS (U , V )
2
∇ GS (U , V ) =
with
∇2V ,U GS (U , V ) ∇2V GS (U , V )

∇2U GS (U , V ) = V > V ⊗ In − diag vec (U V > − F ) ~k (U V > )


diag U:,1

(2U V > − F )V:,1
..
.



diag U:,k

(2U V > − F )V:,1



−


···
..
.
···

diag U:,1

(2U V > − F )V:,k
..
.

 

diag U:,k

(2U V > − F )V:,k






∇2U ,V GS (U , V ) = Ik ⊗ (U V > − F ) + U  V


−

(2U V > − F )


(2U V > − F )

((U:,1
..
.
((U:,k

· · · (2U V > − F )
..
.
U:1 )11×m ) · · · (2U V > − F )
U:1 )11×m )

((U:,1
..
.

U:k )11×m )

((U:,k

U:k )11×m )





>
∇2V ,U GS (U , V ) = ∇2U ,V GS (U , V )

∇2V GS (U , V ) = U > U ⊗ In − diag vec (V U > − F > ) ~k (V U > )


diag V:,1

−

diag V:,k

(2V U > − F > )U:,1
..
.



· · · diag V:,1
..
.

(2V U > − F > )U:,1
· · · diag V:,k

(2V U > − F > )U:,k
..
.

 

(2V U > − F > )U:,k






e , Ve )) = λi (∇2 GS (U , V )) for all i ∈ [(n+m)k] = {1, 2, . . . , (n+m)k}
Then we have λi (∇2 GS (U
Ui,j
Vi,j
by noticing that we normalize the data as kUi,:
k2 for all i ∈ [n] and kVi,: k2 for all i ∈ [m]. This
finishes the proof.

14

