Stochastic Gradient Optimization Techniques

Latest papers

• Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks

  Xavier Gonzalez · 18 March 2026

  Massively parallel hardware (GPUs) and long sequence data have made parallel algorithms essential for machine learning at scale. Yet dynamical systems, like recurrent neural networks and Markov chain Monte Carlo, were thought to suffer from sequential bottlenecks. Recent work showed that dynamical s…

• Spectral Edge Dynamics of Training Trajectories: Signal--Noise Geometry Across Scales

  Yongzhong Xu · 18 March 2026

  Despite hundreds of millions of parameters, transformer training trajectories evolve within only a few coherent directions. We introduce \emph{Spectral Edge Dynamics} (SED) to measure this structure: rolling-window SVD of parameter updates reveals a sharp boundary -- the \emph{spectral edge} -- betw…

• On Interpolation Formulas Describing Neural Network Generalization

  Jin Guo, Roy Y. He, Jean-Michel Morel · 17 March 2026

  In 2020 Domingos introduced an interpolation formula valid for "every model trained by gradient descent". He concluded that such models behave approximately as kernel machines. In this work, we extend the Domingos formula to stochastic training. We introduce a stochastic gradient kernel that extends…

• Ghosts of Softmax: Complex Singularities That Limit Safe Step Sizes in Cross-Entropy

  Piyush Sao · 17 March 2026

  Optimization analyses for cross-entropy training rely on local Taylor models of the loss to predict whether a proposed step will decrease the objective. These surrogates are reliable only inside the Taylor convergence radius of the true loss along the update direction. That radius is set not by real…

• Power-Law Spectrum of the Random Feature Model

  Elliot Paquette, Ke Liang Xiao, Yizhe Zhu · 17 March 2026

  Scaling laws for neural networks, in which the loss decays as a power-law in the number of parameters, data, and compute, depend fundamentally on the spectral structure of the data covariance, with power-law eigenvalue decay appearing ubiquitously in vision and language tasks. A central question is …

• Dataset Distillation Efficiently Encodes Low-Dimensional Representations from Gradient-Based Learning of Non-Linear Tasks

  Yuri Kinoshita, Naoki Nishikawa, Taro Toyoizumi · 17 March 2026

  Dataset distillation, a training-aware data compression technique, has recently attracted increasing attention as an effective tool for mitigating costs of optimization and data storage. However, progress remains largely empirical. Mechanisms underlying the extraction of task-relevant information fr…

• Learning in Function Spaces: An Unified Functional Analytic View of Supervised and Unsupervised Learning

  K. Lakshmanan · 17 March 2026

  Many machine learning algorithms can be interpreted as procedures for estimating functions defined on the data distribution. In this paper we present a conceptual framework that formulates a wide range of learning problems as variational optimization over function spaces induced by the data distribu…

• Probabilistic Gaussian Homotopy: A Probability-Space Continuation Framework for Nonconvex Optimization

  Eshed Gal, Samy Wu Fung, Eldad Haber · 17 March 2026

  We introduce Probabilistic Gaussian Homotopy (PGH), a probability-space continuation framework for nonconvex optimization. Unlike classical Gaussian homotopy, which smooths the objective and uniformly averages gradients, PGH deforms the associated Boltzmann distribution and induces Boltzmann-weighte…

• Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach

  Mathukumalli Vidyasagar · 17 March 2026

  In this paper, we analyze the two time-scale stochastic approximation (TTSSA) algorithm introduced in Borkar (1997) using a martingale approach. This approach leads to simple sufficient conditions for the iterations to be bounded almost surely, as well as estimates on the rate of convergence of the …

• Muon Converges under Heavy-Tailed Noise: Nonconvex H\"{o}lder-Smooth Empirical Risk Minimization

  Hideaki Iiduka · 17 March 2026

  Muon is a recently proposed optimizer that enforces orthogonality in parameter updates by projecting gradients onto the Stiefel manifold, leading to stable and efficient training in large-scale deep neural networks. Meanwhile, the previously reported results indicated that stochastic noise in practi…

• Accelerating Byzantine-Robust Distributed Learning with Compressed Communication via Double Momentum and Variance Reduction

  Yanghao Li, Changxin Liu, Yuhao Yi · 17 March 2026

  In collaborative and distributed learning, Byzantine robustness reflects a major facet of optimization algorithms. Such distributed algorithms are often accompanied by transmitting a large number of parameters, so communication compression is essential for an effective solution. In this paper, we pr…

• Why Grokking Takes So Long: A First-Principles Theory of Representational Phase Transitions

  Truong Xuan Khanh, Truong Quynh Hoa, Luu Duc Trung, Phan Thanh Duc · 17 March 2026

  Grokking is the sudden generalization that appears long after a model has perfectly memorized its training data. Although this phenomenon has been widely observed, there is still no quantitative theory explaining the length of the delay between memorization and generalization. Prior work has noted t…

• Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions

  Quoc Tran-Dinh, Nghia Nguyen-Trung · 17 March 2026

  This paper develops new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method to solve a class of possibly nonmonotone stochastic composite inclusions. Unlike unbiased estimators such as mini-batching, developing stochastic biased variants faces a fundamental techn…

