SURVEY OF MODERN SMOOTH OPTIMIZATION ALGORITHMS WITH COMPARISON ORACLE

Cover Page

Cite item

Full Text

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

Abstract

Modern optimization methods often encounter limited access to the values of the objective function, leading to the development of works dedicated to comparative oracles. This review provides an overview of contemporary algorithms for smooth, multivariate optimization that utilize only information about the order of the function values, rather than their numerical magnitudes. Both non-accelerated and accelerated methods are considered, including the latest advancements in optimization with comparative oracles. Special attention is paid to the diversity of approaches for designing algorithms that achieve convergence rates comparable to first-order methods (coordinate algorithms), as well as the first accelerated method within this oracle framework. Additionally, stochastic generalizations of the comparative oracle and their theoretical guarantees are discussed.

About the authors

A. V Lobanov

National Research University Higher School of Economics; Moscow Institute of Physics and Technology

Email: lobbsasha@mail.ru
Moscow, Russia

A. V Gasnikov

Innopolis University; Moscow Institute of Physics and Technology

Email: gasnikov@yandex.ru
Corresponding Member of the RAS Innopolis, Russia; Moscow, Russia

References

  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.

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