The Power of Online Learning in Stochastic Network Optimization

Speaker : Longbo Huang
Tsinghua University
Date: 22/05/2015
Time: 10:30 am - 11:30 am
Location: LINCS Meeting Room 40


Abstract: We investigate the power of online learning in stochastic network optimization with unknown system statistics a priori. We are interested in understanding how information and learning can be efficiently incorporated into system control techniques, and what are the fundamental benefits of doing so. We propose two Online Learning-Aided Control techniques, OLAC and OLAC2, that explicitly utilize the past system information in current system control via a learning procedure called dual learning. We prove strong performance guarantees of the proposed algorithms: OLAC and OLAC2 achieve the near-optimal O(epsilon), O([log(1/epsilon)^2)]$ utility-delay tradeoff and OLAC2 possesses an $O(epsilon^-2/3)$ convergence time. OLAC and OLAC2 are probably the first algorithms that simultaneously possess explicit near-optimal delay guarantee and sub-linear convergence time. Simulation results also confirm the superior performance of the proposed algorithms in practice. To the best of our knowledge, our attempt is the first to explicitly incorporate online learning into stochastic network optimization and to demonstrate its power in both theory and practice.
Biography: Dr. Longbo Huang received his Ph.D. from the EE department at the University of Southern California in August 2011. He was then a postdoctoral researcher in the EECS department at UC Berkeley from July 2011 to August 2012. Since then he has been an assistant professor at the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Dr. Huang was a visiting scholar at the LIDS lab at MIT in summer 2012 and 2014, at the EECS department at UC Berkeley in summer 2013, and at Bell-labs France in April 2013. He was also a visiting professor at the Institute of Network Coding at CUHK in winter 2012. Dr. Huang was selected into China’sYouth 1000-talent program in 2013. Dr. Huang’s research interests lie in the areas of stochastic learning and optimization for networked systems, delay-efficient network control, mobile networks, data center networking, energy management and smart grid.