Stochastic Gradient Optimization Techniques

Derniers papiers

• Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networks

  Ouns El Harzli, Yoonsoo Nam, Ilja Kuzborskij, Bernardo Cuenca Grau, Ard A. Louis · 17 février 2026

  Algorithmic stability is a classical framework for analyzing the generalization error of learning algorithms. It predicts that an algorithm has small generalization error if it is insensitive to small perturbations in the training set such as the removal or replacement of a training point. While sta…

• Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise

  Yuchen Fang, James Demmel, Javad Lavaei · 17 février 2026

  We develop a worst-case complexity theory for stochastically preconditioned stochastic gradient descent (SPSGD) and its accelerated variants under heavy-tailed noise, a setting that encompasses widely used adaptive methods such as Adam, RMSProp, and Shampoo. We assume the stochastic gradient noise h…

• Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Sampling

  Valery Parfenov, Grigoriy Evseev, Andrey Veprikov, Nikolay Bushkov, Stanislav Moiseev, Aleksandr Beznosikov · 17 février 2026

  Fine-tuning large pretrained language models (LLMs) is a cornerstone of modern NLP, yet its growing memory demands (driven by backpropagation and large optimizer States) limit deployment in resource-constrained settings. Zero-order (ZO) methods bypass backpropagation by estimating directional deriva…

• On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling

  Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma · 17 février 2026

  Correlation Clustering (CC) is a fundamental unsupervised learning primitive whose strongest LP-based approximation guarantees require $\Theta(n^3)$ triangle inequality constraints and are prohibitive at scale. We initiate the study of \emph{sparsification--approximation trade-offs} for CC, asking h…

• LRD-MPC: Efficient MPC Inference through Low-rank Decomposition

  Tingting Tang, Yongqin Wang, Murali Annavaram · 17 février 2026

  Secure Multi-party Computation (MPC) enables untrusted parties to jointly compute a function without revealing their inputs. Its application to machine learning (ML) has gained significant attention, particularly for secure inference services deployed across multiple cloud virtual machines (VMs), wh…

• Quantifying Normality: Convergence Rate to Gaussian Limit for Stochastic Approximation and Unadjusted OU Algorithm

  Shaan Ul Haque, Zedong Wang, Zixuan Zhang, Siva Theja Maguluri · 17 février 2026

  Stochastic approximation (SA) is a method for finding the root of an operator perturbed by noise. There is a rich literature establishing the asymptotic normality of rescaled SA iterates under fairly mild conditions. However, these asymptotic results do not quantify the accuracy of the Gaussian appr…

• Fast Compute for ML Optimization

  Nick Polson, Vadim Sokolov · 17 février 2026

  We study optimization for losses that admit a variance-mean scale-mixture representation. Under this representation, each EM iteration is a weighted least squares update in which latent variables determine observation and parameter weights; these play roles analogous to Adam's second-moment scaling …

• Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking

  Yan Huang, Jinming Xu, Li Chai, Jiming Chen, Karl H. Johansson · 17 février 2026

  This paper addresses distributed stochastic optimization problems under non-i.i.d. data, focusing on the inherent trade-offs between communication and computational efficiency. To this end, we propose FlexGT, a flexible snapshot gradient tracking method that enables tunable numbers of local updates …

• Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds

  Zedong Wang, Yuyang Wang, Ijay Narang, Felix Wang, Yuzhou Wang, Siva Theja Maguluri · 17 février 2026

  Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency. For a fixed stepsize, the iterates typically admit a stationary distribution that is rarely tractable. Prior work shows that as the stepsize $\alpha \downarrow 0$, the centered-and-scaled steady …

• Neural Optimal Transport in Hilbert Spaces: Characterizing Spurious Solutions and Gaussian Smoothing

  Jae-Hwan Choi, Jiwoo Yoon, Dohyun Kwon, Jaewoong Choi · 17 février 2026

  We study Neural Optimal Transport in infinite-dimensional Hilbert spaces. In non-regular settings, Semi-dual Neural OT often generates spurious solutions that fail to accurately capture target distributions. We analytically characterize this spurious solution problem using the framework of regular m…

• An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale

  Adri\'an Javaloy, Antonio Vergari · 17 février 2026

  Orthogonality constraints are ubiquitous in robust and probabilistic machine learning. Unfortunately, current optimizers are computationally expensive and do not scale to problems with hundreds or thousands of constraints. One notable exception is the Landing algorithm (Ablin et al., 2024) which, ho…

