Dynamic Tree Block Coordinate Ascent

Daniel Tarlow, Dhruv Batra, Pushmeet Kohli, Vladimir KolmogorovICML 2011 · OpenReview

TL;DR

This paper introduces Dynamic Tree-Block Coordinate Ascent (DTBCA), an algorithm that significantly speeds up Maximum A Posteriori (MAP) inference in graphical models by being "energy-aware." Instead of passing messages uniformly across an entire graph, DTBCA dynamically identifies and focuses computation on the specific regions that are furthest from convergence, leading to massive efficiency gains over traditional static-schedule methods.

The Problem: Energy-Oblivious Message Passing

In machine learning and computer vision, probabilistic models like Markov Random Fields (MRFs) are frequently used to find the most likely "labeling" for a set of variables—such as assigning a depth value to every pixel in an image. This process is known as Maximum A Posteriori (MAP) inference.

Because exact MAP inference is NP-hard, researchers rely on Linear Programming (LP) relaxations to find strong approximate solutions. However, standard algorithms for this (like TRW-S or MPLP) are fundamentally "energy-oblivious." They follow a fixed, static schedule, passing messages across the entire graph repeatedly. This approach is highly wasteful: the algorithm spends just as much computational effort on regions of the graph that have already converged as it does on regions that remain highly inconsistent. The authors aim to bridge the gap between these standard message-passing methods and "energy-aware" flow-based methods that naturally focus on problematic areas.

Methods: Dynamic Scheduling

The core contribution of this paper is a strategy for dynamic scheduling. Instead of following a fixed path, the algorithm chooses which "forest" (a collection of trees within the graph) to update at each step based on two novel scoring criteria:

  1. Local Primal-Dual Gap (LPDG): Leveraging duality theory, this measure estimates how much the current solution violates optimal conditions at a specific node or edge. It provides an efficiently computable upper bound on how much the objective function could improve if that specific region were updated.
  2. Weak Tree Agreement (WTA) Score: This is a temporal measure that looks at the history of labels assigned to a node over recent iterations. If a node's "best" label is fluctuating or inconsistent with its neighbors, it receives a higher score.

The DTBCA Algorithm in Action: * At each iteration, the algorithm calculates these scores for "dirty" (recently changed) nodes and edges. * It uses a modified version of Kruskal’s algorithm to greedily select a maximum-weight forest based on these scores. * It then performs a block coordinate ascent update only on that selected forest. * To keep computational overhead low, a caching system ensures that scores are only recomputed for parts of the graph directly affected by the previous update.

Key Insights

  • Work Smarter, Not Harder: The breakthrough insight is that the primal-dual gap—traditionally a global measure of optimization progress—can be localized. By decomposing the gap into per-edge contributions, the algorithm creates a "heat map" of where it is struggling most.
  • Dynamic vs. Static: Static schedules (like "combs" on a grid) are easy to implement but ignore the underlying data. Dynamic schedules allow the algorithm to "zoom in" on complex boundaries or high-energy regions, ignoring easy background areas.
  • Warm-Starting is a Killer App: DTBCA is particularly powerful for "dynamic" problems where the model changes slightly over time (e.g., in a branch-and-bound search). Because it only updates what is necessary, it can re-solve a modified problem orders of magnitude faster than starting from scratch.

Key Results

The authors evaluated DTBCA on classic, large-scale vision and biology problems, including Stereo Vision (Middlebury dataset), Object Segmentation (PASCAL VOC), and Protein Design.

  • Efficiency: In segmentation tasks, DTBCA-WTA reached the same dual objective as standard methods while performing orders of magnitude fewer message updates (measured in distance transforms).
Dual Objective vs Distance Transforms
  • Runtime: On certain complex problems, the dynamic approach cut total runtime by more than 80% compared to TRW-S, reaching the optimal MAP objective significantly faster.
Dual Objective vs Time
  • Convergence: In the protein design task, the dynamic schedule converged to the optimum in just 0.39 seconds, whereas the standard "star-based" schedule took 0.86 seconds and required twice as many computations.

Limitations and Future Work

  • Implementation Overhead: While DTBCA performs fewer basic units of work, the logic required to manage the dynamic forest and compute scores adds overhead. For very simple problems, highly optimized static implementations (like the original TRW-S C++ code) can still be faster in raw wall-clock time.
  • Greedy Selection: The use of Kruskal’s algorithm is a greedy heuristic. While highly effective in practice, it does not guarantee the mathematically optimal forest for the next step.
  • Generalization: The authors suggest that the localized LPDG measure is a general tool that could be applied to other optimization problems beyond MAP inference, such as "cluster pursuit" for tightening LP relaxations.

Summary updated

Abstract

This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems.
BibTeX
@inproceedings{tarlow2011dynamic,
  author = {Daniel Tarlow and Dhruv Batra and Pushmeet Kohli and Vladimir Kolmogorov},
  title = {{Dynamic Tree Block Coordinate Ascent}},
  booktitle = {International Conference on Machine Learning},
  year = {2011},
  url = {https://openreview.net/forum?id=ryEhgsWd-H},
}
Figure