Inexact tensor methods and their application to stochastic convex optimization

Abstract

We propose general non-accelerated [The results for non-accelerated methods first appeared in December 2020 in the preprint (A. Agafonov, D. Kamzolov, P. Dvurechensky, and A. Gasnikov, Inexact tensor methods and their application to stochastic convex optimization, preprint 2020. arXiv:2012.15636)] and accelerated tensor methods under inexact information on the derivatives of the objective, analyse their convergence rate. Further, we provide conditions for the inexactness in each derivative that is sufficient for each algorithm to achieve a desired accuracy. As a corollary, we propose stochastic tensor methods for convex optimization and obtain sufficient mini-batch sizes for each derivative.

Keywords:

• High-order methods
• tensor methods
• inexact derivatives
• convex optimization
• stochastic optimization

Acknowledgements

The work of A. Agafonov, and D. Kamzolov was supported by a grant for research centres in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321P5Q0002) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138.

The authors are very grateful to Yu.E. Nesterov, A.I. Golikov, Yu.G. Evtushenko and G. Scutari for fruitful discussions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Artem Agafonov

Artem Agafonov got B.Sc. and M.Sc. degrees from the Department of Control and Applied Mathematics of Moscow Institute of Physics and Technology (MIPT) in 2020 and 2022, respectively. Since 2022 he has been pursuing a Ph.D. in MBZUAI.

Dmitry Kamzolov

Dmitry Kamzolov is a Research Associate at the Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, UAE. Dmitry earned his B.Sc. and M.Sc. degrees from the Department of Control and Applied Mathematics at the Moscow Institute of Physics and Technology (MIPT) in 2016 and 2018, respectively. He also obtained the M.Sc. in Operations Research, Combinatorics and Optimization (ORCO) at the University of Grenoble Alpes (UGA). In 2020, he obtained his Ph.D. in Mathematical Modelling, Numerical Methods and Program Complexes from MIPT. Since 2021, he has been working as a Research Associate in the group led by Martin Takáč at MBZUAI, UAE. His current research interests focus on second-order and high-order optimization methods for both convex and non-convex problems, with application in machine learning and distributed computations.

Pavel Dvurechensky

Pavel Dvurechensky got B.Sc and M.Sc degrees from the Department of Control and Applied Mathematics of Moscow Institute of Physics and Technology in 2008 and 2010 respectively. He obtained a PhD from the same university in 2014. Since 2015 he has been a research associate at Weierstrass Institute for Applied Analysis and Stochastics in Berlin.

Alexander Gasnikov

Alexander Gasnikov obtained B.Sc and M.Sc degrees from the Department of Control and Applied Mathematics at the Moscow Institute of Physics and Technology in 2004 and 2006, respectively. He earned a PhD from the same university in 2007 and a Doctor's degree (Habilitation) in 2016, under the supervision of A. Shananin and Yu. Nesterov. Since 2020, he has held the position of professor at the Moscow Institute of Physics and Technology and the Higher School of Economics. Since 2021, he has led a scientific group at the Ivannikov Institute for System Programming RAS. Starting in 2022, he has been the head of the Laboratory of Mathematical Methods of Optimization and the head of the Department of Mathematical Foundations of Control. As of 2023, he has been appointed as the head of the Laboratory of Mathematical Foundations of Machine Learning at the Institute of Information Transmission Problems RAS and as the head of the Laboratory for Multi-scale Neurodynamics for Smart Systems at Skoltech. He has received awards from Yahoo, Yandex, the Moscow government, and Huawei. He is the author of more than 200 papers, including publications in Q1 journals (JOTA, SIAM, EJOR, OMS, etc.) and A* conferences (NeurIPS, ICML, COLT).

Martin Takáč

Martin Takáč is an Associate Professor and Deputy Department Chair of Machine Learning Department at the Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), UAE. Before joining MBZUAI, he was an Associate Professor in the Department of Industrial and Systems Engineering at Lehigh University, where he has been employed since 2014. He received his B.S. (2008) and M.S. (2010) degrees in Mathematics from Comenius University, Slovakia, and Ph.D. (2014) degree in Mathematics from the University of Edinburgh, United Kingdom. His current research interests include designing and analyzing algorithms for machine learning, AI for science, understanding protein-DNA interactions, and using ML for energy.