Fisher-Rao Metric, Geometry,
and Complexity of Neural
Networks
Tengyuan Liang∗

arXiv:1711.01530v1 [cs.LG] 5 Nov 2017

University of Chicago

Tomaso Poggio†
Massachusetts Institute of Technology

Alexander Rakhlin‡
University of Pennsylvania

James Stokes§
University of Pennsylvania

Abstract.
We study the relationship between geometry and capacity measures for
deep neural networks from an invariance viewpoint. We introduce a new
notion of capacity — the Fisher-Rao norm — that possesses desirable invariance properties and is motivated by Information Geometry. We discover
an analytical characterization of the new capacity measure, through which
we establish norm-comparison inequalities and further show that the new
measure serves as an umbrella for several existing norm-based complexity
measures. We discuss upper bounds on the generalization error induced
by the proposed measure. Extensive numerical experiments on CIFAR-10
support our theoretical findings. Our theoretical analysis rests on a key
structural lemma about partial derivatives of multi-layer rectifier networks.
Key words and phrases: deep learning, statistical learning theory, information geometry, Fisher-Rao metric, invariance, ReLU activation, natural
gradient, capacity control, generalization error.
1. INTRODUCTION
Beyond their remarkable representation and memorization ability, deep neural
networks empirically perform well in out-of-sample prediction. This intriguing
out-of-sample generalization property poses two fundamental theoretical questions:
• What are the complexity notions that control the generalization aspects of
neural networks?
∗

(e-mail: tengyuan.liang@chicagobooth.edu)
(e-mail: tp@ai.mit.edu)
‡
(e-mail: rakhlin@wharton.upenn.edu)
§
(e-mail: stokesj@sas.upenn.edu)
†

1
file: paper_arxiv.tex date: November 7, 2017

2

• Why does stochastic gradient descent, or other variants, find parameters
with small complexity?
In this paper we approach the generalization question for deep neural networks
from a geometric invariance vantage point. The motivation behind invariance is
twofold: (1) The specific parametrization of the neural network is arbitrary and
should not impact its generalization power. As pointed out in [Neyshabur et al.,
2015a], for example, there are many continuous operations on the parameters of
ReLU nets that will result in exactly the same prediction and thus generalization
can only depend on the equivalence class obtained by identifying parameters
under these transformations. (2) Although flatness of the loss function has been
linked to generalization [Hochreiter and Schmidhuber, 1997], existing definitions
of flatness are neither invariant to nodewise re-scalings of ReLU nets nor general
coordinate transformations [Dinh et al., 2017] of the parameter space, which calls
into question their utility for describing generalization.
It is thus natural to argue for a purely geometric characterization of generalization that is invariant under the aforementioned transformations and additionally
resolves the conflict between flat minima and the requirement of invariance. Information geometry is concerned with the study of geometric invariances arising in
the space of probability distributions, so we will leverage it to motivate a particular geometric notion of complexity — the Fisher-Rao norm. From an algorithmic
point of view the steepest descent induced by this geometry is precisely the natural gradient [Amari, 1998]. From the generalization viewpoint, the Fisher-Rao
norm naturally incorporates distributional aspects of the data and harmoniously
unites elements of flatness and norm which have been argued to be crucial for
explaining generalization [Neyshabur et al., 2017].
Statistical learning theory equips us with many tools to analyze out-of-sample
performance. The Vapnik-Chervonenkis dimension is one possible complexity notion, yet it may be too large to explain generalization in over-parametrized models, since it scales with the size (dimension) of the network. In contrast, under
additional distributional assumptions of a margin, Perceptron (a one-layer network) enjoys a dimension-free error guarantee, with an `2 norm playing the role
of “capacity”. These observations (going back to the 60’s) have led the theory
of large-margin classifiers, applied to kernel methods, boosting, and neural networks [Anthony and Bartlett, 1999]. In particular, the analysis of Koltchinskii and
Panchenko [2002] combines the empirical margin distribution (quantifying how
well the data can be separated) and the Rademacher complexity of a restricted
subset of functions. This in turn raises the capacity control question: what is
a good notion of the restrictive subset of parameter space for neural networks?
Norm-based capacity control provides a possible answer and is being actively
studied for deep networks [Krogh and Hertz, 1992, Neyshabur et al., 2015b,a,
Bartlett et al., 2017, Neyshabur et al., 2017], yet the invariances are not always
reflected in these capacity notions. In general, it is very difficult to answer the
question of which capacity measure is superior. Nevertheless, we will show that
our proposed Fisher-Rao norm serves as an umbrella for the previously considered
norm-based capacity measures, and it appears to shed light on possible answers
to the above question.
Much of the difficulty in analyzing neural networks stems from their unwieldy
recursive definition interleaved with nonlinear maps. In analyzing the Fisher-Rao
file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

3

norm, we proved an identity for the partial derivatives of the neural network that
appears to open the door to some of the geometric analysis. In particular, we
prove that any stationary point of the empirical objective with hinge loss that
perfectly separates the data must also have a large margin. Such an automatic
large-margin property of stationary points may link the algorithmic facet of the
problem with the generalization property. The same identity gives us a handle
on the Fisher-Rao norm and allows us to prove a number of facts about it.
Since we expect that the identity may be useful in deep network analysis, we
start by stating this result and its implications in the next section. In Section
3 we introduce the Fisher-Rao norm and establish through norm-comparison
inequalities that it serves as an umbrella for existing norm-based measures of
capacity. Using these norm-comparison inequalities we bound the generalization
error of various geometrically distinct subsets of the Fisher-Rao ball and provide
a rigorous proof of generalization for deep linear networks. Extensive numerical
experiments are performed in Section 5 demonstrating the superior properties of
the Fisher-Rao norm.
2. GEOMETRY OF DEEP RECTIFIED NETWORKS
Definition 1. The function class HL realized by the feedforward neural network architecture of depth L with coordinate-wise activation functions σl : R Ñ R
is defined as set of functions fθ : X Ñ Y (X Ď Rp and Y Ď RK )1 with
(2.1)

fθ pxq “ σL`1 pσL p. . . σ2 pσ1 pxT W 0 qW 1 qW 2 q . . .qW L q ,

