Leveraging Different Types of Predictors for Online Optimization (Invited Paper)

Predictions have a long and rich history in online optimization research, with applications ranging from video streaming to electrical vehicle charging. Traditionally, different algorithms are evaluated on their performance given access to the same type of predictions. However, motivated by the problem of bandwidth cost minimization in large distributed systems, we consider the benefits of using different types of predictions. We show that the two different types of predictors we consider have complimentary strengths and weaknesses. Specifically, we show that one type of predictor has strong average-case performance but weak worst-case performance, while the other has weak average-case performance but strong worst-case performance. By using a learning-augmented meta-algorithm, we demonstrate that it is possible to exploit both types of predictors for strong performance in all scenarios.