Stochastic Gradient Descent

Also known as SGD

Overview

Stochastic Gradient Descent (SGD) updates model parameters using gradients from individual examples or mini-batches, making optimization practical when full-dataset gradients are too costly. Research studies convergence and generalization, and develops variants such as momentum, adaptive learning rates, clipping, variance reduction, and decentralized or federated updates. Analyses span convex and nonconvex objectives, neural-network dynamics, heavy-tailed or dependent noise, and statistical inference from training trajectories. A central tension is that gradient noise can improve exploration and favor flatter solutions, yet can also destabilize training or slow convergence, so its effects depend on batch size, learning-rate schedule, model geometry, and data conditions.

Latest papers

252 papers28 papers in the last four weeks, down 33% on the four weeks before. 0.2% of all new papers.

Nov 18, 2026

Decomposing SGD Dynamics in Neural Networks: Teacher-Induced Spikes and Variance Inflation

We study two-layer neural networks trained by stochastic gradient descent (SGD) on a multi-index teacher model, focusing on how first-layer parameters orthogonal to the teacher subspace affect generalization. We decompose the first-layer weights into a signal component aligned with the teacher and an orthogonal complement, and analyze their joint SGD dynamics together with the second layer in the proportional limit. We show that although SGD updates to the complement are initially isotropic, the training dynamics induce teacher-dependent spectral spikes in the complement Gram matrix. This emergent anisotropy provides a concrete mechanism by which representation variance is amplified, and generalization degrades. To isolate this effect, we introduce Decomposed Dynamics, an analytically tractable surrogate whose asymptotic test-error dynamics coincide with those of SGD. In simulations with a ReLU student, freezing the directions of the orthogonal complement improves generalization relative to training them. Finally, we show that the signal component rapidly aligns with the second-layer weights, revealing strong cross-layer coupling even in this shallow setting. Together, our results provide a dynamical explanation for how feature learning outside the teacher subspace harms generalization.
Nov 18, 2026

Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime

In this paper, we study stochastic gradient descent in the smooth interpolation regime, where the population objective shares a common minimizer with the sample losses. In contrast to prior work, which has largely focused on in-expectation analysis, we obtain high-probability convergence guarantees under the same assumptions. In the convex case, we prove a fast rate of order log⁡(β−1)⋅n−1\log(β^{-1}) \cdot n^{-1} after nn iterations, with failure probability at most ββ. In the strongly convex case, we derive a family of moment-based bounds of order β−p⋅exp⁡(−O(p⋅n))β^{-p} \cdot \exp(-\mathcal{O}(p \cdot n)) for p∈(0,1]p \in (0,1], and complement them with a matching lower bound showing that the corresponding deterioration in the exponential rate is essentially unavoidable. In both settings, our theoretical results are unified across a broad class of step-size schedules. Building on this analysis, we extend our results to a low-noise regime and to nonconvex objectives satisfying the Polyak-Lojasiewicz condition.
Nov 18, 2026

Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

We study the almost sure convergence of the last-iterate optimization error of Stochastic (sub)Gradient Descent (SGD) for convex objectives. For smooth objectives, we establish convergence rates of order k−1/3k^{-1/3} when a stationary minimizer exists, and k−1/4k^{-1/4} otherwise, up to polylogarithmic factors, where kk denotes the iteration counter. We further show that the latter rate extends to nonsmooth convex objectives. All these rates are achieved by deterministic, anytime stepsize policies. Finally, we establish matching lower bounds showing that the exponents −1/3-1/3 and −1/4-1/4 are optimal, up to polylogarithmic factors, for the corresponding problem classes.
Nov 17, 2026

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an εε-surely feasible stochastic optimalsurely\ feasible\ stochastic\ optimal (εε-SFSO) solution, in which the constraint violation is deterministically bounded by εε, and the expected optimality gap is at most εε. While a recently proposed stochastic variance-reduced first-order penalty method can compute an εε-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an εε-SFSO solution and that for computing an εε-expected feasible stochastic optimalexpected\ feasible\ stochastic\ optimal solution, where both the expected constraint violation and the expected optimality gap are bounded by εε. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an εε-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.
Nov 13, 2026

