<div dir="ltr"><div><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, August 7th at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:       </font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Aravindan Vijayaraghavan, Northwestern University</span></font></div></div></div><div style="font-size:medium;color:rgb(0,0,0)"><font face="arial, helvetica, sans-serif"><br><br></font></div><div style="font-size:medium;color:rgb(0,0,0)"><p style="margin-top:0px;margin-bottom:0px;font-size:16px"><font face="arial, helvetica, sans-serif"><span style="color:rgb(33,33,33);font-size:13.3333px">Title:       Learning Mixtures of Well-Separated Gaussians</span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span class="gmail-m_1203820965003856359gmail-m_-5123924791506305975highlight" id="gmail-m_1203820965003856359gmail-m_-51239247915063059750.41218504134581857" name="searchHitInReadingPane" style="color:rgb(33,33,33);font-size:13.3333px">Abstract</span><span style="color:rgb(33,33,33);font-size:13.3333px">:</span><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">Mixtures of spherical Gaussians are among the most widely used statistical models for clustering. We will consider the problem of efficiently learning a mixture of a large number of spherical Gaussian components, when the components of the mixture are well-separated. Here, we are given samples from a mixture of k spherical Gaussians with parameters corresponding to the means, variances and mixing weights for each of the components. The goal is to estimate the parameters up to accuracy \delta using \poly(k,d, 1/\delta) samples. </span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">There is a significant gap between the best known upper bounds and lower bounds in the amount of separation required for efficiently learning a mixture of k spherical Gaussians. </span><span style="color:rgb(33,33,33);font-size:13.3333px">We will consider the following question: what is the minimum order of separation needed for learning a mixture of spherical Gaussians with polynomial samples?</span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">In this talk, I will give a new iterative algorithm for learning mixtures of k spherical Gaussians, and give sample complexity lower bounds that together essentially characterize the optimal order of separation between components that is needed to learn a mixture of k spherical Gaussians with polynomial samples.</span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">This is based on joint work with Oded Regev.</span><br></font></p><p style="margin-top:0px;margin-bottom:0px;font-size:16px"><font face="arial, helvetica, sans-serif"><span style="color:rgb(33,33,33);font-size:13.3333px"><br></span></font></p><div><span style="color:rgb(33,33,33);font-size:13.3333px"><font face="arial, helvetica, sans-serif"><br></font></span></div></div></div><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Host:<a href="mailto:yury@ttic.edu" target="_blank"> </a><a href="mailto:yury@ttic.edu" target="_blank">Yury Makarychev</a></font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px"><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">For more information on the </span><span style="font-size:12.8px"><span class="gmail-m_1203820965003856359gmail-il">colloquium</span></span><span style="font-size:12.8px"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" target="_blank" style="font-size:12.8px">http://www.ttic.edu/colloq<wbr>uium.php</a></font></div><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
<br><div class="gmail_quote">On Mon, Jul 31, 2017 at 3:33 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, August 7th at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><font style="font-size:12.8px">Who:       </font></font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Aravindan Vijayaraghavan, Northwestern University</span></font></div></div></div><div style="font-size:medium;color:rgb(0,0,0)"><font face="arial, helvetica, sans-serif"><br><br></font></div><div style="font-size:medium;color:rgb(0,0,0)"><p style="margin-top:0px;margin-bottom:0px;font-size:16px"><font face="arial, helvetica, sans-serif"><span style="color:rgb(33,33,33);font-size:13.3333px">Title:       Learning Mixtures of Well-Separated Gaussians</span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="background-color:rgb(255,255,255)"><span class="m_1203820965003856359gmail-m_-5123924791506305975highlight" id="m_1203820965003856359gmail-m_-51239247915063059750.41218504134581857" name="searchHitInReadingPane" style="color:rgb(33,33,33);font-size:13.3333px">Abstract</span><span style="color:rgb(33,33,33);font-size:13.3333px">:</span></span><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">Mixtures of spherical Gaussians are among the most widely used statistical models for clustering. We will consider the problem of efficiently learning a mixture of a large number of spherical Gaussian components, when the components of the mixture are well-separated. Here, we are given samples from a mixture of k spherical Gaussians with parameters corresponding to the means, variances and mixing weights for each of the components. The goal is to estimate the parameters up to accuracy \delta using \poly(k,d, 1/\delta) samples. </span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">There is a significant gap between the best known upper bounds and lower bounds in the amount of separation required for efficiently learning a mixture of k spherical Gaussians. </span><span style="color:rgb(33,33,33);font-size:13.3333px">We will consider the following question: what is the minimum order of separation needed for learning a mixture of spherical Gaussians with polynomial samples?</span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">In this talk, I will give a new iterative algorithm for learning mixtures of k spherical Gaussians, and give sample complexity lower bounds that together essentially characterize the optimal order of separation between components that is needed to learn a mixture of k spherical Gaussians with polynomial samples.</span><br style="color:rgb(33,33,33);font-size:13.3333px"><br style="color:rgb(33,33,33);font-size:13.3333px"><span style="color:rgb(33,33,33);font-size:13.3333px">This is based on joint work with Oded Regev.</span><br></font></p><p style="margin-top:0px;margin-bottom:0px;font-size:16px"><font face="arial, helvetica, sans-serif"><span style="color:rgb(33,33,33);font-size:13.3333px"><br></span></font></p><div><span style="color:rgb(33,33,33);font-size:13.3333px"><font face="arial, helvetica, sans-serif"><br></font></span></div></div></div><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Host:<a href="mailto:yury@ttic.edu" target="_blank"> </a><a href="mailto:yury@ttic.edu" target="_blank">Yury Makarychev</a></font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-size:13.3333px"><font face="arial, helvetica, sans-serif"><br></font></span></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">For more information on the </span><span style="font-size:12.8px"><span class="m_1203820965003856359gmail-il">colloquium</span></span><span style="font-size:12.8px"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" style="font-size:12.8px" target="_blank">http://www.ttic.edu/colloq<wbr>uium.php</a></font></div><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:12.8px"><br></div></div></div><div><div class="m_1203820965003856359gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:<a href="tel:(773)%20834-1757" value="+17738341757" target="_blank">(773) 834-1757</a></font></i></div><div><i><font face="arial, helvetica, sans-serif">f: <a href="tel:(773)%20357-6970" value="+17733576970" target="_blank">(773) 357-6970</a></font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
</div>
</blockquote></div><br></div></div>