where the parameter vector θ P ΘL Ď Rd (d “ pk1 `

řL´1
i“1

ki ki`1 ` kL K) and

ΘL “ tW 0 P Rpˆk1 , W 1 P Rk1 ˆk2 , . . . , W L´1 P RkL´1 ˆkL , W L P RkL ˆK u .
For simplicity of calculations, we have set all bias terms to zero2 . We also
assume throughout the paper that
σpzq “ σ 1 pzqz.

(2.2)

for all the activation functions, which includes ReLU σpzq “ maxt0, zu, “leaky”
ReLU σpzq “ maxtαz, zu, and linear activations as special cases.
To make the exposition of the structural results concise, we define the following
intermediate functions in the definition (2.1). The output value of the t-th layer
hidden node is denoted as Ot pxq P Rkt , and the corresponding input value as
N t pxq P Rkt , with Ot pxq “ σt pN t pxqq. By definition, O0 pxq “ x P Rp , and the
final output OL`1 pxq “ fθ pxq P RK . For any Nit , Oit , the subscript i denotes the
i-th coordinate of the vector.
Given a loss function ` : Y ˆ Y Ñ R, the statistical learning problem can be
phrased as optimizing the unobserved population loss:
(2.3)

Lpθq :“

E

pX,Y q„P

`pfθ pXq, Y q ,

1

It is possible to generalize the above architecture to include linear pre-processing operations
such as zero-padding and average pooling.
2
In practice, we found that setting the bias to zero does not significantly impact results on
image classification tasks such as MNIST and CIFAR-10.
file: paper_arxiv.tex date: November 7, 2017

4

based on i.i.d. samples tpXi , Yi quN
i“1 from the unknown joint distribution P. The
unregularized empirical objective function is denoted by
(2.4)

N
ÿ
p θ pXq, Y q “ 1
p
`pfθ pXi q, Yi q .
Lpθq
:“ E`pf
N i“1

We first establish the following structural result for neural networks. It will
be clear in the later sections that the lemma is motivated by the study of the
Fisher-Rao norm, formally defined in Eqn. (3.1) below, and information geometry. For the moment, however, let us provide a different viewpoint. For linear
functions fθ pxq “ xθ, xy, we clearly have that xBf {Bθ, θy “ fθ pxq. Remarkably, a
direct analogue of this simple statement holds for neural networks, even if overparametrized.
Lemma 2.1 (Structure in Gradient). Given a single data input x P Rp , consider the feedforward neural network in Definition 1 with activations satisfying
(2.2). Then for any 0 ď t ď s ď L, one has the identity
ÿ

(2.5)

iPrkt s,jPrkt`1 s

BOs`1 t
Wij “ Os`1 pxq .
BWijt

In addition, it holds that
(2.6)

L
ÿ

ÿ

t“0 iPrkt s,jPrkt`1 s

BOL`1 t
Wij “ pL ` 1qOL`1 pxq .
BWijt

Lemma 2.1 reveals the structural constraints in the gradients of rectified networks. In particular, even though the gradients lie in an over-parametrized highdimensional space, many equality constraints are induced by the network architecture. Before we unveil the surprising connection between Lemma 2.1 and the
proposed Fisher-Rao norm, let us take a look at a few immediate corollaries of
this result. The first corollary establishes a large-margin property of stationary
points that separate the data.
Corollary 2.1 (Large Margin Stationary Points). Consider the binary classification problem with Y “ t´1, `1u, and a neural network where the output layer
has only one unit. Choose the hinge loss `pf, yq “ maxt0, 1 ´ yf u. If a certain
parameter θ satisfies two properties
p
p
1. θ is a stationary point for Lpθq
in the sense ∇θ Lpθq
“ 0;
2. θ separates the data in the sense that Yi fθ pXi q ą 0 for all i P rN s,
then it must be that θ is a large margin solution: for all i P rN s,
Yi fθ pXi q ě 1.
The same result holds for the population criteria Lpθq, in which case p2q is stated
as PpY fθ pXq ą 0q “ 1, and the conclusion is PpY fθ pXq ě 1q “ 1.

file: paper_arxiv.tex date: November 7, 2017

5

CAPACITY MEASURE AND GEOMETRY

q
q
Proof. Observe that B`pf,Y
“ ´y if yf ă 1, and B`pf,Y
“ 0 if yf ě 1. Using
Bf
Bf
Eqn. (2.6) when the output layer has only one unit, we find

„
B`pfθ pXq, Y q
p
p
x∇θ Lpθq, θy “ pL ` 1qE
fθ pXq ,
Bfθ pXq
“
‰
p ´Y fθ pXq1Y f pXqă1 .
“ pL ` 1qE
θ

p
For a stationary point θ, we have ∇θ Lpθq
“ 0, which implies the LHS of the
above equation is 0. Now recall that the second condition that θ separates the
data implies implies ´Y fθ pXq ă 0 for any point in the data set. In this case, the
RHS equals zero if and only if Y fθ pXq ě 1.
Granted, the above corollary can be proved from first principles without the
use of Lemma 2.1, but the proof reveals a quantitative statement about stationary
points along arbitrary directions θ.
In the second corollary, we consider linear networks.
Corollary 2.2 (Stationary Points for Deep Linear Networks). Consider linear neural networks with σpxq “ x and square loss function. Then all stationary
points θ “ tW 0 , W 1 , . . . , W L u that satisfy
„

1
2
p
p
∇θ Lpθq “ ∇θ E pfθ pXq ´ Y q “ 0 ,
2
must also satisfy
xwpθq, XT Xwpθq ´ XT Yy “ 0 ,
where wpθq “

śL

t“0 W

t

P Rp , X P RN ˆp and Y P RN are the data matrices.

Proof. The proof follows from applying Lemma 2.1
«
ff
L
L
ź
ź
p pY ´ X T
p
0 “ θT ∇θ Lpθq
“ pL ` 1qE
W t qX T
Wt ,
t“0

t“0

which means xwpθq, XT Xwpθq ´ XT Yy “ 0.
Remark 2.1. This simple Lemma is not quite asserting that all stationary
points are global optima, since global optima satisfy XT Xwpθq´XT Y “ 0, while
we only proved that the stationary points satisfy xwpθq, XT Xwpθq ´ XT Yy “ 0.
3. FISHER-RAO NORM AND GEOMETRY
In this section, we propose a new notion of complexity of neural networks that
can be motivated by geometrical invariance considerations, specifically the FisherRao metric of information geometry. We postpone this motivation to Section 3.3
and instead start with the definition and some properties. Detailed comparison
with the known norm-based capacity measures and generalization results are
delayed to Section 4.

file: paper_arxiv.tex date: November 7, 2017

6

3.1 An analytical formula
Definition 2. The Fisher-Rao norm for a parameter θ is defined as the
following quadratic form
(3.1) }θ}2fr :“ xθ, Ipθqθy ,

where Ipθq “ Er∇θ lpfθ pXq, Y q b ∇θ lpfθ pXq, Y qs .

The underlying distribution for the expectation in the above definition has
been left ambiguous because it will be useful to specialize to different distributions
depending on the context. Even though we call the above quantity the “FisherRao norm,” it should be noted that it does not satisfy the triangle inequality.
The following Theorem unveils a surprising identity for the Fisher-Rao norm.
Theorem 3.1 (Fisher-Rao norm). Assume the loss function `p¨, ¨q is smooth
in the first argument. The following identity holds for a feedforward neural network (Definition 1) with L hidden layers and activations satisfying (2.2):
«B
F2 ff
B`pfθ pXq, Y q
2
2
}θ}fr “ pL ` 1q E
(3.2)
, fθ pXq
.
Bfθ pXq
The proof of the Theorem relies mainly on the geometric Lemma 2.1 that
describes the gradient structure of multi-layer rectified networks.
Remark 3.1. In the case when the output layer has only one node, Theorem 3.1 reduces to the simple formula
«ˆ
ff
˙
B`pfθ pXq, Y q 2
2
2
2
}θ}fr “ pL ` 1q E
(3.3)
fθ pXq
.
Bfθ pXq
Proof of Theorem 3.1. Using the definition of the Fisher-Rao norm,
“
‰
}θ}2fr “ E xθ, ∇θ lpfθ pXq, Y qy2 ,
«B
F2 ff
B`pfθ pXq, Y q
“E
∇θ fθ pXq
,θ
,
Bfθ pXq
«B
F2 ff
B`pfθ pXq, Y q
“E
, ∇θ fθ pXqT θ
.
Bfθ pXq
By Lemma 2.1,
∇θ fθ pXqT θ “ ∇θ OL`1 pxqT θ ,
L
ÿ

ÿ

“
t“0 iPrkt s,jPrkt`1 s

BOL`1 t
Wij ,
BWijt

“ pL ` 1qOL`1 “ pL ` 1qfθ pXq .
Combining the above equalities, we obtain
«B
F2 ff
B`pf
pXq,
Y
q
θ
}θ}2fr “ pL ` 1q2 E
, fθ pXq
.
Bfθ pXq

file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

7

Before illustrating how the explicit formula in Theorem 3.1 can be viewed as a
unified “umbrella” for many of the known norm-based capacity measures, let us
point out one simple invariance property of the Fisher-Rao norm, which follows
as a direct consequence of Thm. 3.1. This property is not satisfied for `2 norm,
spectral norm, path norm, or group norm.
Corollary 3.1 (Invariance). If there are two parameters θ1 , θ2 P ΘL such
that they are equivalent, in the sense that fθ1 “ fθ2 , then their Fisher-Rao norms
are equal, i.e.,
}θ1 }fr “ }θ2 }fr .
3.2 Norms and geometry
In this section we will employ Theorem 3.1 to reveal the relationship among
different norms and their corresponding geometries. Norm-based capacity control
is an active field of research for understanding why deep learning generalizes
well, including `2 norm (weight decay) in [Krogh and Hertz, 1992, Krizhevsky
et al., 2012], path norm in [Neyshabur et al., 2015a], group-norm in [Neyshabur
et al., 2015b], and spectral norm in [Bartlett et al., 2017]. All these norms are
closely related to the Fisher-Rao norm, despite the fact that they capture distinct
inductive biases and different geometries.
For simplicity, we will showcase the derivation with the absolute loss function
`pf, yq “ |f ´ y| and when the output layer has only one node (kL`1 “ 1). The
argument can be readily adopted to the general setting. We will show that the
Fisher-Rao norm serves as a lower bound for all the norms considered in the
literature, with some pre-factor whose meaning will be clear in Section 4.1. In
addition, the Fisher-Rao norm enjoys an interesting umbrella property: by considering a more constrained geometry (motivated from algebraic norm comparison
inequalities) the Fisher-Rao norm motivates new norm-based capacity control
methods.
The main theorem we will prove is informally stated as follows.
Theorem 3.2 (Norm comparison, informal). Denoting ~ ¨ ~ as any one of:
(1) spectral norm, (2) matrix induced norm, (3) group norm, or (4) path norm,
we have
1
}θ}fr ď ~θ~ ,
L`1
for any θ P ΘL “ tW 0 , W 1 , . . . , W L u. The specific norms (1)-(4) are formally
introduced in Definitions 3-6.
The detailed proof of the above theorem will be the main focus of Section 4.1.
Here we will give a sketch on how the results are proved.
Lemma 3.1 (Matrix form).
(3.4)

fθ pxq “ xT W 0 D1 pxqW 1 D2 pxq ¨ ¨ ¨ DL W L DL`1 pxq ,

where Dt pxq “ diagrσ 1 pN t pxqqs P Rkt ˆkt , for 0 ă t ď L ` 1. In addition, Dt pxq is
a diagonal matrix with diagonal elements being either 0 or 1.
file: paper_arxiv.tex date: November 7, 2017

8

Proof of Lemma 3.1. Since O0 pxqW 0 “ xT W 0 “ N 1 pxq P R1ˆk1 , we have
“ N 1 pxqdiagpσ 1 pN 1 pxqqq “ O1 pxq. Proof is completed via induction.

N 1 pxqD1

`
˘2
For the absolute loss, one has B`pfθ pXq, Y q{Bfθ pXq “ 1 and therefore Theorem 3.1 simplifies to,
“
‰
(3.5)
}θ}2fr “ pL ` 1q2 E vpθ, XqT XX T vpθ, Xq ,
X„P

