Rademacher Averages: Theory and Practice

Posted on April 7, 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.

Download PDF — 2.44 MB

The views expressed above are not necessarily the views of Two Sigma Investments, LP or any of its affiliates (collectively, “Two Sigma”).  The information presented above is only for informational and educational purposes and is not an offer to sell or the solicitation of an offer to buy any securities or other instruments. Additionally, the above information is not intended to provide, and should not be relied upon for investment, accounting, legal or tax advice. Two Sigma makes no representations, express or implied, regarding the accuracy or completeness of this information, and the reader accepts all risks in relying on the above information for any purpose whatsoever. Click here for other important disclaimers and disclosures.