Stochastic Gradient Optimization Techniques

Derniers papiers

• Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm

  Yuman Wu, Xiaochuan Gong, Jie Hao, Mingrui Liu · 3 mars 2026

  Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-{\…

• 3BASiL: An Algorithmic Framework for Sparse plus Low-Rank Compression of LLMs

  Mehdi Makni, Xiang Meng, Rahul Mazumder · 3 mars 2026

  Sparse plus Low-Rank $(\mathbf{S} + \mathbf{LR})$ decomposition of Large Language Models (LLMs) has emerged as a promising direction in model compression, aiming to decompose pre-trained model weights into a sum of sparse and low-rank matrices $(\mathbf{W} \approx \mathbf{S} + \mathbf{LR})$. Despite…

• On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspective

  Guy Smorodinsky, Sveta Gimpleson, Itay Safran · 3 mars 2026

  We study the convergence dynamics of Gradient Descent (GD) in a minimal binary classification setting, consisting of a two-neuron ReLU network and two training instances. We prove that even under these strong simplifying assumptions, while GD successfully converges to an optimal robustness margin, e…

• Leave-One-Out Prediction for General Hypothesis Classes

  Jian Qian, Jiachen Xu · 3 mars 2026

  Leave-one-out (LOO) prediction provides a principled, data-dependent measure of generalization, yet guarantees in fully transductive settings remain poorly understood beyond specialized models. We introduce Median of Level-Set Aggregation (MLSA), a general aggregation procedure based on empirical-ri…

• Training Dynamics of Softmax Self-Attention: Fast Global Convergence via Preconditioning

  Gautam Goel, Mahdi Soltanolkotabi, Peter Bartlett · 3 mars 2026

  We study the training dynamics of gradient descent in a softmax self-attention layer trained to perform linear regression and show that a simple first-order optimization algorithm can converge to the globally optimal self-attention parameters at a geometric rate. Our analysis proceeds in two steps. …

• Co-optimization for Adaptive Conformal Prediction

  Xiaoyi Su, Zhixin Zhou, Rui Luo · 3 mars 2026

  Conformal prediction (CP) provides finite-sample, distribution-free marginal coverage, but standard conformal regression intervals can be inefficient under heteroscedasticity and skewness. In particular, popular constructions such as conformalized quantile regression (CQR) often inherit a fixed noti…

• Maximizing the Spectral Energy Gain in Sub-1-Bit LLMs via Latent Geometry Alignment

  Banseok Lee, Youngmin Kim · 3 mars 2026

  We identify the Spectral Energy Gain in extreme model compression, where low-rank binary approximations outperform tiny-rank floating-point baselines for heavy-tailed spectra. However, prior attempts fail to realize this potential, trailing state-of-the-art 1-bit methods. We attribute this degradati…

• DynaMoE: Dynamic Token-Level Expert Activation with Layer-Wise Adaptive Capacity for Mixture-of-Experts Neural Networks

  G\"okdeniz G\"ulmez · 3 mars 2026

  Mixture-of-Experts (MoE) architectures have emerged as a powerful paradigm for scaling neural networks while maintaining computational efficiency. However, standard MoE implementations rely on two rigid design assumptions: (1) fixed Top-K routing where exactly K experts are activated per token, and …

• Riemannian Dueling Optimization

  Yuxuan Ren, Abhishek Roy, Shiqian Ma · 3 mars 2026

  Dueling optimization considers optimizing an objective with access to only a comparison oracle of the objective function. It finds important applications in emerging fields such as recommendation systems and robotics. Existing works on dueling optimization mainly focused on unconstrained problems in…

• Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operators

  Mike Nguyen, Nicole M\"ucke · 3 mars 2026

  In this work, we investigate the generalization properties of random feature methods. Our analysis extends prior results for Tikhonov regularization to a broad class of spectral regularization techniques and further generalizes the setting to operator-valued kernels. This unified framework enables a…

• Adam Converges Without Any Modification On Update Rules

  Yushun Zhang, Bingran Li, Congliang Chen, Zhi-Quan Luo, Ruoyu Sun · 3 mars 2026

  Adam is the default algorithm for training neural networks, including large language models (LLMs). However, \citet{reddi2019convergence} provided an example that Adam diverges, raising concerns for its deployment in AI model training. We identify a key mismatch between the divergence example and pr…

• Grokking as a Phase Transition between Competing Basins: a Singular Learning Theory Approach

  Ben Cullen, Sergio Estan-Ruiz, Riya Danait, Jiayi Li · 3 mars 2026

  Grokking, the abrupt transition from memorization to generalisation after extended training, suggests the presence of competing solution basins with distinct statistical properties. We study this phenomenon through the lens of Singular Learning Theory (SLT), a Bayesian framework that characterizes t…

• Never Saddle for Reparameterized Steepest Descent as Mirror Flow

  Tom Jacobs, Chao Zhou, Rebekka Burkholz · 3 mars 2026

  How does the choice of optimization algorithm shape a model's ability to learn features? To address this question for steepest descent methods --including sign descent, which is closely related to Adam --we introduce steepest mirror flows as a unifying theoretical framework. This framework reveals h…

• On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation

  Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames · 3 mars 2026

  This work establishes a rigorous connection between stability properties of discrete-time algorithms (DTAs) and corresponding continuous-time dynamical systems derived through $ O(s^r) $-resolution ordinary differential equations (ODEs). We show that for discrete- and continuous-time dynamical syste…

• Accelerating Single-Pass SGD for Generalized Linear Prediction

  Qian Chen, Shihong Ding, Cong Fang · 3 mars 2026

  We study generalized linear prediction under a streaming setting, where each iteration uses only one fresh data point for a gradient-level update. While momentum is well-established in deterministic optimization, a fundamental open question is whether it can accelerate such single-pass non-quadratic…

• Curvature-Weighted Capacity Allocation: A Minimum Description Length Framework for Layer-Adaptive Large Language Model Optimization

  Theophilus Amaefuna, Hitesh Vaidya, Anshuman Chhabra, Ankur Mali · 3 mars 2026

  Layer-wise capacity in large language models is highly non-uniform: some layers contribute disproportionately to loss reduction while others are near-redundant. Existing methods for exploiting this non-uniformity, such as influence-function-based layer scoring, produce sensitivity estimates but offe…

• Scaling Laws of SignSGD in Linear Regression: When Does It Outperform SGD?

  Jihwan Kim, Dogyoon Song, Chulhee Yun · 3 mars 2026

  We study scaling laws of signSGD under a power-law random features (PLRF) model that accounts for both feature and target decay. We analyze the population risk of a linear model trained with one-pass signSGD on Gaussian-sketched features. We express the risk as a function of model size, training ste…

• GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs

  Jiachang Liu, Andrea Lodi, Soroosh Shafiee · 3 mars 2026

  We investigate the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through a cardinality constraint. While Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations, existing methods for solving these relaxations a…

• A short tour of operator learning theory: Convergence rates, statistical limits, and open questions

  Simone Brugiapaglia, Nicola Rares Franco, Nicholas H. Nelsen · 3 mars 2026

  This paper surveys recent developments at the intersection of operator learning, statistical learning theory, and approximation theory. First, it reviews error bounds for empirical risk minimization with a focus on holomorphic operators and neural network approximations. Next, it illustrates fundame…

• Gradient is All You Need? How Consensus-Based Optimization can be Interpreted as a Stochastic Relaxation of Gradient Descent

  Konstantin Riedl, Timo Klock, Carina Geldhauser, Massimo Fornasier · 2 mars 2026

  In this paper, we provide a novel analytical perspective on the theoretical understanding of gradient-based learning algorithms by interpreting consensus-based optimization (CBO), a recently proposed multi-particle derivative-free optimization method, as a stochastic relaxation of gradient descent. …

• Spiky Rank and Its Applications to Rigidity and Circuits

  Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman · 2 mars 2026

  We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the mini…

• Optimizer-Induced Low-Dimensional Drift and Transverse Dynamics in Transformer Training

  Yongzhong Xu · 2 mars 2026

  We study the geometry of training trajectories in small transformer models and find that parameter updates organize into a dominant drift direction with transverse residual dynamics. Using uncentered, row-normalized trajectory PCA, we show that a single direction captures a large fraction of cumulat…

• Taming Momentum: Rethinking Optimizer States Through Low-Rank Approximation

  Zhengbo Wang, Jian Liang, Ran He, Zilei Wang, Tieniu Tan · 2 mars 2026

  Modern optimizers like Adam and Muon are central to training large language models, but their reliance on first- and second-order momenta introduces significant memory overhead, which constrains scalability and computational efficiency. In this work, we reframe the exponential moving average (EMA) u…

• Apprenticeship learning with prior beliefs using inverse optimization

  Mauricio Junca, Esteban Leiva · 2 mars 2026

  The relationship between inverse reinforcement learning (IRL) and inverse optimization (IO) for Markov decision processes (MDPs) has been relatively underexplored in the literature, despite addressing the same problem. In this work, we revisit the relationship between the IO framework for MDPs, IRL,…

• Universality of Shallow and Deep Neural Networks on Non-Euclidean Spaces

  Vugar Ismailov · 2 mars 2026

  We develop a framework for shallow and deep neural networks whose inputs range over a general topological space. The model is built from a prescribed family of continuous feature maps and a fixed scalar activation function, and it reduces to multilayer feedforward networks in the Euclidean case. We …