where vpθ, xq :“ W 0 D1 pxqW 1 D2 pxq ¨ ¨ ¨ DL pxqW L DL`1 pxq P Rp . The norm comparison results are thus established through a careful decomposition of the datadependent vector vpθ, Xq, in distinct ways according to the comparing norm/geometry.
3.3 Motivation and invariance
In this section, we will provide the original intuition and motivation for our
proposed Fisher-Rao norm from the viewpoint of geometric invariance.
Information geometry and the Fisher-Rao metric
Information geometry provides a window into geometric invariances when we
adopt a generative framework where the data generating process belongs to the
parametric family P P tPθ | θ P ΘL u indexed by the parameters of the neural
network architecture. The Fisher-Rao metric on tPθ u is defined in terms of a
local inner product for each value of θ P ΘL as follows. For each α, β P Rd define
the corresponding tangent vectors ᾱ :“ dpθ`tα {dt|t“0 , β̄ :“ dpθ`tβ {dt|t“0 . Then
for all θ P ΘL and α, β P Rd we define the local inner product
ż
ᾱ β̄
(3.6)
xᾱ, β̄ypθ :“
pθ ,
M pθ pθ
where M “ X ˆ Y. The above inner product extends to a Riemannian metric
on the space of positive densities ProbpM q called the Fisher-Rao metric3 . The
relationship between the Fisher-Rao metric and the Fisher information matrix
Ipθq in statistics literature follows from the identity,
(3.7)

xᾱ, β̄ypθ “ xα, Ipθqβy .

Notice that the Fisher information matrix induces a semi -inner product pα, βq ÞÑ
xα, Ipθqβy unlike the Fisher-Rao metric which is non-degenerate4 . If we make
the additional modeling assumption that pθ px, yq “ ppxqpθ py |xq then the Fisher
information becomes,
(3.8)

Ipθq “ EpX,Y q„Pθ r∇θ log pθ pY | Xq b ∇θ log pθ pY | Xqs .

If we now identify our loss function as `pfθ pxq, yq “ ´ log pθ py | xq then the FisherRao metric coincides with the Fisher-Rao norm when α “ β “ θ. In fact, our
Fisher-norm encompasses the Fisher-Rao metric and generalizes it to the case
when the model is misspecified P R tPθ u.
Flatness
3

Bauer et al. [2016] showed that it is essentially the the unique metric that is invariant under
the diffeomorphism group of M .
4
The null space of Ipθq is mapped to the origin under α ÞÑ dpθ`tα {dt|t“0 .
file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

9

Having identified the geometric origin of Fisher-Rao norm, let us study the
implications for generalization of flat minima. Dinh et al. [2017] argued by way
of counter-example that the existing measures of flatness are inadequate for explaining the generalization capability of multi-layer neural networks. Specifically,
by utilizing the invariance property of multi-layer rectified networks under nonnegative nodewise rescalings, they proved that the Hessian eigenvalues of the loss
function can be made arbitrarily large, thereby weakening the connection between
flat minima and generalization. They also identified a more general problem which
afflicts Hessian-based measures of generalization for any network architecture and
activation function: the Hessian is sensitive to network parametrization whereas
generalization should be invariant under general coordinate transformations. Our
proposal can be motivated from the following fact5 which relates flatness to geometry (under appropriate regularity conditions)
(3.9)
EpX,Y q„Pθ xθ, Hess r`pfθ pXq, Y qs θy “ EpX,Y q„Pθ xθ, ∇θ `pfθ pXq, Y qy2 “ }θ}2fr .
θ

In other words, the Fisher-Rao norm evades the node-wise rescaling issue because it is exactly invariant under linear re-parametrizations. The Fisher-Rao
norm moreover possesses an “infinitesimal invariance” property under non-linear
coordinate transformations, which can be seen by passing to the infinitesimal
form where non-linear coordinate invariance is realized exactly by the following
infinitesimal line element,
ÿ
(3.10)
ds2 “
rIpθqsij dθi dθj .
i,jPrds

Comparing }θ}fr with the above line element reveals the geometric interpretation
of the Fisher-Rao norm as the approximate geodesic distance from the origin. It
is important to realize that our definition of flatness
“
‰ (3.9) differs from [Dinh et al.,
p
2017] who employed the Hessian loss Hessθ Lpθq
. Unlike the Fisher-Rao norm,
the norm induced by the Hessian loss does not enjoy the infinitesimal invariance
property (it only holds at critical points).
Natural gradient
There exists a close relationship between the Fisher-Rao norm and the natural
gradient. In particular, the natural gradient descent is simply the steepest descent
direction induced by the Fisher-Rao geometry of tPθ u. Indeed, the natural gradient can be expressed as a semi-norm-penalized iterative optimization scheme as
follows,
(3.11)
„

1
2
p
p tq .
θt`1 “ arg min xθ ´ θt , ∇Lpθt qy `
}θ ´ θt }Ipθt q “ θt ´ ηt Ipθq` ∇Lpθ
2η
d
t
θPR
We remark that the positive semi-definite matrix Ipθt q changes with different t.
We emphasize an “invariance” property of natural gradient under re-parametrization
and an “approximate invariance” property under over-parametrization, which is
not satisfied for the classic gradient descent. The formal statement and its proof
are deferred to Lemma 6.1 in Section 6.2. The invariance property is desirable:
5

Set `pfθ pxq, yq “ ´ log pθ py|xq and recall the fact that Fisher information can be viewed as
variance as well as the curvature.
file: paper_arxiv.tex date: November 7, 2017

10

in multi-layer ReLU networks, there are many equivalent re-parametrizations of
the problem, such as nodewise rescalings, which may slow down the optimization process. The advantage of natural gradient is also illustrated empirically in
Section 5.5.
4. CAPACITY CONTROL AND GENERALIZATION
In this section, we discuss in full detail the questions of geometry, capacity measures, and generalization. First, let us define empirical Rademacher complexity
for the parameter space Θ, conditioned on data tXi , i P rN su, as
(4.1)

RN pΘq “ E sup
 θPΘ

N
1 ÿ
i fθ pXi q ,
N i“1

where i , i P rN s are i.i.d. Rademacher random variables.
4.1 Norm Comparison
Let us collect some definitions before stating each norm
comparison result.
ř
For a vector v, the vector `p norm is denoted }v}p :“ p i |vi |p q1{p , p ą 0. For a
matrix M , }M }σ :“ maxv‰0 }v T M }{}v} denotes the spectral norm; }M }pÑq “
maxv‰0 }v T M }q {}v}p denotes the matrix induced norm, for p, q ě 1; }M }p,q “
˘ ‰
“ř `ř
p q{p 1{q denotes the matrix group norm, for p, q ě 1.
i |Mij |
j
4.1.1 Spectral norm.
Definition 3 (Spectral norm). Define the following “spectral norm” ball:
« ˜
¸ff1{2
L`1
L
ź
ź
(4.2)
}θ}σ :“ E }X}2
}Dt pXq}2σ
}W t }σ .
t“1

t“0

We have the following norm comparison Lemma.
Lemma 4.1 (Spectral norm).
1
}θ}fr ď }θ}σ .
L`1
Remark 4.1. Spectral norm as a capacity control has been considered in
[Bartlett et al., 2017]. Lemma 4.1 shows that spectral norm serves as a more
stringent constraint than Fisher-Rao norm. Let us provide an explanation of
˘‰
“ `
ś
t
2 1{2 here. Define the set of parameters
the pre-factor E }X}2 L`1
t“1 }D pXq}σ
induced by the Fisher-Rao norm geometry
“
‰
1
Bfr p1q :“ tθ : E vpθ, XqT XX T vpθ, Xq ď 1u “ tθ :
}θ}fr ď 1u .
L`1
p then, because
From Lemma 4.1, if the expectation is over the empirical measure E,
}Dt pXq}σ ď 1, we obtain
« ˜
¸ff1{2
L
L`1
L
ź
ź
“
‰ ź
1
2
t
2
t
2 1{2
p
p
}W }σ ď E}X}
}W t }σ ,
}θ}fr ď E }X}
}D pXq}σ
L`1
t“0
t“1
t“0
#
+
L
ź
1
which implies
θ:
}W t }σ ď “
Ă Bfr p1q .
‰
2 1{2
p
E}X}
t“0
file: paper_arxiv.tex date: November 7, 2017

11

CAPACITY MEASURE AND GEOMETRY

From Theorem 1.1 in [Bartlett et al., 2017], we know that a subset of the
Bfr p1q characterized by the spectral norm enjoys the following upper bound on
Rademacher complexity under mild conditions: for any r ą 0
˜#
+¸
“
‰
L
2 1{2 ¨ Polylog
p
ź
E}X}
t
(4.3)
RN
θ:
}W }σ ď r
Àr¨
.
N
t“0
Plugging in r “ “
(4.4)
˜#
RN

θ:

L
ź

1
‰1{2 ,
2
p
E}X}

we have,

+¸

1

t

}W }σ ď “
‰
2 1{2
p
E}X}
t“0

À“

1
2
p
E}X}

“
‰1{2 ¨

2
p
E}X}

‰1{2

¨ Polylog

N

Ñ0 .

“
‰
2 1{2 in Theorem 1.1 in [Bartlett et al.,
p
Interestingly, the additional factor E}X}
2017] exactly cancels with our pre-factor in the norm comparison. The above
calculations show that a subset of Bfr p1q, induced by the spectral norm geometry,
has good generalization error.

4.1.2 Group norm.
Definition 4 (Group norm).
p ě 1, q ą 0
« ˜
(4.5)

}θ}p,q :“ E

}X}2p˚

Define the following “group norm” ball, for
¸ff1{2

L`1
ź

}D

t

pXq}2qÑp˚

t“1

where

1
p

`

1
p˚

L
ź

}W t }p,q ,

t“0

“ 1. Here } ¨ }qÑp˚ denote the matrix induced norm.

Lemma 4.2 (Group norm).

It holds that
1
}θ}fr ď }θ}p,q .
L`1

(4.6)

Remark 4.2. Group norm as a capacity measure has been considered in
[Neyshabur et al., 2015b]. Lemma 4.2 shows that group norm serves as a more
stringent constraint than Fisher-Rao norm. Again, let us provide an explanation
“ `
˘‰1{2
śL`1 t
here.
of the pre-factor E }X}2p˚ t“1
}D pXq}2qÑp˚
Note that for all X
L`1
ź

}Dt pXq}qÑp˚ ď

t“1

L`1
ź

r

1
1
˚ ´ q s`

kt p

,

t“1

because
}Dt pXq}qÑp˚ “ max
v‰0

