DPCD: Discrete Principal Coordinate Descent for Binary Variable Problems

Huan XiongAAAI 2022 · OpenReview

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. Generally speaking, 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 an efficient algorithm, named Discrete Principal Coordinate Descent (DPCD), to find effective approximate solutions for general binary optimization problems. The proposed algorithm iteratively solves optimization problems related to the linear approximation of loss functions, which leads to updating the binary variables that most impact the value of the loss functions at each step. Our method supports a wide range of empirical objective functions with/without restrictions on the numbers of 1s and -1s 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 binary hashing 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.

Introduction

Binary optimization—the task of finding the optimal configuration for variables restricted to the set $\{-1, 1\}$—is a fundamental challenge in modern machine learning. It is the engine behind diverse applications, including image denoising, community discovery, and high-speed image retrieval via hashing. Despite its importance, binary optimization is notoriously difficult (NP-hard) because the search space grows exponentially with the number of variables $n$, reaching $2^n$ possible combinations.

Traditional approaches typically rely on continuous relaxation, which introduces significant quantization errors, or Signed Gradient Methods (SGM), which often fail to converge for non-concave functions. While coordinate descent offers accuracy, its sequential nature makes it prohibitively slow for large-scale problems. To address these limitations, we introduce Discrete Principal Coordinate Descent (DPCD), a fast and generalized algorithm designed to tackle large-scale binary optimization without the typical trade-offs in accuracy or speed.

Methodology

The core innovation of DPCD is the identification and selective updating of L-principal coordinates. Unlike SGM, which flips all variables based on the gradient, or standard coordinate descent, which updates only one, DPCD identifies a subset of variables that exert the greatest influence on the loss function.

Principal Coordinate Selection

DPCD utilizes adaptive thresholding to determine which variables are "important" enough to flip. By calculating thresholds ($L_1, L_2$) based on current gradients, the algorithm identifies indices where the product of the current value and its gradient is large. These are the principal coordinates where a sign flip is most likely to yield a significant decrease in the objective function. This selective approach prevents the "overshooting" or divergence issues common in global update methods.

Constraint Handling and Convergence

Many real-world tasks, such as balanced hashing, require a fixed number of 1s and -1s. DPCD handles these constraints efficiently by sorting gradients and flipping pairs of variables (e.g., one from 1 to -1 and another from -1 to 1) to maintain the balance condition. Furthermore, we provide theoretical guarantees that DPCD will converge in a finite number of steps for any differentiable function with Lipschitz continuous gradients, a property often missing in heuristic discrete solvers.

Experimental Evaluation

We evaluated DPCD across three major image retrieval benchmarks: CIFAR-10 (60,000 images), ImageNet (127,000 images from 100 classes), and NUS-WIDE (270,000 multi-label images). These datasets represent a range of scales and complexities in visual data.

Sample image from the CIFAR-10 dataset used for benchmarking binary hashing performance.

In these experiments, DPCD was integrated into six existing hashing frameworks, including SDH, FSDH, and FastHash, to demonstrate its versatility as a general-purpose optimizer.

Results and Discussion

The experimental results demonstrate that DPCD consistently outperforms state-of-the-art methods in both accuracy and computational efficiency.

  • Accuracy: On the CIFAR-10 dataset with 96-bit codes, DPCD achieved a Mean Average Precision (MAP) of 0.7126, significantly higher than the 0.6314 achieved by Discrete Coordinate Descent (DCC) and the 0.7013 by SGM.
  • Efficiency: DPCD exhibits massive speedups. For the same 96-bit CIFAR-10 task, DPCD completed training in just 9.39 seconds, compared to 260.22 seconds for MPEC-EPM—a nearly 28-fold improvement.
Example of an airplane image from the large-scale datasets used to test retrieval efficiency.

These results confirm that by focusing on principal coordinates, DPCD achieves a "surgical precision" that avoids the pitfalls of more aggressive gradient methods while maintaining the speed necessary for large-scale applications.

Conclusion

Discrete Principal Coordinate Descent (DPCD) represents a significant advancement in binary optimization. By combining selective variable updates with strong theoretical convergence guarantees, it provides a robust and efficient solution for high-dimensional discrete problems. While future work may focus on further automating hyperparameter tuning and extending the method to non-smooth functions, DPCD currently stands as a state-of-the-art tool for large-scale machine learning tasks like binary hashing.

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. Generally speaking, 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 an efficient algorithm, named Discrete Principal Coordinate Descent (DPCD), to find effective approximate solutions for general binary optimization problems. The proposed algorithm iteratively solves optimization problems related to the linear approximation of loss functions, which leads to updating the binary variables that most impact the value of the loss functions at each step. Our method supports a wide range of empirical objective functions with/without restrictions on the numbers of 1s and -1s 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 binary hashing 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
@inproceedings{xiong2022dpcd,
  author = {Huan Xiong},
  title = {{DPCD: Discrete Principal Coordinate Descent for Binary Variable Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=UtIv55oUDh},
}
Figure