Optimal Regularized Online Allocation by Adaptive Re-Solving

References

• Agrawal S, Devanur NR (2015) Fast algorithms for online stochastic convex programming. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1405–1424.Google Scholar
• 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
• Agrawal S, Zadimoghaddam M, Mirrokni V (2018) Proportional allocation: Simple, distributed, and diverse matching with high entropy. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR, New York), 99–108.Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer Berlin Heidelberg, Berlin, Heidelberg), 16–28.Crossref, Google Scholar
• Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• Balseiro S, Besbes O, Pizarro D (2023) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res., ePub ahead of print May 9, https://doi.org/10.1287/opre.2023.2441.Google Scholar
• Balseiro S, Lu H, Mirrokni V (2020) Dual mirror descent for online allocation problems. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn. (PMLR, New York), 613–628.Google Scholar
• Balseiro S, Lu H, Mirrokni V (2021) Regularized online allocation problems: Fairness and beyond. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., vol. 139 (PMLR, New York), 630–639.Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023b) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Bartlett P, Bousquet O, Mendelson S (2005) Local rademacher complexities. Ann. Statist. 33(4):1497–1537.Crossref, Google Scholar
• Bejerano Y, Han S-J, Li L (2007) Fairness and load balancing in wireless LANs using association control. IEEE/ACM Trans. Networking 15(3):560–573.Google Scholar
• Bertsekas D, Gallager R (2021) Data Networks (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. Oper. Res. 59(1):17–31.Link, Google Scholar
• Boucheron S, Bousquet O, Lugosi G (2005) Theory of classification: A survey of some recent advances. ESAIM Probability Statist. 9:323–375.Crossref, Google Scholar
• Bray R (2019) Does the multisecretary problem always have bounded regret? Preprint, submitted December 17, https://dx.doi.org/10.2139/ssrn.3497056.Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Crossref, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Arge L, Hoffmann M, Welzl E, eds. Proc. Eur. Sympos. Algorithms (Springer Berlin Heidelberg, Berlin, Heidelberg), 253–264.Google Scholar
• Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Sci. 66(7):2993–3009.Link, Google Scholar
• Celli A, Colini-Baldeschi R, Kroer C, Sodomka E (2022) The parity ray regularizer for pacing in auction markets. Proc. ACM Web Conf. (Association for Computing Machinery, New York), 162–172.Google Scholar
• Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50(4):720–727.Link, Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 71–78.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):1–41.Crossref, Google Scholar
• Ferreira KJ, Simchi-Levi D, Wang H (2018) Online network revenue management using Thompson sampling. Oper. Res. 66(6):1586–1602.Link, Google Scholar
• Ghosh A, McAfee P, Papineni K, Vassilvitskii S (2009) Bidding for representative allocations for display advertising. Leonardi S, ed. Proc. Internat. Workshop Internet Network Econom. (Springer Berlin Heidelberg, Berlin, Heidelberg), 208–219.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 982–991.Google Scholar
• Gorbunov E, Hanzely F, Richtárik P (2020) A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. Chiappa S, Calandra R, eds. Proc. Twenty Third Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 680–690.Google Scholar
• Gupta V (2022) Technical Note—Greedy algorithm for multiway matching with bounded regret. Oper. Res. 72(3):1139–1155.Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optimiz. 2(3–4):157–325.Crossref, Google Scholar
• Hazan E, Agarwal A, Kale S (2007) Logarithmic regret algorithms for online convex optimization. Machine Learn. 69(2):169–192.Crossref, Google Scholar
• Hu Y, Kallus N, Mao X (2022) Fast rates for contextual linear optimization. Management Sci. 68(6):4236–4245.Link, Google Scholar
• Jasin S (2015) Performance of an LP-based control for revenue management with unknown demand parameters. Oper. Res. 63(4):909–915.Link, Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Kakade S, Shalev-Shwartz S, Tewari A (2009) On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished manuscript, https://home.ttic.edu/~shai/papers/KakadeShalevTewari09.pdf.Google Scholar
• Kerimov S, Ashlagi I, Gurvich I (2021) On the optimality of greedy policies in dynamic matching. Preprint, submitted September 6, https://dx.doi.org/10.2139/ssrn.Google Scholar
• Kim S, Pasupathy R, Henderson SG (2015) A guide to sample average approximation. Fu MC, ed. Handbook of Simulation Optimization (Springer, New York), 207–243.Crossref, Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 630–631.Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Koltchinskii V (2006) Local Rademacher complexities and oracle inequalities in risk minimization. Ann. Statist. 34(6):2593–2656.Google Scholar
• Koltchinskii V (2011) Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: École D’Été de Probabilités de Saint-Flour XXXVIII-2008, vol. 2033 (Springer Science & Business Media, Boston).Crossref, Google Scholar
• Kurokawa D, Procaccia AD, Shah N (2018) Leximin allocations in the real world. ACM Trans. Econ. Comput. 6(3–4):11.Google Scholar
• Lee K-C, Jalali A, Dasdan A (2013) Real time bid optimization with smooth budget delivery in online advertising. Proc. 7th Internat. Workshop Data Mining Online Advertising (Association for Computing Machinery, New York), 1–9.Google Scholar
• Li X, Ye Y (2021) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• Mahdavi M, Jin R, Yang T (2012) Trading regret for efficiency: Online convex optimization with long term constraints. J. Machine Learn. Res. 13(1):2503–2528.Google Scholar
• McMahan B (2011) Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization. Gordon G, Dunson D, Dudík M, eds. Proc. 14th Internat. Conf. Artificial Intelligence Statist., vol. 15 (PMLR, New York), 525–533.Google Scholar
• McMahan HB (2017) A survey of algorithms and analysis for adaptive online learning. J. Machine Learn. Res. 18(1):3117–3166.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Nace D, Doan N-L, Gourdin E, Liau B (2006) Computing optimal max-min fair resource allocation for elastic flows. IEEE/ACM Trans. Networks 14(6):1272–1281.Crossref, Google Scholar
• Nash JF (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• Radunovic B, Le Boudec J-Y (2007) A unified framework for max-min and min-max fairness with applications. IEEE/ACM Trans. Networks 15(5):1073–1083.Crossref, Google Scholar
• Rakhlin A, Shamir O, Sridharan K (2012) Making gradient descent optimal for strongly convex stochastic optimization. Proc. 29th Internat. Conf. Machine Learn. (Omnipress, Madison, WI), 1571–1578.Google Scholar
• Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257–282.Link, Google Scholar
• Ruszczyński A, Shapiro A (2003) Stochastic programming models. Handbook Oper. Res. Management Sci. 10:1–64.Google Scholar
• Salles RM, Barria JA (2008) Lexicographic maximin optimisation for fair bandwidth allocation in computer networks. Eur. J. Oper. Res. 185(2):778–794.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczynski A (2009) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Talluri KT, Van Ryzin G, Van Ryzin G (2004) The Theory and Practice of Revenue Management, vol. 1 (Springer, Berlin).Crossref, Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• Wu H, Srikant R, Liu X, Jiang C (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems vol. 28 (Curran Associates, Inc., Red Hook, NY), 433–441.Google Scholar
• Xu J, Lam AY, Li VO (2011) Chemical reaction optimization for task scheduling in grid computing. IEEE Trans. Parallel Distribution Systems 22(10):1624–1631.Crossref, Google Scholar
• Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. Proc. 20th Internat. Conf. Machine Learn. (AAAI Press, Palo Alto, CA), 928–936.Google Scholar