Optimization under Uncertainty: Understanding the Correlation Gap

Add to your list(s) Download to your calendar using vCal

• Shipra Agrawal, Stanford
• Monday 04 April 2011, 10:00-11:00
• Large lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

When faced with the challenge of making decisions in presence of multiple uncertainties, a common simplifying heuristic is to assume independence among various sources. Although popular, the effect of this heuristic on the solution quality is little understood. In this talk, I will examine the risk associated with ignoring correlations by introducing a new concept of ‘Correlation Gap’. Correlation gap captures the price of correlations in stochastic optimization—a small correlation gap will imply that the efficient heuristic of assuming independence is actually robust against any adversarial correlations, while a large correlation will suggest that it is important to invest more in data collection and learning correlations. Additionally, I will demonstrate that the problem of bounding correlation gap appears as a fundamental question when analyzing the approximation ratios achieved by some randomized algorithmic strategies for deterministic combinatorial optimization problems. I will use function properties such as monotonicity and submodularity, and employ techniques of cross-monotonic cost-sharing schemes from game theory in a novel manner to provide a tight characterization of functions with small correlation gap. Results include small constant bounds for cost functions resulting from many popular applications such as stochastic facility location, Steiner tree network design, minimum spanning tree, single-source rent-or-buy network design etc.

Towards the end of the talk, I will briefly discuss my research on some other topics, including algorithms for online optimization and techniques for prediction market design.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Large lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.