Search

We develop a framework for analyzing the training and learning rate dynamics on a large class of high-dimensional optimization problems, which we call the high line, trained using one-pass stochastic gradient descent (SGD) with adaptive learning rates. We give exact expressions for the risk and learning rate curves in terms of a deterministic solution to a system of ODEs. We then investigate in detail two adaptive learning rates -- an idealized exact line search and AdaGrad-Norm -- on the least squares problem. When the data covariance matrix has strictly positive eigenvalues, this idealized exact line search strategy can exhibit arbitrarily slower convergence when compared to the optimal fixed learning rate with SGD. Moreover we exactly characterize the limiting learning rate (as time goes to infinity) for line search in the setting where the data covariance has only two distinct eigenvalues. For noiseless targets, we further demonstrate that the AdaGrad-Norm learning rate converges to a deterministic constant inversely proportional to the average eigenvalue of the data covariance matrix, and identify a phase transition when the covariance density of eigenvalues follows a power law distribution.

A key property of deep neural networks (DNNs) is their ability to learn new features during training. This intriguing aspect of deep learning stands out most clearly in recently reported Grokking phenomena. While mainly reflected as a sudden increase in test accuracy, Grokking is also believed to be a beyond lazy-learning/Gaussian Process (GP) phenomenon involving feature learning. Here we apply a recent development in the theory of feature learning, the adaptive kernel approach, to two teacher-student models with cubic-polynomial and modular addition teachers. We provide analytical predictions on feature learning and Grokking properties of these models and demonstrate a mapping between Grokking and the theory of phase transitions. We show that after Grokking, the state of the DNN is analogous to the mixed phase following a first-order phase transition. In this mixed phase, the DNN generates useful internal representations of the teacher that are sharply distinct from those before the transition.

We analyze the dynamics of streaming stochastic gradient descent (SGD) in the high-dimensional limit when applied to generalized linear models and multi-index models (e.g. logistic regression, phase retrieval) with general data-covariance. In particular, we demonstrate a deterministic equivalent of SGD in the form of a system of ordinary differential equations that describes a wide class of statistics, such as the risk and other measures of sub-optimality. This equivalence holds with overwhelming probability when the model parameter count grows proportionally to the number of data. This framework allows us to obtain learning rate thresholds for stability of SGD as well as convergence guarantees. In addition to the deterministic equivalent, we introduce an SDE with a simplified diffusion coefficient (homogenized SGD) which allows us to analyze the dynamics of general statistics of SGD iterates. Finally, we illustrate this theory on some standard examples and show numerical simulations which give an excellent match to the theory., Comment: Preliminary version

State-of-the-art neural networks require extreme computational power to train. It is therefore natural to wonder whether they are optimally trained. Here we apply a recent advancement in stochastic thermodynamics which allows bounding the speed at which one can go from the initial weight distribution to the final distribution of the fully trained network, based on the ratio of their Wasserstein-2 distance and the entropy production rate of the dynamical process connecting them. Considering both gradient-flow and Langevin training dynamics, we provide analytical expressions for these speed limits for linear and linearizable neural networks e.g. Neural Tangent Kernel (NTK). Remarkably, given some plausible scaling assumptions on the NTK spectra and spectral decomposition of the labels -- learning is optimal in a scaling sense. Our results are consistent with small-scale experiments with Convolutional Neural Networks (CNNs) and Fully Connected Neural networks (FCNs) on CIFAR-10, showing a short highly non-optimal regime followed by a longer optimal regime.

Physically informed neural networks (PINNs) are a promising emerging method for solving differential equations. As in many other deep learning approaches, the choice of PINN design and training protocol requires careful craftsmanship. Here, we suggest a comprehensive theoretical framework that sheds light on this important problem. Leveraging an equivalence between infinitely over-parameterized neural networks and Gaussian process regression (GPR), we derive an integro-differential equation that governs PINN prediction in the large data-set limit -- the neurally-informed equation. This equation augments the original one by a kernel term reflecting architecture choices and allows quantifying implicit bias induced by the network via a spectral decomposition of the source term in the original differential equation.

Deep neural networks (DNNs) are powerful tools for compressing and distilling information. Their scale and complexity, often involving billions of inter-dependent parameters, render direct microscopic analysis difficult. Under such circumstances, a common strategy is to identify slow variables that average the erratic behavior of the fast microscopic variables. Here, we identify a similar separation of scales occurring in fully trained finitely over-parameterized deep convolutional neural networks (CNNs) and fully connected networks (FCNs). Specifically, we show that DNN layers couple only through the second moment (kernels) of their activations and pre-activations. Moreover, the latter fluctuates in a nearly Gaussian manner. For infinite width DNNs, these kernels are inert, while for finite ones they adapt to the data and yield a tractable data-aware Gaussian Process. The resulting thermodynamic theory of deep learning yields accurate predictions in various settings. In addition, it provides new ways of analyzing and understanding DNNs in general.

We study in this paper lower bounds for the generalization error of models derived from multi-layer neural networks, in the regime where the size of the layers is commensurate with the number of samples in the training data. We show that unbiased estimators have unacceptable performance for such nonlinear networks in this regime. We derive explicit generalization lower bounds for general biased estimators, in the cases of linear regression and of two-layered networks. In the linear case the bound is asymptotically tight. In the nonlinear case, we provide a comparison of our bounds with an empirical study of the stochastic gradient descent algorithm. The analysis uses elements from the theory of large random matrices., Comment: Minor correction+conference information. To appear in IEEE Trans. Inf. Th

We study the directed polymer model for general graphs (beyond $\mathbb Z^d$) and random walks. We provide sufficient conditions for the existence or non-existence of a weak disorder phase, of an $L^2$ region, and of very strong disorder, in terms of properties of the graph and of the random walk. We study in some detail (biased) random walk on various trees including the Galton Watson trees, and provide a range of other examples that illustrate counter-examples to intuitive extensions of the $\mathbb Z^d$/SRW result.

Dynamics among central sources (hubs) providing a resource and large number of components enjoying and contributing to this resource describes many real life situations. Modeling, controlling, and balancing this dynamics is a general problem that arises in many scientific disciplines. We analyze a stochastic dynamical system exhibiting this dynamics with a multiplicative noise. We show that this model can be solved exactly by passing to variables that describe the mass ratio between the components and the hub. We derive a deterministic equation for the average mass ratio. This equation describes logistic growth. We derive the full phase diagram of the model and identify three regimes by calculating the sample and moment Lyapunov exponent of the system. The first regime describes full balance between the non-hub components and the hub, in the second regime the entire resource is concentrated mainly in the hub, and in the third regime the resource is localized on a few non-hub components and the hub. Surprisingly, in the limit of large number of components the transition values do not depend on the amount of resource given by the hub. This model has interesting application in the context of analysis of porous media using Magnetic Resonance (MR) techniques.

We develop a multiple compartment Susceptible-Infected-Recovered (SIR) model to analyze the spread of several infectious diseases through different geographic areas. Additionally, we propose a data-quality sensitive optimization framework for fitting this model to observed data. We fit the model to the temporal profile of the number of people infected by one of six influenza strains in Europe over $7$ influenza seasons. In addition to describing the temporal and spatial spread of influenza, the model provides an estimate of the inter-country and intra-country infection and recovery rates of each strain and in each season. We find that disease parameters remain relatively stable, with a correlation greater than $0.5$ over seasons and stains. Clustering of influenza strains by the inferred disease parameters is consistent with genome sub-types. Surprisingly, our analysis suggests that inter-country human mobility plays a negligible role in the spread of influenza in Europe. Finally, we show that the model allows the estimation of disease load in countries with poor or none existent data from the disease load in adjacent countries. Our findings reveal information on the spreading mechanism of influenza and on disease parameters. These can be used to assist in disease surveillance and in control of influenza as well as of other infectious pathogens in a heterogenic environment.

Understanding the dynamics of infectious disease spread in a heterogeneous population is an important factor in designing control strategies. Here, we develop a novel tensor-driven multi-compartment version of the classic Susceptible-Infected-Recovered (SIR) model and apply it to Internet data to reveal information about the complex spatial structure of disease spread. The model is used to analyze state-level Google search data from the US pertaining to two viruses, Respiratory Syncytial Virus (RSV), and West Nile Virus (WNV). We fit the data with correlations of $R^2=0.70$, and $0.52$ for RSV and WNV, respectively. Although no prior assumptions on spatial structure are made, human movement patterns in the US explain 27-30\% of the estimated inter-state transmission rates. The transmission rates within states are correlated with known demographic indicators, such as population density and average age. Finally, we show that the patterns of disease load for subsequent seasons can be predicted using the model parameters estimated for previous seasons and as few as $7$ weeks of data from the current season. Our results are applicable to other countries and similar viruses, allowing the identification of disease spread parameters and prediction of disease load for seasonal viruses earlier in season.

An array of quantum wires is a natural starting point in realizing two-dimensional topological phases. We study a system of weakly coupled quantum wires with Rashba spin-orbit coupling, proximity coupled to a conventional s-wave superconductor. A variety of topological phases are found in this model. These phases are characterized by "Strong" and "Weak" topological invariants, that capture the appearance of mid-gap Majorana modes (either chiral or non-chiral) on edges along and perpendicular to the wires. In particular, a phase with a single chiral Majorana edge mode (analogous to a $p+ip$ superconductor) can be realized. At special values of the magnetic field and chemical potential, this edge mode is almost completely localized at the outmost wires. In addition, a phase with two co-propagating chiral edge modes is observed. We also consider ways to distinguish experimentally between the different phases in tunneling experiments.