Minimum-Entropy Coupling Approximation Guarantees Beyond the Majorization Barrier
Minimum-Entropy Coupling Approximation Guarantees Beyond the Majorization Barrier
复制标题
DOI：
10.48550/arxiv.2302.11838
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Spencer Compton;Dmitriy A. Katz;Benjamin Qi;K. Greenewald;Murat Kocaoglu
中科院分区：
文献类型：
--
作者：
Spencer Compton;Dmitriy A. Katz;Benjamin Qi;K. Greenewald;Murat Kocaoglu
给定一组离散概率分布，最小熵耦合是以输入分布作为其边缘的最小熵联合分布。这与诸如用于因果图发现的熵因果推理和我们分别观察的变量之间的边界互信息等任务直接相关。由于寻找最小熵耦合是NP-Hard，各种工作已经研究了近似算法。[Compton，ISIT 2022]的工作表明，[Kocaoglu等人，AAAI 2017]总是在最佳耦合的$log_2（e）\约1.44$位内。此外，他们表明，这是不可能的，以获得更好的近似保证使用的优势下界，所有以前的作品已经使用：从而建立一个优势障碍。在这项工作中，我们通过设计一个更强的下限，我们称之为配置文件方法，打破了优化障碍。使用这种配置文件方法，我们能够证明贪婪算法总是在$log_2（e）/e \approximately 0.53$ bits内耦合两个分布（以前的最佳已知界限在1位内），并且在$（1 + log_2（e））/2 \approximately 1.22$ bits内耦合任何数量的分布（以前的最佳已知界限在1.44位内）。我们还研究了最小熵耦合问题的推广：凹最小成本耦合。我们能够获得类似的保证，这种推广的凹成本函数。此外，我们在[Kovaevi 'c et al.，信息计算2015]关于最小熵耦合问题的NP成员资格，通过表明任何超过NP的最小熵耦合的难度来自于复杂性类NP中计算算术的难度。最后，我们提出了指数时间算法计算的最优解。
Given a set of discrete probability distributions, the minimum entropy coupling is the minimum entropy joint distribution that has the input distributions as its marginals. This has immediate relevance to tasks such as entropic causal inference for causal graph discovery and bounding mutual information between variables that we observe separately. Since finding the minimum entropy coupling is NP-Hard, various works have studied approximation algorithms. The work of [Compton, ISIT 2022] shows that the greedy coupling algorithm of [Kocaoglu et al., AAAI 2017] is always within $log_2(e) \approx 1.44$ bits of the optimal coupling. Moreover, they show that it is impossible to obtain a better approximation guarantee using the majorization lower-bound that all prior works have used: thus establishing a majorization barrier. In this work, we break the majorization barrier by designing a stronger lower-bound that we call the profile method. Using this profile method, we are able to show that the greedy algorithm is always within $log_2(e)/e \approx 0.53$ bits of optimal for coupling two distributions (previous best-known bound is within 1 bit), and within $(1 + log_2(e))/2 \approx 1.22$ bits for coupling any number of distributions (previous best-known bound is within 1.44 bits). We also examine a generalization of the minimum entropy coupling problem: Concave Minimum-Cost Couplings. We are able to obtain similar guarantees for this generalization in terms of the concave cost function. Additionally, we make progress on the open problem of [Kova\v{c}evi\'c et al., Inf. Comput. 2015] regarding NP membership of the minimum entropy coupling problem by showing that any hardness of minimum entropy coupling beyond NP comes from the difficulty of computing arithmetic in the complexity class NP. Finally, we present exponential-time algorithms for computing the exactly optimal solution.