The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems

References

• Agrawal S, Devanur NR (2014) Fast algorithms for online stochastic convex programming. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1405–1424.Google Scholar
• Agrawal S, Devanur NR, Li L (2016) An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. Conf. Learn. Theory (PMLR), 4–18. 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. Internat. Conf. Machine Learn (PMLR), 99–108.Google Scholar
• Ahmed F, Dickerson JP, Fuge M (2017) Diverse weighted bipartite b-matching. Preprint, submitted February 23, https://arxiv.org/abs/1702.07134.Google Scholar
• Anderson SP, De Palma A, Thisse JF (1992) Discrete Choice Theory of Product Differentiation (MIT Press, Cambridge, MA).Crossref, Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: A meta-algorithm and applications. Theory Comput. 8(1):121–164.Crossref, Google Scholar
• Badanidiyuru A, Langford J, Slivkins A (2014) Resourceful contextual bandits. Conf. Learn. Theory (PMLR), 1109–1134.Google Scholar
• Ball MO, Queyranne M (2009) Toward robust revenue management: Competitive analysis of online booking. Oper. Res. 57(4):950–963.Link, 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, Lu H, Mirrokni V (2020) Dual mirror descent for online allocation problems. Internat. Conf. Machine Learn. PMLR 119:613–628.Google Scholar
• Bauschke HH, Borwein JM, Combettes PL (2001) Essential smoothness, essential strict convexity, and legendre functions in banach spaces. Comm. Contemporary Math. 3(04):615–647.Crossref, Google Scholar
• Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3):167–175.Crossref, Google Scholar
• Bernstein F, Gürhan Kök A, Xie L (2015) Dynamic assortment customization with limited inventories. Manufacturing Service Oper. Management 17(4):538–553.Link, Google Scholar
• Bertsekas D (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Bertsekas DP (2014) Constrained Optimization and Lagrange Multiplier Methods (Academic Press, Cambridge, MA).Google Scholar
• Besbes O, Gur Y, Zeevi A (2014) Stochastic multi-armed-bandit problem with non-stationary rewards. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. 27th Inter. Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 199–207.Google Scholar
• Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. Oper. Res. 63(5):1227–1244.Link, Google Scholar
• Bhalgat A, Feldman J, Mirrokni V (2012) Online allocation of display ads with smooth delivery. Proc. 18th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1213–1221.Google Scholar
• Bitran G, Caldentey R (2003) An overview of pricing models for revenue management. Manufacturing Service Oper. Management 5(3):203–229.Link, Google Scholar
• Bradac D, Gupta A, Singla S, Zuzic G (2020) Robust algorithms for the secretary problem. Vidick T, ed. 11th Innovations Theoret. Comput. Sci. Conf., Leibniz International Proceedings in Informatics, vol. 151 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 32:1–32:26.Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations and Trends Machine Learn. 8(3-4):231–357.Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Arge L, Hoffman M, Welzl E, eds. Proc. 15th Annual Eur. Conf. Algorithms (Springer, Berlin), 253–264.Google Scholar
• Chen X, Krishnamurthy A, Wang Y (2019) Robust dynamic assortment optimization in the presence of outlier customers. Preprint, submitted October 9, https://arxiv.org/abs/1910.04183.Google Scholar
• Ciocan DF, Farias VF (2012) Dynamic allocation problems with volatile demand. Math. Oper. Res. 37(3):501–525.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 (ACM, 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
• Duchi J, Hazan E, Singer Y (2011) Adaptive subgradient methods for online learning and stochastic optimization. J. Machine Learn. Res. 12(7):2121–2159.Google Scholar
• Duchi JC, Agarwal A, Johansson M, Jordan MI (2012) Ergodic mirror descent. SIAM J. Optim. 22(4):1549–1578.Crossref, Google Scholar
• Dughmi S, Hartline J, Kleinberg RD, Niazadeh R (2021) Bernoulli factories and black-box reductions in mechanism design. J. ACM 68(2):1–30.Crossref, Google Scholar
• Dütting P, Kesselheim T (2019) Posted pricing and prophet inequalities with inaccurate priors. Proc. 2019 ACM Conf. Econom. Comput. (ACM, New York), 111–129.Google Scholar
• eMarketer (2019) US programmatic ad spending forecast 2019. Accessed January 20, 2020, https://www.emarketer.com/content/us-programmatic-ad-spending-forecast-2019.Google Scholar
• Esfandiari H, Korula N, Mirrokni V (2018) Allocation with traffic spikes: Mixing adversarial and stochastic models. ACM Trans. Econom. Comput. 6(3-4):1–23.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009b) Online stochastic matching: Beating 1-1/e. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 117–126.Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. de Berg M, Meyer U, eds. Proc. 18th Annual Eur. Conf. Algorithms (Springer-Verlag, Berlin), 182–194.Google Scholar
• Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pál M (2009a) Online ad assignment with free disposal. Leonardi S, ed. Proc. 5th Internat. Workshop Internet Network Econom. (Springer, Berlin), 374–385.Google Scholar
• Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research and Management Science, vol. 279 (Springer, New York).Google Scholar
• Glover F, Glover R, Lorenzo J, McMillan C (1982) The passenger-mix problem in the scheduled airlines. Interfaces 12(3):73–80.Link, Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Gupta A, Molinaro M (2016) How the experts algorithm can help solve LPs online. Math. Oper. Res. 41(4):1404–1431.Link, Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3-4):157–325.Google Scholar
• Hazan E, Kale S (2010) Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine Learn. 80(2):165–188.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
• Jiang J, Li X, Zhang J (2020) Online stochastic optimization with Wasserstein based non-stationarity. Preprint, submitted December 13, https://arxiv.org/abs/2012.06961.Google Scholar
• Kanoria Y, Qian P (2020) Blind dynamic resource allocation in closed networks via mirror backpressure. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 503.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. Twenty-Second Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
• Kesselheim T, Molinaro M (2020) Knapsack secretary with bursty adversary. Preprint, submitted June 20, https://arxiv.org/abs/2006.11607.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. Proc. Forty-Sixth Annual ACM Sympos. Theory Comput. (ACM, New York), 303–312.Google Scholar
• Kingma DP, Ba J (2015) Adam: A method for stochastic optimization. 3rd Internat. Conf. Learn. Representations. Google Scholar
• Lan T, Kao D, Chiang M, Sabharwal A (2010) An axiomatic theory of fairness in network resource allocation. Proc. 29th Conf. Inform. Comm. (IEEE Press, Piscataway, NJ), 1343–1351.Google Scholar
• Lee K-C, Jalali A, Dasdan A (2013) Real time bid optimization with smooth budget delivery in online advertising. Proc. Seventh Internat. Workshop Data Mining Online Advertising (ACM, New York), 1–9.Google Scholar
• Levin DA, Peres Y (2017) Markov Chains and Mixing Times, vol. 107 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Li X, Ye Y (2019) Online linear programming: Dual convergence, new algorithms, and regret bounds. Preprint, submitted September 12, https://doi.org/10.48550/arXiv.1909.05499.Google Scholar
• Li X, Sun C, Ye Y (2020) Simple and fast algorithm for binary integer and online linear programming. Preprint, submitted March 5, https://arxiv.org/abs/2003.02513.Google Scholar
• Lu H (2019) “Relative continuity” for non-Lipchitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent. INFORMS J. Optim. 1(4):288–303.Link, Google Scholar
• Lu H, Freund R, Nesterov Y (2018) Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1):333–354.Crossref, Google Scholar
• Lykouris T, Mirrokni V, Leme RP (2018) Stochastic bandits robust to adversarial corruptions. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 114–122.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22–es.Crossref, Google Scholar
• Meyn SP, Tweedie RL (2012) Markov Chains and Stochastic Stability (Springer Science & Business Media, Berlin).Google Scholar
• Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 2012 Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1690–1701.Google Scholar
• Nemirovsky AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization (Wiley, New York).Google Scholar
• Qin L, Zhu X (2013) Promoting diversity in recommendation by entropy regularizer. Proc. Twenty-Third Internat. Joint Conf. Artificial Intelligence (AAAI Press, Menlo Park, CA), 2698–2704.Google Scholar
• Shalev-Shwartz S, Singer Y (2007) A primal-dual perspective of online learning algorithms. Machine Learn. 69(2):115–142.Crossref, 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
• Talluri KT, van Ryzin GJ (2004) The Theory and Practice of Revenue Management, International Series in Operations Research & Management Science, vol. 68 (Springer, New York).Google Scholar
• Talluri KT, van Ryzin GJ (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, Berlin).Google Scholar
• Venkatasubramanian V (2010) Fairness is an emergent self-organized property of the free market for labor. Entropy 12(6):1514–1531.Crossref, Google Scholar
• Wang KW (1983) Optimum seat allocation for multi-leg flights with multiple fare types. AGIFORS Proc., 225–246.Google Scholar
• Xu J, Lee K, Li W, Qi H, Lu Q (2015) Smart pacing for effective online ad campaign optimization. Proc. 21th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 2217–2226.Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Internat. Workshop Internet Network Econom. (Springer, Berlin), 566–576.Crossref, Google Scholar
• Zhou Y-H, Liang C, Li N, Yang C, Zhu S, Jin R (2019) Robust online matching with user arrival distribution drift. Proc. AAAI Conf. Artificial Intelligence 33(1):459–466.Crossref, Google Scholar