l_p-Box ADMM: A Versatile Framework for Integer Programming.

Area of Science:

• Computer Vision
• Machine Learning
• Optimization

Background:

• Integer programming (IP) is crucial for computer vision and machine learning, but existing methods struggle with accuracy, feasibility, and scalability.
• Current approaches often focus on specific IP forms, limiting their general applicability.

Purpose of the Study:

• To propose a novel and versatile framework, $\ell _p$ℓp-box ADMM, for addressing the limitations of existing integer programming solvers.
• To enhance the accuracy, feasibility, and scalability of solving IP problems in machine learning and computer vision.

Main Methods:

• The $\ell _p$ℓp-box ADMM framework replaces discrete constraints with the intersection of a box and an $\ell _p$ℓp-norm sphere.
• This equivalence is integrated into the Alternating Direction Method of Multipliers (ADMM) to manage continuous constraints effectively.
• Theoretical analysis of global convergence is provided for the perturbed IP problem, ensuring solutions are close to the original problem's stationary points.

Main Results:

• The $\ell _p$ℓp-box ADMM framework demonstrates efficacy on binary quadratic programming (BQP), yielding simple and computationally efficient ADMM steps.
• Applied to MRF energy minimization, graph matching, and clustering, the framework significantly outperforms generic IP solvers in runtime and objective value.
• The method achieves competitive performance against specialized state-of-the-art algorithms for these applications.

Conclusions:

• The $\ell _p$ℓp-box ADMM offers a versatile and effective solution for integer programming problems in machine learning and computer vision.
• Its ability to handle continuous constraints separately within the ADMM framework leads to manageable sub-problems and improved performance.
• The framework presents a significant advancement, offering superior accuracy, feasibility, and scalability compared to existing generic IP solvers.