• High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

  Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos · 17 March 2026

  We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and …

• PACED: Distillation and Self-Distillation at the Frontier of Student Competence

  Yuanda Xu, Hejian Sang, Zhengze Zhou, Ran He, Zhipeng Wang · 17 March 2026

  Standard LLM distillation wastes compute on two fronts: problems the student has already mastered (near-zero gradients) and problems far beyond its reach (incoherent gradients that erode existing capabilities). We show that this waste is not merely intuitive but structurally inevitable: the gradient…

• IGU-LoRA: Adaptive Rank Allocation via Integrated Gradients and Uncertainty-Aware Scoring

  Xuan Cui, Huiyue Li, Run Zeng, Yunfei Zhao, Jinrui Qian, Wei Duan, Bo Liu, Zhanpeng Zhou · 17 March 2026

  As large language models (LLMs) scale to billions of parameters, full-parameter fine-tuning becomes compute- and memory-prohibitive. Parameter-efficient fine-tuning (PEFT) mitigates this issue by updating only a small set of task-specific parameters while keeping the base model frozen. Among PEFT ap…

• Grokking as a Variance-Limited Phase Transition: Spectral Gating and the Epsilon-Stability Threshold

  Pratyush Acharya, Habish Dhakal · 17 March 2026

  Standard optimization theories struggle to explain grokking, where generalization occurs long after training convergence. While geometric studies attribute this to slow drift, they often overlook the interaction between the optimizer's noise structure and landscape curvature. This work analyzes Adam…

• Deep learning and the rate of approximation by flows

  Jingpu Cheng, Qianxiao Li, Ting Lin, Zuowei Shen · 17 March 2026

  We investigate the dependence of the approximation capacity of deep residual networks on its depth in a continuous dynamical systems setting. This can be formulated as the general problem of quantifying the minimal time-horizon required to approximate a diffeomorphism by flows driven by a given fami…

• Enhancing LLM Training via Spectral Clipping

  Xiaowen Jiang, Andrei Semenov, Sebastian U. Stich · 17 March 2026

  While spectral-based optimizers like Muon operate directly on the spectrum of updates, standard adaptive methods such as AdamW do not account for the global spectral structure of weights and gradients, leaving them vulnerable to two empirical issues in large language model (LLM) training: (i) the op…

• Interleaved Resampling and Refitting: Data and Compute-Efficient Evaluation of Black-Box Predictors

  Haichen Hu, David Simchi-Levi · 17 March 2026

  We study the problem of evaluating the excess risk of large-scale empirical risk minimization under the square loss. Leveraging the idea of wild refitting and resampling, we assume only black-box access to the training algorithm and develop an efficient procedure for estimating the excess risk. Our …

• Intrinsic training dynamics of deep neural networks

  Sibylle Marcotte, Gabriel Peyr\'e, R\'emi Gribonval · 16 March 2026

  A fundamental challenge in the theory of deep learning is to understand whether gradient-based training can promote parameters belonging to certain lower-dimensional structures (e.g., sparse or low-rank sets), leading to so-called implicit bias. As a stepping stone, motivated by the proof structure …

• Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization

  Noel Smith, Andrzej Ruszczynski · 16 March 2026

  We consider a stochastic optimization problem involving two random variables: a context variable $X$ and a dependent variable $Y$. The objective is to minimize the expected value of a nonlinear loss functional applied to the conditional expectation $\mathbb{E}[f(X, Y,\beta) \mid X]$, where $f$ is a …

• Optimize Wider, Not Deeper: Consensus Aggregation for Policy Optimization

  Zelal Su (Lain), Mustafaoglu, Sungyoung Lee, Eshan Balachandar, Risto Miikkulainen, Keshav Pingali · 16 March 2026

  Proximal policy optimization (PPO) approximates the trust region update using multiple epochs of clipped SGD. Each epoch may drift further from the natural gradient direction, creating path-dependent noise. To understand this drift, we can use Fisher information geometry to decompose policy updates …

• Byzantine-Robust Optimization under $(L_0, L_1)$-Smoothness

  Arman Bolatov, Samuel Horv\'ath, Martin Tak\'a\v{c}, Eduard Gorbunov · 16 March 2026

  We consider distributed optimization under Byzantine attacks in the presence of $(L_0,L_1)$-smoothness, a generalization of standard $L$-smoothness that captures functions with state-dependent gradient Lipschitz constants. We propose Byz-NSGDM, a normalized stochastic gradient descent method with mo…

• Influence Malleability in Linearized Attention: Dual Implications of Non-Convergent NTK Dynamics

  Jose Marie Antonio Mi\~noza, Paulo Mario P. Medina, Sebastian C. Iba\~nez · 16 March 2026

  Understanding the theoretical foundations of attention mechanisms remains challenging due to their complex, non-linear dynamics. This work reveals a fundamental trade-off in the learning dynamics of linearized attention. Using a linearized attention mechanism with exact correspondence to a data-depe…