论文标题
来自嘈杂距离样品的贪婪K-中心
Greedy k-Center from Noisy Distance Samples
论文作者
论文摘要
我们在公制空间中的一组顶点上研究了规范k-中心问题的变体，在公制空间中，下面的距离是未知的。相反，我们可以查询一个甲骨文，该甲骨文提供了任何对顶点之间距离的嘈杂/不完整的估计。我们考虑两个Oracle模型：维度采样，每个查询到Oracle在一个维度中返回一对点之间的距离；和嘈杂的距离采样，甲骨文返回噪音破坏的真实距离。我们根据在密切相关的多军匪徒问题中开发的UCB，Thompson抽样和轨道上的思想提出了主动算法，这些算法可以自适应地决定将哪些查询发送到Oracle，并能够在两个近似值的近似值中解决K-Center问题，并具有很高的可能性。我们通过分析表征了算法的实例依赖性查询复杂性，并且还通过对两个现实世界数据集（Tiny Imagenet和UT Zappos50k）的数值评估对幼稚实现显示了显着改善。
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 such as UCB, Thompson Sampling and Track-and-Stop developed in the closely related Multi-Armed Bandit problem, which adaptively decide which queries to send to the oracle and are able to solve the k-center 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 over naive implementations via numerical evaluations on two real-world datasets (Tiny ImageNet and UT Zappos50K).
