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

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Современные методы оптимизации часто сталкиваются с ограниченным доступом к значениям целевой функции, что приводит к развитию работ посвященным сравнительному оракулу. В этом обзоре предоставляются современные алгоритмы гладкой многомерной оптимизации, использующие только информацию о порядке значений функции, но не их числовые значения. Рассматриваются как неускоренные, так и ускоренные методы, включая последние достижения в области оптимизации со сравнительным оракулом. Особое внимание уделяется разнообразию подходов к созданию алгоритмов, достигающих сходимости, сопоставимой с методами первого порядка (координатными алгоритмами), а также первому ускоренному методу в данной концепции оракула. Кроме того, обсуждаются стохастическое обобщение сравнительного оракула и их теоретические гарантии.

Об авторах

А. В Лобанов

Национальный исследовательский университет "Высшая школа экономики"; Московский физико-технический институт

Email: lobbsasha@mail.ru
Москва, Россия

А. В Гасников

Университет Иннополис; Московский физико-технический институт

Email: gasnikov@yandex.ru
член-корреспондент РАН Иннополис, Россия; Москва, Россия

Список литературы

  1. Conn A.R., Scheinberg K., and Vicente L.N. Introduction to derivative-free optimization // SIAM. 2009.
  2. Kimiaei M. and Neumaier A. Efficient unconstrained black box optimization // Mathematical Programming Computation. V. 14(2). 2022. P. 365–414.
  3. Rosenbrock H. An automatic method for finding the greatest or least value of a function // The computer journal. V. 3(3). 1960. P. 175–184.
  4. Chen P.Y., Zhang H., Sharma Y., Yi J., and Hsieh C.J. Zoo: Zeroth order optimization based blackbox attacks to deep neural networks without training substitute models // In Proceedings of the 10th ACMworkshop on artificial intelligence and security. 2017. P. 15–26.
  5. Gao J., Lanchantin J., Soffa M.L., and Qi Y. Black-box generation of adversarial text sequences to evade deep learning classifiers // In 2018 IEEE Security and Privacy Workshops (SPW). IEEE. 2018. P. 50–56.
  6. Dai Z., Low B.K.H., and Jaillet P. Federated bayesian optimization via thompson sampling // Advances in Neural Information Processing Systems. V. 33. 2020. P. 9687–9699.
  7. Alashqar B., Gasnikov A., Dvinskikh D., and Lobanov A. Gradient-free federated learning methods with l1 and l2-randomization for non-smooth convex stochastic optimization problems // Computational Mathematics and Mathematical Physics. V. 63(9). 2023. P. 1600–1653.
  8. Patel K.K., Saha A., Wang L., and Srebro N. Distributed online and bandit convex optimization // In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop). 2022.
  9. Choromanski K., Rowland M., Sindhwani V., Turner R., and Weller A. Structured evolution with compact architectures for scalable policy optimization / In International Conference on Machine Learning. PMLR. 2018. P. 970–978.
  10. Mania H., Guy A., and Recht B. Simple random search of static linear policies is competitive for reinforcement learning // Advances in Neural Information Processing Systems. V. 31. 2018.
  11. Lobanov A. and Gasnikov A. Accelerated zero-order sgd method for solving the black box optimization problem under “overparametrization” condition / In International Conference on Optimization and Applications. Springer. 2023. P. 72–83.
  12. Agarwal A., Dekel O., and Xiao L. Optimal algorithms for online convex optimization with multi-point bandit feedback // In Colt. Citeseer. 2010. P. 28–40.
  13. Bach F. and Perchet V. Highly-smooth zero-th order online optimization // In Conference on Learning Theory. PMLR. 2016. P. 257–283.
  14. Akhavan A., Chzhen E., Pontil M., and Tsybakov A. A gradient estimator via l1-randomization for online zero-order optimization with two point feedback // Advances in Neural Information Processing Systems. V. 35. 2022. P. 7685–7696.
  15. Shamir O. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback // The Journal of Machine Learning Research. V. 18(1). 2017. P. 1703–1713.
  16. Lattimore T. and Gyorgy A. Improved regret for zeroth-order stochastic convex bandits // In Conference on Learning Theory. PMLR. 2021. P. 2938–2964.
  17. Bergstra J. and Bengio Y. Random search for hyper-parameter optimization // Journal of machine learning research. V. 13(2). 2012.
  18. Hernandez-Lobato J.M., Hoffman M.W., and Ghahramani Z. Predictive entropy search for efficient global optimization of black-box functions // Advances in neural information processing systems. V. 27. 2014.
  19. Nguyen A. and Balasubramanian K. Stochastic zeroth-order functional constrained optimization: Oracle complexity and applications // INFORMS Journal on Optimization. 2022.
  20. Bansal S., Calandra R., Xiao T., Levine S., and Tomlin C.J. Goal-driven dynamics learning via bayesian optimization / In 2017 IEEE 56th Annual Conference on Decision and Control (CDC). IEEE. 2017. P. 5168–5173.
  21. Xu W., Jones C.N., Svetozarevic B., Laughman C.R., and Chakrabarty A. Vabo: Violation-aware bayesian optimization for closed-loop control performance optimization with unmodeled constraints / In 2022 American Control Conference (ACC). IEEE. 2022. P. 5288–5293.
  22. Gasnikov A., Dvinskikh D., Dvurechensky P., Gorbunov E., Beznosikov A., and Lobanov A. Randomized gradient-free methods in convex optimization / arXiv preprint arXiv:2211.13566. 2022.
  23. Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM Journal on Optimization. V. 22(2). 2012. P. 341–362.
  24. Lin Q., Lu Z., and Xiao L. An accelerated proximal coordinate gradient method // Advances in Neural Information Processing Systems. V. 27. 2014.
  25. Zhang Y. and Xiao L. Stochastic primal-dual coordinate method for regularized empirical risk minimization // Journal of Machine Learning Research. V. 18(84). 2017. P. 1–42.
  26. Mangold P., Bellet A., Salmon J., and Tommasi M. High-dimensional private empirical risk minimization by greedy coordinate descent / In International Conference on Artificial Intelligence and Statistics. PMLR. 2023. P. 4894–4916.
  27. Duchi J. Lecture notes for statistics 311/electrical engineering 377 // https://stanford.edu/class/stats311/Lectures/fullnotes.pdf . Last visited on. V. 2. 2016. Р. 23.
  28. Shi B., Du S.S., Su W., and Jordan M.I. Acceleration via symplectic discretization of high-resolution differential equations // Advances in Neural Information Processing Systems. V. 32. 2019.
  29. Asi H., Feldman V., Koren T., and Talwar K. Private stochastic convex optimization: Optimal rates in l1 geometry / In International Conference on Machine Learning. PMLR. 2021. P. 393–403.
  30. Lee Y.T. and Sidford A. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems / In 2013 ieee 54th annual symposium on foundations of computer science. IEEE. 2013. P. 147–156.
  31. Allen-Zhu Z., Qu Z., Richtarik P., and Yuan Y. Even faster accelerated coordinate descent using non-uniform sampling / In International Conference on Machine Learning. PMLR. 2016. P. 1110–1119.
  32. Bergou E.H., Gorbunov E., and Richtarik P. Stochastic three points method for unconstrained smooth minimization // SIAM Journal on Optimization. V. 30(4). 2020. P. 2726–2749.
  33. Gorbunov E., Bibi A., Sener O., Bergou E.H., and Richtarik P. A stochastic derivative free optimization method with momentum / In International Conference on Learning Representations. 2019.
  34. Saadi T.E.B.E.K. et al. On the almost sure convergence of the stochastic three points algorithm / arXiv preprint arXiv:2501.13886. 2025.
  35. Lobanov A., Gasnikov A., and Krasnov A. Acceleration exists! optimization problems when oracle can only compare objective function values // In The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.
  36. Saha A., Koren T., and Mansour Y. Dueling convex optimization / In International Conference on Machine Learning. PMLR. 2021. P. 9245–9254.
  37. Nesterov Y. and Stich S.U. Efficiency of the accelerated coordinate descent method on structured optimization problems // SIAM Journal on Optimization. V. 27(1). 2017. P. 110–123.
  38. Polyak B.T. and Tsypkin Y.Z. Optimal pseudogradient adaptation algorithms // Avtomatika i Telemekhanika, (8). 1980. P. 74–84.
  39. Smirnov V., Kazistova K., Sudakov I., Leplat V., Gasnikov A., and Lobanov A. Ruppert-polyak averaging for stochastic order oracle / arXiv preprint arXiv:2411.15866. 2024.
  40. Polyak B.T. and Juditsky A.B. Acceleration of stochastic approximation by averaging // SIAM journal on control and optimization. V. 30(4). 1992. P. 838–855.
  41. Gadat S. and Panloup F. Optimal non-asymptotic analysis of the ruppert–polyak averaging stochastic algorithm // Stochastic Processes and their Applications. V. 156. 2023. P. 312–348.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025

Согласие на обработку персональных данных

 

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