Search

We analyze the problem of storing random pattern-label associations using two classes of continuous non-convex weights models, namely the perceptron with negative margin and an infinite-width two-layer neural network with non-overlapping receptive fields and generic activation function. Using a full-RSB ansatz we compute the exact value of the SAT/UNSAT transition. Furthermore, in the case of the negative perceptron we show that the overlap distribution of typical states displays an overlap gap (a disconnected support) in certain regions of the phase diagram defined by the value of the margin and the density of patterns to be stored. This implies that some recent theorems that ensure convergence of Approximate Message Passing (AMP) based algorithms to capacity are not applicable. Finally, we show that Gradient Descent is not able to reach the maximal capacity, irrespectively of the presence of an overlap gap for typical states. This finding, similarly to what occurs in binary weight models, suggests that gradient-based algorithms are biased towards highly atypical states, whose inaccessibility determines the algorithmic threshold., Comment: 39 pages, 12 figures

How neurons integrate the myriad synaptic inputs scattered across their dendrites is a fundamental question in neuroscience. Multiple neurophysiological experiments have shown that dendritic non-linearities can have a strong influence on synaptic input integration. These non-linearities have motivated mathematical descriptions of single neuron as a two-layer computational units, which have been shown to increase substantially the computational abilities of neurons, compared to linear dendritic integration. However, current analytical studies are restricted to neurons with unconstrained synaptic weights and unplausible dendritic non-linearities. Here, we introduce a two-layer model with sign-constrained synaptic weights and a biologically plausible form of dendritic non-linearity, and investigate its properties using both statistical physics methods and numerical simulations. We find that the dendritic non-linearity enhances both the number of possible learned input-output associations and the learning velocity. We characterize how capacity and learning speed depend on the implemented non-linearity and the levels of dendritic and somatic inhibition. We calculate analytically the distribution of synaptic weights in networks close to maximal capacity, and find that a large fraction of zero-weight ('silent' or 'potential') synapses naturally emerge in neurons with sign-constrained synapses, as a consequence of non-linear dendritic integration. Non-linearly induced sparsity comes with a second central advantage for neuronal information processing, i.e. input and synaptic noise robustness. We test our model on standard real-world benchmark datasets and observe empirically that the non-linearity provides an enhancement in generalization performance, showing that it enables to capture more complex input/output relations., Comment: 29 pages, 10 figures

It has been recently shown that a learning transition happens when a Hopfield Network stores examples generated as superpositions of random features, where new attractors corresponding to such features appear in the model. In this work we reveal that the network also develops attractors corresponding to previously unseen examples generated with the same set of features. We explain this surprising behaviour in terms of spurious states of the learned features: we argue that, increasing the number of stored examples beyond the learning transition, the model also learns to mix the features to represent both stored and previously unseen examples. We support this claim with the computation of the phase diagram of the model.

We discuss numerical aspects of instantons in two- and three-dimensional $\phi^4$ theories with an internal $O(N)$ symmetry group, the so-called $N$-vector model. Combining asymptotic transseries expansions for large argument with convergence acceleration techniques, we obtain high-precision values for certain integrals of the instanton that naturally occur in loop corrections around instanton configurations. Knowledge of these numerical properties are necessary in order to evaluate corrections to the large-order factorial growth of perturbation theory in $\phi^4$ theories. The results contribute to the understanding of the mathematical structures underlying the instanton configurations., Comment: 11 pages; RevTeX

Recent works demonstrated the existence of a double-descent phenomenon for the generalization error of neural networks, where highly overparameterized models escape overfitting and achieve good test performance, at odds with the standard bias-variance trade-off described by statistical learning theory. In the present work, we explore a link between this phenomenon and the increase of complexity and sensitivity of the function represented by neural networks. In particular, we study the Boolean mean dimension (BMD), a metric developed in the context of Boolean function analysis. Focusing on a simple teacher-student setting for the random feature model, we derive a theoretical analysis based on the replica method that yields an interpretable expression for the BMD, in the high dimensional regime where the number of data points, the number of features, and the input size grow to infinity. We find that, as the degree of overparameterization of the network is increased, the BMD reaches an evident peak at the interpolation threshold, in correspondence with the generalization error peak, and then slowly approaches a low asymptotic value. The same phenomenology is then traced in numerical experiments with different model classes and training setups. Moreover, we find empirically that adversarially initialized models tend to show higher BMD values, and that models that are more robust to adversarial attacks exhibit a lower BMD., Comment: 37 pages, 31 figures

