Abstract
Binary optimization is a cornerstone of machine learning and computer vision, yet its NP-hard nature makes large-scale applications computationally prohibitive. This paper introduces Discrete Principal Coordinate Descent (DPCD), an efficient algorithm designed to find approximate solutions for general binary optimization problems. By iteratively solving linear surrogates and selectively updating "principal coordinates"—variables with the highest impact on the loss function—DPCD achieves significant speedups and maintains theoretical convergence. Extensive experiments on massive datasets demonstrate that DPCD outperforms state-of-the-art methods in both accuracy and computational efficiency.
The Challenge of Binary Optimization
Many critical tasks, such as image hashing, graph bisection, and community discovery, rely on binary optimization. These problems involve variables constrained to discrete values (e.g., $\{-1, 1\}$). With $n$ variables, the search space grows exponentially ($2^n$), making exact solutions impossible for "web-scale" data. Furthermore, real-world applications often impose balance constraints (e.g., an equal number of 1s and -1s), which standard continuous relaxation methods struggle to handle without significant quantization errors.
Discrete Principal Coordinate Descent (DPCD)
The core innovation of DPCD is its selective update strategy. Rather than updating all variables simultaneously—which can lead to instability or divergence in discrete spaces—DPCD identifies Principal Coordinates.
As illustrated in the optimization path comparison above, DPCD moves strategically through the discrete space. The algorithm employs:
- Linear Surrogates: It approximates the objective function locally to determine the most beneficial update directions.
- Adaptive Thresholding: By calculating thresholds based on the gradient, the algorithm determines which bits to flip to maximize loss reduction.
- Constraint Preservation: For problems requiring fixed bit counts, DPCD uses a sorting-and-swapping mechanism to maintain constraints while improving the objective value.
- Neighborhood Search: To escape local minima, a heuristic search explores nearby binary configurations.
Key Results and Scalability
The authors evaluated DPCD against several state-of-the-art methods across diverse tasks like dense subgraph discovery and binary hashing. The performance gains are particularly striking in terms of efficiency and solution quality.
As shown in the performance plots above, DPCD consistently achieves higher density scores across various graph cardinalities. Notable highlights include:
- Efficiency: On the
hollywood-2009dataset (1.13M nodes), DPCD converged in just 21.8 seconds, nearly 100x faster than the competing MPEC-EPM method (2,114 seconds). - Accuracy: In supervised binary hashing on
CIFAR-10, DPCD improved Mean Average Precision (MAP) by over 8% compared to Discrete Coordinate Descent (DCC). - Theoretical Convergence: Unlike many heuristic discrete solvers, DPCD is mathematically proven to converge in a finite number of steps for functions with Lipschitz continuous gradients.
Conclusion
DPCD offers a powerful framework for large-scale discrete optimization, balancing theoretical rigor with practical performance. By focusing on principal coordinates, it avoids the pitfalls of global updates in discrete spaces. Future work aims to extend this framework to more general discrete sets beyond binary variables and integrate advanced optimization techniques like Adam or Momentum to further push the boundaries of speed and accuracy.
Summary updated