<html 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=utf-8">
<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:12.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;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Courtesy of Jason Hartline---see below.
<o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Note, this is the same day as our prospective students visit (but workshop talks are all in the morning).<o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">==================================================<o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><o:p> </o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Northwestern Computer Science <o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Quarterly Theory Workshop: Optimization with Uncertainty<o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222"><a href="https://theory.cs.northwestern.edu/events/optimization-w-uncertainty/" target="_blank"><span style="color:#1155CC">https://theory.cs.northwestern.edu/events/optimization-w-uncertainty/</span></a><o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Seeley Mudd 3514, Northwestern U, 2211 Campus Dr, Evanston, IL 60208.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom:12.0pt;background:white"><span style="font-family:"Arial",sans-serif;color:#222222">Friday, March 8, 2019<o:p></o:p></span></p>
<p class="MsoNormal" style="background:white"><span style="font-family:"Arial",sans-serif;color:#222222">==================================================<br>
<br>
About the Series<br>
<br>
The Quarterly Theory Workshop brings in three or four theoretical<br>
computer science experts present their perspective and research on a<br>
common theme. Chicago and Midwest area researchers with interest in<br>
theoretical computer science are invited to attend. The technical<br>
program is in the morning and includes coffee and lunch. The afternoon<br>
of the workshop will allow for continued discussion between attendees<br>
and the speakers.<br>
<br>
Synopsis<br>
<br>
The focus of this workshop will be on optimization with uncertainty.<br>
Uncertainty arises in optimization problem when all the information<br>
relevant to the optimization is not available at the time of the<br>
optimization. Such uncertainty arises in online algorithms, mechanism<br>
design, and stochastic optimization. Theoretical frameworks include<br>
worst-case, Bayesian, and learning theoretic analyses. The speakers<br>
for this workshop are Nikhil Devanur, Robert Kleinberg, and Anupam<br>
Gupta.<br>
<br>
Logistics<br>
<br>
Date: Friday, March 8, 2019.<br>
Location: Seeley Mudd 3514, Northwestern U, 2211 Campus Dr, Evanston, IL 60208.<br>
Transit: Noyes St. Purple Line.<br>
Parking: Validation for North Campus Parking Garage (map) available at workshop.<br>
Recommended Hotel: Hilton Orrington.<br>
Registration: Please register. Please bring your ownname badge from past conference.<br>
<br>
Tentative Schedule<br>
<br>
9:00-9:30: Continental Breakfast<br>
9:30-9:35: Opening Remarks<br>
9:35-10:20: Nikhil Devanur<br>
Online Algorithms, learning and game theory: linear, convex and beyond.<br>
10:20-10:40: Coffee Break<br>
10:40-11:25: Robert Kleinberg<br>
Approximately Optimal Sequential Search: Variations on a Theme by Weitzman<br>
11:25-11:45: Coffee Break<br>
11:45-12:30: Anupam Gupta<br>
Robust Algorithms for Secretaries and Bandits<br>
12:30-1:30: Lunch<br>
<br>
Titles and Abstracts<br>
<br>
Speaker: Nikhil Devanur<br>
Title: Online Algorithms, learning and game theory: linear, convex and<br>
beyond.<br>
<br>
Online Stochastic Optimization is a class of problems that capture<br>
decision making under uncertainty. The algorithm has to make real time<br>
decisions as it sees new input without knowing future arrival. The<br>
initial motivating applications were formulated as linear programs,<br>
but many extensions need a convex programming formulation. Some mild<br>
stochastic assumptions about the input such as random arrival order<br>
can give near optimal algorithms. One such algorithm is a primal-dual<br>
algorithm, where the dual update is done via no-regret online<br>
learning. Convexity not only captures a broader class of problems but<br>
also clarifies the primaI-dual aspect and the connection to online<br>
learning. Finally, I will show how game theoretic considerations lead<br>
to formulations that are beyond convexity.<br>
<br>
Speaker: Robert Kleinberg<br>
Title: Approximately Optimal Sequential Search: Variations on a Theme<br>
by Weitzman<br>
<br>
To optimize, one must often invest resources exploring the values of<br>
different alternatives. For example, firms devote time and money to<br>
researching potential acquisition targets or to interviewing job<br>
candidates; college applicants visit schools before selecting one. The<br>
“box problem”, introduced by Martin Weitzman in 1979, models this as a<br>
problem of choosing one of finitely many alternatives with independent<br>
random values, subject to a cost that must be invested to discover an<br>
alternative’s value before it can be selected. The simplicity of the<br>
optimal solution, called “Pandora’s rule”, belies the fragility of the<br>
assumptions on which its optimality is based. I will present a new<br>
proof of the optimality of Pandora’s rule that, unlike Weitzman’s<br>
original proof, combines nicely with tools used to analyze<br>
approximation algorithms, game equilibria, and online selection rules.<br>
This enables us to design and analyze approximately optimal policies<br>
for environments similar to the box problem but with competing agents,<br>
exogenous order of inspection, or non-obligatory inspection.<br>
<br>
The first part of the talk is joint work with Bo Waggoner and Glen<br>
Weyl; the latter part is joint work with Hedyeh Beyhaghi.<br>
<br>
Speaker: Anupam Gupta<br>
Title: Robust Algorithms for Secretaries and Bandits<br>
<br>
In the secretary problem, a set of items are revealed to us in random<br>
order, and we want to maximize the probability of picking the best<br>
among them. In the (stochastic) multi-armed bandit problem, we perform<br>
pulls from a set of arms, each with a fixed but unknown payoff<br>
probability, and want to minimize the regret. Both these problems are<br>
well-studied in the sequential decision-making literature.<br>
<br>
We consider the semi-adversarial setting where an adversary is allowed<br>
to introduce some limited amount of corruptions. We show that<br>
classical algorithms fail badly in the presence of corruptions, and<br>
then we give algorithms that are more robust to corruptions.<br>
<br>
This is based on joint works with Domagoj Bradac, Sahil Singla, and<br>
Goran Zuzic, and with Tomer Koren and Kunal Talwar.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
</div>
</body>
</html>