PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact information accounting for SGD methods

Akshay Balsubramani

arXiv:2610.00446v1cs.LGcs.ITmath.ITmath.OCstat.ML

TL;DR

Geometric SGD analyses discard information at each round, leaving an incomplete account of how realized updates relate to regret. This paper recasts preconditioned SGD as Gaussian Bayesian updating and derives an exact information balance. On real networks, the balance identifies terms behind classical-bound slack and distinguishes optimizers at matched training loss, while its sharpness-based certificate has a network-scale limitation.

  • Problem

    Standard geometric analyses of SGD lose information each round, motivating an exact account of the update and its relation to regret.

    Source: §1 · p. 1

  • Method

    The paper specializes an adaptive Bayes identity to Gaussian posteriors and local gradient scores, yielding an exact information ledger for SGD and its variants.

    Source: §1 · p. 1, §8 · p. 19

  • Results

    On real networks, the ledger attributes classical convergence-bound slack to dropped terms and separates optimizers reaching the same training loss by step count and consistency; its relation to generalization differs between networks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For gradient-free SGD, the sampling covariance should carry a query-only curvature probe: this recovers nearly all the gain of an oracle Hessian-diagonal preconditioner, unlike applying that preconditioner to the step.

    Source: §1 · p. 2

    With a data-independent isotropic prior, the sharpness-based certificate is vacuous at network scale unless curvature is nearly flat across all parameters.

    Source: §6.2 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

The paper replaces geometric SGD analyses with an exact Bayesian information balance for realized updates. It uses that balance to reinterpret optimizer variants and training behavior, while identifying limits of its sharpness-based generalization certificate.

Information ledger framework

  • The information ledger interprets preconditioned and adaptive SGD as Gaussian posterior-mean updates, splitting one-step excess composite loss into intrinsic-time cost and comparator-information change.Classical convergence results follow when assumptions permit dropping selected terms; retaining a Bregman remainder yields an objective-level identity.Source: §1 · p. 1

Optimizer variants and schedules

  • The same accounting organizes adaptive, momentum, and variance-reduced optimizers, learning-rate schedules, and cyclic descent-and-escape schedules.Variance reduction is read as intrinsic-time reduction; the cyclic schedule alternates information-gain steps with escape steps when realized decrease per unit intrinsic time stalls.Source: §1 · pp. 1–2

Curvature and generalization

  • Curvature enters through a log-determinant Hessian-spectrum penalty, but the sharpness-based PAC-Bayes certificate with a data-independent isotropic prior is vacuous at network scale unless curvature is nearly flat across parameters.Near a strict saddle, negative-curvature components of comparator information are amplified per step and receive additive noise injection.Source: §1 · p. 2

Noise and momentum

  • Finite-cumulant perturbations add a cumulant entry without changing the other ledger terms, while heavy-tailed noise and phase-space momentum admit corresponding information-accounting descriptions.Phase-space momentum resolves into conservative transport plus a thermostat channel.Source: §1 · p. 2

Gradient-free SGD

  • For gradient-free SGD, the sampling covariance acts as an implicit preconditioner, and a query-only curvature probe in that covariance recovers nearly all the gain of an oracle Hessian-diagonal preconditioner.Applying the same preconditioner directly to the step makes no progress on the reported real objective.Source: §1 · p. 2

Empirical measurements

  • On real networks, the ledger attributes slack in classical convergence bounds to dropped terms and separates optimizers reaching the same training loss by step count and consistency.The separation’s relation to generalization differs between networks.Source: §1 · p. 2

2 Related work

The related work connects the ledger to stochastic approximation, Bayesian interpretations of optimization, information-theoretic generalization, sharpness, and modern optimizers. It distinguishes this paper’s exact, realized-path accounting from prior approximate or differently scoped analyses.

Stochastic approximation

  • Classical stochastic approximation studies gradient alignment, variance, and averaging; the ledger maps these to comparator-information change, intrinsic time, and a weighted-average identity.Time-uniform guarantees and confidence sequences provide related rate analyses [3] [4] [36] [57].Source: §2 · p. 2

Bayesian interpretations

  • Prior Bayesian accounts recover optimizers through approximations, stationary distributions, or diffusion limits, whereas this identity is exact on each realized discrete trajectory for fixed covariance and any preconditioned first-order step.An exact earlier equivalence is specific to Fisher-preconditioned online stochastic natural gradient [77].Source: §2 · p. 3

Generalization and sharpness

  • Information-theoretic generalization bounds and sharpness analyses are complementary: the ledger supplies an optimization-side account, while its terminal Gaussian relative entropy serves as PAC-Bayes complexity.The paper also expresses saddle-point behavior as information amplification plus noise injection, without claiming a sharper escape rate.Source: §2 · p. 3

Optimizers and schedules

  • Many adaptive optimizers and schedules can be read through choices of preconditioner, gradient forecast, and learning-rate schedule; minimizing expected intrinsic time connects preconditioner choice to covariance estimation.The discussion relates these choices to methods including Adam, RMSProp, Shampoo, and optimistic learning.Source: §2 · p. 3

3 Preliminaries

The preliminaries establish the stochastic-gradient setting, Gaussian relative-entropy geometry, and the Bregman remainder used to connect linearized scores with objective loss.

Stochastic optimization setup

  • For stochastic optimization, the conditional mean of the sampled gradient is the objective gradient, and its conditional covariance records gradient noise.The notation also distinguishes the history before each stochastic gradient draw.Source: §3 · p. 3

