On efficient randomized algorithms for finding the PageRank vector

DOI10.1134/S0965542515030069zbMath1332.68280MaRDI QIDQ2354453

D. Yu. Dmitriev, Alexander V. Gasnikov

Publication date: 13 July 2015

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

stochastic optimizationrandomizationMarkov chain Monte CarloPageRankmirror descent method

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Minimax problems in mathematical programming (90C47) Stochastic programming (90C15) Randomized algorithms (68W20) Internet topics (68M11)

Related Items

Efficient numerical methods to solve sparse linear equations with application to PageRank ⋮ Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints ⋮ On the efficiency of a randomized mirror descent algorithm in online optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual subgradient methods for convex problems
• Smooth minimization of non-smooth functions
• Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Markov chains and stochastic stability
• Parametric estimation. Finite sample theory
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Computational methods of linear algebra
• Chernoff-type bound for finite Markov chains
• Laplacians and the Cheeger inequality for directed graphs
• Forest matrices around the Laplacian matrix
• On the efficiency of a randomized mirror descent algorithm in online optimization problems
• Regularization-based solution of the PageRank problem for large matrices
• Recursive aggregation of estimators by the mirror descent algorithm with averaging
• On entropy-type functionals arising in stochastic chemical kinetics related to the concentration of the invariant measure and playing the role of Lyapunov functions in the dynamics of quasiaverages
• Concentration Inequalities
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Using PageRank to Characterize Web Structure
• Mathematical Aspects of Mixing Times in Markov Chains
• The Markov chain Monte Carlo revolution
• Robust Stochastic Approximation Approach to Stochastic Programming
• Matrix Analysis
• DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Prediction, Learning, and Games