Parameter-free Optimization, Universal Prediction, And Kolmogorov Complexity (Internship)

Overview

About the project

The basic idea behind these algorithms is in the link between universal strategies for prediction with log loss and online convex optimization, first unveiled in Orabona&Pal (2016). By now, this line of work has produced a number of parameter-free optimization algorithms. However, universal prediction with log loss is also connected to the concept of Kolmogorov complexity for binary strings, as showed by Cover (1974). In this project, we aim at studying all these links, going from parameter-free optimization to Kolmogorov complexity, passing through universal prediction with log loss. We want to construct explicit reductions to transform each of these problem in one of the other ones. 

The final aim of  Parameter-free Optimization, Universal Prediction, And Kolmogorov Complexity (Internship) project offered at  King Abdullah University of Science and Technology (KAUST)  is to directly link convex optimization to an appropriate notion of computational complexity for functions. Moreover, we want to extend some of these concepts from binary strings to strings of bounded real numbers. Given the theoretical nature of this project, the ideal candidate must have an excellent mathematical background.