Gradient Descent

Ask about this topic

Overview

Gradient descent is a family of methods that repeatedly adjusts parameters in the direction that lowers an objective, making it a basic tool for training neural networks and fitting models such as logistic regression. Common approaches include full-batch and stochastic gradient descent, momentum and Nesterov acceleration, adaptive optimizers such as Adam, and geometry-aware variants such as natural, preconditioned, projected, or mirror descent. Theory and applications span deep-network training, matrix recovery, differential privacy, and decentralized or federated learning, with evaluations often measuring convergence, prediction quality, communication, memory, or privacy cost. A central tension is that larger or adaptive steps can speed training but also cause oscillations or instability, while the geometry, noise, and stopping time can change both which solution is reached and how well it generalizes.

Latest papers

CardsList

118 papers16 papers in the last four weeks, up 60% on the four weeks before. 0.1% of all new papers.

Mar 31, 2026

Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity

The low-rank matrix recovery problem seeks to reconstruct an unknown n1×n2n_1 \times n_2 rank-rr matrix from mm linear measurements, where m≪n1n2m\ll n_1n_2. This problem has been extensively studied over the past few decades, leading to a variety of algorithms with solid theoretical guarantees. Among these, gradient descent based non-convex methods have become particularly popular due to their computational efficiency. However, these methods typically suffer from two key limitations: a sub-optimal sample complexity of O((n1+n2)r2)O((n_1 + n_2)r^2) and an iteration complexity of O(κlog⁡(1/ε))O(κ\log(1/ε)) to achieve εε-accuracy, resulting in slow convergence when the target matrix is ill-conditioned. Here, κκ denotes the condition number of the unknown matrix. Recent studies show that a preconditioned variant of GD, known as scaled gradient descent (ScaledGD), can significantly reduce the iteration complexity to O(log⁡(1/ε))O(\log(1/ε)). Nonetheless, its sample complexity remains sub-optimal at O((n1+n2)r2)O((n_1 + n_2)r^2). In contrast, a delicate virtual sequence technique demonstrates that the standard GD in the positive semidefinite (PSD) setting achieves the optimal sample complexity O((n1+n2)r)O((n_1 + n_2)r), but converges more slowly with an iteration complexity O(κ2log⁡(1/ε))O(κ^2 \log(1/ε)). In this paper, through a more refined analysis, we show that ScaledGD achieves both the optimal sample complexity O((n1+n2)r)O((n_1 + n_2)r) and the improved iteration complexity O(log⁡(1/ε))O(\log(1/ε)). Notably, our results extend beyond the PSD setting to general low-rank matrix recovery problem. Numerical experiments further validate that ScaledGD accelerates convergence for ill-conditioned matrices with the optimal sampling complexity.

Zhenxuan Li, Meng Huang

Gradient Descent
AskPDF
Mar 24, 2026

Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraints

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 data. We introduce NucGD, a geometry-aware optimizer designed to enforce low rank structures through nuclear norm constraints. Beyond the algorithm itself, we connect NucGD with emerging low-rank projection methods, providing a unified perspective. To enable scalable training, we derive an efficient SVD-free update rule via asynchronous power iteration. Furthermore, we empirically dissect the impact of stochastic optimization dynamics, characterizing how varying levels of gradient noise induced by mini-batch sampling and momentum modulate the convergence toward the expected maximum margin solutions.Our code is accessible at: https://github.com/Tsokarsic/observing-the-implicit-bias-on-multiclass-seperable-data.

Shengping Xie, Zekun Wu, Quan Chen +1

School of Mathematical Sciences, Peking University

Implicit BiasGradient DescentNuclear Norm MinimizationMulticlass ClassificationStochastic Gradient Descent
AskPDF
Mar 23, 2026

Optimizing Multi-Agent Weather Captioning via Text Gradient Descent: A Training-Free Approach with Consensus-Aware Gradient Fusion

Generating interpretable natural language captions from weather time series data remains a significant challenge at the intersection of meteorological science and natural language processing. While recent advances in Large Language Models (LLMs) have demonstrated remarkable capabilities in time series forecasting and analysis, existing approaches either produce numerical predictions without human-accessible explanations or generate generic descriptions lacking domain-specific depth. We introduce WeatherTGD, a training-free multi-agent framework that reinterprets collaborative caption refinement through the lens of Text Gradient Descent (TGD). Our system deploys three specialized LLM agents including a Statistical Analyst, a Physics Interpreter, and a Meteorology Expert that generate domain-specific textual gradients from weather time series observations. These gradients are aggregated through a novel Consensus-Aware Gradient Fusion mechanism that extracts common signals while preserving unique domain perspectives. The fused gradients then guide an iterative refinement process analogous to gradient descent, where each LLM-generated feedback signal updates the caption toward an optimal solution. Experiments on real-world meteorological datasets demonstrate that WeatherTGD achieves significant improvements in both LLM-based evaluation and human expert evaluation, substantially outperforming existing multi-agent baselines while maintaining computational efficiency through parallel agent execution.

