Timezone: »
We study k-median clustering under the sequential no-substitution setting. In this setting, a data stream is sequentially observed, and some of the points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. We give the first algorithm for this setting that obtains a constant approximation factor on the optimal cost under a random arrival order, an exponential improvement over previous work. This is also the first constant approximation guarantee that holds without any structural assumptions on the input data. Moreover, the number of selected centers is only quasi-linear in k. Our algorithm and analysis are based on a careful cost estimation that avoids outliers, a new concept of a linear bin division, and a multi-scale approach to center selection.
Author Information
Tom Hess (Ben-Gurion University of the Negev)
Michal Moshkovitz (UCSD)
Sivan Sabato (Ben-Gurion University of the Negev)
More from the Same Authors
-
2020 : Unexpected effects of online k-means clustering »
Michal Moshkovitz -
2020 Poster: Towards a Combinatorial Characterization of Bounded-Memory Learning »
Alon Gonen · Shachar Lovett · Michal Moshkovitz -
2019 Poster: Epsilon-Best-Arm Identification in Pay-Per-Reward Multi-Armed Bandits »
Sivan Sabato -
2018 Poster: Learning from discriminative feature feedback »
Sanjoy Dasgupta · Sivan Sabato · Nicholas Roberts · Akansha Dey -
2017 Poster: Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions »
Aryeh Kontorovich · Sivan Sabato · Roi Weiss -
2016 Poster: Active Nearest-Neighbor Learning in Metric Spaces »
Aryeh Kontorovich · Sivan Sabato · Ruth Urner -
2014 Poster: Active Regression by Stratification »
Sivan Sabato · Remi Munos -
2013 Poster: Auditing: Active Learning with Outcome-Dependent Query Costs »
Sivan Sabato · Anand D Sarwate · Nati Srebro -
2012 Poster: Multiclass Learning Approaches: A Theoretical Comparison with Implications »
Amit Daniely · Sivan Sabato · Shai Shalev-Shwartz -
2012 Spotlight: Multiclass Learning Approaches: A Theoretical Comparison with Implications »
Amit Daniely · Sivan Sabato · Shai Shalev-Shwartz -
2010 Poster: Tight Sample Complexity of Large-Margin Learning »
Sivan Sabato · Nati Srebro · Naftali Tishby