The Indy Autonomous Challenge (IAC) brought together for the first time in history nine autonomous racing teams competing at unprecedented speed and in head-to-head scenario, using independently developed software on open-wheel racecars. This paper presents the complete software architecture used by team TII EuroRacing (TII-ER), covering all the modules needed to avoid static obstacles, perform active overtakes and reach speeds above 75 m/s (270 km/h). In addition to the most common modules related to perception, planning, and control, we discuss the approaches used for vehicle dynamics modelling, simulation, telemetry, and safety. Overall results and the performance of each module are described, as well as the lessons learned during the first two events of the competition on oval tracks, where the team placed respectively second and third., Comment: Preprint: Accepted to Field Robotics "Opportunities and Challenges with Autonomous Racing" Special Issue

In these pedagogic notes I review the statistical mechanics approach to neural networks, focusing on the paradigmatic example of the perceptron architecture with binary an continuous weights, in the classification setting. I will review the Gardner's approach based on replica method and the derivation of the SAT/UNSAT transition in the storage setting. Then, I discuss some recent works that unveiled how the zero training error configurations are geometrically arranged, and how this arrangement changes as the size of the training set increases. I also illustrate how different regions of solution space can be explored analytically and how the landscape in the vicinity of a solution can be characterized. I give evidence how, in binary weight models, algorithmic hardness is a consequence of the disappearance of a clustered region of solutions that extends to very large distances. Finally, I demonstrate how the study of linear mode connectivity between solutions can give insights into the average shape of the solution manifold., Comment: 22 pages, 9 figures, based on a set of lectures done at the "School of the Italian Society of Statistical Physics", IMT, Lucca

Optical microcavities are often proposed as platforms for spectroscopy in the single- and few-photon regime due to strong light-matter coupling. For classical-light spectroscopies, an empty microcavity simply acts as an optical filter. However, we find that in the single- or few-photon regime treating the empty microcavity as an optical filter does not capture the full effect on the quantum state of the transmitted photons. Focusing on the case of entangled photon-pair spectroscopy, we consider how the propagation of one photon through an optical microcavity changes the joint spectrum of a frequency-entangled photon pair. Using the input-output treatment of a Dicke model, we find that propagation through a strongly coupled microcavity above a certain coupling threshold enhances the entanglement entropy between the signal and idler photons. These results show that optical microcavities are not neutral platforms for quantum-light spectroscopies and their effects must be carefully considered when using change in entanglement entropy as an observable.

Empirical studies on the landscape of neural networks have shown that low-energy configurations are often found in complex connected structures, where zero-energy paths between pairs of distant solutions can be constructed. Here we consider the spherical negative perceptron, a prototypical non-convex neural network model framed as a continuous constraint satisfaction problem. We introduce a general analytical method for computing energy barriers in the simplex with vertex configurations sampled from the equilibrium. We find that in the over-parameterized regime the solution manifold displays simple connectivity properties. There exists a large geodesically convex component that is attractive for a wide range of optimization dynamics. Inside this region we identify a subset of atypical high-margin solutions that are geodesically connected with most other solutions, giving rise to a star-shaped geometry. We analytically characterize the organization of the connected space of solutions and show numerical evidence of a transition, at larger constraint densities, where the aforementioned simple geodesic connectivity breaks down., Comment: 27 pages, 16 figures, comments are welcome

We study the binary and continuous negative-margin perceptrons as simple non-convex neural network models learning random rules and associations. We analyze the geometry of the landscape of solutions in both models and find important similarities and differences. Both models exhibit subdominant minimizers which are extremely flat and wide. These minimizers coexist with a background of dominant solutions which are composed by an exponential number of algorithmically inaccessible small clusters for the binary case (the frozen 1-RSB phase) or a hierarchical structure of clusters of different sizes for the spherical case (the full RSB phase). In both cases, when a certain threshold in constraint density is crossed, the local entropy of the wide flat minima becomes non-monotonic, indicating a break-up of the space of robust solutions into disconnected components. This has a strong impact on the behavior of algorithms in binary models, which cannot access the remaining isolated clusters. For the spherical case the behaviour is different, since even beyond the disappearance of the wide flat minima the remaining solutions are shown to always be surrounded by a large number of other solutions at any distance, up to capacity. Indeed, we exhibit numerical evidence that algorithms seem to find solutions up to the SAT/UNSAT transition, that we compute here using an 1RSB approximation. For both models, the generalization performance as a learning device is shown to be greatly improved by the existence of wide flat minimizers even when trained in the highly underconstrained regime of very negative margins., Comment: 34 pages, 13 figures

