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

Обложка

Цитировать

Полный текст

Аннотация

В статье рассматривается поисковый метод стохастической оптимизации с возмущением на входе, предназначенный для отслеживания изменений точки минимума функции (трекинга) с гельдеровским градиентом в условиях наблюдений при почти произвольных неизвестных ограниченных помехах (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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».