• Better Hessians Matter: Studying the Impact of Curvature Approximations in Influence Functions

  Steve Hong, Runa Eschenhagen, Bruno Mlodozeniec, Richard Turner · 17 février 2026

  Influence functions offer a principled way to trace model predictions back to training data, but their use in deep learning is hampered by the need to invert a large, ill-conditioned Hessian matrix. Approximations such as Generalised Gauss-Newton (GGN) and Kronecker-Factored Approximate Curvature (K…

• On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials

  Rotem Mulayoff, Sebastian U. Stich · 17 février 2026

  The dynamical stability of the iterates during training plays a key role in determining the minima obtained by optimization algorithms. For example, stable solutions of gradient descent (GD) correspond to flat minima, which have been associated with favorable features. While prior work often relies …

• Unbiased Approximate Vector-Jacobian Products for Efficient Backpropagation

  Killian Bakong (DI-ENS), Laurent Massouli\'e (Inria, ARGO, CMAP), Edouard Oyallon (MLIA), Kevin Scaman · 17 février 2026

  In this work we introduce methods to reduce the computational and memory costs of training deep neural networks. Our approach consists in replacing exact vector-jacobian products by randomized, unbiased approximations thereof during backpropagation. We provide a theoretical analysis of the trade-off…

• Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities

  Pavel Dvurechensky, Andrea Ebner, Johannes Carl Schnebel, Shimrit Shtern, Mathias Staudigl · 17 février 2026

  We are concerned with optimization in a broad sense through the lens of solving variational inequalities (VIs) -- a class of problems that are so general that they cover as particular cases minimization of functions, saddle-point (minimax) problems, Nash equilibrium problems, and many others. The ke…

• High-accuracy log-concave sampling with stochastic queries

  Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin · 17 février 2026

  We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/\delta)$, where $\delta$ is the desired target accuracy -- are achievable using stochastic gradients with subexponential tails. Notably, this exhibits a sep…

• Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs

  Pedram Bakhtiarifard, Tong Chen, Jonathan Wensh{\o}j, Erik B Dam, Raghavendra Selvan · 17 février 2026

  Large-scale deep learning models are well-suited for compression. Methods like pruning, quantization, and knowledge distillation have been used to achieve massive reductions in the number of model parameters, with marginal performance drops across a variety of architectures and tasks. This raises th…

• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition

  ZhiMing Li, JiaHe Feng · 17 février 2026

  We study matrix-free eigendecomposition under a matrix-vector product (MVP) oracle, where each step observes a covariance operator $C_k = C_{sig} + \sigma_k^2 I + E_k$. Standard stochastic approximation methods either use fixed steps that couple stability to $\|C_k\|_2$, or adapt steps in ways that …

• Block-Sample MAC-Bayes Generalization Bounds

  Matthias Frey, Jingge Zhu, Michael C. Gastpar · 16 février 2026

  We present a family of novel block-sample MAC-Bayes bounds (mean approximately correct). While PAC-Bayes bounds (probably approximately correct) typically give bounds for the generalization error that hold with high probability, MAC-Bayes bounds have a similar form but bound the expected generalizat…

• Leverage-Weighted Conformal Prediction

  Shreyas Fadnavis · 16 février 2026

  Split conformal prediction provides distribution-free prediction intervals with finite-sample marginal coverage, but produces constant-width intervals that overcover in low-variance regions and undercover in high-variance regions. Existing adaptive methods require training auxiliary models. We propo…

• Learning on a Razor's Edge: Identifiability and Singularity of Polynomial Neural Networks

  Vahid Shahverdi, Giovanni Luca Marchetti, Kathl\'en Kohn · 16 février 2026

  We study function spaces parametrized by neural networks, referred to as neuromanifolds. Specifically, we focus on deep Multi-Layer Perceptrons (MLPs) and Convolutional Neural Networks (CNNs) with an activation function that is a sufficiently generic polynomial. First, we address the identifiability…

• Stabilizing Native Low-Rank LLM Pretraining

  Paul Janson, Edouard Oyallon, Eugene Belilovsky · 16 février 2026

  Foundation models have achieved remarkable success, yet their growing parameter counts pose significant computational and memory challenges. Low-rank factorization offers a promising route to reduce training and inference costs, but the community lacks a stable recipe for training models from scratc…

• Improved Regret Guarantees for Online Mirror Descent using a Portfolio of Mirror Maps

  Swati Gupta, Jai Moondra, Mohit Singh · 16 février 2026

  OMD and its variants give a flexible framework for OCO where the performance depends crucially on the choice of the mirror map. While the geometries underlying OPGD and OEG, both special cases of OMD, are well understood, it remains a challenging open question on how to construct an optimal mirror m…

• Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

  Michael Crawshaw, Mingrui Liu · 16 février 2026

  We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data. With a budget of $T$ iterations, it was recently shown that an accelerated $1/T^2$ rate is possible by choosing a large step size $\eta = …

• AdaGrad-Diff: A New Version of the Adaptive Gradient Algorithm

  Matia Bojovic, Saverio Salzo, Massimiliano Pontil · 16 février 2026

  Vanilla gradient methods are often highly sensitive to the choice of stepsize, which typically requires manual tuning. Adaptive methods alleviate this issue and have therefore become widely used. Among them, AdaGrad has been particularly influential. In this paper, we propose an AdaGrad-style adapti…