42837

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Пленарный доклад

Название: 

Algorithms of Inertial Mirror Descent in Convex Optimization Problems

Электронная публикация: 

Да

Наименование конференции: 

  • 17th Baikal international school-seminar "Methods of Optimization and Their Applications" (Иркутск, 2017)

Наименование источника: 

  • Abstracts of the 17th Baikal international school-seminar "Methods of Optimization and Their Applications" (Иркутск, 2017)

Город: 

  • Irkutsk

Издательство: 

  • ИСЭМ СО РАН

Год издания: 

2017

Страницы: 

9-9
Аннотация
Consider a problem of minimizing the mathematical expectation of a convex loss function on a given convex compact set of a finite-dimensional real space $E$ with a norm $\|\cdot\|$. The oracle produces unbiased stochastic subgradients of the loss function at current points with a uniformly bounded second moment of dual norm in $E^*$. The goal is to modify the well-known method of Mirror Descent (MD) proposed in 1979 by A.S. Nemirovskii and D.B. Yudin [1] and generalized the famous gradient method from the Euclidean case to an arbitrary primal-dual pair of spaces $(E,E^*)$; see also [2] and the references therein. In this paper (cf. [3]): - The idea of a new, so-called inertial MD method is demonstrated on the example of a deterministic optimization problem with continuous time; in particular, in the Euclidean case the heavy ball method [4] is realized; it is noted that the new method does not use additional averaging; - The discrete algorithm of the inertial MD is described; the theorem on the upper bound on the regret is proved (i.e., the difference between the current mean loss value and the minimum value) for the problem of stochastic optimization; - An illustrative computational example is given. In the conclusion, we discuss future work on both deterministic and stochastic algorithms of inertial mirror descent. References [1] Nemirovskii, A. S. and Yudin, D. B., Slozhnost’ zadach i effektivnost’ metodov optimizatsii, Moscow: Nauka, 1979 (in Russian). Translated under the title Problem Complexity and Method Efficiency in Optimization, Chichester: Wiley, 1983. [2] Juditsky, A. B., Nazin, A. V., Tsybakov, A. B., and N. Vayatis, N.: Recursive aggregation of estimators by the mirror descent algorithm with averaging // Problems of Information Transmission, 41(4):368–384, 2005. Translated from Problemy Peredachi Informatsii, No.4, 2005, pp.78–96. [3] Nazin, A. V.: Algorithms of Inertial Mirror Descent in Convex Problems of Stochastic Optimization // Automation and Remote Control. 2017. Submitted. [4] Polyak, B. T.: Some methods of speeding up the convergence of iteration methods // USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964.

Библиографическая ссылка: 

Назин А.В. Algorithms of Inertial Mirror Descent in Convex Optimization Problems / Abstracts of the 17th Baikal international school-seminar "Methods of Optimization and Their Applications" (Иркутск, 2017). Irkutsk: ИСЭМ СО РАН, 2017. С. 9-9.