Аннотация.

Рассматривается задача выпуклой стохастической оптимизации  и метод зеркального спуска (МЗС) как в «классической», так и в «адаптивной» постановке, когда последовательность  обобщенной температуры  не определена  априори и настраивается в процессе наблюдений градиента и итеративного оценивания оптимальной точки. Доказана соответствующая адаптивная верхняя граница ошибки (относительно оптимизируемой функции) в предположении известного ограничения нормы градиента с вероятностью 1. Это является своеобразной  платой за адаптивность метода по сравнению с более слабым ограничением в среднем в неадаптивной постановке.

Ключевые слова:

методы выпуклой оптимизации, задачи стохастической оптимизации, адаптивные алгоритмы, зеркальный спуск, верхняя граница.

Стр. 7-12.

A.V. Nazin

"The adaptive mirror descent algorithms in problems of stochastic convex optimization"

Abstract. The problem of convex stochastic optimization and the mirror descent method (MDM) both in a «classic» and «adaptive» setting, are treated, when a sequence of generalized temperature is not defined a priori and adjusted in process of gradient observations and iterative optimal point estimation. The corresponding adaptive upper bound on the error (relative to the optimizing function) is proved, under assumption of the given constraint on gradient norm with  probability 1.  This  is  a  kind  of  payment  for adaptability method in comparison with a weaker constraint on average in the non-adaptive setting.

Keywords: сonvex optimization methods, stochastic optimization problems, adaptive algorithms, mirror descent, upper bounds.

Полная версия статьи в формате pdf.

REFERENCES

1. Nemirovskiy  A. S.,  Yudin D. B.  Slozhnost  zadach  i effektivnost metodov optimizatsii — M.: Nauka. Glavnaya redaktsiya fiziko-matematicheskoy literatury, 1979. — 384 s.
2. Beck A., Teboulle M. Mirror descent and nonlinear pro- jected subgradient methods for convex optimization // Oper. Res. Lett., 2003. V. 31. No. 3. P. 167–175.
3. Nesterov Yu. Primal-dual subgradient methods for convex problems  //  Mathematical  Programming, 2009. V. 120. No. 1. P. 221–259.
4. Ben-Tal A., Margalit T., Nemirovski A. The Ordered Subsets Mirror Descent Optimization Method with Applications  to  Tomography  //  SIAM  J. Optim.  2001.  V. 12. No. 1. P. 79–108.
5. Claire Tauvel. Optimisation stochastique à grande échelle. PhD thesis, Université Joseph Fourier, Décembre 2008.
6. Nazin A., Polyak B. Adaptive Randomized Algorithm for Finding Eigenvector of Stochastic Matrix with Application to PageRank // Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, Shanghai, P. R. China, December 16–18, 2009.
7. Ben-Tal A., Nemirovski A. S. The Conjugate Barrier Mirror Descent Method for Non-Smooth Convex Optimization, MINERVA Optim. Center Report., Haifa: Faculty of Industrial Engineering and Management, Technion — Israel Institute of Technology, 1999.
8. Rockafellar R. T., Wets R. J. B. Variational Analysis, New
York: Springer, 1998.
9. Yuditskiy  A. B., Nazin A. V., Tsybakov A. B., Vayatis  N. Rekurrentnoe agregirovanie otsenok metodom zerkalnogo spuska s usredneniem // Problemy peredachi informatsii. 2005. № 4. C. 78–96.
10. Polyak B. T., Tsypkin Ya. Z. Kriterialnye algoritmy stokhasticheskoy optimizatsii   //   AiT. 1984. № 6.  S. 95–104.