[Theory] Northwestern Quarterly Theory Workshop (March 8): Optimization with Uncertainty

[Andrew Drucker]

Courtesy of Jason Hartline---see below.

Note, this is the same day as our prospective students visit (but workshop talks are all in the morning).



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

Northwestern Computer Science
Quarterly Theory Workshop: Optimization with Uncertainty
https://theory.cs.northwestern.edu/events/optimization-w-uncertainty/
Seeley Mudd 3514, Northwestern U, 2211 Campus Dr, Evanston, IL 60208.
Friday, March 8, 2019
==================================================

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, Northwestern U, 2211 Campus Dr, Evanston, IL 60208.
Transit: Noyes St. Purple Line.
Parking: Validation for North Campus Parking Garage (map) available at workshop.
Recommended Hotel: Hilton Orrington.
Registration: Please register.  Please bring your ownname 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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20190226/3b1e4769/attachment-0002.html>