The Loss Surface of Deep Linear Networks Viewed Through the Algebraic Geometry Lens.

By using the viewpoint of modern computational algebraic geometry, we explore properties of the optimization landscapes of deep linear neural network models. After providing clarification on the various definitions of "flat" minima, we show that the geometrically flat minima, which are merely artifacts of residual continuous symmetries of the deep linear networks, can be straightforwardly removed by a generalized L2-regularization. Then, we establish upper bounds on the number of isolated stationary points of these networks with the help of algebraic geometry. Combining these upper bounds with a method in numerical algebraic geometry, we find all stationary points for modest depth and matrix size. We demonstrate that, in the presence of the non-zero regularization, deep linear networks can indeed possess local minima which are not global minima. Finally, we show that even though the number of stationary points increases as the number of neurons (regularization parameters) increases (decreases), higher index saddles are surprisingly rare.

Loss surface of XOR artificial neural networks.

Training an artificial neural network involves an optimization process over the landscape defined by the cost (loss) as a function of the network parameters. We explore these landscapes using optimization tools developed for potential energy landscapes in molecular science. The number of local minima and transition states (saddle points of index one), as well as the ratio of transition states to minima, grow rapidly with the number of nodes in the network. There is also a strong dependence on the regularization parameter, with the landscape becoming more convex (fewer minima) as the regularization term increases. We demonstrate that in our formulation, stationary points for networks with N_{h} hidden nodes, including the minimal network required to fit the XOR data, are also stationary points for networks with N_{h}+1 hidden nodes when all the weights involving the additional node are zero. Hence, smaller networks trained on XOR data are embedded in the landscapes of larger networks. Our results clarify certain aspects of the classification and sensitivity (to perturbations in the input data) of minima and saddle points for this system, and may provide insight into dropout and network compression.

Fixed Points of Belief Propagation-An Analysis via Polynomial Homotopy Continuation.

Belief propagation (BP) is an iterative method to perform approximate inference on arbitrary graphical models. Whether BP converges and if the solution is a unique fixed point depends on both the structure and the parametrization of the model. To understand this dependence it is interesting to find all fixed points. In this work, we formulate a set of polynomial equations, the solutions of which correspond to BP fixed points. To solve such a nonlinear system we present the numerical polynomial-homotopy-continuation (NPHC) method. Experiments on binary Ising models and on error-correcting codes show how our method is capable of obtaining all BP fixed points. On Ising models with fixed parameters we show how the structure influences both the number of fixed points and the convergence properties. We further asses the accuracy of the marginals and weighted combinations thereof. Weighting marginals with their respective partition function increases the accuracy in all experiments. Contrary to the conjecture that uniqueness of BP fixed points implies convergence, we find graphs for which BP fails to converge, even though a unique fixed point exists. Moreover, we show that this fixed point gives a good approximation, and the NPHC method is able to obtain this fixed point.

Properties of kinetic transition networks for atomic clusters and glassy solids.

A database of minima and transition states corresponds to a network where the minima represent nodes and the transition states correspond to edges between the pairs of minima they connect via steepest-descent paths. Here we construct networks for small clusters bound by the Morse potential for a selection of physically relevant parameters, in two and three dimensions. The properties of these unweighted and undirected networks are analysed to examine two features: whether they are small-world, where the shortest path between nodes involves only a small number or edges; and whether they are scale-free, having a degree distribution that follows a power law. Small-world character is present, but statistical tests show that a power law is not a good fit, so the networks are not scale-free. These results for clusters are compared with the corresponding properties for the molecular and atomic structural glass formers ortho-terphenyl and binary Lennard-Jones. These glassy systems do not show small-world properties, suggesting that such behaviour is linked to the structure-seeking landscapes of the Morse clusters.

Energy landscapes for machine learning.

Machine learning techniques are being increasingly used as flexible non-linear fitting and prediction tools in the physical sciences. Fitting functions that exhibit multiple solutions as local minima can be analysed in terms of the corresponding machine learning landscape. Methods to explore and visualise molecular potential energy landscapes can be applied to these machine learning landscapes to gain new insight into the solution space involved in training and the nature of the corresponding predictions. In particular, we can define quantities analogous to molecular structure, thermodynamics, and kinetics, and relate these emergent properties to the structure of the underlying landscape. This Perspective aims to describe these analogies with examples from recent applications, and suggest avenues for new interdisciplinary research.

