Primal–dual accelerated gradient methods with small-dimensional relaxation oracle

References

• Z. Allen-Zhu and L. Orecchia, Linear coupling: An ultimate unification of gradient and mirror descent, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
   Google Scholar
• N. Andrei, 40 conjugate gradient algorithms for unconstrained optimization. A survey on their definition, (2008). Available at https://camo.ici.ro/neculai/p13a08.pdf.
   Google Scholar
• A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM. J. Imaging Sci. 2 (2009), pp. 183–202. Available at https://doi.org/10.1137/080716542.
   Web of Science ®Google Scholar
• A. Beck and M. Teboulle, A fast dual proximal gradient algorithm for convex minimization and applications, Oper. Res. Lett. 42 (2014), pp. 1–6. doi: 10.1016/j.orl.2013.10.007
   Web of Science ®Google Scholar
• A. Ben-Tal and A. Nemirovski, Lectures on modern convex optimization (lecture notes), Personal web-page of A. Nemirovski, 2015. Available at http://www2.isye.gatech.edu/nemirovs/Lect_ModConvOpt.pdf.
   Google Scholar
• A. Chernov, P. Dvurechensky and A. Gasnikov, Fast primal–dual gradient method for strongly convex minimization problems with linear constraints, in Discrete Optimization and Operations Research: 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings, Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, and P. Pardalos, eds., Springer International Publishing, Cham, 2016, pp. 391–403.
   Google Scholar
• E. de Klerk, F. Glineur, and A.B. Taylor, On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions, Optim. Lett. 11 (2017), pp. 1185–1199. Available at https://doi.org/10.1007/s11590-016-1087-4.
   Web of Science ®Google Scholar
• Y. Drori and A.B. Taylor, Efficient first-order methods for convex minimization: A constructive approach, Math. Program. (2019). Available at https://doi.org/10.1007/s10107-019-01410-2.
   Google Scholar
• P. Dvurechensky, A. Gasnikov, and A. Kroshnin, Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's algorithm, in Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause, eds., Proceedings of Machine Learning Research, Vol. 80, Stockholmsmässan, Stockholm, Sweden, July 10–15, 2018, pp. 1367–1376. Available at http://proceedings.mlr.press/.
   Google Scholar
• P. Dvurechensky, A. Gasnikov, S. Omelchenko, and A. Tiurin, Adaptive similar triangles method: A stable alternative to Sinkhorn's algorithm for regularized optimal transport, (2017). Available at arXiv:1706.07622.
   Google Scholar
• S. Ghadimi and G. Lan, Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program. 156 (2016), pp. 59–99. Available at http://dx.doi.org/10.1007/s10107-015-0871-8.
   Web of Science ®Google Scholar
• S. Ghadimi, G. Lan, and H. Zhang, Generalized uniformly optimal methods for nonlinear programming, J. Sci. Comput. 79 (2019), pp. 1854–1881. Available at https://doi.org/10.1007/s10915-019-00915-4.
   Google Scholar
• S. Guminov and A. Gasnikov, Accelerated methods for α-weakly-quasi-convex problems, (2017). Available at arXiv preprint arXiv:1710.00797.
   Google Scholar
• S. Guminov, A. Gasnikov, A. Anikin, and A. Gornov, A universal modification of the linear coupling method, Optim. Methods Softw. 34 (2019), pp. 560–577. doi: 10.1080/10556788.2018.1517158
   Web of Science ®Google Scholar
• M. Haarala, K. Miettinen, and M.M. Mäkelä, New limited memory bundle method for large-scale nonsmooth optimization, Optim. Methods Softw. 19 (2004), pp. 673–692. doi: 10.1080/10556780410001689225
   Web of Science ®Google Scholar
• D. Kim and J.A. Fessler, Generalizing the optimized gradient method for smooth convex minimization, SIAM. J. Optim. 28 (2018), pp. 1920–1950. doi: 10.1137/17M112124X
   Web of Science ®Google Scholar
• G. Narkiss and M. Zibulevsky, Sequential subspace optimization method for large-scale unconstrained problems, Technion-IIT, Department of Electrical Engineering, 2005.
   Google Scholar
• A. Nemirovski, Orth-method for smooth convex optimization, Izvestia AN SSSR, Transl.: Eng. Cybern. Soviet J. Comput. Syst. Sci. 2 (1982), pp. 937–947.
   Google Scholar
• A. Nemirovski and Y. David, Information complexity of mathematical programming, Izvestia AN SSSR, Transl.: Eng. Cybern. Soviet J. Comput. Syst. Sci. 1 (1983), pp. 88–117.
   Google Scholar
• A. Nemirovsky, Information-based complexity of linear operator equations, J. Complex. 8 (1992), pp. 153–175. doi: 10.1016/0885-064X(92)90013-2
   Google Scholar
• A. Nemirovsky and D. Yudin, Problem Complexity and Method Efficiency in Optimization, J. Wiley & Sons, New York, 1983.
   Google Scholar
• Y.E. Nesterov, Effective Methods in Nonlinear Programming, Radio i Svyaz, Moscow, 1989.
   Google Scholar
• Y. Nesterov, A method of solving a convex programming problem with convergence rate o(1/k2), Soviet Math. Doklady 27 (1983), pp. 372–376.
   Google Scholar
• Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Massachusetts, 2004.
   Google Scholar
• Y. Nesterov, Introductory lectures on convex optimization, Appl. Optim. 87 (2004), pp. 58–62.
   Google Scholar
• Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. 103 (2005), pp. 127–152. doi: 10.1007/s10107-004-0552-5
   Web of Science ®Google Scholar
• Y. Nesterov, How to make the gradients small, Optima 88 (2012), pp. 10–11.
   Google Scholar
• Y. Nesterov, Gradient methods for minimizing composite functions, Math. Program. 140 (2013), pp. 125–161. First appeared in 2007 as CORE discussion paper 2007/76. doi: 10.1007/s10107-012-0629-5
   Web of Science ®Google Scholar
• Y. Nesterov, Universal gradient methods for convex optimization problems, Math. Program. 152 (2015), pp. 381–404. Available at http://dx.doi.org/10.1007/s10107-014-0790-0.
   Web of Science ®Google Scholar
• J. Nocedal and S.J. Wright, Numerical Optimization, 2nd ed., Springer, New York, NY, 2006.
   Google Scholar
• A. Yurtsever, Q. Tran-Dinh, and V. Cevher, A universal primal–dual convex optimization framework, in Proceedings of the 28th International Conference on Neural Information Processing Systems, MIT Press, Cambridge, MA, USA, NIPS'15, 2015, pp. 3150–3158.
   Google Scholar