On the dual gradient descent method for the resource allocation problem in multiagent systems

D. B. Rokhlin

Sibirskij žurnal industrialʹnoj matematiki, Tome 27 (2024) no. 2, pp. 80-99

Résumé

We consider a sequence of block-separable convex programming problems describing the resource allocation in multiagent systems. We construct several iterative algorithms for setting the resource prices. Under various assumptions about the utility functions and resource constraints, we obtain estimates for the average deviation (regret) of the objective function from the optimal value and the constraint residuals. Here the average is understood as the expectation for independent identically distributed data and as the time average in the online optimization problem. The analysis of the problem is carried out by online optimization methods and duality theory. The algorithms considered use the information concerning the difference between the total demand and supply that is generated by agents' reactions to prices and corresponds to the constraint residuals.

Détail

Keywords: online optimization, duality, revealed preferences.
Mots-clés : adaptive gradient descent, regret

Bibliographie

[1] Bertsekas D. P., Nonlinear Programming, Athena Scientific, Belmont, 2016

[2] Rockafellar R. T., “Problem decomposition in block-separable convex optimization: Ideas old and new”, J. Nonlinear Convex Anal., 19:9 (2018), 1459–1474

[3] J.-P. Aubin, L'analyse non linéaire et ses motivations économiques, Masson, Paris—New York—Barcelone, 1984

[4] Jalota D., Gopalakrishnan K., Azizan N., Johari R., Pavone M., “Online learning for traffic routing under unknown preferences”, Proc. 26th Int. Conf. Artif. Intell. Stat., PMLR, 206, 2023, 3210–3229, arXiv: 2203.17150

[5] Beck A., Nedić A., Ozdaglar A., Teboulle M., “An $O(1/k)$ gradient method for network resource allocation problems”, IEEE Trans. Control. Netw. Syst., 1:1 (2014), 64–73 | DOI

[6] E. A. Vorontsova, A. V. Gasnikov, A. S. Ivanova, and E. A. Nurminsky, “The Walrasian equilibrium and centralized distributed optimization in terms of modern convex optimization methods by an example of the resource allocation problem”, Numer. Anal. Appl., 12:4 (2019), 338–358 | DOI

[7] Dengl R., “Smart grid and demand side management”, Handbook of real-time computing, 2022, 681–703 | DOI

[8] Mahdavi M., Jin R., Yang T., “Trading regret for efficiency: online convex optimization with long term constraints”, J. Mach. Learn. Res., 13:1 (2012), 2503–2528

[9] Zinkevich M., “Online convex programming and generalized infinitesimal gradient ascent”, Proc. Twentieth Int. Conf. Mach. Learn, AAAI Press, USA, 2003, 928–936

[10] Hazan E., Introduction to online convex optimization, MIT Press, Cambridge—Massachusetts, 2022

[11] Cesa-Bianchi N., Conconi A., Gentile C., “On the generalization ability of on-line learning algorithms”, IEEE Trans. Inf. Theory, 50:9 (2004), 2050–2057 | DOI

[12] Shalev-Shwartz S., “Online learning and online convex optimization”, Found. Trends Mach. Learn, 4:2 (2012), 107–194 | DOI

[13] Cutkosky A., “Anytime online-to-batch, optimism and acceleration”, Proc. 36th Int. Conf. Mach. Learn, PMLR, 97, 2019, 1446–1454

[14] Chen T., Ling Q., Giannakis G. B., “An online convex optimization approach to proactive network resource allocation”, IEEE Trans. Signal Process, 65:24 (2017), 6350–6364 | DOI

[15] Yu H., Neely M. J., “A low complexity algorithm with $O(\sqrt{T})$ regret and $O(1)$ constraint violations for online convex optimization with long term constraints”, J. Mach. Learn. Res., 21:1 (2020), 1–24

[16] Yi X., Li X., Yang T., Xie L., Johansson K., “Regret and cumulative constraint violation analysis for online convex optimization with long term constraints”, Proc. 38th Int. Conf. Mach. Learn, PMLR, 139, 2021, 11998–12008