Kinetic Transition Networks for the Thomson Problem and Smale's Seventh Problem.

The Thomson problem, arrangement of identical charges on the surface of a sphere, has found many applications in physics, chemistry and biology. Here, we show that the energy landscape of the Thomson problem for N particles with N=132, 135, 138, 141, 144, 147, and 150 is single funneled, characteristic of a structure-seeking organization where the global minimum is easily accessible. Algorithmically, constructing starting points close to the global minimum of such a potential with spherical constraints is one of Smale's 18 unsolved problems in mathematics for the 21st century because it is important in the solution of univariate and bivariate random polynomial equations. By analyzing the kinetic transition networks, we show that a randomly chosen minimum is, in fact, always "close" to the global minimum in terms of the number of transition states that separate them, a characteristic of small world networks.

Algebraic geometrization of the Kuramoto model: Equilibria and stability analysis.

Finding equilibria of the finite size Kuramoto model amounts to solving a nonlinear system of equations, which is an important yet challenging problem. We translate this into an algebraic geometry problem and use numerical methods to find all of the equilibria for various choices of coupling constants K, natural frequencies, and on different graphs. We note that for even modest sizes (N ~ 10-20), the number of equilibria is already more than 100 000. We analyze the stability of each computed equilibrium as well as the configuration of angles. Our exploration of the equilibrium landscape leads to unexpected and possibly surprising results including non-monotonicity in the number of equilibria, a predictable pattern in the indices of equilibria, counter-examples to conjectures, multi-stable equilibrium landscapes, scenarios with only unstable equilibria, and multiple distinct extrema in the stable equilibrium distribution as a function of the number of cycles in the graph.

Exploring the potential energy landscape of the Thomson problem via Newton homotopies.

Locating the stationary points of a real-valued multivariate potential energy function is an important problem in many areas of science. This task generally amounts to solving simultaneous nonlinear systems of equations. While there are several numerical methods that can find many or all stationary points, they each exhibit characteristic problems. Moreover, traditional methods tend to perform poorly near degenerate stationary points with additional zero Hessian eigenvalues. We propose an efficient and robust implementation of the Newton homotopy method, which is capable of quickly sampling a large number of stationary points of a wide range of indices, as well as degenerate stationary points. We demonstrate our approach by applying it to the Thomson problem. We also briefly discuss a possible connection between the present work and Smale's 7th problem.

Energy landscape of the finite-size mean-field 2-spin spherical model and topology trivialization.

Motivated by the recently observed phenomenon of topology trivialization of potential energy landscapes (PELs) for several statistical mechanics models, we perform a numerical study of the finite-size 2-spin spherical model using both numerical polynomial homotopy continuation and a reformulation via non-Hermitian matrices. The continuation approach computes all of the complex stationary points of this model while the matrix approach computes the real stationary points. Using these methods, we compute the average number of stationary points while changing the topology of the PEL as well as the variance. Histograms of these stationary points are presented along with an analysis regarding the complex stationary points. This work connects topology trivialization to two different branches of mathematics: algebraic geometry and catastrophe theory, which is fertile ground for further interdisciplinary research.

Communication: Newton homotopies for sampling stationary points of potential energy landscapes.

One of the most challenging and frequently arising problems in many areas of science is to find solutions of a system of multivariate nonlinear equations. There are several numerical methods that can find many (or all if the system is small enough) solutions but they all exhibit characteristic problems. Moreover, traditional methods can break down if the system contains singular solutions. Here, we propose an efficient implementation of Newton homotopies, which can sample a large number of the stationary points of complicated many-body potentials. We demonstrate how the procedure works by applying it to the nearest-neighbor ϕ(4) model and atomic clusters.

Certification and the potential energy landscape.

Typically, there is no guarantee that a numerical approximation obtained using standard nonlinear equation solvers is indeed an actual solution, meaning that it lies in the quadratic convergence basin. Instead, it may lie only in the linear convergence basin, or even in a chaotic region, and hence not converge to the corresponding stationary point when further optimization is attempted. In some cases, these non-solutions could be misleading. Proving that a numerical approximation will quadratically converge to a stationary point is termed certification. In this report, we provide details of how Smale's α-theory can be used to certify numerically obtained stationary points of a potential energy landscape, providing a mathematical proof that the numerical approximation does indeed correspond to an actual stationary point, independent of the precision employed.

An inversion-relaxation approach for sampling stationary points of spin model Hamiltonians.

