Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method
From MaRDI portal
Publication:2046546
Abstract: In this work, we develop a level-set subdifferential error bound condition aiming towards convergence rate analysis of a variable Bregman proximal gradient (VBPG) method for a broad class of nonsmooth and nonconvex optimization problems. It is proved that the aforementioned condition guarantees linear convergence of VBPG, and is weaker than Kurdyka-Lojasiewicz property, weak metric subregularity and Bregman proximal error bound. Along the way, we are able to derive a number of verifiable conditions for level-set subdifferential error bounds to hold, and necessary conditions and sufficient conditions for linear convergence relative to a level set for nonsmooth and nonconvex optimization problems. The newly established results not only enable us to show that any accumulation point of the sequence generated by VBPG is at least a critical point of the limiting subdifferential or even acritical point of the proximal subdifferential with a fixed Bregman function in each iteration, but also provide a fresh perspective that allows us to explore inner-connections among many known sufficient conditions for linear convergence of various first-order methods.
Recommendations
- Error bounds, quadratic growth, and linear convergence of proximal methods
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- scientific article; zbMATH DE number 7404502
- Linear convergence of prox-SVRG method for separable non-smooth convex optimization problems under bounded metric subregularity
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
Cites work
- A coordinate gradient descent method for nonsmooth separable minimization
- A unified approach for minimizing composite norms
- An extended descent framework for variational inequalities
- Auxiliary problem principle and decomposition of optimization problems
- Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Compressed sensing
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Decoding by Linear Programming
- Decomposition coordination in deterministic and stochastic optimization
- Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
- Error bounds in mathematical programming
- Error bounds, quadratic growth, and linear convergence of proximal methods
- From error bounds to the complexity of first-order descent methods for convex functions
- Group sparse optimization via \(\ell_{p,q}\) regularization
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 3313108 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Hölder error bounds and Hölder calmness with applications to convex semi-infinite optimization
- Implicit Functions and Solution Mappings
- Introductory lectures on convex optimization. A basic course.
- Linear convergence of first order methods for non-strongly convex optimization
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- On the Convergence of a Regularized Jacobi Algorithm for Convex Optimization
- Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Strongly Regular Generalized Equations
- Subsmooth sets: Functional characterizations and related concepts
- Uniform prox-regularity of functions and epigraphs in Hilbert spaces
- Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
- Variable metric inexact line-search-based methods for nonsmooth optimization
- Variational Analysis
- Weak sharp minima revisited. I: Basic theory
Cited in
(7)- Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- The equivalence of three types of error bounds for weakly and approximately convex functions
- The level-set subdifferential error bound via Moreau envelopes
- A Bregman proximal subgradient algorithm for nonconvex and nonsmooth fractional optimization problems
- Convergence of a class of algorithms with the level-set subdifferential error bound
- Revisiting subgradient method: complexity and convergence beyond Lipschitz continuity
This page was built for publication: Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046546)
