2017-11-16 | Wei Chen: Combinatorial Online Learning
The adoption of electronic trading systems has transformed financial markets into a trading platform with the limit order book as a dominant trading mechanism. In this talk, we explore and discuss some of the basic questions that have arisen in limit order markets. In Part I, we discuss asymptotic analysis of a two-sided Markov order book model and establish a fluid limit; In Part II, we study dynamic optimal order execution using a special order type known as hidden orders; In Part III, we discuss performance analysis questions in dark pool trading, using a Hawkes process approach.
Combinatorial optimization is one of the core areas in theoretical computer science and operations research, with many classical problems such as graph shortest paths, minimum spanning trees, maximum weighted matchings, and it also has numerous modern applications such as in networking, online advertising, crowd sourcing, and viral marketing. However, in many of these modern applications, the exact parameters needed as inputs, such as link latencies in wireless networking, click-through rates in online advertising, worker-task performance in crowd sourcing, and diffusion probabilities in viral marketing, are stochastic and unknown, and thus have to be learned over time. On the other hand, well-studied online learning and optimization frameworks, exemplified by the classical multi-armed bandit problem, cannot be applied directly to address these problems due to the exponential blowup in the solution space. Therefore, it demands a new framework that could incorporate combinatorial learning seamlessly into the existing combinatorial optimization framework, without re-engineering the optimization tasks from scratch.
In this talk, I will introduce a series of works I and my collaborators have done in the recent years to systematically build such a framework. I will first introduce our work on the general combinatorial multi-armed bandit (CMAB) framework that incorporates optimization tasks with non-linear objective functions and approximation guarantees, and provide a modularized learning algorithm with tight regret analysis. I will then introduce our recent studies including CMAB with probabilistically triggered arms, CMAB with general reward functions, and combinatorial pure exploration, which cover different aspects of combinatorial online learning. Throughout my talk I will illustrate how the framework and the results can be applied to applications such as online advertising, crowd-sourcing, and viral marketing, and discuss many opportunities in further advancing this line of research.
Wei Chen is a Senior Researcher at Microsoft Research Asia, and also an Adjunct Professor at Tsinghua University, Institute of Interdisciplinary Information Science, and an Adjunct Researcher at Chinese Academy of Sciences, Institute of Computing Technology. His main research interests include social and information networks, online learning, network game theory and economics, distributed computing, and fault tolerance.
He is one of the leading researchers in the algorithmic study on influence propagation in social networks, with a series publications in top conferences such as KDD, ICDM, AAAI, VLDB, NIPS, which receive aggregate citations of more than 3500 times. His research on combinatorial online learning since 2013 also leads to a series of influential publications in the top machine learning conferences ICML and NIPS.
He is a founding member of the Big Data Task Force of Chinese Computer Federation (CCF), and a member of the Theoretical Computer Science Task Force of CCF. He is an editor in the Big Data journal, and program committee members of many top conferences (KDD, WWW, SIGMOD, NIPS, etc.). He coauthored a monograph in 2013, “Information and Influence Propagation in Social Networks”, in Morgan & Claypool’s Data Management Synthesis series, which is ranked top 10 in downloads in the series. His Ph.D dissertation won the 2000 William C. Carter Award on dependable computing.