1. Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- Author
-
Puya Latafat, Panagiotis Patrinos, and Andreas Themelis
- Subjects
Lyapunov function ,Mathematical optimization ,General Mathematics ,0211 other engineering and technologies ,010103 numerical & computational mathematics ,02 engineering and technology ,90C06, 90C25, 90C26, 49J52, 49J53 ,01 natural sciences ,Convexity ,Separable space ,symbols.namesake ,Convergence (routing) ,FOS: Mathematics ,Nonsmooth nonconvex optimization ,0101 mathematics ,Mathematics - Optimization and Control ,Mathematics ,021103 operations research ,Block-coordinate updates ,Function (mathematics) ,Rate of convergence ,Optimization and Control (math.OC) ,KL inequality ,symbols ,Proximal Gradient Methods ,Minification ,Forward-backward envelope ,Software - 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-\L 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-\L 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.
- Published
- 2021