革新知能統合研究センター

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) 9:00am-10:00am

【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.

https://zoom.us/j/94479183806?pwd=UUtnNTJTRjc5RXIrN2syczhOVmt3Zz09
ミーティングID: 944 7918 3806
パスコード: XE7aWwR14E