<div dir="ltr"><div style="font-size:12.8px"><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:     <span class="gmail-m_-5917841537509666441gmail-m_-3568727914368024249gmail-il">Friday</span>, October 28th at noon </span><br></font></div><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 style="font-size:12.8px"><span style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Who:       Dan Garber; TTIC</font></span></div><div><span style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></span></div></div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Title: Faster Projection-free Optimization and Learning</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract:</div><div style="font-size:12.8px">Projected gradient descent (PGD), and its close variants, are often considered the methods of choice for solving a very large variety of machine learning optimization problems, including empirical risk minimization problems, stochastic optimization, and online convex optimization. This is not surprising, since PGD is often optimal in a very appealing information-theoretic sense. However, for many problems PGD is infeasible both in theory and practice since each step requires to compute an orthogonal projection onto the feasible set. In many important cases, such as when the feasible set is a non-trivial polytope, or a convex surrogate for a low-rank structure, computing the projection is computationally inefficient in high-dimensional settings. An alternative is the conditional gradient method (aka Frank-Wolfe algorithm) that replaces the expensive projection step with a linear optimization step over the feasible set. Indeed in many problems of interest, the linear optimization step admits much more efficient algorithms than the projection step, which is the reason to the substantial regained interest in this method in the past decade. On the downside, the convergence rates of the CG method often fall behind that of PGD and its variants. </div><div style="font-size:12.8px">In this talk I will survey an ongoing effort to design CG variants that on one hand enjoy the cheap iteration complexity of the original method, and on the other hand converge provably faster, and are applicable to a wider variety of machine learning settings. In particular I will focus on the cases in which the feasible set is either a polytope or a convex surrogate for low-rank matrices. Results will be demonstrated on applications including: LASSO, video co-localization, optical character recognition, matrix completion, and multi-class classification.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">******************************<wbr>******************************<wbr>******************************<wbr>**********************</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div class="gmail_default" style="font-size:12.8px"><b><font face="arial, helvetica, sans-serif">Research at TTIC Seminar Series</font></b></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank">https://groups.google.co<wbr>m/a/ttic.edu/group/<span class="gmail-m_-5917841537509666441gmail-m_-3568727914368024249gmail-m_-7538648194147727859gmail-il"><span class="gmail-m_-5917841537509666441gmail-m_-3568727914368024249gmail-il">talks</span></span>/subsc<wbr>ribe</a></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank">http://www.ttic.edu/tticse<wbr>minar.php</a>.</font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank">nati@ttic.edu</a> </font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></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 Thu, Oct 27, 2016 at 2:52 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 style="font-size:12.8px"><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:     <span class="m_-5917841537509666441gmail-m_-3568727914368024249gmail-il">Friday</span>, October 28th at noon </span><br></font></div><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 style="font-size:12.8px"><span style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Who:       Dan Garber; TTIC</font></span></div><div><span style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></span></div></div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Title: Faster Projection-free Optimization and Learning</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract:</div><div style="font-size:12.8px">Projected gradient descent (PGD), and its close variants, are often considered the methods of choice for solving a very large variety of machine learning optimization problems, including empirical risk minimization problems, stochastic optimization, and online convex optimization. This is not surprising, since PGD is often optimal in a very appealing information-theoretic sense. However, for many problems PGD is infeasible both in theory and practice since each step requires to compute an orthogonal projection onto the feasible set. In many important cases, such as when the feasible set is a non-trivial polytope, or a convex surrogate for a low-rank structure, computing the projection is computationally inefficient in high-dimensional settings. An alternative is the conditional gradient method (aka Frank-Wolfe algorithm) that replaces the expensive projection step with a linear optimization step over the feasible set. Indeed in many problems of interest, the linear optimization step admits much more efficient algorithms than the projection step, which is the reason to the substantial regained interest in this method in the past decade. On the downside, the convergence rates of the CG method often fall behind that of PGD and its variants. </div><div style="font-size:12.8px">In this talk I will survey an ongoing effort to design CG variants that on one hand enjoy the cheap iteration complexity of the original method, and on the other hand converge provably faster, and are applicable to a wider variety of machine learning settings. In particular I will focus on the cases in which the feasible set is either a polytope or a convex surrogate for low-rank matrices. Results will be demonstrated on applications including: LASSO, video co-localization, optical character recognition, matrix completion, and multi-class classification.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">******************************<wbr>******************************<wbr>******************************<wbr>**********************</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div class="gmail_default" style="font-size:12.8px"><b><font face="arial, helvetica, sans-serif">Research at TTIC Seminar Series</font></b></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank">https://groups.google.co<wbr>m/a/ttic.edu/group/<span class="m_-5917841537509666441gmail-m_-3568727914368024249gmail-m_-7538648194147727859gmail-il"><span class="m_-5917841537509666441gmail-m_-3568727914368024249gmail-il">talks</span></span>/subsc<wbr>ribe</a></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank">http://www.ttic.edu/tticse<wbr>minar.php</a>.</font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank">nati@ttic.edu</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"><br></div><div><div class="m_-5917841537509666441gmail_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:%28773%29%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:%28773%29%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>