[Theory] REMINDER: 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>*


On Sun, Aug 22, 2021 at 3:30 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Tue, Aug 17, 2021 at 1:55 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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/20210823/3cdddce1/attachment-0001.html>