Author: Matteo Riondato
Presented at: Dagstuhl Seminar on Probabilistic Methods in the Design and Analysis of Algorithms, Dagstuhl, Germany
Abstract: An overview of Rademacher Averages, a fundamental concept from statistical learning theory that can be used to derive uniform sample-dependent bounds to the deviation of samples averages from their expectations. First we introduce the fundamental definitions and theoretical results and then show how they can be applied to develop an algorithm for estimating the betweenness centralities of all nodes in a graph using progressive random sampling. This second part is based on a joint work with Eli Upfal published at ACM KDD’16.