The Hopfield model is a paradigmatic model of neural networks that has been analyzed for many decades in the statistical physics, neuroscience, and machine learning communities. Inspired by the manifold hypothesis in machine learning, we propose and investigate a generalization of the standard setting that we name Random-Features Hopfield Model. Here $P$ binary patterns of length $N$ are generated by applying to Gaussian vectors sampled in a latent space of dimension $D$ a random projection followed by a non-linearity. Using the replica method from statistical physics, we derive the phase diagram of the model in the limit $P,N,D\to\infty$ with fixed ratios $\alpha=P/N$ and $\alpha_D=D/N$. Besides the usual retrieval phase, where the patterns can be dynamically recovered from some initial corruption, we uncover a new phase where the features characterizing the projection can be recovered instead. We call this phenomena the learning phase transition, as the features are not explicitly given to the model but rather are inferred from the patterns in an unsupervised fashion.

Recently, the large-order behavior of correlation functions of the $O(N)$-anharmonic oscillator has been analyzed by us in [L. T. Giorgini et el., Phys. Rev. D 101, 125001 (2020)]. Two-loop corrections about the instanton configurations were obtained for the partition function, and the two-point and four-point functions, and the derivative of the two-point function at zero momentum transfer. Here, we attempt to verify the obtained analytic results against numerical calculations of higher-order coefficients for the $O(1)$, $O(2)$, and $O(3)$ oscillators, and demonstrate the drastic improvement of the agreement of the large-order asymptotic estimates and perturbation theory upon the inclusion of the two-loop corrections to the large-order behavior., Comment: 18 pages, 4 figures

Current deep neural networks are highly overparameterized (up to billions of connection weights) and nonlinear. Yet they can fit data almost perfectly through variants of gradient descent algorithms and achieve unexpected levels of prediction accuracy without overfitting. These are formidable results that defy predictions of statistical learning and pose conceptual challenges for non-convex optimization. In this paper, we use methods from statistical physics of disordered systems to analytically study the computational fallout of overparameterization in non-convex binary neural network models, trained on data generated from a structurally simpler but "hidden" network. As the number of connection weights increases, we follow the changes of the geometrical structure of different minima of the error loss function and relate them to learning and generalization performance. A first transition happens at the so-called interpolation point, when solutions begin to exist (perfect fitting becomes possible). This transition reflects the properties of typical solutions, which however are in sharp minima and hard to sample. After a gap, a second transition occurs, with the discontinuous appearance of a different kind of "atypical" structures: wide regions of the weight space that are particularly solution-dense and have good generalization properties. The two kinds of solutions coexist, with the typical ones being exponentially more numerous, but empirically we find that efficient algorithms sample the atypical, rare ones. This suggests that the atypical phase transition is the relevant one for learning. The results of numerical tests with realistic networks on observables suggested by the theory are consistent with this scenario., Comment: 28 pages, 14 figures

The success of deep learning has revealed the application potential of neural networks across the sciences and opened up fundamental theoretical problems. In particular, the fact that learning algorithms based on simple variants of gradient methods are able to find near-optimal minima of highly nonconvex loss functions is an unexpected feature of neural networks. Moreover, such algorithms are able to fit the data even in the presence of noise, and yet they have excellent predictive capabilities. Several empirical results have shown a reproducible correlation between the so-called flatness of the minima achieved by the algorithms and the generalization performance. At the same time, statistical physics results have shown that in nonconvex networks a multitude of narrow minima may coexist with a much smaller number of wide flat minima, which generalize well. Here we show that wide flat minima arise as complex extensive structures, from the coalescence of minima around "high-margin" (i.e., locally robust) configurations. Despite being exponentially rare compared to zero-margin ones, high-margin minima tend to concentrate in particular regions. These minima are in turn surrounded by other solutions of smaller and smaller margin, leading to dense regions of solutions over long distances. Our analysis also provides an alternative analytical method for estimating when flat minima appear and when algorithms begin to find solutions, as the number of model parameters varies., Comment: 15 pages, 8 figures

In molecular photochemistry, the non-equilibrium character and subsequent ultrafast relaxation dynamics of photoexcitations near the Franck-Condon region limit the control of their chemical reactivity. We address how to harness strong light-matter coupling in optical microcavities to isolate and preferentially select specific reaction pathways out of the myriad of possibilities present in large-scale complex systems. Using Fermi's Golden Rule and realistic molecular parameters, we estimate the extent to which molecular configurations can be "locked" into non-equilibrium excited state configurations for timescales well beyond their natural relaxation times. For upper polaritons--which are largely excitonic in character, molecular systems can be locked into their ground state geometries for tens to thousands of picoseconds and varies with the strength of the exciton/phonon coupling (Huang-Rhys parameter). On the other hand, relaxed LP lifetimes are nearly uniformly distributed between 2.1-2.4\,ps and are nearly independent of the Huang-Rhys parameter., Comment: Submitted perspective artcle

