Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent

Huan Xiong, Mengyang Yu, Li Liu, Fan Zhu, Fumin Shen, Ling ShaoarXiv 2019 · OpenReview

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.

Comparison of optimization paths between SGM and DPCD

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.

Density performance across large-scale graph datasets (uk-2007-05, dblp-2010, eswiki-2013, hollywood-2009)

As shown in the performance plots above, DPCD consistently achieves higher density scores across various graph cardinalities. Notable highlights include:

  • Efficiency: On the hollywood-2009 dataset (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

Abstract

Binary optimization, a representative subclass of discrete optimization, plays an important role in mathematical optimization and has various applications in computer vision and machine learning. Usually, binary optimization problems are NP-hard and difficult to solve due to the binary constraints, especially when the number of variables is very large. Existing methods often suffer from high computational costs or large accumulated quantization errors, or are only designed for specific tasks. In this paper, we propose a fast algorithm to find effective approximate solutions for general binary optimization problems. The proposed algorithm iteratively solves minimization problems related to the linear surrogates of loss functions, which leads to the updating of some binary variables most impacting the value of loss functions in each step. Our method supports a wide class of empirical objective functions with/without restrictions on the numbers of $1$s and $-1$s in the binary variables. Furthermore, the theoretical convergence of our algorithm is proven, and the explicit convergence rates are derived, for objective functions with Lipschitz continuous gradients, which are commonly adopted in practice. Extensive experiments on several binary optimization tasks and large-scale datasets demonstrate the superiority of the proposed algorithm over several state-of-the-art methods in terms of both effectiveness and efficiency.
BibTeX
@misc{xiong2019fast,
  author = {Huan Xiong and Mengyang Yu and Li Liu and Fan Zhu and Fumin Shen and Ling Shao},
  title = {{Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent}},
  year = {2019},
  eprint = {1909.07079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.07079},
}

Loading related content...

Figure