Robust accelerated gradient methods for smooth strongly convex functions
From MaRDI portal
Abstract: We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent (GD) and accelerated gradient (AG) methods for minimizing strongly convex functions when the gradient has random errors in the form of additive white noise. With gradient errors, the function values of the iterates need not converge to the optimal value; hence, we define the robustness of an algorithm to noise as the asymptotic expected suboptimality of the iterate sequence to input noise power. For this robustness measure, we provide exact expressions for the quadratic case using tools from robust control theory and tight upper bounds for the smooth strongly convex case using Lyapunov functions certified through matrix inequalities. We use these characterizations within an optimization problem which selects parameters of each algorithm to achieve a particular trade-off between rate and robustness. Our results show that AG can achieve acceleration while being more robust to random gradient errors. This behavior is quite different than previously reported in the deterministic gradient noise setting. We also establish some connections between the robustness of an algorithm and how quickly it can converge back to the optimal solution if it is perturbed from the optimal point with deterministic noise. Our framework also leads to practical algorithms that can perform better than other state-of-the-art methods in the presence of random gradient noise.
Recommendations
- A frequency-domain analysis of inexact gradient methods
- An optimal gradient method for smooth strongly convex minimization
- Accelerated extra-gradient descent: a novel accelerated first-order method
- Gradient Convergence in Gradient methods with Errors
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
Cites work
- A Stochastic Approximation Method
- Acceleration of Stochastic Approximation by Averaging
- Adaptive restart for accelerated gradient schemes
- An optimal method for stochastic composite optimization
- Analysis and design of optimization algorithms via integral quadratic constraints
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- Couplings and quantitative contraction rates for Langevin dynamics
- First-order methods of smooth convex optimization with inexact oracle
- scientific article; zbMATH DE number 1001726 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Parameter-dependent Lyapunov functions and the discrete-time Popov criterion for robust analysis
- Polynomial Roots from Companion Matrix Eigenvalues
- Smooth Optimization with Approximate Gradient
- Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
- The risk-sensitive index and the \(H_ 2\) and \(H_ \infty\) norms for nonlinear systems
- The robust H/sub 2/ control problem: a worst-case design
Cited in
(21)- Bounds for the tracking error of first-order online optimization methods
- On strongly quasiconvex functions: existence results and proximal point algorithms
- A frequency-domain analysis of inexact gradient methods
- Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
- A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives
- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
- Relaxed-inertial proximal point type algorithms for quasiconvex minimization
- Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
- scientific article; zbMATH DE number 7370566 (Why is no real title available?)
- Robustness of Accelerated First-Order Algorithms for Strongly Convex Optimization Problems
- Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach
- scientific article; zbMATH DE number 7626754 (Why is no real title available?)
- Differentially Private Accelerated Optimization Algorithms
- Scheduled restart momentum for accelerated stochastic gradient descent
- Optimal convergence rates for convex distributed optimization in networks
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
- Bregman proximal point type algorithms for quasiconvex minimization
- Entropic risk-averse generalized momentum methods
- Accelerated gradient methods with biased gradient estimates: risk sensitivity, high-probability guarantees, and large deviation bounds
- On the fast convergence of minibatch heavy ball momentum
- On a family of relaxed gradient descent methods for strictly convex quadratic minimization
This page was built for publication: Robust accelerated gradient methods for smooth strongly convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853717)
