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.

arXiv commentin Russian language

References in corpus (53)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Distributed Learning with Compressed Gradient Differences
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Acceleration Methods
• On Biased Compression for Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• SEGA: Variance Reduction via Gradient Sketching
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Recent theoretical advances in decentralized distributed convex optimization
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank
• Mirror Descent for Constrained Optimization Problems with Large Subgradient Values
• The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems
• Stochastic model-based minimization under high-order growth
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods
• Convex optimization in Hilbert space with applications to inverse problems
• Decentralized Optimization Over Slowly Time-Varying Graphs: Algorithms and Lower Bounds
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance
• Optimal and Adaptive Monteiro-Svaiter Acceleration
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• On the Lower Bound of Minimizing Polyak-Łojasiewicz Functions
• Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
• Generalized Polyak Step Size for First Order Optimization with Momentum
• Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction
• Primal-Dual Stochastic Mirror Descent for MDPs
• An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition
• Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
• Gradient-Free Federated Learning Methods with $l_1$ and $l_2$-Randomization for Non-Smooth Convex Stochastic Optimization Problems
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Stochastic Extragradient: General Analysis and Improved Rates
• Exploiting higher-order derivatives in convex optimization methods
• DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule
• 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
• A Parameter-Free Conditional Gradient Method for Composite Minimization under Hölder Condition
• Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
• Intermediate Gradient Methods with Relative Inexactness
• Universal Average-Case Optimality of Polyak Momentum
• An Optimal Algorithm for Strongly Convex Min-min Optimization
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning