BEZGRADIENTNAYa STOKhASTIChESKAYa OPTIMIZATsIYa DLYa ADDITIVNYKh MODELEY

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Acesso é pago ou somente para assinantes

Resumo

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

Sobre autores

A. AKhAVAN

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

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

A. TsYBAKOV

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

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

Bibliografia

  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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © Russian Academy of Sciences, 2025