On some stochastic mirror descent methods for constrained online optimization problems

 pdf (153K)  / Annotation

List of references:

  1. B. Awerbuch, R. Kleinberg. Online linear optimization and adaptive routing // Journal of Computer and System Sciences. — 2008. — V. 74, no. 1. — P. 97–114. — DOI: 10.1016/j.jcss.2007.04.016. — MathSciNet: MR2364184.
  2. A. Bayandina. Adaptive Stochastic Mirror Descent for Constrained Optimization. — 2017. — https://arxiv.org/pdf/1705.02031.pdf .
  3. A. Bayandina, A. Gasnikov, E. Gasnikova, S. Matsievsky. Primal-dual mirror descent for the stochastic programming problems with functional constraints // Computational Mathematics and Mathematical Physics. — 2018. — (accepted). — https://arxiv.org/pdf/1604.08194.pdf. — in Russian. — MathSciNet: MR3884238.
  4. A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, A. Titov. Mirror descent and convex optimization problems with non-smooth inequality constraints / Large-Scale and Distributed Optimization. Lecture Notes in Mathematics. — 2018. — V. 2227. — P. 181–213. — MathSciNet: MR3888675.
  5. A. Beck, A. Ben-Tal, N. Guttmann-Beck, L. Tetruashvili. The comirror algorithm for solving nonsmooth constrained convex problems // Operations Research Letters. — 2010. — V. 38, no. 6. — P. 493–498. — DOI: 10.1016/j.orl.2010.08.005. — MathSciNet: MR2734206.
  6. A. Beck, M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization // Operations Research Letters. — 2003. — V. 31, no. 3. — P. 167–175. — DOI: 10.1016/S0167-6377(02)00231-6. — MathSciNet: MR1967286.
  7. A. Ben-Tal, A. Nemirovski. Lectures on Modern Convex Optimization. — Philadelphia: Society for Industrial and Applied Mathematics, 2001. — 590 p. — MathSciNet: MR1857264.
  8. A. Ben-Tal, A. Nemirovski. Robust Truss Topology Design via semidefinite programming // SIAM Journal on Optimization. — 1997. — V. 7, no. 4. — P. 991–1016. — DOI: 10.1137/S1052623495291951. — MathSciNet: MR1479611.
  9. S. Boyd, L. Vandenberghe. Convex Optimization. — New York: Cambridge University Press, 2004. — 730 p. — MathSciNet: MR2061575.
  10. S. Bubeck, R. Eldan. Multi-scale exploration of convex functions and bandit convex optimization. — 2015. — e-print. — http://research.microsoft.com/en-us/um/people/sebubeck/ConvexBandits.pdf.
  11. S. Bubeck, N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems // Foundation and Trends in Machine Learning. — 2012. — V. 5, no. 1. — P. 1–122. — DOI: 10.1561/2200000024.
  12. A. V. Gasnikov, A. A. Lagunovskaya, L. E. Morozova. On the relationship between simulation logit dynamics in the population game theory and a mirror descent method in the online optimization using the example of the shortest path problem // PROCEEDINGS OF MIPT. — 2015. — V. 7, no. 4. — P. 104–113. — in Russian.
  13. A. V. Gasnikov, A. A. Lagunovskaya, I. N. Usmanova, F. A. Fedorenko, E. A. Krymova. Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and stronglyconvex case // Automation and Remote Control. — 2017. — V. 78, no. 2. — P. 224–234. — DOI: 10.1134/S0005117917020035. — MathSciNet: MR3665422.
  14. E. Hazan, S. Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic stronglyconvex optimization // JMLR. — 2014. — V. 15. — P. 2489–2512. — MathSciNet: MR3247148.
  15. E. Hazan. Introduction to online convex optimization // Foundations and Trends in Optimization. — 2015. — V. 2, no. 3–4. — P. 157–325.
  16. Hao Yu, Neely M. J., Wei. Xiaohan. Online Convex Optimization with Stochastic Constraints. — 2017. — https://arxiv.org/pdf/1708.03741.pdf .
  17. R. Jenatton, J. Huang, C. Archambeau. Adaptive Algorithms for Online Convex Optimization with Long-term Constraints. — 2015. — https://arxiv.org/abs/1512.07422 .
  18. A. Kalai, S. Vempala. Efficient algorithms for online decision problems // Journal of Computer and System Sciences. — 2005. — V. 71. — P. 291–307. — DOI: 10.1016/j.jcss.2004.10.016. — MathSciNet: MR2168355.
  19. G. Lugosi, N. Cesa-Bianchi. Prediction, learning and games. — New York: Cambridge University Press, 2006. — 403 p. — MathSciNet: MR2409394.
  20. A. Nemirovski. Efficient methods for large-scale convex optimization problems // Ekonomika i Matematicheskie Metody. — 1979. — V. 15, no. 1. — in Russian.
  21. A. Nemirovsky, D. Yudin. Problem Complexity and Method Efficiency in Optimization. — New York: J. Wiley & Sons, 1983. — 404 p. — MathSciNet: MR0702836.
  22. Yu. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. — Massachusetts: Kluwer Academic Publishers, 2004. — 236 p. — MathSciNet: MR2142598.
  23. B. Polyak. A general method of solving extremum problems // Soviet Mathematics Doklady. — 1967. — V. 8, no. 3. — P. 593–597. — in Russian. — MathSciNet: MR0217997.
  24. N. Z. Shor. Generalized gradient descent with application to block programming // Kibernetika. — 1967. — V. 3, no. 3. — P. 53–55. — in Russian.
  25. F. S. Stonyakin, M. S. Alkousa, A. N. Stepanov, M. A. Barinov. Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints // Trudy Instituta Matematiki i Mekhaniki URO RAN. — 2018. — V. 24, no. 2. — P. 266–279. — DOI: 10.21538/0134-4889-2018-24-2-266-279. — Math-Net: Mi eng/timm1541. — MathSciNet: MR3853340.
  26. S. Shpirko, Yu. Nesterov. Primal-dual subgradient methods for huge-scale linear conic problem // SIAM Journal on Optimization. — 2014. — V. 24, no. 3. — P. 1444–1457. — DOI: 10.1137/130929345. — MathSciNet: MR3257645.
  27. A. A. Titov, F. S. Stonyakin, A. V. Gasnikov, M. S. Alkousa. Mirror Descent and Constrained Online Optimization Problems // Communications in Computer and Information Science. — 2019. — V. 974. — P. 64–78. — Optimization and Applications. 9th International Conference OPTIMA- 2018 (Petrovac, Montenegro, October 1–5, 2018). Revised Selected Papers. — DOI: 10.1007/978-3-030-10934-9_5.
  28. M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent / Proceedings of International Conference on Machine Learning (ICML). — 2003.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"