New analysis of linear convergence of gradient-type methods via unifying error bound conditions

DOI10.1007/S10107-018-01360-1zbMATH Open1435.90111arXiv1606.00269OpenAlexW2963154066WikidataQ128687537 ScholiaQ128687537MaRDI QIDQ2297652FDOQ2297652

Hui Zhang

Publication date: 20 February 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: This paper reveals that a common and central role, played in many error bound (EB) conditions and a variety of gradient-type methods, is a residual measure operator. On one hand, by linking this operator with other optimality measures, we define a group of abstract EB conditions, and then analyze the interplay between them; on the other hand, by using this operator as an ascent direction, we propose an abstract gradient-type method, and then derive EB conditions that are necessary and sufficient for its linear convergence. The former provides a unified framework that not only allows us to find new connections between many existing EB conditions, but also paves a way to construct new EB conditions. The latter allows us to claim the weakest conditions guaranteeing linear convergence for a number of fundamental algorithms, including the gradient method, the proximal point algorithm, and the forward-backward splitting algorithm. In addition, we show linear convergence for the proximal alternating linearized minimization algorithm under a group of equivalent EB conditions, which are strictly weaker than the traditional strongly convex condition. Moreover, by defining a new EB condition, we show Q-linear convergence of Nesterov's accelerated forward-backward algorithm without strong convexity. Finally, we verify EB conditions for a class of dual objective functions.

Full work available at URL: https://arxiv.org/abs/1606.00269

zbMATH Keywords

error boundproximal point algorithmforward-backward splitting algorithmlinear convergencegradient descentproximal alternating linearized minimizationNesterov's accelerationdual objective functionresidual measure operator

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Numerical methods involving duality (49M29)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Variational Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• Introductory lectures on convex optimization. A basic course.
• Convex Analysis
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Title not available (Why is that?)
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• Implicit Functions and Solution Mappings
• Some continuity properties of polyhedral multifunctions
• Title not available (Why is that?)
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Title not available (Why is that?)
• On the rate of convergence of the proximal alternating linearized minimization algorithm for convex problems
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Asymptotic Convergence Analysis of the Proximal Point Algorithm
• Error bounds and convergence analysis of feasible descent methods: A general approach
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• Performance of first-order methods for smooth convex minimization: a novel approach
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• Optimized first-order methods for smooth convex minimization
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods
• Asymptotic convergence of nonlinear contraction semigroups in Hilbert space
• Second-order growth, tilt stability, and metric regularity of the subdifferential
• Metric subregularity of the convex subdifferential in Banach spaces
• An introduction to continuous optimization for imaging
• A proximal-gradient homotopy method for the sparse least-squares problem
• Iteration complexity analysis of block coordinate descent methods
• From error bounds to the complexity of first-order descent methods for convex functions
• Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
• Linear convergence of first order methods for non-strongly convex optimization
• Augmented \(\ell_1\) and nuclear-norm models with a globally linearly convergent algorithm
• Title not available (Why is that?)
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
• The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth
• On the Convergence of a Regularized Jacobi Algorithm for Convex Optimization
• Projected shrinkage algorithm for box-constrained \(\ell _1\)-minimization
• Title not available (Why is that?)
• A unified approach to error bounds for structured convex optimization problems
• A dual algorithm for a class of augmented convex signal recovery models
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
• On equiwellset minimum problems
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
• Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
• On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
• Convergence Rates of Inertial Forward-Backward Algorithms
• Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
• On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
• Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences

Cited In (10)

• Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
• Conditions for linear convergence of the gradient method for non-convex optimization
• Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence Under Bregman Distance Growth Conditions
• Revisiting linearized Bregman iterations under Lipschitz-like convexity condition
• Randomized smoothing variance reduction method for large-scale non-smooth convex optimization
• Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition
• Scaled relative graphs: nonexpansive operators via 2D Euclidean geometry
• Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method
• Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
• Inertial proximal incremental aggregated gradient method with linear convergence guarantees

Uses Software

• PESTO

This page was built for publication: New analysis of linear convergence of gradient-type methods via unifying error bound conditions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297652)