Online algorithms receive input that is revealed step-by-step over time, and the algorithm needs to make its current decision without the knowledge of the future. Examples include scheduling jobs that arrive over time, managing a portfolio of stocks, making prediction based on expert advice and so on. Thus, the main issue for such algorithms is to obtain good performance in the face of uncertainty due to inputs arriving sequentially, one at a time. In the past decades, two main paradigms for online problems have emerged. The first, studied by the algorithms community, is to consider the competitive ratio. This is the maximum ratio, over all input sequences, of the online algorithm’s cost to that of the optimum offline algorithm that knows the entire input sequence beforehand. The second, studied by the learning community, is to consider regret: the gap between the online cost and that of the optimum static offline solution.

In recent years there has been remarkable progress in our understanding of online computation, based on convex optimization techniques. For example, the primal-dual method provides a unified framework for design algorithms for a wide variety of online problems. For learning, various seemingly different regret minimization algorithms can be viewed as gradient descent rules applied to a certain convex set. These insights have led to intense activity and several important breakthroughs in these areas. It now seems likely that convex optimization will provide the key unifying link between various models for online computation, and that is what prompted this workshop.  

The main goal of the workshop was to bring the algorithms and the learning communities together, and to facilitate the exchange of techniques, outstanding open questions and important recent developments in these areas, with an emphasis on the unifying framework that convex optimization provides to both these areas.

To achieve this goal, we had several tutorial talks by world-class experts in both areas. These speakers – who were chosen because of their reputation as excellent communicators - invariably did an outstanding job in providing overviews of the key results and techniques in their respective fields, as well as in pointing towards bridges between the two communities – we think that all participants learned a lot. Apart from the tutorials, we had several short contributed talks about cutting-edge research, both by some of the most senior people in both fields and by some ‘up-and-coming’, highly promising junior researchers. We should also note that almost all invitees accepted our invitation, resulting in stimulating discussions during and after the presentations, and allowing participants to get a good overview of both fields. Several participants told us afterwards that they really enjoyed both the workshop contents and its organization. Given all this, we consider the workshop a big success – where we emphasize that the main underlying reason for the success is the Lorentz center concept itself with its excellent facilities and extremely friendly and capable staff, which allowed not only the participants but also the organizers to focus 100% on the science.

Nikhil Bansal (TU Eindhoven, Netherlands)
Peter Grünwald (CWI and Leiden University, Netherlands)