Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision Making in Online Linear Programming

References

• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res. 72(5):2168–2189.Link, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Balseiro SR, Lu H, Mirrokni V, Sivan B (2022) Analysis of dual-based PID controllers through convolutional mirror descent. Preprint, submitted February 12, https://arxiv.org/abs/2202.06152.Google Scholar
• Bray RL (2024) Logarithmic regret in multisecretary and online linear programs with continuous valuations. Oper. Res. 73(4):2188–2203.Link, Google Scholar
• Chen G, Li X, Ye Y (2024) An improved analysis of LP-based control for revenue management. Oper. Res. 72(3):1124–1138.Link, Google Scholar
• Gao W, Ge D, Sun C, Ye Y (2023) Solving linear programs with fast online learning algorithms. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., vol. 202 (PMLR, New York), 10649–10675.Google Scholar
• Hussain H, Malik SUR, Hameed A, Khan SU, Bickler G, Min-Allah N, Qureshi MB, et al. (2013) A survey on resource allocation in high performance distributed computing systems. Parallel Comput. 39(11):709–736.Crossref, Google Scholar
• Jiang J, Ma W, Zhang J (2025) Degeneracy is OK: Logarithmic regret for network revenue management with indiscrete distributions. Oper. Res. 73(6):3405–3420.Link, Google Scholar
• Johnstone PR, Moulin P (2020) Faster subgradient methods for functions with Hölderian growth. Math. Programming 180(1):417–450.Crossref, Google Scholar
• Katoh N, Ibaraki T (1998) Resource allocation problems. Du D-Z, Pardalos PM, eds. Handbook of Combinatorial Optimization, vol. 2 (Kluwer Academic Publishers, Dordrecht, Netherlands), 159–260.Crossref, Google Scholar
• Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing LPs in the random-order model. Shmoys DB, ed. Proc. 46th Annual ACM Sympos. Theory Comput. (ACM, New York), 303–312.Google Scholar
• Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• Li X, Sun C, Ye Y (2023) Simple and fast algorithm for binary integer and online linear programming. Math. Programming 200(2):831–875.Crossref, Google Scholar
• Li G, Wang Z, Zhang J (2024) Infrequent resolving algorithm for online linear programming. Preprint, submitted August 1, https://arxiv.org/abs/2408.00465.Google Scholar
• Liu Z, Zhou Z (2024) Revisiting the last-iterate convergence of stochastic gradient methods. Proc. 12th Internat. Conf. Learn. Representations (OpenReview.net), 53613–53647.Google Scholar
• Lobos A, Grigas P, Wen Z (2021) Joint online learning and decision-making via dual mirror descent. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., vol. 139 (PMLR, New York), 7080–7089.Google Scholar
• Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6):1787–1803.Link, Google Scholar
• Ma W, Cao Y, Tsang DHK, Xia D (2024) Optimal regularized online allocation by adaptive re-solving. Oper. Res. 73(4):2079–2096.Link, Google Scholar
• Mahdian M, Nazerzadeh H, Saberi A (2012) Online optimization with uncertain information. ACM Trans. Algorithms 8(1):1–29.Crossref, Google Scholar
• Mirrokni VS, Oveis Gharan S, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’12 (SIAM, Philadelphia), 1690–1701.Google Scholar
• Sun R, Wang X, Zhou Z (2020) Near-optimal primal-dual algorithms for quantity-based network revenue management. Preprint, submitted November 12, https://arxiv.org/abs/2011.06327.Google Scholar
• Sun J, Gao W, Vitercik E, Ye Y (2025) Wait-less offline tuning and re-solving for online decision making. Singh A, Fazel M, Hsu D, Lacoste-Julien S, Berkenkamp F, Maharaj T, Wagstaff K, Zhu J, eds. Proc. 42nd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 267 (PMLR, New York), 57419–57449.Google Scholar
• Talluri KT, Van Ryzin G (2004) The Theory and Practice of Revenue Management, vol. 1 (Springer, Berlin).Crossref, Google Scholar
• Xu H, Glynn PW, Ye Y (2024) Online linear programming with batching. Preprint, submitted August 1, https://arxiv.org/abs/2408.00310.Google Scholar
• Xu Y, Lin Q, Yang T (2017) Stochastic convex optimization: Faster local growth implies faster global convergence. Proc. Internat. Conf. Machine Learn. (PMLR, New York), 3821–3830.Google Scholar
• Yang T, Lin Q (2018) RSG: Beating subgradient method without smoothness and strong convexity. J. Machine Learn. Res. 19(1):236–268.Google Scholar