Gradient Convergence in Gradient methods with Errors

2000/01/01 by Dimitri P. Bertsekas, John N. Tsitsiklis · 458 citations
Computer Science · Economics, Econometrics and Finance · Mathematics · #Combinatorics #Function (biology) #Gradient descent #Lipschitz continuity #Mathematical analysis #Mathematics #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques #Stochastic processes and financial applications

paper · doi:10.1137/s1052623497331063

published in SIAM Journal on Optimization 10(3), 627-642 (Society for Industrial and Applied Mathematics)

openalex publication_date 2000/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

We consider the gradient method x_t+1=x_t+\g_t(s_t+w_t), where s_t is a descent direction of a function f:\rn→\re and w_t is a deterministic or stochastic error. We assume that \gr f is Lipschitz continuous, that the stepsize \g_t diminishes to 0, and that s_t and w_t satisfy standard conditions. We show that either f(x_t)→-∞ or f(x_t) converges to a finite value and \gr f(x_t)→0 (with probability 1 in the stochastic case), and in doing so, we remove various boundedness conditions that are assumed in existing results, such as boundedness from below of f, boundedness of \gr f(x_t), or boundedness of xt.

Cited by

• Backtracking Gradient Descent Method and Some Applications in Large Scale Optimisation. Part 2: Algorithms and Experiments
• Numerical approximation of McKean-Vlasov SDEs via stochastic gradient descent
• Stochastic Successive Convex Approximation for General Stochastic Optimization Problems
• Improving the Variational Quantum Eigensolver Using Variational Adiabatic Quantum Computing
• Block layer decomposition schemes for training deep neural networks
• A Parallel Decomposition Method for Nonconvex Stochastic Multi-Agent Optimization Problems
• Towards Weaker Variance Assumptions for Stochastic Optimization
• Backtracking line search [wikipedia]