Efficient and Provably Convergent Computation of Information Bottleneck: A Semi-Relaxed Approach
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913304788598784 |
|---|---|
| author | Chen, Lingyi Wu, Shitong Ye, Jiachuan Wu, Huihui Zhang, Wenyi Wu, Hao |
| author_facet | Chen, Lingyi Wu, Shitong Ye, Jiachuan Wu, Huihui Zhang, Wenyi Wu, Hao |
| contents | Information Bottleneck (IB) is a technique to extract information about one target random variable through another relevant random variable. This technique has garnered significant interest due to its broad applications in information theory and deep learning. Hence, there is a strong motivation to develop efficient numerical methods with high precision and theoretical convergence guarantees. In this paper, we propose a semi-relaxed IB model, where the Markov chain and transition probability condition are relaxed from the relevance-compression function. Based on the proposed model, we develop an algorithm, which recovers the relaxed constraints and involves only closed-form iterations. Specifically, the algorithm is obtained by analyzing the Lagrangian of the relaxed model with alternating minimization in each direction. The convergence property of the proposed algorithm is theoretically guaranteed through descent estimation and Pinsker's inequality. Numerical experiments across classical and discrete distributions corroborate the analysis. Moreover, our proposed algorithm demonstrates notable advantages in terms of computational efficiency, evidenced by significantly reduced run times compared to existing methods with comparable accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04862 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient and Provably Convergent Computation of Information Bottleneck: A Semi-Relaxed Approach Chen, Lingyi Wu, Shitong Ye, Jiachuan Wu, Huihui Zhang, Wenyi Wu, Hao Information Theory Information Bottleneck (IB) is a technique to extract information about one target random variable through another relevant random variable. This technique has garnered significant interest due to its broad applications in information theory and deep learning. Hence, there is a strong motivation to develop efficient numerical methods with high precision and theoretical convergence guarantees. In this paper, we propose a semi-relaxed IB model, where the Markov chain and transition probability condition are relaxed from the relevance-compression function. Based on the proposed model, we develop an algorithm, which recovers the relaxed constraints and involves only closed-form iterations. Specifically, the algorithm is obtained by analyzing the Lagrangian of the relaxed model with alternating minimization in each direction. The convergence property of the proposed algorithm is theoretically guaranteed through descent estimation and Pinsker's inequality. Numerical experiments across classical and discrete distributions corroborate the analysis. Moreover, our proposed algorithm demonstrates notable advantages in terms of computational efficiency, evidenced by significantly reduced run times compared to existing methods with comparable accuracy. |
| title | Efficient and Provably Convergent Computation of Information Bottleneck: A Semi-Relaxed Approach |
| topic | Information Theory |
| url | https://arxiv.org/abs/2404.04862 |