Block Coordinate Descent Only Converge to Minimizers

2017/10/25 by Enbin Song, Song, Enbin, Zhubin Shen +3
Computer Science · Engineering · Medicine · #Bone and Joint Diseases #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1710.09047

openalex publication_date 2017/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a non-convex twice continuously differentiable cost function with Lipschitz continuous gradient, we prove that all of block coordinate gradient descent, block mirror descent and proximal block coordinate descent converge to a local minimizer, almost surely with random initialization. Furthermore, we show that these results also hold true even for the cost functions with non-isolated critical points.

Citations

• Gradient Descent Converges to Minimizers
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Related

• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• First-order algorithms converge faster than O(1/k) on convex problems
• The Randomized Block Coordinate Descent Method in the Hölder Smooth Setting
• On the global convergence of randomized coordinate gradient descent for non-convex optimization
• Markov Chain Block Coordinate Descent