arXiv research

Improved Frank-Wolfe algorithm for constrained convex optimization with nearest extreme point oracle.

Intuitive clustering algorithm balances cluster size and cohesion.

Machine learning has played an important role in information retrieval (IR) in recent times. In search engines, for example, query keywords are accepted and documents are returned in order of relevance to the given query; this can be cast as a multi-label ranking problem in machine learning. Generally, the number of ca…

In our physically inspired in-tree (IT) based clustering algorithm and the series after it, there is only one free parameter involved in computing the potential value of each point. In this work, based on the Delaunay Triangulation or its dual Voronoi tessellation, we propose a nonparametric process to compute potentia…

Characterizes Lebesgue points using nearest neighbor methods.

New algorithm reduces regret in contextual bandits with many near-boundary contexts.

VNNGP uses nearest neighbors to approximate GPs, improving scalability and performance.

Spectral clustering identifies clusters of multivariate extremes.

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…

We introduce multi-frequency vector diffusion maps (MFVDM), a new framework for organizing and analyzing high dimensional datasets. The new method is a mathematical and algorithmic generalization of vector diffusion maps (VDM) and other non-linear dimensionality reduction methods. MFVDM combines different nonlinear emb…

Algorithms often carry out equally many computations for "easy" and "hard" problem instances. In particular, algorithms for finding nearest neighbors typically have the same running time regardless of the particular problem instance. In this paper, we consider the approximate k-nearest-neighbor problem, which is the pr…

Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning task as finding a partition in which the nearest neighbors of a training set point belong to the same…

Constructs harmonic maps near retractions in hyperbolic spaces.

We show that the nearest point retraction is a uniform quasi-isometry from the Thurston metric on a hyperbolic domain in the Riemann sphere to the boundary of the convex hull of its complement. As a corollary, one obtains explicit bounds on the quasi-isometry constant of the nearest point retraction with respect to the…

If we pick $n$ random points uniformly in $[0,1]^d$ and connect each point to its $k-$nearest neighbors, then it is well known that there exists a giant connected component with high probability. We prove that in $[0,1]^d$ it suffices to connect every point to $c_{d,1} \log{\log{n}}$ points chosen randomly among its $…

In the machine learning field, dimensionality reduction is an important task. It mitigates the undesired properties of high-dimensional spaces to facilitate classification, compression, and visualization of high-dimensional data. During the last decade, researchers proposed many new (non-linear) techniques for dimensio…

The condensed nearest neighbor (CNN) algorithm is a heuristic for reducing the number of prototypical points stored by a nearest neighbor classifier, while keeping the classification rule given by the reduced prototypical set consistent with the full set. I present an upper bound on the number of prototypical points ac…

Introduces Grassmann Distance Complexity to measure algebraic set nearest point problems.

We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs…

This paper surveys various methods for dimensionality reduction and nearest neighbor search.

New method speeds up k-means clustering for large k by improving nearest-neighbor search.

In the panoply of pattern classification techniques, few enjoy the intuitive appeal and simplicity of the nearest neighbor rule: given a set of samples in some metric domain space whose value under some function is known, we estimate the function anywhere in the domain by giving the value of the nearest sample per the …

We consider machine learning in a comparison-based setting where we are given a set of points in a metric space, but we have no access to the actual distances between the points. Instead, we can only ask an oracle whether the distance between two points $i$ and $j$ is smaller than the distance between the points $i$ an…

The objective in extreme multi-label learning is to train a classifier that can automatically tag a novel data point with the most relevant subset of labels from an extremely large label set. Embedding based approaches make training and prediction tractable by assuming that the training label matrix is low-rank and hen…

A new ensemble method improves kNN performance by extending the neighborhood rule.

Given a hyperbolic domain, the nearest point retraction is a conformally natural homotopy equivalence from the domain to the boundary of the convex core of its complement. Marden and Markovic showed that if the domain is uniformly perfect, then there exists a conformally natural quasiconformal map which admits a bounde…

The paper analyzes how much data points can be altered to change their rank in nearest neighbor searches.

We define regular points of an extremal subset in an Alexandrov space and study their basic properties. We show that a neighborhood of a regular point in an extremal subset is almost isometric to an open subset in Euclidean space and that the set of regular points in an extremal subset has full measure and is dense in …

Method tracks change-points in crypto-assets extremes.

Algorithm identifies nearest mode in noisy data.

ASK-NN detects distribution drifts in LLM-generated text.

The Nearest subspace classifier (NSS) finds an estimation of the underlying subspace within each class and assigns data points to the class that corresponds to its nearest subspace. This paper mainly studies how well NSS can be generalized to new samples. It is proved that NSS is strongly consistent under certain assum…

The paper studies empirical processes from nearest neighbors in regression.

Improves time series classification with forest proximities.

In this paper known results of symmetric orthogonality, as introduced by G. Birkhoff, and non-expansive nearest point projections are extended from the linear to the metric setting. If the space has non-positive curvature in the sense Busemann then it is shown that those concepts are actually equivalent. In the end it …

Let $P : Σ\rightarrow S$ be a finite degree covering map between surfaces. Rafi and Schleimer show that there is an induced quasi-isometric embedding $Π: \mathcal{C}(S) \rightarrow \mathcal{C}(Σ)$ between the associated curve complexes. We define an operation on curves in $\mathcal{C}(Σ)$ using minimal intersection num…

The multilabel learning problem with large number of labels, features, and data-points has generated a tremendous interest recently. A recurring theme of these problems is that only a few labels are active in any given datapoint as compared to the total number of labels. However, only a small number of existing work ta…

Multi-class classification with a very large number of classes, or extreme classification, is a challenging problem from both statistical and computational perspectives. Most of the classical approaches to multi-class classification, including one-vs-rest or multi-class support vector machines, require the exact estima…

In many scientific disciplines structures in high-dimensional data have to be found, e.g., in stellar spectra, in genome data, or in face recognition tasks. In this work we present a novel approach to non-linear dimensionality reduction. It is based on fitting K-nearest neighbor regression to the unsupervised regressio…

This paper proposes a new hashing-based KNN technique for faster nearest neighbor selection.

Deep neural networks (DNNs) enable innovative applications of machine learning like image recognition, machine translation, or malware detection. However, deep learning is often criticized for its lack of robustness in adversarial settings (e.g., vulnerability to adversarial inputs) and general inability to rationalize…

A framework for flagging content with limited data.

We explore and expand the $\textit{Soft Nearest Neighbor Loss}$ to measure the $\textit{entanglement}$ of class manifolds in representation space: i.e., how close pairs of points from the same class are relative to pairs of points from different classes. We demonstrate several use cases of the loss. As an analytical to…

SPlit optimizes dataset splitting for better model performance.

Take N sites distributed randomly and uniformly on a smooth closed surface. We express the expected distance <D_k(N)> from an arbitrary point on the surface to its kth-nearest neighboring site, in terms of the function A(l) giving the area of a disc of radius l about that point. We then find two universalities. First, …

Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space and a query point (image), efficiently determine the nearest subspace to the query in $\ell^1$ distance. We …

New method selects recent similar periods for better electricity price forecasting.

Algorithm finds adversarial examples for k-NN classifiers using Voronoi diagrams.