Sampling the stationary points of a complicated potential energy landscape is a challenging problem. Here, we introduce a sampling method based on relaxation from stationary points of the highest index of the Hessian matrix. We illustrate how this approach can find all the stationary points for potentials or Hamiltonians bounded from above, which includes a large class of important spin models, and we show that it is far more efficient than previous methods. For potentials unbounded from above, the relaxation part of the method is still efficient in finding minima and transition states, which are usually the primary focus of attention for atomistic systems.

Potential energy landscapes for the 2D XY model: minima, transition states, and pathways.

We describe a numerical study of the potential energy landscape for the two-dimensional XY model (with no disorder), considering up to 100 spins and central processing unit and graphics processing unit implementations of local optimization, focusing on minima and saddles of index one (transition states). We examine both periodic and anti-periodic boundary conditions, and show that the number of stationary points located increases exponentially with increasing lattice size. The corresponding disconnectivity graphs exhibit funneled landscapes; the global minima are readily located because they exhibit relatively large basins of attraction compared to the higher energy minima as the lattice size increases.

Energy landscape of the finite-size spherical three-spin glass model.

We study the three-spin spherical model with mean-field interactions and Gaussian random couplings. For moderate system sizes of up to 20 spins, we obtain all stationary points of the energy landscape by means of the numerical polynomial homotopy continuation method. On the basis of these stationary points, we analyze the complexity and other quantities related to the glass transition of the model and compare these finite-system quantities to their exact counterparts in the thermodynamic limit.

Communication: Certifying the potential energy landscape.

It is highly desirable for numerical approximations to stationary points for a potential energy landscape to lie in the corresponding quadratic convergence basin. However, it is possible that an approximation may lie only in the linear convergence basin, or even in a chaotic region, and hence not converge to the actual stationary point when further optimization is attempted. Proving that a numerical approximation will quadratically converge to the associated stationary point is termed certification. Here, we apply Smale's α-theory to stationary points, providing a certification serving as a mathematical proof that the numerical approximation does indeed correspond to an actual stationary point, independent of the precision employed. As a practical example, employing recently developed certification algorithms, we show how the α-theory can be used to certify all the known minima and transition states of Lennard-Jones LJ(N) atomic clusters for N = 7, ..., 14.

Energy-landscape analysis of the two-dimensional nearest-neighbor φ4 model.

The stationary points of the potential energy function of the φ4 model on a two-dimensional square lattice with nearest-neighbor interactions are studied by means of two numerical methods: a numerical homotopy continuation method and a globally convergent Newton-Raphson method. We analyze the properties of the stationary points, in particular with respect to a number of quantities that have been conjectured to display signatures of the thermodynamic phase transition of the model. Although no such signatures are found for the nearest-neighbor φ4 model, our study illustrates the strengths and weaknesses of the numerical methods employed.

Phase transitions detached from stationary points of the energy landscape.

The stationary points of the potential energy function V are studied for the ϕ4 model on a two-dimensional square lattice with nearest-neighbor interactions. On the basis of analytical and numerical results, we explore the relation of stationary points to the occurrence of thermodynamic phase transitions. We find that the phase transition potential energy of the ϕ4 model does in general not coincide with the potential energy of any of the stationary points of V. This disproves earlier, allegedly rigorous, claims in the literature on necessary conditions for the existence of phase transitions. Moreover, we find evidence that the indices of stationary points scale extensively with the system size, and therefore the index density can be used to characterize features of the energy landscape in the infinite-system limit. We conclude that the finite-system stationary points provide one possible mechanism of how a phase transition can arise, but not the only one.

Finding all the stationary points of a potential-energy landscape via numerical polynomial-homotopy-continuation method.

The stationary points (SPs) of a potential-energy landscape play a crucial role in understanding many of the physical or chemical properties of a given system. However, unless they are found analytically, no efficient method is available to obtain all the SPs of a given potential. We present a method, called the numerical polynomial-homotopy-continuation method, which numerically finds all the SPs, and is embarrassingly parallelizable. The method requires the nonlinearity of the potential to be polynomial-like, which is the case for almost all of the potentials arising in physical and chemical systems. We also certify the numerically obtained SPs so that they are independent of the numerical tolerance used during the computation. It is then straightforward to separate out the local and global minima. As a first application, we take the XY model with power-law interaction, which is shown to have a polynomial-like nonlinearity, and we apply the method.