ADAPTIVE AND IMPLICIT ONLINE LEARNING

This thesis is dedicated to the study of online learning algorithms. In particular, after reviewing fundamental concepts in the theory of convex and online linear optimization, we provide a refined analysis of Implicit updates in the framework of Online Mirror Descent. We design a new adaptive algorithm based on it and carefully study its regret bound in the static case, linking it to the variability of the sequence of loss functions. Furthermore, we extend its application to the dynamic setting, studying its dynamic regret. In particular, we show that it achieves the optimal dynamic regret bound, when the quantities of interest are observable or known beforehand. On the other hand, in order to have a fully adaptive algorithm we show how to combine strongly adaptive algorithms with a simple greedy strategy. Finally, we focus on the well known problem of learning with expert advice. We review existing algorithm and describe an existing open problem. We provide some recent results and partial progress on how this problem could be addressed.