Shixu Liu

School of Computer & Information Technology, Northeast Petroleum University, No. 99 Xuefu Street, Ranghulu District, Daqing, Heilongjiang, 163318, P.R. China

Multi-Agent LLM SystemsGradient Descent
AskPDF
Mar 22, 2026

A Generalised Exponentiated Gradient Approach to Enhance Fairness in Binary and Multi-class Classification Tasks

The widespread use of AI and ML models in sensitive areas raises significant concerns about fairness. While the research community has introduced various methods for bias mitigation in binary classification tasks, the issue remains under-explored in multi-class classification settings. To address this limitation, in this paper, we first formulate the problem of fair learning in multi-class classification as a multi-objective problem between effectiveness (i.e., prediction correctness) and multiple linear fairness constraints. Next, we propose a Generalised Exponentiated Gradient (GEG) algorithm to solve this task. GEG is an in-processing algorithm that enhances fairness in binary and multi-class classification settings under multiple fairness definitions. We conduct an extensive empirical evaluation of GEG against six baselines across seven multi-class and three binary datasets, using four widely adopted effectiveness metrics and three fairness definitions.

Maryam Boubekraoui, Giordano d'Aloisio, Antinisca Di Marco

Laboratoire d’Intelligence Artificielle et Systèmes Industriels (LIASI), HESTIM Engineering and Business School, Casablanca, Morocco · Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, L’Aquila, Italy

Gradient DescentAlgorithmic FairnessMulticlass Classification
AskPDF
Mar 18, 2026

Auto-Unrolled Proximal Gradient Descent: An AutoML Approach to Interpretable Waveform Optimization

This study explores the combination of automated machine learning (AutoML) with model-based deep unfolding (DU) for optimizing wireless beamforming and waveforms. We convert the iterative proximal gradient descent (PGD) algorithm into a deep neural network, wherein the parameters of each layer are learned instead of being predetermined. Additionally, we enhance the architecture by incorporating a hybrid layer that performs a learnable linear gradient transformation prior to the proximal projection. By utilizing AutoGluon with a tree-structured parzen estimator (TPE) for hyperparameter optimization (HPO) across an expanded search space, which includes network depth, step-size initialization, optimizer, learning rate scheduler, layer type, and post-gradient activation, the proposed auto-unrolled PGD (Auto-PGD) achieves 98.8% of the spectral efficiency of a traditional 200-iteration PGD solver using only five unrolled layers, while requiring only 100 training samples. We also address a gradient normalization issue to ensure consistent performance during training and evaluation, and we illustrate per-layer sum-rate logging as a tool for transparency. These contributions highlight a notable reduction in the amount of training data and inference cost required, while maintaining high interpretability compared to conventional black-box architectures.

Ahmet Kaplan

Deep UnfoldingWireless CommunicationsGradient Descent
AskPDF
Mar 11, 2026

Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

In this work, we study the convergence properties of the Dual Space Preconditioned Gradient Descent, encompassing optimizers such as Normalized Gradient Descent and Gradient Clipping. We consider preconditioners of the form ∇K\nabla K, where K:Rd×k→RK: \mathbb{R}^{d \times k} \to \mathbb{R} is convex and apply ∇K(⋅)\nabla K(\cdot) to train an over-parameterized linear model with a convex loss of the form ℓ(XW−Y)\ell(X W - Y), for weights W∈Rd×kW \in \mathbb{R}^{d \times k}, labels Y∈Rn×kY \in \mathbb{R}^{n \times k} and data X∈Rn×dX \in \mathbb{R}^{n \times d}. Under the aforementioned assumptions, we prove that the iterates of the full-batch preconditioned gradient descent converge at an exponential rate to a point W∞∈Rd×kW_{\infty} \in \mathbb{R}^{d \times k} satisfying XW∞=YXW_{\infty} = Y. We also study the implicit bias of Dual Space Preconditioned Gradient Descent. First, we demonstrate analytically and empirically that, for general K(⋅)K(\cdot), W∞W_\infty depends on the chosen constant step size, hindering a precise characterization of the implicit bias. We also provide an approximate implicit bias property for general preconditioners, namely, ∥W0−W∞∥F≤c∥W0−WGD,∞∥F\|W_0 - W_{\infty}\|_F \le c \|W_0 - W_{\text{GD}, \infty}\|_F for a constant c>0c>0 and WGD,∞W_{\text{GD}, \infty} denoting the convergence point of GD initialized at W0W_0. Furthermore, for preconditioners of the form K(G)=h(∥G∥F)K(G) = h(\|G\|_F), known as {\it isotropic preconditioners}, and for the stochastic variation of the algorithm with arbitrary batch-size, we prove linear convergence to WGD,∞W_{\text{GD}, \infty}. Finally, in the experiments, we demonstrate faster convergence on a nonlinear model obtained using the smoothed matrix elastic-net as a preconditioner.

