| Paper ID | D5-S1-T3.3 |
| Paper Title |
Greedy k-Center from Noisy Distance Samples |
| Authors |
Neharika Jali, Nikhil Karamchandani, Sharayu Moharir, Indian Institute of Technology Bombay, India |
| Session |
D5-S1-T3: Kernels & Clustering |
| Chaired Session: |
Friday, 16 July, 22:00 - 22:20 |
| Engagement Session: |
Friday, 16 July, 22:20 - 22:40 |
| Abstract |
We study a variant of the canonical k-center problem over a set of vertices in a metric space, where the underlying distances are apriori unknown. Instead, we can query an oracle which provides noisy/incomplete estimates of the distance between any pair of vertices. We consider two oracle models: Dimension Sampling where each query to the oracle returns the distance between a pair of points in one dimension; and Noisy Distance Sampling where the oracle returns the true distance corrupted by noise. We propose active algorithms, based on ideas of UCB, Thompson sampling and adaptive estimation developed in the closely related multi-armed bandit problem, that solve the problem within an approximation ratio of two with high probability. We analytically characterize instance-dependent query complexity of our algorithms and also demonstrate significant improvements on two real-world datasets.
|
