Stochastic Gradient Optimization Techniques

Derniers papiers

• The Implicit Bias of Steepest Descent with Mini-batch Stochastic Gradient

  Jichu Li, Xuan Tang, Difan Zou · 13 février 2026

  A variety of widely used optimization methods like SignSGD and Muon can be interpreted as instances of steepest descent under different norm-induced geometries. In this work, we study the implicit bias of mini-batch stochastic steepest descent in multi-class classification, characterizing how batch …

• Fine-tuning Quantized Neural Networks with Zeroth-order Optimization

  Sifeng Shang, Jiayi Zhou, Chenyu Lin, Minxian Li, Kaiyang Zhou · 13 février 2026

  As the size of large language models grows exponentially, GPU memory has become a bottleneck for adapting these models to downstream tasks. In this paper, we aim to push the limits of memory-efficient training by minimizing memory usage on model weights, gradients, and optimizer states, within a uni…

• Efficient Analysis of the Distilled Neural Tangent Kernel

  Jamie Mahowald, Brian Bell, Alex Ho, Michael Geyer · 13 février 2026

  Neural tangent kernel (NTK) methods are computationally limited by the need to evaluate large Jacobians across many data points. Existing approaches reduce this cost primarily through projecting and sketching the Jacobian. We show that NTK computation can also be reduced by compressing the data dime…

• Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance

  Hongxu Chen, Ke Wei, Luo Luo · 13 février 2026

  Decentralized optimization is critical for solving large-scale machine learning problems over distributed networks, where multiple nodes collaborate through local communication. In practice, the variances of stochastic gradient estimators often differ across nodes, yet their impact on algorithm desi…

• Fully First-Order Algorithms for Online Bilevel Optimization

  Tingkai Jia, Cheng Chen · 13 février 2026

  In this work, we study non-convex-strongly-convex online bilevel optimization (OBO). Existing OBO algorithms are mainly based on hypergradient descent, which requires access to a Hessian-vector product (HVP) oracle and potentially incurs high computational costs. By reformulating the original OBO pr…

• On the Complexity of Offline Reinforcement Learning with $Q^\star$-Approximation and Partial Coverage

  Haolin Liu, Braham Snyder, Chen-Yu Wei · 13 février 2026

  We study offline reinforcement learning under $Q^\star$-approximation and partial coverage, a setting that motivates practical algorithms such as Conservative $Q$-Learning (CQL; Kumar et al., 2020) but has received limited theoretical attention. Our work is inspired by the following open question: "…

• Optimal Initialization in Depth: Lyapunov Initialization and Limit Theorems for Deep Leaky ReLU Networks

  Constantin Kogler, Tassilo Schwarz, Samuel Kittle · 12 février 2026

  The development of effective initialization methods requires an understanding of random neural networks. In this work, a rigorous probabilistic analysis of deep unbiased Leaky ReLU networks is provided. We prove a Law of Large Numbers and a Central Limit Theorem for the logarithm of the norm of netw…

• Hierarchical Zero-Order Optimization for Deep Neural Networks

  Sansheng Cao, Zhengyu Ma, Yonghong Tian · 12 février 2026

  Zeroth-order (ZO) optimization has long been favored for its biological plausibility and its capacity to handle non-differentiable objectives, yet its computational complexity has historically limited its application in deep neural networks. Challenging the conventional paradigm that gradients propa…

• Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementation

  Deyi Kong, Zaiwei Chen, Shuzhong Zhang, Shancong Mou · 12 février 2026

  In this work, we propose Natural Hypergradient Descent (NHGD), a new method for solving bilevel optimization problems. To address the computational bottleneck in hypergradient estimation--namely, the need to compute or approximate Hessian inverse--we exploit the statistical structure of the inner op…

• Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization

  Benjy Friedmann, Nadav Dym · 12 février 2026

  Recent advances in Neural Combinatorial Optimization (NCO) have been dominated by diffusion models that treat the Euclidean Traveling Salesman Problem (TSP) as a stochastic $N \times N$ heatmap generation task. In this paper, we propose CycFlow, a framework that replaces iterative edge denoising wit…

• Position: Many generalization measures for deep learning are fragile

  Shuofeng Zhang, Ard Louis · 12 février 2026

  In this position paper, we argue that many post-mortem generalization measures -- those computed on trained networks -- are \textbf{fragile}: small training modifications that barely affect the performance of the underlying deep neural network can substantially change a measure's value, trend, or sc…

• Renet: Principled and Efficient Relaxation for the Elastic Net via Dynamic Objective Selection

  Albert Dorador · 12 février 2026

  We introduce Renet, a principled generalization of the Relaxed Lasso to the Elastic Net family of estimators. While, on the one hand, $\ell_1$-regularization is a standard tool for variable selection in high-dimensional regimes and, on the other hand, the $\ell_2$ penalty provides stability and solu…

• Learning under Quantization for High-Dimensional Linear Regression

  Dechen Zhang, Junwei Su, Difan Zou · 12 février 2026

  The use of low-bit quantization has emerged as an indispensable technique for enabling the efficient training of large-scale models. Despite its widespread empirical success, a rigorous theoretical understanding of its impact on learning performance remains notably absent, even in the simplest linea…

