PhD Dissertation Defense - Mengxiao Zhang

Title:  Robust and Adaptive Algorithm Design in Online Learning: Regularization, Exploration, and Aggregation  
 
Abstract: In recent years, online learning is becoming a central component in Artificial Intelligence and has been widely applied in many real applications.  In this thesis, we focus on designing algorithms for online learning with the two characteristics: robustness and adaptivity. Motivated by the existence of unpredictable corruptions and noises in real-world applications such as E-commerce recommendation systems, robustness is a desired property. It means that the designed algorithm is guaranteed to perform well even in adversarial environments. In contrast, adaptivity complements robustness by enhancing performance in benign environments.In order to achieve robustness and adaptivity, we utilize the following three methodologies, namely regularization, exploration, and aggregation. Regularization method has been widely used in the field of machine learning to control the dynamic of the decisions, which is especially important when facing a possibly adversarial environment. In online learning problems, very often the learner can only observe partial information of the environment, making an appropriate exploration method crucial. Aggregation, a natural idea to achieve adaptivity, combines multiple algorithms that work well in different environments. Though intuitive, this requires non-trivial algorithm design for different online learning problems.In this thesis, we design algorithms for a wide range of online learning problems. We first consider the problem of multi-armed bandits with feedback graphs. Then, we consider more complex problems including linear bandits and convex bandits, which involve an infinite number of actions. We hope that the techniques and algorithms developed in this thesis can help improve the current online learning algorithms for real-world applications.       Committee Members:Haipeng Luo (Chair), Vatsal Sharan, Renyuan Xu  

Location: Ronald Tutor Hall of Engineering (RTH) - 114

Audiences: Everyone Is Invited

Contact: Ellecia Williams