<div dir="ltr"><div class="gmail_default"><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><b>When: </b>   Tuesday, April 9th <span class="m_3990007417496972239gmail-m_7407195392352708254gmail-m_4202911429418909403gmail-m_4607447733685507446gmail-m_-4272534296826282993gmail-m_-1945979869721099263gmail-m_-3723170228854223066m_6264176026242749646gmail-m_-1990911872965724707gmail-m_-648026695923463142gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il">at</span> 11:00 AM</font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="m_3990007417496972239gmail-m_7407195392352708254gmail-m_4202911429418909403gmail-m_4607447733685507446gmail-m_-4272534296826282993gmail-m_-1945979869721099263gmail-m_-3723170228854223066m_6264176026242749646gmail-m_-1990911872965724707gmail-m_-648026695923463142gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="m_3990007417496972239gmail-m_7407195392352708254gmail-m_4202911429418909403gmail-m_4607447733685507446gmail-m_-4272534296826282993gmail-m_-1945979869721099263gmail-m_-3723170228854223066m_6264176026242749646gmail-m_-1990911872965724707gmail-m_-648026695923463142gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="m_3990007417496972239gmail-m_7407195392352708254gmail-m_4202911429418909403gmail-m_4607447733685507446gmail-m_-4272534296826282993gmail-m_-1945979869721099263gmail-m_-3723170228854223066m_6264176026242749646gmail-m_-1990911872965724707gmail-m_-648026695923463142gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div class="gmail_default"><font face="arial, helvetica, sans-serif"><br></font></div><font face="arial, helvetica, sans-serif"><span style="font-weight:bold;color:rgb(0,0,0)">Who:</span><span style="color:rgb(0,0,0)">       </span></font><a class="m_3990007417496972239gmail-m_7407195392352708254gmail-Oux49" style="color:rgb(32,33,36);line-height:28px;overflow:hidden;white-space:nowrap"><font face="arial, helvetica, sans-serif"><span class="m_3990007417496972239gmail-il">Dmitrii</span> Ostrovskii, </font></a><span style="color:rgb(51,51,51)"><font face="arial, helvetica, sans-serif">Inria Paris</font></span><br clear="all"></div><div class="gmail_default"><br></div><div class="gmail_default"><b>Title:</b>       <font face="arial, helvetica, sans-serif"><span style="color:rgb(0,0,0);white-space:pre-wrap">On Algorithmic Efficiency and Statistical Optimality in Empirical Risk </span>M</font><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;white-space:pre-wrap">inimization</span>  <br><br><b>Abstract:</b> <span style="background-color:transparent;white-space:pre-wrap;color:rgb(0,0,0)"><font face="arial, helvetica, sans-serif">In this talk we will view the standard empirical risk minimization (ERM) from two different perspectives, focusing first on computationally efficient procedures to find approximate minimizers, and then on the statistical optimality of ERM itself as an idealized procedure. </font></span></div><div class="gmail_default"><span style="background-color:transparent;white-space:pre-wrap;color:rgb(0,0,0)"><font face="arial, helvetica, sans-serif"><br></font></span></div><p dir="ltr" style="color:rgb(0,0,0);line-height:1.38;margin:0px"><font face="arial, helvetica, sans-serif"><span style="background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">In the first part of the talk, I will show how stochastic mirror descent can be exploited to efficiently train l1-regularized multi-class linear classifiers, assuming a large number $k$ of classes, sample size $n$, and number of features $d$. We consider the class of losses with explicit dual representation, focusing on the multiclass hinge and logistic losses. </span><span style="background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">I will start with a common observation that regularized ERM with such losses can be recast as a convex-concave saddle-point problem (CCSPP) with a quasi-bilinear objective and specific geometry of the primal and dual feasible sets. Such problems can be solved via primal-dual algorithms such as mirror descent and mirror prox, and in the case of quasi-bilinear CCSPPs both these algorithms can be accelerated via randomization. However, it has remained unclear how to choose the proximal geometry in these algorithms to control the additional loss of accuracy due to randomization. We fill in this gap, showing that appropriately randomized mirror descent with a particular choice of geometry converges essentially at the same speed (in terms of the number of iterations) as its deterministic counterpart, while having a drastically reduced iteration cost. In particular, we achieve the *sublinear* iteration cost $O(d+n+k)$ for the multiclass </span><span style="background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">hinge loss, and I will also provide insight on how this could be extended to the multiclass logistic loss.</span></font></p><p dir="ltr" style="color:rgb(0,0,0);line-height:1.38;margin:0px"><font face="arial, helvetica, sans-serif"><span style="background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><br></span></font></p><p dir="ltr" style="color:rgb(0,0,0);line-height:1.38;margin:0px"><span style="background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, helvetica, sans-serif">The second part of the talk will be focused on the statistical optimality of ERM. The inspiration comes from the classical statistical theory: the rate $O(d/n)$ for the excess risk of ERM (or M-estimators in the statistical terminology) holds under very general conditions when $d$ is fixed, and $n$ tends to infinity, and is optimal in this regime. The learning problem in this regime is fully characterized by the local quadratic approximation of the excess risk in the true minimizer. However, extending this result to the finite-sample regime is non-trivial, as it requires to localize the estimator to the right neighborhood of the true optimum, for which one has to impose some *global* conditions on the excess risk. We will see that such global assumptions can be avoided when using self-concordant cost functions (in the sense of Nesterov and Nemirovski (1994) or Bach (2010)) which includes the logistic loss and some robust regression losses. Combining self-concordance with some covariance estimation results allows to localize the M-estimator to the constant-radius Dikin ellipsoid of the true minimizer, which implies $O(d/n)$ rate already when $n \gg d$. We will then briefly consider l1- and l2-penalized cases.</font></span></p><div class="gmail_default"><br></div><div class="gmail_default"><b>Host: </b><a href="mailto:nati@ttic.edu" target="_blank">Nati Srebro</a></div><div><br></div>-- <br><div dir="ltr" class="m_3990007417496972239gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 510</i></div><div><font color="#0b5394"><i>Chicago, IL 60637</i></font></div><div><font color="#0b5394"><i>773-702-5370</i></font></div></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div>