Seminars

View all Seminars  |  Download ICal for this event

Cascaded Norms in Clustering

Series: Theory Seminar

Speaker: Eden Chlamtáč, Assistant professor, Department of Computer Science, Ben Gurion University.

Date/Time: Feb 04 11:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
Clustering is one of the most fundamental tasks in various areas such as machine learning and optimization. In theoretical computer science, we are interested in the complexity of finding a good clustering, given a data set with some distance function, and a target number of centers to choose from among the input points. Our goal is to find a set of centers (of the required cardinality) which minimizes some cost function which aggregates the distances of all input points from their respective nearest centers. This includes well-studied notions such as k-Medians Clustering and k-Means Clustering.
<br>
More recently, there has been a focus on fairness in clustering, in which we want to take into consideration not only the global cost but also to counteract structural bias against marginalized groups. To this end, one first aggregates the costs incurred within the given groups of interest, before aggregating the costs incurred by these groups.
<br>
We focus on a very general notion of fairness - the input consists of data points, a target number of centers, and a collection of groups represented by different weight functions. The objective we wish to minimize is the L_q norm of the group costs, where each group cost is computed as the (weighted) L_p norm of distances of points in the group to their respective nearest centers. We study this problem from the point of view of approximation algorithms, giving algorithms for all values of p and q that smoothly interpolate between optimal and near-optimal approximations for fundamental parameter settings of (p,q), such as (infinity, q), (p, infinity), and (p,p).
<br>
<br>
Based on joint work with Yury Makarychev and Ali Vakilian.
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link
<br>
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Anand Louis