Stochastic Gradient Optimization Techniques

Neueste Paper

• Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks

  Yunwen Lei, Yufeng Xie · 2. April 2026

  Overparameterized neural networks often show a benign overfitting property in the sense of achieving excellent generalization behavior despite the number of parameters exceeding the number of training examples. A promising direction to explain benign overfitting is to relate generalization to the no…

• Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization

  Lam M. Nguyen, Dzung T. Phan, Jayant Kalagnanam · 2. April 2026

  Shuffling strategies for stochastic gradient descent (SGD), including incremental gradient, shuffle-once, and random reshuffling, are supported by rigorous convergence analyses for arbitrary within-epoch permutations. In particular, random reshuffling is known to improve optimization constants relat…

• Breaking Data Symmetry is Needed For Generalization in Feature Learning Kernels

  Marcel Tom\`as Bernal, Neil Rohit Mallinar, Mikhail Belkin · 2. April 2026

  Grokking occurs when a model achieves high training accuracy but generalization to unseen test points happens long after that. This phenomenon was initially observed on a class of algebraic problems, such as learning modular arithmetic (Power et al., 2022). We study grokking on algebraic tasks in a …

• Beyond Softmax and Entropy: Convergence Rates of Policy Gradients with f-SoftArgmax Parameterization & Coupled Regularization

  Safwan Labbi, Daniil Tiapkin, Paul Mangold, Eric Moulines · 2. April 2026

  Policy gradient methods are known to be highly sensitive to the choice of policy parameterization. In particular, the widely used softmax parameterization can induce ill-conditioned optimization landscapes and lead to exponentially slow convergence. Although this can be mitigated by preconditioning,…

• Empirical Likelihood for Nonsmooth Functionals

  Hongseok Namkoong · 31. März 2026

  Empirical likelihood is an attractive inferential framework that respects natural parameter boundaries, but existing approaches typically require smoothness of the functional and miscalibrate substantially when these assumptions are violated. For the optimal-value functional central to policy evalua…

• High dimensional theory of two-phase optimizers

  Atish Agarwala · 31. März 2026

  The trend towards larger training setups has brought a renewed interest in partially asynchronous two-phase optimizers which optimize locally and then synchronize across workers. Additionally, recent work suggests that the one-worker version of one of these algorithms, DiLoCo, shows promising result…

• Expectation Error Bounds for Transfer Learning in Linear Regression and Linear Neural Networks

  Meitong Liu, Christopher Jung, Rui Li, Xue Feng, Han Zhao · 31. März 2026

  In transfer learning, the learner leverages auxiliary data to improve generalization on a main task. However, the precise theoretical understanding of when and how auxiliary data help remains incomplete. We provide new insights on this issue in two canonical linear settings: ordinary least squares r…

• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction

  Alexander Tyurin · 31. März 2026

  We consider centralized distributed optimization in the classical federated learning setup, where $n$ workers jointly find an $\varepsilon$-stationary point of an $L$-smooth, $d$-dimensional nonconvex function $f$, having access only to unbiased stochastic gradients with variance $\sigma^2$. Each wo…

• FI-KAN: Fractal Interpolation Kolmogorov-Arnold Networks

  Gnankan Landry Regis N'guessan · 31. März 2026

  Kolmogorov-Arnold Networks (KAN) employ B-spline bases on a fixed grid, providing no intrinsic multi-scale decomposition for non-smooth function approximation. We introduce Fractal Interpolation KAN (FI-KAN), which incorporates learnable fractal interpolation function (FIF) bases from iterated funct…

• Universal Approximation Constraints of Narrow ResNets: The Tunnel Effect

  Christian Kuehn, Sara-Viola Kuntz, Tobias W\"ohrer · 31. März 2026

  We analyze the universal approximation constraints of narrow Residual Neural Networks (ResNets) both theoretically and numerically. For deep neural networks without input space augmentation, a central constraint is the inability to represent critical points of the input-output map. We prove that thi…

• On the Loss Landscape Geometry of Regularized Deep Matrix Factorization: Uniqueness and Sharpness

  Anil Kamber, Rahul Parhi · 31. März 2026

  Weight decay is ubiquitous in training deep neural network architectures. Its empirical success is often attributed to capacity control; nonetheless, our theoretical understanding of its effect on the loss landscape and the set of minimizers remains limited. In this paper, we show that $\ell^2$-regu…

• The Geometric Cost of Normalization: Affine Bounds on the Bayesian Complexity of Neural Networks

  Sungbae Chun · 31. März 2026

  LayerNorm and RMSNorm impose fundamentally different geometric constraints on their outputs - and this difference has a precise, quantifiable consequence for model complexity. We prove that LayerNorm's mean-centering step, by confining data to a linear hyperplane (through the origin), reduces the Lo…

• Taming the Instability: A Robust Second-Order Optimizer for Federated Learning over Non-IID Data

  Yuanqiao Zhang, Tiantian He, Yuan Gao, Yixin Wang, Yew-Soon Ong, Maoguo Gong, A. K. Qin, Hui Li · 31. März 2026

  In this paper, we present Federated Robust Curvature Optimization (FedRCO), a novel second-order optimization framework designed to improve convergence speed and reduce communication cost in Federated Learning systems under statistical heterogeneity. Existing second-order optimization methods are of…

• Is Supervised Learning Really That Different from Unsupervised?

  Oskar Allerbo, Thomas B. Sch\"on · 30. März 2026

  We demonstrate how supervised learning can be decomposed into a two-stage procedure, where (1) all model parameters are selected in an unsupervised manner, and (2) the outputs y are added to the model, without changing the parameter values. This is achieved by a new model selection criterion that - …

• Kernel Density Machines

  Andrea Della Vecchia, Damir Filipovic, Paul Schneider · 27. März 2026

  We introduce kernel density machines (KDM), an agnostic kernel-based framework for learning the Radon-Nikodym derivative (density) between probability measures under minimal assumptions. KDM applies to general measurable spaces and avoids the structural requirements common in classical nonparametric…

• A Systematic Empirical Study of Grokking: Depth, Architecture, Activation, and Regularization

  Shalima Binta Manir, Anamika Paul Rupa · 27. März 2026

  Grokking the delayed transition from memorization to generalization in neural networks remains poorly understood, in part because prior empirical studies confound the roles of architecture, optimization, and regularization. We present a controlled study that systematically disentangles these factors…

• Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming

  Ruobing Wang, Xin Li, Yujie Fang, Mingzhong Wang · 26. März 2026

  Predict-and-search (PaS) methods have shown promise for accelerating mixed-integer linear programming (MILP) solving. However, existing approaches typically assume variable independence and rely on deterministic single-point predictions, which limits solution diversityand often necessitates extensiv…

• Manifold Generalization Provably Proceeds Memorization in Diffusion Models

  Zebang Shen, Ya-Ping Hsieh, Niao He · 26. März 2026

  Diffusion models often generate novel samples even when the learned score is only \emph{coarse} -- a phenomenon not accounted for by the standard view of diffusion training as density estimation. In this paper, we show that, under the \emph{manifold hypothesis}, this behavior can instead be explaine…

• Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective

  Emi Zeger, Mert Pilanci · 26. März 2026

  Deep neural networks (DNNs), particularly those using Rectified Linear Unit (ReLU) activation functions, have achieved remarkable success across diverse machine learning tasks, including image recognition, audio processing, and language modeling. Despite this success, the non-convex nature of DNN lo…

• Perturbing the Derivative: Doubly Wild Refitting for Model-Free Evaluation of Opaque Machine Learning Predictors

  Haichen Hu, David Simchi-Levi · 26. März 2026

  We study the problem of excess risk evaluation for empirical risk minimization (ERM) under convex losses. We show that by leveraging the idea of wild refitting, one can upper bound the excess risk through the so-called "wild optimism," without relying on the global structure of the underlying functi…

• Deep Neural Regression Collapse

  Akshay Rangamani, Altay Unal · 26. März 2026

  Neural Collapse is a phenomenon that helps identify sparse and low rank structures in deep classifiers. Recent work has extended the definition of neural collapse to regression problems, albeit only measuring the phenomenon at the last layer. In this paper, we establish that Neural Regression Collap…

• Boost Like a (Var)Pro: Trust-Region Gradient Boosting via Variable Projection

  Abhijit Chowdhary, Elizabeth Newman, Deepanshu Verma · 26. März 2026

  Gradient boosting, a method of building additive ensembles from weak learners, has established itself as a practical and theoretically-motivated approach to approximate functions, especially using decision tree weak learners. Comparable methods for smooth parametric learners, such as neural networks…

• Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraints

  Shengping Xie, Zekun Wu, Quan Chen, Kaixu Tang · 25. März 2026

  Implicit bias induced by gradient-based algorithms is essential to the generalization of overparameterized models, yet its mechanisms can be subtle. This work leverages the Normalized Steepest Descent} (NSD) framework to investigate how optimization geometry shapes solutions on multiclass separable …

• Asymptotic Learning Curves for Diffusion Models with Random Features Score and Manifold Data

  Anand Jerry George, Nicolas Macris · 25. März 2026

  We study the theoretical behavior of denoising score matching--the learning task associated to diffusion models--when the data distribution is supported on a low-dimensional manifold and the score is parameterized using a random feature neural network. We derive asymptotically exact expressions for …

• Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles

  Lesi Chen, Yaohua Ma, Jingzhao Zhang · 25. März 2026

  In this work, we consider bilevel optimization when the lower-level problem is strongly convex. Recent works show that with a Hessian-vector product (HVP) oracle, one can provably find an $\epsilon$-stationary point within ${\mathcal{O}}(\epsilon^{-2})$ oracle calls. However, the HVP oracle may be i…