Algorithmic models of human behavior and stochastic optimization
DOI:
https://doi.org/10.26577/jmmcs-2017-3-473Keywords:
Stochastic mirror descent, gradient methods, the search for equilibrium in transport networksAbstract
The article explores the parallelization of computations in solving stochastic optimization
problems; The application of the results obtained here to the search for an equilibrium distribution
of flows along paths is considered; The dependence of the rate of convergence of optimal algorithms
in the problems of stochastic, gradient optimization is investigated, depending on the number of
calls to the oracle behind the implementation of the function at each iteration. A distinctive feature
of this article is the demonstration of the results obtained with illustrative examples.
Key words: Stochastic mirror descent, gradient methods, the search for equilibrium in
References
[1] Agarwal A., Dekel O. and Xiao L., "Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit
Feedback."Proceedings of 23 Annual Conference on Learning Theory (2010): 528.
[2] Andersen S.P., de Palma A. and Thisse J.F., Discrete Choice Theory of Product Differentiation. (Cambridge: MIT Press,
1992), 423.
[3] Beckmann M., McGuire C.B. and Winsten C. Studies in the Economics of Transportation. (Santa Monica: RAND
Corporation, 1955), 323.
[4] Bubeck S. and Cesa-Bianchi N., "Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit
Problems"Foundation and Trends in Machine Learning 5(2012): 122.
[5] Bubeck S. and Eldan R., "Multi-Scale Exploration of Convex Functions and Bandit Convex Optimization"e-print, 2015,
http://research.microsoft.com/en-us/um/people/sebubeck/ConvexBandits.pdf
[6] Duchi J.C., Jordan M.I., Wainwright M.J. and Wibisono A., "Optimal Rates for Zero-Order Convex Optimization: the
Power of Two Function Evaluations"IEEE Transaction of Information 61(2015): 2952.
[7] Gasnikov A.V., Gasnikova Ye.V., Matsiyevskiy S.V. and Usik I.V., "O Svyazi Modeley Diskretnogo Vybora s
Raznomasshtabnymi po Vremeni Populyatsionnymi Igrami Zagruzok"Trudy MFTI. 7(2015): 204.
[8] Gasnikov A.V., Krymova Ye.A., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Stokhasticheskaya Onlain
Optimizatsiya. Odnotochechnyye i Dvukhtochechnyye Nelineynyye Mnogorukiye Bandity. Vypuklyy i Sil’no Vypuklyy
Sluchai."Avtomatika i Telemekhanika 2(2017): 144.
[9] Gasnikov A.V., Lagunovskaya A.A. and Morozova L.E., "O Svyazi Imitatsionnoy Logit Dinamiki v Populyatsionnoy Teorii
Igr i Metoda Zerkal’nogo Spuska v Onlayn Optimizatsii na Primere Zadachi Vybora Kratchayshego Marshruta."Trudy
MFTI 7(2015): 204.
[10] Gasnikov A.V., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Bezgradiyentnyye Proks-Metody s Netochnym
Orakulom Dlya Negladkikh Zadach Vypukloy Stokhasticheskoy Optimizatsii na Simplekse"Avtomatika i telemekhanika
10(2016): 166.
[11] Gasnikova Ye.V., "Modelirovaniye Dinamiki Makrosistem na Osnove Kontseptsii Ravnovesiya"(Associate prof. diss.,
MFTI, 2012).
[12] Hazan E., "Introduction to Online Convex Optimization."Foundations and Trends in Optimization 2(2016): 325.
[13] Hazan E. and Kale S., "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex
Optimization."JMLR 15(2014): 2512.
[14] Juditsky A., Lan G., Nemirovski A. and Shapiro A., "Stochastic Approximation Approach to Stochastic
Programming."SIAM Journal on Optimization 19 (2009): 2014.
[15] Juditsky A. and Nemirovski A., "First Order Methods for Nonsmooth Convex Large-Scale Optimization, I,
II."Optimization for Machine Learning (2012): 63.
[16] Ledoux M., Concentration of Measure Phenomenon (Amer Mathematical Society, 2001), 192.
[17] Lugosi G. and Cesa-Bianchi N., Prediction, Learning and Games. (New York: Cambridge University Press, 2006), 403.
[18] Nemirovski A., "Lectures on Modern Convex Optimization Analysis, Algorithms,
and Engineering Applications."Philadelphia: SIAM, 2016, accessed August 12, 2017,
http://www2.isye.gatech.edu/nemirovs/LectModConvOpt.pdf.
[19] Nemirovski А.С. and Judin D.B., Lozhnost’ Zadach i Effektivnost’ Metodov Optimizatsii (Moscow: Nauka, 1979), 384.
[20] Nesterov Yu., "Primal-Dual Subgradient Methods for Convex Problems."Math. Program. Ser. B. 120(2009): 287.
[21] Nesterov Y. and Vial J.-Ph., "Confidence Level Solution for Stochastic Programming."Automatica 44(2008): 1652.
[22] Polyak B.T., Vvedeniye v Optimizatsiyu (Moscow: Nauka, 1983), 384.
[23] Sandholm W., Population Games and Evolutionary Dynamics. Economic Learning and Social Evolution. (Cambridge:
MIT Press, 2010), 616.
[24] Sheffi Y., Urban Transportation Networks: Equilibrium Analysis With Mathematical Programming Methods. (N.J.:
Prentice-Hall Inc, 1985), 416.
[25] Razzhevaykin V.N., Analiz Modeley Dinamiki Populyatsiy. Uchebnoye posobiye. (Moscow: MFTI, 2010), 174.
Feedback."Proceedings of 23 Annual Conference on Learning Theory (2010): 528.
[2] Andersen S.P., de Palma A. and Thisse J.F., Discrete Choice Theory of Product Differentiation. (Cambridge: MIT Press,
1992), 423.
[3] Beckmann M., McGuire C.B. and Winsten C. Studies in the Economics of Transportation. (Santa Monica: RAND
Corporation, 1955), 323.
[4] Bubeck S. and Cesa-Bianchi N., "Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit
Problems"Foundation and Trends in Machine Learning 5(2012): 122.
[5] Bubeck S. and Eldan R., "Multi-Scale Exploration of Convex Functions and Bandit Convex Optimization"e-print, 2015,
http://research.microsoft.com/en-us/um/people/sebubeck/ConvexBandits.pdf
[6] Duchi J.C., Jordan M.I., Wainwright M.J. and Wibisono A., "Optimal Rates for Zero-Order Convex Optimization: the
Power of Two Function Evaluations"IEEE Transaction of Information 61(2015): 2952.
[7] Gasnikov A.V., Gasnikova Ye.V., Matsiyevskiy S.V. and Usik I.V., "O Svyazi Modeley Diskretnogo Vybora s
Raznomasshtabnymi po Vremeni Populyatsionnymi Igrami Zagruzok"Trudy MFTI. 7(2015): 204.
[8] Gasnikov A.V., Krymova Ye.A., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Stokhasticheskaya Onlain
Optimizatsiya. Odnotochechnyye i Dvukhtochechnyye Nelineynyye Mnogorukiye Bandity. Vypuklyy i Sil’no Vypuklyy
Sluchai."Avtomatika i Telemekhanika 2(2017): 144.
[9] Gasnikov A.V., Lagunovskaya A.A. and Morozova L.E., "O Svyazi Imitatsionnoy Logit Dinamiki v Populyatsionnoy Teorii
Igr i Metoda Zerkal’nogo Spuska v Onlayn Optimizatsii na Primere Zadachi Vybora Kratchayshego Marshruta."Trudy
MFTI 7(2015): 204.
[10] Gasnikov A.V., Lagunovskaya A.A., Usmanova I.N. and Fedorenko F.A., "Bezgradiyentnyye Proks-Metody s Netochnym
Orakulom Dlya Negladkikh Zadach Vypukloy Stokhasticheskoy Optimizatsii na Simplekse"Avtomatika i telemekhanika
10(2016): 166.
[11] Gasnikova Ye.V., "Modelirovaniye Dinamiki Makrosistem na Osnove Kontseptsii Ravnovesiya"(Associate prof. diss.,
MFTI, 2012).
[12] Hazan E., "Introduction to Online Convex Optimization."Foundations and Trends in Optimization 2(2016): 325.
[13] Hazan E. and Kale S., "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex
Optimization."JMLR 15(2014): 2512.
[14] Juditsky A., Lan G., Nemirovski A. and Shapiro A., "Stochastic Approximation Approach to Stochastic
Programming."SIAM Journal on Optimization 19 (2009): 2014.
[15] Juditsky A. and Nemirovski A., "First Order Methods for Nonsmooth Convex Large-Scale Optimization, I,
II."Optimization for Machine Learning (2012): 63.
[16] Ledoux M., Concentration of Measure Phenomenon (Amer Mathematical Society, 2001), 192.
[17] Lugosi G. and Cesa-Bianchi N., Prediction, Learning and Games. (New York: Cambridge University Press, 2006), 403.
[18] Nemirovski A., "Lectures on Modern Convex Optimization Analysis, Algorithms,
and Engineering Applications."Philadelphia: SIAM, 2016, accessed August 12, 2017,
http://www2.isye.gatech.edu/nemirovs/LectModConvOpt.pdf.
[19] Nemirovski А.С. and Judin D.B., Lozhnost’ Zadach i Effektivnost’ Metodov Optimizatsii (Moscow: Nauka, 1979), 384.
[20] Nesterov Yu., "Primal-Dual Subgradient Methods for Convex Problems."Math. Program. Ser. B. 120(2009): 287.
[21] Nesterov Y. and Vial J.-Ph., "Confidence Level Solution for Stochastic Programming."Automatica 44(2008): 1652.
[22] Polyak B.T., Vvedeniye v Optimizatsiyu (Moscow: Nauka, 1983), 384.
[23] Sandholm W., Population Games and Evolutionary Dynamics. Economic Learning and Social Evolution. (Cambridge:
MIT Press, 2010), 616.
[24] Sheffi Y., Urban Transportation Networks: Equilibrium Analysis With Mathematical Programming Methods. (N.J.:
Prentice-Hall Inc, 1985), 416.
[25] Razzhevaykin V.N., Analiz Modeley Dinamiki Populyatsiy. Uchebnoye posobiye. (Moscow: MFTI, 2010), 174.
Downloads
How to Cite
Bektemessov, M. A., Gasnikov, A. V., Lagunskaya А А. А., & Ordabayeva, Z. M. (2018). Algorithmic models of human behavior and stochastic optimization. Journal of Mathematics, Mechanics and Computer Science, 95(3), 50–68. https://doi.org/10.26577/jmmcs-2017-3-473
Issue
Section
Applied Mathematics
