Stochastic Gradient Optimization Techniques

Latest papers

• Difference of Convex Programming in the Wasserstein Space with Applications to MMD Optimization

  Cl\'ement Bonet, Pierre-Cyril Aubin-Frankowski, Youssef Mroueh · 29 June 2026

  Optimizing functionals over the space of probability measures is now ubiquitous in machine learning. A widely used approach is to perform the optimization directly over the Wasserstein space, but many objective functionals of practical interest are non-convex along Wasserstein geodesics, making the …

• Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

  Thomas Boudou, Batiste Le Bars, Nirupam Gupta, Aur\'elien Bellet · 29 June 2026

  Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator. While linear averaging preserves the monotonicity of gradient updates, this property is often violated when gradients are aggregated non-affinely, as in modern pipe…

• Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

  Shuang Li, Zhihui Zhu, Qiuwei Li · 29 June 2026

  We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor…

• How Width and Data Shape Generalization Scaling Laws in Quadratic Neural Networks

  Julius Girardin, Emanuele Troiani, Yizhou Xu, Vittorio Erba, Florent Krzakala, Lenka Zdeborov\'a · 29 June 2026

  Understanding how performance scales jointly with model size and data is a central problem in modern machine learning. Existing theoretical works on scaling laws typically describe generalization as a function of data or compute, often in fixed-feature or infinite-width regimes and for online SGD. H…

• Stochastic Gradient Optimization with Model-Assisted Sampling

  Jonne Pohjankukka, Jukka Heikkonen · 26 June 2026

  This work addresses the problem of variance in stochastic gradient estimation for machine learning optimization. Deep learning relies on mini-batch methods such as stochastic gradient descent, which approximate full gradients but introduce noise, creating trade-offs between convergence stability, sp…

• Sketched Linear Contrastive Learning: Approximation, Optimization, and Statistical Scaling

  Ziyan Chen, Zhongzhu Zhou, Ding-Xuan Zhou · 26 June 2026

  Scaling laws describe how learning performance varies with model size, data size, and compute. While recent theoretical work has established scaling laws for sketched linear regression, much less is understood for contrastive representation learning. In this paper, we study a sketched linear model f…

• Finding Stationary Points by Comparisons

  Helin Wang, Chenyi Zhang, Xiwen Tao, Yexin Zhang, Tongyang Li · 26 June 2026

  We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient…

• \chisao{}: A GPU-Native Parallel Optimizer for Multimodal Black-Box Functions via Convergence-Anticonvergence Oscillation

  Ira Wolfson · 26 June 2026

  Finding all modes of a multimodal black-box function is a fundamental challenge in optimization, Bayesian inference, and scientific computing. Existing approaches -- basin-hopping, CMA-ES, multistart gradient descent -- operate sequentially and cannot exploit the massive parallelism of modern GPU ha…

• Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation

  Anastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim, Gregory Cousins, Haitz S\'aez de Oc\'ariz Borde · 26 June 2026

  Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comp…

• Learning Non-Vacuous Generalization Bounds from Optimization

  Chengli Tan, Jiangshe Zhang, Junmin Liu, Yihong Gong · 25 June 2026

  One of the fundamental challenges in the deep learning community is to theoretically understand how well a deep neural network generalizes to unseen data. However, current approaches often yield generalization bounds that are either too loose to be informative of the true generalization error or onl…

• Improving Neural Network Training by Decoupling the Magnitude and Direction of Weight Vectors

  Alexander H\"agele, Alejandro Hern\'andez-Cano, Atli Kosson, Martin Jaggi · 25 June 2026

  Modern neural network training relies on optimizers such as Adam and Muon which act on each weight matrix as a single object. Yet every weight matrix carries two distinct quantities -- a \emph{magnitude} and a \emph{direction} -- and all optimizers stepping in the matrix as a whole couple their dyna…

• KANLib -- A Modular, Extensible and Fast Kolmogorov-Arnold Network Implementation

  Julian Hoever, Gregor Schiele · 24 June 2026

  Kolmogorov-Arnold Networks (KANs) have recently emerged as a promising alternative to traditional multilayer perceptrons by replacing linear weights with learnable univariate functions. Despite their theoretical advantages in interpretability and expressiveness, practical research of KANs remains di…

• Decentralized SGD with Controlled Disagreement Finds Flatter Minima

  Zesen Wang, Mikael Johansson · 24 June 2026

  Decentralized training is often regarded as inferior to centralized training because the consensus errors between workers are thought to undermine convergence and generalization. This work challenges this view by introducing decentralized SGD with Adaptive Consensus (DSGD-AC), which uses a time-depe…

• Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling

  Trenton Lau, Gary P. T. Choi · 24 June 2026

  The exact computation of the Normalized Maximum Likelihood (NML) codelength for regular non-smooth estimators (e.g., Lasso) has been historically limited by the cubic scaling walls of manifold-constrained projection and volume integration. At each step of the geometric Propose-and-Project Metropolis…

• Uniform Sampling from High-dimensional Spectral Norm Balls

  Michael R. Metel · 24 June 2026

  Motivated by an application in machine learning optimization, this paper focuses on the challenges of sampling a matrix uniformly from the unit spectral norm ball. It is proven that all singular values of sampled matrices converge to 1 almost surely as the matrix dimensions increase. This result pro…

• New Bounds for the Last Iterate of the Stochastic subGradient Method

  Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni, Andrea Paudice · 24 June 2026

  We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon $n$, we consider the standard fixed stepsizes $\eta =\Theta(1/\sqrt n)$. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniform…

• Constrained Variable Projection for Structured Problems

  Emanuele Zangrando, Sara Venturini, Francesco Rinaldi, Francesco Tudisco · 24 June 2026

  Variable projection is a classical technique for separable nonlinear least-squares problems, in which variables that enter linearly are eliminated exactly, yielding a reduced nonlinear problem. By expressing this framework as a particular instance of a broader class of bilevel optimization problems,…

• DREG: A Layer-Wise Jacobian Regularization as a General-Purpose Penalty

  Rowan Martnishn · 24 June 2026

  We present a large-scale empirical study isolating the contributions of the Derivative Regularization penalty (DREG). Across a fully-crossed factorial sweep of 960 experiments spanning 4 activations, 6 regularizers, 8 datasets, and 5 random seeds, we ask: when, where, and why does DREG work? Our res…

• Layer-wise Geometric Approximation Rates for Deep Networks

  Shijun Zhang, Zuowei Shen, Yuesheng Xu · 24 June 2026

  Depth is widely viewed as a central contributor to the success of deep neural networks, whereas standard neural network approximation theory typically provides guarantees only for the final output and leaves the role of intermediate layers largely unclear. We address this gap by developing a quantit…

• Decentralised AI Training and Inference with BlockTrain

  Peter Toth · 24 June 2026

  Frontier AI training is increasingly shaped by access to dense, centrally controlled accelerator clusters. This creates a structural advantage for hyperscalers and large centralized laboratories, and makes open or independent AI efforts depend on scarce capital, privileged infrastructure, and data-c…

• Data Augmentation: A Fourier Analysis Perspective

  Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka · 24 June 2026

  Data augmentation is a simple and model-agnostic approach for exploiting known invariances in learning problems. Given a group acting on the input space, one augments the training set with transformed copies of each sample. Because it exploits symmetries without modifying the underlying learning alg…

• Non-asymptotic estimates of the minimal risk in statistical learning

  Liming Wu (Laboratoire de Math\'ematiques Blaise Pascal, CNRS-UMR 6620, Universit\'e Clermont Auvergne), Sen Yang (IASM, Harbin Institute of Technology) · 23 June 2026

  In this paper we prove some concentration inequalities for two types of error probabilities in the Empirical Risk Principle (ERP) in statistical learning, which provide a lower bound and an upper bound for the minimal risk (in terms of the minimal empirical risk) with non-asymptotic high confidence.…

• Convergence of Gradient Descent for General Neural Network Architectures Beyond the NTK Regime

  Yuqing Wang · 23 June 2026

  Training dynamics is central to understanding neural networks, yet its theoretical analysis remains difficult even for simple architectures and becomes substantially more challenging for general modern architectures. In this paper, we propose a convergence framework for analyzing gradient descent (G…

• Clipping the Price of Adaptivity at the Tail

  Itai Kreisler, Yair Carmon, Oliver Hinder · 23 June 2026

  Adaptive stochastic convex optimization (SCO) methods face a fundamental ``price of adaptivity'' barrier: under the standard set of assumptions, they cannot efficiently adapt to large uncertainty in both the initial distance to optimality and the Lipschitz constant. We circumvent this barrier by req…

• GRAIN: Group Aggregation via Min-Norm Objective

  Nghia Bui, Jiarui Yao, Lijing Wang · 23 June 2026

  Learning instability is a long-standing problem across machine learning, but it is especially acute in the overparameterized regime that defines modern deep learning: large models fine-tuned or trained on limited data traverse flat loss landscapes with many nearly-equivalent minima, and stochastic f…