Stochastic Gradient Optimization Techniques

Latest papers

• Distributed Gradient Clustering: Convergence and the Effect of Initialization

  Aleksandar Armacki, Himkant Sharma, Dragana Bajovi\'c, Du\v{s}an Jakoveti\'c, Mrityunjoy Chakraborty, Soummya Kar · 24 March 2026

  We study the effects of center initialization on the performance of a family of distributed gradient-based clustering algorithms introduced in [1], that work over connected networks of users. In the considered scenario, each user contains a local dataset and communicates only with its immediate neig…

• Fast convergence of a Federated Expectation-Maximization Algorithm

  Zhixu Tao, Rajita Chandak, Sanjeev Kulkarni · 24 March 2026

  Data heterogeneity has been a long-standing bottleneck in studying the convergence rates of Federated Learning algorithms. In order to better understand the issue of data heterogeneity, we study the convergence rate of the Expectation-Maximization (EM) algorithm for the Federated Mixture of $K$ Line…

• RMNP: Row-Momentum Normalized Preconditioning for Scalable Matrix-Based Optimization

  Shenyang Deng, Zhuoli Ouyang, Tianyu Pang, Zihang Liu, Ruochen Jin, Shuhua Yu, Yaoqing Yang · 24 March 2026

  Preconditioned adaptive methods have gained significant attention for training deep neural networks, as they capture rich curvature information of the loss landscape . The central challenge in this field lies in balancing preconditioning effectiveness with computational efficiency of implementing th…

• Model Evolution Under Zeroth-Order Optimization: A Neural Tangent Kernel Perspective

  Chen Zhang, Yuxin Cheng, Chenchen Ding, Shuqi Wang, Jingreng Lei, Runsheng Yu, Yik-Chung WU, Ngai Wong · 24 March 2026

  Zeroth-order (ZO) optimization enables memory-efficient training of neural networks by estimating gradients via forward passes only, eliminating the need for backpropagation. However, the stochastic nature of gradient estimation significantly obscures the training dynamics, in contrast to the well-c…

• Universality of shallow and deep neural networks on non-Euclidean spaces

  Vugar Ismailov · 24 March 2026

  We study 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 reduces to multilayer feedforward networks in the Euclidean case. We focus on the universal approximation property and establish g…

• Hard labels sampled from sparse targets mislead rotation invariant algorithms

  Avrajit Ghosh, Bin Yu, Manfred Warmuth, Peter Bartlett · 24 March 2026

  One of the most common machine learning setups is logistic regression. In many classification models, including neural networks, the final prediction is obtained by applying a logistic link function to a linear score. In binary logistic regression, the feedback can be either soft labels, correspondi…

