Can LLMs predict the convergence of Stochastic Gradient Descent?

Oussama Zekri, Abdelhakim Benechehab, Ievgen Redko

Abstract: Large-language models are notoriously famous for their impressive performance across a wide range of tasks. One surprising example of such impressive performance is a recently identified capacity of LLMs to understand the governing principles of dynamical systems satisfying the Markovian property. In this paper, we seek to explore this direction further by studying the dynamics of stochastic gradient descent in convex and non-convex optimization. By leveraging the theoretical link between the SGD and Markov chains, we show a remarkable zero-shot performance of LLMs in predicting the local minima to which SGD converges for previously unseen starting points. On a more general level, we inquire about the possibility of using LLMs to perform zero-shot randomized trials for larger deep learning models used in practice.

Introduction

Stochastic Gradient Descent (SGD) serves as the foundational optimization engine for modern machine learning. Despite its widespread use, predicting the final convergence point of an optimizer within a complex, often non-convex, loss landscape typically requires the actual execution of the optimization process. This is computationally expensive and offers little foresight into the training dynamics.

Recent advancements have highlighted the "In-Context Learning" (ICL) capabilities of Large Language Models (LLMs), enabling them to model complex dynamical systems—such as physical pendulums or meteorological patterns—solely from numerical observations. This research investigates whether these capabilities can be extended to the optimization process itself. Specifically, can an LLM, by observing a sequence of optimization steps, perform "zero-shot" forecasting to predict where a model will converge from an entirely new starting point, without ever computing a gradient?

Methodology

The proposed framework bridges optimization theory and LLM capabilities through a multi-step pipeline designed to treat SGD as a predictable dynamical system.

Overview of the proposed pipeline for predicting SGD convergence using a pre-trained LLM.
  1. SGD as a Markov Chain: The approach relies on the theoretical property that SGD with a constant step size behaves as a homogeneous Markov chain. In this view, the next state is determined solely by the current state and a fixed transition rule.
  2. Numerical Tokenization: To interface with text-based LLMs, SGD iterates (weight coordinates) are rescaled and encoded into strings of digits. This transformation allows the model to process continuous numerical data as discrete tokens.
  3. Hierarchy-PDF for Density Estimation: Rather than simple point predictions, the researchers utilize the LLM's internal logits. An algorithm termed Hierarchy-PDF converts these probability scores into a continuous probability distribution, representing the potential next states of the optimizer.
  4. Kernel Estimation and Imputation: Given the limited sequence length an LLM can process, the resulting transition matrix is inherently sparse. To generalize across the landscape, the authors employ debiased Sinkhorn barycenters—a method from optimal transport—to smooth and complete the estimated transition kernel.
  5. Forecasting: With the estimated kernel, the optimizer's path can be simulated from any novel initialization by iteratively applying the transition rule, effectively "hallucinating" the optimization trajectory.

Experimental Setup

The methodology was rigorously tested in controlled environments using the pre-trained LLaMA-2-7B model in a zero-shot setting. The tasks included:

  • Convex Optimization: Standard 2D linear regression.
  • Non-Convex Optimization: A sinusoidal regression task characterized by multiple local minima.

Key Results

The experiments revealed several significant insights into the LLM's ability to model optimization dynamics.

LLM predictions of SGD convergence across different optimization landscapes and regimes.

Regime Identification and Accuracy

The LLM demonstrated a sophisticated ability to distinguish between different optimization regimes. In overparametrized problems, where the optimizer converges to a single point, the model correctly output a Dirac distribution (a sharp peak). Conversely, in underparametrized regimes where the optimizer fluctuates within a stable distribution, the model predicted a Gaussian-like spread, matching theoretical expectations. Most importantly, the estimated kernels successfully predicted the correct local minima even when starting from initializations not present in the training sequences.

The Role of the Spectral Gap

A key theoretical finding was the influence of the "spectral gap" of the Markov chain on the LLM's learning efficiency. The spectral gap is a measure of convergence speed. Interestingly, the results suggest that LLMs find it easier to internalize the transition rules of systems that converge more slowly, providing a new perspective on the relationship between dynamical mixing times and neural scaling laws.

Discussion and Future Work

This work provides a proof-of-concept for using LLMs to "scout" optimization landscapes. However, significant challenges remain for scaling this to real-world deep learning:

  • Dimensionality: While successful in 2D space, modern models involve millions of parameters. Scaling transition kernel estimation to such high-dimensional spaces is computationally daunting.
  • Parameter Correlation: The current assumption of parameter independence may not hold in complex models where weights are highly correlated.
  • Tokenization Sensitivity: The precision and robustness of numerical representation within LLMs remain areas for improvement.

Despite these limitations, the ability of LLMs to perform zero-shot forecasting of SGD convergence opens the door to "zero-shot randomized trials," potentially allowing researchers to evaluate training configurations without the overhead of full-scale training runs.

Summary updated

Abstract

Large-language models are notoriously famous for their impressive performance across a wide range of tasks. One surprising example of such impressive performance is a recently identified capacity of LLMs to understand the governing principles of dynamical systems satisfying the Markovian property. In this paper, we seek to explore this direction further by studying the dynamics of stochastic gradient descent in convex and non-convex optimization. By leveraging the theoretical link between the SGD and Markov chains, we show a remarkable zero-shot performance of LLMs in predicting the local minima to which SGD converges for previously unseen starting points. On a more general level, we inquire about the possibility of using LLMs to perform zero-shot randomized trials for larger deep learning models used in practice.
BibTeX
@inproceedings{zekri2024can,
  author = {Oussama Zekri and Abdelhakim Benechehab and Ievgen Redko},
  title = {{Can LLMs predict the convergence of Stochastic Gradient Descent?}},
  booktitle = {ICL @ ICML},
  year = {2024},
  url = {https://openreview.net/forum?id=FraikHzMu9},
}
Figure