Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01qz20sv914
 Title: Optimal and Adaptive Online Learning Authors: Luo, Haipeng Advisors: Schapire, Robert E Contributors: Computer Science Department Keywords: boostingmachine learningonline learningoptimizationprediction Subjects: Computer scienceArtificial intelligence Issue Date: 2016 Publisher: Princeton, NJ : Princeton University 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. URI: http://arks.princeton.edu/ark:/88435/dsp01qz20sv914 Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: http://catalog.princeton.edu/ Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Computer Science

Files in This Item:
File Description SizeFormat
Luo_princeton_0181D_11787.pdf949.16 kBAdobe PDF

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.