Force balance controls the relaxation time of the gradient descent algorithm in the satisfiable phase

Sungmin Hwang, Harukuni Ikeda

Published 2019-10-16Version 1

We numerically study the relaxation dynamics of the single layer perceptron with the spherical constraint. This is the simplest model of neural networks and serves a prototypical mean-field model of both convex and non-convex optimization problems. The relaxation time of the gradient descent algorithm rapidly increases near the SAT-UNSAT transition point. We numerically confirm that the first non-zero eigenvalue of the Hessian controls the relaxation time. This first eigenvalue vanishes much faster upon approaching the SAT-UNSAT transition point than the prediction of Marchenko-Pastur law in random matrix theory derived under the assumption that the set of unsatisfied constraints are uncorrelated. This leads to a non-trivial critical exponent of the relaxation time in the SAT phase. Using a simple scaling analysis, we show that the isolation of this first eigenvalue from the bulk of spectrum is attributed to the force balance at the SAT-UNSAT transition point. Finally, we show that the estimated critical exponent of the relaxation time in the non-convex region agrees very well with that of frictionless spherical particles, which have been studied in the context of the jamming transition of granular materials.