<div dir="ltr"><div dir="ltr"><div class="gmail_default"><div style="font-size:small"><div class="gmail_default"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, August 23rd, 2021 at <b>11:10 am CT</b></font></font><br></font></div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default"><div class="gmail_default"><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_thsbK_zKTtW5TU3qbrnsCQ" target="_blank">register in advance here</a></font></b><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Eden Chlamtáč, Ben Gurion University</font></p></div></div></div></div></div></div></div></div></div></div></div></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div style="font-size:small"><b><font face="arial, sans-serif"><br></font></b></div><div><font face="arial, sans-serif" style="font-size:small"><b>Title:</b> <span class="gmail_default">        </span>Cascaded Norms in Clustering<br><br></font><b style="font-size:small">Abstract:</b><br>Clustering is one of the most fundamental tasks in various areas such as machine learning and optimization. In theoretical computer science,<br>we are interested in the complexity of finding a "good" clustering, given a data set with some distance function, and a target number of<br>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<br>function which aggregates the distances of all input points from their respective nearest centers. This includes well-studied notions such as<br>k-Medians Clustering and k-Means Clustering.<br><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<br>also to counteract structural bias against marginalized groups. To this end, one first aggregates the costs incurred within the given<br>groups of interest, before aggregating the costs incurred by these groups.<br><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<br>represented by different weight functions. The objective we wish to minimize is the ell_q norm of the group costs, where each group cost<br>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<br>the point of view of approximation algorithms, giving algorithms for all values of p and q that smoothly interpolate between optimal and<br>near-optimal approximations for fundamental parameter settings of (p,q), such as (infinity, q), (p, infinity), and (p,p).<font face="arial, sans-serif" style="font-size:small"><br></font><font face="arial, sans-serif" style="font-size:small"><br></font></div><div style="font-size:small"><font face="arial, sans-serif">Based on joint work with Yury Makarychev and Ali Vakilian.</font></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div style="font-size:small"><font face="arial, sans-serif"><span class="gmail_default"><b>Hos</b></span><span class="gmail_default"><b>t:</b> <a href="mailto:yury@ttic.edu" target="_blank"><b>Yury Makarychev</b></a></span></font></div><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div></div><div dir="ltr"><div style="font-size:small"><div><font face="arial, sans-serif"><br></font></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Aug 17, 2021 at 1:55 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, August 23rd, 2021 at <b>11:10 am CT</b></font></font><br></font></div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_thsbK_zKTtW5TU3qbrnsCQ" target="_blank">register in advance here</a></font></b><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Eden Chlamtáč, Ben Gurion University</font></p></div></div></div></div></div></div></div></div></div></div></div></div><div><font face="arial, sans-serif"><br></font></div><div><b><font face="arial, sans-serif"><br></font></b></div><div><font face="arial, sans-serif"><b>Title:</b> <span class="gmail_default" style="font-size:small">        </span>Cascaded Norms in Clustering<br><br></font><b>Abstract:</b><br>Clustering is one of the most fundamental tasks in various areas such<span class="gmail_default" style="font-size:small"> </span>as machine learning and optimization. In theoretical computer science,<br>we are interested in the complexity of finding a "good" clustering,<span class="gmail_default" style="font-size:small"> </span>given a data set with some distance function, and a target number of<br>centers to choose from among the input points. Our goal is to find a<span class="gmail_default" style="font-size:small"> </span>set of centers (of the required cardinality) which minimizes some cost<br>function which aggregates the distances of all input points from their<span class="gmail_default" style="font-size:small"> </span>respective nearest centers. This includes well-studied notions such as<br>k-Medians Clustering and k-Means Clustering.<br><br>More recently, there has been a focus on 'fairness' in clustering, in<span class="gmail_default" style="font-size:small"> </span>which we want to take into consideration not only the global cost but<br>also to counteract structural bias against marginalized groups. To<span class="gmail_default" style="font-size:small"> </span>this end, one first aggregates the costs incurred within the given<br>groups of interest, before aggregating the costs incurred by these<span class="gmail_default" style="font-size:small"> </span>groups.<br><br>We focus on a very general notion of fairness - the input consists of<span class="gmail_default" style="font-size:small"> </span>data points, a target number of centers, and a collection of groups<br>represented by different weight functions. The objective we wish to<span class="gmail_default" style="font-size:small"> </span>minimize is the ell_q norm of the group costs, where each group cost<br>is computed as the (weighted) ell_p norm of distances of points in the<span class="gmail_default" style="font-size:small"> </span>group to their respective nearest centers. We study this problem from<br>the point of view of approximation algorithms, giving algorithms for<span class="gmail_default" style="font-size:small"> </span>all values of p and q that smoothly interpolate between optimal and<br>near-optimal approximations for fundamental parameter settings of<span class="gmail_default" style="font-size:small"> </span>(p,q), such as (infinity, q), (p, infinity), and (p,p).<font face="arial, sans-serif"><br></font><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">Based on joint work with Yury Makarychev and Ali Vakilian.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><span class="gmail_default"><b>Hos</b></span><span class="gmail_default"><b>t:</b> <a href="mailto:yury@ttic.edu" target="_blank"><b>Yury Makarychev</b></a></span></font></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><span class="gmail_default" style="font-size:small"><br></span></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><span class="gmail_default" style="font-size:small"></span></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div>
</blockquote></div>
</div>