<div dir="ltr"><div dir="ltr"><div class="gmail_default" style=""><div class="gmail_default" style=""><div class="gmail_default" style=""><font face="arial, sans-serif" style=""><b style="font-size:small">When</b>:    Monday, November 11<font size="1">th</font> from<b style="font-size:small;background-color:rgb(255,255,255)"> </b><b style="font-size:small;background-color:rgb(255,255,0)">9</b><b style="font-size:small"><span style="background-color:rgb(255,255,0)">:30am - 10:30am CT</span></b></font></div><div class="gmail_default" style="font-size:small"><div><b><font face="arial, sans-serif"><br></font></b></div><div><font face="arial, sans-serif"><b>Where</b>:   Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>               TTIC, 6045 S. Kenwood Avenue<br>               5th Floor, <b><u><font color="#000000">Room 530</font></u></b></font></div><div><font face="arial, sans-serif"><br><b>Virtually</b>: via <a href="https://uchicago.zoom.us/j/98071793141?pwd=EZ9xJtPzE8kkxUbXRZ0sqqRfzaCh7y.1" target="_blank"><b>Zoom</b></a> <br></font></div><div><font face="arial, sans-serif">                 </font></div><div><font face="arial, sans-serif"><b>Who:  </b>    Naren Sarayu Manoj, TTIC</font></div><div><font face="arial, sans-serif"><br></font></div></div><div class="gmail_default" style="font-size:small"><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><font face="arial, sans-serif"><b><br></b></font></div><div><font face="arial, sans-serif"><b>Title:</b> High-dimensional phenomena in graph clustering and linear regression</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Abstract: </b>Graph clustering and linear regression are foundational machine learning primitives. In addition to being ubiquitously used in practice, these problems are useful testbeds with which to evaluate new statistical and algorithmic ideas. In this talk, we will look at variants of these classical problems that demand new technical tools.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">In the first part, we will analyze the behavior of popular graph clustering algorithms in "helpfully" misspecified stochastic block models. This input model will help us understand whether algorithms used in practice have overfit to distributional assumptions on their input. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">In the second part, we will describe a family of geometric constructions that enables both improved sparsification results and a new algorithm for socially fair least squares regression. In the sparsification problem, we are interested in finding a small weighted subset of an objective function that approximates the objective well on all inputs. In the socially fair least squares regression problem, our goal is to find a parameter vector that gets a uniformly small squared error across several subproblems, each of which corresponds to data coming from some predefined subpopulation. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">More generally, my thesis explores applications of high-dimensional probability and geometry to problems in statistical and computational learning. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">This thesis is based on joint work with Aditya Bhaskara, Avrim Blum, Meghal Gupta, Agastya Vibhuti Jha, Gene Li, Michael Kapralov, Yury Makarychev, Davide Mazzali, Max Ovsiankin, Kumar Kshitij Patel, Aadirupa Saha, Weronika Wrosz-Kaminska, and Chloe Yang. The presentation is based on joint work with Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov, Davide Mazzali, Max Ovsiankin, Kumar Kshitij Patel, and Weronika Wrosz-Kaminska.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Thesis Committee: </b>Avrim Blum (co-chair), Michael Kapralov, Sepideh Mahabadi, Yury Makarychev (co-chair)</font></div></div></div><div style="font-size:small"></div><div style="font-size:small;outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div style="font-size:small;outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div></div><div><div dir="ltr" class="gmail_signature"><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, Rm 517</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><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></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, Oct 29, 2024 at 4:47 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">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 style="font-size:small"><div><div><font face="arial, sans-serif"><b>When</b>:    Monday, November 11 from<b style="background-color:rgb(255,255,0)"> 09</b><b><span style="background-color:rgb(255,255,0)">:30am - 10:30am CT</span></b></font></div><div><div><b><font face="arial, sans-serif"><br></font></b></div><div><font face="arial, sans-serif"><b>Where</b>:   Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>               TTIC, 6045 S. Kenwood Avenue<br>               5th Floor, <b><u><font color="#000000">Room 530</font></u></b></font></div><div><font face="arial, sans-serif"><br><b>Virtually</b>: via <a href="https://uchicago.zoom.us/j/98071793141?pwd=EZ9xJtPzE8kkxUbXRZ0sqqRfzaCh7y.1" target="_blank"><b>Zoom</b></a> <br></font></div><div><font face="arial, sans-serif">                 </font></div><div><font face="arial, sans-serif"><b>Who:  </b>    Naren Sarayu Manoj, TTIC</font></div><div><font face="arial, sans-serif"><br></font></div></div><div><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><font face="arial, sans-serif"><b><br></b></font></div><div><font face="arial, sans-serif"><b>Title:</b> High-dimensional phenomena in graph clustering and linear regression</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Abstract: </b>Graph clustering and linear regression are foundational machine learning primitives. In addition to being ubiquitously used in practice, these problems are useful testbeds with which to evaluate new statistical and algorithmic ideas. In this talk, we will look at variants of these classical problems that demand new technical tools.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">In the first part, we will analyze the behavior of popular graph clustering algorithms in "helpfully" misspecified stochastic block models. This input model will help us understand whether algorithms used in practice have overfit to distributional assumptions on their input. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">In the second part, we will describe a family of geometric constructions that enables both improved sparsification results and a new algorithm for socially fair least squares regression. In the sparsification problem, we are interested in finding a small weighted subset of an objective function that approximates the objective well on all inputs. In the socially fair least squares regression problem, our goal is to find a parameter vector that gets a uniformly small squared error across several subproblems, each of which corresponds to data coming from some predefined subpopulation. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">More generally, my thesis explores applications of high-dimensional probability and geometry to problems in statistical and computational learning. </font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">This thesis is based on joint work with Aditya Bhaskara, Avrim Blum, Meghal Gupta, Agastya Vibhuti Jha, Gene Li, Michael Kapralov, Yury Makarychev, Davide Mazzali, Max Ovsiankin, Kumar Kshitij Patel, Aadirupa Saha, Weronika Wrosz-Kaminska, and Chloe Yang. The presentation is based on joint work with Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov, Davide Mazzali, Max Ovsiankin, Kumar Kshitij Patel, and Weronika Wrosz-Kaminska.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Thesis Committee: </b>Avrim Blum (co-chair), Michael Kapralov, Sepideh Mahabadi, Yury Makarychev (co-chair)</font></div></div></div><div></div><div style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div></div><div><div dir="ltr" class="gmail_signature"><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, Rm 517</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><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></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></div>
</blockquote></div></div>