Reza Ghane, Danil Akhtiamov, Babak Hassibi

Electrical Engineering Department, California Institute of Technology, Pasadena, CA 91125 USA · Computing + Mathematical Sciences Department, California Institute of Technology, Pasadena, CA 91125 USA

Gradient DescentImplicit BiasStochastic Optimization Convergence
AskPDF
Mar 6, 2026

Omni-Masked Gradient Descent: Memory-Efficient Optimization via Mask Traversal with Improved Convergence

Memory-efficient optimization methods have recently gained increasing attention for scaling full-parameter training of large language models under the GPU-memory bottleneck. Existing approaches either lack clear convergence guarantees, or only achieve the standard O(ε−4){\mathcal{O}}(ε^{-4}) iteration complexity in the nonconvex settings. We propose Omni-Masked Gradient Descent (OMGD), an optimization method based on mask traversal for memory efficient training, and provide a nonconvex convergence analysis that establishes a strictly improved iteration complexity of O~(ε−3)\tilde{\mathcal{O}}(ε^{-3}) for finding an εε-approximate stationary point. Empirically, OMGD is a lightweight, plug-and-play approach that integrates seamlessly into most mainstream optimizers, yielding consistent improvements over competitive baselines in both fine-tuning and pre-training tasks.

Hui Yang, Tao Ren, Jinyang Jiang +2

1Guanghua School of Management, Peking University · 2Wangxuan Institute of Computer Technology, Peking University.

Gradient DescentMemory-Efficient TrainingNonconvex Optimization
AskPDF
Mar 5, 2026

How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?

Overparameterized ML models, including neural networks, typically induce underdetermined training objectives with multiple global minima. The implicit bias refers to the limiting global minimum that is attained by a common optimization algorithm, such as gradient descent (GD). In this paper, we characterize the implicit bias of GD for training a shallow ReLU model with the squared loss on high-dimensional random features. Prior work (Vardi and Shamir, 2021) showed that the implicit bias does not exist in the worst-case, or corresponds exactly to the minimum-ℓ2\ell_2-norm interpolating solution under exactly orthogonal data (Boursier et al., 2022). Our work interpolates between these two extremes and shows that, for sufficiently high-dimensional random data, the implicit bias approximates the minimum-ℓ2\ell_2-norm solution with high probability with a gap on the order Θ(n/∣∣λ∣∣1)Θ(\sqrt{n/||λ||_1}), where nn is the number of training examples and λλ denotes the spectrum of the data covariance matrix. Our results are obtained through a novel primal-dual analysis that carefully tracks the evolution of predictions, data-span coefficients, as well as their interactions, and show that the ReLU activation pattern quickly stabilizes with high probability over random data.

Kuo-Wei Lai, Guanghui Wang, Molei Tao +1

School of Electrical and Computer Engineering, Georgia Institute of Technology · College of Computing, Georgia Institute of Technology · School of Mathematics, Georgia Institute of Technology +1

High-Dimensional Linear RegressionRandom Feature MethodsImplicit BiasReLU Neural NetworksGradient DescentShallow Neural Networks
AskPDF
Mar 4, 2026

Exploiting Subgradient Sparsity in Max-Plus Neural Networks

Deep Neural Networks are powerful tools for solving machine learning problems, but their training often involves dense and costly parameter updates. In this work, we use a novel Max-Plus neural architecture in which classical addition and multiplication are replaced with maximum and summation operations respectively. This is a promising architecture in terms of interpretability, but its training is challenging. A particular feature is that this algebraic structure naturally induces sparsity in the subgradients, as only neurons that contribute to the maximum affect the loss. However, standard backpropagation fails to exploit this sparsity, leading to unnecessary computations. In this work, we focus on the minimization of the worst sample loss which transfers this sparsity to the optimization loss. To address this, we propose a sparse subgradient algorithm that explicitly exploits the algebraic sparsity. By tailoring the optimization procedure to the non-smooth nature of Max-Plus models, our method achieves more efficient updates while retaining theoretical guarantees. This highlights a principled path toward bridging algebraic structure and scalable learning.

Ikhlas Enaieh, Olivier Fercoq

LTCI, S2A · Image, Data, Signal Department (IDS), Telecom Paris, Institut Polytechnique de Paris, France. · S2A, LTCI

Neural Network OptimizationGradient Descent
AskPDF
Mar 3, 2026

Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents

This paper proposes a novel parameter selection strategy for kernel-based gradient descent (KGD) algorithms, integrating bias-variance analysis with the splitting method. We introduce the concept of empirical effective dimension to quantify iteration increments in KGD, deriving an adaptive parameter selection strategy that is implementable. Theoretical verifications are provided within the framework of learning theory. Utilizing the recently developed integral operator approach, we rigorously demonstrate that KGD, equipped with the proposed adaptive parameter selection strategy, achieves the optimal generalization error bound and adapts effectively to different kernels, target functions, and error metrics. Consequently, this strategy showcases significant advantages over existing parameter selection methods for KGD.

Xiaotong Liu, Yunwen Lei, Xiangyu Chang +1

Center for Intelligent Decision-Making and Machine Learning, School of Management, Xi’an Jiaotong University, Xi’an, China · Department of Mathematics, The University of Hong Kong, Hongkong, China

Kernel MethodsHyperparameter OptimizationGradient DescentStatistical Learning Theory
AskPDF
Mar 3, 2026

The power of small initialization in noisy low-tubal-rank tensor recovery

We study the problem of recovering a low-tubal-rank tensor X_⋆∈Rn×n×k\mathcal{X}\_\star\in \mathbb{R}^{n \times n \times k} from noisy linear measurements under the t-product framework. A widely adopted strategy involves factorizing the optimization variable as U∗U⊤\mathcal{U} * \mathcal{U}^\top, where U∈Rn×R×k\mathcal{U} \in \mathbb{R}^{n \times R \times k}, followed by applying factorized gradient descent (FGD) to solve the resulting optimization problem. Since the tubal-rank rr of the underlying tensor X⋆\mathcal{X}_\star is typically unknown, this method often assumes r<R≤nr < R \le n, a regime known as over-parameterization. However, when the measurements are corrupted by some dense noise (e.g., Gaussian noise), FGD with the commonly used spectral initialization yields a recovery error that grows linearly with the over-estimated tubal-rank RR. To address this issue, we show that using a small initialization enables FGD to achieve a nearly minimax optimal recovery error, even when the tubal-rank RR is significantly overestimated. Using a four-stage analytic framework, we analyze this phenomenon and establish the sharpest known error bound to date, which is independent of the overestimated tubal-rank RR. Furthermore, we provide a theoretical guarantee showing that an easy-to-use early stopping strategy can achieve the best known result in practice. All these theoretical findings are validated through a series of simulations and real-data experiments.

ZHiyu Liu, Haobo Geng, Xudong Wang +3

State Key Laboratory of Robotics and Intelligent Systems, Shenyang Institute of Automation, Chinese Academy of Sciences, China · University of Chinese Academy of Sciences, China · School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore +1

OverparameterizationGradient Descent
AskPDF
Mar 2, 2026

Never Saddle for Reparameterized Steepest Descent as Mirror Flow

How does the choice of optimization algorithm shape a model's ability to learn features? To address this question for steepest descent methods --including sign descent, which is closely related to Adam --we introduce steepest mirror flows as a unifying theoretical framework. This framework reveals how optimization geometry governs learning dynamics, implicit bias, and sparsity and it provides two explanations for why Adam and AdamW often outperform SGD in fine-tuning. Focusing on diagonal linear networks and deep diagonal linear reparameterizations (a simplified proxy for attention), we show that steeper descent facilitates both saddle-point escape and feature learning. In contrast, gradient descent requires unrealistically large learning rates to escape saddles, an uncommon regime in fine-tuning. Empirically, we confirm that saddle-point escape is a central challenge in fine-tuning. Furthermore, we demonstrate that decoupled weight decay, as in AdamW, stabilizes feature learning by enforcing novel balance equations. Together, these results highlight two mechanisms how steepest descent can aid modern optimization.

Tom Jacobs, Chao Zhou, Rebekka Burkholz

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Neural Network Training DynamicsGradient Descent DynamicsAdaptive Gradient MethodsGradient DescentMirror DescentRepresentation Learning
AskPDF
Mar 2, 2026

Training Dynamics of Softmax Self-Attention: Fast Global Convergence via Preconditioning

We study the training dynamics of gradient descent in a softmax self-attention layer trained to perform linear regression and show that a simple first-order optimization algorithm can converge to the globally optimal self-attention parameters at a geometric rate. Our analysis proceeds in two steps. First, we show that in the infinite-data limit the regression problem solved by the self-attention layer is equivalent to a nonconvex matrix factorization problem. Second, we exploit this connection to design a novel "structure-aware" variant of gradient descent which efficiently optimizes the original finite-data regression objective. Our optimization algorithm features several innovations over standard gradient descent, including a preconditioner and regularizer which help avoid spurious stationary points, and a data-dependent spectral initialization of parameters which lie near the manifold of global minima with high probability.

