Exact asymptotic characterisation of running time for approximate gradient descent on random graphs

Matthieu Jonckheere, Manuel Sáenz

In this work we study the time complexity for the search of local minima in random graphs whose vertices have i.i.d. cost values. We show that, for Erdös-Rényi graphs with connecti…