LACCO: Local Accumulation with Computation--Communication Overlap

Training language models across low-bandwidth networks requires reducing synchronization overhead. Local optimization methods such as DiLoCo communicate only after several local steps, but outer gradient averaging and the outer update remain on the critical path. Existing computation-communication overlap methods avoid this stall through delayed or replica-local updates, which can degrade convergence or cause replicas to drift. We propose LACCO (Local Accumulation with Computation-Communication Overlap), a two-stage algorithm that overlaps global communication with local computation while applying globally aggregated updates shared by every replica, without introducing staleness in the outer update. We establish convergence guarantees for smooth non-convex objectives. Experiments on language-model pre-training with FineWeb show that LACCO consistently outperforms communication-overlapped baselines such as Eager and Delayed DiLoCo. These gains remain robust as model size scales up to 0.5B parameters and across a range of communication intervals and numbers of replicas up to 16 workers, while incurring only negligible-or fully overlappable-computational or memory overhead, which demonstrates the strength of LACCO.
Nov 12, 2026

When and How SignSGD Outperforms SGD: A Functional Scaling Law Perspective

We study how the sign operator interacts with gradient noise to shape the learning dynamics and scaling behavior of sign-based optimizers. In power-law kernel regression with diagonal features, we establish a functional scaling law (FSL) for SignSGD under general learning rate schedules. The FSL describes the learning dynamics through two processes: signal learning and noise forgetting. The key mechanism is noise-induced preconditioning: gradient noise smooths the sign operator, inducing an effective preconditioned SGD. Noise-curvature alignment enables this preconditioning to transform the effective Hessian from H\mathbf{H} to H1/2\mathbf{H}^{1/2}. The resulting dynamics exhibit faster signal learning but slower noise forgetting than SGD. This tradeoff yields a regime-dependent comparison with SGD: (i) SignSGD achieves improved data efficiency in the hard-task regime; (ii) both optimizers achieve the same data efficiency in the easy-task regime, but SignSGD maintains this efficiency at larger batch sizes, requiring fewer optimization steps for a fixed data budget. Power-law kernel regression experiments support the proposed mechanism and predicted scaling behavior. LLM pre-training experiments further suggest that the SignSGD FSL better captures the batch-size dependence of loss dynamics for sign-based optimizers than the original SGD FSL.
Nov 10, 2026

Improved last-iterate bounds for SGD with and without replacement

In this work, we study last-iterate convergence bounds for stochastic gradient descent (SGD) on convex and ββ-smooth loss functions and improve the bound from \cO((log⁡T)3/T)\cO((\log T)^3/T) to \cO((log⁡T)3/(Tlog⁡log⁡T))\cO((\log T)^3/(T\log\log T)) in the interpolation regime. The improvement comes from applying a horizon-dependent multiscale estimate of gradients to the comparison of trajectories. The bound applies to both sampling with replacement and sampling without replacement within one pass.
Nov 10, 2026

Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression

We study the excess risk of constant-stepsize online stochastic gradient descent (SGD) with tail-averaging for high-dimensional linear regression. Building on the instance-dependent spectral framework of Zou et al. (2021), we establish matching initialization-explicit upper and lower bounds on the total excess risk of tail-averaged SGD in terms of the population covariance spectrum H\mathbf{H} and initialization w0−w∗\mathbf{w}_0-\mathbf{w}^* whenever a trajectory spectral feedback condition holds. Existing analyses exhibit a fundamental gap in the effective variance: the upper bound of Zou et al. (2021) retains an undamped contribution from the initial error in the head eigenspace I0:k†\mathbf{I}_{0:k^\dagger}, whereas their lower bound omits the variance induced by the head initialization altogether. We show that both the existing upper and lower bounds are loose: the single-hop fast-mode variance contribution from the head initialization is exponentially damped during the burn-in phase, whereas fourth-moment energy scattered from the head initialization into slow spectral modes during the early burn-in steps survives undamped into the averaging window. We prove that our spectral feedback condition is satisfied in two concrete constant-stepsize regimes: (i) for arbitrary covariance spectra H\mathbf{H} and any finite horizon, under an explicit horizon-dependent stepsize chosen prior to execution; and (ii) for polynomially decaying spectra λi≍i−aλ_i\asymp i^{-a} (a>1a>1), under a single horizon-independent positive stepsize. Finally, we complement these positive results with explicit one- and two-dimensional separation constructions proving an exponential-versus-polynomial gap in the lower bound of Zou et al. (2021) and showing why fourth-moment assumptions alone cannot determine the asymptotic exponential decay rate without additional structural conditions.
Nov 9, 2026

