Inexact tensor methods and their application to stochastic convex optimization

References

• A. Agafonov, D. Kamzolov, P. Dvurechensky, and A. Gasnikov, Inexact tensor methods and their application to stochastic convex optimization, preprint 2020. arXiv:2012.15636.
   Google Scholar
• N. Agarwal and E. Hazan, Lower bounds for higher-order convex optimization, preprint 2017. arXiv:1710.10329.
   Google Scholar
• Y. Arjevani, O. Shamir, and R. Shiff, Oracle complexity of second-order methods for smooth convex optimization, Math. Program. 178(1-2) (2019), pp. 327–360.
   Web of Science ®Google Scholar
• M. Baes, Estimate sequence methods: extensions and approximations. Institute for Operations Research, ETH, Zürich, Switzerland, 2009.
   Google Scholar
• S. Bellavia and G. Gurioli, Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic hessian accuracy, Optimization 71(1) (2022), pp. 227–261.
   Web of Science ®Google Scholar
• S. Bellavia, G. Gurioli, and B. Morini, Adaptive cubic regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization, IMA J. Numerical Anal. 41(1) (2020), pp. 764–799.
   Web of Science ®Google Scholar
• S. Bellavia, G. Gurioli, B. Morini, and P.L. Toint, Adaptive regularization algorithms with inexact evaluations for nonconvex optimization, SIAM. J. Optim. 29(4) (2019), pp. 2881–2915.
   Web of Science ®Google Scholar
• S. Bellavia, G. Gurioli, B. Morini, and P.L. Toint, Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives, J. Complex. 68 (2022), p. 101591.
   Web of Science ®Google Scholar
• S. Bubeck, Q. Jiang, Y.T. Lee, Y. Li, and A. Sidford, Near-optimal method for highly smooth convex optimization, in Conference on Learning Theory, Phoenix, USA, PMLR, 2019, pp. 492–507.
   Google Scholar
• C. Cartis, N.I. Gould, and P.L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program. 127(2) (2011), pp. 245–295.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and P.L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity, Math. Program. 130(2) (2011), pp. 295–319.
   Web of Science ®Google Scholar
• C. Cartis, N.I. Gould, and P.L. Toint, Universal regularization methods: varying the power, the smoothness and the accuracy, SIAM. J. Optim. 29(1) (2019), pp. 595–615.
   Web of Science ®Google Scholar
• C. Cartis, N.I. Gould, and P.L. Toint, Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, preprint 2017. arXiv:1708.04044.
   Google Scholar
• C. Cartis and K. Scheinberg, Global convergence rate analysis of unconstrained optimization methods based on probabilistic models, Math. Program. 169 (2018), pp. 337–375.
   Web of Science ®Google Scholar
• P.L. Chebyshev, Collected Works [in Russian], Vol. 5, Izd. Akad. NaukSSSR, Moscow-Leningrad, 1951.
   Google Scholar
• M. Cohen, J. Diakonikolas, and L. Orecchia, On acceleration with noise-corrupted gradients, in Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, J. Dy and A. Krause, eds., PMLR, Stockholmsmässan, Stockholm, 2018, pp. 1019–1028.
   Google Scholar
• A. Conn, N. Gould, and P. Toint, Trust Region Methods, Society for Industrial and Applied Mathematics, 2000. https://doi.org/10.1137/1.9780898719857.
   Google Scholar
• A. d'Aspremont, Smooth optimization with approximate gradient, SIAM. J. Optim. 19(3) (2008), pp. 1171–1183.
   Web of Science ®Google Scholar
• O. Devolder, Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, Ph.D. diss., ICTEAM and CORE, Université Catholique de Louvain, 2013.
   Google Scholar
• N. Doikov and Y. Nesterov, Convex optimization based on global lower second-order models, in Advances in Neural Information Processing Systems 33 proceedings (NeurIPS 2020), Curran Associates, Inc., 2020.
   Google Scholar
• D. Dvinskikh and A. Gasnikov, Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems, J. Inverse Ill Posed Problems 29(3) (2021), pp. 385–405.
   Web of Science ®Google Scholar
