Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems

Abstract

This paper analyzes block-coordinate proximal gradient methods for minimizing the sum of a separable smooth function and a (nonseparable) nonsmooth function, both of which are allowed to be nonconvex. The main tool in our analysis is the forward-backward envelope (FBE), which serves as a particularly suitable continuous and real-valued Lyapunov function. Global and linear convergence results are established when the cost function satisfies the Kurdyka-Łojasiewicz property without imposing convexity requirements on the smooth function. Two prominent special cases of the investigated setting are regularized finite sum minimization and the sharing problem; in particular, an immediate byproduct of our analysis leads to novel convergence results and rates for the popular Finito/MISO algorithm in the nonsmooth and nonconvex setting with very general sampling strategies. This paper analyzes block-coordinate proximal gradient methods for minimizing the sum of a separable smooth function and a (nonseparable) nonsmooth function, both of which are allowed to be nonconvex. The main tool in our analysis is the forward-backward envelope (FBE), which serves as a particularly suitable continuous and real-valued Lyapunov function. Global and linear convergence results are established when the cost function satisfies the Kurdyka-Łojasiewicz property without imposing convexity requirements on the smooth function. Two prominent special cases of the investigated setting are regularized finite sum minimization and the sharing problem; in particular, an immediate byproduct of our analysis leads to novel convergence results and rates for the popular Finito/MISO algorithm in the nonsmooth and nonconvex setting with very general sampling strategies.

References in corpus (13)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Stochastic Variance Reduction for Nonconvex Optimization
• Splitting methods with variable metric for KL functions
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• SEGA: Variance Reduction via Gradient Sketching
• On the acceleration of forward-backward splitting via an inexact Newton method
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• MISO is Making a Comeback With Better Proofs and Rates

Cited by in corpus (6)

• 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
• Random coordinate descent methods for nonseparable composite optimization
• Coordinate projected gradient descent minimization and its application to orthogonal nonnegative matrix factorization
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Efficiency of stochastic coordinate proximal gradient methods on nonseparable composite optimization