[en] Gradient descent dynamics in complex energy landscapes, i.e. featuring multiple minima, finds application in many different problems, from soft matter to machine learning. Here, we analyze one of the simplest examples, namely that of soft repulsive particles in the limit of infinite spatial dimension d. The gradient descent dynamics then displays a jamming transition: at low density, it reaches zero-energy states in which particles' overlaps are fully eliminated, while at high density the energy remains finite and overlaps persist. At the transition, the dynamics becomes critical. In the d → ∞ limit, a set of self-consistent dynamical equations can be derived via mean field theory. We analyze these equations and we present some partial progress towards their solution. We also study the random Lorentz gas in a range of d = 2...22, and obtain a robust estimate for the jamming transition in d → ∞. The jamming transition is analogous to the capacity transition in supervised learning, and in the appendix we discuss this analogy in the case of a simple one-layer fully-connected perceptron.
Disciplines :
Physique
Auteur, co-auteur :
MANACORDA, Alessandro ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Physics and Materials Science (DPHYMS)
Zamponi, Francesco; Centre National de la Recherche Scientifique - CNRS > Laboratoire de Physique de l'École Normale Supérieure
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Gradient descent dynamics and the jamming transition in infinite dimensions
Date de publication/diffusion :
15 août 2022
Titre du périodique :
Journal of Physics. A, Mathematical and Theoretical
ISSN :
1751-8113
eISSN :
1751-8121
Maison d'édition :
Institute of Physics (IOP), Bristol, Royaume-Uni
Titre particulier du numéro :
Random Landscapes and Dynamics in Evolution, Ecology and Beyond
Cugliandolo L F Kurchan J 1993 Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model Phys. Rev. Lett. 71 173 10.1103/physrevlett.71.173
Cugliandolo L F Kurchan J 1994 On the out-of-equilibrium relaxation of the Sherrington-Kirkpatrick model J. Phys. A: Math. Gen. 27 5749 10.1088/0305-4470/27/17/011
Cugliandolo L F 2003 Dynamics of glassy systems Slow Relaxations and Nonequilibrium Dynamics in Condensed Matter Barrat J Feigelman M Kurchan J Dalibard J Berlin Springer
Barrat A Franz S Parisi G 1997 Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses J. Phys. A: Math. Gen. 30 5593 10.1088/0305-4470/30/16/006
Montanari A Ricci-Tersenghi F 2004 Cooling-schedule dependence of the dynamics of mean-field glasses Phys. Rev. B 70 134406 10.1103/physrevb.70.134406
Rizzo T 2013 Replica-symmetry-breaking transitions and off-equilibrium dynamics Phys. Rev. E 88 032135 10.1103/physreve.88.032135
Folena G Franz S Ricci-Tersenghi F 2020 Rethinking mean-field glassy dynamics and its relation with the energy landscape: the surprising case of the spherical mixed p-spin model Phys. Rev. X 10 031045 10.1103/physrevx.10.031045
Altieri A Biroli G Cammarota C 2020 Dynamical mean-field theory and aging dynamics J. Phys. A: Math. Theor. 53 375006 10.1088/1751-8121/aba3dd
Kurchan J 2021 Time-reparametrization invariances, multithermalization and the Parisi scheme (arXiv: 2101.12702)
Baity-Jesi M Sagun L Geiger M Spigler S Ben Arous G Cammarota C LeCun Y Wyart M Biroli G 2019 Comparing dynamics: deep neural networks versus glassy systems J. Stat. Mech. 124013 10.1088/1742-5468/ab3281
Mannelli S S Krzakala F Urbani P Zdeborova L 2019 Passed spurious: descent algorithms and local minima in spiked matrix-tensor models Int. Conf. Machine Learning (PMLR) 4333 4342 4333-42
Mannelli S S Biroli G Cammarota C Krzakala F Zdeborová L 2019 Who is afraid of big bad minima? Analysis of gradient-flow in spiked matrix-tensor models Advances in Neural Information Processing Systems vol 32 p 8679
Mannelli S S Biroli G Cammarota C Krzakala F Urbani P Zdeborová L 2020 Complex dynamics in simple neural networks: understanding gradient flow in phase retrieval Advances in Neural Information Processing Systems vol 33 p 3265
Sclocchi A Urbani P 2022 High dimensional optimization under non-convex excluded volume constraints Phys. Rev. E 105 024134 10.1103/physreve.105.024134
Biroli G Cammarota C Ricci-Tersenghi F 2020 How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA J. Phys. A: Math. Theor. 53 174003 10.1088/1751-8121/ab7b1f
Mannelli S S Biroli G Cammarota C Krzakala F Urbani P Zdeborová L 2020 Marvels and pitfalls of the Langevin algorithm in noisy high-dimensional inference Phys. Rev. X 10 011057 10.1103/physrevx.10.011057
Mignacco F Urbani P Zdeborová L 2021 Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem Mach. Learn.: Sci. Technol. 2 035029 10.1088/2632-2153/ac0615
Franz S Parisi G 2016 The simplest model of jamming J. Phys. A: Math. Theor. 49 145001 10.1088/1751-8113/49/14/145001
Franz S Parisi G Sevelev M Urbani P Zamponi F 2017 Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems SciPost Phys. 2 019 10.21468/scipostphys.2.3.019
Franz S Hwang S Urbani P 2019 Jamming in multilayer supervised learning models Phys. Rev. Lett. 123 160602 10.1103/physrevlett.123.160602
Spigler S Geiger M d’Ascoli S Sagun L Biroli G Wyart M 2019 A jamming transition from under- to over-parametrization affects generalization in deep learning J. Phys. A: Math. Theor. 52 474001 10.1088/1751-8121/ab4c8b
Franz S Sclocchi A Urbani P 2021 Surfing on minima of isostatic landscapes: avalanches and unjamming transition J. Stat. Mech. 023208 10.1088/1742-5468/abdc16
Mitchell D Selman B Levesque H 1992 Hard and easy distributions of sat problems Tenth National Conference on Artificial Intelligence (AAAI-92) San Jose, CA, US July 1992 459 465 459-65
Kirkpatrick S Selman B 1994 Critical behavior in the satisfiability of random Boolean expressions Science 264 1297 10.1126/science.264.5163.1297
Monasson R Zecchina R Kirkpatrick S Selman B Troyansky L 1999 Determining computational complexity from characteristic ‘phase transitions’ Nature 400 133 10.1038/22055
Altarelli F Monasson R Semerjian G Zamponi F 2009 A review of the statistical mechanics approach to random optimization problems Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications Biere A Heule M van Maaren H Walsh T Amsterdam IOS Press ( https://doi.org/10.3233/978-1-58603-929-5-569) 10.3233/978-1-58603-929-5-569
Folena G Manacorda A Zamponi F 2022 Introduction to the dynamics of disordered systems: equilibrium and gradient descent (arXiv: 2202.02413)
Hwang S Ikeda H 2020 Force balance controls the relaxation time of the gradient descent algorithm in the satisfiable phase Phys. Rev. E 101 052308 10.1103/physreve.101.052308
Gardner E Derrida B 1988 Optimal storage properties of neural network models J. Phys. A: Math. Gen. 21 271 10.1088/0305-4470/21/1/031
Krauth W Mézard M 1989 Storage capacity of memory networks with binary couplings J. Phys. France 50 3057 10.1051/jphys:0198900500200305700
Brunel N Nadal J-P Toulouse G 1992 Information capacity of a perceptron J. Phys. A: Math. Gen. 25 5017 10.1088/0305-4470/25/19/015
Monasson R Zecchina R 1995 Learning and generalization theories of large committee-machines Mod. Phys. Lett. B 09 1887 10.1142/s0217984995001868
Tikhonov M Monasson R 2017 Collective phase in resource competition in a highly diverse ecosystem Phys. Rev. Lett. 118 048103 10.1103/physrevlett.118.048103
Landmann S Engel A 2018 Systems of random linear equations and the phase transition in MacArthur’s resource-competition model Europhys. Lett. 124 18004 10.1209/0295-5075/124/18004
Altieri A Franz S 2019 Constraint satisfaction mechanisms for marginal stability and criticality in large ecosystems Phys. Rev. E 99 010401 10.1103/physreve.99.010401
Martino A D Marsili M Castillo I P 2004 Statistical mechanics analysis of the equilibria of linear economies J. Stat. Mech. P04002 10.1088/1742-5468/2004/04/p04002
Moran J Bouchaud J-P 2019 May’s instability in large economies Phys. Rev. E 100 032307 10.1103/physreve.100.032307
Sharma D Bouchaud J-P Tarzia M Zamponi F 2021 Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model J. Stat. Mech. 063403 10.1088/1742-5468/ac014a
Durian D J 1995 Foam mechanics at the bubble scale Phys. Rev. Lett. 75 4780 10.1103/physrevlett.75.4780
O’Hern C S Langer S A Liu A J Nagel S R 2002 Random packings of frictionless particles Phys. Rev. Lett. 88 075507 10.1103/PhysRevLett.88.075507
O’Hern C S Silbert L E Liu A J Nagel S R 2003 Jamming at zero temperature and zero applied stress: the epitome of disorder Phys. Rev. E 68 011306 10.1103/PhysRevE.68.011306
Liu A J Nagel S R 2010 The jamming transition and the marginally jammed solid Annu. Rev. Condens. Matter Phys. 1 347 10.1146/annurev-conmatphys-070909-104045
Liu A Nagel S Van Saarloos W Wyart M 2011 The jamming scenario—an introduction and outlook Dynamical Heterogeneities and Glasses Berthier L Biroli G Bouchaud J-P Cipelletti L van Saarloos W Oxford Oxford University Press
Ikeda A Kawasaki T Berthier L Saitoh K Hatano T 2020 Universal relaxation dynamics of sphere packings below jamming Phys. Rev. Lett. 124 058001 10.1103/physrevlett.124.058001
Nishikawa Y Ikeda A Berthier L 2021 Relaxation dynamics of non-Brownian spheres below jamming J. Stat. Phys. 182 37 10.1007/s10955-021-02710-8
Chacko R N Sollich P Fielding S M 2019 Slow coarsening in jammed athermal soft particle suspensions Phys. Rev. Lett. 123 108001 10.1103/physrevlett.123.108001
Nishikawa Y Ozawa M Ikeda A Chaudhuri P Berthier L 2021 Relaxation dynamics in the energy landscape of glass-forming liquids Phys. Rev. X 12 021001 10.1103/PhysRevX.12.021001
Sompolinsky H Zippelius A 1981 Dynamic theory of the spin-glass phase Phys. Rev. Lett. 47 359 10.1103/physrevlett.47.359
Sompolinsky H Zippelius A 1982 Relaxational dynamics of the Edwards-Anderson model and the mean-field theory of spin-glasses Phys. Rev. B 25 6860 10.1103/physrevb.25.6860
Maimbourg T Kurchan J Zamponi F 2016 Solution of the dynamics of liquids in the large-dimensional limit Phys. Rev. Lett. 116 015902 10.1103/physrevlett.116.015902
Szamel G 2017 Simple theory for the dynamics of mean-field-like models of glass-forming fluids Phys. Rev. Lett. 119 155502 10.1103/physrevlett.119.155502
Agoritsas E Biroli G Urbani P Zamponi F 2018 Out-of-equilibrium dynamical mean-field equations for the perceptron model J. Phys. A: Math. Theor. 51 085002 10.1088/1751-8121/aaa68d
Agoritsas E Maimbourg T Zamponi F 2019 Out-of-equilibrium dynamical equations of infinite-dimensional particle systems: I. The isotropic case J. Phys. A: Math. Theor. 52 144002 10.1088/1751-8121/ab099d
Liu C Biroli G Reichman D R Szamel G 2021 Dynamics of liquids in the large-dimensional limit Phys. Rev. E 104 054606 10.1103/physreve.104.054606
Ikeda H Shimada M 2020 Vibrational density of states of jammed packing: mean-field theory and beyond (arXiv: 2009.12060)
Shimada M Mizuno H Berthier L Ikeda A 2020 Low-frequency vibrations of jammed packings in large spatial dimensions Phys. Rev. E 101 052906 10.1103/physreve.101.052906
Franz S Parisi G Urbani P Zamponi F 2015 Universal spectrum of normal modes in low-temperature glasses Proc. Natl Acad. Sci. USA 112 14539 10.1073/pnas.1511134112
Lerner E Düring G Wyart M 2013 Low-energy non-linear excitations in sphere packings Soft Matter 9 8252 10.1039/c3sm50515d
Ikeda H 2020 Relaxation time below jamming J. Chem. Phys. 153 126102 10.1063/5.0024042
Biroli G Charbonneau P Corwin E I Hu Y Ikeda H Szamel G Zamponi F 2021 Interplay between percolation and glassiness in the random Lorentz gas Phys. Rev. E 103 L030104 10.1103/physreve.103.l030104
Biroli G Charbonneau P Hu Y Ikeda H Szamel G Zamponi F 2021 Mean-field caging in a random Lorentz gas J. Phys. Chem. B 125 144 10.1021/acs.jpcb.1c02067
Parisi G Urbani P Zamponi F 2020 Theory of Simple Glasses: Exact Solutions in Infinite Dimensions Cambridge Cambridge University Press
Manacorda A Schehr G Zamponi F 2020 Numerical solution of the dynamical mean field theory of infinite-dimensional equilibrium liquids J. Chem. Phys. 152 164506 10.1063/5.0007036
Bun J Bouchaud J-P Potters M 2017 Cleaning large correlation matrices: tools from random matrix theory Phys. Rep. 666 1 10.1016/j.physrep.2016.10.005
Arnoulx de Pirey T Manacorda A van Wijland F Zamponi F 2021 Active matter in infinite dimensions: Fokker-Planck equation and dynamical mean-field theory at low density J. Chem. Phys. 155 174106 10.1063/5.0065893
Roy F Biroli G Bunin G Cammarota C 2019 Numerical implementation of dynamical mean field theory for disordered systems: application to the Lotka-Volterra model of ecosystems J. Phys. A: Math. Theor. 52 484001 10.1088/1751-8121/ab1f32
Mignacco F Krzakala F Urbani P Zdeborová L 2021 Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification J. Stat. Mech. 124008 10.1088/1742-5468/ac3a80
Folena G Urbani P 2022 Marginal stability of soft anharmonic mean field spin glasses J. Stat. Mech. 053301 10.1088/1742-5468/ac6253
Mignacco F Urbani P 2021 The effective noise of stochastic gradient descent (arXiv: 2112.10852)
Charbonneau P Corwin E I Parisi G Zamponi F 2015 Jamming criticality revealed by removing localized buckling excitations Phys. Rev. Lett. 114 125504 10.1103/physrevlett.114.125504
Mangeat M Zamponi F 2016 Quantitative approximation schemes for glasses Phys. Rev. E 93 012609 10.1103/physreve.93.012609
Charbonneau P Hu Y Kundu J Morse P K 2022 The dimensional evolution of structure and dynamics in hard sphere liquids J. Chem. Phys. 156 134502 10.1063/5.0080805
Sartor J D Ridout S A Corwin E I 2021 Mean-field predictions of scaling prefactors match low-dimensional jammed packings Phys. Rev. Lett. 126 048001 10.1103/physrevlett.126.048001
Bouchaud J P 1992 Weak ergodicity breaking and aging in disordered systems J. Phys. I France 2 1705 10.1051/jp1:1992238
Olsson P Teitel S 2007 Critical scaling of shear viscosity at the jamming transition Phys. Rev. Lett. 99 178001 10.1103/physrevlett.99.178001
Vagberg D Olsson P Teitel S 2011 Glassiness, rigidity, and jamming of frictionless soft core disks Phys. Rev. E 83 031307 10.1103/physreve.83.049901
Olsson P Teitel S 2020 Dynamic length scales in athermal, shear-driven jamming of frictionless disks in two dimensions Phys. Rev. E 102 042906 10.1103/physreve.102.042906
Mari R Krzakala F Kurchan J 2009 Jamming versus glass transitions Phys. Rev. Lett. 103 025701 10.1103/physrevlett.103.025701
Mari R Kurchan J 2011 Dynamical transition of glasses: from exact to approximate J. Chem. Phys. 135 124504 10.1063/1.3626802
Parisi G Zamponi F 2010 Mean-field theory of hard sphere glasses and jamming Rev. Mod. Phys. 82 789 10.1103/revmodphys.82.789
Ozawa M Berthier L Coslovich D 2017 Exploring the jamming transition over a wide range of critical densities SciPost Phys. 3 027 10.21468/scipostphys.3.4.027
Berthier L Jacquin H Zamponi F 2011 Microscopic theory of the jamming transition of harmonic spheres Phys. Rev. E 84 051103 10.1103/physreve.84.051103
Scalliet C Berthier L Zamponi F 2019 Marginally stable phases in mean-field structural glasses Phys. Rev. E 99 012107 10.1103/physreve.99.012107
Monasson R 1995 Structural glass transition and the entropy of the metastable states Phys. Rev. Lett. 75 2847 10.1103/physrevlett.75.2847
Wyart M 2012 Marginal stability constrains force and pair distributions at random close packing Phys. Rev. Lett. 109 125502 10.1103/physrevlett.109.125502
Müller M Wyart M 2015 Marginal stability in structural, spin, and electron glasses Annu. Rev. Condens. Matter Phys. 6 177 10.1146/annurev-conmatphys-031214-014614
Montanari A Ricci-Tersenghi F 2003 On the nature of the low-temperature phase in discontinuous mean-field spin glasses Eur. Phys. J. B 33 339 10.1140/epjb/e2003-00174-7
Charbonneau P Kurchan J Parisi G Urbani P Zamponi F 2014 Exact theory of dense amorphous hard spheres in high dimension: III. The full replica symmetry breaking solution J. Stat. Mech. P10009 10.1088/1742-5468/2014/10/p10009
Charbonneau P Kurchan J Parisi G Urbani P Zamponi F 2014 Fractal free energy landscapes in structural glasses Nat. Commun. 5 3725 10.1038/ncomms4725
Bernaschi M Billoire A Maiorano A Parisi G Ricci-Tersenghi F 2020 Strong ergodicity breaking in aging of mean-field spin glasses Proc. Natl Acad. Sci. USA 117 17522 10.1073/pnas.1910936117
