[Theory] 8/23 TTIC Colloquium: Eden Chlamtáč, Ben Gurion University

[Mary Marre]

*When:*      Monday, August 23rd, 2021 at *11:10 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_thsbK_zKTtW5TU3qbrnsCQ>*)



*Who: *       Eden Chlamtáč, Ben Gurion University


*Title:*         Cascaded Norms in Clustering

*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.

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.

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 ell_q norm of the group costs, where each group cost
is computed as the (weighted) ell_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).

Based on joint work with Yury Makarychev and Ali Vakilian.


*Hos**t:* *Yury Makarychev* <yury at ttic.edu>

Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210817/40ff97e2/attachment.html>