Эффективные численные методы решения задачи PageRank для дважды разреженных матриц

Автор: Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 4 (28) т.7, 2015 года.

Бесплатный доступ

В работе приводятся три метода поиска вектора PageRank (вектора Фробениуса- Перрона стохастической матрицы) для дважды разреженных матриц. Все три метода сводят поиск вектора PageRank к решению задачи выпуклой оптимизации на симплексе (или седловой задаче). Первый метод базируется на обычном градиентном спуске. Однако особенностью этого метода является выбор нормы l1 вместо привычной евклидовой нормы. Второй метод базируется на алгоритме Франка-Вульфа. Третий метод базируется на рандомизированном варианте метода зеркального спуска. Все три способа хорошо учитывают разреженность постановки задачи.

Разреженность, рандомизация, метод франка- вульфа, l1-оптимизация

Короткий адрес: https://sciup.org/142186107

IDR: 142186107

Список литературы Эффективные численные методы решения задачи PageRank для дважды разреженных матриц

Brin S., Page L. The anatomy of a large-scale hypertextual web search engine//Comput. Network ISDN Syst. 1998. V. 30(1-7). P. 107-117
Langville A.N., Meyer C.D. Google’s PageRank and beyond: The science of search engine rankings. Princeton University Press, 2006
Назин А.В., Поляк Б.Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank//Автоматика и телемеханика. 2011. № 2. C. 131-141
Nesterov Y.E. Subgradient methods for huge-scale optimization problems//CORE Discussion Paper. 2012. V. 2012/2
Nesterov Y.E. Efficiency of coordinate descent methods on large scale optimization problem//SIAM Journal on Optimization. 2012. V. 22, N 2. P. 341-362
Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank//ЖВМиМФ. 2015. Т. 55, № 3. C. 355-371
Hastie T., Tibshirani R., Friedman R. The Elements of statistical learning: Data mining, Inference and Prediction. Springer, 2009
Zhang Y., Roughan M., Duffield N., Greenberg A. Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads//In ACM Sigmetrics. 2003. San Diego, CA
Bubeck S. Convex optimization: algorithms and complexity//In Foundations and Trends in Machine Learning. 2015. V. 8, N 3-4. P. 231-357. arXiv:1405.4980
Candes E.J., Wakin M.B., Boyd S.P. Enhancing Sparsity by Reweighted l1 Minimization. J. Fourier Anal. Appl. 2008. V. 14. P. 877-905
Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent. e-print, 2014. arXiv:1407.1537
Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом. e-print, 2015. arXiv:1411.4218
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, Second Edition. The MIT Press, 2001
Frank M., Wolfe P. An algorithm for quadratic programming//Naval research logistics quarterly. 1956. V. 3, N 1-2. P. 95-110
Revisiting J.M. Frank-Wolfe: Projection-free sparse convex optimization//Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. https://sites.google.com/site/frankwolfegreedytutorial
Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization//Math. Program. Ser. B. 2015. http://www2.isye.gatech.edu/~nemirovs/ccg_revised_apr02.pdf
Nesterov Yu. Complexity bounds for primal-dual methods minimizing the model of objective function//CORE Discussion Papers. 2015/03
Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale optimization, II. In: Optimization for Machine Learning. Eds. S. Sra, S. Nowozin, S. Wright. MIT Press, 2012. http://www2.isye.gatech.edu/~nemirovs/MLOptChapterII.pdf
Grigoriadis M., Khachiyan L. A sublinear-time randomized approximation algorithm for matrix games//Oper. Res. Lett. 1995. V. 18, N 2. P. 53-58
Гасников А.В., Нестеров Ю.Е., Спокойный В.Г. Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации//ЖВМ и МФ. 2015. Т. 55, № 4. С. 55-71. arXiv:1410.3118
Nesterov Yu. Gradient methods for minimizing composite functions//Math. Prog. 2013. V. 140, N 1. P. 125-161
Shalev-Shwartz S., Zhang T. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization//Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014. P. 64-72. arXiv:1309.2375
Zheng Q., Richtarik P., Zhang T. Randomized dual coordinate ascent with arbitrary sampling. e-print, 2015. arXiv:1411.5873
Fercoq O., Richtarik P. Accelerated, Parallel and Proximal Coordinate Descent. e-print, 2013. arXiv:1312.5799
Qu Z., Richtarik P. Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity. e-print, 2014. arXiv:1412.8060
Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006
Stanford Large Network Dataset Collection, Web graphs. http://snap.stanford.edu/data/#web

Еще

Статья научная