Abstract:

Online linear programming (OLP) has gained attention from both researchers and practitioners due to its extensive applications, such as online auction, network revenue management and advertising. Existing algorithms for OLP can be categorized into two types, LP-based algorithms and LP-free algorithms. The former one typically guarantees better performance, even offering a constant regret, but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithm only requires a few first-order computations but induces a worse performance, lacking a constant regret bound. In this work, we bridge the gap between these two extremes by proposing an algorithm that achieves a constant regret while solving LPs only O(log log T) times over the time horizon T. Moreover, we demonstrate the algorithm can guarantee an O(T^{(1/2+ϵ)^(M−1)}) regret by solving LPs only M times. Furthermore, when the arrival probabilities are known at the beginning, our algorithm can also guarantee a constant regret by solving LPs O(log log T) times, and guarantee an O(T^{(1/2+ϵ)^(M)}) regret by solving LPs only M times. In addition, we revisit several resolving schedules (e.g., periodic schedule, midpoint schedule and hyper-exponential schedule) in the literature of network revenue management, prove the constant bound under these schedules, and provide corresponding modified schedules to fit the OLP problem. Lastly, numerical experiments are conducted to demonstrate the efficiency of the proposed algorithm.

Bio:

Zizhuo Wang is a Professor and Associate Dean at the School of Data Science. He is also the co-founder and CTO of Cardinal Operations (杉数科技). He obtained his bachelor's degree in Mathematics from Tsinghua University in 2007, and his Ph.D. degree in Operations Research from Stanford University in 2012.

His research interests mainly focus on optimization and stochastic modeling, especially with applications to pricing and revenue management. He has published over 50 papers in top journal in the field of operations research and management science, and has been the Associate Editors or Senior Editors for the top journals such as Management Science, Operations Research, MSOM and POMS.

Zizhuo Wang has extensive experiences in applying data-driven methods in industry. In 2016, he co-founded Cardinal Operations with others, which served over 200 enterprises to provide data-driven decision support service and products.

Recording: https://archive.ymsc.tsinghua.edu.cn/pacm_lecture?html=Infrequent_Resolving_Algorithm_for_Online_Linear_Programming.html