Stochastic Gradient Optimization Techniques

Latest papers

• Gaussian Approximation for Two-Timescale Linear Stochastic Approximation

  Bogdan Butyrin, Artemy Rubtsov, Alexey Naumov, Vladimir Ulyanov, Sergey Samsonov · 10 December 2025

  In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise. Focusing on both the last iterate and Polyak-Ruppert averaging regimes, we derive bounds for nor…

• Understanding the Implicit Regularization of Gradient Descent in Over-parameterized Models

  Jianhao Ma, Geyu Liang, Salar Fattahi · 10 December 2025

  Implicit regularization refers to the tendency of local search algorithms to converge to low-dimensional solutions, even when such structures are not explicitly enforced. Despite its ubiquity, the mechanism underlying this behavior remains poorly understood, particularly in over-parameterized settin…

• Correction of Decoupled Weight Decay

  Jason Chuan-Chih Chou · 10 December 2025

  Decoupled weight decay, solely responsible for the performance advantage of AdamW over Adam, has long been set to proportional to learning rate $\gamma$ without questioning. Some researchers have recently challenged such assumption and argued that decoupled weight decay should be set $\propto \gamma…

• LUNA: Linear Universal Neural Attention with Generalization Guarantees

  Ashkan Shahbazi, Ping He, Ali Abbasi, Yikun Bai, Xinran Liu, Elaheh Akbari, Darian Salehi, Navid NaderiAlizadeh, Soheil Kolouri · 10 December 2025

  Scaling attention faces a critical bottleneck: the $\mathcal{O}(n^2)$ quadratic computational cost of softmax attention, which limits its application in long-sequence domains. While linear attention mechanisms reduce this cost to $\mathcal{O}(n)$, they typically rely on fixed random feature maps, su…

• Mathematical Foundations of Neural Tangents and Infinite-Width Networks

  Rachana Mysore, Preksha Girish, Kavitha Jayaram, Shrey Kumar, Preksha Girish, Shravan Sanjeev Bagal, Kavitha Jayaram, Shreya Aravind Shastry · 10 December 2025

  We investigate the mathematical foundations of neural networks in the infinite-width regime through the Neural Tangent Kernel (NTK). We propose the NTK-Eigenvalue-Controlled Residual Network (NTK-ECRN), an architecture integrating Fourier feature embeddings, residual connections with layerwise scali…

• Complexity of One-Dimensional ReLU DNNs

  Jonathan Kogan, Hayden Jananthan, Jeremy Kepner · 10 December 2025

  We study the expressivity of one-dimensional (1D) ReLU deep neural networks through the lens of their linear regions. For randomly initialized, fully connected 1D ReLU networks (He scaling with nonzero bias) in the infinite-width limit, we prove that the expected number of linear regions grows as $\…

