A Generalized Method for Binary Optimization: Convergence Analysis and Applications.

Area of Science:

• Computer Science
• Optimization Theory

Background:

• Binary optimization problems (BOPs) are prevalent in machine learning, computer vision, and information retrieval.
• Current methods often suffer from quantization errors or limited applicability to specific loss functions.

Purpose of the Study:

• To introduce a generalized and efficient method for solving BOPs.
• To address limitations of existing continuous relaxation and specialized algorithms.

Main Methods:

• Propose Alternating Binary Matrix Optimization (ABMO), a novel generalized approach for BOPs.
• Reformulate constraints as an intersection of closed sets, enabling iterative decomposition into solvable subproblems.
• Employ a perturbation technique for theoretical convergence analysis on a continuous approximated problem.

Main Results:

• Demonstrate ABMO's ability to handle BOPs with diverse constraints (orthogonality, linear) and a wide range of loss functions.
• Provide rigorous mathematical proof of convergence to stationary and feasible points.
• Derive the convergence rate of the ABMO algorithm.
• Achieve superior performance across four distinct binary optimization tasks.

Conclusions:

• ABMO offers a superior and more general solution for binary optimization problems compared to state-of-the-art methods.
• The method's theoretical convergence guarantees and practical performance validate its effectiveness.