• Does This Gradient Spark Joy?

  Ian Osband · 24 March 2026

  Policy gradient computes a backward pass for every sample, even though the backward pass is expensive and most samples carry little learning value. The Delightful Policy Gradient (DG) provides a forward-pass signal of learning value: \emph{delight}, the product of advantage and surprisal (negative l…

• On the Role of Batch Size in Stochastic Conditional Gradient Methods

  Rustem Islamov, Roman Machacek, Aurelien Lucchi, Antonio Silveti-Falls, Eduard Gorbunov, Volkan Cevher · 24 March 2026

  We study the role of batch size in stochastic conditional gradient methods under a $\mu$-Kurdyka-{\L}ojasiewicz ($\mu$-KL) condition. Focusing on momentum-based stochastic conditional gradient algorithms (e.g., Scion), we derive a new analysis that explicitly captures the interaction between stepsiz…

• Optimal low-rank stochastic gradient estimation for LLM training

  Zehao Li, Tao Ren, Zishi Zhang, Xi Chen, Yijie Peng · 24 March 2026

  Large language model (LLM) training is often bottlenecked by memory constraints and stochastic gradient noise in extremely high-dimensional parameter spaces. Motivated by empirical evidence that many LLM gradient matrices are effectively low-rank during training, we present an unbiased, memory-effic…

• Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate

  Yingzhen Yang, Ping Li · 24 March 2026

  We study the problem of learning a low-degree spherical polynomial of degree $k_0 = \Theta(1) \ge 1$ defined on the unit sphere in $\RR^d$ by training an over-parameterized two-layer neural network with augmented feature in this paper. Our main result is the significantly improved sample complexity …

• CRPS-Optimal Binning for Conformal Regression

  Paolo Toccaceli · 24 March 2026

  We propose a method for non-parametric conditional distribution estimation based on partitioning covariate-sorted observations into contiguous bins and using the within-bin empirical CDF as the predictive distribution. Bin boundaries are chosen to minimise the total leave-one-out Continuous Ranked P…

• RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation

  Abolfazl Hashemi · 24 March 2026

  A celebrated method for Variational Inequalities (VIs) is Extragradient (EG), which can be viewed as a standard discrete-time integration scheme. With this view in mind, in this paper we show that EG may suffer from discretization bias when applied to non-linear vector fields, conservative or otherw…

• Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent

  Sharan Vaswani, Benjamin Dubois-Taine, Reza Babanezhad · 24 March 2026

  We aim to make stochastic gradient descent (SGD) adaptive to (i) the noise $\sigma^2$ in the stochastic gradients and (ii) problem-dependent constants. When minimizing smooth, strongly-convex functions with condition number $\kappa$, we prove that $T$ iterations of SGD with exponentially decreasing …

• Two-Time-Scale Learning Dynamics: A Population View of Neural Network Training

  Giacomo Borghi, Hyesung Im, Lorenzo Pareschi · 23 March 2026

  Population-based learning paradigms, including evolutionary strategies, Population-Based Training (PBT), and recent model-merging methods, combine fast within-model optimisation with slower population-level adaptation. Despite their empirical success, a general mathematical description of the result…

• Minimax Generalized Cross-Entropy

  Kartheek Bondugula, Santiago Mazuelas, Aritz P\'erez, Anqi Liu · 23 March 2026

  Loss functions play a central role in supervised classification. Cross-entropy (CE) is widely used, whereas the mean absolute error (MAE) loss can offer robustness but is difficult to optimize. Interpolating between the CE and MAE losses, generalized cross-entropy (GCE) has recently been introduced …

• Scalable Learning of Multivariate Distributions via Coresets

  Zeyu Ding, Katja Ickstadt, Nadja Klein, Alexander Munteanu, Simon Omlor · 23 March 2026

  Efficient and scalable non-parametric or semi-parametric regression analysis and density estimation are of crucial importance to the fields of statistics and machine learning. However, available methods are limited in their ability to handle large-scale data. We address this issue by developing a no…

• Global Convergence of Multiplicative Updates for the Matrix Mechanism: A Collaborative Proof with Gemini 3

  Keith Rush · 23 March 2026

  We analyze a fixed-point iteration $v \leftarrow \phi(v)$ arising in the optimization of a regularized nuclear norm objective involving the Hadamard product structure, posed in~\cite{denisov} in the context of an optimization problem over the space of algorithms in private machine learning. We prove…

• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition

  Calvin Ang, Sungyoon Kim, Mert Pilanci · 23 March 2026

  We study entrywise scalar quantization of two matrices prior to multiplication. Given $A\in R^{m\times k}$ and $B\in R^{k\times n}$, we quantize entries of $A$ and $B$ independently using scalar quantizers with $K_X$ and $K_Y$ levels per entry, and form $\widehat C=\widehat A\,\widehat B$. The objec…

• Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis

  Siddharth Chandak, Anuj Yadav, Ayfer Ozgur, Nicholas Bambos · 23 March 2026

  Stochastic approximation (SA) is a fundamental iterative framework with broad applications in reinforcement learning and optimization. Classical analyses typically rely on martingale difference or Markov noise with bounded second moments, but many practical settings, including finance and communicat…

• Uniform a priori bounds and error analysis for the Adam stochastic gradient descent optimization method

  Steffen Dereich, Thang Do, Arnulf Jentzen · 20 March 2026

  The adaptive moment estimation (Adam) optimizer proposed by Kingma & Ba (2014) is presumably the most popular stochastic gradient descent (SGD) optimization method for the training of deep neural networks (DNNs) in artificial intelligence (AI) systems. Despite its groundbreaking success in the train…

• ResNets of All Shapes and Sizes: Convergence of Training Dynamics in the Large-scale Limit

  Louis-Pierre Chaintron, L\'ena\"ic Chizat, Javier Maas · 20 March 2026

  We establish convergence of the training dynamics of residual neural networks (ResNets) to their joint infinite depth L, hidden width M, and embedding dimension D limit. Specifically, we consider ResNets with two-layer perceptron blocks in the maximal local feature update (MLU) regime and prove that…

• Computational and Statistical Hardness of Calibration Distance

  Mingda Qiao · 20 March 2026

  The distance from calibration, introduced by B{\l}asiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for probabilistic predictors. We study the fundamental problems of computing and estimating this quantity, given either an exact description of …

• Learning Decision-Sufficient Representations for Linear Optimization

  Yuhan Ye, Saurabh Amin, Asuman Ozdauglar · 20 March 2026

  We study how to construct compressed datasets that suffice to recover optimal decisions in linear programs with an unknown cost vector $c$ lying in a prior set $\mathcal{C}$. Recent work by Bennouna et al. provides an exact geometric characterization of sufficient decision datasets (SDDs) via an int…

• Mirror Descent on Riemannian Manifolds

  Jiaxin Jiang, Lei Shi, Jiyuan Tan · 19 March 2026

  Mirror Descent (MD) is a scalable first-order method widely used in large-scale optimization, with applications in image processing, policy optimization, and neural network training. This paper generalizes MD to optimization on Riemannian manifolds. In particular, we develop a Riemannian Mirror Desc…

• Variational Kernel Design for Internal Noise: Gaussian Chaos Noise, Representation Compatibility, and Reliable Deep Learning

  Ziran Liu · 19 March 2026

  Internal noise in deep networks is usually inherited from heuristics such as dropout, hard masking, or additive perturbation. We ask two questions: what correlation geometry should internal noise have, and is the implemented perturbation compatible with the representations it acts on? We answer thes…