Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization

DOI10.1137/19M1298007zbMATH Open1486.90147arXiv1904.03537MaRDI QIDQ5037570FDOQ5037570

Authors: Mahesh Chandra Mukkamala, Peter Ochs, Thomas Pock, Shoham Sabach 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: Backtracking line-search is an old yet powerful strategy for finding a better step sizes to be used in proximal gradient algorithms. The main principle is to locally find a simple convex upper bound of the objective function, which in turn controls the step size that is used. In case of inertial proximal gradient algorithms, the situation becomes much more difficult and usually leads to very restrictive rules on the extrapolation parameter. In this paper, we show that the extrapolation parameter can be controlled by locally finding also a simple concave lower bound of the objective function. This gives rise to a double convex-concave backtracking procedure which allows for an adaptive choice of both the step size and extrapolation parameters. We apply this procedure to the class of inertial Bregman proximal gradient methods, and prove that any sequence generated by these algorithms converges globally to a critical point of the function at hand. Numerical experiments on a number of challenging non-convex problems in image processing and machine learning were conducted and show the power of combining inertial step and double backtracking strategy in achieving improved performances.

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

Recommendations

• Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
• A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem
• Backtracking strategies for accelerated descent methods with smooth composite objectives
• General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems
• iPiano: inertial proximal algorithm for nonconvex optimization

zbMATH Keywords

global convergenceBregman distancecomposite minimizationinertial methodsproximal gradient algorithmsnon-Euclidean distancesKurdyka-Łojasiewicz propertyconvex-concave backtracking

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Convexity of real functions of several variables, generalizations (26B25) Decomposition methods (49M27) Convex functions and convex programs in convex geometry (52A41)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• iPiano: inertial proximal algorithm for nonconvex optimization
• The elements of statistical learning. Data mining, inference, and prediction
• Phase retrieval via Wirtinger flow: theory and algorithms
• Variational Analysis
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• An iterative row-action method for interval convex programming
• Clarke Subgradients of Stratifiable Functions
• Title not available (Why is that?)
• Proximité et dualité dans un espace hilbertien
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Title not available (Why is that?)
• Analysis of the Recovery of Edges in Images and Signals by Minimizing Nonconvex Regularized Least-Squares
• On gradients of functions definable in o-minimal structures
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Proximal minimization algorithm with \(D\)-functions
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• Some methods of speeding up the convergence of iteration methods
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems
• First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
• Local convergence of the heavy-ball method and iPiano for non-convex optimization
• A simplified view of first order methods for optimization
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
• Non-smooth non-convex Bregman minimization: unification and new algorithms
• Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
• Variational phase retrieval with globally convergent preconditioned proximal algorithm

Cited In (23)

• Bregman proximal gradient algorithms for deep matrix factorization
• Block Bregman majorization minimization with extrapolation
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• The backtrack Hölder gradient method with application to min-max and min-min problems
• New Bregman proximal type algoritms for solving DC optimization problems
• A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems
• A stochastic two-step inertial Bregman proximal alternating linearized minimization algorithm for nonconvex and nonsmooth problems
• A refined inertial DC algorithm for DC programming
• A nonmonotone accelerated proximal gradient method with variable stepsize strategy for nonsmooth and nonconvex minimization problems
• Provable Phase Retrieval with Mirror Descent
• Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
• Backtracking strategies for accelerated descent methods with smooth composite objectives
• Optimal complexity and certification of Bregman first-order methods
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Global convergence of model function based Bregman proximal minimization algorithms
• Bregman proximal point type algorithms for quasiconvex minimization
• Convergence Analysis for Bregman Iterations in Minimizing a Class of Landau Free Energy Functionals
• A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging
• An alternating structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant
• A Bregman stochastic method for nonconvex nonsmooth problem beyond global Lipschitz gradient continuity
• Stochastic composition optimization of functions without Lipschitz continuous gradient
• Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity
• Learning consistent discretizations of the total variation

Uses Software

• iPiano
• ElemStatLearn
• Wirtinger Flow

This page was built for publication: Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization

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