<html><body><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000"><div><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;">Karan Singh&nbsp;will present his generals exam </span><span class="Object" role="link" id="OBJ_PREFIX_DWT9371_com_zimbra_date" style="color: #005a95; text-decoration: none; cursor: pointer; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" data-mce-style="color: #005a95; text-decoration: none; cursor: pointer; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">Monday, May 15</span><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;">, 2017 at 1pm in CS 401.</span><br style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"><br style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;">The members of his committee are:</span><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;">&nbsp;</span><span style="color: #000000; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; font-family: 'times new roman'; font-size: 14.16px; float: none; display: inline !important;" data-mce-style="color: #000000; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; font-family: 'times new roman'; font-size: 14.16px; float: none; display: inline !important;">Elad Hazan (Advisor), Sanjeev Arora, and Ran Raz</span><br style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"><br style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;" data-mce-style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial; display: inline !important; float: none;">Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below.</span></div><div data-marker="__QUOTED_TEXT__"><div dir="ltr"><div><div>
















<div style="border-top: none; border-right: none; border-left: none; border-bottom: 1pt solid windowtext; padding: 0in 0in 1pt;" data-mce-style="border-top: none; border-right: none; border-left: none; border-bottom: 1pt solid windowtext; padding: 0in 0in 1pt;">

<h2 style="border: none; padding: 0in;" data-mce-style="border: none; padding: 0in;"><span style="color: #62051b; font-weight: normal;" data-mce-style="color: #62051b; font-weight: normal;"><span style="color: windowtext;" data-mce-style="color: windowtext;">Random Perturbations in Online Learning</span></span><span style="color: #62051b; font-weight: normal;" data-mce-style="color: #62051b; font-weight: normal;"><span></span></span></h2>

</div>

<p class="gmail-MsoTitle"><span class="gmail-Heading3Char"><span style="font-size: 14pt; font-weight: normal;" data-mce-style="font-size: 14pt; font-weight: normal;">Adaptivity, Privacy, and Efficiency</span></span><span style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;">Explicit regularization (via adding a convex regularizer) is the
mainstay of (distribution-free) statistically efficient learning algorithms. <i>[Kalai,
Vempala 2002]</i>, also <i>[Hannan 1957]</i>, present an alternative framework
(FTPL) for sequential prediction, based on randomly perturbing the history of
losses on previous predictions. While these perturbation-based algorithms admit
computationally efficient implementations, discounting some simple settings,
their statistical efficiency is not well understood (vis-a-vis regularization).
Building on some recent progress towards this understanding, we present three
compelling cases for the use of perturbation methods for online learning that
improve upon the state-of-the-art. The theme unifying the three applications is
the utilization of structured noise for perturbations, an element hence so far
not employed by the previous analyses.</span><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"><br>
<br>
<span style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Adapting to the Inherent
Structure</span></span></span><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;">For the problem of expert advice, when the loss vectors are restricted
to some unknown d-dimensional subspace (fondly referred to as <b>low-rank experts</b>), we demonstrate that
a natural variant of FTPL achieves a regret of <b>d^0.75√T</b>, crucially independent of the number of experts. This
improves on the previous best of d√T achieved by regularization-based schemes
due to <i>[Hazan, Koren, Livni, Mansour 2016]</i>.<span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"><br>
</span></span><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Privacy for Free</span></span></span><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;">We design differentially private algorithms for the problem of online
linear optimization in the full information and bandit settings with <b>optimal √T regret bounds</b>. In the
full-information setting, our results demonstrate that <i><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;">differential
privacy may be ensured for free</span></i> -- in particular, <b>the regret bounds scale as √T+1/ε</b>. <i><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;">Notably, this phenomenon
was unacknowledged even in the (weaker) setting of statistical learning.</span></i>
This separation of the extra (additive) regret suffered to ensure privacy from
the non-private regret bound is permitted through a reinterpretation of
privacy-aimed noise addition schemes as random perturbations of the objective.
For bandit linear optimization, and as a special case, for non-stochastic
multi-armed bandits, the proposed algorithm achieves a regret of √T/ε, while
the previously best-known regret bound was T^0.75/ε.</span><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"><br>
<br>
<span style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Efficient
Algorithms for Contextual Learning</span></span></span><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="font-size: 11pt; color: black; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;">We devise the first algorithm for transductive <b>contextual learning</b> that enjoys <i><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;">optimal √T regret guarantees
while admitting computationally efficient implementations</span></i> at run-time.
In contrast, previous works either obtain sub-optimal regret bounds or require
explicit enumeration of the policy class on every iteration. Contextual
learning (with partial feedback) is a strict, far-reaching generalization of the
Markov Decision Process model for policy-based reinforcement learning. Contextual
learning offers the same sample complexity bounds without placing any
assumption on the underlying state dynamics (for example, conditional Markovian
evolution of states).<span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"><br>
<span style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;">The first and third results are due to
collaborations with my advisor <b>Elad
Hazan</b> (Princeton). The second result is joint work with <b>Naman Agarwal</b> (Princeton).<span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><br></p><p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><br></p><div style="border-top: none; border-right: none; border-left: none; border-bottom: 1pt solid windowtext; padding: 0in 0in 1pt; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="border-top: none; border-right: none; border-left: none; border-bottom: 1pt solid windowtext; padding: 0in 0in 1pt; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;">

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial; border: none; padding: 0in;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial; border: none; padding: 0in;"><span class="gmail-Heading2Char"><span style="font-size: 17pt; color: #62051b; font-weight: normal;" data-mce-style="font-size: 17pt; color: #62051b; font-weight: normal;"><span style="color: windowtext;" data-mce-style="color: windowtext;">Reading List</span></span></span><b><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"><span></span></span></b></p>

