cs.LGSep 30, 2026
SaveExact information accounting for SGD methods
Abstract
As an alternative to the standard geometric analyses, we give an exact, information-theoretic analysis of stochastic gradient descent (SGD) and its variants. We show that a preconditioned SGD step is the posterior-mean update of a Gaussian Bayes model, and that its one-step regret splits into an intrinsic-time cost and a change in comparator information. The split extends to an identity for the objective itself. Convex convergence, strict-saddle-point escape, the link between flatness and generalization, the standard learning-rate schedules, adaptive optimizers, and the noisy, momentum, heavy-tailed, and gradient-free variants of SGD each correspond to a term or a special case of this identity. We measure its terms on synthetic and real training runs. On real networks it attributes the slack of classical convergence bounds to the terms their derivations drop and separates optimizers that reach the same training loss. That separation follows the number and consistency of their steps. Its relation to which of them generalizes better differs between networks. For gradient-free SGD the identity determines how a curvature preconditioner should enter the update. The sharpness-based generalization certificate it yields, with a data-independent isotropic prior, is vacuous at network scale unless the curvature spectrum is nearly flat across all parameters.
Figures & tables
Figure 1: At a matched training loss the information ledger separates five optimizers by where their losses differ by less than . In the learning-rate and width sweeps the intrinsic-time fraction follows the shape of the path. (a) Five optimizers stopped at a common training loss, with a spread in training loss and a spread in test error. Each marker is one seed. (b) A learning-rate sweep at a fixed budget: the test error (blue) is smallest at , while the fraction (vermillion) rises with as larger steps make the path less consistent. (c) A width sweep under label noise: the test error’s double-descent peak sits at the interpolation threshold (dotted, training points), where the fraction has no feature.
| Optimizer | Choice of | Information-ledger term it incurs |
|---|---|---|
| Plain SGD | fixed , no forecast | in fixed -geometry |
| Natural gradient † [ 2 ] | , the Fisher matrix | Fisher-metric intrinsic time |
| K-FAC † [ 68 ] , Shampoo † [ 33 ] | block-structured | per round |
| Muon † [ 46 ] | momentum buffer , orthogonalized (Newton–Schulz) | , the nuclear norm; the Newton–Schulz iterate is a deliberate approximation to this |
| AdaGrad-Norm [ 26 ] | (the scalar variant; per-coordinate AdaGrad instead sets ) | terminal-remainder-saturating square-root clock |
| RMSProp † [ 98 ] , Adam † [ 51 ] | , score , fixed |
Table 1: Every SGD-class optimizer is one reading of the same information ledger. Each row gives an optimizer’s choice of preconditioner , forecast , and schedule , and the term incurred by that choice. Rows marked have a time-varying , for which the pathwise account is exact only with the metric-drift term of ( 87 ) included alongside . Derivations are in § 5.2 , § 5.3 , § 5.4 , and § E.3 .
Figure 2: On real networks the information ledger attributes each classical envelope’s slack to the terms dropped by its derivation. It also separates optimizers that reach the same training loss: their intrinsic-time fractions differ by more than an order of magnitude. (a) Comparator information still to be transported at prefix , as a share of the linearized envelope . (b) Cumulative Bregman remainder over the same envelope; below zero the objective-level envelope does not apply. AdamW stays within of zero on both networks. (c) Intrinsic-time fraction at the deepest training loss reached by every optimizer. Solid lines ResNet-20, dashed lines the character-level language model (char LM); each line is a median over seeds.
Figure 3: The intrinsic-time inflation and the strict-saddle-point escape times track their closed forms. (a) Realized inflation against inverse batch size on linear regression with mini-batches drawn without replacement from examples; the fit proportional to solid and the plain law dashed. (b) Mean escape iteration against the leading-order time ( 37 ) on the strict saddle point of ( ), started from ; deterministic runs filled, their constant ratio solid, and equality dotted. Here in ( 37 ) is , so runs with the same share a leading-order time. Error bars are standard errors over seeds.
Figure 4: On a real objective with a wide curvature spread, a curvature probe drawn into the sampling covariance speeds zeroth-order search more than 50-fold, while applied to the step it makes no progress. (a) Function queries to close of the initial suboptimality of seven-class logistic regression on principal components of Covertype, at three spreads of the Hessian diagonal; small markers are seeds, bars are medians, and open markers on the dashed line did not reach the target within the budget. (b) Top Hessian eigenvalue against the train–test gap at the end of training, Wide-ResNet-28-4 on CIFAR-10, one marker per run; circles batch , squares batch . Sharpness tracks the generalization gap only along the batch axis. (c) Final test accuracy of ResNet-20 on CIFAR-10 against the share of logged steps on which the pressure-cycled controller’s stall signal is on, one marker per seed. The stall signal responds to mini-batch noise.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Queries to the target grow far more slowly with the condition number when the probe captures the curvature. (a) Probes on the axis-aligned quadratic drawn from the isotropic covariance, from an AdaGrad accumulator and from the oracle covariance . The accumulator does not identify the curvature. (b) Probes that apply the preconditioner to the step. The oracle is on the axis-aligned quadratics and on the rotated ones. The probes’ curvature sweeps count toward their queries. On rotated quadratics only the full-matrix probe captures the curvature. Bars are medians over seeds of the function-evaluation pairs in (a) and the function queries in (b) to , or to on the Rosenbrock valley. A pale dashed bar marks a sampler that reached the target on no seed and ends at the budget. A fraction at the foot of a bar is the share of seeds that reached the target, where that share is below one.
Figure 6: At fine-tuning scale the probe allocation that follows the curvature ends at the lowest validation loss. Validation cross-entropy of the fine-tuned encoder after queries for four per-group probe scales that share one learning rate and one total probe energy. Open circles are seeds, filled circles their mean, and bars the percentile-bootstrap interval of the mean. The dashed line is the cross-entropy before fine-tuning.
| Noise or momentum class | How it enters the information ledger |
|---|---|
| Mini-batch score noise, post-step Gaussian, Langevin thermal | one additive quadratic entry each. The expected ledger depends on the perturbation only through its covariance, but the three attach at different places and scale differently in : score noise inflates , post-step injection adds a channel term, and the Langevin thermal entry is (§ F.3 ) |
| Finite-cumulant non-Gaussian (Rademacher, Laplace, mixtures) | the Gaussian quadratic is replaced by the cumulant-generating function (Proposition F.8 ), of which it is the second-order term |
| Heavy-tailed and -stable | the pathwise and channel relative-entropy identities still hold. The conditional-expectation entry is finite only after truncation, robustification, or a fractional or jump regime |
| State-dependent (Riemannian) preconditioning | a metric-drift term with an Itô correction |
| Phase-space momentum: stochastic-gradient Hamiltonian Monte Carlo (SGHMC), underdamped Langevin, thermostats | conservative Hamiltonian transport plus an Ornstein–Uhlenbeck thermostat channel; SGHMC’s friction is the covariance-balance condition. Heavy-ball is instead a linear phase-space recursion (Proposition F.11 ) and Nesterov a lookahead-transport correction |
Table 2: Every noise class and every momentum scheme resolves to one explicit entry of the information ledger.
Figure 7: The information ledger separates the optimizers that keep a momentum buffer from those that do not. (a) Intrinsic-time fraction ( 13 ) at the end of the run, in the Euclidean metric against the final iterate. (b) Share of the logged grid points at which the cumulative Bregman remainder is negative. There the objective-level envelope does not apply. (c) Max/min ratio across optimizers at the deepest training loss reached by every optimizer of a network. The fraction spreads by an order of magnitude on ResNet-20 and the char LM, where the training and test losses spread by less than . Markers are medians over seeds. The vision transformer runs only AdamW, Muon, SOAP and Sophia-G.
Figure 8: Further terms of the information ledger behave as its identities imply. (a) Realized regret over over the late half of each run, for noisy SGD on quadratics with and , by condition number and step size. The dashed line is one half. Error bars are standard errors over seeds. (b) The unstable clock and the total clock at escape from strict saddle points in with , three noise scales and two initializations, each divided by its mean over the runs. CV is the coefficient of variation. (c) Realized over deterministic intrinsic time for SVRG on logistic regression (UCI Adult and Covertype) against its inner-loop length, with SGD dashed. Error bars are bootstrap intervals. (d) Per-step intrinsic time for logistic regression under Student- gradient noise over steps, for plain SGD, clipping and Catoni’s score. Circles are seeds, bars their mean, and each percentage is the change of the mean against SGD. (e) The realized noise-energy entry on a quadratic against the stability index of -stable noise: its 99th percentile, and its mean without robustification, under Catoni’s score and truncated at .
Figure 9: Scaled coordinate by coordinate, the gradient noise of a character-level transformer at batch 32 is not heavy-tailed. (a) Hill tail index at a tail fraction for three architectures, one marker per seed. Open circles pool the raw noise over coordinates, and crosses pool Gaussian noise with the measured per-coordinate scales. Filled circles pool the noise after each coordinate is divided by its own robust scale, with bars over tail fractions from to . Lines mark the standardized Gaussian and Student- (1.5) controls and index . (b) Ratio of the noise variance along the mean-gradient direction to its diagonal approximation, for the real noise and for Gaussian noise with the same covariance. The dashed line is equality.
Figure 10: The intrinsic clock and its step-weighted form seldom fit or forecast the loss better than the step counter. Each forecast estimates the step at which the run reaches a target loss. In (b) and (c) the clock is the step-weighted sum . (a) Completed runs of the curriculum sweep: of the two log-loss fits versus the defect of regressed on . Open markers are runs that neither fit describes with . (b) Held-out prefix instances: the disagreement of the two forecasts at a common window versus the defect on the prefix. (c) The difference in median forecast error , clock minus step counter, with each forecast at its own fit fraction; below zero the clock is closer to the truth. Bars are paired intervals, hidden where narrower than the marker.
Figure 11: The pressure-cycled controller finds the deep basin of a synthetic potential on every seed but slows or degrades training on real networks. (a) Best-iterate on the two-basin potential for fixed-step and constant-Langevin SGD and for the controller. The dashed line is the target. (b) Steps to grok for AdamW with and without the escape, and for SGD at a fixed and at a pressure-target step. (c) Best validation accuracy of the vision transformer on CIFAR-10 for the same four. (d) Steps to grok for AdamW without kicks and with isotropic or curvature-targeted kicks. Markers are seeds and bars their means. Color gives the base optimizer, and an open triangle marks a run with the escape phase.
Figure 12: Sharpness tracks the generalization gap with the sign the flatness bound implies along the batch axis, but not across optimizers. Each entry is the Spearman correlation of a sharpness statistic with the train–test gap or with the test error over the endpoints of one sweep. Its color is that correlation times the sign the bound implies ( for and , for ), so blue agrees with the bound and red opposes it. Gray entries were not measured. On ResNet-20 at epochs the gap is the final test loss minus the last logged training loss. is the Lanczos rank.