r 1˚ ´ 1 s`
}v T Dt pXq}p˚
}v}p˚
ď max
ď kt p q
.
v‰0 }v}q
}v}q

file: paper_arxiv.tex date: November 7, 2017

12

p we know
From Lemma 4.2, if the expectation is over the empirical measure E,
that in the case when kt “ k for all 0 ă t ď L,
« ˜
¸ff1{2
L`1
L
ź
ź
1
t
2
p }X}2˚
}θ}fr ď E
}D
pXq}
}W t }p,q ,
˚
p
qÑp
L`1
t“1
t“0
ˆ
˙1{2 ´
L
¯
L ź
r 1 ´1s
}W t }p,q ,
ď max }Xi }2p˚
k p˚ q ` ¨
i

t“0

$
’
&
which implies

θ:
’
%

L
ź

}W t }p,q ď ´
k

t“0

r p1˚ ´ 1q s`

,
/
.

1
¯L

Ă Bfr p1q .
/
maxi }Xi }p˚ -

By Theorem 1 in [Neyshabur et al., 2015b], we know that a subset of Bfr p1q
(different from the subset induced by spectral geometry) characterized by the
group norm, satisfies the following upper bound on the Rademacher complexity,
for any r ą 0
˜#
(4.7) RN

L
ź

θ:

+¸
}W t }p,q ď r

t“0

1
,
ˆ 1 1 ˙L
r ˚ ´ q s`
p
k
maxi }Xi }p˚

Plugging in r “

(4.8)

´
¯L
r 1 ´1s
2k p˚ q ` maxi }Xi }p˚ ¨ Polylog
?
Àr¨
.
N
we have

,˛
¨$
/
’
L
.
& ź
1
‹
˚
t
RN ˝ θ :
}W }p,q ď ´ 1 1 ¯L
‚
/
’
r p˚ ´ q s`
% t“0
maxi }Xi }p˚
k
´ 1 1 ¯L
r
´ s
L
2
k p˚ q ` maxi }Xi }p˚ ¨ Polylog
1
?
À ´ 1 1 ¯L
¨
Ñ0 .
r
´ s
N
k p˚ q ` max }X } ˚
i

i p

Once again, we point out that the intriguing combinatorial factor in Theorem
1 of Neyshabur et al. [2015b] exactly cancels with our pre-factor in the norm
comparison. The above calculations show that another subset of Bfr p1q, induced
by the group norm geometry, has good generalization error (without additional
factors).

4.1.3 Path norm.
Definition 5 (Path norm).

Define the following “path norm” ball, for q ě 1

(4.9)
» ˜
}πpθq}q :“ –E

L`1
ź

ÿ
|Xi0
i0 ,i1 ,...,iL

t“1

¸2{q˚ fi1{2 ˜
Ditt pXq|q

˚

ÿ
fl

L
ź

¨

¸1{q
|Witt it`1 |q

,

i0 ,i1 ,...,iL t“0

where 1q ` q1˚ “ 1, indices set i0 P rps, i1 P rk1 s, . . . iL P rkL s, iL`1 “ 1. Here πpθq
is a notation for all the paths (from input to output) of the weights θ.
file: paper_arxiv.tex date: November 7, 2017

13

CAPACITY MEASURE AND GEOMETRY

Lemma 4.3 (Path-q norm).

The following inequality holds for any q ě 1,

1
}θ}fr ď }πpθq}q .
L`1

(4.10)

Remark 4.3. Path norm has been investigated in [Neyshabur et al., 2015a],
where the definition is
˜
¸1{q
L
ÿ ź
t
q
.
|Wit it`1 |
i0 ,i1 ,...,iL t“0

Again, let us provide an intuitive explanation for our pre-factor
» ˜
¸2{q˚ fi1{2
L`1
ÿ
ź
˚
–E
fl
|Xi0
Ditt pXq|q
,
t“1

i0 ,i1 ,...,iL

here for the case q “ 1. Due to Lemma 4.3, when the expectation is over empirical
measure,
» ˜
¸2{q˚ fi1{2 ˜
¸1{q
L`1
L
ÿ
ź
ÿ ź
1
˚
t
q
t
q
fl ¨
}θ}fr ď –p
E
|Xi0
Dit pXq|
|Wit it`1 |
,
L`1
t“1
i0 ,i1 ,...,iL
i0 ,i1 ,...,iL t“0
˜
¸
L
ÿ ź
t
|Wit it`1 | ,
ď max }Xi }8 ¨
i

i0 ,i1 ,...,iL t“0

#
which implies

ÿ

θ:

i0 ,i1 ,...,iL

L
ź

1
|Witt it`1 | ď
maxi }Xi }8
t“0

+
Ă Bfr p1q .

By Corollary 7 in [Neyshabur et al., 2015b], we know that for any r ą 0, the
Rademacher complexity of path-1 norm ball satisfies
˜#
+¸
L
ÿ ź
2L maxi }Xi }8 ¨ Polylog
t
?
.
RN
θ:
|Wit it`1 | ď r
Àr¨
N
i0 ,i1 ,...,iL t“0
Plugging in r “ maxi 1}Xi }8 , we find that the subset of Fisher-Rao norm ball Bfr p1q
induced by path-1 norm geometry, satisfies
˜#
+¸
L
ÿ ź
1
1
2L maxi }Xi }8 ¨ Polylog
?
RN
θ:
|Witt it`1 | ď
¨
À
Ñ0 .
maxi }Xi }8
maxi }Xi }8
N
i0 ,i1 ,...,iL t“0
Once again, the additional factor appearing in the Rademacher complexity bound
in [Neyshabur et al., 2015b], cancels with our pre-factor in the norm comparison.
4.1.4 Matrix induced norm.
Definition 6 (Induced norm). Define the following “matrix induced norm”
ball, for p, q ą 0, as
« ˜
¸ff1{2
L`1
L
ź
ź
2
t
2
(4.11)
}θ}pÑq :“ E }X}p
}D pXq}qÑp
}W t }pÑq .
t“1

t“0

file: paper_arxiv.tex date: November 7, 2017

14

Lemma 4.4 (Matrix induced norm). For any p, q ą 0, the following inequality
holds
1
}θ}fr ď }θ}pÑq .
L`1
Remark that }Dt pXq}2qÑp may contain dependence on k when p ‰ q. This
motivates us to consider the following generalization of matrix induced norm,
where the norm for each W t can be different.
Definition 7 (Chain of induced norm). Define the following “chain of induced norm” ball, for a chain of P “ pp0 , p1 , . . . , pL`1 q, pi ą 0
« ˜
¸ff1{2
L`1
L
ź
ź
2
t
2
(4.12)
}θ}P :“ E }X}p0
}D pXq}pt Ñpt
}W t }pt Ñpt`1 .
t“1

t“0

Lemma 4.5 (Chain of induced norm).

It holds that

1
}θ}fr ď }θ}P .
L`1
Remark 4.4. Lemma 4.5 exhibits a new flexible norm that dominates the
Fisher-Rao norm. The example shows that one can motivate a variety of new
norms (and their corresponding geometry) as subsets of the Fisher-Rao norm
ball.
We will conclude this section with two geometric observations about the FisherRao norm with absolute loss function `pf, yq “ |f ´ y| and one output node. In
1
this case, even though tθ : L`1
}θ}fr ď 1u is non-convex, it is star-shaped.
Lemma 4.6 (Star shape). For any θ P Θ, let trθ, r ą 0u denote the line
connecting between 0 and θ to infinity. Then one has,
d
2pL ` 1q
}rθ}2fr “
}rθ}2fr .
dr
r
This also implies
}rθ}fr “ rL`1 }θ}fr .
Despite the non-convexity of set of parameters with a bound on the Fisher-Rao
norm, there is certain “convexity” in the function space:
Lemma 4.7 (Convexity in fθ ).

For any θ1 , θ2 P ΘL that satisfy

1
}θi }fr ď 1, for i “ 1 or 2,
L`1
we have for any 0 ă λ ă 1, the convex combination λfθ1 ` p1 ´ λqfθ2 can be
realized by a parameter θ1 P ΘL`1 in the sense
fθ1 “ λfθ1 ` p1 ´ λqfθ2 ,
and satisfies
1
}θ1 }fr ď 1 .
pL ` 1q ` 1
file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

15

