Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems

Abstract

The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothness condition, which is satisfied by any finite-order polynomial objective function. Further, this work develops new Bregman-divergence based algorithms that are guaranteed to converge to a second-order stationary point for any relatively smooth problem. In addition, the proposed optimization methods cover both the proximal alternating minimization and the proximal alternating linearized minimization when we specialize the Bregman divergence to the Euclidian distance. Therefore, this work not only develops guaranteed optimization methods for non-Lipschitz smooth problems but also solves an open problem of showing the second-order convergence guarantees for these alternating minimization methods.

References in corpus (7)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Global Optimality in Low-rank Matrix Optimization
• The Non-convex Geometry of Low-rank Matrix Optimization
• First-order Methods Almost Always Avoid Saddle Points
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Global Optimality in Distributed Low-rank Matrix Factorization

Cited by in corpus (7)

• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Bregman Proximal Framework for Deep Linear Neural Networks
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• Efficient numerical methods for computing the stationary states of phase field crystal models
• First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approach