[17] Jalota D., Sun H., Azizan N., Online learning for equilibrium pricing in markets under incomplete information, 2023 | DOI

[18] Roth A., Ullman J., Wu Z. S., “Watch and learn: optimizing from revealed preferences feedback”, Proc. forty-eighth Annual ACM Symp. Theory Comput., ACM, New York, 2016, 949–962 | DOI

[19] Ji Z., Mehta R., Telgarsky M., “Social welfare and profit maximization from revealed preferences”, Lect. Notes Comput. Sci., 11316, 2018, 264–281 | DOI

[20] Roth A., Slivkins A., Ullman J., Wu Z. S., “Multidimensional dynamic pricing for welfare maximization”, ACM Trans. Econ. Comput., 8:1 (2020), 1–35 | DOI

[21] R. T. Rockafellar, Convex Analysis, Princeton Univ. Press, Princeton, 1970

[22] Bertsekas D. P., Nedic A., Ozdaglar A. E., Convex analysis and optimization, Athena Scientific, Belmont, 2003

[23] Beck A., First-order methods in optimization, SIAM, Philadelphia, 2017 | DOI

[24] Orabona F., A Modern Introduction to Online Learning, 2019, arXiv: 1912.13213 | DOI

[25] Auer P., Cesa-Bianchi N., Gentile C., “Adaptive and self-confident on-line learning algorithms”, J. Comput. Syst. Sci., 64:1 (2002), 48–75 | DOI

[26] Aliprantis C. D., Border K. C., Infinite dimensional analysis: a hitchhiker's guide, Springer, Berlin, 2006 | DOI

[27] Rockafellar R. T., Wets R. J.-B., Variational analysis, Springer, Berlin, 2009

[28] Sh. Shalev-Shwartz and Sh. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge Univ. Press, Cambridge, 2014

[29] Nesterov Y., Shikhman V., “Dual subgradient method with averaging for optimal resource allocation”, Eur. J. Oper. Res., 270:3 (2018), 907–916 | DOI

[30] Shapiro A., Dentcheva D., Ruszczynski A., Lectures on stochastic programming: modeling and theory, SIAM, Philadelphia, 2009 | DOI

[31] Bertsekas D.P., “Stochastic optimization problems with nondifferentiable cost functionals”, J. Optim. Theory Appl., 12:2 (1973), 218–231 | DOI

[32] Shreve S. E., Stochastic salculus for finance II, continuous-time models, Springer, N. Y., 2004

[33] D. B. Rokhlin, “Resource allocation in communication networks with large number of users: The dual stochastic gradient method”, Theory Probab. Appl., 66:1 (2021), 105–120 | DOI

[34] Joulani P., Raj A., György A.,Szepesvári C., “A simpler approach to accelerated optimization: iterative averaging meets optimism”, Proc. 37th Int. Conf. Mach. Learn, PMLR, 119, 2020, 4984–4993

[35] Joulani P., György P., Szepesvári C., “A modular analysis of adaptive (non-)convex optimization: Optimism, composite objectives, variance reduction, and variational bounds”, Theor. Comput. Sci., 808:2 (2020), 108–138 | DOI

[36] E. A. Vorontsova, A. V. Gasnikov, P. E. Dvurechensky, A. S. Ivanova, and D. A. Pasechnyuk, “Numerical methods for the resource allocation problem in a computer network”, Comput. Math. Math. Phys., 61:2 (2021), 297–328 | DOI | DOI

[37] Yu. E. Nesterov, “A method for solving convex programming problems with complexity $O(1/k^2)$”, Dokl. Akad. Nauk SSSR, 269:3 (1982), 543–547

[38] Yu. E. Nesterov, Introduction to Convex Optimization, MTsNMO, M., 2010

[39] Nesterov Y., “Universal gradient methods for convex optimization problems”, Math. Program, 152:1–2 (2015), 381–404 | DOI