CS Paper Radar

Sampling and Curvature in First-Exit Comparisons for Momentum SGD

Haiyi Li

cs.LG ·submitted 2026-10-18 11:24 UTC · v1

Abstract

First-exit prediction for momentum SGD depends on sampling information that pointwise gradient laws omit. Strongly convex finite pools with identical pointwise laws and matched iid momentum dynamics can have different reshuffled exits; even analytic pools with uniformly close pointwise laws can have separated exit probabilities. For persistent sampling in one dimension, we establish an explicit $O(h)$ mean-exit comparison with a finite-rate switching process under nonvanishing component velocities and step-size conditions; iid sampling instead averages to an ODE. Retaining realized minibatches and sampled curvature yields finite-window exit brackets beyond this regime. In 32 trained ridge-logistic runs, 29 meet prespecified targets with rounding-certified brackets; an enclosure control explains most of the width advantage. Exact-real certificates establish finite means at the original tested radii for three ResNet-18 checkpoints and give local finite-mean conditions for tanh and ViT networks; their upper bounds remain loose, and original-radius ViT mean guarantees remain unresolved despite 128 fresh continuation paths. A two-network replication gives 32/32 successful seeds in each of four finite-path persistence comparisons. Independent equal-length controls retain slower exits after refresh resets than without resets, but the refresh-versus-random ordering reverses with update length at both networks. These interventions do not causally decompose raw momentum SGD. Neural step-size scaling does not validate the switching limit.

Comment
84 pages, including references and appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Rare Gate Disagreements Can Limit Plasticity: When Gradient Flow Mispredicts Finite-Batch SGD

cs.LG math.OCstat.ML ·2026-10-08 ·Ruoyu Zhao, Mingxuan Zhang, Jianbo Dai, Jiaqi Wu, Chenyu Zhu +1 more
similarity 0.62
Abstract · 25 pages, 5 figures. Tong Che leads the project

Population gradient flow is a common tool for reasoning about how neural networks adapt, including after pretraining. We show that it can mispredict finite-batch stochastic gradient descent (SGD) qualitatively, and we trace the discrepancy to a specific mechanism. In a two-unit ReLU regression, a source task drives the two neurons toward positive proportionality and a target task rewards separating them. After source training for time $T$, gradient flow recovers on the target in time linear in $T$. Online SGD with batch size $b$ and step size $η$ in both phases instead fails with high probability throughout a horizon of order $e^{c/η}$ once $T \gtrsim \log(b/η)$, uniformly on an explicit set of initializations with Gaussian probability above one percent. For each fixed $T$, small-step SGD still recovers, so the failure requires the joint limit of small steps and long pretraining. At the target clone, the population instability is carried entirely by inputs on which the two ReLU gates disagree. For units at angle $δ$ these inputs form a wedge of probability $δ/π$, and weight decay shrinks the angle exponentially during pretraining. On every other input both units receive the same random linear update, which contracts their separation in conditional expectation. Bounding the cumulative probability of sampling the wedge along the exact online recursion, without a diffusion approximation, shows that recovery with fixed probability from an identical source-gradient-flow checkpoint, within $e^{c/η}$ updates, requires $Nb \gtrsim e^{λT}$ target samples and batch size $b \gtrsim ηe^{λT}$, where $N$ counts updates and $λ$ is the weight decay. In simulations, recovery is approximately a function of the disagreement budget $bδ/η$ and saturates in the horizon.

0.30

A Convergence Framework for Deep $V$-Learning: Error Propagation and Sharp Action-Gap Bounds

cs.LG cs.ROmath.OC ·2026-09-16 ·Yury Kolomeytsev
similarity 0.60
Abstract · 37 pages

