Critical Slowing Down Near Topological Transitions in Rate-Distortion Problems I

In Rate Distortion (RD) problems one seeks reduced representations of a source that meet a target distortion constraint. Such optimal representations undergo topological transitions at some critical rate values, when their cardinality or dimensionality change. We study the convergence time of the Arimoto-Blahut alternating projection algorithms, used to solve such problems, near those critical points, both for the Rate Distortion and Information Bottleneck settings. We argue that they suffer from Critical Slowing Down -- a diverging number of iterations for convergence -- near the critical points. This phenomenon can have theoretical and practical implications for both Machine Learning and Data Compression problems.