Gradient Descent

Follow this topic Ask about this topic

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

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

Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity
Mar 31, 2026Zhenxuan Li, Meng HuangGradient Descent
Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraints
Mar 24, 2026Shengping Xie, Zekun Wu, Quan Chen +1Implicit Bias Gradient Descent
School of Mathematical Sciences, Peking University
Optimizing Multi-Agent Weather Captioning via Text Gradient Descent: A Training-Free Approach with Consensus-Aware Gradient Fusion
Mar 23, 2026Shixu LiuMulti-Agent LLM Systems Gradient Descent
School of Computer & Information Technology, Northeast Petroleum University, No. 99 Xuefu Street, Ranghulu District, Daqing, Heilongjiang, 163318, P.R. China
A Generalised Exponentiated Gradient Approach to Enhance Fairness in Binary and Multi-class Classification Tasks
Mar 22, 2026Maryam Boubekraoui, Giordano d'Aloisio, Antinisca Di MarcoGradient Descent Algorithmic Fairness
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
Auto-Unrolled Proximal Gradient Descent: An AutoML Approach to Interpretable Waveform Optimization
Mar 18, 2026Ahmet KaplanDeep Unfolding Wireless Communications
Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime
Mar 11, 2026Reza Ghane, Danil Akhtiamov, Babak HassibiGradient Descent Implicit Bias
Electrical Engineering Department, California Institute of Technology, Pasadena, CA 91125 USA · Computing + Mathematical Sciences Department, California Institute of Technology, Pasadena, CA 91125 USA
Omni-Masked Gradient Descent: Memory-Efficient Optimization via Mask Traversal with Improved Convergence
Mar 6, 2026Hui Yang, Tao Ren, Jinyang Jiang +2Gradient Descent Memory-Efficient Training
1Guanghua School of Management, Peking University · 2Wangxuan Institute of Computer Technology, Peking University.
How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?
Mar 5, 2026Kuo-Wei Lai, Guanghui Wang, Molei Tao +1High-Dimensional Linear Regression Random Feature Methods
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
Exploiting Subgradient Sparsity in Max-Plus Neural Networks
Mar 4, 2026Ikhlas Enaieh, Olivier FercoqNeural Network Optimization Gradient Descent
LTCI, S2A · Image, Data, Signal Department (IDS), Telecom Paris, Institut Polytechnique de Paris, France. · S2A, LTCI
Beyond Cross-Validation: Adaptive Parameter Selection for Kernel-Based Gradient Descents
Mar 3, 2026Xiaotong Liu, Yunwen Lei, Xiangyu Chang +1Kernel Methods Hyperparameter Optimization
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
The power of small initialization in noisy low-tubal-rank tensor recovery
Mar 3, 2026ZHiyu Liu, Haobo Geng, Xudong Wang +3Overparameterization Gradient Descent
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
Never Saddle for Reparameterized Steepest Descent as Mirror Flow
Mar 2, 2026Tom Jacobs, Chao Zhou, Rebekka BurkholzNeural Network Training Dynamics Gradient Descent Dynamics
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Training Dynamics of Softmax Self-Attention: Fast Global Convergence via Preconditioning
Mar 2, 2026Gautam Goel, Mahdi Soltanolkotabi, Peter BartlettSelf-Attention Softmax Attention
Simons Institute, UC Berkeley · Department of Electrical and Computer Engineering, University of Southern California
Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression
Feb 21, 2026Sacchit Kale, Piyushi Manupriya, Pierre Marion +2Gradient Descent Stochastic Optimization Convergence
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.
The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks
Feb 18, 2026Eitan Gronich, Gal VardiGradient Descent Adaptive Gradient Methods
Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel
Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities
Jan 30, 2026Yungi Jeong, Takumi OtsukaNonconvex Stochastic Optimization Stochastic Optimization Convergence
Department of Mathematics, National University of Singapore · Department of Computer Science and Communication Engineering, Waseda University
Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval
Jan 30, 2026Guillaume Braun, Han Bao, Wei Huang +1Gradient Descent Gradient Descent Dynamics
RIKEN AIP · The Institute of Statistical Mathematics · Tohoku University +2
Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis
Dec 31, 2025Seunghoon Paik, Kangjie Zhou, Matus Telgarsky +1Early Stopping Gradient Descent
University of California, Berkeley · Columbia University · New York University
Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance
Nov 30, 2025Robin Yadav, Shuo Xie, Tianhao Wang +1Sign-Based Optimization Class-Imbalanced Learning
Toyota Technological Institute at Chicago · University of British Columbia · University of California, San Diego
A Byzantine-Robust Federated Learning with Nesterov Momentum
Nov 4, 2025Lihan Xu, Xiaoyi Fan, Gang Wang +3Federated Learning Aggregation Byzantine-Robust Federated Learning
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.
Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?
Jul 15, 2025Si Yi Meng, Baptiste Goujaud, Antonio Orvieto +1Logistic Regression Gradient Descent
Inria Paris, Paris, France · Inria Saclay, Palaiseau, France · ELLIS Institute Tübingen; MPI for Intelligent Systems; Tübingen AI Center, Germany +1
When majority rules, minority loses: bias amplification of gradient descent
May 19, 2025François Bachoc, Jérôme Bolte, Ryan Boustany +1Class-Imbalanced Learning Gradient Descent
LPP · University of Lille · Institut Universitaire de France (IUF) +6
Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra
May 16, 2025Ivan Bioli, Carlo Marcati, Giancarlo SangalliNeural PDE Solvers Gradient Descent
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
The Utility and Complexity of in- and out-of-Distribution Machine Unlearning
Dec 12, 2024Youssef Allouah, Joshua Kazdan, Rachid Guerraoui +1Machine Unlearning Gradient Descent
EPFL, Switzerland · Stanford University, USA
Convergence Rate Analysis of LION
Nov 12, 2024Yiming Dong, Huan Li, Zhouchen LinSign-Based Optimization Deep Learning Optimization
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
Jacobian Descent for Multi-Objective Optimization
Jun 23, 2024Pierre Quinton, Valérian ReyMulti-Objective Optimization Pareto Optimization
Independent
Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
Jun 7, 2024Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao +1Dynamical Systems Logistic Regression
Department of Computer Science Cornell University Ithaca, NY, USA · ELLIS Institute Tübingen MPI for Intelligent Systems Tübingen AI Center, Germany
Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant
Jan 26, 2022John ChiangLogistic Regression Gradient Descent

Mar 31, 2026J/K move · Enter open · S save

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

Zhenxuan Li, Meng Huang

Gradient Descent

Open paper AskPDF arXiv

The low-rank matrix recovery problem seeks to reconstruct an unknown

n_1 \times n_2

rank-

r

matrix from

m

linear measurements, where

m\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((n_1 + n_2)r^2)

and an iteration complexity of

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/ε))

. Nonetheless, its sample complexity remains sub-optimal at

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((n_1 + n_2)r)

, but converges more slowly with an iteration complexity

O(κ^2 \log(1/ε))

. In this paper, through a more refined analysis, we show that ScaledGD achieves both the optimal sample complexity

O((n_1 + n_2)r)

and the improved iteration complexity

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.