[theory students] Fwd: Northwestern Workshop (QTW) on "Optimization with Uncertainty" on March 8th (Friday)

[Shuchi Chawla <shuchi@xxxxxxxxxxx>]

This looks super interesting but it's in two weeks. Let me know if you're interested in going and I'll inform the organizers of how many to expect. In the past students have carpooled and done a 1-2 day trip to attend these workshops.

Shuchi

---------- Forwarded message ---------
From: Aravindan Vijayaraghavan <v.aravindan@xxxxxxxxx>
Date: Fri, Feb 22, 2019 at 4:48 PM
Subject: Northwestern Workshop (QTW) on "Optimization with Uncertainty" on March 8th (Friday)
To: Shuchi Chawla <shuchi@xxxxxxxxxxx>

Dear Shuchi,

We are having our next Quarterly Theory Workshop (QTW) at Northwestern
on March 8th (Friday). This workshop topic is Optimization with
Uncertainty, and will feature talks by Nikhil Devanur, Anupam Gupta
and Robert Kleinberg.

Full details and registration are available on the workshop webpage:
https://theory.cs.northwestern.edu/events/optimization-w-uncertainty/

It would be great if you could attend, and also forward this
announcement to the rest of your group.

We hope to see you there!

Thanks,
Aravindan, Jason, Kostya and Samir.

==================================================

About the Series

The Quarterly Theory Workshop brings in three or four theoretical
computer science experts present their perspective and research on a
common theme. Chicago and Midwest area researchers with interest in
theoretical computer science are invited to attend. The technical
program is in the morning and includes coffee and lunch. The afternoon
of the workshop will allow for continued discussion between attendees
and the speakers.

Synopsis

The focus of this workshop will be on optimization with uncertainty.
Uncertainty arises in optimization problem when all the information
relevant to the optimization is not available at the time of the
optimization. Such uncertainty arises in online algorithms, mechanism
design, and stochastic optimization. Theoretical frameworks include
worst-case, Bayesian, and learning theoretic analyses. The speakers
for this workshop are Nikhil Devanur, Robert Kleinberg, and Anupam
Gupta.

Logistics

Date: Friday, March 8, 2019.
Location: Seeley Mudd 3514, (map), Northwestern U, 2211 Campus Dr,
Evanston, IL 60208.
Transit: Noyes St. Purple Line (map).
Parking: Validation for North Campus Parking Garage (map) available at workshop.
Recommended Hotel: Hilton Orrington.
Registration: TBA. Please bring your own name badge from past conference.

Tentative Schedule

9:00-9:30: Continental Breakfast
9:30-9:35: Opening Remarks
9:35-10:20: Nikhil Devanur
Online Algorithms, learning and game theory: linear, convex and beyond.
10:20-10:40: Coffee Break
10:40-11:25: Robert Kleinberg
Approximately Optimal Sequential Search: Variations on a Theme by Weitzman
11:25-11:45: Coffee Break
11:45-12:30: Anupam Gupta
Robust Algorithms for Secretaries and Bandits
12:30-1:30: Lunch

Titles and Abstracts

Speaker: Nikhil Devanur
Title: Online Algorithms, learning and game theory: linear, convex and beyond.

Online Stochastic Optimization is a class of problems that capture
decision making under uncertainty. The algorithm has to make real time
decisions as it sees new input without knowing future arrival. The
initial motivating applications were formulated as linear programs,
but many extensions need a convex programming formulation. Some mild
stochastic assumptions about the input such as random arrival order
can give near optimal algorithms. One such algorithm is a primal-dual
algorithm, where the dual update is done via no-regret online
learning. Convexity not only captures a broader class of problems but
also clarifies the primaI-dual aspect and the connection to online
learning. Finally, I will show how game theoretic considerations lead
to formulations that are beyond convexity.

Speaker: Robert Kleinberg
Title: Approximately Optimal Sequential Search: Variations on a Theme
by Weitzman

To optimize, one must often invest resources exploring the values of
different alternatives. For example, firms devote time and money to
researching potential acquisition targets or to interviewing job
candidates; college applicants visit schools before selecting one. The
âbox problemâ, introduced by Martin Weitzman in 1979, models this as a
problem of choosing one of finitely many alternatives with independent
random values, subject to a cost that must be invested to discover an
alternativeâs value before it can be selected. The simplicity of the
optimal solution, called âPandoraâs ruleâ, belies the fragility of the
assumptions on which its optimality is based. I will present a new
proof of the optimality of Pandoraâs rule that, unlike Weitzmanâs
original proof, combines nicely with tools used to analyze
approximation algorithms, game equilibria, and online selection rules.
This enables us to design and analyze approximately optimal policies
for environments similar to the box problem but with competing agents,
exogenous order of inspection, or non-obligatory inspection.

The first part of the talk is joint work with Bo Waggoner and Glen
Weyl; the latter part is joint work with Hedyeh Beyhaghi.

Speaker: Anupam Gupta
Title: Robust Algorithms for Secretaries and Bandits

In the secretary problem, a set of items are revealed to us in random
order, and we want to maximize the probability of picking the best
among them. In the (stochastic) multi-armed bandit problem, we perform
pulls from a set of arms, each with a fixed but unknown payoff
probability, and want to minimize the regret. Both these problems are
well-studied in the sequential decision-making literature.

We consider the semi-adversarial setting where an adversary is allowed
to introduce some limited amount of corruptions. We show that
classical algorithms fail badly in the presence of corruptions, and
then we give algorithms that are more robust to corruptions.

This is based on joint works with Domagoj Bradac, Sahil Singla, and
Goran Zuzic, and with Tomer Koren and Kunal Talwar.

--

Shuchi Chawla
shuchi@xxxxxxxxxxx

http://pages.cs.wisc.edu/~shuchi