Getting Feasible Variable Estimates From Infeasible Ones: MRF Local Polytope Study
This addresses a computational bottleneck in optimization for researchers and practitioners in fields like machine learning and computer vision, offering an incremental improvement over existing projection methods.
The paper tackles the problem of efficiently obtaining feasible primal solutions from dual ones in large-scale optimization with separability, proposing an alternative to Euclidean projection that maintains similar convergence properties. It demonstrates the method's superiority on the local polytope relaxation for Markov Random Fields inference.
This paper proposes a method for construction of approximate feasible primal solutions from dual ones for large-scale optimization problems possessing certain separability properties. Whereas infeasible primal estimates can typically be produced from (sub-)gradients of the dual function, it is often not easy to project them to the primal feasible set, since the projection itself has a complexity comparable to the complexity of the initial problem. We propose an alternative efficient method to obtain feasibility and show that its properties influencing the convergence to the optimum are similar to the properties of the Euclidean projection. We apply our method to the local polytope relaxation of inference problems for Markov Random Fields and demonstrate its superiority over existing methods.