Об ускоренных методах поиска канонического тензорного разложения
Автор: Меркулов Д.М., Тупица Н.К.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 4 (48) т.12, 2020 года.
Бесплатный доступ
Рассматриваются методы на основе ускорения Нестерова для задачи альтернированных наименьших квадратов (ALS) для поиска канонического тензорного разложения. Для получения гарантий сходимости к стационарной точке в данной невыпуклой задаче используется модификация ускоренного градиентного метода с одномерным поиском для решения задач альтернированной минимизации. Изучается механизм рестартов, позволяющий преодолеть численную нестабильность процедуры линейного поиска и добиться более быстрой работы метода. Численные эксперименты показывают, что ускоренный метод альтернированных наименьших квадратов с рестартами может быть более эффективным, если задача плохо обусловлена. Существует потенциал развития описанного подхода для ускорения других невыпуклых задач оптимизации, например, таких как разложение Таккера.
Каноническое тензорное разложение, метод альтернированных наименьших квадратов, ускорение нестерова, невыпуклая оптимизация
Короткий адрес: https://sciup.org/142230095
IDR: 142230095
Список литературы Об ускоренных методах поиска канонического тензорного разложения
- Acar Е., Dunlavy D.M., Kolda T.G. A scalable optimization approach for fitting canonical tensor decompositions .Journal of Chemometrics. 2011. 25(2). P. 67 86.
- Ang A.M.S., Gillis N. Accelerating nonnegative matrix factorization algorithms using extrapolation /7 Neural computation. 2019. 31(2). P. 417 439.
- Ghadimi S., ban G. Accelerated gradient methods for nonconvcx nonlinear and stochastic programming /7 Mathematical Programming. 2016. 156(1 2). P. 59 99.
- Goldstein T., О 'Donoghue. В., Se.tze.r S., Baraniuk R. Fast alternating direction optimization methods /7 SIAM .Journal on Imaging Sciences. 2014. 7(3). P. 1588 1623.
- Guminov S., Dvurechensky P., Tupitsa N., Gasnikov A. Accelerated Alternating Minimization, Accelerated Sinkhorn's Algorithm and Accelerated Iterative Bregman Projections // arXiv e-prints. page arXiv:1906.03622. June 2019.
- Kolda T.G., Bader B.W. Tensor decompositions and applications // SIAM review. 2009. 51(3). P. 455-500.
- Li H., Lin Zh. Accelerated proximal gradient methods for nonconvex programming // Advances in neural information processing systems. 2015. P. 379-387.
- Nesterov Yu. A method of solving a convex programming problem with convergence rate o(1/k2) 11 Soviet Mathematics Dokladv. 1983. V. 27. P. 372-376.
- Nguyen N.C., Fernandez P., Freund R.M., Peraire J. Accelerated residual methods for the iterative solution of systems of equations // SIAM Journal on Scientific Computing. 2018. 40(5). P. Л3157 Л3179.
- О 'donoghue В., Candes E. Adaptive restart for accelerated gradient schemes // Foundations of computational mathematics. 2015. 15(3). P. 715-732.
- Su W., Boyd S., Candes E.J. A differential equation for modeling nesterov's accelerated gradient method: theory and insights // Journal of Machine Learning Research. 2016. 17(153). P. 1-43.
