2/6/20 | 4:15pm | E51-325
Reception to follow.
Ben Moseley
Assistant Professor
Carnegie Mellon
Abstract: Combinatorial optimization often focuses on optimizing for the worst-case. However, the best algorithm to use depends on the "relative inputs", which is application specific and often does not have a formal definition.
The talk gives a new theoretical model for designing algorithms that are tailored to inputs for the application at hand. In the model, learning is performed on past problem instances to make predictions on future instances. These predictions are incorporated into the design and analysis of the algorithm. The predictions can be used to achieve "instance-optimal" algorithm design when the predictions are accurate and the algorithm's performance gracefully degrades when there is error in the prediction.
The talk will apply this framework to applications in online algorithm design and give algorithms with theoretical performance that goes beyond worst-case analysis. The majority of the talk will focus on load balancing on unrelated machines.
Bio: Ben Moseley is the Carnegie Bosch Assistant Professor of Operations Research in the Tepper School of Business at Carnegie Mellon University (CMU) and is a consulting professor at the start-up Relational AI. He was an Assistant Professor in the Department of Computer Science and Engineering at Washington University in St. Louis from 2014-2017. He was a 2016 Simons-Berkeley Fellow. From 2012-2014 he was a Research Assistant Professor at the Toyota Technological Institute at Chicago. He was a visiting professor at Sandia National Laboratories in 2013 and has frequently been affiliated with Yahoo Labs.
His interests are broadly in operations research, theoretical computer science and machine learning. He works on the design, analysis and evaluation of algorithms. He is currently working on the algorithmic foundations of machine learning, big data analysis (e.g. relational in-database algorithms, distributed algorithm design, and streaming), and algorithms for scheduling and logistics.
Ben Moseley has won several best paper awards including a 2015 IPDPS Best Paper Award, a SPAA 2013 Best Paper Award, and a SODA 2010 Best Student Paper Award. His work has been recognized with an oral presentation at NIPS 2017 (top 1.3% of submissions) and a spotlight presentation at NIPS 2018 (top 3.5% of submissions).
Moseley's work has been supported by generous grants from the National Science Foundation, Yahoo, Infor, Google and Bosch