<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:"Courier New";}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>INSTITUTE FOR ADVANCED STUDY<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>School of Mathematics<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Princeton, NJ 08540<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><b><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Mathematics Seminars<o:p></o:p></span></b></pre><pre><b><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Week of April 16, 2018<o:p></o:p></span></b></pre><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><pre><b><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Thursday, April 19<o:p></o:p></span></b></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Seminar on Theoretical Machine Learning<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Topic: Online Improper Learning with an Approximation Oracle<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Speaker: Zhiyuan Li, Princeton University<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Time/Room: 12:15pm - 1:45pm/White-Levy Room*<o:p></o:p></span></pre><pre><span style='font-size:11.0pt;font-family:"Times New Roman",serif'>Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=136912">http://www.math.ias.edu/seminars/abstract?event=136912</a><o:p></o:p></span></pre><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'>We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require only poly-logarithmically many calls to the approximation oracle per iteration. Furthermore, these algorithms apply to the more general improper learning problems. In the bandit setting, our algorithm also significantly improves the best previously known oracle complexity while maintaining the same regret.<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'> <o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'>Joint work with Elad Hazan, Wei Hu, Yuanzhi Li.<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:"Times New Roman",serif'>---------------------------------<o:p></o:p></span></p><pre><span style='font-size:9.0pt;font-family:"Times New Roman",serif'>*</span><span style='font-family:"Times New Roman",serif'>Please help us preserve our White Levy Room privileges by maintaining the Idea Board (DaLite markers only; clean when finished).<o:p></o:p></span></pre><p class=MsoNormal><span style='font-family:"Times New Roman",serif'>IAS Math Seminars Home Page:<br><a href="http://www.math.ias.edu/seminars">http://www.math.ias.edu/seminars</a><o:p></o:p></span></p></div></body></html>