Gaussian geometry

  • Equal-covariance Gaussian distributions centered at the comparator and iterate have relative entropy equal to their squared distance in the inverse-covariance metric.The Gaussian prior covariance therefore sets the geometry used to measure comparator information.Source: §3 · p. 3

Bregman remainder

  • The first-order Bregman remainder is the gap between a function value and its linearization; it is nonnegative for convex functions and signed for nonconvex ones.In the nonconvex case it records curvature.Source: §3 · p. 4

SGD update

  • Preconditioned SGD updates the iterate by subtracting the learning rate times the preconditioned gradient; ordinary SGD uses a scalar identity covariance.For scalar covariance, the effective step size is the learning rate multiplied by that scalar.Source: §3 · p. 4

Local score

  • The Bayesian machinery uses the affine local score, which bounds convex round-loss regret but remains an exact trajectory-level bookkeeping identity even when nonconvexity removes that inequality.The convex subgradient inequality supplies the regret connection; it is not assumed for the nonconvex identity.Source: §3 · p. 4

4 The SGD information ledger

The section derives SGD’s exact information accounting from Gaussian Bayes updates, then extends it to changing covariance, objective loss, and path-based intrinsic-time analysis. These components explain how optimizer trajectories and stochastic gradients enter the ledger.

4.1 SGD as Gaussian adaptive Bayes

  • Reweighting a Gaussian posterior by the local linear gradient score preserves its covariance and shifts its mean by the preconditioned SGD step.The update’s centered cumulant cost is a quadratic in the observed gradient, and the Gaussian prior also serves as a comparator decoder and regularizer.Source: §4.1 · p. 4

4.2 The one-step identity

  • For any comparator, one-step inner-product regret equals intrinsic-time cost plus the change in Gaussian comparator information, without convexity or smoothness assumptions.The identity is the Gaussian specialization of an adaptive-Bayes balance [5].Source: §4.2 · p. 5

4.3 Covariance drift for adaptive preconditioning

  • Changing an adaptive preconditioner’s covariance adds an information term that measures the cost or benefit of changing covariance geometry..Source: §4.3 · p. 5

4.4 Objective-level identities

  • The objective-level identity retains the Bregman remainder: it is a nonnegative curvature gain for convex losses and signed curvature information for nonconvex losses.Under unbiased mini-batch noise, the stochastic component of intrinsic time scales with gradient covariance; larger batches reduce that component.Source: §4.4 · p. 6

4.5 Intrinsic time

  • Intrinsic time forecasts loss decay like iteration count when it grows as a power of time; across 150 curriculum-sweep runs, log intrinsic time is affine in log time within 0.4% of its variance.Across real-data training prefixes, the log step-weighted clock is affine in log time within 4%.Source: §4.5 · p. 6
  • At matched training loss, five optimizers span 31× in intrinsic-time fraction despite a 1.04× training-loss spread and a 1.53× test-error spread.The fraction rises with learning rate as steps become less consistent, but has no feature at the width-sweep double-descent peak.Source: Figure 1 · p. 7
  • The intrinsic-time fraction measures path shape through step count and consistency, separating trajectories that reach the same loss even when their achieved losses do not.Across a learning-rate sweep it rises monotonically through the test-error optimum, but shows no feature at the double-descent peak.Source: §4.5 · p. 7, Figure 1 · p. 7
  • For Gaussian SGD, intrinsic and relaxed clocks coincide and reduce to cumulative preconditioned squared-gradient quantities; for general exponential-family posteriors, they diverge.Intrinsic time can grow linearly, sublinearly, or saturate, corresponding to different gradient-decay regimes.Source: §4.5 · p. 7

5 Classical results as readings of the information ledger

This section interprets classical convergence bounds and optimizer variants through an information ledger, accounting for comparator information, intrinsic time, curvature, schedules, gradient estimates, and prior geometry. It extends this framing to function-value gradient-free updates and nonconvex objectives, including curvature-sensitive sampling, direction-wise information dynamics, and saddle escape and benign convergence in terms of intrinsic time.

5.1 Convex convergence

  • Classical convex bounds follow by dropping terminal comparator information and the nonnegative curvature gain from the weighted identity.The identity also exposes these as separate diagnostic quantities, so runs with identical worst-case bounds can have different decompositions. Under the Robbins–Monro schedule, expected comparator information is O(log T/(µ^2 T)); retaining the loss term gives an O(1/(µ^2 T)) distance rate, while the last-iterate objective rate is O(log T/(µ T)).Source: §5.1 · p. 8
  • On quadratics, curvature gain is half the linearized regret, while shifting comparators add a path-length penalty to the exact tracking identity.For noisy quadratics at stable step sizes, the regret-to-bound ratio lies between 0.492 and 0.500, up to the terminal-information share and a martingale term.Source: §5.1 · pp. 8–9

5.2 Learning-rate design from intrinsic time

  • Learning-rate schedules balance comparator information against intrinsic time, with AdaGrad- and Adam-style clocks and pressure-target updates as ledger-based constructions.A pressure target below current progress yields the Polyak step; cycling through Chebyshev-root reciprocals gives limiting per-round contraction ρ_cyc = (√κ − 1)/(√κ + 1) when the quadratic spectrum is known.Source: §5.2 · p. 9

5.3 The stochastic-gradient information ledger

  • The stochastic ledger separates gradient-noise martingales from intrinsic-time inflation, while variance reduction lowers the clock and forecasts can reduce or sign-change step costs.Biased estimates contribute a predictable bias term, EMA bias correction cancels its leading part, and Catoni-robustified scores keep the clock finite under heavy-tailed gradients; momentum enters as a predictable forecast.Source: §5.3 · p. 10

