A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima

Abstract

We introduce Bella, a locally superlinearly convergent Bregman forward backward splitting method for minimizing the sum of two nonconvex functions, one of which satisfying a relative smoothness condition and the other one possibly nonsmooth. A key tool of our methodology is the Bregman forward-backward envelope (BFBE), an exact and continuous penalty function with favorable first- and second-order properties, and enjoying a nonlinear error bound when the objective function satisfies a Lojasiewicz-type property. The proposed algorithm is of linesearch type over the BFBE along candidate update directions, and converges subsequentially to stationary points, globally under a KL condition, and owing to the given nonlinear error bound can attain superlinear convergence rates even when the limit point is a nonisolated minimum, provided the directions are suitably selected.

References in corpus (13)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• A Geometric Analysis of Phase Retrieval
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Variable metric inexact line-search based methods for nonsmooth optimization
• Regularizing with Bregman-Moreau envelopes
• SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators
• Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
• On the acceleration of forward-backward splitting via an inexact Newton method
• Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms
• Stochastic model-based minimization under high-order growth
• Accelerated first-order methods for large-scale convex minimization

Cited by in corpus (11)

• Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC
• Block Alternating Bregman Majorization Minimization with Extrapolation
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization
• Dualities for non-Euclidean smoothness and strong convexity under the light of generalized conjugacy
• High-order methods beyond the classical complexity bounds, I: inexact high-order proximal-point methods
• High-order methods beyond the classical complexity bounds, II: inexact high-order proximal-point methods with segment search
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• An interior proximal gradient method for nonconvex optimization
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness