Haipeng Luo will present his Pre FPO on July 27, 2015 at 2pm in CS 401. The committee members are Robert Schapire (adviser); Elad Hazan and Readers: Satyen Kale (Yahoo Labs); and Non-readers: Sanjeev Arora, Barbara Engelhardt Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Optimal and Adaptive Online Learning Online learning is one of the important and well-established learning models in the area of machine learning. Generally speaking, the goal of online learning is to make a sequence of accurate predictions “on the fly†when interacting with the environment. Online learning has been extensively studied in recent years, and has also become of great interest to practitioners due to its applicability to large scale applications such as advertisement placement and recommendation systems. Existing online learning algorithms, however, are not always directly applicable in practice, because they usually rely on sophisticated tuning of parameters that gives sound theoretical guarantees but hardly works in practice. In this thesis, our main focus is thus to design practical and ready-to-use online learning algorithms that are parameter-free and work simultaneously under different patterns of data as well as different evaluation criteria. Our main contributions are new optimal and adaptive algorithms for the following three online learning problems: 1. We study the classic problem of online learning by combining expert advice with several new and challenging goals. By converting the problem into a “drifting game†and analyzing the approximate minimax optimal solutions, we propose a new parameter-free algorithm called AdaNormalHedge. Our algorithm is the first one that achieves several desirable objectives simultaneously, including learning from unknown or even infinite number of experts, competing with a sequence of unknown competitors, and achieving much better performance when dealing with easy problems, while still ensuring worst case robustness in difficult situations. Our results lead to significant improvements in several applications, such as predicting almost as well as the best pruning tree of a decision tree. 2. The second problem we study is online boosting. Boosting is one of the central methodology in machine learning that studies the task of combining weak rule-of-thumbs into a strong learning algorithm. While it is well-studied in the offline batch setting, there is very few work on the theory of online boosting. We thus develop a set of optimal and adaptive online boosting algorithms, some that achieve arbitrarily small error under a novel notion of weak online learnability, and the others which converge to the best possible achieved by the linear combination of weak learners. Experiments on benchmark data are conducted to show that our new algorithms indeed improve upon previous work. 3. The last problem we investigate is online learning without knowing the actual time horizon, which is yet another important feature for a practical algorithm. Previously, different techniques have been used, such as the so-called “doubling trick†which is unfortunately inelegant and wasteful. We formalize this problem as a game and study the exact minimax optimal solutions. We first prove that learning with unknown time horizon is strictly harder, and then propose a simple minimax optimal algorithm for a special case. Based on this special case, we further develop a new algorithm for the general case which, although not being exact optimal, enjoys a better performance guarantee compared to previous work.