2022/02/05 by J. Jon Ryu, Ryu, J. Jon, Young-Han Kim +1
Computer Science · Mathematics · #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel #Statistical Methods and Inference #Statistics Theory (math.ST) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.02464
openalex publication_date 2022/02/05 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
This paper presents how to perform minimax optimal classification, regression, and density estimation based on fixed-k nearest neighbor (NN) searches. We consider a distributed learning scenario, in which a massive dataset is split into smaller groups, where the k-NNs are found for a query point with respect to each subset of data. We propose optimal rules to aggregate the fixed-k-NN information for classification, regression, and density estimation that achieve minimax optimal rates for the respective problems. We show that the distributed algorithm with a fixed k over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor under some regularity conditions. Roughly speaking, distributed k-NN rules with M groups has a performance comparable to the standard Θ(kM)-NN rules even for fixed k.