5.4 Preconditioning as prior geometry

  • Preconditioning is prior geometry: a Gaussian covariance gives the update metric and its intrinsic time, while mirror descent measures time by divergence between consecutive iterates.The mirror identity is exact for unconstrained updates and affine constraint sets in the mirror domain; other Bregman projections leave only a one-sided account. Choosing a preconditioner by minimizing intrinsic time requires fixing its scale.Source: §5.4 · p. 11

5.5 Optimizer families as readings of the information ledger

  • SGD-class optimizers are readings of one ledger, determined by their preconditioner, forecast, and schedule, with metric drift required for time-varying preconditioners.Their recorded intrinsic time uses the score actually played in the update, including moment estimates in first-moment methods.Source: §5.5 · p. 11, Table 1 · p. 12

5.6 Zeroth-order optimization: the gradient-free information ledger

  • For gradient-free updates, the ledger remains algebraically exact with a finite-difference score, and probe covariance determines the expected preconditioned step.Gaussian probes give the finite-smoothing identity for the smoothed objective, whereas other probe laws need not; isotropic sampling is unbiased for the gradient, while covariance B realizes metric B without explicit matrix multiplication or extra function queries.Source: §5.6 · pp. 11–12
  • The zeroth-order intrinsic-time cost is d + 2 times the first-order cost, expressing the dimension penalty in the information ledger.The passage identifies this factor as the ledger form of the Θ(d) slowdown of gradient-free methods.Source: §5.6 · p. 13
  • On quadratics, sampling covariance C ∝ H^-1 contracts expected error equally in every direction regardless of condition number, and function-value probes can realize this covariance.Probing from a preconditioner and scaling the step by it give the same expected step, so their second moments distinguish the alternatives.Source: §5.6 · p. 13

5.7 Nonconvex objectives and saddle point information

  • For nonconvex objectives, the identity holds for linearized regret, but signed curvature information means that regret need not upper-bound objective regret.The subgradient inequality that would provide the upper bound does not generally hold for nonconvex functions.Source: §5.7 · p. 13
  • At quadratic critical points, stable directions contract for 0 < ηλ_j < 2 while negative-curvature directions amplify information distance by (1 + ηγ)^2; noise injects η^2Var(ξ_t,j)/2 per step.Without noise, flat directions are neutral and incur no information cost; with noise, they diffuse.Source: §5.7 · p. 13
  • Strict-saddle escape requires an unstable-direction displacement supplied initially or by noise; the larger displacement sets leading-order escape time, and negative-curvature intrinsic time predicts synthetic escapes better than total gradient norm [20].The information identity does not require Hessian-Lipschitz bounds, which enter when deriving explicit escape-time guarantees with dimension dependence.Source: §5.7 · pp. 13–14
  • For an L-smooth objective satisfying the stated condition, fixed-step descent with η ≤ 1/L gives exponential objective-gap decay at rate ημ; smoothness cannot be dropped.Without smoothness, F(θ) = |θ|^3/2 can stall in a two-cycle under fixed-rate gradient descent.Source: §5.7 · p. 14
  • The ledger defines weighted information complexity, trajectory intrinsic-time measures, and policy-optimized surface complexity; for quadratic fixed-rate descent, the latter has a bound combining posterior-information cost, prior distance, and a finite-net path term.Source: §5.7 · p. 14

6 Flatness and generalization

The paper connects basin flatness to terminal posterior information and derives PAC-Bayes generalization certificates from the information ledger. It also accounts for noise and momentum as explicit ledger terms, while identifying limits on the sharpness certificate at network scale.

6.1 Flatness as terminal posterior information

  • A flat basin permits larger posterior covariance and entropy while maintaining small expected loss; its information penalty depends on the Hessian log-determinant, not only the largest eigenvalue.Near-zero-curvature directions contribute little, while sharp directions contribute logarithmically once the posterior is optimized.Source: §6.1 · pp. 14–15
  • Raw Euclidean Hessian flatness changes under reparameterization, whereas relative entropy remains invariant when the prior is transformed with the posterior; Fisher SAM’s generalization advantage is not mediated by the log-determinant penalty alone.SAM uses a worst-case-perturbed score, with intrinsic-time density based on the path-averaged Hessian along the ascent ray.Source: §6.1 · p. 15

6.2 PAC-Bayes from the information ledger

  • A PAC-Bayes certificate combines optimization-side information with terminal posterior information; for a tightened Gaussian posterior, basin-curvature complexity has leading term 1/2 log det H, so flatter minima incur lighter complexity.With a data-independent isotropic prior, the certificate is vacuous at network scale unless curvature is nearly flat across parameters; a data-fitted prior requires accounting for its data dependence.Source: §6.2 · pp. 15–16

6.3 Noise and momentum as entries of the information ledger

  • Adding noise or momentum leaves the ledger’s structure intact by attaching explicit terms; finite-cumulant perturbations add a cumulant entry, while phase-space momentum separates into conservative transport and a thermostat channel.Mini-batch score noise, post-step Gaussian injection, and Langevin heat each contribute an additive quadratic entry, with different attachment points and learning-rate scaling.Source: §6.3 · p. 16

7 Experimental evaluation

Across synthetic and real runs, the information ledger measures terms in classical bounds and distinguishes optimizers that reach similar losses. The experiments also show where closed-form predictions hold and where generalization and controller behavior depend on the setting.

