The Randomized Block Coordinate Descent Method in the Hölder Smooth Setting

2024/03/12 by Leandro Farias Maia, Maia, Leandro Farias, David H. Gutman +1
Computer Science · #FOS: Mathematics #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2403.08080

openalex publication_date 2024/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This work provides the first convergence analysis for the Randomized Block Coordinate Descent method for minimizing a function that is both Hölder smooth and block Hölder smooth. Our analysis applies to objective functions that are non-convex, convex, and strongly convex. For non-convex functions, we show that the expected gradient norm reduces at an O(k^\fracγ1+γ) rate, where k is the iteration count and γ is the Hölder exponent. For convex functions, we show that the expected suboptimality gap reduces at the rate O(k^-γ). In the strongly convex setting, we show this rate for the expected suboptimality gap improves to O(k^{-(2γ)/(1-γ)}) when γ>1 and to a linear rate when γ=1. Notably, these new convergence rates coincide with those furnished in the existing literature for the Lipschitz smooth setting.

Related

• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• Robust Block Coordinate Descent
• Block Coordinate Descent Only Converge to Minimizers
• First-order algorithms converge faster than O(1/k) on convex problems
• On the global convergence of randomized coordinate gradient descent for non-convex optimization