Research map / Optimization / Implicit bias and generalization

Statistical Guarantees for High-Dimensional Stochastic Gradient Descent

NeurIPS 2025 · Optimization › Implicit bias and generalization · approach: SGD noise and flat minima · 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.

Shows that constant learning-rate high-dimensional SGD is geometric-moment contractive in l^s norms (l^inf via s ~ log d), derives q-th moment and Fuk-Nagaev-type high-probability bounds for averaged SGD, and a Gaussian approximation.

Problem

Theoretical guarantees for constant learning-rate SGD and Ruppert-Polyak averaged SGD (ASGD) in high-dimensional settings, particularly in the l^infinity norm, where existing results assume decaying learning rates and low dimension.

Approach

View constant-step SGD as a nonlinear autoregressive process and adapt coupling / functional dependence measure techniques from high-dimensional time series to show geometric-moment contraction in l^s norms; use a smooth l^s surrogate (s ~ log d) for the l^inf norm and a high-dimensional Rio-type moment inequality.

Key results

• Geometric-moment contraction of SGD with constant learning rate alpha below 2mu/(max{q,s}L^2_{s,q}) (up to constant), with contraction rate 1-2 mu alpha + max{q,s} L^2 alpha^2.
• Learning-rate range scales as 1/(d^2 log d) when s = s_d ~ log d and L_{s_d,q} ~ d in linear regression.
• Complexity bound of order 1/epsilon^2 for ASGD l^inf error when d is fixed; Fuk-Nagaev-type high-probability bound for ASGD with polynomial-tailed noise.

Limitations

• Requires strong convexity and smoothness assumptions in l^s norm; extension to non-convex is only suggested.
• Learning-rate range shrinks as 1/(d^2 log d) in high dimensions, which is conservative.
• Gaussian approximation requires d = o(T^{1/4-zeta}) to be nontrivial.

Experimental setup

Metrics: q-th moment error bound high-probability tail bound iteration complexity

Builds on: Ruppert-Polyak averaging geometric-moment contraction functional dependence measure Rio inequality

Closest papers by meaning

• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.90)
• The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.90)
• High-dimensional Limit of SGD for Diagonal Linear Networks (NeurIPS 2026 · similarity 0.90)
• The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms (NeurIPS 2024 · similarity 0.89)
• Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.89)
• Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization (NeurIPS 2025 · similarity 0.89)