2023-04-11-chatterjee23a.md

title	software	abstract	section	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Two-Sample Tests for Inhomogeneous Random Graphs in $L_r$ Norm: Optimality and Asymptotics	https://github.com/sdan2/Lp-graph-testing	In this paper we study the two-sample problem for inhomogeneous Erdős-Rényi (IER), random graph models, in the $L_r$ norm, in the high-dimensional regime where the number of samples is smaller or comparable to the size of the graphs. Given two symmetric matrices $P, Q \in [0, 1]^{n \times n}$ (with zeros on the diagonals), the two-sample problem for IER graphs (with respect to the $L_r$ norm $||\cdot||_r$) is to test the hypothesis $H_0: P=Q$ versus $H_1: ||P-Q||_r \geq \varepsilon$, given a sample of $m$ graphs from the respective distributions. In this paper, we obtain the optimal sample complexity for testing in the $L_r$-norm, for all integers $r \geq 1$. We also derive the asymptotic distribution of the optimal tests under $H_0$ and develop a method for consistently estimating their variances. This allows us to efficiently implement the optimal tests with precise asymptotic level and establish their asymptotic consistency. We validate our theoretical results by numerical experiments for various natural IER models.	Regular Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chatterjee23a	0	Two-Sample Tests for Inhomogeneous Random Graphs in $L_r$ Norm: Optimality and Asymptotics	6903	6911	6903-6911	6903	false	Chatterjee, Sayak and Saha, Dibyendu and Dan, Soham and Bhattacharya, Bhaswar B.	given family Sayak Chatterjee given family Dibyendu Saha given family Soham Dan given family Bhaswar B. Bhattacharya	2023-04-11		Proceedings of The 26th International Conference on Artificial Intelligence and Statistics	206	inproceedings	date-parts 2023 4 11	https://proceedings.mlr.press/v206/chatterjee23a/chatterjee23a.pdf