12 citations · 14 across the 8 of their papers we have counts for
10 papers
Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning
Fangzhou Wu, Haike Xu, Sandeep Silwal
Graph-based approximate nearest neighbor search (ANNS) is widely used for large-scale semantic search. Its indices are constructed primarily based on geometric relationships among…
Even Faster Kernel Matrix Linear Algebra via Density Estimation
Rikhav Shah, Sandeep Silwal, Haike Xu
This paper studies the use of kernel density estimation (KDE) for linear algebraic tasks involving the kernel matrix of a collection of data points in . In particu…
Statistical-Computational Trade-offs for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +4
We study the density estimation problem defined as follows: given distributions over a discrete domain , as well as a collection of samples chosen from…
SparseCL: Sparse Contrastive Learning for Contradiction Retrieval
Haike Xu, Zongyu Lin, Yizhou Sun +2
Contradiction retrieval refers to identifying and extracting documents that explicitly disagree with or refute the content of a query, which is important to many downstream applica…
A Bi-metric Framework for Fast Similarity Search
Haike Xu, Sandeep Silwal, Piotr Indyk
We propose a new "bi-metric" framework for designing nearest neighbor data structures. Our framework assumes two dissimilarity functions: a ground-truth metric that is accurate but…
Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
Piotr Indyk, Haike Xu
Graph-based approaches to nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. We study the…
A Universal Discriminator for Zero-Shot Generalization
Haike Xu, Zongyu Lin, Jing Zhou +2
Generative modeling has been the dominant approach for large-scale pretraining and zero-shot generalization. In this work, we challenge this convention by showing that discriminati…
Embeddings and labeling schemes for A*
Talya Eden, Piotr Indyk, Haike Xu
A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function that estimates the shortest distance from any input…
Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations
Haike Xu, Jian Li
We consider the stochastic combinatorial semi-bandit problem with adversarial corruptions. We provide a simple combinatorial algorithm that can achieve a regret of $\tilde{O}\left(…
Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
Haike Xu, Tengyu Ma, Simon S. Du
This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB), which enjoys a stronger gap-depende…