Barcodes as summary of objective functions' topology
Authors: Serguei Barannikov
Alexander Korotin
Dmitry Oganesyan
Daniil Emtsev
Evgeny Burnaev
Venue:  (2020)
Keywords: Barcodes
canonical form invariants
loss surface
gradient complexes

Abstract: We apply canonical forms of gradient complexes (barcodes) to explore neural networks loss surfaces. We present an algorithm for calculations of the objective function's barcodes of minima.  Our experiments confirm two principal observations: (1) the barcodes of minima are located in a small lower part of the range of values of objective function and (2) increase of the neural network's depth brings down the minima's barcodes. This has natural implications for the neural network learning and the ability to generalize. 

Under review as a conference paper at ICLR 2020
BARCODES AS SUMMARY OF OBJECTIVE FUNCTIONS' TOPOLOGY
Anonymous authors Paper under double-blind review
ABSTRACT
We apply the canonical forms of gradient Morse complexes (barcodes) to explore topology of loss surfaces. We present a new algorithm for calculations of the objective function's barcodes of minima. Our experiments confirm two principal observations: (1) the barcodes of minima are located in a small lower part of the range of values of loss function of neural networks and (2) increase of the neural network's 's depth brings down the minima's 's barcodes. This has natural implications for the neural network learning and the ability to generalize.
INTRODUCTION
The learning via finding minima of objective functions is the principal strategy underlying majority of learning algorithms. For example, in Neural Network training, the objective function's 's input is model parameters (weights) and the objective function's 's output the loss on training dataset. The graph of the loss function, often called loss surface, typically has complex structure (e.g. see loss surface visualisations by [Li et al. (2018)): non-convexity, many local minima, flat regions, steep slopes. These obstacles harm exploration of the loss surface and complicate searching for optimal network weights.
The optimization of modern neural networks is based on the gradient descent algorithm. The global topological characteristics of the gradient vector field trajectories are captured by the Morse complex via decomposing the parameter space into cells of uniform flow, see [Barannkkvv (1994); Le Roux et al. (2018) and references therein. The invariants of Morse complex called "canonical forms" (or barcodes) constitute the fundamental summary of the topology of the gradient vector field flow.
The "canonical forms", or barcodes, in this context are decompositions of the change of topology of the sublevel sets of objective function into simple "birth-death" phenomena of topological feautures of different dimensions.
The caleulation of the barcodes for different functions constitutes the essence of the topological data analysis. The currently available software packages for the calculation of barcodes of functions, also called "sublevel persistence". are GUDHI, Dionysus, PHAT, and TDA package which incorporates all three previous packages F.s.Fasy et al. (0014). They are based on the algorithm, described in Barannikov (1994). see also appendix and e.g. Bauer al.) (2014) and references therein. This algorithm which has complexity of (nz)). These packages can currently handle calculations of barcodes for functions defined on a grid of up to 106 points, and in dimensions two and three. Thus
all current packages have the scalability issues.
We describe a new algorithm for computations of the barcodes of functions in lowest degree. Our algorithm works with functions defined on randomly sampled or specifically chosen point clouds. Point cloud based methods are known to work better than grid based methods in optimization related problems (Bergstra and Bengio (2012)). We also use the fact that the definition of the barcode of lowest degree can be reformulated in geometrical terms (see definition in section 2). The previously known algorithms were based the more algebraic approach as in definition 3. Our algorithm has complexity of (n log(n)). It was tested in dimensions up to 16 and with number of points of up to 108.
In this work, we develop a methodology to describe the properties of the loss surface of the neural network via topologiaal features of local minima.

---

Under review as a conference paper at ICLR 2020
We emphasize that the value of the objective function at the minimum be viewed only part of its topologiaal characteristic from the "canonical form" (barcode). The second half can be described as the value of objective function at the index-one saddle, which can be naturally associated with each local minimum.
The difference between the values of objective function at the associated index-one saddle and the local minimum is topologiaal invariant of the minimum. For optimization algorithms this quantity measures, in particular, the obligatory penalty for moving from the given local minimum to lower minimum.
The main contributions of the paper are follows:
Applying the one-to-one correspondence between local minima and 1-saddles to exploration of loss surfaces. For each local minimum p there is canonically defined I-saddle q (see Section 2). The I-saddle associated with p can be described as follows. The 1- saddle is precisely the point where the connected component of the sublevel set f = {0 E f(0) S c} containing the minimum merges with another connected component of the sublevel set whose minimum is lower. This correspondence between the local minima and the 1-saddles, killing a connected component of Ofşe. is one-to-one. The segment (p): [()) is then the "canonical form" invariant attached to the minimum p. The set of all such segments is the barcode ("canonical form") ") of minima invariant of s. It is robust topological invariant of objective function. It is invariant in particular under the action of homeomorphisms of O. Full "canonical form" invariants give a concise summary of the topology of objective function and of the global structure of its gradient flow.
Algorithm for calculations of the barcodes (canonical invariants) of minima. We describe an algorithm for caleulation of the canonical invariants of minima. The algorithm works with function's values on a a randomly sampled or specifically chosen set of points. The local minima give birth to clusters of points in sublevel sets. The algorithm works by looking at neighbors of each point with lower value of the function and deciding if this point belongs to the existing clusters, gives birth new cluster (minimum), or merges two or more clusters (index one saddle). A variant of the algorithm has complexity of O( log(n)), where n is the cardinality of the set of points.
Calculations confirming observations on behaviour of neural networks loss functions barcodes. We calculate the canonical invariants (barcodes) of minima for small fully- cully-coneected neural networks of up to three hidden layers and verify that all segments of minima's barcode belong to a small lower part of the total range of loss function's 's values and that with the increase in the neural network depth the minima's barcodes descend lower.
The usefulness of our approach and algorithms is clearly not limited to the optimization problems. Our algorithm permits really fast computation of the canonical form invariants (persistence barcodes) of many functions which were not accessible until now. These sublevel persistence barcodes have been successfully applied in different discipline, to mention just a few: cognitive science (M. K. Chung and Kim (2009) ), cosmology (Sousbie al. (2011)). see c.g. Pun al. (2018) ) and references therein.
Our viewpoint should also have applications in chemistry and material science where 1-saddle points on potential energy landscapes correspond transition states and minima stable states corresponding to different materials or protein foldings (see e.g. Dellago et al. (2003), Oganov and Valle ).09)).
The article is structured as follows. First we describe three definitions of barcodes of minima. After that our algorithm for their calculation is described. In the last part we give examples of calculations, including the loss functions of simple neural nets.
TOPOLOGY OF LOSS SURFACES VIA CANONICAL FORM INVARIANTS
The "canonical form" invariants (barcodes) give concise summary of topological features of functions (see Barannikov] (1994). Le Roux et al.] (2018) and references therein). These invariants describe a decomposition of the change of topology of the function into the finite sum of "birth"- "death" of elementary features. We propose to apply these invariants as a tool for exploring topology of loss surfaces.
2

---

