Optimal and Adaptive Online Learning

Abstract

Online learning is one of the most important and well-established machine learning models. Generally speaking, the goal of online learning is to make a sequence of accurate predictions “on the fly,” given some information of the correct answers to previous prediction tasks. Online learning has been extensively studied in recent years, and has also become of great interest to practitioners due to its effectiveness in dealing with non-stationary data as well as its applicability to large-scale applications.

While many useful ideas are well-established in the offline learning setting where a set of data is available beforehand, their counterparts in the online setting are not always straightforward and require more understanding. Moreover, existing online learning algorithms are not always directly applicable in practice. One important reason is that they usually rely on sophisticated tuning of parameters, a delicate approach that can yield sound theoretical guarantees, but that does not work well in practice. Another reason is that existing algorithms are usually guaranteed to work well in one particular situation or another, but not all. A single algorithm that can ensure worst-case robustness while still enjoying the ability to exploit easier data at the same time is relatively rare and certainly desirable in practice.

Motivated by all the above issues, this thesis focuses on designing more practical, adaptive and ready-to-use online learning algorithms, including:

1) novel online algorithms which combine expert advice in an optimal and parameter-free way and work simultaneously under different patterns of data as well as different evaluation criteria;

2) a novel and rigorous theory of online boosting which studies improving the accuracy of any existing online learning algorithm by training and combining several copies of it in a carefully designed manner;

3) a family of highly efficient online learning algorithms which make use of second order information of the data and enjoy good performance even when dealing with ill-conditioned data.

In summary, this thesis develops and analyzes several novel, optimal and adaptive online learning algorithms which greatly improve upon previous work and have great practical potential.