Gautam Goel, Mahdi Soltanolkotabi, Peter Bartlett

Simons Institute, UC Berkeley · Department of Electrical and Computer Engineering, University of Southern California

Self-AttentionSoftmax AttentionGradient Descent DynamicsGradient Descent
AskPDF
Feb 21, 2026

Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression

Gradient descent and stochastic gradient descent are central to modern machine learning, yet their behavior under large step sizes remains theoretically unclear. Recent work suggests that acceleration often arises near the edge of stability, where optimization trajectories become unstable and difficult to analyze. Existing results for separable logistic regression achieve faster convergence by explicitly leveraging such unstable regimes through constant or adaptive large step sizes. In this paper, we show that instability is not inherent to acceleration. We prove that gradient descent with a simple, non-adaptive increasing step-size schedule achieves exponential convergence for separable logistic regression under a margin condition, while remaining entirely within a stable optimization regime. The resulting method is anytime and does not require prior knowledge of the optimization horizon or target accuracy. We also establish exponential convergence of stochastic gradient descent using a lightweight adaptive step-size rule that avoids line search and specialized procedures, improving upon existing polynomial-rate guarantees. Together, our results demonstrate that carefully structured step-size growth alone suffices to obtain exponential acceleration for both gradient descent and stochastic gradient descent.

Sacchit Kale, Piyushi Manupriya, Pierre Marion +2

Undergraduate Programme Indian Institute of Science, Bangalore. · Dept. of Computer Science and Automation Indian Institute of Science, Bangalore. · Inria, Ecole Normale Supérieure PSL Research University, Paris, France.

Gradient DescentStochastic Optimization ConvergenceStochastic Gradient DescentLearning Rate SchedulingLogistic Regression
AskPDF
Feb 18, 2026

The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks

We study the implicit bias of momentum-based optimizers on smooth homogeneous models. We show that momentum steepest descent algorithms like Muon (spectral norm), MomentumGD (ℓ2\ell_2 norm), and Signum (ℓ∞\ell_\infty norm) are approximate steepest descent trajectories under a decaying learning rate schedule, proving that these algorithms have a bias towards KKT points of the corresponding margin maximization problem. We extend the analysis to Adam (without the stability constant), which maximizes the ℓ∞\ell_\infty margin, and to Muon-Signum and Muon-Adam, which maximize a hybrid norm. Our experiments corroborate the theory and show that the identity of the margin maximized depends on the choice of optimizer. Overall, our results extend earlier lines of work on steepest descent in homogeneous models and momentum-based optimizers in linear models.

Eitan Gronich, Gal Vardi

Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel

Gradient DescentAdaptive Gradient MethodsAlgorithmic Bias
AskPDF
Jan 30, 2026

Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities

Stochastic non-convex non-concave optimization, formally characterized as Stochastic Variational Inequalities (SVIs), presents unique challenges due to rotational dynamics and the absence of a global merit function. While adaptive step-size methods (like Armijo line-search) have revolutionized convex minimization, their application to this setting is hindered by the Stochasticity Barrier: the noise in gradient estimation masks the true operator curvature, triggering erroneously large steps that destabilize convergence. In this work, we propose VR-SDA-A (Variance-Reduced Stochastic Descent-Ascent with Armijo), a novel algorithm that integrates recursive momentum (STORM) with a rigorous Same-Batch Curvature Verification mechanism. We introduce a theoretical framework based on a Lyapunov potential tracking the Operator Norm, proving that VR- SDA-A achieves an oracle complexity of O(epsilon -3) for finding an epsilon-stationary point in general Lipschitz continuous operators. This matches the optimal rate for non-convex minimization while uniquely enabling automated step-size adaptation in the saddle-point setting. We validate our approach on canonical rotational benchmarks and non-convex robust regression tasks, demonstrating that our method effectively suppresses limit cycles and accelerates convergence with reduced dependence on manual learning rate scheduling.

Yungi Jeong, Takumi Otsuka

Department of Mathematics, National University of Singapore · Department of Computer Science and Communication Engineering, Waseda University

Nonconvex Stochastic OptimizationStochastic Optimization ConvergenceVariance ReductionGradient Descent
AskPDF
Jan 30, 2026

Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval

Spectral gradient methods, such as the Muon optimizer, modify gradient updates by preserving directional information while discarding scale, and have shown strong empirical performance in deep learning. We investigate the mechanisms underlying these gains through a dynamical analysis of a nonlinear phase retrieval model with anisotropic Gaussian inputs, equivalent to training a two-layer neural network with the quadratic activation and fixed second-layer weights. Focusing on a spiked covariance setting where the dominant variance direction is orthogonal to the signal, we show that gradient descent (GD) suffers from a variance-induced misalignment: during the early escaping stage, the high-variance but uninformative spike direction is multiplicatively amplified, degrading alignment with the true signal under strong anisotropy. In contrast, spectral gradient descent (SpecGD) removes this spike amplification effect, leading to stable alignment and accelerated noise contraction. Numerical experiments confirm the theory and show that these phenomena persist under broader anisotropic covariances.

Guillaume Braun, Han Bao, Wei Huang +1

RIKEN AIP · The Institute of Statistical Mathematics · Tohoku University +2

Gradient DescentGradient Descent DynamicsGradient Alignment
AskPDF
Dec 31, 2025

Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis

In this work, we introduce basic inequalities\textit{basic inequalities} for first-order iterative optimization algorithms, forming a simple yet versatile framework which connects implicit and explicit regularization. Building on related comparison inequalities for optimization iterates that already exist in the literature, we extend and unify these arguments to produce a general framework, which can be used as a tool for statistical analysis. In more detail, let ff denote the objective function to be optimized. Given a first-order iterative algorithm initialized at θ0θ_0, with current iterate θTθ_T, the basic inequality upper bounds f(θT)−f(z)f(θ_T) - f(z) for any reference point zz in terms of the accumulated step sizes, and the distances between θ0θ_0, θTθ_T, and zz. These distances are measured in a geometry inherent to the optimization algorithm, which then translates into a notion of regularization being applied across the path of iterates. In addition to refining existing results on gradient descent, we provide new results for mirror descent and other first-order methods. We then show how to use these basic inequalities to derive elementary yet useful bounds on the prediction risk of early-stopped gradient descent and exponentiated gradient descent iterates in generalized linear models. We also supplement these findings with numerical experiments.

Seunghoon Paik, Kangjie Zhou, Matus Telgarsky +1

University of California, Berkeley · Columbia University · New York University

Early StoppingGradient DescentMirror DescentGeneralized Linear ModelsImplicit Regularization
AskPDF
Nov 30, 2025

Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance

Adaptive and non-Euclidean optimizers often outperform Euclidean methods such as stochastic gradient descent (SGD) in language modeling by a large margin. Existing theory usually explains this gap by assuming favorable smoothness geometry or noise structure tailored to the specific optimizer. We instead ask whether such geometry can be induced from a concrete learning setting. Starting from an optimizer gap that persists across realistic language-modeling experiments, we progressively remove sequence dependence, architectural complexity, and stochasticity. We find that the gap exists in a minimal setting: the softmax unigram model with heavy-tailed data. This model exposes a simple deterministic mechanism under heavy-tailed class imbalance. We prove that GD learns rare tokens slowly because the corresponding logits receive only tiny updates, while SignGD removes this magnitude dependence and moves rare and common coordinates on a more comparable scale. We make this precise with upper and lower bounds for the convergence rate of GD and upper bounds for the convergence of SignGD. Our stochastic bounds contain additional noise-dependent terms that can obscure this advantage in the convergence guarantees and can be reduced by increasing the batch size

Robin Yadav, Shuo Xie, Tianhao Wang +1

Toyota Technological Institute at Chicago · University of British Columbia · University of California, San Diego

Sign-Based OptimizationClass-Imbalanced LearningGradient DescentLanguage ModelingStochastic Optimization Convergence
AskPDF
Nov 4, 2025

A Byzantine-Robust Federated Learning with Nesterov Momentum

We investigate robust federated learning, where a group of workers collaboratively train a shared model under the orchestration of a central server in the presence of Byzantine adversaries capable of arbitrary and potentially malicious behaviors. To improve communication efficiency while retaining resilience against such adversaries, we propose a Byzantine-resilient Nesterov-augmented federated learning (Byrd-NAFL) algorithm. Byrd-NAFL applies Nesterov's momentum at the server to the output of any soft γγ-Byzantine resilient aggregation rule, while each worker only computes and uploads a stochastic gradient, which keeps the workers stateless, as desired for intermittently participating Internet of Things devices. For smooth non-convex losses, we establish a finite-time convergence guarantee for all momentum factors β∈[0,1)β\in[0,1) without requiring the aggregated gradient to be unbiased or bounded; the bound reduces to that of Byzantine-resilient stochastic gradient descent at β=0β=0 and is tighter than that of server-side heavy-ball momentum. Experiments on MNIST, CIFAR-10, and Sentiment140 show that Byrd-NAFL converges faster and attains higher accuracy than existing benchmarks in most i.i.d. and non-i.i.d. setups under diverse attacks, while its resilience is bounded by that of the underlying aggregation rule.

Lihan Xu, Xiaoyi Fan, Gang Wang +3

