Algorithmic models of human behavior and stochastic optimization

Authors

  • M. A. Bektemessov al-Farabi Kazakh National University, Almaty, Republic of Kazakhstan
  • A. V. Gasnikov Moscow Institute of Physics and Technology, Moscow, Russian Federation
  • А. А. Lagunskaya А Moscow Institute of Physics and Technology, Moscow, Russian Federation
  • Zh. M. Ordabayeva al-Farabi Kazakh National University, Almaty, Republic of Kazakhstan

DOI:

https://doi.org/10.26577/jmmcs-2017-3-473

Keywords:

Stochastic mirror descent, gradient methods, the search for equilibrium in transport networks

Abstract

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.

Downloads

Published

2018-08-24