English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a set of discrete probability distributions, the minimum entropycoupling is the minimum entropy joint distribution that has the inputdistributions as its marginals. This has immediate relevance to tasks such asentropic causal inference for causal graph discovery and bounding mutualinformation between variables that we observe separately. Since finding theminimum entropy coupling is NP-Hard, various works have studied approximationalgorithms. The work of [Compton, ISIT 2022] shows that the greedy couplingalgorithm of [Kocaoglu et al., AAAI 2017] is always within $log_2(e) \approx1.44$ bits of the optimal coupling. Moreover, they show that it is impossibleto obtain a better approximation guarantee using the majorization lower-boundthat all prior works have used: thus establishing a majorization barrier. Inthis work, we break the majorization barrier by designing a strongerlower-bound that we call the profile method. Using this profile method, we areable to show that the greedy algorithm is always within $log_2(e)/e \approx0.53$ bits of optimal for coupling two distributions (previous best-known boundis within 1 bit), and within $(1 + log_2(e))/2 \approx 1.22$ bits for couplingany number of distributions (previous best-known bound is within 1.44 bits). Wealso examine a generalization of the minimum entropy coupling problem: ConcaveMinimum-Cost Couplings. We are able to obtain similar guarantees for thisgeneralization in terms of the concave cost function. Additionally, we makeprogress 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 thatany hardness of minimum entropy coupling beyond NP comes from the difficulty ofcomputing arithmetic in the complexity class NP. Finally, we presentexponential-time algorithms for computing the exactly optimal solution.

Minimum-Entropy Coupling Approximation Guarantees Beyond the Majorization Barrier