Stochastic Gradient Optimization Techniques

Neueste Paper

• Linear Gradient Prediction with Control Variates

  Kamil Ciosek, Nicol\`o Felicioni, Juan Elenter Litwin · 10. November 2025

  We propose a new way of training neural networks, with the goal of reducing training cost. Our method uses approximate predicted gradients instead of the full gradients that require an expensive backward pass. We derive a control-variate-based technique that ensures our updates are unbiased estimate…

• A New Framework for Convex Clustering in Kernel Spaces: Finite Sample Bounds, Consistency and Performance Insights

  Shubhayan Pan, Saptarshi Chakraborty, Debolina Paul, Kushal Bose, Swagatam Das · 10. November 2025

  Convex clustering is a well-regarded clustering method, resembling the similar centroid-based approach of Lloyd's $k$-means, without requiring a predefined cluster count. It starts with each data point as its centroid and iteratively merges them. Despite its advantages, this method can fail when dea…

• On Flow Matching KL Divergence

  Maojiang Su, Jerry Yao-Chieh Hu, Sophia Pi, Han Liu · 10. November 2025

  We derive a deterministic, non-asymptotic upper bound on the Kullback-Leibler (KL) divergence of the flow-matching distribution approximation. In particular, if the $L_2$ flow-matching loss is bounded by $\epsilon^2 > 0$, then the KL divergence between the true data distribution and the estimated di…

• Sharp Minima Can Generalize: A Loss Landscape Perspective On Data

  Raymond Fan, Bryce Sandlund, Lin Myat Ko · 10. November 2025

  The volume hypothesis suggests deep learning is effective because it is likely to find flat minima due to their large volumes, and flat minima generalize well. This picture does not explain the role of large datasets in generalization. Measuring minima volumes under varying amounts of training data …

• Federated Stochastic Minimax Optimization under Heavy-Tailed Noises

  Xinwen Zhang, Hongchang Gao · 7. November 2025

  Heavy-tailed noise has attracted growing attention in nonconvex stochastic optimization, as numerous empirical studies suggest it offers a more realistic assumption than standard bounded variance assumption. In this work, we investigate nonconvex-PL minimax optimization under heavy-tailed gradient n…

• The Strong Lottery Ticket Hypothesis for Multi-Head Attention Mechanisms

  Hikari Otsuka, Daiki Chijiwa, Yasuyuki Okoshi, Daichi Fujiki, Susumu Takeuchi, Masato Motomura · 7. November 2025

  The strong lottery ticket hypothesis (SLTH) conjectures that high-performing subnetworks, called strong lottery tickets (SLTs), are hidden in randomly initialized neural networks. Although recent theoretical studies have established the SLTH across various neural architectures, the SLTH for transfor…

• High-dimensional limit theorems for SGD: Momentum and Adaptive Step-sizes

  Aukosh Jagannath, Taj Jones-McCormick, Varnan Sarangian · 7. November 2025

  We develop a high-dimensional scaling limit for Stochastic Gradient Descent with Polyak Momentum (SGD-M) and adaptive step-sizes. This provides a framework to rigourously compare online SGD with some of its popular variants. We show that the scaling limits of SGD-M coincide with those of online SGD …

• Non-Asymptotic Optimization and Generalization Bounds for Stochastic Gauss-Newton in Overparameterized Models

  Semih Cayci · 7. November 2025

  An important question in deep learning is how higher-order optimization methods affect generalization. In this work, we analyze a stochastic Gauss-Newton (SGN) method with Levenberg-Marquardt damping and mini-batch sampling for training overparameterized deep neural networks with smooth activations …

• On the Equivalence of Regression and Classification

  Jayadeva, Naman Dwivedi, Hari Krishnan, N. M. Anoop Krishnan · 7. November 2025

  A formal link between regression and classification has been tenuous. Even though the margin maximization term $\|w\|$ is used in support vector regression, it has at best been justified as a regularizer. We show that a regression problem with $M$ samples lying on a hyperplane has a one-to-one equiv…

• Min-Max Optimization Is Strictly Easier Than Variational Inequalities

  Henry Shugart, Jason M. Altschuler · 6. November 2025

  Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality conditions. Is it possible to solve min-max problems faster by bypassing this reduction? This paper initiates this investigat…

• Towards Scalable Backpropagation-Free Gradient Estimation

  Daniel Wang, Evan Markou, Dylan Campbell · 6. November 2025

  While backpropagation--reverse-mode automatic differentiation--has been extraordinarily successful in deep learning, it requires two passes (forward and backward) through the neural network and the storage of intermediate activations. Existing gradient estimation methods that instead use forward-mod…

• Flat Minima and Generalization: Insights from Stochastic Convex Optimization

  Matan Schliserman, Shira Vansover-Hager, Tomer Koren · 6. November 2025

  Understanding the generalization behavior of learning algorithms is a central goal of learning theory. A recently emerging explanation is that learning algorithms are successful in practice because they converge to flat minima, which have been consistently associated with improved generalization per…

• Precise asymptotic analysis of Sobolev training for random feature models

  Katharine E Fisher, Matthew TC Li, Youssef Marzouk, Timo Schorlepp · 6. November 2025

  Gradient information is widely useful and available in applications, and is therefore natural to include in the training of neural networks. Yet little is known theoretically about the impact of Sobolev training -- regression with both function and gradient data -- on the generalization error of hig…

• Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

  Dan Garber · 5. November 2025

  We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and the unit nuclear-norm ball. A key te…

• Matrix Sensing with Kernel Optimal Loss: Robustness and Optimization Landscape

  Xinyuan Song, Jiaye Teng, Ziye Ma · 5. November 2025

  In this paper we study how the choice of loss functions of non-convex optimization problems affects their robustness and optimization landscape, through the study of noisy matrix sensing. In traditional regression tasks, mean squared error (MSE) loss is a common choice, but it can be unreliable for …

• The Geometry of Grokking: Norm Minimization on the Zero-Loss Manifold

  Tiberiu Musat · 5. November 2025

  Grokking is a puzzling phenomenon in neural networks where full generalization occurs only after a substantial delay following the complete memorization of the training data. Previous research has linked this delayed generalization to representation learning driven by weight decay, but the precise u…

• Limit Theorems for Stochastic Gradient Descent in High-Dimensional Single-Layer Networks

  Parsa Rangriz · 5. November 2025

  This paper studies the high-dimensional scaling limits of online stochastic gradient descent (SGD) for single-layer networks. Building on the seminal work of Saad and Solla, which analyzed the deterministic (ballistic) scaling limits of SGD corresponding to the gradient flow of the population loss, …

• Gradient-Variation Online Adaptivity for Accelerated Optimization with H\"older Smoothness

  Yuheng Zhao, Yu-Hu Yan, Kfir Yehuda Levy, Peng Zhao · 5. November 2025

  Smoothness is known to be crucial for acceleration in offline optimization, and for gradient-variation regret minimization in online learning. Interestingly, these two problems are actually closely connected -- accelerated optimization can be understood through the lens of gradient-variation online …

• ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models

  Lejs Deen Behric, Liang Zhang, Bingcong Li, Kiran Koshy Thekumparampil · 5. November 2025

  Zeroth-order or derivative-free optimization (MeZO) is an attractive strategy for finetuning large language models (LLMs) because it eliminates the memory overhead of backpropagation. However, it converges slowly due to the inherent curse of dimensionality when searching for descent directions in th…

• Adam Reduces a Unique Form of Sharpness: Theoretical Insights Near the Minimizer Manifold

  Xinghan Li, Haodong Wen, Kaifeng Lyu · 5. November 2025

  Despite the popularity of the Adam optimizer in practice, most theoretical analyses study Stochastic Gradient Descent (SGD) as a proxy for Adam, and little is known about how the solutions found by Adam differ. In this paper, we show that Adam implicitly reduces a unique form of sharpness measure sh…

• Emergence and scaling laws in SGD learning of shallow neural networks

  Yunwei Ren, Eshaan Nichani, Denny Wu, Jason D. Lee · 5. November 2025

  We study the complexity of online stochastic gradient descent (SGD) for learning a two-layer neural network with $P$ neurons on isotropic Gaussian data: $f_*(\boldsymbol{x}) = \sum_{p=1}^P a_p\cdot \sigma(\langle\boldsymbol{x},\boldsymbol{v}_p^*\rangle)$, $\boldsymbol{x} \sim \mathcal{N}(0,\boldsymb…

• DeepContour: A Hybrid Deep Learning Framework for Accelerating Generalized Eigenvalue Problem Solving via Efficient Contour Design

  Yeqiu Chen, Ziyan Liu, Hong Wang · 5. November 2025

  Solving large-scale Generalized Eigenvalue Problems (GEPs) is a fundamental yet computationally prohibitive task in science and engineering. As a promising direction, contour integral (CI) methods, such as the CIRR algorithm, offer an efficient and parallelizable framework. However, their performanc…

• Computational Budget Should Be Considered in Data Selection

  Weilin Wan, Weizhong Zhang, Cheng Jin · 4. November 2025

  Data selection improves computational efficiency by choosing informative subsets of training samples. However, existing methods ignore the compute budget, treating data selection and importance evaluation independently of compute budget constraints. Yet empirical studies show no algorithm can consis…

• Provable Generalization Bounds for Deep Neural Networks with Momentum-Adaptive Gradient Dropout

  Adeel Safder · 4. November 2025

  Deep neural networks (DNNs) achieve remarkable performance but often suffer from overfitting due to their high capacity. We introduce Momentum-Adaptive Gradient Dropout (MAGDrop), a novel regularization method that dynamically adjusts dropout rates on activations based on current gradients and accum…

• Sharp Lower Bounds for Linearized ReLU^k Approximation on the Sphere

  Tong Mao, Jinchao Xu · 4. November 2025

  We prove a saturation theorem for linearized shallow ReLU$^k$ neural networks on the unit sphere $\mathbb S^d$. For any antipodally quasi-uniform set of centers, if the target function has smoothness $r>\tfrac{d+2k+1}{2}$, then the best $\mathcal{L}^2(\mathbb S^d)$ approximation cannot converge fast…