Learning Rate Decay Can Exponentially Accelerate SGD for Global Optimization of Nonconvex Functions

Stochastic Gradient Descent (SGD) is a workhorse algorithm for continuous optimization. It is a folk belief among deep learning practitioners that learning rate decay in SGD substantially improves performance. However, it has remained unclear whether learning rate decay offers an asymptotic advantage for global nonconvex optimization. We answer this question in the affirmative by demonstrating a natural class of nonconvex functions for which, we prove that SGD with learning rate decay requires exponentially fewer gradient queries for global optimization than SGD with any fixed learning rate in the small-step size regime. To the best of our knowledge, this is the first exponential advantage that has been demonstrated for learning rate decay. The class of functions we consider includes many popular benchmark nonconvex functions. Our results provide a robust explanatory theory for the empirically observed benefits of learning rate decay for global optimization. We show that annealing performs the non-logconcave sampling task associated to the optimization problem in polynomial time, via a novel application of weak Poincaré inequalities.
Nov 8, 2026

Orthogonal Updates for the Win: Towards Accelerated Adaptive Minimax Optimization

Single-loop minimax methods are appealing for modern machine learning, but standard stochastic gradient updates can be unstable and oscillatory under tightly coupled primal-dual dynamics, making performance notoriously sensitive to stepsizes. To fundamentally improve stability, we develop an orthogonal update framework tailored to minimax optimization, which applies updates along orthogonalized directions to reduce update anisotropy. However, orthogonalization reshapes the optimization geometry and makes coordinating primal-dual stepsizes even more delicate. To overcome this challenge, we develop AdaSGDA, which equips orthogonal updates with an adaptive stepsize rule driven by accumulated gradient norms. This mechanism automatically balances coupled primal-dual progress under orthogonalization, yielding an effectively parameter-free method for nonconvex-strongly-concave minimax optimization. We prove that AdaSGDA avoids problem-dependent tuning while attaining the state-of-the-art O(T−1/4)\mathcal{O}\left(T^{-1/4}\right) convergence rate. We further propose AdaSGDA-VR, which incorporates a carefully designed variance reduction scheme and achieves the faster O(T−1/3)\mathcal{O}\left(T^{-1/3}\right) rate. Extensive experiments demonstrate that our methods deliver competitive performance compared to existing minimax optimization methods.
Nov 8, 2026

Full Fine-Tuning is not the Problem: Why Adam Fails and SGD Succeeds in Few-Shot CLIP Adaptation

Few-shot CLIP adaptation is often treated as a parameterization problem. Full fine-tuning is assumed to overfit, so parameter-efficient fine-tuning (PEFT) methods are preferred. In this paper, we show that this conclusion conflates parameterization with optimization. Across 11 datasets, 3 CLIP backbones, and 5 shot levels, dense full fine-tuning with plain SGD outperforms representative PEFT methods under the reported evaluation protocol, whereas Adam/AdamW collapses. We trace this collapse to unreliable support-set preconditioning. The few-shot second moment systematically underestimates the corresponding full-data statistic, already at initialization. Adam's inverse-square-root normalization converts this error into an oversized adaptive update. Matching Adam's first-step update budget to SGD resolves most of the collapse, whereas numerator-side alignment does not explain the failure. Shampoo and SOAP also fail, so richer preconditioning alone does not resolve the problem. Theory formalizes how few-shot estimation error is amplified into unsafe updates. SGD succeeds because it avoids unreliable preconditioners and stays close to pretrained CLIP. Interpolation probes show low-loss connections along tested directions, and curvature probes show favorable directional curvature. These results identify optimizer-induced preconditioning, not dense full fine-tuning itself, as the main source of failure in few-shot CLIP adaptation.
Nov 6, 2026