7.1 Optimizers at a matched training loss

  • Intrinsic-time fractions span 31× across five optimizers whose training losses agree within 1.04× and test errors within 1.53× at a shared target.The spread follows the number and consistency of steps, which the matched losses do not register.Source: §7.1 · p. 16

7.2 The slack of the classical envelopes

  • At the deepest shared loss, intrinsic-time fractions span 29× on ResNet-20 and 18× on the language model, while losses span less than 1.5×; momentum-buffer optimizers have the smallest fractions.The linearized envelope exceeds realized weighted regret by exactly the comparator information still to be transported; that information is 45% of the envelope one-fifth into ResNet-20 training, 75% for the language model, and zero at the end.Source: §7.2 · p. 17, Figure 2 · p. 17

7.3 Terms with a closed form

  • Measured intrinsic-time inflation follows the mini-batch factor (N − b)/(b(N − 1)), and strict-saddle escape times track the leading-order prediction.Further controlled measurements track closed forms for the Bregman half-gain, escape threshold, variance reduction, bounded-influence scores, and α-stable-noise energy.Source: §7.3 · p. 17, Figure 3 · p. 18

7.4 The information ledger on real problems

  • On Covertype logistic regression, covariance-sampled curvature probing removes 90% of initial suboptimality in a median 2,754 queries; the same preconditioner on the step closes at most 0.3% within 150,000 queries.The caption reports that the covariance probe recovers nearly all of the gain of an oracle knowing the Hessian diagonal, whereas isotropic sampling does not reach the target within 150,000 queries.Source: §7.4 · p. 17, Figure 4 · p. 18
  • On Wide-ResNet-28-4, sharpness tracks the generalization gap along the batch axis, but across optimizers Lion is flattest and has the widest gap.A larger batch gives both a sharper endpoint and a wider gap; on ResNet-20, larger batches likewise give sharper endpoints and wider gaps.Source: §7.4 · p. 17, Figure 4 · p. 18
  • On ResNet-20, the stall signal is on for more than half of cosine annealing’s steps, and acting on it makes that schedule train worst among four schedules.The signal responds to mini-batch noise.Source: §7.4 · p. 18, Figure 4 · p. 18

7.5 Limits

  • Across optimizers, intrinsic-time fraction correlates with the train–test gap at +0.41 on ResNet-20 but −0.18 on the language model; its early accumulation ranks final losses at only +0.11 on average.At the same prefix, training loss reaches a +0.78 rank correlation with final losses.Source: §7.5 · pp. 18–19
  • With a data-independent isotropic prior, the terminal sharpness certificate is vacuous at network scale unless curvature is nearly flat across all parameters.The certificate’s minimum over prior scale grows with the spread of the curvature spectrum.Source: §7.5 · p. 19

8 Discussion

The discussion presents the information ledger as a modular identity for SGD trajectories, with familiar upper bounds arising by dropping explicit terms. It also states that exact accounting does not explain what keeps the information accrued by SGD small.

8 Discussion

  • The identity makes SGD analysis modular across rates, losses, predictable side information, and comparators, while leaving established optimization lower bounds intact.The discussion retains the Ω(1/√T) lower bound for convex stochastic optimization, gradient-oracle lower bounds, and minimax lower bounds for non-convex smooth optimization.Source: §8 · p. 19
  • Classical upper bounds become identities with quantifiable slack, and adaptive step sizes become controllers driven by intrinsic time.The familiar regret bound follows only after dropping terminal information and nonnegative curvature gain, then applying Jensen’s inequality.Source: §8 · p. 19
  • The accounting tracks information accrued along realized trajectories but supplies no mechanism that keeps it small along SGD trajectories.For label-noise SGD, the discussion cites a partial mechanism: convergence to stationary points of training loss plus a sharpness penalty, and Hessian-trace gradient flow near minimizer manifolds.Source: §8 · p. 19
  • The Gaussian-Bayes construction is local, and its objective-level identity is exact only when the Bregman remainder is retained.For nonconvex objectives, the discussion instead notes a smoothness-plus-Polyak–Łojasiewicz bound; the linearized posterior keeps covariance Σ, while the quadratic composite-loss treatment accumulates curvature in precision.Source: §8 · p. 19
  • The paper characterizes SGD as a Gaussian-prior, linearized Bayes update and treats the results as consequences of its one-step identity, with intrinsic time as their common clock.Source: §8 · p. 19

A The proper Gaussian likelihood construction

The construction represents an SGD update through Gaussian Bayesian conditioning and covariance reheating. In the weak-observation limit, the predictive posterior mean becomes the SGD iterate.

A The proper Gaussian likelihood construction

  • A Gaussian observation contracts the posterior covariance, and independent process noise reheats it while preserving the SGD mean update.The prior is N(θt, Σ), the observation is yt = θt − ηt/(1−χt) Σgt, and reheating gives qt+1 = N(θt − ηtΣgt, Σ).Source: A The proper Gaussian likelihood… · p. 21
  • As χt approaches 1, the likelihood factor converges, up to θ-independent constants, to the linear score exp(−ηt⟨gt, θ⟩).In the linear-score update, covariance is preserved directly; accounting for finite shrinkage and reheating adds covariance change as relative-entropy drift.Source: A The proper Gaussian likelihood… · p. 21
  • With a Gaussian mixture sharing covariance Σ, reweighting by the linear score shifts every component mean by the same SGD step and reweights component probabilities.The cumulative cross-entropy correction is the mixture free energy.Source: A The proper Gaussian likelihood… · p. 21

B Schedule constructions in full

