U-statistics on network-structured data with kernels of degree larger than one

Yuyi Wang, Christos Pelekis, Jan Ramon
Proceedings of the Workshop on Statistically Sound Data Mining at ECML/PKDD, PMLR 47:37-48, 2015.

Abstract

Most analysis of U-statistics assumes that data points are independent or stationary. However, when we analyze network data, these two assumptions do not hold any more. We first define the problem of weighted U-statistics on networked data by extending previous work. We analyze their variance using Hoeffding’s decomposition and also give exponential concentration inequalities. Two efficiently solvable linear programs are proposed to find estimators with minimum worst-case variance or with tighter concentration inequalities.

Cite this Paper

BibTeX
@InProceedings{pmlr-v47-wang14a, title = {U-statistics on network-structured data with kernels of degree larger than one}, author = {Wang, Yuyi and Pelekis, Christos and Ramon, Jan}, booktitle = {Proceedings of the Workshop on Statistically Sound Data Mining at ECML/PKDD}, pages = {37--48}, year = {2015}, editor = {Hämäläinen, Wilhelmiina and Petitjean, François and Webb, I.}, volume = {47}, series = {Proceedings of Machine Learning Research}, address = {Nancy, France}, month = {15 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v47/wang14a.pdf}, url = {https://proceedings.mlr.press/v47/wang14a.html}, abstract = {Most analysis of U-statistics assumes that data points are independent or stationary. However, when we analyze network data, these two assumptions do not hold any more. We first define the problem of weighted U-statistics on networked data by extending previous work. We analyze their variance using Hoeffding’s decomposition and also give exponential concentration inequalities. Two efficiently solvable linear programs are proposed to find estimators with minimum worst-case variance or with tighter concentration inequalities.} }
Endnote
%0 Conference Paper %T U-statistics on network-structured data with kernels of degree larger than one %A Yuyi Wang %A Christos Pelekis %A Jan Ramon %B Proceedings of the Workshop on Statistically Sound Data Mining at ECML/PKDD %C Proceedings of Machine Learning Research %D 2015 %E Wilhelmiina Hämäläinen %E François Petitjean %E I. Webb %F pmlr-v47-wang14a %I PMLR %P 37--48 %U https://proceedings.mlr.press/v47/wang14a.html %V 47 %X Most analysis of U-statistics assumes that data points are independent or stationary. However, when we analyze network data, these two assumptions do not hold any more. We first define the problem of weighted U-statistics on networked data by extending previous work. We analyze their variance using Hoeffding’s decomposition and also give exponential concentration inequalities. Two efficiently solvable linear programs are proposed to find estimators with minimum worst-case variance or with tighter concentration inequalities.
RIS
TY - CPAPER TI - U-statistics on network-structured data with kernels of degree larger than one AU - Yuyi Wang AU - Christos Pelekis AU - Jan Ramon BT - Proceedings of the Workshop on Statistically Sound Data Mining at ECML/PKDD DA - 2015/11/27 ED - Wilhelmiina Hämäläinen ED - François Petitjean ED - I. Webb ID - pmlr-v47-wang14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 47 SP - 37 EP - 48 L1 - http://proceedings.mlr.press/v47/wang14a.pdf UR - https://proceedings.mlr.press/v47/wang14a.html AB - Most analysis of U-statistics assumes that data points are independent or stationary. However, when we analyze network data, these two assumptions do not hold any more. We first define the problem of weighted U-statistics on networked data by extending previous work. We analyze their variance using Hoeffding’s decomposition and also give exponential concentration inequalities. Two efficiently solvable linear programs are proposed to find estimators with minimum worst-case variance or with tighter concentration inequalities. ER -
APA
Wang, Y., Pelekis, C. & Ramon, J.. (2015). U-statistics on network-structured data with kernels of degree larger than one. Proceedings of the Workshop on Statistically Sound Data Mining at ECML/PKDD, in Proceedings of Machine Learning Research 47:37-48 Available from https://proceedings.mlr.press/v47/wang14a.html.

Related Material