4.2 Generalization
In this section, we will investigate the generalization puzzle for deep learning
through the lens of the Fisher-Rao norm. We will first introduce a rigorous proof
in the case of multi-layer linear networks, that capacity control with Fisher-Rao
norm ensures good generalization. Then we will provide a heuristic argument why
Fisher-Rao norm seems to be the right norm-based capacity control for rectified
neural networks, via norm caparison in Section 4.1. We complement our heuristic
argument with extensive numerical investigations in Section 5.
Theorem 4.1 (Deep Linear Networks). Consider multi-layer linear networks
with σpxq “ x, L hidden layers, input dimension p and single output unit, and
parameters θ P ΘL “ tW 0 , W 1 , . . . , W L u. Define the Fisher-Rao norm ball as in
Eqn. (3.5)
1
Bfr pγq “ tθ :
}θ}fr ď γu .
L`1
Then we have
c
p
(4.13)
,
E RN pBfr pγqq ď γ
N
assuming the Gram matrix ErXX T s P Rpˆp is full rank.6
Remark 4.5. Combining the above Theorem with classic symmetrization
and margin bounds [Koltchinskii and Panchenko, 2002], one can deduce that for
binary classification, the following generalization guarantee holds (for any margin
parameter α ą 0),
c
1 ÿ
log 1{δ
C
E 1 rfθ pXqY ă 0s ď
,
1 rfθ pXi qYi ď αs ` RN pBfr pγqq ` C
N i
α
N
for any θ P Bfr pγq with probability at least 1 ´ δ, where C ą 0 is some constant.
We would like to emphasize that to explain generalization in this over-parametrized
multi-layer linear network, it is indeed desirable that the generalization error in
Theorem 4.1 only depends on the Fisher-Rao norm and the intrinsic input dimension p, without additional dependence on other network parameters (such as
width, depth) and the X dependent factor.
In the case of ReLU networks, it turns out that bounding RN pBfr pγqq in terms
of the Fisher-Rao norm is a very challenging task. Instead, we provide heuristic
arguments via bounding the Rademacher complexity for various subsets of Bfr pγq.
As discussed in Remarks 4.1-4.3, the norms considered (spectral, group, and path
norm) can be viewed as a subset of unit Fisher-Rao norm ball induced by distinct
6

This assumption is to simplify exposition, and can be removed.

file: paper_arxiv.tex date: November 7, 2017

16

geometry. To remind ourselves, we have shown
$
,
’
/
L
& ź
.
γ
t
spectral norm B}¨}σ :“ θ :
}W }σ ď ”
ı1{2 / Ă Bfr pγq ,
’
% t“0
2
p
E}X}
,
$
/
’
L
.
& ź
γ
t
Ă Bfr pγq ,
group p, q norm B}¨}p,q :“ θ :
}W }p,q ď ´ 1 1 ¯L
/
’
r ´ s
% t“0
k p˚ q ` maxi }Xi }p˚ +
#
L
ÿ ź
γ
Ă Bfr pγq ,
path-1 norm B}πp¨q}1 :“ θ :
|Witt it`1 | ď
maxi }Xi }8
i ,i ,...,i t“0
0 1

L

from which the following bounds follow,
`
˘
Polylog
RN B}¨}σ ď γ ¨
,
N
`
˘
2L Polylog
?
RN B}¨}p,q ď γ ¨
,
N
`
˘
2L Polylog
?
RN B}πp¨q}1 ď γ ¨
.
N
The surprising fact is that despite the distinct geometry of the subsets B}¨}σ ,
B}¨}p,q and B}πp¨q}1 (which are described by different norms), the Rademacher
complexity of these sets all depend on the “enveloping” Fisher-Rao norm explicitly without either the intriguing combinatorial factor or the X dependent
factor. We believe this envelope property sheds light on how to compare different
norm-based capacity measures.
Before concluding this section, we present the contour plot of Fisher-Rao norm
and path-2 norm in a simple two layer ReLU network in Fig. 1, to better illustrate
the geometry of Fisher-Rao norm and the subset induced by other norm. We
choose two weights as x, y-axis and plot the levelsets of the norms.
5. EXPERIMENTS
5.1 Experimental details
In the realistic K-class classification context there is no activation function on
the K-dimensional output layer of the network (σL`1 pxq “ x) and we focus on
ReLU activation σpxq “ maxt0, xu for the intermediate layers. The loss function
is taken to be the cross entropy `py 1 , yq “ ´xey , log gpy 1 qy, where ey P RK denotes
the one-hot-encoded class label and gpzq is the softmax function defined by,
˜
¸T
exppz1 q
exppzK q
gpzq “ řK
, . . . , řK
.
k“1 exppzk q
k“1 exppzk q
It can be shown that the gradient of the loss function with respect to the output
of the neural network is ∇`pf, yq “ ´∇xey , log gpf qy “ gpf q ´ ey , so plugging into
the general expression for the Fisher-Rao norm we obtain,
(5.1)

}θ}2fr “ pL ` 1q2 Ertxgpfθ pXqq, fθ pXqy ´ fθ pXqY u2 s.
file: paper_arxiv.tex date: November 7, 2017

17

CAPACITY MEASURE AND GEOMETRY
2.0

2.0

1.5
1.5

category

category

fr

fr

3.4

path

level

x_2

x_2

path

level
1.0

3.2
1.0

3.0

4

2.8
3

2.6
2.4
2.2

2

0.5

0.5

0.0

0.0

0.5

1.0

1.5

2.0

0.0

0.5

x_1

1.0

1.5

2.0

x_1

2

2

1

1

category

category

fr

fr

0

path

x_2

x_2

path

level

level
3

0

1.5

2

1.0

−1

1

−1

−2

−2

−2

−1

0

1

2

−2

x_1

−1

0

1

2

x_1

Fig 1. The levelsets of Fisher-Rao norm (solid) and path-2 norm (dotted). The color denotes
the value of the norm.

In practice, since we do not have access to the population density ppxq of the
covariates, we estimate the Fisher-Rao norm by sampling from a test set of size
m, leading to our final formulas
(5.2)

}θ}2fr “ pL ` 1q2

(5.3)

}θ}2fr,emp “ pL ` 1q2

m K
1 ÿÿ
gpfθ pxi qqy rxgpfθ pxi qq, fθ pxi qy ´ fθ pxi qy s2 ,
m i“1 y“1
m
1 ÿ
rxgpfθ pxi qq, fθ pxi qy ´ fθ pxi qyi s2 .
m i“1

5.2 Over-parametrization with Hidden Units
In order to understand the effect of network over-parametrization we investigated the relationship between different
řL´1proposals for capacity control and the
number of parameters d “ pk1 ` i“1 ki ki`1 ` kL K of the neural network.
For simplicity we focused on a fully connected architecture consisting of L hidden layers with k neurons per hidden layer so that the expression simplifies to
d “ krp ` kpL ´ 1q ` Ks. The network parameters were learned by minimizing the
cross-entropy loss on the CIFAR-10 image classification dataset with no explicit
regularization nor data augmentation. The cross-entropy loss was optimized using 200 epochs of minibatch gradient descent utilizing minibatches of size 50 and
otherwise identical experimental conditions described in [Zhang et al., 2016]. The
same experiment was repeated using minibatch natural gradient descent employing the Kronecker-factored approximate curvature (K-FAC) method [Martens and
Grosse, 2015] with the same learning rate and momentum schedules. The first
fact we observe is that the Fisher-Rao norm remains approximately constant (or
decreasing) when the network is overparametrized by increasing the width k at
fixed depth L “ 2 (see Fig. 2). If we vary the depth L of the network at fixed
file: paper_arxiv.tex date: November 7, 2017

18

width k “ 500 then we find that the Fisher-Rao norm is essentially constant
when measured in its ‘natural units’ of L ` 1 (see Fig. 3). Finally, if we compare
each proposal based on its absolute magnitude, the Fisher-Rao norm is distinguished as the minimum-value norm, and becomes Op1q when evaluated using
the model distribution. This self-normalizing property can be understood as a
consequence of the relationship to flatness discussed in section 3.3, which holds
when the expectation is taken with respect to the model.
5.3 Corruption with Random Labels
Over-parametrized neural networks tend to exhibit good generalization despite
perfectly fitting the training set [Zhang et al., 2016]. In order to pinpoint the
“correct” notion of complexity which drives generalization error, we conducted a
series of experiments in which we changed both the network size and the signal-tonoise ratio of the datasets. In particular, we focus on the set of neural architectures
obtained by varying the hidden layer width k at fixed depth L “ 2 and moreover
for each training/test example we assign a random label with probability α.
It can be seen from the last two panels of Fig. 5 and 4 that for non-random
labels (α “ 0), the empirical Fisher-Rao norm actually decreases with increasing
k, in tandem with the generalization error and moreover this correlation seems
to persist when we vary the label randomization. Overall the Fisher-Rao norm
is distinguished from other measures of capacity by the fact that its empirical
version seems to track the generalization gap and moreover this trend does not
appear to be sensitive to the choice of optimization.
It is also interesting to note that the Fisher-Rao norm has a stability property with respect to increasing k which suggests that a formal k Ñ 8 limit might
exist. Finally, we note that unlike the vanilla gradient, the natural gradient differentiates the different architectures by their Fisher-Rao norm. Although we don’t
completely understand this phenomenon, it is likely a consequence of the fact
that the natural gradient is iteratively minimizing the Fisher-Rao semi-norm.
5.4 Margin Story
Bartlett et al. [2017] adopted the margin story to explain generalization. They
investigated the spectrally-normalized margin to explain why CIFAR-10 with random labels is a harder dataset (generalize poorly) than the uncorrupted CIFAR-10
(which generalize well). Here we adopt the same idea in this experiment, where
we plot margin normalized by the empirical Fisher-Rao norm, in comparison to
the spectral norm, based on the model trained either by vanilla gradient and natural gradient. It can be seen from Fig. 6 that the Fisher-Rao-normalized margin
also accounts for the generalization gap between random and original CIFAR10. In addition, Table 1 shows that the empirical Fisher-Rao norm improves the
normalized margin relative to the spectral norm. These results were obtained
by optimizing with the natural gradient but are not sensitive to the choice of
optimizer.
5.5 Natural Gradient and Pre-conditioning
It was shown in [Shalev-Shwartz et al., 2017] that multi-layer networks struggle
to learn certain piecewise-linear curves because the problem instances are poorlyconditioned. The failure was attributed to the fact that simply using a black-box
model without a deeper analytical understanding of the problem structure could
file: paper_arxiv.tex date: November 7, 2017

19

CAPACITY MEASURE AND GEOMETRY

α“0
α“1
Ratio

Model Fisher-Rao

Empirical Fisher-Rao

Spectral

1.61
2.12
0.76

22.68
35.98
0.63

136.67
205.56
0.66

Table 1
Comparison of Fisher-Rao norm and spectral norm after training with natural gradient using
original dataset (α “ 0) and with random labels (α “ 1). Qualitatively similar results holds for
GD+momentum.

180

225

160

200

140

175

120

150

Path norm

l2 norm