The appendix derives step-size and schedule constructions as projections or specializations of the information ledger. It gives a tight convex rate for Schedule-Free SGD and a Chebyshev cycle with a quadratic convergence comparison.

B.1 Matrix clocks and classical step-size rules

  • For predictable diagonal or full-matrix Σt, intrinsic-time density already encodes the preconditioner, while each covariance change adds drift.A preconditioner helps only if it lowers future intrinsic time or comparator information by more than its drift; parameter-free methods adapt to an unknown comparator without AdaGrad’s D tuning.Source: §B.1 · p. 21

B.2 Schedule-Free SGD: the tight convex rate as an identity projection

  • Under γ = D/(G√T) and bounded gradients, Schedule-Free SGD attains the tight nonsmooth convex rate E[F(xT) − F(u)] ≤ DG/√T.The derivation drops the terminal information term, bounds intrinsic-time cost using G, and applies a telescoping inequality that drops nonnegative Bregman terms.Source: §B.2 · pp. 21–22

B.3 Chebyshev step-size cycling: a closed-form schedule on quadratics

  • At κ = 100, the Chebyshev cycle reaches relative norm at most 10^-3 in every eigencoordinate in 38 rounds, versus 346 for the fixed step, while cumulative intrinsic time stays bounded in T.The comparison concerns full-gradient descent on a quadratic with curvature interval known; the cycle uses reciprocal Chebyshev nodes.Source: §B.3 · p. 22

B.4 Pressure-cycled SGD: alternating descent and escape schedules

Pressure-cycled SGD alternates information-gain descent with escape steps when realized progress per intrinsic-time cost stalls. The same section develops zeroth-order curvature probes, whose sampling covariance preconditions expected dynamics.

B.4 Pressure-cycled SGD: alternating descent and escape schedules

  • Descent maximizes comparator-information gain, while escape maximizes information injected along unstable directions after a run of small objective decrease per intrinsic-time cost.The descent step is ηdesc_t = St/(2Qt); escape uses a large step plus thermal injection.Source: §B.4 · p. 23
  • On the synthetic two-basin potential, pressure-cycled SGD reaches within 10^-3 of the deep minimum on every seed, while fixed-step and constant-temperature baselines do so on none.Its measured trigger cannot distinguish a stall from mini-batch noise or convergence, and escape continues after the minimum is found; the method returns the recorded best iterate.Source: §B.4 · p. 23

C Zeroth-order constructions and their measured reach

  • For zeroth-order SGD, the probe covariance preconditions expected dynamics, whereas an AdaGrad accumulator built from noisy rank-one probe scores does not identify curvature.On a quadratic, covariance C = H^-1 contracts every direction by the same factor 1 − ηt, whatever the condition number.Source: C Zeroth-order constructions and their… · p. 23

C.1 A query-only curvature-probed sampler

  • A coordinate sweep estimates diag(H) in 2d + 1 function queries, and drawing probes from the damped inverse-curvature covariance realizes that preconditioner using function values.The method alternates curvature sweeps with probe steps; the same second differences can recover full symmetric H in d^2 + d + 1 queries.Source: §C.1 · pp. 23–24

C.2 Measured reach of the zeroth-order samplers

Curvature-aware probe covariance improves zeroth-order reach when curvature varies widely, while applying the same preconditioner to the step can fail because of its second moment. At fine-tuning scale, the allocation following group curvature has the lowest validation loss among those tested.

C.2 Measured reach of the zeroth-order samplers

  • At κ = 10 to 1000, the diagonal curvature probe reaches f < 10^-3 in fewer than 400 function-evaluation pairs, while isotropic sampling needs more as κ grows.The probe-score AdaGrad accumulator needs about as many pairs as isotropic sampling.Source: §C.2 · p. 24, Figure 5 · p. 25
  • On rotated quadratics, the diagonal probe needs 1.4 times isotropic queries at κ = 10 and gains 1.9× at κ = 100; the full-matrix probe takes 1.3–1.5 times its oracle’s queries.The full-matrix sweep costs 273 queries at d = 16.Source: §C.2 · p. 24, Figure 5 · p. 25
  • With stricter tuning on the quartic bowl, every seed reaches the target in a median 786 queries for the diagonal probe, 1,842 for the full-matrix probe, and 2,046 for isotropic sampling.On the Rosenbrock valley, isotropic sampling diverges at every grid step size; the full-matrix probe reaches f < 1 on 5 of 8 seeds in a median 3,649 queries.Source: §C.2 · p. 24
  • On raw Covertype components, the covariance-form probe reaches the 90%-suboptimality-reduction target in a median 2,754 queries, versus no target reached by isotropic sampling within 150,000 queries.The exact diagonal oracle takes 2,039 queries; scaling an isotropic probe’s step by the same preconditioner diverges or stalls at every tried step size.Source: §C.2 · p. 24
  • On raw Covertype components, the covariance probe recovers at least 93% of the exact diagonal oracle’s gain on a log scale, while the step-scaled form makes no progress.The covariance form reaches the target with a speed-up of more than 54× over isotropic sampling; the exact diagonal oracle’s speed-up is 73×.Source: §C.2 · p. 24
  • At fine-tuning scale, the curvature-following per-group probe allocation ends at the lowest validation cross-entropy among four allocations after 700 queries.The allocations share one learning rate and total probe energy, but their effective group rates differ with the squared probe scales.Source: §C.2 · p. 25, Figure 6 · p. 26

