Research map / Optimization / Nonconvex and smooth optimization

Gradient Span Algorithms Make Predictable Progress in High Dimension

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that gradient span algorithms (e.g. gradient descent, momentum, conjugate gradient) follow asymptotically deterministic trajectories on scaled isotropic Gaussian random functions as dimension grows, explaining predictable progress in ML training.

Problem

Explaining why optimization runs from different random initializations of high-dimensional, non-convex machine learning cost functions show approximately equal cost curves ("predictable progress").

Approach

Extends prior predictable-progress results for random quadratic functions and spin glasses to general non-stationary isotropic Gaussian random functions, showing that the information vector of any gradient span algorithm converges in probability as dimension N grows, using a previsible custom orthonormal coordinate system and functional Gaussian conditioning.

Key results

• Theorem: for any gradient span algorithm with continuous prefactors and isotropic GRF with smooth kernel, the information vector converges in probability as N tends to infinity to a deterministic limit.
• Corollary: different random initializations with equal norm yield max_k |f_N(X_k^(1)) - f_N(X_k^(2))| converging to zero in probability.
• Simulations of gradient descent on a Gaussian random function show trajectory variance decreasing with dimension.

Surprising findings

• Function values concentrate to the mean exponentially fast, yet gradient norms do not vanish under the 1/N covariance scaling.

Limitations

• Covers only full (non-stochastic) gradients; stochastic gradients are not analyzed.
• Preconditioning methods such as Adam and Shampoo are excluded from the gradient span algorithm class.
• Convergence is in probability rather than almost surely.

Experimental setup

Datasets: MNIST

Metrics: convergence in probability of function values and gradient i

Builds on: spin glass state evolution approximate message passing Bayesian optimization conditioning

Closest papers by meaning

• Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.86)
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.86)
• Random Function Descent (NeurIPS 2024 · similarity 0.86)
• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.85)
• Tuning-Free Stochastic Optimization (ICML 2024 · similarity 0.85)
• Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.85)