Under review as a conference paper at ICLR 2020
In this work concentrate the part of these canonical form invariants, describing the "birth"- "death" phenomena of connected components of sublevel sets of the function.
However it should be stressed that this approach works similarly also for "almost minima", i.c. for the critical points (manifolds) of small indexes, which are often the terminal points of the optimization algorithms in very high dimensions.
We give three definitions of the "canonical form" invariants of minima.
DEFINITION 1: MERGING WITH CONNECTED COMPONENT OF LOWER MINIMUM
The values parameter e which the topology of sublevel set
+ gze
(0 θ ((0) s c]
changes critical values of
Let p be one of minima of f. When increases from f(p) - to f(p) + c, new connected component of the S is born (see fig Tal the connected components St, S2, S3 of sublevel set born at the blue, green and red minima correspondingly.
If p is minimum, which born at p merges with a connected component born at a lower minimum. Let g is the merging point where this happens. The intersection of the set + f< f(g) with any small neighborhood of q has two connected components. This is the index-one saddle associated with
global, then, when is increased, the connected component of yyge
S
S₁
S1
(a) "Death" of the connected com- ponent S3. The connected com- ponent S3 of sublevel merges with connected component at red saddle, red saddle is associ- ated with the red minimum.
(b) "Death" of the connected com- ponent S4. The connected com- ponent S4 of sublevel set merges with connected component S; violet saddle, violet saddle is as- sociated with the violct minimum
(c) "Death" of the connected com- ponent S2. The connected com- ponent S2 of sublevel merges with connected component at green saddle, green saddle as- sociated with the green minimum.
Figure 1: Merging of connected components of sublevel sets at saddles. Note that the green saddle associated with the green minimum which is separated by another minimum from the green saddle.
Also these two subsets small neighborhood of q belong to two different connected components of the whole set ) The 1-saddles of this type called "+" ("plus") "death" type. The described correspondence between local minima and 1-saddles of this type is one-to-one.
In similar way, the 1-saddle q associated with p be described also as follows.
Proposition 2.1. Consider various paths " starting from the local minimum p and going to lower minimum. Let m. ④ is the maximun of the restriction of f to such path xy_ Then 1-saddle q which is paired with the local minimum is the minimum over the set of all such paths ry of the maxima my
max ((((0)
q arg
min 1: <(0=p,. ((()))(()))
DEFINITION 2: NEW MINIMUM ON CONNECTED COMPONENTS OF SUBLEVEL SETS
The correspondence in the opposite direction can be described analogously. Let is 1 1-saddle point of such type that the two branches of the set (() - near g belong to different connected components of θ f (f5((g)- A new connected component of the set O e is formed when e decreases from f()) + +et to f(g) e. The restriction of f to each of the two connected components has its global minimum.
3

---

Under review as a conference paper at ICLR 2020
Proposition 2.2. Given a I-saddle 9, the minimum p which is paired with is the minimum of f on the connected component of the set Oyge which is formed when с decreases from f(q) + c to f(g) [
The two branches of the set θ f(f()) near q can also belong to the same connected components of this set. Then such saddle is of "irthh type and it is naturally paired with index-two saddle of "death" type (see theorem 2.3)
DEFINITION 3: INVARIANTS AILTERED COMPLEXES
Chain complex the algebraic counterpart of intuitive idea representing complicated geometric objects decomposition into simple pieces. It converts such decomposition into collection of vector spaces and linear maps.
A chain complex (C., 0,) is sequence of finite-dimensional k-vector spaces and linear operators
+ Cj+1 " Cj 4 Cj-1 +... Co.
which satisfy
0 0.
The jhth homology of the chain complex (C., is the quotient
H = ker (0,) //mm (0j+1).
chain complex C. is called IR filtered C. equipped with an increasing sequence of sub- complexes (R (i-fiitration) Fsy C2 C Fez C. .... C F Fsmea Cx C., indexed by finite set of real
numbers 81 < 82 <... < Smax.
Theorem 2.3. (Barannikov (7994)) Any R. RR-fltered chain complex C. can be brought by a linear transformation preserving the filtration "canonical form", canonically defined direct sum of R R-filtered complexes of two types: one- oie-dimenso complexes with trivial differential 0z(e:) and wwoddimensional complexes with trivial homology Öz(ei,) City The resulting canonical form is uniquely determined.
The full barcode is a visualization of the decomposition of an R filtered complexes according to the theorem 2.3 Each filtered 2-dimensional complex with trivial homology (eig)) ex (ei,) = - ( Gig) = F5 describes a topological feature in dimension j which is "born" at 81 and which "dies" 82- is represented by segment [81, $2] in the degree-j barcode. And each filtered 1 I-dimensional complex with trivial differential, 0je, 0, (ex) = F&r describes a topological fcature in dimension which is "born" at and never "dies". It represented by the half-line [r, +oo the degree-j barcode.
The proof of the theorem given in Appendix. Essentially, one can bring an R R-filtered complex to the required canonical form by induction, starting from the lowest basis elements of degree one, in such a way that the manipulation of degree j basis elements does not destroy the canonical form in degree 1 and in lower filtration pieces in degree j.
Let f - TR is smooth, or more generally, piece-wise smooth continuous function such that the sublevel sets Ozze (0 θ f(0)= c) are compact.
One filtered complex naturally associated with function f and such that the subcomplexes F,C. compute the homology of sublevel sets Oys, is the gradient (Morse) complex, see e.g. [Barannikov] (1994): Le Peutrec et al. (2033) and references therein. Without loss of generality the function j can be assumed smooth here, otherwise one always replace by its smoothing, By adding small perturbation such as a regularization term we can also assume that critical points of f are non-degenerate.
The generators of the gradient (Morse) complex correspond to the critical points of f. The differential is defined by counting gradient trajectories between critical points when their number is finite.
The canonical form of the gradient (Morse) complex describes a decomposition of the gradient flow associated with f into standard simple pieces.
4

---

Under review as a conference paper at ICLR 2020
Let p be a minimum, which is not global minimum. Then the generator corresponding p represents trivial homology class in the canonical form, since the homology class of its connected component is already represented by the global minimum. Then p is the lower generator of a two-dimensional complex with trivial homology in the canonical form. Lee is paired with an index-one saddle in the canonical form. The segment [f(), f(4) is then the canonical invariant (barcode) corresponding to the minimum p.
The full canonical form of the gradient (Morse) complex of all indexes is summary of global structure of the objective function's 's gradient flow.
The total number of different topological features in sublevel sets Sge of the objective function can be read immediately from the barcode. Namely the number of intersections of horizontal line at level e with segments in the index j barcode gives the number of independent topological features of dimension j in Oyge-
The description of the barcode of minima on manifold O with nonempty boundary de is modified in the following way. A connected component can be also born at a local minimum of restriction of f to the boundary f' lay. if grad is pointed inside manifold e. The merging of two connected components can also happen at an index-one critical point of f' lae. if grad is pointed inside O.
AN ALGORITHM FOR CALCULATION OF BARCODES OF MINIMA
In this section describe the developed algorithm for calculation of the canonical form invariants of local minima. The computation exploits the first definition of barcodes (see Section 2 which is based on the evolution on the connected components of the sublevel sets.
To analyse the surface of the given function f: θ -> IR, we first build its approximation by finite graph-based construction. To do this, we consider a random subset of points ( 0N θ and build graph with these points as vertices. The edges connect close points. Thus, for every vertex 0n by comparing f(,)) with f(0,)) for neighbors On of On, we are able understand the local topology near the point 6,. At the same time, connected componenets of sublevel sets Ojze (A E [0) S c) will naturally correspond connected components of the subgraph on point 8R such that f(0,) S e
Two technical details here are the choice of points 0₂ and the definition of closeness, i.c. when to connect points by an edge. In our experiments, we sample points uniformly from some rectangular box of interest. To add edges, we compute the oriented k-Nearest Neighbor Graph on the given points and then drop the orientation of edges. Thus, every node in the obtained graph has a degree in [k: 2k). In all our experiments we use k 2D, where D is the dimension of f's input.
Next we describe our algorithm, which computes barcodes approximation described above. The key idea is to monitor the evolution of the connected components of the sublevel sets of the graph, i.c. sets θ = {6,, (0x) S c} for increasing c.
function from its graph-based
For simplicity we assume that points 0 are ordered w.r.t. the value of function f. i.e. for < n' we have f(O,)) < f(,,)). In this case we are interested in the evolution of connected components throughout the process sequential adding of vertices 0g, 92..... fy graph, starting from an empty graph. We denote the subgraph on vertices f,...., 8n by θ, When we add new vertex 0x41 to 8n.. there are three possibilities for connected componenets evolve:
......,,,
1. Vertex 0x+1 has zero degree in 0n+1. This means that 0n+1 is local minimum of f and forms new connected component in the sublevel set.
2. All the neighbors of 0.+1 in Ox+1 belong one connected component in O,.-
3. All the neighbors of 0x41 in Ox+1 belong
connected components 81, 8K, C θn. Thus, all these components will form a single connected compo- nent O,+1
In fact we build a filtered simplicial complex, which approximates the function plot. Its degree zero chains spanned by the points 0,,, and degree one chains are spanned by the edges between close pairs of points.
5

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Barcodes of minima computation for function on graph.
Input Connected undirected graph = (V, E); function f on graph vertices.
Output: Barcodes: list of "birth"-" "drctt" pairs.
S S+ 0::
f min f(0) for 0 EV;
Barcodes + [[f*;,)]];
for 0 E V increasing order of (() do
S' - {s E S 30' E s such that (0, 8*) E E and f(0) > f(0");;
S' then
5 <- U {{0)):
else
f - min f(0') for 0' E L
#ES'
for S' do
+ min f(0) for 0' E 8; if f f then
Barcodes <- Barcodes U {()));
end
( s) ( "ES'
now
6 (8 \ (') (Snew):
end
return Barcodes
end
In the third case, according definition of Section the point 0. a 1-saddle point. Thus, one of the components sk swallows the rest. This is the component which has the lowest minimal value. For other components this gives their barcodes: for sy the birth-death pair is min -EEk f(
We summarize the procedure the following algorithm Note that we assume that the input graph is connected (otherwise the algorithm can be run separate connected components).
In the practical implementation of the algorithm, we precompute the values of function at all the vertices of G. Besides that, we use the disjoint set data structure to store and merge connected components during the process. We also keep and update the global minima each component. We did not include these tricks into the algorithm's 's pseuso-code in order to keep it simple.
The resulting complexity of the algorithm ONN log N) in the number of points. Here it is important to note that the procedure of graph creation may be itself time-consuning. In our case, the most time consuming operation is nearest neighbor search. our code, we used efficient HNSW Algorithm for aproximate NN search by Malkov and Yashunin (2018).
4 EXPERIMENTS
In this section we apply our algorithm to describing the surfaces of functions. In Subsection 4.] we apply the algorithm toy visual examples. In Subsection 4.2 apply the algorithm to analyse the loss surfaces of small neural networks.
4.1 ToY FUNCTIONS
In this subsection demonstrate the application of the algorithm to simple toy functions f RP R. For {1,2) we consider three following functions:
TTypicllly it merges two connected components of O.. However, due to noise and non-dense approximation of function by graph in high-dimensional spaces, it may happen that it merges more than two connected components.

---

The barcode of Under review as a conference paper at ICLR 2020
1.5
Local Minima
Local Minima
Local Minima
0.6
1.0
0.4
0.5
0.5
0.2
0.0
0.0
0.5
00.
-1.0
-1.0
-1.5
-1.5
(a) Polynomial Plot
(b) Hump Camel 3 Colorplot
(c) Hump Camel 6 Colorplot
2.0
0.05
0.10
0.6
1.0
0.15
0.4
0.20
0.0
Value at Local Min
Value at Local Min
-0.5
0.0
at 1-Saddle
0.0
Value at 1-Saddle
-1.0
(d) Barcode for Polynomial
(e) Barcode for Hump Camel
Barcode for Hump Camel 6
Figure 2: Plots (first row) and the coresponding barcodes (second row) for Polynomial of Degree 4. Hump Camel Hump Camel functions respectively.
1. Polynomial of single variable of degree 4 with 2 local minima (see Fig.
2a
01
f(0:) = 0 0
10
2. Camel function with 3 humps, i.c. 3 local minima (see Fig.
2b
f(0,, 0₂) (2 1.050 0 /6)0 + 0,02 + 02
(2)
3. Camel function with humps, i.c. 6 local minima (see Fig. 2c
f(0,, 02) (4 2. + 01 /)/ 0,02 (-4 46% )03
Function plots with their corresponding barcodes of minima are given in Figure the global minimum represented by the dashed half-line which goes to infinity.
2
4.2 TOPOLOGY OF NEURAL NETWORK LOSS FUNCTION
In this section we compute and analyse barcodes of small fully connected neural networks with up to three hidden layers.
For several architectures of the neural networks many results on the loss surface and its local minima are known (see e.g. Kawaguchi (2016) Gori and Tesi (1992) and references therein). Different geometrical and topological properties of loss surfaces
studied in Cao et al. (007): Yi et al.
(2019): Chaudhari et al. (2017); Dinh et al. (2017).
There ground truth on how should the best loss surface of neural network looks like. Neverthe- less, there exists many common opinions on this topic. First of all, from practical optimization point of view, the desired local (or global) minima should be easily reached via basic training methods such
7

---

Under review as a conference paper at ICLR 2020
Stochastic Gradient Descent, see Ruder (2016). Usually this requires more-or-less stable slopes of the surface to prevent instabilities such as gradient explosions or vamishing gradients. Secondly, the value of obtained minimum is typically desired to be close to global, i.c. attain smallest training error. Thirdly, from the generalization point of view, such minima are required to provide small loss on the testing set. Although in general it is assumed that the good local optimum is the that is flat, some recent development provide completely contrary arguments and examples, c.g. sharp minima that generalize well.
Besides the optimization of the weights for a given architecture, neural network training implies also choice of the architecture the network, as well the loss function be used for training. In fact, it is the choice of the architecture and the loss function that determines the shape of the loss surface. Thus, proper selection the network's 's architecture may simplify the loss surface and lead to potential improvements in the weight optimization procedure.
We have analyzed very tiny neural networks. However our method permits full exploration of the loss surface as opposed to stochastical exploration of higher-dimensional loss surfaces. Let us emphasize that even from practical point of view is important to understand first the behavior barcodes in simplest examples where all hyper-parametens optimization schemes can be easily turned off. For every analysed neural network the objective function is its mean squared error for predicting (randomly selected) function g [- T] - RR given by
g(z) 0.31 sin( (x) 0.72 sin(-2::) 0.21 cos(x) + 0.89 cos(
plus 12 re--rlllarizziion.... The error is computed for prediction on uniformly distributed inputs x {-x
100 k = 0,.,..., 1003.
The neural networks considered were fully connected one-hidden layer with 2, 3 and 4 neurons, two-hidden layers with 2x2, 3x2 and 3x3 neurons, and three hidden layers with 2x2x2 and 3x2x2 neurons. We have calculated the barcodes of the loss functions on the hyper-cubical sets @ which were chosen based on the typical range of parameters of minima. The results are as shown in Figure
3
We summarize our findings into two main observations:
1. the barcodes are located in tiny lower part of the range of values; typically the maximum value of the function was around 200, and the saddles paired with minima lie below 1;
2. with the increase of the neural network depth the barcodes descend lower.
For example the upper bounds of barcodes of one-layer (2) net are range [0.55, 0.65), two-layer (2 x 2) net in range [0.35, 0.45], and three-layer (2 x 2) net in range (0.1, 0.3).
CONCLUSION
In this work have introduced methodology for analysing the plots of functions, in particular, loss surfaces of neural networks. The methodology is based on computing topological invariants called canonical forms or barcodes.
To compute barcodes we used graph-based construction which approximates the function plot. Then we apply the algorithm we developed to compute the barcodes of minima on the graph. Our experimental results of computing barcodes for small neural networks lead to two principal observations.
First all barcodes sit in tiny lower part of the total function's range. Secondly, with increase of the depth of neural network the barcodes descend lower. From the practical point of view, this means that gradient descent optimization cannot stuck in high local minima, and it is also not difficult to get from one local minimum to another (with smaller value) during learning.
The method we developed has several further research directions. Although tested the method on small neural networks, is possible to apply to large-scale modern neural networks such as convolutional networks (i.e. ResNet, VGG, AlexNet. U-Net, see Alom et al. (2018)) for image- processing based tasks. However, in this case the graph-based approximation we use requires wise choice of representative graph vertices, which is hardcore in high-dimensional spaces (dense filling
8

---

Under review as a conference paper at ICLR 2020
0.7
0.5
0.5
0.3
0.0
0.9
(a) Barcodes for (2) net
(b) Barcodes for (3) net
Vasue at 1-Sante
Value Local Value 1-Geddie
Value Value 1-Gaddl
(c) Barcodes for (2 2) net
(d) Barcodes for (3 x 2) net
(c) Barcodes for (3 x 3) net
Value Local Viiue T-Swiiile
0.6
1-Saddiee
0.5
(I) Barcodes for (2 x x 2) net
(g) Barcodes for (3 x x 2) net
Figure 3: Barcodes of different neural network loss surfaces.
of area by points is computationally intractable). Another direction is to study the connections between the barcode of local minima and the generalization properties of given minimum and of neural network. There are clearly also connections, deserving further investigation, between the barcodes of minima and results concerning the rate of convergency during learning of neural networks.
REFERENCES
Md Zahangir Alom, Tarek M Taha, Christopher Yakopcic, Stefan Westberg, Paheding Sidike, Mst Shamima Nasrin. Brian Van Esesn, Abdul Awwal, and Vijayan K Asari. The his- tory began from alexnet: A comprehensive survey deep learning approaches. arXiv preprint arXiv:1803.01164 2018
S. Barannikov. Framed Morse complexes and its invariants. Adv. Soviet Math., 22:93-115, 1994.
U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. Phat persistent homology algorithms toolbox. In Mathematical Software ICMS 2014, pages 137-143. Springer, 2014.
James Bergstra and Yoshua Bengio. Random search for paprmmtrreetter optimization. Journal of Machine Learning Research, 13(Feb):281-300) 2012.
B. T.Fyy. J.Kim, F.Lecci, and M.riii.. Introduction to the R package TDA. preprint arxiv:1411.183 1411.1830. 2014.

---

Under review as a conference paper at ICLR 2020
Jiezhang Cao, Qingyao Wu, Yuguang Yan, Li Wang, and Mingkui Tan. On the flatness of loss surface for two-layered relu networks. In Asian Conference on Machine Learning, pages 545-560, 2017.
Chaudhari, A. Choromanska, Soatto, Y. LeCun, Baldassi, Borgs, J. Chayes, L. Sagun, and R. Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In International Conference on Learning Representations (ICIR), 2017.
Ch. Dellago, G. Bolhuis, and Ph. L. Geissler. Transition Path Sampling, pages 1-78. John Wiley Sons, Ltd, 2003. ISBN 978047123 1509. doi: 10. 10.1002/047123155000oo
L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference Machine Learning, Proceedings of Machine Learning Research, pages 1019-1028. PMLR, 2017.
Marco Gori and Alberto Tesi. On the problem of local minima in backpropagation. IEEE Transactions on Pattern Analysis & Machine Intelligence, 14(1):76-88 1992.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594, 2016.
D. Le Peutrec, F. Nier, and C. Viterbo. Precise Arrhenius law for p-forms: The Witten Lapla- cian and BarsnnBarayy complex. Annales Henri Poincaré, 14(3)5667-610, Apr 2013. ISSN 1424-0661. doi: 10. 10.1007/00023-012-009934 s0C023- 012-0033-12
http:: http:ss://di.ooo//......
Le Roux, S. Seyfaddini, and C. Viterbo. Barcodes and area- urea-preserving homeomorphisms, arXiv preprint IXX::1804009028 art. arXiv:1810.03133 Oct 2018.
H. Li, Zh. Xu, G. Taylor, Ch. Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances Neural Information Processing Systems, pages 6389-6399, 2018.
Bubenik M. K. Chung and P. T. Kim. Persistence diagrams of cortical surface data. Information Processing in Medical Imaging, 5636:386-397, 2009,
Yury A Malkov and Dmitry Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions pattern analysis and machine intelligence, 2018
A. R. Oganov and M. Valle. How to quantify energy landscapes of solids. The Journal of Chemical Physics, 130(10): 104504, 2009, doi: 10. 10.1066/1.0079326
Chi Seng Pun, Kelin Xia, and Si Xian Lee. Persistent- Persistent-homology based machine learning and its applications a survey. preprint arxiv: 1811.00252, 2018
Sebastian Ruder. An overview of gradient descent optimization algorithms. 1rXiv:1609.044477 2016.
arXiv preprint
Sousbie, C. Pichon, and H. Kawahara. The persistent cosmie web and its filamentary structure aÄş IL Illustrations. Monthly Notices of the Royal Astronomical Society, 414(1):384-40) 403, 06 2011. doi:
Mingyang Yi, Qi Meng. Wei Chen, Zhi-ming Ma, and Tie- Yae Liu. Positively scale-invariant flatness of relu neural networks. arXiv preprint arXiv: 1903.0223, 2019.
APPENDIX
5.1 PROOF OF THE THEOREM
The theorem is similar in spirit to the bringing quadratic form to sum of squares.
10

---

Under review as a conference paper at ICLR 2020
Proof. (Barannikov (1994) Let's choose basis in the vector spaces C, compatible with the filtration, so that each subspace F,C,, is the span el (n)
,..., e, (m)
Let dej has the required form for n j and S or n < j and I. Le. either deg") 0 or
De mll)
(n-1) where m(l) # m(l") for l * l'.
Let
dett1 Σ (1-1)
Let's move all the terms with (j-1) Deg. S i, from the right to the left side. We get
6/
a(e
(1)
Σ
9 (l(x))) = Σ
(
(1-1)
3x
k
If A3 = 0 for all k, then define
(ax(())
9
so that
0e(1) = 0,
and de," (2) has the required form for 1 i 1 and n = j. and for n < j and all
Otherwise let ko be the maximal &o with 3x # 0. Then
Mech
1 (awa))
(1-1) Bko
Σ ck (0 Br, 3ko # 0.
Goo
95$
k<ko
Define
21) (+1
c+11
(
Σ
2. ax(n)
/Bea
cko
20-11
Cko
11-1)
+ Σ ck (i-1))
Ba/BKo
25$
ko
Then
0e f+1
-011)
ko
and for j and < i 1, or <j and all 1, dei")
(n)
has the required form. If the complex has been
reduced to "canonical form" on subcomplex Bng then reduce similarly 0e and so on.
Uniqueness of the canonical form follows essentially from the uniqueness at each previous step. Let (1)
(0 J. {160 = =Ens "k Ork be two bases of C, for two different canonical forms. Assume that for all indexes < j and all and p = j and n S the canonical forms agree. Let 0a = am (j-1) and (b(1), = 81 1 with m > I.
(1)
It follows that
b ak
Σ
a
(j-1)
3
a*k
ASi+1
n
where 0:41 # 0. +0. Therefore
0aff)
Σ
a (1)-1) ///1111
Σoage
aa ar 0
ns!
On the other hand 0a am
1), with and 0a for l are either zero or some basis
elements (f-1)) different from a (1-1) This gives contradiction.
Similarly if ()) 0, then ++1
dali (
-
> Dak okk /4411
which again gives contradiction by the same arguments. Therefore the canonical forms must agree for p == and + also
11


Reviews:
[{"review_id": "SkxeCjmJqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces the notion of barcodes as a topological invariant of loss surfaces that encodes the \"depth\" of local minima by associating to each minimum the lowest index-one saddle. An algorithm is presented for the computation of barcodes, and some small-scale experiments are conducted. For very small neural networks, the barcodes are found to live at small loss values, and the authors argue that this suggests it may be hard to get stuck in a suboptimal local minimum.\n\nI believe the concept of barcodes will be new to most members of the ICLR community (at least it was to me), and I appreciate the authors' effort to convey the ideas through multiple definitions in Section 2. I wasn't able to fully appreciate the importance of Definition 3, and Definitions 1 and 2 were tough to digest owing to imprecise language, but I think I got the main point. I was also unable to fully comprehend the definitions of \"birth\" and \"death\" in this context. I'd strongly encourage the authors to improve the readability of this section so that non-experts can follow the story.\n\nIt seems like the main contribution is a new algorithm for computing barcodes of minima. I am unfamiliar with prior work in this direction, and I was also unable from the paper to infer what the main improvements were relative to the existing algorithms. I'd encourage the authors to state their explicit algorithmic improvements, and to demonstrate empirically that the new algorithm outperforms the prior ones in the expected ways.\n\nThe main experiments are on extremely tiny neural networks, presumably owing to computational restrictions. The authors state that \"it is possible to apply it to large-scale modern neural networks\", but it's not clear to me how that would work or what additional algorithmic improvements (if any) would need to be made in order to do so. I don't think that the results on tiny neural networks have much relevance to practice, so I think the empirical data presented in this paper will have very limited impact. If there were results for practical models, it would be a different story. So I'd encourage the authors to devote additional effort to scaling up the method for use on practical neural network architectures.\n\nOverall, I think there may be some really nice ideas in this paper that could help shape our understanding of neural network loss surfaces, but the current paper does not explore those ideas fully and does not convey them in a sufficiently clear manner. I hope to see an improved version of this paper at a future conference, but I cannot recommend acceptance of this version to ICLR.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklZP2GiFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work is focused on topological characterization of target surfaces of optimization objectives (i.e. loss functions) by computing so called barcodes, which are lists of pairs of local minima and their connected saddle points. The authors claim that the barcodes constitute a representation of target objectives that is invariant under homeomorphisms of input to the objectives. The authors present an algorithm for computing the barcodes from graph-based representation of a surface, and present barcodes computed on toy examples in numerical analysis. \n\nIn my opinion, the main contribution of the work i.e. creation of barcodes is based on a rather trivial idea. The concept of characterizing optimization objectives through pairs of local minima and one-index saddle points is straightforward given that one can (thoroughly if not exhaustively) compute them in a computationally feasible manner; this is however hardy the case in any realistic scenario. I therefore struggle to see how the idea can be practically significant. Maybe the authors can put more emphasis on the theoretical aspect of their work, which is about the invariance nature of barcodes. They can for instance demonstrate how one can exploit the invariance property of barcodes for parameter optimization. \n\nThe authors can consider application of their work to hyper-parameter optimization, which is usually low-dimensional and one can also compare with other approaches such as Gaussian processes or other Bayesian methodologies. \n\nIn numerical experiments, for the toy task solved using neural network I don't find it very surprising that the barcodes descend lower as the capacity of the network is increased. Can the authors further clarify why it is a significant finding for them?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BkeqaMZJ5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims to study the topology of loss surfaces of neural networks using tools from algebraic topology. From what I understood, the idea is to effectively (1) take a grid over the parameters of a function (say a parameters of a neural net), (2) evaluate the function at those points, (3) compute sub-levelset persistent homology and (4) study the resulting barcode (for 0/1-dim features) (i.e., the mentioned \"canonical form\" invariants). Some experiments are presented on extremely simple toy data.\n\nOverall, the paper is very hard to read, as different concepts and terminology appear all over the place without a precise definition (see comments below). Given the problems in the writing of the paper, my assessment is that this idea boils down to computing persistent homology of the sub-levelset filtration of the loss surface sampled at fixed parameter realizations. I do not think that this will be feasible to do, even for small-scale real-world neural networks, simply due to the difficulty of finding a suitable grid, let alone the vast number of function evaluations involved.\n\nThe paper is also unclear in many parts. A selection is listed below:\n\n(1) What do you mean by gradient flow? One can define a gradient flow in a linear space X and for a function F: X->R, e.g., as  a smooth curve R->X, such that x'(t) = -\\nabla F(x(t)); is that what is meant? \n\n(2) What do you mean by \"TDA package\"? There are many TDA packages these days (maybe the CRAN TDA package?)\n\n(3) \"It was tested in dimensions up to 16 ...\" What is meant by dimension here? The dimensionality of the parameter space?\n\n(4) The author's talk about the \"minima's barcode\" - I have no idea what is meant by that either; the barcode is the result of sub-levelset persistent homology of a function -> it's not associated to a minima.\n\n(5) Is Theorem 2.3. not just a restatement of a theorem from Barannikov '94? At least the proof in the appendix seems to be .\n\n(6) Right before Theorem 2.3., what does the notation F_sC_* mean? This needs to be introduced somewhere.\n\nFrom my perspective, the whole story revolves around how to compute persistence barcodes from the sub-levelset filtration of the loss surface, obtained from function values taken on a grid over the parameters. The paper devotes quite some time to the introduction of these concepts, but not in a very clear or understandable manner. The experiments are effectively done on toy data, which is fine, but the paper stops at that point. I do not buy the argument that \"it is possible to apply it [the method] to large-scale modern neural networks\". Without a clear strategy to extend this, or at least some preliminary \"larger\"-scale results, the paper does not meet the ICLR threshold. The more theoretical part is too convoluted and, from my perspective, just a restatement of earlier results.\n\n\n\n\n\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main concern raised by the reviewers is that the paper is difficult to read and potentially unclear. Therefore, the area chair read the paper, and also found it fairly dense and challenging to read. While there may be important discoveries in the paper, the paper in its current form makes it too difficult to read. Since four reviewers (including the AC) struggled to understand the paper, we believe the presentation of the paper should be improved. In particular, the claims of the paper should be better put into context.
Decision: Reject