C.3 Any sampling law via the cumulant information ledger

  • For non-Gaussian probe laws, the mean step depends only on covariance, while the adaptive-Bayes normalizer uses the cumulant-generating function and higher moments alter the ledger.The Gaussian second moment is the cumulant-generating function’s second-order term.Source: §C.3 · pp. 25–26

D Information complexity of loss surfaces

The information complexity of a loss surface separates comparator description cost, intrinsic-time energy, and signed curvature gain. Its quadratic specialization links posterior-information cost to flatness, while posterior contraction near a minimum reflects local curvature.

D Information complexity of loss surfaces

  • The realized weighted information complexity equals weighted excess loss and separates prior description cost, intrinsic-time energy, and signed curvature gain.The intrinsic clock also defines worst-case trajectory, initialization-average, and least-time-to-target notions of path difficulty.Source: D Information complexity of loss… · p. 26
  • For a positive-definite quadratic with an isotropic Gaussian prior and fixed-rate full-gradient descent, the surface complexity includes eigenvalue-wise posterior-information cost and a prior-distance penalty.As ε decreases, feasibility forces β to grow roughly as d/(2ε), making tighter certification cost order d log(1/ε); the signed path remainder’s initial largest-eigenvalue coefficient grows linearly in condition number.Source: D Information complexity of loss… · p. 26

E.1 Basin evidence and posterior contraction

  • Near a minimum with Ht ≈ H, the quadratic composite-loss update yields posterior covariance ΣT ≈ (αTH)^-1, narrow along sharp directions and broad along flat ones.This is the Laplace form of Bayesian identification of sharpness with a narrow posterior.Source: §E.1 · p. 27

E.2 Coordinate dependence and practical estimation

Practical curvature estimates on deep networks are limited by truncated spectra and coordinate dependence. The paper also accounts for SAM’s path-averaged curvature and treats noise and momentum as explicit ledger entries.

E.2 Coordinate dependence and practical estimation

  • At a critical point, the Fisher matrix and Hessian transform alike, but only the spectrum of F^-1H is invariant; the relative entropy remains invariant when posterior and prior are transformed together.The Hessian trace and spectral radius are not invariant under the parameter change.Source: §E.2 · p. 27
  • Deep-network curvature estimates use truncated spectra, and function-preserving rescaling can move eigenvalues into or out of the top-K subspace while flooring and trace residuals distort log-determinants.At K = 512, flooring dominates the Hessian log-determinant; the Fisher has fewer floored values, but its log-determinant also shifts under reparameterization.Source: §E.2 · p. 27

E.3 Sharpness-aware minimization as an information-ledger entry with path-averaged Hessian

  • The exact SAM ledger holds at every order in ρt because the path-averaged Hessian absorbs higher-order loss content along the ascent ray.Its dominant small-ρt correction is directional sharpness along the realized step, while terminal log det H records resulting flatness.Source: §E.3 · p. 28
  • In synthetic convex logistic regression, Fisher SAM’s terminal log-determinant is comparable to or larger than SAM’s, so that quantity alone does not mediate the documented Fisher-SAM generalization advantage.Fisher SAM’s ascent has no first-order preference for flat directions where Fisher equals Hessian; SAM’s Euclidean ascent raises loss least along the flattest directions.Source: §E.3 · p. 28

F The full noise-and-momentum information ledger

F.1 The master decomposition under added noise

This section extends the information accounting to noisy and adaptive updates, separating noise energy and comparator displacement from information erased when learner and comparator share a noise channel. It applies the accounting across several update dynamics and reports optimizer-panel measurements relating intrinsic-time fraction to optimizer steps and test error.

F.1 The master decomposition under added noise

  • Added noise contributes a signed comparator displacement and nonnegative energy to the exact pointwise ledger; under conditional mean-zero noise, the expected objective ledger also includes its energy cost.Langevin covariance proportional to η_tΣ gives expected energy proportional to η_td, whereas fixed-variance noise makes the penalty divided by η_t grow as 1/η_t.Source: §F.1 · pp. 29–30

F.2 Noise as an information channel

  • A shared noise kernel contracts KL divergence, and the exact contraction gap is the conditional information loss between the input and output of the channel.This identifies the comparator information erased by noise, which a data-processing inequality alone discards.Source: §F.2 · p. 30

F.3 Gaussian Langevin dynamics; F.4 Quadratic example: the stationary covariance of noisy SGD and SGLD

  • Langevin’s ledger adds a thermal cost β^-1η_td, while its free-energy identity describes dissipation of relative entropy to the Gibbs law.In a one-dimensional quadratic well, fixed-variance noise leaves a floor that diverges as η decreases, while Langevin noise proportional to η leaves a finite temperature-set floor.Source: §F.3 · p. 31, §F.4 · p. 31

F.5 State-dependent preconditioning and Riemannian Langevin corrections

  • For state-dependent preconditioning, the ledger separates gradient intrinsic time and metric drift; omitting the corresponding correction biases the sampler’s invariant law.The Itô correction vanishes for constant preconditioning.Source: §F.5 · pp. 31–32

F.6 Survival and change under non-Gaussian noise

  • With finite variance, the conditional mean ledger depends on non-Gaussian noise only through its first two moments, while cumulant information captures distributional effects beyond them.For centered noise with a moment-generating function near zero, the cumulant function has a covariance-based second-order expansion; symmetric α-stable noise has an infinite cumulant function in nonzero directions, so the score must be truncated or robustified. The cited transformer measurement at batch 32 does not find heavy-tailed per-coordinate gradient noise.Source: §F.6 · p. 32

