ПОИСКОВЫЙ МЕТОД СТОХАСТИЧЕСКОЙ НЕСТАЦИОНАРНОЙ ОПТИМИЗАЦИИ ФУНКЦИИ С ГЕЛЬДЕРОВСКИМ ГРАДИЕНТОМ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

В статье рассматривается поисковый метод стохастической оптимизации с возмущением на входе, предназначенный для отслеживания изменений точки минимума функции (трекинга) с гельдеровским градиентом в условиях наблюдений при почти произвольных неизвестных ограниченных помехах (unknown–but–bounded noise). Подобные методы используются в задачах адаптивного управления (энергетика, логистика, робототехника, трекинг целей), оптимизации зашумленных систем (биомоделирование, физические эксперименты) и онлайн-обучения с дрейфом параметров данных (финансы, потоковая аналитика). В качестве апробации алгоритма исследуется эффективность его работы в условиях, имитирующих отслеживание эволюции человеческих ожиданий в задачах обучения с подкреплением на основе обратной связи от человека и при отслеживании центра кластера задач в системах массового обслуживания. Поисковые методы с возмущениями на входе активно развивались в работах Б.Т. Поляка с 1990 г.

Об авторах

И. А АКИНФИЕВ

Санкт-Петербургский государственный университет

Email: i@iakinfiev.ru

О. Н ГРАНИЧИН

Санкт-Петербургский государственный университет; Институт проблем машиноведения РАН, Санкт-Петербург

Email: o.granichin@spbu.ru

Е. Ю ТАРАСОВА

Санкт-Петербургский государственный университет

Email: elizaveta.tarasova@spbu.ru

Список литературы

  1. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 384 с.
  2. Поляк Б.Т., Цыпкин Я.З. Псевдоградиентные алгоритмы адаптации и обучения // АиТ. 1973. № 3. С. 45–68.
  3. Поляк Б.Т., Цыпкин Я.З Адаптивные алгоритмы оценивания (сходимость, оптимальность, устойчивость) // АиТ. 1979. № 3. С. 71–84.
  4. Поляк Б.Т., Цыпкин Я.З. Оптимальные псевдоградиентные алгоритмы адаптации // АиТ. 1980. № 8. С. 74–84.
  5. Поляк Б.Т. О некоторых способах ускорения сходимости итерационных методов // Журн. вычисл. мат. и мат. физики. 1964. V. 4. № 5. С.791–803.
  6. Поляк Б.Т. Новый метод типа стохастической аппроксимации // АиТ. 1990. № 7. С. 98–108.
  7. Polgak B.T., Yuditskij A.B. Acceleration of stochastic approximation procedures by averaging // SIAM J. Contr. Optim. 1992. V. 30. No. 4. P. 838–855.
  8. Поляк Б.Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. I // АиТ. 1976. № 12. С. 83-94.
  9. Поляк Б.Т. Сходимость и скорость сходимости итеративных стохастических алгоритмов. II // АиТ. 1977. № 4 С. 101–107.
  10. Поляк Б.Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической оптимизации // Проблемы передачи информации. 1990. № 26. 2. С. 45–53.
  11. Распаригин Л.А. Статистические методы поиска. М.: Наука, 1968. 376 с.
  12. Граничин О.Н. Стохастическая аппроксимация с возмущением на входе при зависимых помехах наблюдения // Вестн. ЛГУ. 1989. С. 27–31.
  13. Spall J.C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation // IEEE Transact. Autom. Control. 1992. 37(3). С. 332–341.
  14. Spall J.C. A one-measurement form of simultaneous perturbation stochastic approximation // Automatica. 1997. 33(1). P. 109–112.
  15. Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003. 291 с.
  16. Granichin O., Volkovich V., Toledano-Kitai D. Randomized algorithms in automatic control and data mining. Berlin Heldenberg: Springer, 2015. 251 p.
  17. Попков А.Ю. Градиентные методы для нестационарных задач безусловной оптимизации // АиТ. 2005. № 6. С. 38–46.
  18. Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function // The Annals of Mathematical Statistics. 1952. 23(3). P. 462–466.
  19. Вахитов А.Т., Граничин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // АиТ. 2009. № 11. С. 70–79.
  20. Granichin O., Amelina N. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances // IEEE Transact. Autom. Control. 2015. V. 60. No. 6. P. 1653–1658.
  21. Шиблев И.А. Безградиентные методы оптимизации для функций с гельдеровым градиентом // Дисс. ... канд. физ.-мат. наук. Долгопрудный: МФТИ, 2024.
  22. Shibaev I., Dvurechensky P., Gasnikov A. Zeroth-order methods for noisy Holder-gradient functions // Optimization Letters. 2022. V. 16. P. 2123–2143.
  23. Mandelbrot B. New methods in statistical economics // Journal of Political Economy. 1963. V. 71. No. 5. P. 421–440.
  24. Bazumos A.T., Гранцман О.Н., Сысоев С.С. Точность оценивания рандомизированного алгоритма стохастической оптимизации // АиТ. 2006. № 4. С. 86–96.
  25. Гранцман О.Н. Поисковые алгоритмы стохастической аппроксимации с рандоминацией на входе // АиТ. 2015. № 5. С. 43–59.
  26. Min T. et al. Understanding Impact of Human Feedback via Influence Functions. arXiv preprint arXiv:2501.05790. 2025.
  27. Shen W. et al. Loose lips sink ships: mitigating length bias in reinforcement learning from human feedback // Findings of the Association for Computational Linguistics: EMNLP 2023, 2023. P. 2859–2873.
  28. Christiano P.F. et al. Deep reinforcement learning from human preferences // Advances in Neural Information Processing Systems. 2017. V. 30. P. 1–9.
  29. Sitemon N. et al. Learning to summarize with human feedback // Advances in Neural Information Processing Systems. 2020. V. 33. P. 3008–3021.
  30. Ouyang L. et al. Training language models to follow instructions with human feedback // Advances in Neural Information Processing Systems. 2022. V. 35. P. 27730–27744.
  31. Gans N., Koole G., Mandelbaum A. Telephone call centers: Tutorial, review, and research prospects // Manufacturing and Service Operations Management. 2003. V. 5. No. 2. P. 79–141.
  32. Anderson. C. The Long Tail: Why the Future of Business is Selling Less of More, NY.: Hyperion, 2006. 256 p.
  33. Goel S., Broder A., Gabrilovich E., Pang. B. Anatomy of the long tail: Ordinary People With Extraordinary Tastes // Proceedings of the Third ACM International Conference on Web Search and Data Mining (WSDM’10), ACM, New York, NY, USA, 2010. P. 201–210.
  34. Akinfiev I., Tarasova E. Cluster-Aware LVP: Enhancing Task Allocation with Growth Dynamics // 15th IFAC Workshop on Adaptive and Learning Control Systems (ALCOS), 2025.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025