Abstract

This talk will discuss a model for augmenting algorithms with useful predictions to improve the performance of algorithms.  The model can be used for improving running time offline and the quality of the solution produced by online algorithms. The model ensures predictions are formally learnable and robust. Learnability guarantees that predictions can be efficiently constructed from past data. Robustness formally ensures a prediction is robust to modest changes in the problem input. This talk will discuss predictions that satisfy these properties and result in improved run times or better competitive ratios in the online setting.

Biography

Ben Moseley is the Carnegie Bosch Associate 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.

Professor Moseley's research 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 approximation and online algorithms.

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 NeurIPS 2021 (top 1% of submissions), 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, Office of Naval Research, Yahoo, Infor, Google, and Bosch. Financial support for Moseley's work includes a NSF CAREER Award, grants from NSF divisions on Computing and Communication Foundations (CCF) and Operations Engineering (OE), grants from the Office of Naval Research's Mathematical and Resource Optimization division, two Google Faculty Research Awards, a Yahoo! Academic Career Enabling (ACE) Award, an Infor faculty award and a Carnegie-Bosch faculty chair.