BEZGRADIENTNAYa STOKhASTIChESKAYa OPTIMIZATsIYa DLYa ADDITIVNYKh MODELEY

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Рассматривается задача оптимизации нулевого порядка по зашумленным наблюдениям для целевой функции, удовлетворяющей условию Поляка–Лоясевича или условию сильной выпуклости. Кроме того, предполагается, что целевая функция имеет аддитивную структуру и удовлетворяет свойству гладкости высокого порядка, характеризуемому гельдеровым семейством функций. Аддитивная модель для гельдеровых классов функций хорошо изучена в литературе по непараметрическому оцениванию функций; в частности, показано, что точность оценивания для такой модели существенно лучше, чем для гельдеровой модели без аддитивной структуры. В данной статье аддитивная модель изучается в задаче безградиентной оптимизации. Предлагается рандомизированная оценка градиента, позволяющая при подключении к алгоритму градиентного спуска достичь минимаксно-оптимальной ошибки оптимизации порядка dT−(β−1)/β, где d – размерность задачи, T – количество пробных точек, а β ⩾2 – гельдерова степень гладкости. Устанавливается, что, в отличие от непараметрических задач оценивания, использование аддитивных моделей в безградиентной оптимизации не приводит к существенному выигрышу в точности.

References

  1. Stone C.J. Additive regression and other nonparametric models // Annals of Statistics. 1985. V. 13. P. 689–705.
  2. Hastie T., Tibshirani R. Generalized additive models // Statistical Science. 1986. V. 1. No. 3. P. 297–310.
  3. Wood S.N. Generalized additive models. Chapman and Hall/CRC, 2017.
  4. Stone C.J. Optimal rates of convergence for nonparametric estimators // Annals of Statistics. 1980. V. 8. P. 1348–1360.
  5. Stone C.J. Optimal global rates of convergence for nonparametric regression // Annals of Statistics. 1982. V. 10. P. 1040–1053.
  6. Ibragimov I.A., Khas’minskiˇı R.Z. Statistical estimation: Asymptotic theory. Springer, 1981.
  7. Ибрагимов И.А., Хасьминский Р.З. О границах качества непараметрического оценивания регрессии // Теория вероятн. и ее примен. 1982. V. 27. No. 1. P. 81–94.
  8. Поляк Б.Т. Градиентные методы минимизации функционалов // Ж. вычисл. матем. и матем. физ. 1963. V. 3. No. 4. P. 643–653.
  9. Lojasiewicz S. A topological property of real analytic subsets // Coll. du CNRS, Les ´equations aux d´eriv´ees partielles. 1963. V. 117. No. 2. P. 87–89.
  10. Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function // Annals of Mathematical Statistics. 1952. V. 23. P. 462–466.
  11. Fabian V. Stochastic approximation of minima with improved asymptotic speed // Annals of Mathematical Statistics. 1967. V. 38. No. 1. P. 191–200.
  12. Nemirovsky A.S., Yudin D.B. Problem complexity and method efficiency in optimization. Wiley & Sons, 1983.
  13. Поляк Б.Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической оптимизации // Пробл. передачи информ. 1990. V. 26. No. 2. P. 45–53.
  14. Jamieson K.G., Nowak R., Recht B. Query complexity of derivative-free optimization // Advances in Neural Information Processing Systems. 2012. V. 26. P. 2672– 2680.
  15. Shamir O. On the complexity of bandit and derivative-free stochastic convex optimization // Proc. 30th Annual Conference on Learning Theory. 2013. P. 1–22.
  16. Ghadimi S., Lan G. Stochastic firstand zeroth-order methods for nonconvex stochastic programming // SIAM Journal on Optimization. 2013. V. 23(4). P. 2341–2368.
  17. Nesterov Y., Spokoiny V. Random gradient-free minimization of convex functions // Foundations of Computational Mathematics. 2017. V. 17. No. 2. P. 527–566.
  18. Bach F., Perchet V. Highly-smooth zero-th order online optimization // Proc. 29th Annual Conference on Learning Theory. 2016.
  19. Akhavan A., Pontil M., Tsybakov A.B. Exploiting higher order smoothness in derivative-free optimization and continuous bandits // Advances in Neural Information Processing Systems. 2020. V. 33. P. 9017–9027.
  20. Balasubramanian K., Ghadimi S. Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionality, and saddle points // Foundations of Computational Mathematics. 2021. P. 1–42.
  21. Akhavan A., Chzhen E., Pontil M., Tsybakov A.B. Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm // Journal of Machine Learning Research. 2024. V. 25. No. 370. P. 1–50.
  22. Гасников А.В., Лагуновская А.А., Усманова И.Н., Федоренко Ф.A. Безградиентные прокc-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе // Автомат. и телемех. 2016. No. 10. P. 57–77.
  23. Novitskii V., Gasnikov A. Improved exploitation of higher order smoothness in derivative-free optimization // Optimization Letters. 2022. V. 16. P. 2059–2071.
  24. Akhavan A., Pontil M., Tsybakov A.B. Distributed zero-order optimization under adversarial noise // Advances in Neural Information Processing Systems. 2021. V. 34. P. 10209–10220.
  25. Gasnikov A.V., Lobanov A.V., Stonyakin F.S. Highly smooth zeroth-order methods for solving optimization problems under the PL condition // Computational Mathematics and Mathematical Physics. 2024. V. 64. P. 739–770.
  26. Yu Q., Wang Y., Huang B., et al. Stochastic zeroth-order optimization under strong convexity and Lipschitz Hessian: Minimax sample complexity // Advances in Neural Information Processing Systems. 2024. V. 37.
  27. Fokkema H., van der Hoeven D., Lattimore T., Mayo J.J. Online Newton method for bandit convex optimisation // arXiv preprint arXiv:2406.06506. 2024.
  28. Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximalgradient methods under the Polyak–Lojasiewicz condition // Machine Learning and Knowledge Discovery in Databases. 2016. P. 795–811.
  29. Tsybakov A.B. Introduction to nonparametric estimation. New York: Springer, 2009.
  30. Граничин О.Н. Процедура стохастической аппроксимации с возмущением на входе // Автомат. и телемех. 1992. No. 2. P. 97–104.
  31. Polyak B.T., Tsybakov A.B. On stochastic approximation with arbitrary noise (the KW-case) // Advances in Soviet Mathematics, vol. 12. 1992. P. 107–113.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences

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

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») на элемент с текстом «Принять и продолжить».