Stochastic Gradient Optimization Techniques

Neueste Paper

• Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

  Alex Buna, Shirley Xiaoqi Liu, Patrick Rebeschini · 7. August 2026

  In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be s…

• Optimal Training-Time Scaling in Gradual Adaptation

  Zonghuan Xu, Krishna Harish · 6. August 2026

  In gradual adaptation, how should the training time on each task change as the number of intermediate tasks increases? We study this question for overparameterized linear regression tasks that change smoothly and share a zero-loss solution. With $N$ tasks and training time $s_N$ on each, the final l…

• Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics

  Han Bao · 6. August 2026

  Gradient descent has been of particular interest in modern machine learning beyond sole focus on optimization. Implicit bias emerging from optimization, though not being encoded by the learning objective, often prevents from overfitting to spurious patterns. A typical instance is the max-margin impl…

• The Loss Does Not See the Basis, but Adam Does

  Devender Singh · 6. August 2026

  Gradient descent on a factored model $W = UV^\top$ is implicitly biased toward low-rank solutions, while Adam, starting from the same small initialization, is not. We trace the difference to the gauge symmetry of the loss, its invariance under $(U, V) \mapsto (UQ, VQ)$. Gradient flow's low-rank mech…

• A Trust-region Framework for Moment Estimation

  Oluwasegun A. Somefun · 6. August 2026

  In this paper, we develop a trust-region framework for understanding the behavior of adaptive moment estimation mechanisms, such as \textsc{Adam}, in stochastic gradient optimization. Specifically, in this framework, the magnitude of the update step for each individual weight is constrained within a…

• Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework

  Junwen Qiu, Bohao Ma, Andre Milzarek, Junyu Zhang · 5. August 2026

  Unit excitation (UE) is a common assumption in stochastic saddle avoidance: the stochastic error must have a uniformly positive component along every direction, in expectation. This condition gives a direct way to rule out convergence to strict saddles, but it also oversimplifies the actual noise st…

• Joint Affine Spectral Shaping: Coupling Weight and Bias Updates Beyond Weight-Only Muon

  Gongyue Zhang, Honghai Liu · 5. August 2026

  Matrix spectral optimizers reshape weight-update spectra but usually delegate vector-valued biases to a separate optimizer. We study whether this separation is neutral. We formulate each affine layer as a joint momentum matrix $A=[M_W,\alpha m_b]$ and apply a capped regularized-inverse spectral map …

• Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices

  Zhao Song · 5. August 2026

  For $n$ unit vectors $x_1,\ldots,x_n \in \mathbb{R}^d$, we study the continuous ReLU derivative Gram matrix $H$, whose entries are obtained by averaging pairwise gated inner products over a standard Gaussian direction. Writing $ \Delta_\pm := \min_{i \neq j} \min\{ \|x_i-x_j\|_2, \|x_i+x_j\|_2 \} $ …

• On the Implicit Flatness Bias of Sharpness-Aware Minimization: A Linear Stability Analysis with Quantitative Hyperparameter Bounds

  Jiaxin Deng, Junbiao Pang · 5. August 2026

  Sharpness-Aware Minimization (SAM) improves generalization by seeking parameters whose loss is robust to local adversarial perturbations, but the quantitative mechanism underlying its implicit bias toward flat minima remains unclear. In particular, the perturbation radius $\rho$ is typically treated…

• The Fourth Quadrant: A Stylized View of Benign Misfitting

  Gireeja Ranade, Anant Sahai · 4. August 2026

  Training error is what we can observe on a training set; test error is the quantity we actually care about. We study linear regression with squared-error in a deterministic $(d+1)$-dimensional single-spike model. Each stylized training vector has the same informative spike coordinate, of amplitude $…

• The Convergence Behavior of Adam under Heavy-Tailed Noise

  Yijiang Pang · 4. August 2026

  We establish the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise. While several Adam variants are known to achieve optimal iteration complexity in bounded-variance nonsmooth nonconvex optimization, little is understood about their behavior wh…