School of Cyber Science and Engineering, Xi’an Jiaotong University, Xi’an 710049, China. · the Artificial Intelligence Research Institute and Guangdong-Hong Kong-Macao Joint Laboratory for Emotional Intelligence and Pervasive Computing, Shenzhen MSU-BIT University, Shenzhen 518172, China. · the State Key Laboratory of Autonomous Intelligent Unmanned Systems, Beijing Institute of Technology, Beijing 100081, China.

Federated Learning AggregationByzantine-Robust Federated LearningCommunication-Efficient Distributed TrainingGradient DescentFederated Learning
AskPDF
Jul 15, 2025

Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?

Gradient descent on logistic regression has many fascinating properties not fully captured by classical analyses. For linearly separable data, the iterates converge in direction to the maximum-margin separator regardless of how large the step size is. For non-separable data, however, cycles may occur even for step sizes below the local stability threshold of 2/λ∗2/λ^*, where λ∗λ^* is the largest eigenvalue of the Hessian at the solution. We ask whether requiring all examples to have equal norm is a sufficient condition for global convergence below this threshold. We prove that this is indeed true in one dimension. In higher dimensions, even equal-norm datasets can produce cycles, although global convergence holds for the population loss when the examples are uniformly distributed on the sphere. Finally, in one dimension, we relax the equal-norm assumption to an annulus condition that ensures global convergence below the stability threshold, suggesting a path towards analogous sufficient conditions in higher dimensions.

Si Yi Meng, Baptiste Goujaud, Antonio Orvieto +1

Inria Paris, Paris, France · Inria Saclay, Palaiseau, France · ELLIS Institute Tübingen; MPI for Intelligent Systems; Tübingen AI Center, Germany +1

Logistic RegressionGradient DescentGradient Descent Dynamics
AskPDF
May 19, 2025

When majority rules, minority loses: bias amplification of gradient descent

Despite growing empirical evidence of bias amplification in machine learning, its theoretical foundations remain poorly understood. We develop a formal framework for majority-minority learning tasks, showing how standard training can favor majority groups and produce stereotypical predictors that neglect minority-specific features. Assuming population and variance imbalance, our analysis reveals three key findings: (i) the close proximity between ``full-data'' and stereotypical predictors, (ii) the dominance of a region where training the entire model tends to merely learn the majority traits, and (iii) a lower bound on the additional training required. Our results are illustrated through experiments in deep learning for tabular and image classification tasks.

François Bachoc, Jérôme Bolte, Ryan Boustany +1

LPP · University of Lille · Institut Universitaire de France (IUF) +6

Class-Imbalanced LearningGradient DescentAlgorithmic BiasClassificationStatistical Learning Theory
AskPDF
May 16, 2025

Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra

Natural Gradient Descent (NGD) has emerged as a promising optimization algorithm for training neural network-based solvers for partial differential equations (PDEs), such as Physics-Informed Neural Networks (PINNs). However, its practical use is often limited by the high computational cost of solving linear systems involving the Gramian matrix. While matrix-free NGD methods based on the conjugate gradient (CG) method avoid explicit matrix inversion, the ill-conditioning of the Gramian significantly slows the convergence of CG. In this work, we extend matrix-free NGD to broader classes of problems than previously considered and propose the use of Randomized Numerical Linear Algebra (RandNLA) techniques for efficient preconditioning of the inner CG solver. The resulting algorithms demonstrate substantial performance improvements over existing NGD-based methods on a range of PDE problems discretized using neural networks, and offer competitive results compared to other state-of-the-art optimizers.

Ivan Bioli, Carlo Marcati, Giancarlo Sangalli

Department of Mathematics, University of Pavia, 27100 Pavia, Italy · Department of Civil Engineering and Architecture, University of Pavia, 27100 Pavia, Italy · Institut Camille Jordan, Lyon 1 Université, 69622 Villeurbanne, France +1

Neural PDE SolversGradient DescentPhysics-Informed ML
AskPDF
Dec 12, 2024

The Utility and Complexity of in- and out-of-Distribution Machine Unlearning

Machine unlearning, the process of selectively removing data from trained models, is increasingly crucial for addressing privacy concerns and knowledge gaps post-deployment. Despite this importance, existing approaches are often heuristic and lack formal guarantees. In this paper, we analyze the fundamental utility, time, and space complexity trade-offs of approximate unlearning, providing rigorous certification analogous to differential privacy. For in-distribution forget data -- data similar to the retain set -- we show that a surprisingly simple and general procedure, empirical risk minimization with output perturbation, achieves tight unlearning-utility-complexity trade-offs, addressing a previous theoretical gap on the separation from unlearning "for free" via differential privacy, which inherently facilitates the removal of such data. However, such techniques fail with out-of-distribution forget data -- data significantly different from the retain set -- where unlearning time complexity can exceed that of retraining, even for a single sample. To address this, we propose a new robust and noisy gradient descent variant that provably amortizes unlearning time complexity without compromising utility.