• PVeRA: Probabilistic Vector-Based Random Matrix Adaptation

  Leo Fillioux, Enzo Ferrante, Paul-Henry Courn\`ede, Maria Vakalopoulou, Stergios Christodoulidis · 9 December 2025

  Large foundation models have emerged in the last years and are pushing performance boundaries for a variety of tasks. Training or even finetuning such models demands vast datasets and computational resources, which are often scarce and costly. Adaptation methods provide a computationally efficient s…

• Jointly Computation- and Communication-Efficient Distributed Learning

  Xiaoxing Ren, Nicola Bastianello, Karl H. Johansson, Thomas Parisini · 9 December 2025

  We address distributed learning problems over undirected networks. Specifically, we focus on designing a novel ADMM-based algorithm that is jointly computation- and communication-efficient. Our design guarantees computational efficiency by allowing agents to use stochastic gradients during local tra…

• Stepsize anything: A unified learning rate schedule for budgeted-iteration training

  Anda Tang, Yiming Dong, Yutao Zeng, zhou Xun, Zhouchen Lin · 9 December 2025

  The expanding computational costs and limited resources underscore the critical need for budgeted-iteration training, which aims to achieve optimal learning within predetermined iteration budgets. While learning rate schedules fundamentally govern the performance of different networks and tasks, par…

• AuON: A Linear-time Alternative to Orthogonal Momentum Updates

  Dipan Maity · 9 December 2025

  Orthogonal momentum gradient updates have emerged to overcome the limitations of vector-based optimizers like Adam. The vector-based optimizer Adam suffers from high memory costs and ill-conditioned momentum gradient updates. However, traditional Orthogonal momentum approaches, such as SVD/QR decomp…

• Optimizing Optimizers for Fast Gradient-Based Learning

  Jaerin Lee, Kyoung Mu Lee · 9 December 2025

  We lay the theoretical foundation for automating optimizer design in gradient-based learning. Based on the greedy principle, we formulate the problem of designing optimizers as maximizing the instantaneous decrease in loss. By treating an optimizer as a function that translates loss gradient signals…

• Generalized Probabilistic Approximate Optimization Algorithm

  Abdelrahman S. Abdelrahman, Shuvro Chowdhury, Flaviano Morone, Kerem Y. Camsari · 9 December 2025

  We introduce a generalized \textit{Probabilistic Approximate Optimization Algorithm (PAOA)}, a classical variational Monte Carlo framework that extends and formalizes prior work by Weitz \textit{et al.}~\cite{Combes_2023}, enabling parameterized and fast sampling on present-day Ising machines and pr…

• FOAM: Blocked State Folding for Memory-Efficient LLM Training

  Ziqing Wen, Jiahuan Wang, Ping Luo, Dongsheng Li, Tao Sun · 9 December 2025

  Large language models (LLMs) have demonstrated remarkable performance due to their large parameter counts and extensive training data. However, their scale leads to significant memory bottlenecks during training, especially when using memory-intensive optimizers like Adam. Existing memory-efficient …

• Contextual Strongly Convex Simulation Optimization: Optimize then Predict with Inexact Solutions

  Nifei Lin, Heng Luo, L. Jeff Hong · 9 December 2025

  In this work, we study contextual strongly convex simulation optimization and adopt an "optimize then predict" (OTP) approach for real-time decision making. In the offline stage, simulation optimization is conducted across a set of covariates to approximate the optimal-solution function; in the onli…

• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance

  Georgios Tzachristas, Lei Deng, Ioannis Tzachristas, Gong Zhang, Renhai Chen · 9 December 2025

  We develop a unified mathematical framework for certified Top-$k$ attention truncation that quantifies approximation error at both the distribution and output levels. For a single attention distribution $P$ and its Top-$k$ truncation $\hat P$, we show that the total-variation distance coincides with…

• A Bootstrap Perspective on Stochastic Gradient Descent

  Hongjian Lan, Yucong Liu, Florian Sch\"afer · 9 December 2025

  Machine learning models trained with \emph{stochastic} gradient descent (SGD) can generalize better than those trained with deterministic gradient descent (GD). In this work, we study SGD's impact on generalization through the lens of the statistical bootstrap: SGD uses gradient variability under ba…

• SSP-GNN: Learning to Track via Bilevel Optimization

  Griffin Golias, Masa Nakura-Fan, Vitaly Ablavsky · 9 December 2025

  We propose a graph-based tracking formulation for multi-object tracking (MOT) where target detections contain kinematic information and re-identification features (attributes). Our method applies a successive shortest paths (SSP) algorithm to a tracking graph defined over a batch of frames. The edge…

• Comparing BFGS and OGR for Second-Order Optimization

  Adrian Przybysz, Miko{\l}aj Ko{\l}ek, Franciszek Sobota, Jarek Duda · 9 December 2025

  Estimating the Hessian matrix, especially for neural network training, is a challenging problem due to high dimensionality and cost. In this work, we compare the classical Sherman-Morrison update used in the popular BFGS method (Broy-den-Fletcher-Goldfarb-Shanno), which maintains a positive definite…

• Stochastic Approximation with Block Coordinate Optimal Stepsizes

  Tao Jiang, Lin Xiao · 9 December 2025

  We consider stochastic approximation with block-coordinate stepsizes and propose adaptive stepsize rules that aim to minimize the expected distance from the next iterate to an (unknown) target point. These stepsize rules employ online estimates of the second moment of the search direction along each…

• Zero Generalization Error Theorem for Random Interpolators via Algebraic Geometry

  Naoki Yoshida, Isao Ishikawa, Masaaki Imaizumi · 9 December 2025

  We theoretically demonstrate that the generalization error of interpolators for machine learning models under teacher-student settings becomes 0 once the number of training samples exceeds a certain threshold. Understanding the high generalization ability of large-scale models such as deep neural ne…

• Entropic Confinement and Mode Connectivity in Overparameterized Neural Networks

  Luca Di Carlo, Chase Goddard, David J. Schwab · 9 December 2025

  Modern neural networks exhibit a striking property: basins of attraction in the loss landscape are often connected by low-loss paths, yet optimization dynamics generally remain confined to a single convex basin and rarely explore intermediate points. We resolve this paradox by identifying entropic b…

• ONG: Orthogonal Natural Gradient Descent

  Yajat Yadav, Patrick Mendoza, Jathin Korrapati · 9 December 2025

  Orthogonal Gradient Descent (OGD) has emerged as a powerful method for continual learning. However, its Euclidean projections do not leverage the underlying information-geometric structure of the problem, which can lead to suboptimal convergence in learning tasks. To address this, we propose incorpo…

• Learnability Window in Gated Recurrent Neural Networks

  Lorenzo Livi · 8 December 2025

  We develop a theoretical framework that explains how gating mechanisms determine the learnability window $\mathcal{H}_N$ of recurrent neural networks, defined as the largest temporal horizon over which gradient information remains statistically recoverable. While classical analyses emphasize numeric…

• Symmetric Linear Dynamical Systems are Learnable from Few Observations

  Minh Vu, Andrey Y. Lokhov, Marc Vuffray · 8 December 2025

  We consider the problem of learning the parameters of a $N$-dimensional stochastic linear dynamics under both full and partial observations from a single trajectory of time $T$. We introduce and analyze a new estimator that achieves a small maximum element-wise error on the recovery of symmetric dyn…

• Convergence for Discrete Parameter Update Schemes

  Paul Wilson, Fabio Zanasi, George Constantinides · 8 December 2025

  Modern deep learning models require immense computational resources, motivating research into low-precision training. Quantised training addresses this by representing training components in low-bit integers, but typically relies on discretising real-valued updates. We introduce an alternative appro…