Abstract. 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 connection probability… Click to show full abstract
Abstract. 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 connection probability given by λ∕nα (with λ > 0 and 0<α<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.
Keywords:
gradient descent;
approximate gradient;
time;
random graphs
Journal Title: Stochastic Analysis and Applications
Year Published: 2025
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Stochastic Analysis and Applications
Year Published: 2025
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!