Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory

2021-05-20 · Ruiqi Liu, Ganggang Xu, Zuofeng Shang

When data is of an extraordinarily large size or physically stored in different locations, the distributed nearest neighbor (NN) classifier is an attractive tool for classification. We propose a novel distributed adaptive NN classifier for which the number of nearest neighbors is a tuning parameter stochastically chosen by a data-driven criterion. An early stopping rule is proposed when searching for the optimal tuning parameter, which not only speeds up the computation but also improves the finite sample performance of the proposed Algorithm. Convergence rate of excess risk of the distributed adaptive NN classifier is investigated under various sub-sample size compositions. In particular, we show that when the sub-sample sizes are sufficiently large, the proposed classifier achieves the nearly optimal convergence rate. Effectiveness of the proposed approach is demonstrated through simulation studies as well as an empirical application to a real-world dataset.

📄 PDF Abstract BibTeX arXiv:2105.09788

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Early Stopping Early Stopping is a regularization technique for deep neural networks that stops training when parameter updates no longer begin to yield improves on a validation set. In…

Statistical Guarantees of Distributed Nearest Neighbor Classification

2020-12-01 · NeurIPS 2020 12 · Jiexin Duan, Xingye Qiao, Guang Cheng

Nearest neighbor is a popular nonparametric method for classification and regression with many appealing properties. In the big data era, the sheer volume and spatial/temporal disparity of big data may prohibit centrally…

Classification General Classification

Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator

2024-09-08 · Alexandre Luís Magalhães Levada, Frank Nielsen, Michel Ferreira Cardia Haddad

The $k$-nearest neighbor ($k$-NN) algorithm is one of the most popular methods for nonparametric classification. However, a relevant limitation concerns the definition of the number of neighbors $k$. This parameter exert…

A Two-Stage Active Learning Algorithm for $k$-Nearest Neighbors

2022-11-19 · Nick Rittler, Kamalika Chaudhuri

$k$-nearest neighbor classification is a popular non-parametric method because of desirable properties like automatic adaption to distributional scale changes. Unfortunately, it has thus far proved difficult to design ac…

Active Learning Vocal Bursts Valence Prediction

A Graph-Based Semi-Supervised k Nearest-Neighbor Method for Nonlinear Manifold Distributed Data Classification

2016-06-03 · Enmei Tu, Yaqian Zhang, Lin Zhu, Jie Yang 외

$k$ Nearest Neighbors ($k$NN) is one of the most widely used supervised learning algorithms to classify Gaussian distributed data, but it does not achieve good results when it is applied to nonlinear manifold distributed…

General Classification

An adaptive nearest neighbor rule for classification

2019-05-29 · NeurIPS 2019 12 · Akshay Balsubramani, Sanjoy Dasgupta, Yoav Freund, Shay Moran

We introduce a variant of the $k$-nearest neighbor classifier in which $k$ is chosen adaptively for each query, rather than supplied as a parameter. The choice of $k$ depends on properties of each neighborhood, and there…

Classification General Classification Generalization Bounds