The power of online learning in stochastic network optimization
The power of online learning in stochastic network optimization
复制标题
DOI：
10.1145/2591971.2591990
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
Longbo Huang-;Xin Liu;Xiaohong Hao
中科院分区：
文献类型：
--
作者：
Longbo Huang-;Xin Liu;Xiaohong Hao
在本文中，我们研究了在线学习的力量在随机网络优化与未知的系统统计先验。我们有兴趣了解如何将信息和学习有效地纳入系统控制技术，以及这样做的基本好处是什么。我们提出了两个在线学习辅助控制技术，OLAC和OLAC 2，明确地利用过去的系统信息在当前的系统控制，通过一个学习过程称为双学习。我们证明了所提出的算法的强性能保证：OLAC和OLAC 2实现了接近最优的[O（ε），O（[log（1/ε）]2）]效用延迟权衡和OLAC 2具有O（ε-2/3）收敛时间。仿真结果也证实了所提出的算法在实践中的上级性能。据我们所知，OLAC和OLAC 2是第一个同时具有显式近优延迟保证和次线性收敛时间的算法，我们的尝试是第一个明确地将在线学习纳入随机网络优化，并在理论和实践中展示其功能。
In this paper, 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(ε), O([log(1/ε)]2)] utility-delay tradeoff and OLAC2 possesses an O(ε-2/3) convergence time. Simulation results also confirm the superior performance of the proposed algorithms in practice. To the best of our knowledge, OLAC and OLAC2 are the first algorithms that simultaneously possess explicit near-optimal delay guarantee and sub-linear convergence time, and our attempt is the first to explicitly incorporate online learning into stochastic network optimization and to demonstrate its power in both theory and practice.