• Deep Network Trainability via Persistent Subspace Orthogonality

  Alex Massucco, Davide Murari, Carola-Bibiane Sch\"onlieb · 12 février 2026

  Training neural networks via backpropagation is often hindered by vanishing or exploding gradients. In this work, we design architectures that mitigate these issues by analyzing and controlling the network Jacobian. We first provide a unified characterization for a class of networks with orthogonal …

• A Unified Theory of Random Projection for Influence Functions

  Pingbang Hu, Yuzheng Hu, Jiaqi W. Ma, Han Zhao · 12 février 2026

  Influence functions and related data attribution scores take the form of $g^{\top}F^{-1}g^{\prime}$, where $F\succeq 0$ is a curvature operator. In modern overparameterized models, forming or inverting $F\in\mathbb{R}^{d\times d}$ is prohibitive, motivating scalable influence computation via random …

• Convergence Rates for Distribution Matching with Sliced Optimal Transport

  Gauthier Thurin (ENS-PSL), Claire Boyer (LMO, IUF), Kimia Nadjahi (ENS-PSL) · 12 février 2026

  We study the slice-matching scheme, an efficient iterative method for distribution matching based on sliced optimal transport. We investigate convergence to the target distribution and derive quantitative non-asymptotic rates. To this end, we establish __ojasiewicz-type inequalities for the Sliced-W…

• Rank-Accuracy Trade-off for LoRA: A Gradient-Flow Analysis

  Michael Rushka, Diego Klabjan · 12 février 2026

  Previous empirical studies have shown that LoRA achieves accuracy comparable to full-parameter methods on downstream fine-tuning tasks, even for rank-1 updates. By contrast, the theoretical underpinnings of the dependence of LoRA's accuracy on update rank remain relatively unexplored. In this work, …

• Deep Learning of Compositional Targets with Hierarchical Spectral Methods

  Hugo Tabanelli, Yatin Dandi, Luca Pesce, Florent Krzakala · 12 février 2026

  Why depth yields a genuine computational advantage over shallow methods remains a central open question in learning theory. We study this question in a controlled high-dimensional Gaussian setting, focusing on compositional target functions. We analyze their learnability using an explicit three-laye…

• Low-Dimensional Execution Manifolds in Transformer Learning Dynamics: Evidence from Modular Arithmetic Tasks

  Yongzhong Xu · 12 février 2026

  We investigate the geometric structure of learning dynamics in overparameterized transformer models through carefully controlled modular arithmetic tasks. Our primary finding is that despite operating in high-dimensional parameter spaces ($d=128$), transformer training trajectories rapidly collapse …

• $\mu$pscaling small models: Principled warm starts and hyperparameter transfer

  Yuxin Ma, Nan Chen, Mateo D\'iaz, Soufiane Hayou, Dmitriy Kunisky, Soledad Villar · 12 février 2026

  Modern large-scale neural networks are often trained and released in multiple sizes to accommodate diverse inference budgets. To improve efficiency, recent work has explored model upscaling: initializing larger models from trained smaller ones in order to transfer knowledge and accelerate convergenc…

• Adaptive Optimization via Momentum on Variance-Normalized Gradients

  Francisco Patitucci, Aryan Mokhtari · 12 février 2026

  We introduce MVN-Grad (Momentum on Variance-Normalized Gradients), an Adam-style optimizer that improves stability and performance by combining two complementary ideas: variance-based normalization and momentum applied after normalization. MVN-Grad scales each coordinate by an exponential moving ave…

• Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization

  Benjy Friedmann, Nadav Dym · 12 février 2026

  Recent advances in Neural Combinatorial Optimization (NCO) have been dominated by diffusion models that treat the Euclidean Traveling Salesman Problem (TSP) as a stochastic $N \times N$ heatmap generation task. In this paper, we propose CycFlow, a framework that replaces iterative edge denoising wit…

• SVD-Preconditioned Gradient Descent Method for Solving Nonlinear Least Squares Problems

  Zhipeng Chang, Wenrui Hao, Nian Liu · 11 février 2026

  This paper introduces a novel optimization algorithm designed for nonlinear least-squares problems. The method is derived by preconditioning the gradient descent direction using the Singular Value Decomposition (SVD) of the Jacobian. This SVD-based preconditioner is then integrated with the first- a…

• WildCat: Near-Linear Attention in Theory and Practice

  Tobias Schr\"oder, Lester Mackey · 11 février 2026

  We introduce WildCat, a high-accuracy, low-cost approach to compressing the attention mechanism in neural networks. While attention is a staple of modern network architectures, it is also notoriously expensive to deploy due to resource requirements that scale quadratically with the input sequence le…

• Step-Size Stability in Stochastic Optimization: A Theoretical Perspective

  Fabian Schaipp, Robert M. Gower, Adrien Taylor · 11 février 2026

  We present a theoretical analysis of stochastic optimization methods in terms of their sensitivity with respect to the step size. We identify a key quantity that, for each method, describes how the performance degrades as the step size becomes too large. For convex problems, we show that this quanti…