Stochastic Gradient Optimization Techniques

Últimos artículos

• The Implicit Bias of Depth: From Neural Collapse to Softmax Codes

  Connall Garrod, Jonathan P. Keating, Christos Thrampoulidis · 25 de mayo de 2026

  Neural collapse (NC) describes the structured geometry that emerges in the features and weights of trained classifiers. Recent theory suggests NC can be suboptimal in deep architectures, attributing this to an explicit low-rank bias from L2 regularization. We study the deep unconstrained feature mod…

• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes

  Ivan Lau, Jonathan Scarlett · 25 de mayo de 2026

  In this paper, we study the problem of mean estimation under 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is $…

• Optimal Dimension-Free Sampling for Regularized Classification

  Meysam Alishahi, Alexander Munteanu, Simon Omlor, Jeff M. Phillips · 25 de mayo de 2026

  We prove optimal sampling bounds achieving $(1\pm\varepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and p…

• Automated Random Embedding for Practical Bayesian Optimization with Unknown Effective Dimension

  Hong Qian, Xiang Shu, Xiang Xia, Xuhui Liu, Yangde Fu, Bei Liang, Huibin Wang, Liang Dou · 25 de mayo de 2026

  Bayesian optimization is widely employed for optimizing complex black-box functions but struggles with the curse of dimensionality. Random embedding, as a dimension reduction strategy, simplifies tasks that possess the effective dimension by optimizing within a low-dimensional subspace. However, det…

• RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs

  Yi-Shuai Niu · 25 de mayo de 2026

  We study nonsmooth difference-of-convex programs whose subtracted convex term is a finite maximum of smooth convex functions. In this setting, standard DCA iterations may converge to critical points that are not directionally stationary, whereas exact active-vertex screening can be expensive when ac…

• Anytime Training with Schedule-Free Spectral Optimization

  Anuj Apte, Pranav Deshpande, Niraj Kumar, Shouvanik Chakrabarti, Junhyung Lyle Kim · 25 de mayo de 2026

  Standard neural network training relies on learning-rate schedules tied to a fixed horizon, leading to strong path dependence and costly re-tuning as data availability changes. Schedule-Free (SF) methods address this by removing explicit schedules, yet SF-AdamW, the current state-of-the-art anytime …

• Asymmetric Scaling Laws from Sparse Features

  John Sous, Michael Winer · 25 de mayo de 2026

  We introduce a model for neural scaling laws under sparse activations. In the model, test loss is often dominated by rare coordinates that are never observed in the training input. This mechanism induces a novel bottleneck absent from dense models. We derive the asymptotic population loss in both th…

• Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models

  Hongyi Li, Jun Xu, Hong Yan · 25 de mayo de 2026

  Learning high-quality oblique decision trees remains a significant challenge due to the discrete and non-convex nature of split optimization. We present the Hinge Regression Tree (HRT) framework, which reframes each oblique split as a nonlinear least-squares problem over two linear predictors whose …

• Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

  Yuhan Ye · 25 de mayo de 2026

  We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral …

• Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit

  Konstantin Riedl, Konstantinos Spiliopoulos, Justin Sirignano · 22 de mayo de 2026

  A convergence analysis is developed for the regularized Newton method for training neural networks (NNs) in the overparameterized limit. As the number of hidden units tends to infinity, the NN training dynamics converge in probability to the solution of a deterministic limit equation involving a ``N…

• Large-Step Training Dynamics of a Two-Factor Linear Transformer Model

  Krishnakumar Balasubramanian · 21 de mayo de 2026

  Gradient-flow analyses show that simplified linear transformers can learn the in-context linear-regression algorithm, but they do not explain the finite-step behavior of gradient descent at large learning rates. Motivated by empirical work on high-learning-rate transformer instabilities and by the c…

• Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit

  Konstantin Riedl, Konstantinos Spiliopoulos, Justin Sirignano · 21 de mayo de 2026

  A convergence analysis is developed for the regularized Newton method for training neural networks (NNs) in the overparameterized limit. As the number of hidden units tends to infinity, the NN training dynamics converge in probability to the solution of a deterministic limit equation involving a ``N…

• A Rigorous, Tractable Measure of Model Complexity

  Oskar Allerbo, Thomas B. Sch\"on · 21 de mayo de 2026

  An accurate assessment of a model's complexity is crucial for topics such as interpretation, generalization, and model selection. However, most existing complexity measures either rely on heuristic assumptions or are computationally prohibitive. In this paper, we present a mathematically rigorous ye…

• Approximation Theory for Neural Networks: Old and New

  Soumendu Sundar Mukherjee, Himasish Talukdar · 21 de mayo de 2026

  Universal approximation theorems provide a mathematical explanation for the expressive power of neural networks. They assert that, under mild conditions on the activation function, feedforward neural networks are dense in broad function classes, such as continuous functions on compact subsets of $\m…

• Semiparametric Efficient Bilevel Gradient Estimation

  Fares El Khoury, Houssam Zenati, Nathan Kallus, Michael Arbel, Aur\'elien Bibaut · 21 de mayo de 2026

  Functional bilevel methods estimate a lower-level function and plug it into a hypergradient, but this plug-in gradient can retain first-order bias when the lower-level problem is learned nonparametrically. To remove this bias, we develop a semiparametric debiasing theory for population bilevel gradi…

• HORST: Composing Optimizer Geometries for Sparse Transformer Training

  Tom Jacobs, Rohan Jain, Rebekka Burkholz · 21 de mayo de 2026

  Sparsifying transformers remains a fundamental challenge, as standard optimizers fail to simultaneously encourage sparsity and maintain training stability. Effective adaptive optimizers exhibit an implicit $L_{\infty}$ bias favoring stability, yet, sparsity requires an $L_1$ bias. To integrate spars…

• SMoA: Spectrum Modulation Adapter for Parameter-Efficient Fine-Tuning

  Yongkang Liu, Xing Li, Mengjie Zhao, Shanru Zhang, Zijing Wang, Qian Li, Shi Feng, Feiliang Ren, Daling Wang, Hinrich Sch\"utze · 21 de mayo de 2026

  As the number of model parameters increases, parameter-efficient fine-tuning (PEFT) has become the go-to choice for tailoring pre-trained large language models. Low-rank Adaptation (LoRA) uses a low-rank update method to simulate full parameter fine-tuning, which is widely used to reduce resource re…

• LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging

  Yassine Maziane, Ammar Mahran, Artavazd Maranjyan, Peter Richt\'arik · 21 de mayo de 2026

  Communication is a major bottleneck in distributed learning, especially in large-scale settings and in federated learning environments with slow links. Three standard ways to reduce this cost are communication compression, local training, and communication-computation overlap. Methods that combine t…

• A Sharper Picture of Generalization in Transformers

  Paul Lintilhac, Sair Shaikh · 21 de mayo de 2026

  We study transformers' generalization behavior on boolean domains from the perspective of the Fourier Spectra of their target functions. In contrast to prior work (Edelman et al., 2022; Trauger and Tewari, 2024), which derived generalization bounds from Rademacher complexity, we investigate the feas…

• Correcting Stochastic Update Bias in Preconditioned Language Model Optimizers

  Nikhil Nayak, Julia White, Urchade Zaratiana, Kelton Zhang, Henrijs Princis, Dhruv Atreja, Henry Fawcett, Matthew Thomas, George Hurn-Maloney, Ash Lewis · 21 de mayo de 2026

  Preconditioned optimizers are central to language model training, but their stochastic update rules are usually treated as direct approximations to population preconditioned descent. We show that this view misses two finite-sample biases. First, the gradient and preconditioner are typically estimate…

• A Typed Tensor Language for Federated Learning

  Theofilos Mailis, Kalliopi-Christina Despotidou, Konstantinos Filippopolitis, Yannis Foufoulas, Thanasis-Michail Karampatsis, Andreas Ktenidis, Evdokia Mailli, Theodore Papamarkou, Yannis Ioannidis · 21 de mayo de 2026

  Federated learning and analytics are often described as collections of separate protocols, even when they share the same mathematical form: client-local tensor computation, mergeable aggregation into shared state, and shared-only post-processing. We introduce a typed tensor language that formalizes …

• Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

  Shubhada Agrawal, Siva Theja Maguluri, Martin Zubeldia · 21 de mayo de 2026

  We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian component plus a Martingale-difference component. When the Martingale-difference noise is bounded, we show that the tail o…

• Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

  Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold, Sergey Samsonov · 20 de mayo de 2026

  In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated Gaussian approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms, quantifying the effects …

• When Does Model Collapse Occur in Structured Interactive Learning?

  Yuchen Wu, Kangjie Zhou, Weijie Su · 20 de mayo de 2026

  The proliferation of generative artificial intelligence has given rise to an interactive learning environment, where model parameters are continuously updated using not only data generated by natural processes, but also synthetic outputs produced by other models. This paradigm introduces two major c…

• Adynamical systems view of training generativemodels and the memorization phenomenon

  Siva Athreya, Chiranjib Bhattacharya, Vivek S. Borkar · 20 de mayo de 2026

  Using recent works of one of the authors (VSB) on collapse in generative models and two time scale dynamics in stochastic gradient descent in high dimensions, we give a system theoretic explanation of the memorization phenomenon in generative models. This relies purely on the dynamic aspects of the …