Timezone: »
The medoid of a set of n points is the point in the set that minimizes the sum of distances to other points. It can be determined exactly in O(n^2) time by computing the distances between all pairs of points. Previous works show that one can significantly reduce the number of distance computations needed by adaptively querying distances. The resulting randomized algorithm is obtained by a direct conversion of the computation problem to a multi-armed bandit statistical inference problem. In this work, we show that we can better exploit the structure of the underlying computation problem by modifying the traditional bandit sampling strategy and using it in conjunction with a suitably chosen multi-armed bandit algorithm. Four to five orders of magnitude gains over exact computation are obtained on real data, in terms of both number of distance computations needed and wall clock time. Theoretical results are obtained to quantify such gains in terms of data parameters. Our code is publicly available online at https://github.com/TavorB/Correlated-Sequential-Halving.
Author Information
Tavor Baharav (Stanford University)
I am a second year PhD student in Electrical Engineering at Stanford University working with Professor David Tse, recently on developing fast (near linear time) randomized algorithms using techniques from multi-armed bandits. I am grateful to be supported by the NSF Graduate Research Fellowship and the Stanford Graduate Fellowship (SGF). I graduated from UC Berkeley in May 2018 where I studied Electrical Engineering and Computer Science. In my time there, I was fortunate to get the chance to work with Professor Kannan Ramchandran on coding theory and its applications to distributed computing. My current research focus is on constructing algorithms that adapt to problem instance difficulty, and more broadly in randomized algorithms, machine learning, multi-armed bandits, and their applications in engineering and computational biology problems.
David Tse (Stanford University)
More from the Same Authors
-
2020 Poster: Adaptive Learning of Rank-One Models for Efficient Pairwise Sequence Alignment »
Govinda Kamath · Tavor Baharav · Ilan Shomorony -
2018 Poster: Porcupine Neural Networks: Approximating Neural Network Landscapes »
Soheil Feizi · Hamid Javadi · Jesse Zhang · David Tse -
2018 Poster: A Convex Duality Framework for GANs »
Farzan Farnia · David Tse -
2017 Poster: Tensor Biclustering »
Soheil Feizi · Hamid Javadi · David Tse -
2017 Poster: NeuralFDR: Learning Discovery Thresholds from Hypothesis Features »
Fei Xia · Martin J Zhang · James Zou · David Tse -
2016 Poster: A Minimax Approach to Supervised Learning »
Farzan Farnia · David Tse -
2015 Poster: Discrete Rényi Classifiers »
Meisam Razaviyayn · Farzan Farnia · David Tse