Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
Extension of a saddle point mirror descent algorithm with application to robust PageRank
Conference Name: The 52th IEEE Conference on Decision and Control
Publisher: IEEE
Conference Location: Florence, Italy
ISBN Number: 978-1-4673-5716-6

The paper is devoted to designing an efficient recursive algorithm for solving the robust PageRank problem recently proposed by Juditsky and Polyak (2012) [4]. To this end, we reformulate the problem to a specific convexconcave saddle point problem min_{x\?n X} max_{y\?n Y} q(x, y) with simple convex sets X\subset{R^N} and Y\subset{R^N}, i.e., standard simplex and Euclidean unit ball, respectively. Aiming this goal we develop an extension of saddle point mirror descent algorithm where additional parameter sequence is introduced, thus providing more degree of freedom and the refined error bounds. Detailed complexity results of this method applied to the robust PageRank problem are given and discussed. Numerical example illustrates the theoretical results proved.

Авторы: Nazin Alexander , Tremba, A

Дата: 16 ноября 2014

Статус: опубликована

Год: 2013

Google scholar:

Направления исследований

Primal-dual subgradient methods

Huge-scale problems

Дополнительные материалы