be computationally sub-optimal. Our results suggest that the problem can be
overcome within the confines of black-box optimization by using natural gradient. In other words, the natural gradient automatically pre-conditions the problem and appears to achieve similar performance as that attained by hard-coded
convolutions [Shalev-Shwartz et al., 2017], within the same number of iterations
(see Fig. 7).

100
80

125
100

60

75

40

50

20
0

25
200

300

400

500

600

700

Neurons per hidden layer

800

900

0

1000

200

300

400

200

300

400

500

600

700

800

900

1000

500

600

700

800

900

1000

Neurons per hidden layer

1.8
600

1.6
1.4

Model Fisher-Rao norm

Spectral norm

500
400
300
200

1.2
1.0
0.8
0.6
0.4

100
0

0.2
200

300

400

500

600

700

Neurons per hidden layer

800

900

0.0

1000

Neurons per hidden layer

30

Empirical Fisher-Rao norm

25
20
15
10
5
0

200

300

400

500

600

700

Neurons per hidden layer

800

900

1000

Fig 2. Dependence of different norms on width k of hidden layers pL “ 2q after optimizing with
vanilla gradient descent (red) and natural gradient descent (blue).

file: paper_arxiv.tex date: November 7, 2017

20

160

700

140

600

120

500

Path norm

l2 norm

100
80
60

100

20
1

2

3

4

Hidden layers

0

5

5000
4000

Spectral norm

1

2

1

2

3

4

5

3

4

5

Hidden layers

0.6

Model Fisher-Rao norm (normalized)

6000

3000
2000
1000
0

300
200

40

0

400

1

2

3

4

Hidden layers

0.5
0.4
0.3
0.2
0.1
0.0

5

Hidden layers

Empirical Fisher-Rao (normalized)

12
10
8
6
4
2
0

1

2

3

Hidden layers

4

5

Fig 3. Dependence of different norms on depth L (k “ 500) after optimzing with vanilla gradient
descent (red) and natural gradient descent (blue). The Fisher-Rao norms are normalized by L`1.

file: paper_arxiv.tex date: November 7, 2017

21

160

1000

140

800

Spectral norm

l2 norm

CAPACITY MEASURE AND GEOMETRY

120

600

100
400
80
200
0.0

0.2

0.4

0.6

label randomization

0.8

1.0

0.0

0.2

0.0

0.2

0.0

0.2

0.4

0.6

0.8

1.0

0.4

0.6

0.8

1.0

0.4

0.6

0.8

1.0

label randomization

2.3

275

2.2

Model Fisher-Rao norm

Path norm

2.4
300

250
225
200

2.1
2.0
1.9
1.8

175
1.7
150

1.6
0.0

0.2

0.4

0.6

label randomization

0.8

1.0

label randomization

0.90
32
0.80

Generalization gap

Empirical Fisher-Rao norm

0.85
30
28
26
24

0.75
0.70
0.65
0.60

22
0.55
20

0.50
0.0

0.2

0.4

0.6

label randomization

0.8

1.0

label randomization

Fig 4. Dependence of capacity measures on label randomization after optimizing with vanilla
gradient descent. The colors show the effect of varying network width from k “ 200 (red) to
k “ 1000 (blue) in increments of 100.

file: paper_arxiv.tex date: November 7, 2017

22

160

275
250

Spectral norm

l2 norm

140

120

100

225
200
175
150

80
125
0.0

0.2

0.4

0.6

label randomization

0.8

1.0

2.2

240

2.1

Model Fisher-Rao norm

260

Path norm

220
200
180
160

0.0

0.2

0.0

0.2

0.0

0.2

0.4

0.6

0.8

1.0

0.4

0.6

0.8

1.0

0.4

0.6

0.8

1.0

label randomization

2.0
1.9
1.8
1.7
1.6

140
1.5
120
0.0

0.2

0.4

0.6

label randomization

0.8

1.0

label randomization

0.90
0.85

40

Generalization gap

Empirical Fisher-Rao norm

45

35
30

0.80
0.75
0.70
0.65
0.60

25
0.55
20
0.0

0.2

0.4

0.6

label randomization

0.8

1.0

label randomization

Fig 5. Dependence of capacity measures on label randomization after optimizing with the natural
gradient descent. The colors show the effect of varying network width from k “ 200 (red) to
k “ 1000 (blue) in increments of 100. The natural gradient optimization clearly distinguishes
the network architectures according to their Fisher-Rao norm.

0.5

70

12

60

0.4

10

50
8

0.3

40
6
30

0.2

4

20
0.1

2

10
0.0

0

5

10

15

20

25

0
0.00

0.02

0.04

0.06

0.08

0.10

0

0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

0.6

0.8

1.0

8

0.25
100
0.20

7
6

80

5

0.15

60
4

0.10

40

0.05

20

3
2
1

0.00

0

5

10

15

20

25

0
0.00

0.02

0.04

0.06

0.08

0.10

0

Fig 6. Distribution of margins found by natural gradient (top) and vanilla gradient (bottom)
before rescaling (left) and after rescaling by spectral norm (center) and empirical Fisher-Rao
norm (right).

file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

23

0
10
20
30
40
50
0

20

40

60

80

100

Fig 7. Reproduction of conditioning experiment from [Shalev-Shwartz et al., 2017] after 104
iterations of Adam (dashed) and K-FAC (red).

6. FURTHER DISCUSSION
In this paper we studied the generalization puzzle of deep learning from an
invariance point of view. The notions of invariance come from several angles: invariance in information geometry, invariance of non-linear local transformation,
invariance under function equivalence, algorithmic invariance of parametrization,
“flat” minima invariance of linear transformations, among many others. We proposed a new non-convex capacity measure using the Fisher-Rao norm. We demonstrated the good properties of Fisher-Rao norm as a capacity measure both from
the theoretical and the empirical side.
6.1 Parameter identifiability
Let us briefly discuss the aforementioned parameter identifiability issue in deep
networks. The function classes considered in this paper admit various group actions, which leave the function output invariant7 . This means that our hypothesis
class is in bijection with the equivalence class HL – Θ{ „ where we identify θ „ θ1
if and only if fθ ” fθ1 . Unlike previously considered norms, the capacity measure
introduced in this paper respects all of the symmetries of HL .
Non-negative homogeneity In the example of deep linear networks, where
σpxq “ x, we have the following non-Abelian Lie group symmetry acting on the
network weights for all Λ1 , . . . , ΛL P GLpk1 , Rq ˆ ¨ ¨ ¨ ˆ GLpkL , Rq,
´1
´1
1
l
L
θ ÝÑ pW 0 Λ1 , Λ´1
1 W Λ2 . . . , Λl W Λl`1 , . . . , ΛL W q .

It is convenient to express these transformations in terms of the Lie algebra of
real-valued matrices M1 , . . . , ML P Mk1 pRq ˆ ¨ ¨ ¨ ˆ MkL pRq,
θ ÝÑ pW 0 eM1 , e´M1 W 1 eM2 . . . , e´Ml W l eMl`1 , . . . , e´ML W L q .
If σpxq “ maxt0, xu (deep rectified network) then the symmetry is broken to the
abelian subalgebra vl , . . . , vL P Rk1 ˆ ¨ ¨ ¨ ˆ RkL ,
Λ1 “ ediagpv1 q , . . . , ΛL “ ediagpvL q .
Dead neurons. For certain choices of activation function the symmetry group
is enhanced at some θ P Θ. For example, if σpxq “ maxt0, xu and the parameter
7

In the statistics literature this is referred to as a non-identifiable function class.
file: paper_arxiv.tex date: November 7, 2017

24

vector θ is such that all the weights and biases feeding into some hidden unit v P V
are negative, then fθ is invariant with respect to all of the outgoing weights of v.
Permutation symmetry. In addition to the continuous symmetries there is
discrete group of permutation symmetries. In the case of a single hidden layer
with k units, this discrete symmetry gives rise to k! equivalent weights for a given
θ. If in addition the activation function satisfies σp´xq “ ´σpxq (such as tanh)
then we obtain an additional degeneracy factor of 2k .
6.2 Invariance of natural gradient
Consider the continuous-time analog of natural gradient flow,
(6.1)

dθt “ ´Ipθt q´1 ∇θ Lpθt qdt,

where θ P Rp . Consider a differentiable transformation from one parametrization
to another θ ÞÑ ξ P Rq denoted by ξpθq : Rp Ñ Rq . Denote the Jacobian Jξ pθq “
Bpξ1 ,ξ2 ,...,ξq q
qˆp . Define the loss function L̃ : ξ Ñ R that satisfies
Bpθ1 ,θ2 ,...,θp q P R
Lpθq “ L̃pξpθqq “ L̃ ˝ ξpθq,
and denote Ĩpξq as the Fisher Information on ξ associated with L̃. Consider also
the natural gradient flow on the ξ parametrization,
(6.2)

dξt “ ´Ĩpξt q´1 ∇ξ L̃pξt qdt.

Intuitively, one can show that the natural gradient flow is “invariant” to the
specific parametrization of the problem.
Lemma 6.1 (Parametrization invariance). Denote θ P Rp , and the differentiable transformation from one parametrization to another θ ÞÑ ξ P Rq as
ξpθq : Rp Ñ Rq . Assume Ipθq, Ĩpξq are invertible, and consider two natural gradient flows tθt , t ą 0u and tξt , t ą 0u defined in Eqn. (6.1) and (6.2) on θ and ξ
respectively.
(1) Re-parametrization: if q “ p, and assume Jξ pθq is invertible, then natural
gradient flow on the two parameterizations satisfies,
ξpθt q “ ξt ,

@t,

if the initial locations θ0 , ξ0 are equivalent in the sense ξpθ0 q “ ξ0 .
(2) Over-parametrization: If q ą p and ξt “ ξpθt q at some fixed time t, then
the infinitesimal change satisfies
ξpθt`dt q ´ ξpθt q “ Mt pξt`dt ´ ξt q,

Mt has eigenvalues either 0 or 1

where Mt “ Ipξt q´1{2 pIq ´ UK UKT qIpξt q1{2 , and UK denotes the null space of
Ipξq1{2 Jξ pθq.
7. PROOFS
Proof of Lemma 2.1. Recall the property of the activation function in (2.2).
Let us prove for any 0 ď t ď s ď L, and any l P rks`1 s
(7.1)