Youssef Allouah, Joshua Kazdan, Rachid Guerraoui +1

EPFL, Switzerland · Stanford University, USA

Machine UnlearningGradient Descent
AskPDF
Nov 12, 2024

Convergence Rate Analysis of LION

The LION (evoLved sIgn mOmeNtum) optimizer for deep neural network training was found by Google via program search, with the simple sign update yet showing impressive performance in training large scale networks. Although previous studies have investigated its convergence properties, a comprehensive analysis, especially the convergence rate, is still desirable. Recognizing that LION can be regarded as solving a specific constrained problem, this paper focuses on demonstrating its convergence to the Karush-Kuhn-Tucker (KKT) point at the rate of O(dK−1/4)\cal O(\sqrt{d}K^{-1/4}) measured by gradient ℓ1\ell_1 norm, where dd is the problem dimension and KK is the number of iteration steps. Step further, we remove the constraint and establish that LION converges to the critical point of the general unconstrained problem at the same rate. This rate not only delivers the currently optimal dependence on the problem dimension dd but also tightly matches the theoretical lower bound for nonconvex stochastic optimization algorithms, which is typically measured using the gradient ℓ2\ell_2 norm, with respect to the number of iterations KK. Through extensive experiments, we not only demonstrate that LION achieves lower loss and higher performance compared to standard SGD, but also empirically confirm that the gradient ℓ1/ℓ2\ell_1/\ell_2 norm ratio aligns with Θ(d)Θ(\sqrt{d}), thus proving that our convergence rate matches the theoretical lower bound with respect to dd in the empirical sense.

Yiming Dong, Huan Li, Zhouchen Lin

State Key Lab of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University, Beijing, 100871, China · Institute of Robotics and Automatic Information Systems, College of Artificial Intelligence, Nankai University, Tianjin, 300071, China · Pazhou Laboratory (Huangpu), Guangzhou, 510555, China

Sign-Based OptimizationDeep Learning OptimizationGradient DescentNonconvex Stochastic OptimizationStochastic Optimization Convergence
AskPDF
Jun 23, 2024

Jacobian Descent for Multi-Objective Optimization

Many optimization problems require balancing multiple conflicting objectives. To generalize gradient descent, which is limited to single-objective optimization, we introduce Jacobian descent (JD) and its stochastic variants. This algorithm iteratively updates parameters using the Jacobian matrix of a vector-valued objective function, in which each row is the gradient of an individual objective. While several methods to combine gradients already exist in the literature, they generally struggle when the objectives conflict. In contrast, we propose projecting gradients to fully resolve conflict. We prove convergence to the Pareto front in the smooth convex case with this approach, a stronger guarantee than the usual convergence to a weakly Pareto stationary point. Our method also enables instance-wise risk minimization (IWRM), a novel learning paradigm in which the loss of each training example is considered a separate objective. Early experimentation on image classification shows promising results for IWRM. Lastly, we provide an efficient implementation of JD using the Gramian of the Jacobian matrix to drastically reduce memory requirements.

Pierre Quinton, Valérian Rey

Independent

Multi-Objective OptimizationPareto OptimizationGradient Descent
AskPDF
Jun 7, 2024

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size 2/λ2/λ, where λλ is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than 1/λ1/λ suffices for global convergence. However, for all step sizes between 1/λ1/λ and the critical step size 2/λ2/λ, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than 1/λ1/λ. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.

Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao +1

Department of Computer Science Cornell University Ithaca, NY, USA · ELLIS Institute Tübingen MPI for Intelligent Systems Tübingen AI Center, Germany

Dynamical SystemsLogistic RegressionOptimization Convergence AnalysisGradient DescentGradient Descent Dynamics
AskPDF
Jan 26, 2022

Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant

Training logistic regression over encrypted data has emerged as a prominent approach to addressing security concerns in recent years. In this paper, we introduce an efficient gradient variant, termed the quadratic gradient, which is specifically designed for privacy-preserving logistic regression while remaining equally effective in plaintext optimization. By incorporating this quadratic gradient, we enhance Nesterov's Accelerated Gradient (NAG), Adaptive Gradient (AdaGrad), and Adam algorithms. We evaluate these enhanced algorithms across various datasets, with experimental results demonstrating state-of-the-art convergence rates that significantly outperform traditional first-order gradient methods. Furthermore, we apply the enhanced NAG method to implement homomorphic logistic regression training, achieving comparable performance within only four iterations. The proposed quadratic-gradient approach offers a unified framework that synergizes the advantages of first-order gradient methods and second-order Newton-type methods, suggesting broad applicability to diverse numerical optimization tasks.

John Chiang

Logistic RegressionGradient DescentPrivacy-Preserving MLAdaptive Gradient MethodsAccelerated Gradient Methods
AskPDF