Beyond worst-case analysis

Well, last week was the final workshop in the semester-long “Algorithms & Uncertainty” program that I helped to organize at the Simons institute.  There are a few weeks of reading groups / seminars / etc. left, but the workshop marks the last “big” event.  It’s sad to see the program wrapping up, though I’m definitely happy that I will be spending a lot less time on planes pretty soon — I’ve been flying back and forth every week!

The last workshop was on “Beyond worst-case analysis” and the organizers (Avrim Blum, Nir Ailon, Nina Balcan, Ravi Kumar, Kevin Leyton-Brown, Tim Roughgarden) did a great job of putting together a really unique program.  Since there’s not “one way” to go beyond worst-case, the week included a huge array of interesting ways to get results beyond what is possible from worst-case analysis, whether it be learning commonalities of different types of instances, semi-random / smoothed analysis models, or extracting features that enable learning what algorithmic approach to use.

If you’re interested in getting a broad overview of the approaches, I highly recommend watching Avrim’s introductory talk, which gave a survey of a ton of different approaches for going “beyond worst-case” that have received attention recently.  Tim also has a great course on the topic that is worth checking out…

My own contribution was the final talk of the week, which gave an overview of our work on how to use properties of prediction noise to help design better online optimization algorithms.  The idea is that predictions are crucial to almost all online problems, but we don’t really understand how properties of prediction error should influence algorithm design.  Over the last few years we’ve developed some models and results that allow initial insights into, e.g., how correlation structure in prediction errors changes the “optimal” algorithm form.  Check out the video for more details!

Algorithms & Uncertainty at the Simons Institute

I’m hoping that most of the people who read this blog have already heard, but in case they haven’t — next Fall, the Simons Institute is hosting a semester-long program on Algorithms and Uncertainty, which I am co-organizing with Avrim Blum, Anupam Gupta, Robert Kleinberg, Stefano Leonardi, and Eli Upfal.

It should be a very interesting semester, and we’ve already lined up a long list of interesting long-term participants.  The planning for the workshops is just beginning, but there will be three main events: an initial “Boot Camp” and then two workshops: “Optimization and Decision-Making Under Uncertainty” and “Learning, Algorithm Design, and Beyond Worst-Case Analysis”.

More info about all of the events will be posted here as it becomes available.

The reason for posting about this now is that a call recently went up for Simons-Berkeley Research Fellowships, which are for junior researchers within six years of their PhD.  Please spread the word about the application — the deadline is December 15, 2015.