The Soft Nearest Neighbor Loss improves representation quality and generalization.
problem Improving the quality of representations in machine learning models.
method Explored and expanded the Soft Nearest Neighbor Loss to measure class entanglement.
result Maximizing the entanglement of different class representations leads to better generalization and uncertainty estimation.
Improved clustering accuracy with disentangled latent code representation.
problem Improving k-Means clustering performance.
method Optimizing the entanglement of autoencoder latent code representation using soft nearest neighbor loss with annealing temperature.
result 96.2% test clustering accuracy on MNIST, 85.6% on Fashion-MNIST, and 79.2% on EMNIST Balanced datasets.
Method generates prototypes from small datasets for efficient learning.
problem Efficiently learning from small datasets with soft labels.
method Modular method for generating soft-label prototypical lines and Hierarchical Soft-Label Prototype k-Nearest Neighbor algorithm.
result High classification accuracy with significantly fewer prototypes than classes.
Less-than-one-shot learning tackles few-shot learning with minimal data.
problem Training models on very small datasets while maintaining accuracy.
method Soft-label k-Nearest Neighbors classifier and theoretical lower bounds analysis.
result Achieving learning of multiple classes with fewer than the required samples.
New method accelerates large margin metric learning for nearest neighbor classification.
problem Efficiently learning metrics for nearest neighbor classification.
method Triplet mining and stratified sampling for large margin metric learning.
result Improved efficiency and scalability of optimization.
Improved KNN data valuation method with reduced computation time.
problem Efficiently valuing individual data points in KNN models.
method Proposed a new utility function and derived its calculation for KNN classifiers/regressors, achieving similar time complexity as the original method.
result Soft-label KNN-SV outperforms the original method in mislabeled data detection.
UMAP's true loss function differs from what was previously thought, focusing on nearest neighbor graph similarities.
problem Understanding the true effectiveness and mechanism of UMAP for high-dimensional data visualization.
method Deriving UMAP's effective loss function in closed form and analyzing its optimization scheme.
result UMAP aims to reproduce similarities encoded in the nearest neighbor graph, not the full high-dimensional similarities.
New method generates plausible counterfactuals for time series classification.
problem Generating realistic counterfactuals for time series data.
method Gradient-based optimization with soft-DTW alignment and multi-faceted loss function.
result Our method outperforms existing approaches in temporal realism and distributional alignment.
Reduces bounded loss learning to binary classification.
problem Universal consistency of non-i.i.d. processes with bounded loss.
method Constructive reduction to binary classification.
result Any bounded loss output setting can be reduced to binary classification.
Study nearest-neighbor radii under dependent sampling, finding they remain informative.
problem Analyzing nearest-neighbor radii under dependent sampling.
method Consider strong mixing dependent observations, establish distribution-free almost sure convergence and sharp non-asymptotic moment bounds.
result Nearest-neighbor geometry remains informative under dependence sampling.
Deep nearest neighbors outperform self-supervised methods in anomaly detection.
problem Anomaly detection using self-supervised deep methods.
method Simple nearest-neighbor approach on Imagenet pretrained features.
result Nearest-neighbor method outperforms self-supervised methods in accuracy, few shot generalization, training time, and noise robustness.
Develops LSH schemes for f-divergences and mutual information loss.
problem Approximating nearest neighbors in high-dimensional probability distributions.
method General framework and specific LSH schemes for f-divergences and mutual information loss.
result Generalized Jensen-Shannon divergence can be approximated by Hellinger distance.
Characterizes Lebesgue points using nearest neighbor methods.
problem Consistency of classification algorithms based on nearest neighbors.
method Characterization of Lebesgue points via 1-Nearest Neighbor regression.
result Proves convergence of 1-Nearest Neighbor classification algorithms in metric spaces.
The distance metric plays an important role in nearest neighbor (NN) classification. Usually the Euclidean distance metric is assumed or a Mahalanobis distance metric is optimized to improve the NN performance. In this paper, we study the problem of embedding arbitrary metric spaces into a Euclidean space with the goal…
The paper explains how nearest neighbor methods succeed in prediction.
problem Explaining the success of nearest neighbor methods in prediction.
method The paper covers both theoretical and practical aspects of nearest neighbor methods, including statistical guarantees and practical algorithms.
result The paper provides nonasymptotic statistical guarantees and practical algorithms for nearest neighbor methods.
AWNN improves matrix completion by adaptively weighting nearest neighbors.
problem Matrix completion with optimal nearest neighbor weights and radii selection.
method Adaptively weighted nearest neighbor method for matrix completion.
result Theoretical guarantees and synthetic experiments support the effectiveness of AWNN.
A new method uses nearest neighbors for importance weighting.
problem Data covariate shift problems in machine learning.
method Nearest neighbor classification scheme for determining importance weights.
result Demonstrated effectiveness through comparative experiments on various classification tasks.
Adaptive algorithm speeds up k-nearest-neighbor searches.
problem Finding k nearest neighbors with varying efficiency.
method Adaptive estimation of distances to optimize search.
result The algorithm achieves significant speedups compared to naive methods.
This paper compares FAISS and FENSHSES for nearest neighbor search in Hamming space.
problem Comparing nearest neighbor search systems in Hamming space.
method Comprehensive evaluations of indexing speed, search latency, and RAM consumption.
result Better understanding of trade-offs between main memory and secondary memory systems.
Nearest neighbor methods are a popular class of nonparametric estimators with several desirable properties, such as adaptivity to different distance scales in different regions of space. Prior work on convergence rates for nearest neighbor classification has not fully reflected these subtle properties. We analyze the b…
The estimation of optimal treatment regimes is of considerable interest to precision medicine. In this work, we propose a causal k-nearest neighbor method to estimate the optimal treatment regime. The method roots in the framework of causal inference, and estimates the causal treatment effects within the nearest neig…
A new method for covariate shift adaptation using nearest neighbors.
problem Mitigating distribution shift between source and target datasets.
method Directly work on unlabeled target data, labeled by nearest neighbors in source data.
result Optimal choice of k=1 simplifies hyper-parameter tuning and improves efficiency. A defense against adversarial examples using k-Nearest Neighbor and deep learning.
problem Evaluating robustness of k-Nearest Neighbor and its deep learning combination.
method Proposed heuristic attack to find adversarial examples for kNN and DkNN.
result Our attack significantly outperforms other attacks on DkNN.
VNNGP uses nearest neighbors to approximate GPs, improving scalability and performance.
problem Scalability issues in Gaussian process approximations.
method Sparse precision structure via nearest neighbors, variational framework.
result VNNGP outperforms low-rank methods and is less prone to overfitting.
New method for clustering binary data using nearest neighbor median shift.
problem Clustering binary data effectively.
method BinNNMS based on nearest neighbor median shift.
result BinNNMS accurately discovers cluster locations in binary data.
BigNN classifier improves nearest neighbor classification for large datasets.
problem Classification of large datasets that cannot fit into a single machine's memory.
method Divide and conquer scheme with majority voting for final decision; pre-training acceleration technique.
result Rates of convergence for bigNN classifier under minimal assumptions, proving it as optimal.
Paper studies L2-consistency of nearest neighbor matching for biased samples.
problem Biased sampling and missing data in statistical problems.
method Nearest neighbor matching (NNM) to estimate population quantities from biased samples.
result NNM is L2-consistent in finite dimensions without smoothness and boundedness assumptions. Java implementation improves nearest neighbor algorithm complexity.
problem Improving efficiency of nearest neighbor descent algorithm.
method Parallel streams implementation with statistical termination criterion.
result Complexity up to O(nK2logK(n)) for K-nearest neighbors. The paper tackles time series data by applying conformal prediction with nearest neighbors.
problem Time series data violates the exchangeability assumption required for conformal prediction.
method The approach uses the nearest neighbors method with fast parameter tuning and weighted nearest neighbors (FPTO-WNN) to construct reliable prediction intervals.
result Data analysis shows the effectiveness of the proposed approach.
A new multilabel classification framework improves ANN search performance.
problem Efficiently finding approximate nearest neighbors in large datasets.
method Formulated ANN search as a multilabel classification problem, using partitioning classifiers.
result Natural classifier leads to strictly improved performance in ANN search.
K-Nearest neighbor classifier (k-NNC) is simple to use and has little design time like finding k values in k-nearest neighbor classifier, hence these are suitable to work with dynamically varying data-sets. There exists some fundamental improvements over the basic k-NNC, like weighted k-nearest neighbors classifier (wh…
The paper studies empirical processes from nearest neighbors in regression.
problem Estimating conditional cumulative distribution functions and local linear regression.
method Uniform central limit theorem and non-asymptotic bound under local bracketing entropy and uniform entropy numbers.
result Gaussian limit of empirical process with simple covariance.
This paper proposes a new hashing-based KNN technique for faster nearest neighbor selection.
problem Slowness of KNN in big datasets due to searching entire dataset.
method Divide data space into subcells, use hashing to map data points, and select nearest neighbors layer by layer.
result The proposed technique offers competitive performance with KNN and KDtree while significantly improving time efficiency.
New methods use vector search and nearest-neighbor matching for policy learning in causal inference.
problem Learning optimal policies in causal inference with limited data.
method RAG-based policy learning with vector search and nearest-neighbor matching.
result The methods bound the within-candidate choice regret and evaluate the one-step method directly as a policy.
Sublinear memory sketch finds nearest neighbors in streaming data.
problem Finding nearest neighbors in large datasets with limited memory.
method Combines LSH, online kernel density estimation, and compressed sensing to achieve sublinear memory.
result Achieves sublinear memory performance on stable queries, reporting nearest neighbors efficiently.
CGMMD generates conditional samples in one shot with MMD and nearest neighbors.
problem Generating samples from a conditional distribution unseen in training.
method CGMMD uses MMD for a direct minimization problem, producing samples in one forward pass.
result CGMMD achieves convergence to the true conditional distribution with theoretical bounds.
The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X,D), build a data structure that, given any point q, returns a point in P that is closest to q (its "nearest neighbor" in P). The data structure stores additional information about the set P, which is th…
Unsupervised space partitioning improves ANNS performance without pre-processing.
problem Efficient nearest neighbor search in high-dimensional spaces.
method Custom unsupervised learning framework for space partitioning and learning-to-search.
result Our method outperforms state-of-the-art approaches on ANNS benchmarks.
We propose a simple kernel based nearest neighbor approach for handwritten digit classification. The "distance" here is actually a kernel defining the similarity between two images. We carefully study the effects of different number of neighbors and weight schemes and report the results. With only a few nearest neighbo…
A conceptually simple way to classify images is to directly compare test-set data and training-set data. The accuracy of this approach is limited by the method of comparison used, and by the extent to which the training-set data cover configuration space. Here we show that this coverage can be substantially increased u…
Locally adaptive nearest neighbors improve automated systems' performance and are easier to interpret.
problem Improving automated systems' performance and interpretability.
method Developed a method for k nearest neighbors algorithms to learn locally adaptive metrics.
result Locally adaptive metrics improve performance and are interpretable.
New method speeds up k-means clustering for large k by improving nearest-neighbor search.
problem Efficiently clustering large datasets with high-dimensional points.
method Seeded Approximate Nearest-Neighbor Search methods to improve Lloyd's algorithm.
result Significantly faster k-means clustering for large k values.
Improved multiclass classification with class-weighted nearest neighbors.
problem Multiclass classification with large or imbalanced classes.
method Class-weighted k-nearest neighbors algorithm, derived bounds on accuracy and risk.
result Optimized classification metrics like F1 score or Matthew's Correlation Coefficient.
Combines fast evaluation with Bayes consistency in nearest neighbors.
problem Balancing fast evaluation time with Bayes consistency in nearest neighbors.
method Combines locality-sensitive hashing (LSH) with a missing-mass argument.
result Fast and Bayes-consistent classifier with comparable risk decay rates.
New Q-learning methods improve sample complexity for MDPs with continuous states.
problem Challenges in MDPs with continuous state spaces.
method Two nearest neighbor Q-learning methods with improved sample complexities.
result Minimax optimal sample complexities for offline and online settings.
This paper improves nearest neighbor search by learning optimal routing functions.
problem Local minima issues in greedy routing on similarity graphs.
method Learn routing function that considers global graph structure.
result Significant improvement in search performance via learning.
Study shows k-NN regressor consistency in complex survey designs.
problem Lack of consistency results for k-NN regressor in complex survey data. method Analysis of regularity conditions on sampling design and data distribution.
result Consistency of k-NN regressor under complex survey designs. Nonasymptotic error bounds and strong consistency rates for survival analysis methods.
problem Establishing reliable error bounds and consistency rates for survival analysis methods.
method Nonasymptotic error bounds for Kaplan-Meier-based nearest neighbor and kernel survival probability estimators in metric spaces.
result Rates of strong consistency match existing lower bounds for conditional CDF estimation.