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

Эффективные численные методы решения задачи 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
Еще
Статья научная
SciUp 2024 © 2024 ©