Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models
Authors: Valentin Durante, George Katsirelos, Thomas Schiex
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches. 3. Experiments 3.2. Experiments on random instances 3.3. Experiments on a real instance |
| Researcher Affiliation | Academia | 1Universit e F ed erale de Toulouse, ANITI, INRAE, UR 875, 31326 Toulouse, France 2MIA-Paris-Math ematiques et Informatique Appliqu ees, INRAE, 75231 Paris, France. |
| Pseudocode | No | The paper describes the algorithms in detail, but it does not include formally labeled pseudocode or algorithm blocks. |
| Open Source Code | Yes | We implemented the row-by-row updates with the dualized exactly-one constraints (LR-LAS) as well as the BCD update method (LR-BCD) in C++ (code available at github.com/Val Durante/LR-BCD) with the Eigen3 (Guennebaud et al., 2010) sparse matrix library (MPL2 licence). |
| Open Datasets | Yes | This instance has been made available in the Cost Function Library, in the real/fish category. |
| Dataset Splits | No | The paper does not specify distinct training, validation, and test splits with percentages or counts for the datasets used. It describes how random instances were generated and uses a single real-world instance. |
| Hardware Specification | Yes | All experiments were run on a single thread on a server equipped with a Xeon Gold 6248R CPU@3.00GHz and 1TB of RAM running Debian Linux 4.19.98-1. |
| Software Dependencies | Yes | We implemented the row-by-row updates with the dualized exactly-one constraints (LR-LAS) as well as the BCD update method (LR-BCD) in C++ (code available at github.com/Val Durante/LR-BCD) with the Eigen3 (Guennebaud et al., 2010) sparse matrix library (MPL2 licence). We use rank r = p 2(d + 1) by default for LR-LAS and r = p 2(n + d + 1) for LR-BCD but also tried variants with fixed lower ranks. The penalty coefficient ρ is set as the sum of the maximum of all the binary and unary functions. Thus, it enforces the theoretical assumption of the Lasserre dualization result. They are compared with exact LP (local polytope) bounds and message passing MAP/MRF algorithms Min-Sum and TRW-S. The LP bounds are computed using CPLEX 20.1.0.0. We used Open-GM2 (Kappes et al., 2015), an efficient C++ MIT-licensed library, in release 3.3.7, available at https://github.com/opengm for Min-Sum (maximum number of iterations of 100, minimal message distance of 0.01 and damping of 0.8) and TRW-S (maximum number of iterations 100, 000, tolerance of 10 5, TABLE mode). |
| Experiment Setup | Yes | We use rank r = p 2(d + 1) by default for LR-LAS and r = p 2(n + d + 1) for LR-BCD but also tried variants with fixed lower ranks. The penalty coefficient ρ is set as the sum of the maximum of all the binary and unary functions. Thus, it enforces the theoretical assumption of the Lasserre dualization result. ... for Min-Sum (maximum number of iterations of 100, minimal message distance of 0.01 and damping of 0.8) and TRW-S (maximum number of iterations 100, 000, tolerance of 10 5, TABLE mode). |