Kevin Leyton-Brown (University of British Columbia)
Calvin Lab Room 116 or Zoom
Title: What Does It Mean To Prefer The Fastest Algorithm?
Abstract: It is surprisingly difficult to identify a defensible, general rule describing when we prefer one runtime distribution to another, particularly if we have only a bounded amount of time for performing each run and not all runs will terminate. (We restrict our attention to settings in which all algorithm runs produce exact, correct answers, and where we care only about runtimes; think e.g. of complete SAT or MIP solvers.) Identifying such a scoring function is critical when we use machine learning approaches to learn new algorithms from data, as in the case of algorithm configuration.
This talk shows how we can make progress on the question by leveraging an economic perspective. Specifically, it describes a new, utility-theoretic answer to the question of how we should formalize our preferences between arbitrary pairs of algorithms. It leverages axiomatic assumptions about preferences over runtime distributions to prove the existence of a scoring function and to identify its properties. This function depends on the way our value for a solution decreases with time and on the distribution from which captimes are drawn. We describe a maximum-entropy approach to modeling captime distributions and show how our overall framework can be applied in a variety of realistic scenarios.
The talk is based on joint work with Devon Graham (UBC) and Tim Roughgarden (Columbia).