Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent
arXiv:1909.07079
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 s and 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.
arXiv comment14 pages
References in corpus (7)
- An overview of gradient descent optimization algorithms
- Fast Supervised Hashing with Decision Trees for High-Dimensional Data
- Truncated Power Method for Sparse Eigenvalue Problems
- PU Learning for Matrix Completion
- Large-scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications
- Binary Optimization via Mathematical Programming with Equilibrium Constraints
- Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints