BEZGRADIENTNAYa STOKhASTIChESKAYa OPTIMIZATsIYa DLYa ADDITIVNYKh MODELEY

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

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

作者简介

A. AKhAVAN

Оксфордский университет, Великобритания

Email: arya.akhavan@stats.ox.ac.uk
д-р Великобритания

A. TsYBAKOV

Центр исследований по экономике и статистике (CREST); Парижская национальная школа статистики и экономического управления (ENSAE); Политехнический институт Парижа, Франция

Email: alexandre.tsybakov@ensae.fr
д-р физ.-мат. наук Франция

参考

  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.

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Russian Academy of Sciences, 2025