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

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"os-R'enyi graphs with connection probability given by $\lambda \mathrm{/}{n}^{\alpha }$ (with $\lambda >0$ and $0<\alpha <1$), a family of local algorithms that approximate a gradient descent find local minima faster than the full gradient descent. Furthermore, we find a probabilistic representation for the running time of these algorithms leading to asymptotic estimates of the mean running times.