The global rate of convergence for optimal tensor methods in smooth convex optimization

 pdf (180K)  / Annotation

List of references:

  1. А. С. Баяндина, А. В. Гасников, Ф. Ш. Гулиев, А. А. Лагуновская. Безградиентные двухточечные методы решения задач стохастической негладкой выпуклой оптимизации при наличии малых шумов не случайной природы // Автоматика и Телемеханика. — 2018. — № 9. — (в печати). — https://arxiv.org/ftp/arxiv/papers/1701/1701.03821.pdf . — (дата обращения: 03.09.2018).
    • A. S. Bayandina, A. V. Gasnikov, F. S. Guliev, A. A. Lagunovskaya. Gradientfree two-points optimal method for non smooth stochastic convex optimization problem with additional small noise // Automation and Remote Control. — 2018. — no. 9. — (in print). — https://arxiv.org/ftp/arxiv/papers/1701/1701.03821.pdf. — (accessed: 03.09.2018). — in Russian.
  2. Ф. П. Васильев. Методы оптимизации. — М: МЦНМО, 2011. — Т. 2. — 433 с.
    • F. P. Vasiliev. Methods of Optimization. — Moscow: MTSNMO, 2011. — V. 2. — 433 p. — in Russian.
  3. Е. А. Воронцова, А. В. Гасников, Э. А. Горбунов. Ускоренные спуски по случайному направлению с неевклидовой прокс-структурой // Автоматика и Телемеханика. — 2019. — (в печати). — https://arxiv.org/pdf/1710.00162.pdf. — (дата обращения: 03.09.2018).
    • E. A. Vorontsova, A. V. Gasnikov, E. A. Gorbunov. Accelerated Directional Search with non-Euclidean prox-structure // Automation and Remote Control. — 2019. — (in print). — https://arxiv.org/pdf/1710.00162.pdf. — (accessed: 03.09.2018). — in Russian.
  4. А. В. Гасников. Современные численные методы оптимизации. Метод универсального градиентного спуска. — М: МФТИ, 2018. — 166 с.
    • A. V. Gasnikov. Universal gradient descent. — Moscow: MIPT, 2018. — 166 p. — in Russian.
  5. А. В. Гасников, Д. А. Ковалев. Гипотеза об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков // Компьютерные исследования и моделирование. — 2018. — Т. 10, № 3. — С. 305–314. — DOI: 10.20537/2076-7633-2018-10-3-305-314
    • A. V. Gasnikov, D. A. Kovalev. Hypothesis of optimal estimates of the rate of convergence of numerical methods of convex optimization of high orders // Computer Research and Modeling. — 2018. — V. 10, no. 3. — P. 305–314. — in Russian. — DOI: 10.20537/2076-7633-2018-10-3-305-314.
  6. А. О. Гельфонд. Исчисление конечных разностей. — М: ГИФМЛ, 1959. — 400 с.
    • A. O. Gelfond. Calculus of finite differences. — Moscow: GIFML, 1959. — 400 p. — in Russian. — MathSciNet: MR0342890.
  7. Ю. Г. Евтушенко. Оптимизация и быстрое автоматическое дифференцирование. — М: ВЦ РАН, 2013. — 144 с. — http://www.ccas.ru/personal/evtush/p/198.pdf. — (дата обращения: 03.09.2018).
  8. Дж. Денис, Р. Шнабель. Численные методы безусловной оптимизации и решения нелинейных уравнений. — М: Мир, 1988. — 440 с.
    • J. Dennis, R. Schnabel. Numerical methods for unconditional optimization and nonlinear equations. — Moscow: Mir, 1988. — 440 p. — in Russian. — MathSciNet: MR0956645.
  9. А. Ф. Измаилов, М. В. Солодов. Численные методы оптимизации. — М: Физматлит, 2005. — 304 с.
    • A. P. Izmailov, M. V. Solodov. Numerical Optimization Methods. — Moscow: Fizmatlit, 2005. — 304 p. — in Russian. — MathSciNet: MR2071073.
  10. В. Г. Карманов. Математическое программирование. — М: Наука, 1986. — 288 с.
    • V. G. Karmanov. Mathematical programming. — Moscow: Nauka, 1986. — 288 p. — in Russian. — MathSciNet: MR0411559.
  11. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ:. — пер. с англ. — М: Издательский дом Вильямс, 2009.
    • T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to algorithms. — Moscow: Izdatelskii dom Vilyams, 2009. — in Russian. — MathSciNet: MR2572804.
  12. А. С. Немировский, Д. Б. Юдин. Сложность задач и эффективность методов оптимизации. — М: Наука, 1979.
    • A. S. Nemirovski, D. B. Yudin. Problem Complexity and method Efficiency in Optimization. — Moscow: Nauka, 1979. — in Russian. — MathSciNet: MR0702836.
  13. Ю. Е. Нестеров. Введение в выпуклую оптимизацию. — М: МЦНМО, 2010. — 262 с.
    • Yu. E. Nesterov. Introduction to convex optimization. — Moscow: MTSNMO, 2010. — 262 p. — in Russian.
  14. В. Ю. Протасов. К вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям // Мат. заметки. — 1996. — Т. 59, № 1. — С. 95–102.
    • V. Yu. Protasov. On the question of algorithms for the approximate calculation of a minimum of a convex function from its values // Math. notes. — 1996. — V. 59, no. 1. — P. 95–102. — in Russian. — DOI: 10.1007/BF02312467. — Math-Net: Mi eng/mzm1697. — MathSciNet: MR1391825.
  15. Y. Arjevani, O. Shamir, R. Shiff. Oracle complexity of second-order methods for smooth convex optimization // Mathematical Programming. — 2017. — P. 1–34.
  16. M. Baes. Estimate sequence methods: extensions and approximations. — 2009. — http://www.optimization-online.org/DB_FILE/2009/08/2372.pdf. — (accessed: 03.09.2018).
  17. S. Bubeck. Convex optimization: algorithms and complexity // Foundations and Trends in Machine Learning. — 2015. — V. 8, no. 3–4. — P. 231–357. — DOI: 10.1561/2200000050.
  18. A. B. Conn, N. I. M. Gould, P. L. Toint. Trust region methods. — Philadelphia: SIAM, 2000. — MathSciNet: MR1774899.
  19. P. Dvurechensky, A. Gasnikov, A. Tiurin. Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method). — 2017. — https://arxiv.org/pdf/1707.08486.pdf. — (accessed: 03.09.2018).
  20. S. Ghadimi, H. Liu, T. Zhang. Second-order methods with cubic regularization under inexact information. — 2017. — https://arxiv.org/pdf/1710.05782.pdf. — (accessed: 03.09.2018).
  21. G. N. Grapiglia, Yu. Nesterov. Regularized Newton methods for minimizing functions with H ¨older continuous Hessian // SIAM J. Optim. — 2017. — V. 27, no. 1. — P. 478–506. — DOI: 10.1137/16M1087801. — MathSciNet: MR3625807.
  22. F. Hanzely, P. Richtarik, L. Xiao. Accelerated Bregman proximal gradient method for relatively smooth functions. — 2018. — https://arxiv.org/pdf/1808.03045.pdf. — (accessed: 03.09.2018).
  23. Y.-T. Lee, A. Sidford, S. C.-W. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. — 2015. — https://arxiv.org/pdf/1508.04874.pdf . — (accessed: 03.09.2018). — MathSciNet: MR3473356.
  24. H. Lin, J. Mairal, Z. Harchaoui. Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice // Journal of Machine Learning Research. — 2018. — V. 18. — P. 1–54. — 212. — MathSciNet: MR3827100. — ads: 2018JSR...135....1L.
  25. R. Monteiro, B. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods // SIAM Journal on Optimization. — 2013. — V. 23, no. 2. — P. 1092–1125. — DOI: 10.1137/110833786. — MathSciNet: MR3063151.
  26. A. Nemirovski. Lectures on modern convex optimization analysis, algorithms, and engineering applications. — Philadelphia: SIAM, 2015. — http://www2.isye.gatech.edu/�..nemirovs/Lect_ModConvOpt.pdf. — (accessed: 03.09.2018).
  27. Yu. Nesterov. Accelerating the cubic regularization of Newton’s method on convex problems // Math. Prog., Ser. A. — 2008. — V. 112. — P. 159–181. — DOI: 10.1007/s10107-006-0089-x. — MathSciNet: MR2327005.
  28. Yu. Nesterov. Implementable tensor methods in unconstrained convex optimization. — Universit´e catholique de Louvain, Center for Operations Research and Econometrics (CORE), 2018. — CORE discussion paper 2018/05.
  29. Yu. Nesterov. Lectures on convex optimization. — Springer, 2018. — MathSciNet: MR2142598.
  30. Yu. Nesterov. Minimizing functions with bounded variation of subgradients. — 2005. — 13 p. — CORE Discussion Papers 2005/79. — http://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2005_79.pdf. — (accessed : 03.09.2018).
  31. Yu. Nesterov, B. Polyak. Cubic regularization of Newton method and its global performance // Mathematical Programming. — 2006. — V. 108, no. 1. — P. 177–205. — DOI: 10.1007/s10107-006-0706-8. — MathSciNet: MR2229459.
  32. Yu. Nesterov, V. Spokoiny. Random gradient-free minimization of convex functions // Foundations of Computational Mathematics. — 2017. — V. 17, no. 2. — P. 527–566. — DOI: 10.1007/s10208-015-9296-2. — MathSciNet: MR3627456.
  33. J. Nocedal, S. Wright. Numerical optimization. — Springer, 2006.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"