| Paper ID | D6-S3-T2.2 |
| Paper Title |
Critical Slowing Down Near Topological Transitions in Rate-Distortion Problems |
| Authors |
Shlomi Agmon, Etam Benger, Or Ordentlich, Naftali Tishby, The Hebrew University of Jerusalem, Israel |
| Session |
D6-S3-T2: Rate-Distortion Theory I |
| Chaired Session: |
Monday, 19 July, 22:40 - 23:00 |
| Engagement Session: |
Monday, 19 July, 23:00 - 23:20 |
| Abstract |
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.
|