ÿ
iPrkt s,jPrkt`1 s

BOls`1 t
Wij “ Ols`1 pxq.
BWijt
file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

25

We prove this statement via induction on the non-negative gap s ´ t. Starting
with s ´ t “ 0, we have
BOlt`1 BNlt`1
BOlt`1
“
“ σ 1 pNlt`1 pxqqOit pxq,
BWilt
BNlt`1 BWilt
BOlt`1
“ 0,
BWijt

for j ‰ l,

and, therefore,
(7.2)
ÿ
iPrkt s,jPrkt`1 s

ÿ
BOlt`1 t
W
“
σ 1 pNlt`1 pxqqOit pxqWilt “ σ 1 pNlt`1 pxqqNlt`1 pxq “ Olt`1 pxq.
ij
BWijt
iPrkt s

This solves the base case when s ´ t “ 0.
Let us assume for general s ´ t ď h the induction hypothesis (h ě 0), and let
us prove it for s ´ t “ h ` 1. Due to chain-rule in the back-propagation updates
BOls`1
BOls`1 ÿ BNls`1 BOks
“
.
BWijt
BNls`1 kPrk s BOks BWijt

(7.3)

s

Using the induction on

BOks
t
BWij

as ps ´ 1q ´ t “ h
ÿ

(7.4)

iPrkt s,jPrkt`1 s

BOks t
W “ Oks pxq,
BWijt ij

and, therefore,
ÿ
iPrkt s,jPrkt`1 s

BOls`1 t
Wij
BWijt

ÿ
“
iPrkt s,jPrkt`1

“

BOls`1 ÿ BNls`1 BOks t
Wij
BNls`1 kPrk s BOks BWijt
s
s

BOls`1 ÿ
BNls`1 kPrk s
s

ÿ
BNls`1
BOks
iPrkt s,jPrkt`1 s
ÿ

“ σ 1 pNls`1 pxqq

BOks t
W
BWijt ij

s s
Wkl
Ok pxq “ Ols`1 pxq.

kPrks s

This completes the induction argument. In other words, we have proved for any
t, s that t ď s, and l is any hidden unit in layer s
(7.5)

ÿ
i,jPdimpW t q

BOls`1 t
Wij “ Ols`1 pxq.
BWijt

Remark that in the case when there are hard-coded zero weights, the proof
still goes through exactly. The reason is, for the base case s “ t,
ÿ
iPrkt s,jPrkt`1 s

ÿ
BOlt`1 t
W
“
σ 1 pNlt`1 pxqqOit pxqWilt 1pWilt ‰ 0q “ σ 1 pNlt`1 pxqqNlt`1 pxq “ Olt`1 pxq.
ij
BWijt
iPrkt s

file: paper_arxiv.tex date: November 7, 2017

26

and for the induction step,
ÿ
iPrkt s,jPrkt`1 s

ÿ
BOls`1 t
s s
s
Wij “ σ 1 pNls`1 pxqq
Wkl
Ok pxq1pWkl
‰ 0q “ Ols`1 pxq.
t
BWij
kPrks s

Proof of Lemma 4.1. The proof follows from a peeling argument from the
right hand side. Recall Ot P R1ˆkt , one has
“
‰
1
}θ}2fr “ E |OL W L DL`1 |2
because |OL W L | ď |W L }σ ¨ }OL }2
2
pL ` 1q
“
‰
ď E }W L }2σ ¨ }OL }22 ¨ |DL`1 pXq|2
“
‰
“ E |DL`1 pXq|2 ¨ }W L }2σ ¨ }OL´1 W L´1 DL }22
“
‰
ď E |DL`1 pXq|2 ¨ }W L }2σ ¨ }OL´1 W L´1 }22 ¨ }DL }2σ
“
‰
ď E }DL }2σ |DL`1 pXq|2 ¨ }W L }2σ }W L´1 }2σ ¨ }OL´1 }22
“
‰
ď E }DL }2σ }DL`1 pXq}2σ }OL´1 }22 ¨ }W L´1 }2σ }W L }2σ
repeat the process to bound }OL´1 }2
˜
¸
L`1
L
ź
ź
2
t
2
ď E }X}
}D pXq}σ
}W t }2σ “ }θ}2σ .

...

t“1

t“0

Proof of Lemma 4.2. The proof still follows a peeling argument from the
right. We know that
“
‰
1
}θ}2fr “ E |OL W L DL`1 |2
2
pL ` 1q
“
‰
ď E }W L }2p,q ¨ }OL }2p˚ ¨ |DL`1 pXq|2
use (7.6)
“ L`1
‰
2
L 2
L´1
L´1 L 2
“ E |D
pXq| ¨ }W }p,q ¨ }O
W
D }p˚
“
‰
ď E |DL`1 pXq|2 ¨ }W L }2p,q ¨ }OL´1 W L´1 }2q ¨ }DL }2qÑp˚
“
‰
ď E }DL }2qÑp˚ }DL`1 pXq}2p,q ¨ }W L }2p,q }W L´1 }2p,q ¨ }OL´1 }2p˚
“
‰
“ E }DL }2qÑp˚ }DL`1 pXq}2p,q ¨ }OL´1 }2p˚ ¨ }W L´1 }2p,q }W L }2p,q

use (7.8)

ď . . . repeat the process to bound }OL´1 }p˚
˜
¸
L`1
L
ź
ź
2
t
2
ď E }X}p˚
}D pXq}qÑp˚
}W t }2p,q “ }θ}2p,q
t“1

t“0

In the proof the first inequality we use Holder’s inequality
(7.6)
where
(7.7)

xw, vy ď }w}p }v}p˚
1
p

`

1
p˚

“ 1. Let’s prove for v P Rn , M P Rnˆm , we have
}v T M }q ď }v}p˚ }M }p,q .

file: paper_arxiv.tex date: November 7, 2017

27

CAPACITY MEASURE AND GEOMETRY

Denote each column of M as M¨j , for 1 ď j ď m,
˜
(7.8)

T

}v M }q “

m
ÿ

¸1{q
T

|v M¨j |

q

˜

m
ÿ

ď

¸1{q
}v}qp˚ }M¨j }qp

“ }v}p˚ }M }p,q .

j“1

j“1

Proof. Proof of Lemma 4.3 The proof is due to Holder’s inequality, for any
x P Rp
ˇ
ˇ
ˇ ÿ
ˇ
ˇ
ˇ
0
1
1
L
L L`1
W
D
pxqW
¨
¨
¨
D
x
pxqW
D
pxq
ˇ
ˇ
i0 i 0 i1 i1
i1 i2
iL
iL
ˇi ,i ,...,i
ˇ
0 1
L
˜
¸1{q˚ ˜
¸1{q
ÿ
ÿ
˚
ď
|xi0 Di11 pxq ¨ ¨ ¨ DiLL pxqDL`1 pxq|q
¨
|Wi00 i1 Wi11 i2 Wi22 i3 ¨ ¨ ¨ WiLL |q
.
i0 ,i1 ,...,iL

i0 ,i1 ,...,iL

Therefore we have
ˇ
ˇ2
ˇ ÿ
ˇ
1
ˇ
ˇ
0
2
1
1
L L`1
“
E
X
W
}θ}
D
pXqW
¨
¨
¨
W
D
pXq
ˇ
ˇ
i
i
i
i
i
i
i
0
fr
i
0 1
1
1 2
L
2
L
ˇi ,i ,...,i
ˇ
pL ` 1q
0 1
L
˜
¸2{q˚
¸2{q
˜
ÿ
ÿ
˚
|Wi00 i1 Wi11 i2 Wi22 i3 ¨ ¨ ¨ WiLL |q
ď
|Xi0 Di11 pXq ¨ ¨ ¨ DiLL pXqDL`1 pXq|q
¨E
,
i0 ,i1 ,...,iL

i0 ,i1 ,...,iL

which is
» ˜
¸2{q˚ fi1{2 ˜
¸1{q
L`1
L
ÿ
ź
ÿ ź
1
˚
t
q
t
q
fl ¨
|Xi0
}θ}fr ď –E
Dit pXq|
|Wit it`1 |
“ }πpθq}q .
L`1
t“1
i ,i ,...,i
i ,i ,...,i t“0
0 1

0 1

L

L

Proof of Lemma 4.4. The proof follows from the recursive use of the inequality,
}M }pÑq }v}p ě }v T M }q .
We have
“
‰
}θ}2fr “ E |OL W L DL`1 |2
“
‰
ď E }W L }2pÑq ¨ }OL }2p ¨ |DL`1 pXq|2
“
‰
ď E |DL`1 pXq|2 ¨ }W L }2pÑq ¨ }OL´1 W L´1 DL }2p
“
‰
ď E |DL`1 pXq|2 ¨ }W L }2pÑq ¨ }OL´1 W L´1 }2q ¨ }DL }2qÑp
“
‰
ď E }DL }2qÑp }DL`1 pXq}2qÑp ¨ }W L }2pÑq }W L´1 }2pÑq ¨ }OL´1 }2p
ď . . . repeat the process to bound }OL´1 }p
¸
˜
L`1
L
ź
ź
ď E }X}2p
}Dt pXq}2qÑp
}W t }2pÑq “ }θ}2pÑq ,
t“1

t“0

