PIDSIA Seminar by Silvio Lattanzi, 22nd February
by Announcements of talks＠IDSIA
Speaker: Silvio Lattanzi, Research Scientist, Google Research Europe, Zurich
Title: Consistent k-Clustering
Abstract:
The study of online algorithms and competitive analysis provide a
solid foundation for studying the quality of irrevocable decision
making when the data arrives in an online manner. While in some
scenarios the decisions are indeed irrevocable, there are many
practical situations when changing a previous decision is not
impossible, but simply expensive.
In this work we formalize this notion and introduce the consistent
k-clustering problem. With points arriving online, the goal is to
maintain a constant approximate solution, while minimizing the number
of reclusterings necessary. We prove a lower bound, showing that Ω(k
log n) changes are necessary in the worst case, for a wide range of
objective functions. On the positive side, we give an algorithm that
needs only O(k^2 log^4 n) changes to maintain a constant competitive
solution. This is an exponential improvement on the naive solution of
reclustering at every time step. Finally, we show experimentally that
our approach performs much better than the theoretical bound, with the
number of changes growing approximately as O(log n).
Joint work with Sergei Vassilvitskii.
Bio:
Silvio is a Research Scientist at Google Research Europe since April
2017. Before he was in the NY Algorithm group at Google New York from
January 2011 to March 2017. He received his PhD from Sapienza
University of Rome under the supervision of Alessandro Panconesi.
During his PhD he interned twice at Google and once at Yahoo!
Research.
His research interests are in the areas of algorithms, machine
learning and information retrieval.
When: 22nd of February 2018, 12:00-13:00
Location: Manno, Galleria 1, 2nd floor, room G1-204
Registration: Pizza (or alternative food) and drinks will be offered
at the end of the talk. If you plan to attend, please register in a
timely fashion at the
following link so that we will have no shortage of food:
https://doodle.com/poll/uxnyzybwp7e5yyyy
7 years
- 1
- 0
Chris Schwiegelshohn: On the Local Structure of Stable Clustering Instances
by Announcements of talks＠IDSIA
Title: On the Local Structure of Stable Clustering Instances
Abstract:
As an optimization problem, clustering exhibits a striking
phenomenon: It is generally regarded as easy in practice, while theory
classifies it among the computationally intractable problems. To address
this dichotomy, research has identified a number of conditions a data set
must satisfy for a clustering to be (1) easily computable and (2)
meaningful.
In this talk we show that all previously proposed notions of struturedness
of a data set are fundamentally local properties, i.e. the global optimum
is in well defined sense close to a local optimum. As a corollary, this
implies that the Local Search heuristic has strong performance guarantees
for both the tasks of recovering the underlying optimal clustering and
obtaining a clustering of small cost.
Bio:
Chris Schwiegelshohn is currently a post-doc in Sapienza, University
of Rome. He did his Phd in Dortmund with a thesis on "Algorithms for
Large-Scale Graph and Clustering Problems". Chris' research interests
include streaming and approximation algorithms as well as machine
learning.
Date: 8th of February 2018, 12:00-13:00
Location: Manno, Galleria 1, 2nd floor, room G1-204
Registration: Pizza and drinks will be offered at the end of the talk.
If you plan to attend, please register in a timely fashion at the
following link so that we will have no shortage of food:
https://doodle.com/poll/sp294b469e9x44bf <https://doodle.com/poll/sp294b469e9x44bf>
7 years, 1 month
- 1
- 0
- ← Newer
- 1
- Older →