The Multiscale Single-Index Model: An MSE Analysis of Online SGD Dynamics

We consider the Multiscale Single-Index Model (MSIM), first introduced by Oymak and Soltanolkotabi (2021), as a stylized model for hierarchical feature learning with scale separation. Each layer extracts a shared single-index feature at one physical scale and passes it to the next, giving a tractable setting in which to study how deep architectures learn local multiscale representations. Under non-degeneracy and delocalization assumptions on the link function and planted features respectively, for the two hidden-layer case (K=2K=2), we analyze joint online spherical SGD under MSE loss, which is a canonical regression objective, in discrete time and show that it achieves weak recovery from random initialization in O(dlog⁡2d)O(d\log^2 d) samples, followed by strong recovery to accuracy ε\varepsilon in O(dlog⁡(1/ε))O(d\log(1/\varepsilon)) additional samples. The main technical challenge arises from the non-Gaussian learned features observed by the second layer. We address this challenge through a quantitative Gaussian comparison using delocalization, combined with sharp trajectory-level control of the coupled SGD dynamics. This work is a companion to Bruna (2026, arXiv:2607.03347), which studies recovery under a correlation objective for general KK.
Nov 5, 2026

On the Few-Shot Adaptation of Vision-Language Models: A Few Gradient Signs Are All You Need

The limited supervision available for the few-shot adaptation of vision-language models makes gradient estimation particularly noisy. We find that the gradient magnitudes are severely miscalibrated, while the signs of a small top-magnitude subset remain informative. This motivates SignSparseSGD and DynSignSparseSGD, two state-free optimizers that use gradient magnitudes only to select where to update and fixed-magnitude signs to decide how to update. The static variant fixes the support after the first minibatch. The dynamic variant refreshes it at every step. Across 11 datasets, three CLIP backbones, and five shot levels, the proposed methods are competitive with or outperform parameter-efficient and optimization-based baselines on average, while exhibiting markedly lower sensitivity to long training schedules. They introduce no task-specific modules, maintain no first- or second-moment optimizer states, and use one shared configuration across datasets, backbones, and shot levels. Our code is included in the supplementary materials and will be released upon publication.
Nov 5, 2026

Compressed Per-Player Local Methods for Multiplayer Federated Learning: Exact Convergence via Increment Sharing

Multiplayer Federated Learning (MpFL), introduced by Yoon et al. (2025), extends classical federated learning to settings where clients are rational players in a game with individual objectives and strategies, seeking an equilibrium. A natural baseline is Per-Player Local SGD (PEARL-SGD), where each player performs several local SGD steps before exchanging strategies through a central server. However, the original PEARL-SGD formulation does not extend cleanly to compressed communication. Directly compressing the players' strategies can prevent convergence to the equilibrium, even with deterministic gradients. To address this issue, we reformulate PEARL-SGD so that players communicate local strategy increments rather than the strategies themselves. Without compression, the two formulations are equivalent, but with compression, increment sharing preserves exact convergence, allowing us to design the communication-efficient compressed PEARL-SGD (C-PEARL-SGD). Beyond compression, we also consider variance reduction as another axis of improvement, introducing PEARL-SVRG and its compressed variant C-PEARL-SVRG. Under the original MpFL assumptions, we establish convergence guarantees for all variants through a unified parametric inequality. Numerical experiments, including distributed spectrum sensing, demonstrate the practical benefits of our methods over vanilla PEARL-SGD.
Nov 5, 2026

Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems

Last-iterate convergence guarantees for stochastic gradient methods have attracted significant attention as practical implementations typically return the last iterate instead of an average of the iterates. In this paper, we study two approaches for analyzing the last-iterate convergence of proximal and projected stochastic gradient methods without bounded domain or bounded variance assumptions, where black-box variational inference serves as a running example. Under two related assumptions relaxing the bounded variance, we show near-optimal anytime rate O~(1/T)\widetilde{\mathcal{O}}(1/\sqrt{T}) for the last iterate. Moreover, when the horizon TT is known, we remove the logarithmic factor and obtain the optimal order O(1/T)\mathcal{O}(1/\sqrt{T}), matching the order known under bounded variance or bounded domain assumptions.
Nov 3, 2026