We establish convergence bounds for deep $V$-learning with horizon $H$. The algorithm fits a scalar value function to targets from executed transitions and selects actions using a predictive model and the value function. For current observed-successor targets with fresh true-kernel outcomes, the conditional mean is $\mathcal{T}^βV$, which averages over behavior-policy actions. The Bellman optimality update is $\mathcal{T} V$. We decompose the update error into six residuals: fitting, transition reuse, target construction, replay, action selection, and exploration. Under $L^s$ concentrability, their $L^p$ norms ($p=s/(s-1)$) control expected $L^1$ policy loss. The bound explicitly weights residuals from only the last $H-1$ update blocks, plus an initialization term for shorter runs. We quantify the cost of a shared sampling distribution across horizon levels. For statistical error bounds of order $n^{-ν}$, we derive optimal continuous allocations and an integer allocation whose objective is within a factor $2^ν$ of the constrained optimum. A margin condition with exponent $α$ gives action error of order $Λ^{1+α/p}$, where $Λ$ combines network drift and score error; a one-step construction proves the exponent sharp. Bounds on the distance between frozen and optimal scores transfer an optimal-gap condition to frozen-iterate gap bounds while retaining the mass of optimal ties. Survival probabilities and coverage conditions at deployment yield bounds for policies selected with approximate scores. Separate spatial ReLU networks per horizon level give a conditional neural regression rate, and the finite-state case gives a log-free expected fit rate. These results give expected policy-loss consistency for the fixed-horizon generative-reset approximate-ERM procedure with exact action scores and provide an explicit residual-decay criterion for FIFO/interleaved SGD.

0.29

Ideal Paths for Approximating Logistic Gradient Descent Trajectories at Large Initialization

cs.LG math.OC ·2026-10-02 ·Junjie Xiao, Huiwen Jia
theory similarity 0.60
Abstract · 42 pages, 5 figures, 6 tables

Modern training on a new task often starts from a previously trained model rather than from scratch, raising the question of how this initialization affects the subsequent training trajectory. Classical implicit-bias results characterize the direction selected by prolonged training, but this direction alone does not provide information regarding the intermediate behavior. We address this question through a geometric approximation of full-batch logistic gradient descent (GD) trajectories on strictly linearly separable data, with large initialization of scale $R$ motivated by prior training. From any limiting normalized initial position, we use minimum-norm projection rules to construct a unique continuous ideal path consisting of finitely many linear segments. The path has two stages: negative-margin correction followed by minimum-margin growth. We prove that, after an explicit two-stage time reparameterization, the fixed-step GD trajectory divided by $R$ converges uniformly to this path on every fixed parameter interval as $R\to\infty$. Further, our quantitative error bounds account for initialization perturbations and the transition between stages. This approximation provides asymptotic formulas for peak evaluation loss and cumulative training loss. In particular, peak evaluation loss can grow linearly in $R$ even when both endpoint losses tend to zero. The cumulative losses in the correction and margin-growth stages, normalized by $R^2$ and $R$, respectively, converge to explicit limits. Experiments on controlled geometries and fixed image features complement our theoretical results.

0.32

Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

cs.LG math.OCstat.ML ·2026-10-14 ·Zijun Chen, Zihan Zhang
similarity 0.59
Abstract

Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex $L$-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order $1/L$. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components $n$. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying $0<η\lesssim 1/(L(1 + \log(nK)))$, where $K$ is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit $1/n$ factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.

0.38

QAM: Quadratic-Accurate Checkpoint Merging via Sequential Consistency

cs.LG cs.AI ·2026-09-28 ·Shihao Wang, Rui Kong, Xinran Chen, Hui Wu, Qipeng Qian +5 more
theory similarity 0.59
Abstract

