Gradient Span Algorithms Make Predictable Progress in High Dimension

Abstract:We prove that all 'gradient span algorithms' have asymptotically deterministic behavior on scaled Gaussian random functions as the dimension tends to infinity. This is a functional generalization of similar results for random quadratic functions and spin glasses. They explain the counterintuitive phenomenon that different training runs of many large machine learning models result in approximately equal cost curves despite random initialization on a complicated non-convex landscape. This 'predictable progress' phenomenon is exploited by the AutoML community: Since the optimization progress of a single run is already representative, multiple retries with the same hyperparameters are not necessary.

Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC); Probability (math.PR)

arXiv:2410.09973 [stat.ML]

(or arXiv:2410.09973v2 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2410.09973 Focus to learn more arXiv-issued DOI via DataCite

Journal of Machine Learning Research 27, no. 121 (2026): 1-62. https://jmlr.org/papers/v27/25-1651.html

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.