</div>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading3Char"><span style="font-size: 14pt;" data-mce-style="font-size: 14pt;">Texts<br>
</span></span><i><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;">Bubeck,
Cesa-Bianchi</span></i><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;">:
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.<br>
<i>Hazan</i>: Introduction to Online Convex Optimization.<br>
<i>Shalev-Shwartz</i>: Online Learning and Online Convex Optimization.<span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;">Szepesvári:</span></i><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"> Algorithms for Reinforcement Learning.<span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span style="font-size: 11pt; color: black;" data-mce-style="font-size: 11pt; color: black;"><br>
</span><span class="gmail-Heading3Char"><span style="font-size: 14pt;" data-mce-style="font-size: 14pt;">Papers<span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Contextual Learning<span></span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Dudik, Hsu, Kale, Karampatziakis,
Langford, Reyzin, Zhang</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Efficient optimal learning for
contextual bandits. <b>UAI 2011</b></span><span class="gmail-Heading4Char"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Kakade, Kalai:</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;"> From batch to transductive online learning. <b>NIPS 2005</b><br>
<i>Langford, Zhang</i>: The epoch-greedy algorithm for multi-armed bandits with
side information. <b>NIPS 2008</b><br>
<i>Rakhlin, Sridharan</i>: BISTRO: An efficient relaxation-based method for
contextual bandits. <b>ICML 2016</b><br>
<i>Syrgkanis, Krishnamurthy, Schapire</i>: Efficient Algorithms for Adversarial
Contextual Learning. <b>ICML 2016</b><span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;"><span>&nbsp;</span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Imitation Learning<span></span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Chang, Krishnamurthy, Agarwal,
Daume, Langford</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Learning to search better than
your teacher. <b>ICML 2015<span></span></b></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Ross, Bagnell:</span></i><b><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;"> </span></b><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Efficient Reductions for Imitation Learning.<b> AISTATS 2010<span></span></b></span></p>

<p class="MsoNormal"><i><span style="font-size: 11pt; line-height: 120%;" data-mce-style="font-size: 11pt; line-height: 120%;">Ross,
Gordon, Bagnell</span></i><span style="font-size: 11pt; line-height: 120%;" data-mce-style="font-size: 11pt; line-height: 120%;">: A
Reduction of Imitation Learning and Structured Prediction to No-Regret Online
Learning. <b>AISTATS 2011</b></span><span class="gmail-Heading4Char"><span style="font-size: 12pt; line-height: 120%;" data-mce-style="font-size: 12pt; line-height: 120%;"><span></span></span></span></p><p class="MsoNormal"><span style="font-size: 11pt; line-height: 120%;" data-mce-style="font-size: 11pt; line-height: 120%;"><b><br></b></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Learning with
Partial Information<span></span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Bubeck, Cesa-Bianchi, Kakade,
Mannor, Srebro, Williamson</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Towards Minimax Policies for
Online Linear Optimization with Bandit Feedback. <b>COLT 2012</b><br>
<i>Dani, Hayes, Kakade:</i> The Price of Bandit Information for Online Optimization.
<b>NIPS 2007<span></span></b></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Neu, Bartók</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Importance weighting without importance weights: An efficient
algorithm for combinatorial semi-bandits. <b>JMLR
2016</b><br>
<br>
</span><span class="gmail-Heading4Char"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Differentially
Private Online Learning<span></span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Dwork, Naor, Pitassi, Rothblum</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Differential privacy under continual observation. <b>STOC 2010</b><span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Jain, Kothari, Thakurta</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Differentially Private Online Learning. <b>COLT 2012</b></span><span class="gmail-Heading4Char"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Smith, Thakurta</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: (Nearly) optimal algorithms for private online learning in
full-information and bandit settings. <b>NIPS
2013</b></span><span class="gmail-Heading4Char"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;"><span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><br></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">Perturbation Schemes
in Statistics</span></span></span></p><p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Abernethy, Lee, Sinha, Tewari</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Online Linear Optimization via Smoothing. <b>COLT 2014</b></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Hazan, Jaakkola</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: On the Partition Function and Random Maximum A-Posteriori
Perturbations. <b>ICML 2012<span></span></b></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;"><span>&nbsp;</span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><span class="gmail-Heading4Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt;" data-mce-style="font-size: 12pt;">No-Regret
Algorithms in Structured Settings</span></span></span><span class="gmail-Heading3Char"><span data-mce-style="text-decoration: underline;" style="text-decoration: underline;"><span style="font-size: 12pt; color: #56152f; letter-spacing: 0pt; font-variant-caps: normal;" data-mce-style="font-size: 12pt; color: #56152f; letter-spacing: 0pt; font-variant-caps: normal;"><span></span></span></span></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Garber, Hazan, Ma</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">: Online Learning of Eigenvectors. <b>ICML
2015<span></span></b></span></p>

<p class="MsoNormal" style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;" data-mce-style="margin-bottom: 0.0001pt; line-height: normal; background-image: initial; background-position: initial; background-size: initial; background-repeat: initial; background-origin: initial; background-clip: initial;"><i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;">Hazan, Koren, Livni, Mansour:</span></i><span style="font-size: 11pt;" data-mce-style="font-size: 11pt;"> Online Learning with Low-Rank Experts. <b>COLT 2016<span></span></b></span></p>

<p class="MsoNormal"><br></p></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid #cccccc; padding-left: 1ex;" data-mce-style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid #cccccc; padding-left: 1ex;"><div><div style="font-family: garamond,'new york',times,serif; font-size: 12pt; color: #000000;" data-mce-style="font-family: garamond,'new york',times,serif; font-size: 12pt; color: #000000;"></div></div></blockquote></div></div></div><br></div></div></body></html>