Non-convex Learning Theory Team Seminar (Dr. Ying TANG)

Mon, 26 Apr 2021 09:00 - 10:00
Online Link visible to participants

Registration is closed

Get invited to future events

Free admission


This is an online seminar. Registration is required.
We’ll send the instruction for attending the online seminar.

【Non-convex Learning Theory Team】
【Date】2021/Apr/26(Mon) 900am-1000am

【Speaker】 Dr. Ying TANG

Title: Randomized Spectral Ranking
Abstract: It is only the order between the elements of eigenvectors that is crucial in spectral ranking, thus the exact value of eigenvectors is not necessary. Here, we address the problem of pairwise comparisons in the HITS algorithm with the tools borrowed from the theory of random matrices and ordinary differential equations. Given a nonnegative symmetric matrix A of order n, we provide an O(1) algorithm for single pairwise comparison without computing the exact value of the principal eigenvector of A if assuming A and A2 have been constructed offline, which trivially leads to an v2 algorithm for ranking any subset of size v, or an O(kn) algorithm for the top k selection. We prove that in ER graphs the correct rate of pairwise comparisons converges to one as n approaches infinity. Further, the similar line can be applied to the PageRank algorithm with some moderate amendment.
ミーティングID: 944 7918 3806
パスコード: XE7aWwR14E

About this community



Public events of RIKEN Center for Advanced Intelligence Project (AIP)

Join community