F.7 Learning-rate design with noise

  • The noisy pressure-target rule has no positive learning rate when noise energy alone meets or exceeds the target.When the noise covariance is independent of the learning rate, the rule requires a positive numerator; for Langevin noise, the thermal term preserves temperature, which optimization can anneal but sampling accepts as a floor.Source: §F.7 · p. 33

F.8 Saddles under noisy dynamics; F.9 Momentum: the information ledger in phase space

  • Noise grows geometrically along an unstable saddle direction, and momentum amplifies negative-curvature directions and their velocity noise in phase space.For heavy-tailed perturbations, escape may instead occur through a single jump, with waiting time of order w^α to exceed width w rather than an Arrhenius barrier dependence.Source: §F.8 · p. 33, §F.9 · pp. 33–34

F.10 Mini-batch gradient noise as intrinsic time; F.11 Loss-surface complexity with noise and momentum

  • Mini-batch gradient noise contributes to intrinsic time and exploration, while flat directions retain larger stationary variance under the stated common-eigendirection approximation.The noisy-trajectory complexity ledger includes gradient intrinsic time, injected-noise energy, unfavorable displacement, metric drift, and terminal comparator information.Source: §F.10 · p. 34, §F.11 · p. 35

G.1 The luckiness constant on a bounded region

  • With bounded iterates and bounded gradient noise, κ is finite at O(LD2 + σ2/µ); fixed-rate noisy SGD has regret Θ(ησ2T), while ηt = 1/(µt) yields O(log T) regret.The bounded-region condition controls the gradient inner-product term by O(LD2), while noise contributes σ2/µ. Constant regret at a fixed rate requires a noiseless oracle.Source: §G.1 · p. 35

G.2 Biased estimators and Adam-style bias correction

  • For biased estimators including EMA, momentum, and clipped gradients, the accounting adds BiasT; Adam-style bias correction cancels leading-order bias, leaving the remaining bias recorded.Source: §G.2 · p. 35

G.3 Heavy-tailed gradients and Catoni transforms

  • Catoni robustification gives the clock finite variance even when E∥ĝt∥4 = ∞; below stability index two, truncation or Catoni robustification restores a finite noise-energy entry without changing the pathwise identity.Source: §G.3 · p. 35

G.4 Comparator-centered PAC-Bayes regret

  • The PAC-Bayesian regret identity applies to Gaussian comparators ρ = N(θ∗, τ2I) with τ ≤ σ; τ = σ gives a self-certified posterior matching SGD’s Bayesian state.Shrinking τ approaches the point-comparator regret.Source: §G.4 · p. 35

G.5 Taylor descent for smooth nonconvex functions

  • For deterministic gradient descent, objective descent is exact with an integral remainder, and bounding that remainder by smoothness yields the descent lemma.Source: §G.5 · p. 36

G.6 AdaGrad two-sided envelope

  • For the square-root step, C√ΓVT ≤ Σt≤T ηtQt ≤ 2C√ΓVT; the bounds are attained or approached by concentrated or equal clock increments, respectively.The predictable schedule using Vt−1 need not satisfy this envelope.Source: §G.6 · p. 36

G.7 Fixed-point partition-function identity for Polyak-step SGD

  • For Polyak-step SGD with at = ft(θ∗), each round has −log Zt = ηtat, and local-update normalizers compose multiplicatively into the linearized problem’s cumulative log-partition function.Source: §G.7 · p. 36

H.1 The optimizer panel on a real network

  • Over 400 full-batch steps, the intrinsic-time fraction rises from plain SGD (0.6%) to RMSProp (7.0%) and AdaGrad (8.4%).At matched training loss, SGD takes 567 steps versus RMSProp’s 29, with R/T of 0.33 versus 0.17. Across 14 interpolating runs, the fraction and training loss rank test error equally well (Spearman −0.91 and +0.91); under widening with 15% label noise, test error peaks at 1210 parameters against 1257 training points, while the fraction has no feature at the peak.Source: §H.1 · p. 36

H.2 Slack of the classical envelopes on real networks

Across real-network experiments, the information ledger identifies where classical envelopes lose tightness, while intrinsic-clock, escape-controller, and sharpness measures show effects that depend on the optimizer, task, and comparison. On 12 Wide-ResNet-28-2 endpoints, a dominant common term makes the certificate bound insensitive to endpoint differences, while the basin term varies across endpoints and orders the optimizers against the generalization gap.

H.2 Slack of the classical envelopes on real networks

  • The ledger identity has no slack across 71 runs, but objective-level Bregman remainders are negative over 94–98% of many runs, and Schedule-Free’s relaxation costs 2.4× and 2.7× the linearized envelope on ResNet-20 and the LM.The square-root clock’s realized sum ηtQt sits 0.96 of the way up its two-sided band on ResNet-20 and 0.79 on the LM, making the classical upper end nearly tight there.Source: §H.2 · p. 37
  • At matched training-loss targets, momentum-buffer optimizers have intrinsic-time fractions of 0.02–0.05, but their train–test gaps are lower on ResNet-20 and higher on the character LM.The average gap difference is 0.08 lower on ResNet-20 and 0.014 higher on the LM; Muon and SOAP account for the LM excess. The fraction–gap correlation averages +0.41 on ResNet-20 and −0.18 on the LM.Source: §H.2 · pp. 37–38, Figure 7 · p. 37

