About some works of Boris Polyak on convergence of gradient methods and their development

Abstract

The paper presents a review of the state-of-the-art of subgradient and accelerated methods of convex optimization, including in the presence of disturbances and access to various information about the objective function (function value, gradient, stochastic gradient, higher derivatives). For nonconvex problems, the Polak-Lojasiewicz condition is considered and a review of the main results is given. The behavior of numerical methods in the presence of sharp minima is considered. The purpose of this survey is to show the influence of the works of B.T. Polyak (1935 -- 2023) on gradient optimization methods and their neighborhoods on the modern development of numerical optimization methods.

in Russian language

References in corpus (22)

• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization
• Decentralized Optimization Over Slowly Time-Varying Graphs: Algorithms and Lower Bounds
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance
• On the Lower Bound of Minimizing Polyak-Łojasiewicz Functions
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm
• Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization
• Gradient-Free Federated Learning Methods with $l_1$ and $l_2$-Randomization for Non-Smooth Convex Stochastic Optimization Problems
• Generalized Polyak Step Size for First Order Optimization with Momentum
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
• Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
• DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• An Optimal Algorithm for Strongly Convex Min-min Optimization
• A Parameter-Free Conditional Gradient Method for Composite Minimization under Hölder Condition
• Optimal Algorithm with Complexity Separation for Strongly Convex-Strongly Concave Composite Saddle Point Problems
• Gradient-Type Method for Optimization Problems with Polyak-Lojasiewicz Condition: Relative Inexactness in Gradient and Adaptive Parameters Setting
• Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
• Intermediate Gradient Methods with Relative Inexactness