Frenkel excitons, the primary photoexcitations in organic semiconductors that are unequivocally responsible for the optical properties of this materials class, are predicted to form \emph{bound} exciton pairs, i.e., biexcitons. These are key intermediates, ubiquitous in many relevant photophysical processes; for example, they determine the exciton bimolecular annihilation dynamics in such systems. Deciphering the details of biexciton correlations is, thus, of utmost importance to understand the optical processes in these semiconductors. To date, however, due to their spectral ambiguity, there has been only scant direct evidence of bound biexcitons, limiting the insights that can be gained. Moreover, a quantum-mechanical basis describing biexciton correlation/stability has so far been lacking. By employing nonlinear coherent spectroscopy, we identify here bound biexcitons in a model polymeric semiconductor. We find, unexpectedly, that excitons with \emph{interchain} vibronic dispersion reveal \emph{intrachain} biexciton correlations and vice versa. Moreover, using a Frenkel exciton model, we can relate the biexciton binding energy to molecular parameters quantified by quantum chemistry, including the magnitude and sign of the exciton-exciton interaction the inter-site hopping energies. Therefore, our work promises a window towards general insights into the many-body electronic structure in polymeric semiconductors and beyond; e.g., other excitonic systems such as organic semiconductor crystals, molecular aggregates, photosynthetic light-harvesting complexes, or DNA., Comment: 4 figures and Supplementary Materials

We analyze the connection between minimizers with good generalizing properties and high local entropy regions of a threshold-linear classifier in Gaussian mixtures with the mean squared error loss function. We show that there exist configurations that achieve the Bayes-optimal generalization error, even in the case of unbalanced clusters. We explore analytically the error-counting loss landscape in the vicinity of a Bayes-optimal solution, and show that the closer we get to such configurations, the higher the local entropy, implying that the Bayes-optimal solution lays inside a wide flat region. We also consider the algorithmically relevant case of targeting wide flat minima of the (differentiable) mean squared error loss. Our analytical and numerical results show not only that in the balanced case the dependence on the norm of the weights is mild, but also, in the unbalanced case, that the performances can be improved., Comment: 19 pages, 4 figures. arXiv admin note: text overlap with arXiv:2006.07897

For a long time, the predictive limits of perturbative quantum field theory have been limited by our inability to carry out loop calculations to arbitrarily high order, which become increasingly complex as the order of perturbation theory is increased. This problem is exacerbated by the fact that perturbation series derived from loop diagram (Feynman diagram) calculations represent asymptotic (divergent) series which limits the predictive power of perturbative quantum field theory. Here, we discuss an ansatz which could overcome these limits, based on the observations that (i) for many phenomenologically relevant field theories, one can derive dispersion relations which relate the large-order growth (the asymptotic limit of "infinite loop order") with the imaginary part of arbitrary correlation functions, for negative coupling ("unstable vacuum"), and (ii) one can analyze the imaginary part for negative coupling in terms of classical field configurations (instantons). Unfortunately, the perturbation theory around instantons, which could lead to much more accurate predictions for the large-order behavior of Feynman diagrams, poses a number of technical as well as computational difficulties. Here, we study, to further the above mentioned ansatz, correlation functions in a one-dimensional (1D) field theory with a quartic self-interaction and an O(N) internal symmetry group, otherwise known as the 1D N-vector model. Our focus is on corrections to the large-order growth of perturbative coefficients, i.e., the limit of a large number of loops in the Feynman diagram expansion. We evaluate, in momentum space, the two-loop corrections for the two-point correlation function, and its derivative with respect to the momentum, as well as the two-point correlation function with a wigglet insertion. Also, we study the four-point function., Comment: 27 pages; RevTeX

Rectified Linear Units (ReLU) have become the main model for the neural units in current deep learning systems. This choice has been originally suggested as a way to compensate for the so called vanishing gradient problem which can undercut stochastic gradient descent (SGD) learning in networks composed of multiple layers. Here we provide analytical results on the effects of ReLUs on the capacity and on the geometrical landscape of the solution space in two-layer neural networks with either binary or real-valued weights. We study the problem of storing an extensive number of random patterns and find that, quite unexpectedly, the capacity of the network remains finite as the number of neurons in the hidden layer increases, at odds with the case of threshold units in which the capacity diverges. Possibly more important, a large deviation approach allows us to find that the geometrical landscape of the solution space has a peculiar structure: while the majority of solutions are close in distance but still isolated, there exist rare regions of solutions which are much more dense than the similar ones in the case of threshold units. These solutions are robust to perturbations of the weights and can tolerate large perturbations of the inputs. The analytical results are corroborated by numerical findings., Comment: 11 pages, 3 figures