Saved checkpoints record states along a training trajectory, but generally do not determine the updates at states that would be visited under a different schedule. We study how accurately these checkpoints can reconstruct the endpoint of a sequential reference with prescribed update strengths. Under a common local transition model, two checkpoint-index moment conditions characterize all convex merges that agree with this reference through second order. We then prove an information limit that for nondegenerate profiles, no algorithm using only a fixed-length gradient-descent (GD) history with step size $h$ can achieve $o(h^3)$ endpoint error uniformly over a fixed class of smooth, strongly convex losses. The lower bound follows from two losses with identical GD checkpoint histories but sequential reference endpoints separated by $Ω(h^3)$. \textbf{Quadratic-Accurate Merging} (QAM) achieves a matching uniform $O(h^3)$ endpoint error bound. Its explicit coefficients also define the unique profile-dependent merge that exactly matches the sequential GD reference across all fixed quadratic objectives. Across two public Adam checkpoint trajectories (SmolLM3-3B and OpenEuroLLM-Prelude-9B), three windows and three profiles per model, and 15 tasks, QAM shows mixed results for short windows and broader advantages over \textbf{Warmup-Stable and Merge} (WSM) for longer windows. Matched-moment GSM8K diagnostics further show that local consistency alone does not fully determine downstream scores. These results characterize the reconstruction limits of saved histories, provide a coefficient rule that attains the optimal rate, and assess its practical utility.

0.27

Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules

cs.LG math.OCmath.STstat.ML ·2026-08-26 ·Liviu Aolaritei, Lucas Lévy, Francis Bach, Michael I. Jordan
similarity 0.58
Abstract

Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon chosen before the algorithm is run, even though practical stopping decisions are made adaptively by inspecting the evolving trajectory. This mismatch creates a fundamental certification problem: fixed-time guarantees do not generally remain valid at data-dependent stopping times, while deterministic horizons derived from worst-case bounds can be highly conservative. We address this problem for strongly convex stochastic optimization by constructing fully observable, trajectory-adaptive upper confidence sequences for the squared distance of the last iterate to the optimizer and the suboptimality of a weighted average. These bounds hold simultaneously over time, attain the optimal $1/t$ decay rate up to iterated-logarithmic factors in the worst case, and adapt to the realized stochastic gradients, allowing SGD to stop as soon as a prescribed accuracy is certified without sacrificing statistical validity. Our approach treats the evolving SGD trajectory as a sequential experiment whose observations provide evidence about the unknown optimization error. To formalize this perspective, we develop new recursive confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes with time-varying conditional means and predictable ranges that may grow without bound. We further extend these confidence-sequence constructions to minibatch SGD, with the empirical Bernstein bounds exploiting the realized second-moment structure within each minibatch. Numerical experiments show that the resulting stopping rules can require several orders of magnitude fewer iterations than natural deterministic horizons.

0.18

Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling

cs.LG cs.AImath.ST ·2026-10-12 ·Bo Yuan, Wei Guo, Yongxin Chen
similarity 0.58
Abstract · Under Review

We study sampling from $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ is $α$-strongly convex and $β$-smooth with condition number $κ=β/α$. For this problem, the proximal sampler preserves the target exactly and recovers overdamped Langevin dynamics in the small-step limit, but its Gaussian resampling step discards directional information. Underdamped Langevin dynamics retains such information through momentum to accelerate exploration, motivating a proximal construction that combines target preservation with directional persistence. We introduce \textit{reflected proximal dynamics}, which combines proximal sampling with an exact reflection of the auxiliary variable, conditional kinetic motion, and controlled refreshment. We develop two realizations: a flux-resampled underdamped half-turn and a persistent-momentum quarter-turn. From a warm start with constant $χ^2$ divergence, both methods achieve total variation error $\varepsilon$ using $\widetilde O(\sqrtκd^{1/4})$ expected oracle queries. We further remove the supplied warm-start assumption by combining either sampler with existing posterior samplers in a proximal initialization stage with an optimized coarse step size. Accounting for both initialization and sampling yields $\widetilde O(κ^{6/7}d^{1/4})$ expected oracle queries. In both regimes, the dependence on the target accuracy $\varepsilon$ is $\mathrm{polylog}(1/\varepsilon)$, making reflected proximal dynamics a promising framework for accelerated high-accuracy log-concave sampling.

0.33

Improved last-iterate bounds for SGD with and without replacement

cs.LG stat.MLmath.OC ·2026-11-10 ·Yimin Zhong, Jiaxin Zhou
similarity 0.57
Abstract

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)$ to $\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.

0.16