H.3 Single terms of the information ledger

  • Ledger terms matched their predicted behaviors: noisy-SGD regret ratios were 0.492–0.500, all 144 strict-saddle runs escaped, and robustification reduced heavy-tailed noise costs.SVRG’s ratio to deterministic intrinsic time was 0.98 on Adult and 0.99 on Covertype, versus 1.44 and 5.58 for SGD; in transformer runs, coordinate-scaled batch-32 gradient noise was not heavy-tailed. For α = 1, truncation reduced mean noise energy from 1.5 × 10^6 to 2.2 and Catoni’s score to 25.Source: §H.3 · p. 38

H.4 The intrinsic clock against iteration count

  • The intrinsic clock rarely improved on iteration count: mean ΔR² was −0.062, −0.007, and −0.041 across three step sizes, while real-data median ΔR² was −0.0018.Under a curriculum, median ΔR² stayed between −0.0035 and −0.0015 despite the non-stationarity statistic rising from 0.18 to 0.74.Source: §H.4 · pp. 38–39
  • Clock-based forecasts differed more from step-based forecasts when the clock defect was larger, but offered a clear advantage only at the shortest drift prefix; equal-clock optimizer rankings also predicted final-loss order well.At the shortest drift prefix, the clock forecast was closer on all 32 instances by 0.88 median error; equal-clock rankings had median Spearman correlation +0.89 to +0.94, while equal-step-weighted-clock rankings were −0.40 to −0.26.Source: §H.4 · pp. 40–41

H.5 Optimizers derived from the information ledger

  • The pressure-cycled controller reached the target on every potential seed, but slowed or degraded training on real networks.It reached f − f⋆ < 10^-3 in a median 553 steps on all 16 potential seeds, while no baseline did; on the vision transformer it lowered AdamW’s best validation accuracy by 0.009–0.061, and on ResNet-20 it trained worst among four schedules. On grokking, the pressure-target rule matched fixed-step SGD, while curvature-targeted kicks did not speed grokking.Source: §H.5 · p. 42, Figure 11 · p. 42

H.6 Sharpness and the generalization gap

  • Sharpness statistics had the predicted sign along batch-size sweeps, but across optimizers they often had the opposite sign or no reliable correlation with the generalization gap.ResNet-20 batch-8192 endpoints had λmax 613 versus 94 and gap 0.399 versus 0.229 for batch 32; on Wide-ResNet-28-4 the corresponding values were 19.0 versus 9.3 and 0.306 versus 0.180. Lion was an exception-driving case: it was flattest yet had the widest gap.Source: §H.6 · p. 43, Figure 12 · p. 43
  • Function-space measures also changed direction across batch sizes: their gap correlations were +0.58 to +0.66 at batch 32 and −0.60 to −0.76 at batch 8192.At both batch sizes, the measures tracked training loss, while training loss’s correlation with the gap changed sign; within-optimizer seed correlations were not reliable.Source: §H.6 · p. 44
  • At all 12 Wide-ResNet-28-2 endpoints, the common term puts bound (45) within 1.3 × 10−4 of 8.68, so this value does not measure the endpoints.The calculation sets the d − 32 unprobed eigenvalues to one and lower-bounds the inverse trace; the parameter-norm term is omitted. A flat spectrum at the prior’s scale gives an exact bound of 0.012 but evaluates to 9.09 by the same rule.Source: §H.6 · p. 44
  • Across the 12 endpoints, the rank-32 basin term ranges over [−119, +1.5] nats, while the inverse-trace term ranges over [0.12, 31.5] nats.The probed Hessians have negative eigenvalues, so the analysis uses a positive-definite surrogate whose floor depends on all d eigenvalues.Source: §H.6 · p. 44
  • The certificate ranks the 12 endpoints as the basin term does, decreasing in −log det eH, and orders optimizers against the gap with ρ(KL, gap) = −0.50.Source: §H.6 · p. 44

J Proofs of deferred statements

The deferred proofs derive the ledger identities and verify their consequences for moving comparators, zeroth-order estimators, saddle dynamics, and learning-rate schedules. They also establish finite intrinsic-time and path costs for stable fixed-rate descent on positive-definite quadratics.

J Proofs of deferred statements

  • Conditional expectation, the Bregman decomposition of the gradient inner product, and telescoping comparator information yield the one-step identity over multiple rounds.Source: J Proofs of deferred statements · pp. 44–45
  • For moving comparators, reindexing isolates a drift whose squared-distance differences are bounded by comparator motion times the iterate’s displacement from the comparator.Source: J Proofs of deferred statements · p. 45
  • For zeroth-order probes, the mean estimator Cg needs only the probe’s second moment; Gaussian probes also yield a finite-μ Stein identity and an explicit second-moment formula.Source: J Proofs of deferred statements · p. 45
  • In the quadratic eigenbasis, saddle-point dynamics obey z_t+1,j = (1 − ηλ_j)z_t,j deterministically, with gradient noise adding −ηξ_t,j to each coordinate.Source: J Proofs of deferred statements · p. 45
  • Chebyshev cycling bounds coordinate contraction by TT(ξ)^−1 and the information ratio by TT(ξ)^−2; the ledger keeps objective regret and Bregman gain opposite intrinsic-time cost.Source: J Proofs of deferred statements · p. 46
  • For Gaussian probes, antithetic Taylor expansion has zero remainder on quadratic objectives, and Isserlis’ theorem gives the summed Hessian moment (d + 2)tr(H).Source: J Proofs of deferred statements · p. 46
  • For positive-definite quadratics, fixed-rate gradient descent is stable when 0 < ηλ_i < 2, and its cumulative intrinsic-time cost and net path term remain finite as T grows.Source: J Proofs of deferred statements · pp. 46–47
Loading 2610.00446v1…