Stepsize modulation for cross entropy from local quadratic optimization

Two methods are presented that perturb a given learning rate schedule in stochastic gradient descent with cross entropy loss. Both methods use an extra forward pass to estimate various derivatives of the minibatch loss. The first method selects a value ηη by linearising the softmax values and minimizing the squared error 12∣∣y−q−ηq′∣∣F2\tfrac 1 2 ||y - q - ηq'||_F^2, where qq is the matrix representing the softmax values of the minibatch and yy is the matrix with one-hot encodings of the labels. The second method considers a quadratic Taylor approximation of the minibatch loss under the outer approximation of the Hessian. Thus, it minimizes L(0)+ηL′(0)+12η2L′′(0)L(0) + ηL'(0) + \tfrac 1 2 η^2 L''(0). Here, the derivatives L′L' and L′′L'' are computed from the derivatives of the logits (using the outer approximation of the Hessian of the loss). We observe that both methods give very similar values of ηη. Finally, these estimated ηη are used to slightly increase or decrease the learning rate of an existing schedule. The method is evaluated on Cifar10 and Cifar100 datasets for training Resnets, where they decrease the loss faster than the schedule that is perturbed and increase monotonicity. For Cifar10 it also leads to a small improvement of test accuracy, but in Cifar100 test accuracy remains the same.
Nov 3, 2026

ZEMA: confidence-calibrated signed descent with only one state

Recent work characterizes the Adam optimizer as sign descent modulated by gradient uncertainty: the update is the sign of the batch gradient, scaled by how strongly the batch supports that sign. We apply this view directly and introduce ZEMA (Z-score Evidence Momentum Adaptation), which measures that support with a per-coordinate zz-score computed from the per-example gradients in the current batch, converts it into a sign probability, and smooths the resulting update with a single exponential moving average. Because the probability is formed before smoothing rather than after, ZEMA keeps one state per parameter instead of Adam's two, at a 4.64.6 increase in per-step time; the per-example variance it requires can also be estimated from a small fraction of the batch. In fine-tuning and pretraining experiments, ZEMA is competitive with Adam, reduces the variability of the validation loss, and in some settings recovers the sign of the full-dataset gradient more consistently. We close with two directions this opens: extending confidence adaptation beyond the sign geometry, to methods such as Muon, and to differentially private training.
Oct 31, 2026

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent γ∈(1/2,1)γ\in(1/2,1), a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order n1/2−γ+nγ−1n^{1/2-γ}+n^{γ-1} in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of γγ. The nonlinear bias contributes n1/2−γn^{1/2-γ} even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order n−(1−γ)/2n^{-(1-γ)/2} for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error ε\varepsilon on this example takes order ε−4\varepsilon^{-4} iterations for the best choice γ=3/4γ=3/4. Achieving both Gaussian approximation and relative mean variance-estimation errors at most ε\varepsilon uniformly over the model class requires at least order ε−6\varepsilon^{-6} iterations for every fixed γγ.
Oct 30, 2026

Stochastic learning flow: moment equations for stochastic gradient descent at finite step size

Analytical theories of learning in deep networks often assume gradient flow, discarding the finite step size and batch noise of stochastic gradient descent (SGD). Starting from the discrete update, we derive continuous-time equations for the mean and covariance of the parameter distribution under a Gaussian closure for a general stochastic learning, to first order in the learning rate ηη. Applying these stochastic learning flow (SLF) equations to SGD, we show that the mean descends an effective loss regularized by the covariance and loss curvature, while the covariance, unlike in stochastic differential equation approximations, becomes unstable at curvature 2/η2/η. In SGD ensembles of linear and nonlinear networks, SLF predicts learning curves and mean trajectories more accurately than gradient flow and captures the covariance dynamics, failing where the parameter distribution becomes strongly non-Gaussian. In the full-batch limit, the edge of stability corresponds to a stationary point of the coupled sharpness-covariance dynamics, recovering self-stabilization and central flow, and batch-to-batch curvature fluctuations lower this threshold under SGD.
Oct 30, 2026

Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization

This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension d≥N+1d\geq N+1, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of NN stepsizes in [0,1.5]N[0,1.5]^N. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least Ω(1/N)Ω(1/\sqrt{N}), our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.
Oct 30, 2026

Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates

Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
Oct 29, 2026

Where, When, and How Many Bits? Scaling Laws for SGD with Stochastic Rounding

Low-precision training reduces computation but introduces additional rounding error. We theoretically study how stochastic rounding (SR) affects prediction risk as model size, training time, and precision change. We consider a two-layer linear network with a fixed random first layer, trained by mini-batch SGD on fresh Gaussian data with power-law spectra. At each SGD step, the features used in forward and backward computations are rounded independently. We prove matched upper and lower bounds on prediction error for the final model and for uniform parameter averaging, with general learning-rate and precision schedules chosen before training. For fixed precisions and constant learning rates with parameter averaging, we derive how the smallest prediction error decreases with compute, and we identify model sizes and training times that achieve this optimal-compute scaling. Rounding only the forward features preserves the compute scaling of exact arithmetic, while rounding backward features changes it. Averaging parameters can change which computation needs higher precision and when higher precision is useful. Our results also give bit requirements for a given accuracy tolerance and show how backward rounding can change learning-rate schedule design. At a fixed compute budget, lower precision can improve prediction when the benefit of a larger model or longer training outweighs the additional SR-induced error. Model simulations illustrate these tradeoffs, and experiments with an MLP and a small transformer examine rounding choices beyond the theoretical model.
Oct 29, 2026

Implicit Bias of (Stochastic) Gradient Descent on Deep Linear Diagonal Networks

Modern machine learning models are often overparameterized, i.e., have more parameters than training data. This typically implies that the loss function admits multiple minimizers so that training methods (and their hyperparameter choices) have significant influence on the computed solution. We study this so-called implicit bias phenomenon in the context of training deep linear diagonal networks. Previous work has shown that the gradient flow for learning such networks converges to (almost) sparse solutions when initialized small. For an arbitrary number of layers, we extend this analysis to the practically more realistic (stochastic) gradient descent iterations. Our approach identifies (stochastic) gradient descent as a perturbed (stochastic) mirror gradient descent. This allows us to establish convergence and characterize the limiting solution, relating it to weighted ℓ1\ell_1-minimization. Moreover, we provide sufficient conditions on the step sizes and quantify the influence of the step sizes on the implicit bias.
Oct 28, 2026

Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

The empirical success of matrix-aware optimizers, such as Muon (Jordan et al., 2024) and Shampoo (arXiv:1802.09568), highlights the potential of non-Euclidean geometry for deep learning, including large language model (LLM) training. Despite this progress, the theoretical understanding of stochastic optimization in general normed spaces remains limited, particularly in distributed settings. We analyze minibatch stochastic gradient descent (SGD) for smooth nonconvex optimization with respect to an arbitrary norm on a finite-dimensional space. Using the framework of κκ-regular normed spaces (arXiv:0809.0813), we derive high-probability oracle complexity bounds under a light-tail condition stated directly in the dual norm induced by the update norm. The bounds make the dependence on geometry explicit through the regularity constant κκ of the dual space. In the Euclidean case, our bound recovers the standard minibatch SGD rate up to logarithmic factors. For some non-Euclidean geometries and noise models, it is sharper than bounds obtained by converting a Euclidean noise assumption, reducing a linear dimension dependence to a logarithmic one. Building on this framework, we introduce Rennala NSGD, a semi-asynchronous distributed algorithm, and establish wall-clock time complexity guarantees under fixed, heterogeneous worker computation times. In the Euclidean case (κ=1κ=1), our bound matches the parameter dependence of classical Rennala SGD up to logarithmic factors.
Oct 28, 2026

B2P-Corr: Batch-to-Population Gradient Estimators for Non-Decomposable Correlation Losses

