Efficient numerical methods to solve sparse linear equations with application to PageRank. (English) Zbl 1502.90122
Summary: Over the last two decades, the PageRank problem has received increased interest from the academic community as an efficient tool to estimate web-page importance in information retrieval. Despite numerous developments, the design of efficient optimization algorithms for the PageRank problem is still a challenge. This paper proposes three new algorithms with a linear time complexity for solving the problem over a bounded-degree graph. The idea behind them is to set up the PageRank as a convex minimization problem over a unit simplex, and then solve it using iterative methods with small iteration complexity. Our theoretical results are supported by an extensive empirical justification using real-world and simulated data.
MSC:
| 90C25 | Convex programming |
| 90C47 | Minimax problems in mathematical programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Allen-Zhu, Z. and Orecchia, L., Linear coupling: An ultimate unification of gradient and mirror descent, in Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 2017, pp. 3:1-3:22. · Zbl 1402.90209 |
| [2] | Avrachenkov, K.; Litvak, N.; Nemirovsky, D.; Osipova, N., Monte carlo methods in pagerank computation: When one iteration is sufficient, SIAM. J. Numer. Anal., 45, 890-904 (2007) · Zbl 1146.60056 |
| [3] | Banerjee, A.; Merugu, S.; Dhillon, I. S.; Ghosh, J., Clustering with Bregman divergences, J. Mach. Learn. Res., 6, 1705-1749 (2005) · Zbl 1190.62117 |
| [4] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1058.90049 |
| [5] | Brin, S.; Page, L., Reprint of: The anatomy of a large-scale hypertextual web search engine, Comput. Netw., 56, 3825-3833 (2012) |
| [6] | Bubeck, S., Convex optimization: Algorithms and complexity, Found. Trends Mach. Learn., 8, 231-357 (2015) · Zbl 1365.90196 |
| [7] | Candes, E. J.; Wakin, M. B.; Boyd, S. P., Enhancing sparsity by reweighted \(####\) minimization, J. Fourier Anal. Appl., 14, 877-905 (2008) · Zbl 1176.94014 |
| [8] | Cesa-Bianchi, N.; Lugosi, G., Prediction, Learning, and Games (2006), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1114.91001 |
| [9] | Cohen, M.B., Kelner, J., Peebles, J., Peng, R., Rao, A.B., Sidford, A., and Vladu, A., Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 410-419. · Zbl 1370.60115 |
| [10] | Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C., Introduction to Algorithms, 3rd ed., MIT Press, Massachusetts, 2009. · Zbl 1187.68679 |
| [11] | Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logistics (NRL), 3, 95-110 (1956) |
| [12] | Friedman, J., Hastie, T., and Tibshirani, R., The Elements of Statistical Learning, Vol. 1, Springer Series in Statistics. New York, 2001. · Zbl 0973.62007 |
| [13] | Gasnikov, A.; Dmitriev, D., On efficient randomized algorithms for finding the pagerank vector, Comput. Math. Math. Phys., 55, 349 (2015) · Zbl 1332.68280 |
| [14] | Gasnikov, A.; Nesterov, Y.; Spokoiny, V., On the efficiency of a randomized mirror descent algorithm in online optimization problems, Comput. Math. Phys., 55, 580-596 (2015) · Zbl 1350.90027 |
| [15] | Gasnikov, A. V.; Nesterov, Y. E., Universal method for stochastic composite optimization problems, Comput. Math. Phys., 58, 48-64 (2018) · Zbl 1457.90099 |
| [16] | Grigoriadis, M. D.; Khachiyan, L. G., A sublinear-time randomized approximation algorithm for matrix games, Oper. Res. Lett., 18, 53-58 (1995) · Zbl 0857.90144 |
| [17] | Harchaoui, Z.; Juditsky, A.; Nemirovski, A., Conditional gradient algorithms for norm-regularized smooth convex optimization, Math. Program., 152, 75-112 (2015) · Zbl 1336.90069 |
| [18] | Jaggi, M., Revisiting Frank-Wolfe: Projection-free sparse convex optimization, in Proceedings of the 30th International Conference on International Conference on Machine Learning (ICML), 2013, MIT Press, Massachusetts, pp. 427-435. |
| [19] | Juditsky, A.; Nemirovski, A., First order methods for nonsmooth convex large-scale optimization, I: General purpose methods, Optim. Mach. Learn., 121-148 (2011) |
| [20] | Kamvar, S.; Haveliwala, T.; Golub, G., Adaptive methods for the computation of pagerank, Linear. Algebra. Appl., 386, 51-65 (2004) · Zbl 1091.68044 |
| [21] | Kamvar, S.D., Haveliwala, T.H., Manning, C.D., and Golub, G.H., Extrapolation methods for accelerating PageRank computations, in Proceedings of the 12th international conference on World Wide Web, 2003, pp. 261-270. |
| [22] | Langville, A. N.; Meyer, C. D., Google’s PageRank and Beyond: The Science of Search Engine Rankings (2011), Princeton University Press: Princeton University Press, Princeton · Zbl 1104.68042 |
| [23] | Levin, D. A.; Peres, Y., Markov Chains and Mixing Times, Vol. 107 (2017), American Mathematical Soc.: American Mathematical Soc., Providence · Zbl 1390.60001 |
| [24] | Logan, D. L., A First Course in the Finite Element Method (2011), Cengage Learning: Cengage Learning, Stamford |
| [25] | Myerson, R. B., Game Theory (2013), Harvard University Press: Harvard University Press, Cambridge |
| [26] | Nazin, A. V.; Polyak, B. T., Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the pagerank problem, Automat. Remote Control, 72, 342-352 (2011) · Zbl 1233.65032 |
| [27] | Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19, 1574-1609 (2009) · Zbl 1189.90109 |
| [28] | Nesterov, Y., Primal-dual subgradient methods for convex problems, Math. Program., 120, 221-259 (2009) · Zbl 1191.90038 |
| [29] | Nesterov, Y., Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22, 341-362 (2012) · Zbl 1257.90073 |
| [30] | Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course, Vol. 87 (2013), Springer: Springer, New York |
| [31] | Nesterov, Y., Subgradient methods for huge-scale optimization problems, Math. Program., 146, 275-297 (2014) · Zbl 1297.90120 |
| [32] | Nesterov, Y., Complexity bounds for primal-dual methods minimizing the model of objective function, Math. Program, 171, 311-330 (2018) · Zbl 1397.90351 |
| [33] | Nesterov, Y., Lectures on Convex Optimization, Vol. 137 (2018), Springer: Springer, Cham · Zbl 1427.90003 |
| [34] | Nesterov, Y.; Nemirovski, A., Finding the stationary states of markov chains by iterative methods, Appl. Math. Comput., 255, 58-65 (2015) · Zbl 1338.65019 |
| [35] | Nutini, J., Schmidt, M., Laradji, I., Friedlander, M., and Koepke, H., Coordinate descent converges faster with the Gauss-Southwell rule than random selection, in International Conference on Machine Learning (ICML), 2015, pp. 1632-1641. |
| [36] | Page, L., Brin, S., Motwani, R., and Winograd, T., The PageRank citation ranking: Bringing order to the web, Tech. Rep., Stanford InfoLab, 1999. |
| [37] | Polyak, B. T.; Tremba, A. A., Regularization-based solution of the pagerank problem for large matrices, Automat. Remote Control, 73, 1877-1894 (2012) · Zbl 1268.93014 |
| [38] | Sarma, A. D.; Molla, A. R.; Pandurangan, G.; Upfal, E., Fast distributed pagerank computation, Theor. Comput. Sci., 561, 113-121 (2015) · Zbl 1303.68148 |
| [39] | Stott, B.; Jardim, J.; Alsaç, O., Dc power flow revisited, IEEE Trans. Power Syst., 24, 1290-1300 (2009) |
| [40] | Tong, H., Faloutsos, C., and Pan, J.Y., Fast random walk with restart and its applications, in Sixth International Conference on Data Mining (ICDM’06), IEEE, 2006, pp. 613-622. |
| [41] | Zhang, Y., Roughan, M., Duffield, N., and Greenberg, A., Fast accurate computation of large-scale IP traffic matrices from link loads, in ACM SIGMETRICS Performance Evaluation Review, ACM, 2003, pp. 206-217. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
