Distributed adaptive nearest neighbor classifier: algorithm and theory

DOI10.1007/S11222-023-10267-7MaRDI QIDQ6172153zbMATH OpenOpenAlexFDO

Authors Rui Qi Liu, Ganggang Xu, Zuofeng Shang

Publication date 16 August 2023

Published in Statistics and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.09788

zbMATH Keywords

minimax optimaladaptive procedurebinary classificationdistributed learning

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: 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.

Recommendations

• Learning k-nearest neighbors classifier from distributed data
• Error analysis of distributed algorithm for large scale data classification
• An adaptive multiclass nearest neighbor classifier
• Distributed kernel gradient descent algorithm for minimum error entropy principle
• A study on the error of distributed algorithms for big data classification with SVM

Cites work

• scientific article; zbMATH DE number 1699986 (Why is no real title available?)
• Classification in general finite dimensional spaces with the \(k\)-nearest neighbor rule
• Computational Limits of A Distributed Algorithm For Smoothing Spline
• Consistent nonparametric regression. Discussion
• Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and Its Asymptotic Optimality
• Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates
• Fast learning rates for plug-in classifiers
• Introduction to algorithms.
• Local asymptotics for polynomial spline regression
• Locally nearest neighbor classifiers for pattern classification
• Nearest neighbor classification in infinite dimension
• Nearest neighbor pattern classification
• Nonparametric Bayesian aggregation for massive data
• On a Problem of Adaptive Estimation in Gaussian White Noise
• On the strong universal consistency of nearest neighbor regression function estimates
• Optimal pointwise adaptive methods in nonparametric estimation
• Optimal weighted nearest neighbour classifiers
• Projection estimation in multiple regression with application to functional ANOVA models
• Transfer learning for nonparametric classification: minimax rate and adaptive classifier
• Universal Bayes consistency in metric spaces

Cited in

(5)

• Distributed Adaptive Binary Quantization for Fast Nearest Neighbor Search
• Error analysis of distributed algorithm for large scale data classification
• Averaging versus voting: a comparative study of strategies for distributed classification
• Learning k-nearest neighbors classifier from distributed data
• Distributed classification learning based on nonlinear vector support machines for switching networks

This page was built for publication: Distributed adaptive nearest neighbor classifier: algorithm and theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172153)