- Код статьи
- S24139777S0005231025090025-1
- DOI
- 10.7868/S2413977725090025
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 9
- Страницы
- 28-45
- Аннотация
- Рассматривается задача оптимизации нулевого порядка по зашумленным наблюдениям для целевой функции, удовлетворяющей условию Поляка–Лоясевича или условию сильной выпуклости. Кроме того, предполагается, что целевая функция имеет аддитивную структуру и удовлетворяет свойству гладкости высокого порядка, характеризуемому гельдеровым семейством функций. Аддитивная модель для гельдеровых классов функций хорошо изучена в литературе по непараметрическому оцениванию функций; в частности, показано, что точность оценивания для такой модели существенно лучше, чем для гельдеровой модели без аддитивной структуры. В данной статье аддитивная модель изучается в задаче безградиентной оптимизации. Предлагается рандомизированная оценка градиента, позволяющая при подключении к алгоритму градиентного спуска достичь минимаксно-оптимальной ошибки оптимизации порядка dT, где d – размерность задачи, T – количество пробных точек, а β ⩾2 – гельдерова степень гладкости. Устанавливается, что, в отличие от непараметрических задач оценивания, использование аддитивных моделей в безградиентной оптимизации не приводит к существенному выигрышу в точности.
- Ключевые слова
- аддитивная модель безградиентная оптимизация минимаксная оптимальность условие Поляка–Лоясевича
- Дата публикации
- 24.02.2026
- Год выхода
- 2026
- Всего подписок
- 0
- Всего просмотров
- 3
Библиография
- 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.
