Polyak’s Method Based on the Stochastic Lyapunov Function for Justifying the Consistency of Estimates Produced by a Stochastic Approximation Search Algorithm under an Unknown-But-Bounded Noise

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

In 1976–1977, Polyak published in the journal Avtomatica i Telemekhanika (Automation and Remote Control) two remarkable papers on how to study the properties of estimates of iterative pseudogradient algorithms. The first paper published in 1976 considered the general case based on the stochastic Lyapunov function, and the second one considered the linear case. The assumptions formulated in these papers and the estimates obtained in them can still be considered the state-of-the art. In the current paper, Polyak’s approach is applied to the study of the properties of estimates of a (randomized) stochastic approximation search algorithm for the case of unknown-but-bounded noise in observations. The obtained asymptotic estimates were already known earlier, and exact estimates for a finite number of observations are published for the first time.

Толық мәтін

Рұқсат жабық

Авторлар туралы

O. Granichin

Saint Petersburg State University; Mechanical Engineering Research Institute, Russian Academy of Sciences

Хат алмасуға жауапты Автор.
Email: oleg_granichin@mail.ru
Ресей, Saint Petersburg; Saint Petersburg

Yu. Ivansky

Saint Petersburg State University; Mechanical Engineering Research Institute, Russian Academy of Sciences

Email: oleg_granichin@mail.ru
Ресей, Saint Petersburg; Saint Petersburg

K. Kopylova

Saint Petersburg State University

Email: oleg_granichin@mail.ru
Ресей, Saint Petersburg

Әдебиет тізімі

  1. Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вест. Ленингр. ун-та. 1989. Т. 1. № 1. С. 19—21.
  2. Поляк Б. Т., Цыбаков А. Б. О некоторых способах ускорения сходимости итерационных методов // Пробл. передачи информ. 1990. Т. 26. № 2. С. 126—133.
  3. Spall J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation// IEEE Trans. Autom. Control. 1992. V. 37. Iss. 6. P. 332—341.
  4. Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемехан. 1992. № 2. C. 97—104.
  5. Polyak B. T., Tsybakov A. B. On stochastic approximation with arbitrary noise (the KW-case) // Adv. Sov. Math. 1992. V. 12. Iss. 8.
  6. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003.
  7. Spall J. C. A one-measurement form of simultaneous perturbation stochastic approximation // Automatica. 1997. V. 33. Iss. 1. P. 109—112.
  8. Chen H., Duncan T. E., Pasik-Duncan B. A Kiefer-Wolfowitz algorithm with randomized differences // IEEE Trans. Autom. Control. 1999. V. 44. Iss. 3. P. 442—453.
  9. Lobanov A., Gasnikov A., Stonyakin F. Highly smoothness zero-order methods for solving optimization problems under PL condition // arXiv preprint arXiv:2305.15828; 2023.
  10. Dvinskikh D., Tominin V., Tominin Y., Gasnikov A. Gradient-free optimization for non-smooth saddle point problems under adversarial noise // arXiv preprint arXiv:2202.06114; 2022.
  11. Akhavan A., Chzhen E., Pontil M., Tsybakov A. B. Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm // arXiv preprint arXiv:2306.02159; 2023.
  12. Antal C., Granichin O. N., Levi S. Adaptive autonomous soaring of multiple UAVs using simultaneous perturbation stochastic approximation // 49th IEEE Conf. on Decision and Control (CDC), 2010. P. 3656—3661.
  13. Granichin O., Amelina N. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances // IEEE Trans. Autom. Control. 2015. V. 60. Iss. 6. P. 1653—1658.
  14. Granichin O. N., Erofeeva V. A., Ivanskiy Y. V., Jiang Y. Simultaneous perturbation stochastic approximation-based consensus for tracking under unknown-but-bounded disturbances // IEEE Trans. Autom. Control. 2021. V. 66. Iss. 8. P. 3710—3717.
  15. Erofeeva V. А., Granichin O. N., Tursunova M., Sergeenko A., Jiang Y. Accelerated simultaneous perturbation stochastic approximation for tracking under unknown-but-bounded disturbances // Am. Control Conf. (ACC) 2022. P. 1582—1587.
  16. Поляк Б. Т. О некоторых способах ускорения сходимости итерационных методов // Ж. вычисл. матем. и матем. физ. 1964. Т. 4. № 5. С. 791—803.
  17. Аблаев С. С., Безносиков А. Н., Гасников А. В., Двинских Д. М., Лобанов A. B., Пучинин C. М., Стонякин Ф. С. О некоторых работах Бориса Теодоровича Поляка по сходимости градиентных методов и их развитии // Ж. вычисл. матем. и матем. физ. 2024. Т. 64. № 4. С. 25–64.
  18. Поляк Б. Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. I. Общий случай // Автоматика и телемехан. 1976. № 12. С. 83—94.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© Russian Academy of Sciences, 2024