Using the replica approach and the cavity method, we study the fluctuations of the optimal cost in the random-link matching problem. By means of replica arguments, we derive the exact expression of its variance. Moreover, we study the large deviation function, deriving its expression in two different ways, namely using both the replica method and the cavity method., Comment: 9 pages, 3 figures

This PhD thesis is organized as follows. In the first two chapters I will review some basic notions of statistical physics of disordered systems, such as random graph theory, the mean-field approximation, spin glasses and combinatorial optimization. The replica method will also be introduced and applied to the Sherrington-Kirkpatrick model, one of the simplest mean-field models of spin-glasses. The second part of the thesis deals with mean-field combinatorial optimization problems. The attention will be focused on the study of finite-size corrections of random integer matching problems (chapter 3) and fractional ones (chapter 4). In chapter 5 I will discuss a very general relation connecting multi-overlaps and the moments of the cavity magnetization distribution. In the third part we consider random Euclidean optimization problems. I will start solving the traveling-salesman-problem (TSP) in one dimension both in its bipartite and monopartite version (chapter 6). In chapter 7 I will discuss the possible optimal solutions of the 2-factor problem. In chapter 8 I will solve the bipartite TSP in two dimensions, in the limit of large number of points. Chapter 9 contains some conclusions., Comment: 211 pages

The traveling-salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity in its statement and the difficulty in its solution. We study the traveling salesman problem when the positions of the cities are chosen at random in the unit interval and the cost associated to the travel between two cities is their distance elevated to an arbitrary power $p\in \mathbb{R}$. We characterize the optimal cycle and compute the average optimal cost for every number of cities when the measure used to choose the position of the cities is flat and asymptotically for large number of cities in the other cases. We also show that the optimal cost is a self-averaging quantity, and we test our analytical results with extensive simulations., Comment: 14 pages, 8 figures

We consider a set of Euclidean optimization problems in one dimension, where the cost function associated to the couple of points $x$ and $y$ is the Euclidean distance between them to an arbitrary power $p\ge1$, and the points are chosen at random with flat measure. We derive the exact average cost for the random assignment problem, for any number of points, by using Selberg's integrals. Some variants of these integrals allows to derive also the exact average cost for the bipartite travelling salesman problem., Comment: 9 pages, 2 figures

We show that the average cost for the traveling-salesman problem in two dimensions, which is the archetypal problem in combinatorial optimization, in the bipartite case, is simply related to the average cost of the assignment problem with the same Euclidean, increasing, convex weights. In this way we extend a result already known in one dimension where exact solutions are avalaible. The recently determined average cost for the assignment when the cost function is the square of the distance between the points provides therefore an exact prediction $$\overline{E_N} = \frac{1}{\pi}\, \log N$$ for large number of points $2N$. As a byproduct of our analysis also the loop covering problem has the same optimal average cost. We also explain why this result cannot be extended at higher dimensions. We numerically check the exact predictions., Comment: 5 pages, 3 figures

In this work we consider the problem of finding the minimum-weight loop cover of an undirected graph. This combinatorial optimization problem is called 2-matching and can be seen as a relaxation of the traveling salesman problem since one does not have the unique loop condition. We consider this problem both on the complete bipartite and complete graph embedded in a one dimensional interval, the weights being chosen as a convex function of the Euclidean distance between each couple of points. Randomness is introduced throwing independently and uniformly the points in space. We derive the average optimal cost in the limit of large number of points. We prove that the possible solutions are characterized by the presence of "shoelace" loops containing 2 or 3 points of each type in the complete bipartite case, and 3, 4 or 5 points in the complete one. This gives rise to an exponential number of possible solutions scaling as p^N , where p is the plastic constant. This is at variance to what happens in the previously studied one-dimensional models such as the matching and the traveling salesman problem, where for every instance of the disorder there is only one possible solution., Comment: 19 pages, 5 figures

We consider two formulations of the random-link fractional matching problem, a relaxed version of the more standard random-link (integer) matching problem. In one formulation, we allow each node to be linked to itself in the optimal matching configuration. In the other one, on the contrary, such a link is forbidden. Both problems have the same asymptotic average optimal cost of the random-link matching problem on the complete graph. Using a replica approach and previous results of W\"{a}stlund [Acta Mathematica 204, 91-150 (2010)], we analytically derive the finite-size corrections to the asymptotic optimal cost. We compare our results with numerical simulations and we discuss the main differences between random-link fractional matching problems and the random-link matching problem., Comment: 24 pages, 3 figures