• P. Dvurechensky and A. Gasnikov, Stochastic intermediate gradient method for convex problems with stochastic inexact oracle, J. Optim. Theory. Appl. 171(1) (2016), pp. 121–145.
   Web of Science ®Google Scholar
• Y.G. Evtushenko, Optimization and Fast Automatic Differentiation, Computing Center of RAS, Moscow, 2013.
   Google Scholar
• A. Gasnikov, D. Dvinskikh, P. Dvurechensky, D. Kamzolov, D. Pasechnyk, V. Matykhin, N. Tupitsa, and A. Chernov, Accelerated meta-algorithm for convex optimization, Comput. Math. Math. Phys. 61(1) (2020), pp. 17–28.
   Web of Science ®Google Scholar
• A.V. Gasnikov and P.E. Dvurechensky, Stochastic intermediate gradient method for convex optimization problems, Doklady Math. 93(2) (2016), pp. 148–151.
   Web of Science ®Google Scholar
• A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C.A. Uribe, B. Jiang, H. Wang, S. Zhang, S. Bubeck, Q. Jiang, Y.T. Lee, Y. Li, and A. Sidford, Near optimal methods for minimizing convex functions with lipschitz pth derivatives, in Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, A. Beygelzimer and D. Hsu, eds., PMLR, Phoenix, 2019, pp. 1392–1393.
   Google Scholar
• A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, and C.A. Uribe, Optimal tensor methods in smooth convex and uniformly convex optimization, in Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, A. Beygelzimer and D. Hsu, eds., PMLR, Phoenix, 2019, pp. 1374–1391.
   Google Scholar
• A. Gasnikov, E. Gorbunov, D. Kovalev, A. Mohammed, and E. Chernousova, The global rate of convergence for optimal tensor methods in smooth convex optimization, Computer Res. Modell. 10(6) (2018), pp. 737–753.
   Google Scholar
• A. Gasnikov, E. Gorbunov, D. Kovalev, A. Mokhammed, and E. Chernousova, Reachability of optimal convergence rate estimates for high-order numerical convex optimization methods, in Doklady Mathematics, Vol. 99, Moscow, Russia, Springer, 2019, pp. 91–94.
   Google Scholar
• A. Gasnikov, Universal gradient descent, Modern numerical optimization methods. MCCME, 2020.
   Google Scholar
• S. Ghadimi, H. Liu, and T. Zhang, Second-order methods with cubic regularization under inexact information, 2017. arXiv:1710.05782.
   Google Scholar
• F. Hanzely, N. Doikov, Y. Nesterov, and P. Richtarik, Stochastic subspace cubic newton method, in International Conference on Machine Learning, PMLR, 2020, pp. 4027–4038.
   Google Scholar
• K.H. Hoffmann and H.J. Kornstaedt, Higher-order necessary conditions in abstract mathematical programming, J. Optim. Theory. Appl. 26(4) (1978), pp. 533–568.
   Web of Science ®Google Scholar
• B. Jiang, H. Wang, and S. Zhang, An optimal high-order tensor method for convex optimization, in Conference on Learning Theory, Phoenix, USA, PMLR, 2019, pp. 1799–1801.
   Google Scholar
• D. Kamzolov and A. Gasnikov, Near-optimal hyperfast second-order method for convex optimization and its sliding, preprint 2020. arXiv:2002.09050.
   Google Scholar
• J.M. Kohler and A. Lucchi, Sub-sampled cubic regularization for non-convex optimization, in International Conference on Machine Learning, Sydney, Australia, PMLR, 2017, pp. 1895–1904.
   Google Scholar
• D. Kovalev, K. Mishchenko, and P. Richtárik, Stochastic newton and cubic newton methods with simple local linear-quadratic rates, preprint 2019. arXiv:1912.01597.
   Google Scholar
• H. Lu, R.M. Freund, and Y. Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM. J. Optim. 28(1) (2018), pp. 333–354.
   Web of Science ®Google Scholar
• A. Lucchi and J. Kohler, A sub-sampled tensor method for nonconvex optimization, IMA J. Numerical Anal. 43(5) (2023), pp. 2856–2891.
   Web of Science ®Google Scholar
