Online Algorithms and Learning

Description:

The traditional design and analysis of algorithms assumes that complete knowledge of the entire input is available to an algorithm. However, in many cases the input is revealed online over time, and the algorithm needs to make its current decision without the knowledge of the future. For example, scheduling jobs that arrive over time, managing a portfolio of stocks, making prediction based on expert advice and so on. Thus, the main issue in online

computation is obtaining good performance in the face of uncertainty due to inputs arriving sequentially, one at a time.

Roughly speaking, two main paradigms for online problems have emerged. The first, studied by the algorithms community is to consider the competitive ratio: defined as the maximum ratio, over all input sequences, of the online algorithms 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 is very likely that convex optimization will provide the key unifying linked between various models for online computation.

Aim:

The main goal of the workshop is 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. An important focus will be on exploring the unifying framework that convex optimization provides to both these areas.

During the workshop, we will have several tutorials style talks by experts in both these areas, that provide an overview of the key results and techniques. Plenty of free time will be provided for informal interaction and discussion.

Talks and posters:

In the registration form you can indicate if you are interested in giving a 20 minute talk or if you would like to present a poster.  

Since a large part of the program will be devoted to tutorials and discussion sections, there will not nearly be enough time for every participant to give a talk; we will choose the talks that best fit into the general workshop theme and let you know in time whether your talk has been selected.  A good alternative is to send a poster to the early-evening /poster session/, during which soft drinks, beer and wine will be available. There will be no obligation to remain posted at your poster. All posters will be accepted.

As stated, we will have explicit discussion sessions and stimulate people from the computing and learning communities to interact.

If there are any specific topics you would like to have discussed, we kindly ask you to indicate them in the registration form.