A Continuation Method For Discrete Optimization And Its Application To Nearest Neighbor Classification

Abstract

The continuation method is a popular approach in non-convex optimization and computer vision. The main idea is to start from a simple function that can be minimized efficiently, and gradually transform it to the more complicated original objective function. The solution of the simpler problem is used as the starting point to solve the original problem. We show a continuation method for discrete optimization problems. Ideally, we would like the evolved function to be hill-climbing friendly and to have the same global minima as the original function. We show that the proposed continuation method is the best affine approximation of a transformation that is guaranteed to transform the function to a hill-climbing friendly function and to have the same global minima. We show the effectiveness of the proposed technique in the problem of nearest neighbor classification. Although nearest neighbor methods are often competitive in terms of sample efficiency, the computational complexity in the

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyshameli2018a

Related papers

• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Explaining The Success Of Nearest Neighbor Methods In Prediction (2025)18.63
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Finding Relevant Points For Nearest-neighbor Classification (2021)4.52
• On Convergence Of Nearest Neighbor Classifiers Over Feature Transformations (2020)0.00
• Neural Nearest Neighbors Networks (2018)0.00