Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-{\L}ojasiewicz Functions

Understand

In this paper we introduce two novel generalizations of the theory for gradient descent type methods in the proximal setting.

• First, we introduce the proportion function, which we further use to analyze all known (and many new) block-selection rules for block coordinate descent methods under a single framework.
• This framework includes randomized methods with uniform, non-uniform or even adaptive sampling strategies, as well as deterministic methods with batch, greedy or cyclic selection rules.
• Second, the theory of strongly-convex optimization was recently generalized to a specific class of non-convex functions satisfying the so-called Polyak-{\L}ojasiewicz condition.