where third to last line is because DL`1 pXq P R1 , |DL`1 pXq| “ }DL`1 pXq}qÑp .

file: paper_arxiv.tex date: November 7, 2017

28

Proof of Lemma 4.5. The proof follows from a different strategy of peeling
the terms from the right hand side, as follows,
“
‰
}θ}2fr “ E |OL W L DL`1 |2
”
ı
ď E }W L }2pL ÑpL`1 ¨ }OL }2pL ¨ |DL`1 pXq|2
”
ı
ď E |DL`1 pXq|2 ¨ }W L }2pL ÑpL`1 ¨ }OL´1 W L´1 DL }2pL
”
ı
ď E |DL`1 pXq|2 ¨ }W L }2pL ÑpL`1 ¨ }OL´1 W L´1 }pL }DL }2pL ÑpL
”
ı
ď E }DL }2pL ÑpL |DL`1 pXq|2 ¨ }W L }2pL ÑpL`1 }W L´1 }2pL´1 ÑpL ¨ }OL´1 }2pL´1
˜
¸
L`1
L
ź
ź
2
t
2
ď E }X}p0
}D pXq}pt Ñpt
}W t }2pt Ñpt`1 “ }θ}2P .
t“1

t“0

Proof of Lemma 4.6.
d
}rθ}2fr “ E r2θ∇frθ pXqfrθ pXqs
dr
„

2pL ` 1q
“E
frθ pXqfrθ pXq
r
2pL ` 1q
“
}rθ}2fr
r

use Lemma 2.1

The last claim can be proved through solving the simple ODE.
Proof of Lemma 4.7. Let us first construct θ1 P ΘL`1 that realizes λfθ1 `
p1 ´ λqfθ2 . The idea is very simple: we put θ1 and θ2 networks side-by-side, then
construct an additional output layer with weights λ, 1 ´ λ on the output of fθ1
and fθ2 , and the final output layer is passed through σpxq “ x. One can easily
see that our key Lemma 2.1 still holds for this network: the interaction weights
between fθ1 and fθ2 are always hard-coded as 0. Therefore we have constructed
a θ1 P ΘL`1 that realizes λfθ1 ` p1 ´ λqfθ2 .
Now recall that
`
˘1{2
1
}θ1 }fr “ E fθ21
L`2
`
˘1{2
“ Epλfθ1 ` p1 ´ λqfθ2 q2
`
˘1{2
`
˘1{2
ď λ E fθ21
` p1 ´ λq E fθ22
ď1
`
˘1{2 ` 2 ˘1{2
because Erfθ1 fθ2 s ď E fθ21
E fθ2
.
Proof of Theorem 4.1. Due to Eqn. (3.5), one has
“
‰
1
2
T
T
}θ}
“
E
vpθ,
Xq
XX
vpθ,
Xq
fr
pL ` 1q2
“
‰
“ vpθqT E XX T vpθq

file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

29

because
in the linear case vpθ, Xq “ W 0 D1 pxqW 1 D2 pxq ¨ ¨ ¨ DL pxqW L DL`1 pxq “
śL
t
p
t“0 W “: vpθq P R . Therefore
N
1 ÿ
i fθ pXi q
RN pBfr pγqq “ E sup
 θPB pγq N
fr
i“1
N
1 ÿ
i XiT vpθq
 θPB pγq N
fr
i“1
G
C
N
1 ÿ
“ E sup
i Xi , vpθq
 θPB pγq N
fr
i“1
›
›
N
›
1 ›› ÿ
›
ď γ E › i Xi ›
 N ›
›
i“1
rEpXX T qs´1
g
f
›2
›
f
N
›
1 f 1 ›› ÿ
›
ď γ ? e E › i Xi ›
›
N N  ›i“1
T

“ E sup

rEpXX qs´1

gC
G
f
N
ÿ
1 f
1
“ γ? e
Xi XiT , rEpXX T qs´1 .
N i“1
N
Therefore
g C
G
f
c
N
ÿ
1 f
1
p
´1
e
T
T
Xi Xi , rEpXX qs
“γ
.
E RN pBfr pγqq ď γ ?
E
N i“1
N
N

Proof of Lemma 6.1. From basic calculus, one has
∇θ Lpθq “ Jξ pθqT ∇ξ L̃pξq
Ipθq “ Jξ pθqT ĨpξqJξ pθq
Therefore, plugging in the above expression into the natural gradient flow in θ
dθt “ ´Ipθt q´1 ∇θ Lpθt qdt
“ ´rJξ pθt qT Ĩpξpθt qqJξ pθt qs´1 Jξ pθt qT ∇ξ L̃pξpθt qqdt.
In the re-parametrization case, Jξ pθq is invertible, and assuming ξt “ ξpθt q,
dθt “ ´rJξ pθt qT Ĩpξpθt qqJξ pθt qs´1 Jξ pθt qT ∇ξ L̃pξpθt qqdt
“ ´Jξ pθt q´1 Ĩpξpθt qq´1 ∇ξ L̃pξpθt qqdt
Jξ pθt qdθt “ ´Ĩpξpθt qq´1 ∇ξ L̃pξpθt qqdt
dξpθt q “ ´Ĩpξpθt qq´1 ∇ξ L̃pξpθt qqdt “ ´Ĩpξt q´1 ∇ξ L̃pξt qdt.
What we have shown is that under ξt “ ξpθt q, ξpθt`dt q “ ξt`dt . Therefore, if
ξ0 “ ξpθ0 q, we have that ξt “ ξpθt q.
file: paper_arxiv.tex date: November 7, 2017

30

In the over-parametrization case, Jξ pθq P Rqˆp is a non-square matrix. For
simplicity of derivation, abbreviate B :“ Jξ pθq P Rqˆp . We have
dθt “ θt`dt ´ θt “ ´Ipθt q´1 ∇θ Lpθt qdt
“ ´rB T ĨpξqBs´1 B T ∇ξ L̃pξpθt qqdt
”
ı´1
B T L̃pξpθt qqdt.
Bpθt`dt ´ θt q “ ´B B T ĨpξqB
Via the Sherman-Morrison-Woodbury formula
„

1
Iq ` Ĩpξq1{2 BB T Ĩpξq1{2


´1
“ Iq ´ Ĩpξq1{2 BpIp ` B T ĨpξqBq´1 B T Ĩpξq1{2

Denoting Ĩpξq1{2 BB T Ĩpξq1{2 “ U ΛU T , we have that rankpΛq ď p ă q. Therefore,
the LHS as
´1
„

„
1 ´1 T
1
1{2
T
1{2
“ U Iq ` Λ
U
Iq ` Ĩpξq BB Ĩpξq


„
´1
1
1{2
T
1{2
lim Iq ` Ĩpξq BB Ĩpξq
“ UK UKT
Ñ0

where UK corresponding to the space associated with zero eigenvalue of Ĩpξq1{2 BB T Ĩpξq1{2 .
Therefore taking  Ñ 0, we have
„

1
lim Iq ` Ĩpξq1{2 BB T Ĩpξq1{2
Ñ0

´1{2

Ĩpξq

´1

UK UKT Ĩpξq´1{2

“ lim Iq ´ Ĩpξq1{2 BpIp ` B T ĨpξqBq´1 B T Ĩpξq1{2
Ñ0

“ Ĩpξq´1 ´ BpB T ĨpξqBq´1 B T

where only the last step uses the fact Ĩpξq is invertible. Therefore
ξpθt`dt q ´ ξpθt q “ Bpθt`dt ´ θt q
“
‰´1 T
“ ´B B T In pξqB
B ∇ξ L̃pξqdt
“ ´ηIpξq´1{2 pId ´ UK UKT qIpξq´1{2 ∇ξ L̃pξqdt
!
)
“ Ipξq´1{2 pId ´ UK UKT qIpξq1{2 Ipξq´1 ∇ξ L̃pξqdt
“ Mt pξt`dt ´ ξt q.
The above claim aserts that in the over-parametrized setting, running natural
gradient in the over-parametrized is nearly “invariant” in the following sense: if
ξpθt q “ ξt , then
ξpθt`dt q ´ ξpθt q “ Mt pξt`dt ´ ξt q
Mt “ Ipξt q´1{2 pIq ´ UK UKT qIpξt q1{2
and we know Mt has eigenvalue either 1 or 0. In the case when p “ q and Jξ pθq
has full rank, it holds that Mt “ I is the identity matrix, reducing the problem
to the re-parametrized case.

file: paper_arxiv.tex date: November 7, 2017

CAPACITY MEASURE AND GEOMETRY

31

REFERENCES
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):
251–276, 1998.
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 1999.
Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for
neural networks. arXiv preprint arXiv:1706.08498, 2017.
Martin Bauer, Martins Bruveris, and Peter W Michor. Uniqueness of the fisher–rao metric on
the space of smooth densities. Bulletin of the London Mathematical Society, 48(3):499–506,
2016.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize
for deep nets. arXiv preprint arXiv:1703.04933, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1–42, 1997.
Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the
generalization error of combined classifiers. Annals of Statistics, pages 1–50, 2002.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep
convolutional neural networks. In Advances in neural information processing systems, pages
1097–1105, 2012.
Anders Krogh and John A Hertz. A simple weight decay can improve generalization. In Advances
in neural information processing systems, pages 950–957, 1992.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International Conference on Machine Learning, pages 2408–2417,
2015.
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized
optimization in deep neural networks. In Advances in Neural Information Processing Systems,
pages 2422–2430, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural
networks. In Conference on Learning Theory, pages 1376–1401, 2015b.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring
generalization in deep learning. arXiv preprint arXiv:1706.08947, 2017.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of deep learning. arXiv
preprint arXiv:1703.07950, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding
deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.

file: paper_arxiv.tex date: November 7, 2017