• Z. Luo, L. Qi, and P.L. Toint, Tensor bernstein concentration inequalities with an application to sample estimators for high-order moments, Front. Math. China 15 (2020), pp. 367–384.
   Web of Science ®Google Scholar
• R.D. Monteiro and B.F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM. J. Optim. 23(2) (2013), pp. 1092–1125.
   Web of Science ®Google Scholar
• Y. Nesterov, Accelerating the cubic regularization of newton's method on convex problems, Math. Program. 112(1) (2008), pp. 159–181.
   Web of Science ®Google Scholar
• Y. Nesterov, Lectures on Convex Optimization, Vol. 137. Springer, 2018. https://doi.org/10.1007/978-3-319-91578-4.
   Google Scholar
• Y. Nesterov, Implementable tensor methods in unconstrained convex optimization, Math. Program. 186 (2019), pp. 157–183.
   PubMed Web of Science ®Google Scholar
• Y. Nesterov, Inexact high-order proximal-point methods with auxiliary search procedure, SIAM J. Optim. 31 (2021), pp. 2807–2828.
   Web of Science ®Google Scholar
• Y. Nesterov, Superfast second-order methods for unconstrained convex optimization, J. Optim. Theory. Appl. 191 (2021), pp. 1–30.
   Web of Science ®Google Scholar
• Y. Nesterov and B. Polyak, Cubic regularization of newton method and its global performance, Math. Program. 108(1) (2006), pp. 177–205.
   Web of Science ®Google Scholar
• S. Park, S.H. Jung, and P.M. Pardalos, Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization, J. Optim. Theory. Appl. 184(3) (2020), pp. 953–971.
   Web of Science ®Google Scholar
• B.T. Polyak, Introduction to Optimization. Optimization Software, Vol. 1, Publications Division Inc., New York, 1987.
   Google Scholar
• A. Rodomanov and D. Kropotov, A superlinearly-convergent proximal newton-type method for the optimization of finite sums, in International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, M. F. Balcan and K. Q. Weinberger, eds., PMLR, New York, NY, 2016, pp. 2597–2605.
   Google Scholar
• F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, M. Alkousa, D. Pasechnyuk, S. Artamonov, and V. Piskunova, Inexact model: a framework for optimization and variational inequalities. Optimization Methods and Software 36(6) (2021), pp. 1155–1201. 10.1080/10556788.2021.1924714.
   Web of Science ®Google Scholar
• L.N. Trefethen, Approximation Theory and Approximation Practice, Vol. 164, SIAM, 2019. https://doi.org/10.1137/1.9781611975949.
   Google Scholar
• N. Tripuraneni, M. Stern, C. Jin, J. Regier, and M.I. Jordan, Stochastic cubic regularization for fast nonconvex optimization, in Advances in Neural Information Processing Systems, Vol. 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., Montreal, Canada., Curran Associates, Inc., 2018, pp. 2899–2908.
   Google Scholar
• Z. Wang, Y. Zhou, Y. Liang, and G. Lan, A note on inexact condition for cubic regularized newton's method, preprint 2018. arXiv:1808.07384v1.
   Google Scholar
• Z. Wang, Y. Zhou, Y. Liang, and G. Lan, Cubic regularization with momentum for nonconvex optimization, in Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, R. P. Adams and V. Gogate, eds., PMLR, Tel Aviv, 2020, pp. 313–322.
   Google Scholar
• P. Xu, F. Roosta, and M.W. Mahoney, Newton-type methods for non-convex optimization under inexact hessian information, Math. Program. 184(1-2) (2020), pp. 35–70.
   Web of Science ®Google Scholar
• Y. Zhang and L. Xiao, Disco: distributed optimization for self-concordant empirical loss, in International Conference on Machine Learning, PMLR, Lille, France, 2015, pp. 362–370.
   Google Scholar
• D. Zhou, P. Xu, and Q. Gu, Stochastic variance-reduced cubic regularized Newton methods, in Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, J. Dy and A. Krause, eds., PMLR, Stockholmsmässan, Stockholm, 2018, pp. 5990–5999.
   Google Scholar