Rademacher Averages: Theory and Practice

Posted ON April 07, 2017

Author: Matteo Riondato

Presented atDagstuhl 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.

Related Articles

Life at Two Sigma

We’re rigorous about our work and developing our people.

Learn More

Interested in working at Two Sigma? Explore careers.

This website uses cookies to ensure you get the best experience on our website. Learn More
Got It