Correlation metrics such as the Pearson Correlation Coefficient (PCC) and Concordance Correlation Coefficient (CCC) are standard regression metrics and learning objectives, but their non-decomposable nature poses a challenge for stochastic optimization. Since these metrics depend on dataset-level moments (mean, variance, covariance), naive mini-batch training with local statistics yields biased, high-variance gradients whose expectation does not align with the population gradient. To bridge this batch-to-population'' (B2P) gap, we propose B2P-Corr, a novel framework that transforms correlation objectives into decomposable pseudo-losses driven by lightweight global moment sketches''. We introduce two efficient variants: B2P-EMA, which utilizes exponential moving averages and stop-gradient operators to ensure asymptotic gradient tracking with O(B)O(B) cost (BB is batch size); and B2P-U, which uses sampled cross-batch U-statistic estimators and a reservoir-based stabilization with an O(B)O(B) implementation. Theoretically, we quantify the O(B−1)O(B^{-1}) bias of naive mini-batch optimization, prove a moving-target tracking result for B2P-EMA under a fast-sketch / slow-parameter regime, and provide an idealized control-variate analysis for B2P-U. Experiments on two synthetic and three real-world datasets demonstrate B2P-Corr achieves stable optimization and higher correlation than naive mini-batch optimization with negligible overhead.
Oct 27, 2026

Finite-step statistical mechanics of scale-invariant learning: spectral equations of state and curvature transport

Stationary learning admits an ideal-gas description under restrictive noise assumptions. In neural networks whose gradient noise departs from these assumptions, however, an entropy-scaling relation resembling a Maxwell relation remains approximately valid. We ask which thermodynamic-looking relations follow from scale symmetry rather than equilibrium, and how departures from the ideal-gas description can be quantified, for discrete stochastic gradient dynamics with memory. An exact rescaling of trajectories explains the entropy relation without assuming thermal equilibrium. Within a local harmonic approximation, self-adjusting weight norms yield a spectral equation of state whose virial coefficients are set by moments of the curvature spectrum, and coupled parameter groups can sustain stationary probability currents. Our central result beyond this approximation is an exact curvature-transport identity. Together with a finite-step loss balance, it decomposes corrections to the harmonic fluctuation relation into measurable curvature changes, finite-step remainders, gradient-memory correlations and finite-window drift terms. A related displacement-weighted curvature change provides a diagnostic of the arrow of time; its mean and second moment give a lower bound on the relative entropy between forward and reversed state pairs. We also calculate the activation-boundary contribution to curvature for rectified teacher-student networks with Gaussian inputs. Tests in sphere models, teacher-student networks and convolutional networks on CIFAR-10 and CIFAR-100 support the transport description and identify limits of the harmonic and cubic-remainder approximations. These results separate symmetry-based relations from equilibrium assumptions and provide quantitative diagnostics of nonideal fluctuations in learning dynamics.
Oct 24, 2026

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

When training stops at a data-dependent time, a guarantee for the returned model must hold at all times simultaneously. We study the last iterate of clipped SGD on smooth convex objectives under heavy-tailed stochastic gradients with a bounded central ppth moment, 1<p≤21<p\le2. With a known horizon TT, clipped SGD reaches the optimal last-iterate rate O(T−αp)O(T^{-α_p}), where αp=(p−1)/pα_p=(p-1)/p (Liu, 2026; Jiang et al., 2026). Without a known horizon, Chezhegov et al. (ICLR 2026) obtained the time-uniform rate O~(t−2(p−1)/(3p))\tilde O(t^{-2(p-1)/(3p)}) and conjectured that a better schedule reaches the optimal rate. We show that for clipped SGD, and more generally for every rule whose iterate does not advance on rounds without new gradient information, the optimal time-uniform rate is O~(t−βp)\tilde O(t^{-β_p}), where βp=2(p−1)/(3p−1)β_p=2(p-1)/(3p-1). Our deterministic schedule for clipped SGD uses neither a horizon nor a confidence input and attains O~(t−βp)\tilde O(t^{-β_p}) at all times simultaneously, and hence almost surely. Conversely, no such rule attains O~(t−r)\tilde O(t^{-r}) at all times for any r>βpr>β_p; for clipped SGD, this holds even with adaptive, randomized step sizes and clipping thresholds. Under finite variance, the known-horizon, optimal time-uniform, and previous time-uniform exponents are 1/21/2, 2/52/5, and 1/31/3. Since βp<αpβ_p<α_p, the conjecture, which holds with a known horizon, fails without one. By contrast, an update that queries gradients at the running average can advance the iterate on rounds without new gradient information and attains O~(t−αp)\tilde O(t^{-α_p}) at all times. Memory alone does not suffice: heavy-ball momentum with geometric forgetting and polynomially bounded step sizes cannot improve on the exponent βpβ_p.
Oct 23, 2026

