Fast parallel and adaptive updates for dual-decomposition solvers

摘要: Dual-decomposition (DD) methods are quickly becoming important tools for estimating the minimum energy state of a graphical model. DD decompose complex model into collection simpler subproblems that can be solved exactly (such as trees), in combination provide upper and lower bounds on exact solution. Subproblem choice play major role: larger tend to improve bound more per iteration, while smaller enable highly parallel solvers benefit from re-using past solutions when there few changes between iterations. We propose an algorithm balance many these aspects speed up convergence. Our method uses cluster tree data structure has been proposed adaptive inference tasks, we apply it this paper dual-decomposition approximate inference. This approach allows us process large at each allowing high degree parallelizability taking advantage with sparse updates. For both synthetic inputs real-world stereo matching problem, demonstrate our is able achieve significant improvement convergence time.