Stochastic Gradient Optimization Techniques

Latest papers

• Smart predict-then-robustly-optimize

  Aakil Caunhye, Xuefei Lu, Belen Martin-Barragan · 27 July 2026

  In this paper, we propose and study a robust variant of the smart predict-then-optimize approach that accounts for prediction shifts due to disturbance in the covariate feature space. While traditional integrated-learning-and-optimization models assume that side information is perfectly revealed, em…

• A Defense of the Quadratic Model

  Alexandru Meterez, Pranav Ajit Nair, Depen Morwani, Cengiz Pehlevan, Sham Kakade, Alex Damian · 27 July 2026

  Due to the complexity of neural network loss landscapes, optimization theory is forced to rely on idealized models, and there is generally a tradeoff between how theoretically tractable the model is, and how accurately it describes the true optimization dynamics. In this work, we stress test the sim…

• Beyond Negative-Ridge Endpoints: Mixed-Sign Spectral Regularization via Negative-Shifted Gradient Descent

  Peng Zhao · 27 July 2026

  In overparameterized linear regression, many weak spectral directions act like a ridge penalty on the signal-bearing spectrum; negative ridge is the natural correction, pushing filters above one. The stable negative-ridge endpoint, however, is structurally limited: its pole must stay below the small…

• Hyperball May Not Be a Free Lunch

  Yihao Xiao, Jialong Sun, Zitian Gao, Zeming Wei, Chutian Wang, Ran Tao, Jiaye Teng, Bryan Dai · 27 July 2026

  For scale-invariant deep networks, Hyperball-style optimizers have shown strong performance in large-scale training by fixing the norms of matrix-valued parameters and normalizing updates. However, the source of their advantage remains unclear. Starting from the angular displacement between consecut…

• Minimum Norm Interpolation via the Local Theory of Banach Spaces: The Role of $2$-Uniform Convexity

  Gil Kur, Pierre Bizeul · 27 July 2026

  The minimum-norm interpolator (MNI) framework has recently attracted considerable attention as a tool for understanding generalization in overparameterized models, such as neural networks. In this work, we study the MNI under a $2$-uniform convexity assumption, which is weaker than requiring the nor…

• Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model

  Ruijian Han, Ding Lu, Yiming Xu · 27 July 2026

  Zermelo's algorithm is a classical method for computing the maximum likelihood estimator in the Bradley--Terry (BT) model, but its convergence can be slow in practice. To accelerate computation, Newman introduced a family of Zermelo-type fixed-point iterations parameterized by $\alpha$, with Zermelo…

• On the Convergence of Stochastic Low-Rank Adaptation

  Ru Wang, Chengchang Liu, John C. S. Lui · 27 July 2026

  Low-rank adaptation (LoRA) optimizes $J(B,A)=\mathcal L(W_\mathrm{base}+sBA)$ over two adapters $B \in \mathbb{R}^{m \times r}$ and $A \in \mathbb{R}^{r \times n}$ that form a low-rank update to a frozen pretrained weight matrix $W_\mathrm{base} \in \mathbb{R}^{m \times n}$. The prior analysis shows…

• Scaling Laws for Classical Machine Learning on Tabular Data: A Benchmark Study

  Kaihua Ding · 27 July 2026

  Prior classical-ML learning-curve work fits power laws to tree, linear, and kernel models on tabular data, but at small scale: typically one curve, one team, a handful of cells. We present a distributed classroom-scale replication: 127 students each ran a fixed protocol on 3 assigned datasets, drawn…

• Three-Pronged Spectral Control for Federated Parameter Efficient Fine Tuning

  Shiva Raj Pokhrel, Dipsan Bhattarai, Anwar Walid · 24 July 2026

  Federated parameter-efficient fine-tuning (PEFT) enables communication-efficient adaptation of large pretrained models on decentralized edge data, but it remains fragile under non-IID client heterogeneity. In low-rank adaptation (LoRA), different clients may learn locally useful but spectrally misal…

• When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers

  Tong Zhang, Junhao Hu, Yun Peng, Tao Xie · 24 July 2026

  When does a weight-tied looped transformer -- one block applied T times -- implement an actual algorithm? We answer with four findings from controlled populations on group word problems. (1) The budget law: free training installs a linear computation frontier, a mechanism that solves v positions per…

• Double-Scoring: Reliable Extraction of Strong Lottery Tickets

  Bryce A. Christopherson, Jack Baretz, Darian Colgrove, Salah Dandan · 24 July 2026

  The lottery ticket hypothesis proposes that large random neural networks contain sparse subnetworks that can match the performance of dense models after comparable training. A stronger version asserts that sufficiently overparameterized random networks contain subnetworks that are already accurate b…

• From Atoms to Entropy: Optimal Noise Allocation for Diffusion Training in the Convex Regime

  Luca Ambrogioni, Giulio Franzese, Alberto Foresti, Gabriel Raya, Bac Nguyen, Georgios Batzolis, Yuhta Takida, Naoki Murata, Chieh-Hsin Lai, Yuki Mitsufuji · 24 July 2026

  How should a diffusion model decide which noise levels to train on, and how much? Despite the importance of this choice, current noise schedules are based largely on heuristics or empirical tuning. Here, we develop a general statistical framework for studying asymptotically optimal noise-level alloc…

• Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization

  Shijie Pan, Agustin Castellano, Zeyu Shen, Enrique Mallada · 24 July 2026

  Learning-enabled decision systems often use offline data or computation to reduce online compute cost. Despite the empirical success of such approaches, there is limited general understanding of how much offline information is needed to achieve a desired accuracy under a fixed online computation bud…

• GaugeQuant: Online Learning of Quantization-Optimal Bases from LLM Symmetries

  Miguel P. Bento, Jo\~ao Seabra · 24 July 2026

  Transformers are known to have internal continuous symmetries that leave outputs invariant, while modifying quantization. GaugeQuant leverages this in-training by introducing a LogSumExp term to the loss that breaks the symmetries, thus selecting a basis that minimizes activation outliers. A stop-gr…

• New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

  Cornelius Brand, Robert Ganian, Mathis Rocton · 24 July 2026

  In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a …

• SOAP, Muon, and Beyond: Pushing LLM Pretraining Scales

  Mikail Khona, Aditya Vavre, Boxiang Wang, Deyu Fu, Hao Wu, Mike Chrzanowski, Bryan Catanzaro, Dheevatsa Mudigere, Jeff Pool, Michael Lightstone, Mohammad Shoeybi, Mostofa Patwary, Nima Tajbakhsh, Tijmen Blankevoort · 24 July 2026

  Higher-order optimizers such as Muon and SOAP offer faster convergence than AdamW, but their computational cost and numerical stability challenges have limited adoption at scale. In this work, we adapt and enhance preconditioned gradient methods to overcome the practical challenges of large-scale LL…

• Pipelined Gradient Coding

  Xian Su, Jun Li · 24 July 2026

  In large-scale machine learning, distributed training commonly involves multiple workers evaluating the gradients of the model on different dataset partitions. A common challenge is the presence of straggling workers, which may significantly slow down training. Traditional gradient coding (GC) addre…

• Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$

  Dawei Li, Xiaotian Jiang, Mingyi Hong · 24 July 2026

  Barzilai--Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. In particular, a central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initializ…

• Weight-norm Criticality: A Mechanism for Loss Spikes Induced by the Normalization and Weight Decay

  Xiaolong Li, Zhangchen Zhou, Zhi-Qin John Xu · 24 July 2026

  Most explanations of training instability focus on \emph{learning-rate criticality}, typically characterized by the Edge of Stability, beyond which optimization becomes unstable. We argue that, in practical deep neural network training, there is an additional and often overlooked \emph{weight-norm c…

• An Isotropy-Preserving Spectral Cap for Muon: Theory and Three Case Studies

  Jiachun Li · 23 July 2026

  Muon and related matrix-sign optimizers are increasingly used to pre-train large language models, but their effect on the internal geometry of individual weight matrices is not well understood. This preliminary report proposes a unified framework built on a single idealizing assumption -- exact scal…

• Theory-to-Practice Gap for Neural Networks and Neural Operators

  Philipp Grohs, Samuel Lanthaler, Margaret Trautner · 23 July 2026

  This work studies the sampling complexity of learning with ReLU neural networks and neural operators. For mappings belonging to relevant approximation spaces, we derive upper bounds on the best-possible convergence rate of any learning algorithm, with respect to the number of samples. In the finite-…

• A Structure-Adaptive Random Feature Method for High-Dimensional Elliptic PDEs

  Jiale Linghu, Hao Dong, Yangshuai Wang · 23 July 2026

  Random-feature methods reduce high-dimensional elliptic PDE collocation to linear coefficient problems, but full-dimensional trial spaces overlook lower-dimensional structure. We introduce the Hierarchical Analysis-of-Variance Random Feature Method (HA-RFM), which selects coordinate blocks using clo…

• Local Stability and Gaussian Smoothing of Quantized Neural Networks

  Sergey Salishev, Anton Makarov, Oleg Granichin · 23 July 2026

  We study Gaussian averaging as a smooth surrogate for quantized neural models. Under bounded local oscillation, we derive a local dimension-dependent bound on |f-g|, linking Gaussian smoothing to the stability analysis of discontinuous networks. We compute closed-form Gaussian averages of the rectif…

• RELTA-SGLD: Relative-Growth Localized Taming for Nonconvex Stochastic-Gradient Langevin Learning

  Yiwei Zhou, Ziheng Chen · 23 July 2026

  We introduce RELTA-SGLD, a taming scheme that stabilizes superlinear stochastic-gradient updates while reducing unnecessary suppression of the original learning drift. A threshold determines where the taming turns on, while a relative-growth principle derived from the one-step Lyapunov stability con…

• On Optimization Complexity of Second-Order Certified Unlearning

  Nikita Doikov, Anastasia Koloskova · 23 July 2026

  We study machine unlearning: the removal of memorized training data from a trained model. Specifically, we investigate the algorithmic complexity of certified unlearning from an optimization perspective. We formalize the goal of an unlearning algorithm as simultaneously achieving certified unlearnin…