• AOS: Adaptive Optimizer Switching via Training-State Signals for Faster Convergence and Better Generalization

  Alok Kumar Pandey, Umang Chaturvedi, Aatish Rana, Gopi Krishna Nedanuri · 4. August 2026

  Single-optimizer training is a poor fit for the distinct phases of deep network optimization: adaptive methods handle noisy early gradients well but overshoot flat minima, while SGD with momentum generalizes better in the late phase but converges slowly early on. We introduce AOS-R (Adaptive Optim…

• Adaptive Gradient-Based Methods for a Broader Class of Optimization Problems under Performative Prediction

  Hiroki Hamaguchi, Yuya Hikima, Hiroshi Sawada, Akiko Takeda · 30. Juli 2026

  We study optimization under performative prediction, where deploying a model affects the future data distribution. For this setting, several gradient-based approaches have been proposed. However, they typically assume specific data distributions or loss functions, which limit their practical applica…

• Between Gradient and Natural Gradient: A Continuum of LoRA Initializations

  Dianze Liu, Farshid Ghezelbash · 30. Juli 2026

  Low-rank adaptation (LoRA) fine-tunes large pretrained models at a fraction of the cost of full fine-tuning, but its performance depends strongly on how the adapters are initialized. Recent schemes initialize the adapters from the downstream loss gradient: some project the raw gradient onto its top …

• Quotient Dynamics, Effective Curvature, and Implicit Bias in Positive Quadratic Networks

  Pengcheng Cheng · 29. Juli 2026

  Positive quadratic networks admit the low-rank representation f_U(x)=x^top UU^top x, where Uinmathbb{R}^{dtimes r} is identifiable only up to right orthogonal multiplication, representing a rank-r PSD matrix Q=UU^top. We study how this quotient structure governs training dynamics, curvature, recover…

• Retraction-Free Optimization over the Stiefel Manifold for the LoRA Fine-Tuning

  Yuan Zhang, Jiang Hu, Zhijian Lai, Lin Lin, Zaiwen Wen · 29. Juli 2026

  Optimization over the Stiefel manifold plays a significant role in various machine learning tasks. Existing methods either use the retraction operators, requiring costly orthonormalization for large-scale matrices, or employ landing methods that rely on careful step size selection and penalty parame…

• Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization

  Lavinia Ghita, Dhruv Desai, Jake Goldberg, Roman Yokunda Enzmann · 28. Juli 2026

  Symmetric non-negative matrix factorization (SymNMF) recovers latent group structure from a dependence matrix, but its dense, quadratic-memory objective has confined prior work to moderate sizes. We present a large-scale GPU study of seven algorithm families (over 30 configurations) on absolute Pear…

• A Resolution of the SS--RS--GD Inequalities

  Binghui Peng · 28. Juli 2026

  Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices $A_1,\dots,A_n$, the operators $W_{ss}$, $W_{rs}$, and $W_{gd}$ that encode the expected iterate of single-shuffle SGD, random-reshuffle SGD, and gradient descent on a …

• Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided H\"older Regularity

  Arzu Ahmadova, Ismail Huseynov · 28. Juli 2026

  We study adaptive gradient descent for continuously differentiable, possibly nonconvex objectives under one-sided H\"older regularity. Unlike classical H\"older- or Lipschitz-gradient assumptions, which control the full gradient variation, our condition bounds only the directional term appearing in …

• The Entropic Bound for Transformers: Why Static Rank Fails and Attention-Native Rank Recovers

  Byeong Hoon Yoon · 28. Juli 2026

  Neural scaling laws describe how loss decreases as models, data, and compute grow, but they do not answer a prior question: for a fixed task, what is the minimum model capacity required to solve it? We study this through the Entropic Bound, a spectral notion of task-intrinsic capacity for Transforme…

• Nesterov acceleration in optimizing over probability measures

  Jiaqi Tang, Qin Li, Wilfrid Gangbo · 28. Juli 2026

  Optimization over probability measures has become an increasingly important paradigm in modern machine learning, scientific computing, and uncertainty quantification. Motivated by Nesterov's accelerated gradient method in Euclidean space, we develop Heavy-ball and Nesterov acceleration methods over …

• Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Scheduling

  Alexandru Meterez, Depen Morwani, Jingfeng Wu, Costin-Andrei Oncescu, Cengiz Pehlevan, Sham Kakade · 28. Juli 2026

  Increasing the batch size during training -- a ''batch ramp'' -- is a promising strategy to accelerate large language model pretraining. While for SGD, doubling the batch size can be equivalent to halving the learning rate, the optimal strategy for adaptive optimizers like Adam is less clear. As a r…

• Hierarchical Grading in Large Language Models

  T. Shaska · 28. Juli 2026

  We introduce Graded Large Language Models (GLLMs), an algebraic framework that equips the representation space of a transformer with a grading and propagates the induced weighted scalar action through embeddings, self-attention, and the training objective. The construction extends the theory of grad…

• Operator Neural Jump ODEs: $L^2$-optimal prediction in function spaces

  Florian Krach, Oliver L\"othgren, Josef Teichmann · 28. Juli 2026

  In this paper, we study the extension of Neural Jump ODEs to infinite-dimensional function spaces. In particular, the underlying process $X$ now takes values in $L^2(\Xi, \mathbb{R}^{d_X})$ instead of $\mathbb{R}^{d_X}$ and the Operator NJ-ODE approximates the optimal predictor of this process by pr…

• Mini-batch Noise Lowers Sharpness via Dominant-Subspace Fluctuations

  Junho So, Dongwook Shin · 28. Juli 2026

  During SGD training, the gradients often align strongly with the dominant subspace spanned by the top-$k$ eigenvectors of the Hessian of the loss. While this seems to naturally imply that loss reduction mainly occurs within this space, prior work has shown that updates within this dominant subspace …