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. Analysis frameworks include worst-case, Bayesian, and learning theoretic. 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: Please register (not compulsory). Please bring your own name badge from past conference.

Tentative Schedule

  • 9:00-9:30: Continental Breakfast

Technical Program

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

Lunch

  • 12:30-2:00: Lunch

Student Meetings with Speakers (in Mudd 3014)

  • 2:00-2:30: Nikhil Devanur
  • 2:30-3:00: Anupam Gupta
  • 3:00-3:30: Bobby Kleinberg

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.