Sharpness-aware Orthogonalized Momentum Algorithms

Adversarial sharpness penalty per iteration of a base optimizer, known as sharpness-aware minimization (SAM), is an accepted technique to improve generalization in deep learning. Recently, Muon has emerged as a dominant optimization algorithm for training large language models (LLMs). It achieves lower sample complexity for heavy-tailed gradient updates - a phenomenon common in LLM training. However, sharpness penalties with Muon updates are yet largely unexplored in the literature. Moreover, the behavior of SAM under heavy-tailed noise is unknown both theoretically and empirically. A potential reason for this gap is the additional cost of extra gradient computation per iteration for penalty perturbations in SAM, which becomes prohibitive for LLMs. This paper introduces Sharpness-aware Orthogonalized Momentum Algorithm (SOMA) to combine a computationally efficient and theoretically grounded perturbation scheme with the Muon algorithm. The key idea is to use stale (purely) stochastic gradient noise for adversarial perturbations. Theoretically, we show that SOMA's sample complexity is invariant to the perturbation direction. We provide explorations and insights into SOMA's robustness to heavy-tailed gradient noise. We extensively explore SOMA's efficacy in (a) mitigating quality degradation due to post-training quantization, and (b) catastrophic forgetting during fine-tuning of LLMs.
Oct 20, 2026

Convergence of stochastic gradient descent for learning linear neural networks

Stochastic gradient descent (SGD) is the cornerstone of modern deep learning, yet its theoretical convergence properties remain poorly understood in non-convex settings. To address this gap, we study SGD dynamics in deep linear neural networks - simplified models that retain key non-convex characteristics while remaining analytically tractable. Building on recent results for gradient descent, we extend convergence guarantees to SGD under regularized squared loss. We establish almost sure boundedness of SGD iterates. Using the framework of asymptotic pseudotrajectories from stochastic approximation theory, our analysis establishes then, for both deterministic and adaptive step-size choices, convergence of SGD to the set of critical points under mild conditions (without relying on Lipschitz properties or whitened data). To our knowledge, this is the first work providing almost sure convergence guarantees for SGD in deep linear networks, bridging the gap between theoretical optimization and practical stochastic training.
Oct 20, 2026

Weak-LαL^α Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

Gradient clipping is a key tool for obtaining high-probability convergence guarantees for stochastic first-order methods under heavy-tailed noise. Existing analyses typically assume a bounded central moment of order α∈(1,2]α\in(1,2], which excludes distributions with tails of order u−αu^{-α} at the critical exponent. In this paper, we consider smooth convex optimization under affine heavy-tailed noise, whose scale may grow with the gradient norm. We derive high-probability convergence guarantees for clipped SGD (Clip-SGD) and its accelerated variant Clip-SSTM under a weak-LαL^α tail condition, which is strictly weaker than the corresponding moment bound. For 1<α<21<α<2, the clipping bounds have the same powers of the clipping level as in the moment case, and both methods attain the additive stochastic rate K−(α−1)/αK^{-(α-1)/α}. The gradient-dependent noise contributes a faster-decaying term of order K−2(α−1)/αK^{-2(α-1)/α}, up to logarithmic factors. At α=2α=2, we characterize the additional logarithmic factor on the Lorentz scale and establish its necessity for the additive error at fixed confidence. We also analyze Clip-SGD with prescribed clipping levels and derive finite-horizon guarantees for reaching a neighborhood determined by the clipping bias. For additive noise, matching lower bounds show that this neighborhood is unavoidable, up to constants and the natural error cap. Numerical experiments with Pareto noise illustrate the theoretical results.