Accelerated Message Passing for Entropy-Regularized MAP Inference
Authors: Jonathan Lee, Aldo Pacchiano, Peter Bartlett, Michael Jordan
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient methods. The proposed algorithms incorporate the familiar steps of standard smooth message passing algorithms, which can be viewed as coordinate minimization steps. We show that these accelerated variants achieve faster rates for finding -optimal points of the unregularized problem, and, when the LP is tight, we prove that the proposed algorithms recover the true MAP solution in fewer iterations than standard message passing algorithms. ... Our goal now is to understand the empirical differences between the above algorithms and also where certain theoretical guarantees can likely be improved, if at all. To this end, we compare the convergence rates of EMP and SMP and their accelerated variants on several synthesized Erd os-Rényi random graphs. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Stanford University, USA 2Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, USA 3Department of Statistics, University of California, Berkeley, USA. Correspondence to: Jonathan Lee <jnl@stanford.edu>, Aldo Pacchiano <pacchiano@berkeley.edu>. |
| Pseudocode | Yes | Algorithm 1 Standard-MP(Update, , P, K), Algorithm 2 Accel-EMP(G, C, , K), Algorithm 3 Accel-SMP(G, C, , K), Algorithm 4 Proj(µ, ) |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository for the methodology described. |
| Open Datasets | No | The paper states: "First, we constructed a graph with n = 100 vertices and then generated edges between each pair of vertices with probability 1.1 log n n . We considered the standard multi-label Potts model with d = 3 labels. The cost vector C was initialized randomly in the following way: Ci(xi) Unif([ 0.01, 0.01]), 8xi 2 χ and Cij(xi, xj) Unif({ 1.0, 1.0}), 8xi, xj 2 χ." This indicates they generated their own data rather than using an existing publicly available dataset with a link or citation. |
| Dataset Splits | No | The paper does not specify any training/test/validation dataset splits, percentages, or absolute sample counts. It describes how the graph was generated and costs were initialized, but not how this data was partitioned for training, validation, or testing. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running its experiments, such as GPU models, CPU types, or memory amounts. |
| Software Dependencies | No | The paper does not list specific software components with their version numbers (e.g., Python 3.8, PyTorch 1.9, CPLEX 12.4). It only mentions using "standard solver in CVXPY" without version details. |
| Experiment Setup | Yes | Each algorithm used = 1000 over 10 trials, measuring means and standard deviations. We computed the ground-truth optimal value of (P) using a standard solver in CVXPY. |