# Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph
$\bm{\beta}$-Model

Sagnik Nandy and Bhaswar B. Bhattacharya  Department of Statistics and Data
Science
University of Pennsylvania
Philadelphia
PA 19104
United States<EMAIL_ADDRESS>Department of Statistics and Data
Science
University of Pennsylvania
Philadelphia
PA 19104
United States<EMAIL_ADDRESS>
###### Abstract.

The $\bm{\beta}$-model for random graphs is commonly used for representing
pairwise interactions in a network with degree heterogeneity. Going beyond
pairwise interactions, Stasi et al. [45] introduced the hypergraph
$\bm{\beta}$-model for capturing degree heterogeneity in networks with higher-
order (multi-way) interactions. In this paper we initiate the rigorous study
of the hypergraph $\bm{\beta}$-model with multiple layers, which allows for
hyperedges of different sizes across the layers. To begin with, we derive the
rates of convergence of the maximum likelihood (ML) estimate and establish
their minimax rate optimality. We also derive the limiting distribution of the
ML estimate and construct asymptotically valid confidence intervals for the
model parameters. Next, we consider the goodness-of-fit problem in the
hypergraph $\bm{\beta}$-model. Specifically, we establish the asymptotic
normality of the likelihood ratio (LR) test under the null hypothesis, derive
its detection threshold, and also its limiting power at the threshold.
Interestingly, the detection threshold of the LR test turns out to be minimax
optimal, that is, all tests are asymptotically powerless below this threshold.
The theoretical results are further validated in numerical experiments. In
addition to developing the theoretical framework for estimation and inference
for hypergraph $\bm{\beta}$-models, the above results fill a number of gaps in
the graph $\bm{\beta}$-model literature, such as the minimax optimality of the
ML estimates and the non-null properties of the LR test, which, to the best of
our knowledge, have not been studied before.

##  1\. Introduction

The $\bm{\beta}$-model is an exponential family distribution on graphs with
the degree sequence as the sufficient statistic. Specifically, in the
$\bm{\beta}$-model with vertex set $[n]:=\\{1,2,\ldots,n\\}$, the edge $(i,j)$
is present independently with probability

$\displaystyle
p_{ij}:=\frac{e^{\beta_{i}+\beta_{j}}}{1+e^{\beta_{i}+\beta_{j}}},$ (1.1)

for $1\leq i<j\leq n$ and
$\bm{\beta}=(\beta_{1},\beta_{2},\ldots,\beta_{n})\in\mathbb{R}^{n}$. This
model was first considered by Park and Newman [41] and can also be viewed as
the undirected version of the $p_{1}$-model that appear in the earlier work of
Holland and Leinhardt [26]. Thereafter, the $\bm{\beta}$-model has been widely
used for capturing degree heterogeneity in networks (see Blitzstein and
Diaconis [7], Chen et al. [11], Graham [23], Jackson et al. [28], among
several others). The term $\bm{\beta}$-model can be attributed to the seminal
paper of Chatterjee et al. [10], which provides the theoretical foundations
for parameter estimation in this model.

While random graph models, such as the $\bm{\beta}$-model, are important tools
for understanding binary (pairwise) relational data, in many modern
applications interactions occur not just between pairs, but among groups of
agents. Examples include folksonomy [17], collaboration networks [29, 30, 42],
complex ecosystems [24], biological networks [37, 43], circuit design [32],
computer vision [1], among others. Hypergraphs provide the natural
mathematical framework for modeling such higher-order interactions [4, 5, 6].
Formally, a hypergraph $H$ is denoted by $H=(V(H),E(H))$, where $V(H)$ is the
vertex set (the agents in the network) and $E(H)$ is a collection of non-empty
subsets of $V(H)$. The elements in $E(H)$, referred to as hyperedges,
represent the interactions among groups of agents. Motivated by the emergence
of complex relational data with higher-order structures, there has been a slew
of recent results on modeling random hypergraphs, community detection,
recovery, clustering, and motif analysis, among others (see [21, 20, 18, 19,
40, 22, 50, 36, 35, 34, 3, 33, 27, 57, 15, 2, 58, 56] and the references
therein).

In this paper we study the hypergraph $\bm{\beta}$-model, introduced by Stasi
et al. [45], that allows one to incorporate degree heterogeneity in higher-
order networks. Like the graph $\bm{\beta}$-model (1.1), this is an
exponential family on hypergraphs where the (hypergraph) degrees are the
sufficient statistics. In its general form it allows for layered hypergraphs
with hyperedges of different sizes across the layers. To describe the model
formally we need a few notations: For $r\geq 2$, denote by ${[n]\choose r}$
the collection of all $r$-element subsets of $[n]:=\\{1,2,\ldots,n\\}$. A
hypergraph $H=(V(H),E(H))$ is said to be $r$-uniform if every element in
$E(H)$ has cardinality $r$. (Clearly, 2-uniform hypergraphs are simple
graphs.) We will denote by $\mathcal{H}_{n,r}$ the collection of all
$r$-uniform hypergraphs with vertex set $[n]$ and
$\mathcal{H}_{n,[r]}:=\bigcup_{s=2}^{r}\mathcal{H}_{n,s}$, the collection of
all hypergraphs with vertex set $[n]$ where every hyperedge has size at most
$r$. Then the $r$-layered hypergraph $\bm{\beta}$-model is a probability
distribution on $\mathcal{H}_{n,[r]}$ defined as follows:

######  Definition 1.1.

[45] Fix $r\geq 2$ and parameters
$\bm{B}:=(\bm{\beta}_{2},\ldots,\bm{\beta}_{r})$, where
$\bm{\beta}_{s}:=(\beta_{s,v})_{v\in[n]}\in\mathbb{R}^{n}$. The $r$-layered
hypergraph $\bm{\beta}$-model is a random hypergraph in $\mathcal{H}_{n,[r]}$,
denoted by $\mathsf{H}_{[r]}(n,\bm{B})$, where, for every $2\leq s\leq r$, the
hyperedge $\\{v_{1},v_{2},\ldots,v_{s}\\}\in{[n]\choose s}$ is present
independently with probability:

$\displaystyle
p_{v_{1},v_{2},\ldots,v_{s}}:=\frac{e^{\beta_{s,v_{1}}+\ldots+\beta_{s,v_{s}}}}{1+e^{\beta_{s,v_{1}}+\ldots+\beta_{s,v_{s}}}}.$
(1.2)

This model can be expressed as an exponential family on $\mathcal{H}_{n,[r]}$
with the hypergraph degrees up to order $r$ as the sufficient statistics (see
(2.1)). Specifically, the parameter $\beta_{s,u}$ encodes the popularity of
the node $u\in[n]$ to form groups of size $s$, for $2\leq s\leq r$.
Consequently, $\beta_{s,u}$ controls the local density of hyperedges of size
$s$ around the around node $u$. The model (1.2) includes as a special case the
classical graph $\bm{\beta}$-model (when $r=2$) and also the $r$-uniform
hypergraph $\bm{\beta}$-model, where only the hyperedges of size $r$ are
present. More formally, given parameters
$\bm{\beta}=(\beta_{1},\beta_{2},\ldots,\beta_{n})\in\mathbb{R}^{n}$, the
$r$-uniform hypergraph $\bm{\beta}$-model is a random hypergraph in
$\mathcal{H}_{n,r}$, denoted by $\mathsf{H}_{r}(n,\bm{\beta})$, where each
$r$-element hyperedge $\\{v_{1},v_{2},\ldots,v_{r}\\}\in{[n]\choose r}$ is
present independently with probability:

$\displaystyle
p_{v_{1},v_{2},\ldots,v_{r}}:=\frac{e^{\beta_{v_{1}}+\ldots+\beta_{v_{r}}}}{1+e^{\beta_{v_{1}}+\ldots+\beta_{v_{r}}}}.$
(1.3)

It is worth noting that, since the degrees are the sufficient statistics in
the aforementioned models, it is enough to observe only the degree sequences
(not the entire network) for inference regarding the model parameters. This
feature makes the $\bm{\beta}$-model particularly attractive because
collecting information about the entire network can often be difficult for
cost or privacy reasons. For example, Elmer et al. [16] (see also Zhang et al.
[59]) studied social networks between a group of Swiss students before and
during COVID-19 lockdown, where, for privacy reasons, only the total number of
connections of each student in the network (that is, the degrees of the
vertices) were released. The $\bm{\beta}$-model is also relevant in the
analysis of aggregated relational data, where instead of asking about
connections between groups of individuals directly, one collects data on the
number of connections of an individual with a given feature (see, for example,
Breza et al. [8] and the references therein).

Stasi et al. [45] proposed two algorithms for computing the maximum likelihood
(ML) estimates for the hypergraph $\bm{\beta}$ models described above and
reported their empirical performance. However, the statistical properties of
the ML estimates in these models have remained unexplored.

###  1.1. Summary of Results

In this paper we develop a framework for estimation and inference in the
hypergraph $\bm{\beta}$-model. Along the way, we obtain a number of new
results on the graph $\beta$-model as well. The following is a summary of the
results:

  * •

Estimation: In Section 2 we derive the rates of convergence of the ML
estimates in $r$-layered hypergraph $\bm{\beta}$-model (1.2), both in the
$L_{\infty}$ and the $L_{2}$ norms. Specifically, we show that given a sample
$H_{n}\sim\mathsf{H}_{[r]}(n,\bm{B})$ from the $r$-layered hypergraph
$\bm{\beta}$-model, the ML estimate
$\hat{\bm{B}}=(\hat{\bm{\beta}}_{2},\ldots,\hat{\bm{\beta}}_{r})$ of $\bm{B}$
satisfies:

$\displaystyle\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}\lesssim_{s,M}\,\sqrt{\frac{1}{\;n^{s-2}}}\quad\text{
and
}\quad\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}\lesssim_{s,M}\,\sqrt{\frac{\log
n}{\;n^{s-1}}},$ (1.4)

for $2\leq s\leq r$, with probability going to 1 (see Theorem 2.1). These
extend the results of Chatterjee et al. [10] on the graph $\bm{\beta}$-model,
where the rate of convergence of the ML estimate was derived only in the
$L_{\infty}$ norm, to the hypergraph case. Next, in Theorem 2.2 we show that
both the rates in (1.4) are, in fact, minimax rate optimal (up to a
$\sqrt{\log n}$ factor for the $L_{\infty}$ norm). To the best of our
knowledge, these are the first results showing the statistical optimality of
the ML estimates in the $\bm{\beta}$-model even for the graph case.

  * •

Inference: In Section 2.3 we derive the asymptotic distribution of the ML
estimate $\hat{\bm{B}}$. In particular, we prove that the finite dimensional
distributions of the ML estimate converges to a multivariate Gaussian
distribution (see Theorem 2.3). Moreover, the covariance matrix of the
Gaussian distribution can be estimated consistently, using which we can
construct asymptotically valid confidence sets for the model parameters (see
Theorem 2.4).

  * •

Testing: In Section 3 we study the goodness-of-fit problem for the hypergraph
$\bm{\beta}$-model, that is, given $\bm{\gamma}\in\mathbb{R}^{n}$ we wish to
distinguish:

$\displaystyle H_{0}:\bm{\beta}_{s}=\bm{\gamma}\quad\mbox{versus}\quad
H_{1}:\bm{\beta}_{s}\neq\bm{\gamma}.$ (1.5)

We show that the likelihood ratio (LR) statistic for this problem (centered
and scaled appropriately) is asymptotically normal under $H_{0}$ (see Theorem
3.1 for details). Using this result we construct an asymptotically level
$\alpha$ test for (1.5). Next, we study the power properties of this test. In
particular, we show that the detection threshold for the LR test in the
$L_{2}$ norm is $n^{-\frac{2s-3}{4}}$, that is, the LR test is asymptotically
powerful/powerless in detecting $\bm{\gamma}^{\prime}\in\mathbb{R}^{n}$
depending on whether $\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}$ is
asymptotically greater/smaller than $n^{-\frac{2s-3}{4}}$, respectively. We
also derive the limiting power function of the LR test at the threshold
$\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}=\Theta(n^{-\frac{2s-3}{4}})$ (see
Theorem 3.2). Further, in Theorem 3.3 we show that this detection threshold
is, in fact, minimax optimal, that is all tests are asymptotically powerless
when $\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}$ is asymptotically smaller than
$n^{-\frac{2s-3}{4}}$. In Section 3.3 we also obtain the detection threshold
of the LR test in the $L_{\infty}$ norm and establish its optimality. Again,
these appear to be the first results on the non-null properties of the LR test
and its optimality in the $\bm{\beta}$-model for the graph case itself.

In Section 4 we illustrate the finite-sample performances of the proposed
methods in simulations.

###  1.2. Related Work on the Graph $\bm{\beta}$-Model

As mentioned before, Chatterjee et al. [10] initiated the rigorous study of
estimation in the graph $\bm{\beta}$-model. They derived, among others things,
the convergence rate of the ML estimate in the $L_{\infty}$ norm. Thereafter,
Rinaldo et al. [44] derived necessary and sufficient conditions for the
existence of the ML estimate in terms of the polytope of the degree sequences.
Yan and Xu [51] proved the asymptotic normality of ML estimate and later, Yan
et al. [53] derived the properties of a moment based estimator. Karwa and
Slavkovic [31] studied the problem of estimation in the $\bm{\beta}$-model
under privacy constraints.

In the context of hypothesis testing, Mukherjee et al. [38] considered the
problem of sparse signal detection in the $\bm{\beta}$-model, that is, testing
whether all the node parameters are zero versus whether a (possibly) sparse
subset of them are non-zero. Recently, Yan et al. [55] derived the asymptotic
properties of the LR test for the goodness-of-fit problem in the graph
$\bm{\beta}$-model, under the null hypothesis.

The graph $\bm{\beta}$-model has also been generalized to incorporate
additional information, such as covariates, directionality, sparsity, and
weights (see Chen et al. [11], Chen and Olvera-Cravioto [12], Graham [23],
Stein and Leng [46], Yan et al. [52], Hillar and Wibisono [25], Yan et al.
[54], Wahlström et al. [49], Zhang et al. [59] and the references therein).
For other exponential random graph models with functions of the degrees as
sufficient statistics, see Mukherjee [39].

###  1.3. Asymptotic Notation

For positive sequences $\\{a_{n}\\}_{n\geq 1}$ and $\\{b_{n}\\}_{n\geq 1}$,
$a_{n}=O(b_{n})$ means $a_{n}\leq C_{1}b_{n}$ and $a_{n}=\Theta(b_{n})$ (and
equivalently, $a_{n}\asymp b_{n}$) means $C_{2}b_{n}\leq a_{n}\leq
C_{1}b_{n}$, for all $n$ large enough and positive constants $C_{1},C_{2}$.
Similarly, for positive sequences $\\{a_{n}\\}_{n\geq 1}$ and
$\\{b_{n}\\}_{n\geq 1}$, $a_{n}\lesssim b_{n}$ means $a_{n}\leq C_{1}b_{n}$
and $a_{n}\gtrsim b_{n}$ means $a_{n}\geq C_{2}b_{n}$ for all $n$ large enough
and positive constants $C_{1},C_{2}$. Moreover, subscripts in the above
notation, for example $O_{\square}$, $\lesssim_{\square}$,
$\gtrsim_{\square}$, and $\Theta_{\square}$, denote that the hidden constants
may depend on the subscripted parameters. Also, for positive sequences
$\\{a_{n}\\}_{n\geq 1}$ and $\\{b_{n}\\}_{n\geq 1}$, $a_{n}\ll b_{n}$ means
$a_{n}/b_{n}\rightarrow 0$ and $a_{n}\gg b_{n}$ means
$a_{n}/b_{n}\rightarrow\infty$, as $n\rightarrow\infty$.

##  2\. Maximum Likelihood Estimation in Hypergraph $\bm{\beta}$-Models

In this section we consider the problem of parameter estimation in the
hypergraph $\bm{\beta}$-model using the ML method. In Section 2.1 we derived
the rates of the consistency of the ML estimate. The central limit theorem of
the ML estimate and the construction of confidence intervals for the model
parameters are presented in Section 2.3.

###  2.1. Rates of Convergence

Given a sample $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ from the $r$-layered
hypergraph $\bm{\beta}$-model, the likelihood function can be written as
follows:

$\displaystyle L_{n}(\bm{B})=\prod_{2\leq s\leq
r}\prod_{\\{v_{1},v_{2},\ldots,v_{s}\\}\in{[n]\choose
s}}\frac{e^{\beta_{s,v_{1}}+\ldots+\beta_{s,v_{s}}}}{1+e^{\beta_{s,v_{1}}+\ldots+\beta_{s,v_{s}}}}.$
(2.1)

Therefore, the negative log-likelihood is given by

$\displaystyle\ell_{n}(\bm{B})$ $\displaystyle:=-\log L_{n}(\bm{B})$
$\displaystyle=-\sum_{s=2}^{r}\left\\{\sum_{v=1}^{n}\beta_{s,v}d_{s}(v)-\sum_{\\{v_{1},v_{2},\ldots,v_{s}\\}\in{[n]\choose
s}}\log{\left(1+\exp\left(\beta_{s,v_{1}}+\ldots+\beta_{s,v_{s}}\right)\right)}\right\\},$
(2.2)

where

$\displaystyle d_{s}(v):=\sum_{\bm{e}\in E(H_{n}):|\bm{e}|=s}\bm{1}\\{v\in
e\\},$ (2.3)

is the $s$-degree of the vertex $v\in[n]$, that is, the number of hyperedges
of size $s$ in $H_{n}$ passing through $v$. The negative log-likelihood in
(2.1) can be re-written as:

$\ell_{n}(\bm{B})=\sum_{s=2}^{r}\ell_{n,s}(\bm{\beta}_{s}),$ (2.4)

where

$\ell_{n,s}(\bm{\beta}):=\sum_{\\{v_{1},v_{2},\ldots,v_{s}\\}\in{[n]\choose
s}}\log{\left(1+\exp\left(\beta_{s,v_{1}}+\ldots+\beta_{s,v_{s}}\right)\right)}-\sum_{v=1}^{n}\beta_{s,v}d_{s}(v).$
(2.5)

Note that (2.4) is separable in $\bm{\beta}_{2},\ldots,\bm{\beta}_{r}$, hence,
the ML estimate of $\bm{B}=(\bm{\beta}_{2},\ldots,\bm{\beta}_{r})$ is given by
$\hat{\bm{B}}=(\hat{\bm{\beta}}_{2},\ldots,\hat{\bm{\beta}}_{r})$, where

$\hat{\bm{\beta}}_{s}:=\operatorname{arg\,min}_{\bm{\beta}}\ell_{n,s}(\bm{\beta}).$
(2.6)

This implies that the ML estimate $\hat{\bm{\beta}}_{s}$ satisfies the
following set of gradient equations: For all $v\in[n]$ and $2\leq s\leq r$,

$d_{s}(v)=\sum_{\\{v_{2},\ldots,v_{s}\\}\in{{[n]\backslash\\{v\\}}\choose{s-1}}}\frac{e^{\hat{\beta}_{s,v}+\hat{\beta}_{s,v_{2}}+\ldots+\hat{\beta}_{s,v_{s}}}}{1+e^{\hat{\beta}_{s,v}+\hat{\beta}_{s,v_{2}}+\ldots+\hat{\beta}_{s,v_{s}}}},$
(2.7)

where ${{[n]\backslash\\{v\\}}\choose{s-1}}$ denotes the collection of all
$(s-1)$-element subsets of $[n]\backslash\\{v\\}$. Stasi et al. [45] presented
two algorithms for computing the ML estimate, an iterative proportional
scaling algorithm and a fixed point algorithm, and showed that both algorithms
converge if the ML estimate exists.

In this paper we study the asymptotic properties of the ML estimates. In the
following theorem we show that the likelihood equations (2.7) have a unique
solution with high-probability and derive its rate of convergence. Hereafter,
we denote by $\|\bm{x}\|_{\infty}$ and $\|\bm{x}\|_{2}$, the $L_{\infty}$ and
the $L_{2}$ norms of a vector $\bm{x}$, respectively. Also, denote
$\mathcal{B}_{M}=\\{\bm{x}:\|\bm{x}\|_{\infty}\leq M\\}$, the $L_{\infty}$ the
ball of radius $M$. Throughout we will assume
$\bm{\beta}_{s}\in\mathcal{B}_{M}$, for all $2\leq s\leq r$, for some constant
$M>0$.

######  Theorem 2.1.

Suppose $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ is a sample from the
$r$-layered hypergraph $\bm{\beta}$-model as defined in (1.2). Then with
probability $1-o(1)$ the likelihood equations (2.7) have a unique solution
$\hat{\bm{B}}=(\hat{\bm{\beta}}_{2},\ldots,\hat{\bm{\beta}}_{r})$, that
satisfies:

$\displaystyle\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}\lesssim_{s,M}\,\sqrt{\frac{1}{\;n^{s-2}}}\quad\text{
and
}\quad\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}\lesssim_{s,M}\,\sqrt{\frac{\log
n}{\;n^{s-1}}},$ (2.8)

for $2\leq s\leq r$.

Theorem 2.1 provides the rates for the ML estimate both in the $L_{2}$ and
$L_{\infty}$ norms for the parameters in a $r$-layered hypergraph
$\bm{\beta}$-model. To interpret the rates in (2.8) note that $s$-degree of a
vertex (recall (2.3)) in the $r$-layered model $\mathsf{H}_{n,[r]}(n,\bm{B})$
is $O(n^{s-1})$ with high probability. This means there are essentially
$O(n^{s-1})$ independent hyperedges containing information about each
parameter in the $s$-th layer. Hence, each parameter in the $s$-th layer can
be estimated at the rate $1/\sqrt{n^{s-1}}$. Aggregating this over the $n$
coordinates gives the rates in (2.8) for the vector of parameters
$\bm{\beta}_{s}$ in the $s$-th layer.

The proof of Theorem 2.1 is given in Appendix A. The following discussion
provides a high-level outline of the proof.

  * •

For the rate in the $L_{2}$ norm we first upper bound the gradient of the log-
likelihood at the true parameter value. Specifically, we show that
$\|\nabla{\ell}_{n,s}(\bm{\beta}_{s})\|_{2}^{2}=O(n^{s})$ with high
probability (see Lemma A.1 for details). Next, we show that the smallest
eigenvalue of the Hessian matrix $\nabla^{2}{\ell}_{n,s}(\bm{\beta}_{s})$ is
bounded below by $n^{s-1}$ (up to constants) in a neighborhood of the true
parameter (see Lemma A.2). Then a Taylor expansion of the log-likelihood
around the true parameter, combined with the above estimates, imply the rate
in the $L_{2}$ norm in (2.8) (see Appendix A.1 for details).

  * •

The proof of the rate in the $L_{\infty}$ norm is more involved. For the graph
case, [10] analyzed the fixed point algorithm for solving the ML equations and
developed a stability version of the Erdős-Gallai condition (which provides a
necessary and sufficient condition for a sequence of numbers to be the degree
sequence of a graph) to derive the rate of ML estimate in the $L_{\infty}$
norm. One of the technical challenges in dealing with the hypergraph case is
the absence of Erdős-Gallai-type characterizations of the degree sequence. To
circumvent this issue, we take a more analytic approach based on the ‘leave-
one-out’ technique, that appear in the analysis of ranking models [13, 14].
Here the idea is to decompose, for each $u\in[n]$, the log-likelihood function
of the $s$-th layer $\ell_{n,s}$ (recall (2.5)) into two parts: one depending
on $\beta_{s,u}$ and the other not depending on it. Using the part of the log-
likelihood not depending on $\beta_{s,u}$ we first analyze the properties of
the constrained leave-one-out ML estimate, which is the maximizer of the part
of the log-likelihood not depending on $\beta_{s,u}$ in a neighborhood of the
leave-one-out true parameter. Then from the part of the log-likelihood
depending on $\beta_{s,u}$ we obtain, by a Taylor expansion around the true
parameter value $\beta_{s,u}$, the $L_{\infty}$ rate in (2.8) with an extra
additive error term which depends on the constrained leave-one-out ML
estimate. Using the bound on the latter obtained earlier we show this error
term is negligible compared to the $L_{\infty}$ rate in (2.8).

The following corollary about the $r$-uniform model is an immediate
consequence of Theorem 2.1. We record it separately for ease of referencing.

######  Corollary 2.1.

Suppose $H_{n}\sim\mathsf{H}_{n,r}(n,\bm{\beta})$ is a sample from the
$r$-uniform hypergraph $\bm{\beta}$-model as defined in (1.3). Then with
probability $1-o(1)$ the ML estimate $\hat{\bm{\beta}}$ is unique and

$\displaystyle\|\hat{\bm{\beta}}-\bm{\beta}\|_{2}\lesssim_{r,M}\sqrt{\frac{1}{\;n^{r-2}}}\quad\text{and}\quad\|\hat{\bm{\beta}}-\bm{\beta}\|_{\infty}\lesssim_{r,M}\sqrt{\frac{\log
n}{\;n^{r-1}}}.$ (2.9)

###  2.2. Minimax Rates

In the following theorem we establish the tightness of the rates of ML
estimate obtained in the previous section by proving matching lower bounds.

######  Theorem 2.2.

Suppose $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$, with
$\bm{B}=(\bm{\beta}_{2},\ldots,\bm{\beta}_{r})$, such that
$\bm{\beta}_{s}\in\mathcal{B}(M)$, for $2\leq s\leq r$. Given $\delta\in(0,1)$
there exists a constant $C$ (depending on $M$, $r$, and $\delta$) such that
the following holds for estimation in the $L_{2}$ norm:

$\displaystyle\min_{\hat{\bm{\beta}}}\max_{\bm{\beta}_{s}\in\mathcal{B}(M)}\mathbb{P}\left(\|\hat{\bm{\beta}}-\bm{\beta}_{s}\|_{2}\geq
C\sqrt{\frac{1}{n^{s-2}}}\right)\geq 1-\delta.$ (2.10)

Moreover, for estimation in the $L_{\infty}$ norm the following holds:

$\displaystyle\min_{\hat{\bm{\beta}}}\max_{\bm{\beta}_{s}\in\mathcal{B}(M)}\mathbb{P}\left(\|\hat{\bm{\beta}}-\bm{\beta}_{s}\|_{\infty}\geq
C\sqrt{\frac{1}{n^{s-1}}}\right)\geq 1-\delta.$ (2.11)

This result shows that the ML estimate is minimax rate optimal in the $L_{2}$
metric and (up to a $\sqrt{\log n}$ factor) in the $L_{\infty}$ metric. The
proof of Theorem 2.2 is given in Appendix B. The bound in (2.10) is proved
using Fano’s lemma. For this we construct $2^{\Theta(n)}$ well-separated
points in the parameter space which have ‘small’ average Kulbeck-Leibler (KL)
divergence with the origin (see Appendix B.1). The bound in (2.11) follows by
a direct application of Le Cam’s 2-point method (see Appendix B.2).

###  2.3. Central Limit Theorems and Confidence Intervals

The results obtained in the previous section show that the vector ML estimates
are consistent in the $L_{\infty}$-norm. However, for conducting
asymptotically precise inference on the individual model parameters, we need
to understand the limiting distribution of the ML estimates. In Theorem 2.3
below we show that the finite dimensional distributions of the ML estimates
(appropriately scaled) converge to a multivariate Gaussian distribution. Using
this result in Theorem 2.4 we construct joint confidence sets for any finite
collection of parameters. Towards this, for
$H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ denote the variance of the $s$-degree
of the node $v\in[n]$ as:

$\displaystyle\sigma_{s}(v)^{2}:=\operatorname{Var}[d_{s}(v)]=\sum_{\\{v_{2},\ldots,v_{s}\\}\in{{[n]\backslash\\{v\\}}\choose{s-1}}}\frac{e^{\beta_{s,v}+\beta_{s,v_{2}}+\ldots+\beta_{s,v_{s}}}}{(1+e^{\beta_{s,v}+\beta_{s,v_{2}}+\ldots+\beta_{s,v_{s}}})^{2}}.$
(2.12)

Then we have the following result:

######  Theorem 2.3.

Suppose $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ is a sample from the
$r$-layered hypergraph $\bm{\beta}$-model as defined in (1.2). For each $2\leq
s\leq r$ fix a collection of $a_{s}\geq 1$ indices
$J_{s}:=\\{v_{s,1},\cdots,v_{s,a_{s}}\\}\in{[n]\choose a_{s}}$. Then as
$n\rightarrow\infty$,

$\displaystyle\begin{pmatrix}[\bm{D}_{2}(\hat{\bm{\beta}}_{2}-\bm{\beta}_{2})]_{J_{2}}\\\
[\bm{D}_{3}(\hat{\bm{\beta}}_{3}-\bm{\beta}_{3})]_{J_{3}}\\\ \vdots\\\
[\bm{D}_{r}(\hat{\bm{\beta}}_{r}-\bm{\beta}_{r})]_{J_{r}}\end{pmatrix}\overset{D}{\rightarrow}\mathcal{N}_{\sum_{s=2}^{r}a_{s}}(\bm{0},\bm{I}),$
(2.13)

where $\bm{D}_{s}=\mathrm{diag}\,(\sigma_{s}(v))_{v\in[n]}$, for $2\leq s\leq
r$ and for any vector $\bm{x}\in\mathbb{R}^{n}$,
$[\bm{x}]_{J_{s}}=(x_{v})_{v\in[J_{s}]}^{\top}$.

The proof of Theorem 2.3 is given in Appendix C.1. The idea of the proof is to
linearize $\hat{\beta}_{s,v}-\beta_{s,v}$ in terms of the $s$-degrees of the
node $v\in[n]$. Since the $s$-degree of a node is the sum of independent
random variables, applying Lindeberg’s CLT gives the result in (2.13). In the
special case of the $r$-uniform model, Theorem 2.3 can be written in the
following simpler form:

######  Corollary 2.2.

Suppose $H_{n}\sim\mathsf{H}_{n,r}(n,\bm{\beta})$ is a sample from the
$r$-uniform hypergraph $\bm{\beta}$-model as defined in (1.3). For all
$v\in[n]$, let

$\sigma(v)^{2}:=\sum_{\\{v_{2},\ldots,v_{s}\\}\in{{[n]\backslash\\{v\\}}\choose{s-1}}}\frac{e^{\beta_{v}+\beta_{v_{2}}+\ldots+\beta_{v_{s}}}}{1+e^{\beta_{v}+\beta_{v_{2}}+\ldots+\beta_{v_{s}}}}.$

Then for any collection of $a\geq 1$ indices
$J:=\\{v_{1},\cdots,v_{a}\\}\in{[n]\choose a}$, as $n\rightarrow\infty$,

$[\bm{D}]_{J}([\hat{\bm{\beta}}]_{J}-[\bm{\beta}]_{J})\stackrel{{\scriptstyle
D}}{{\to}}\mathcal{N}_{a}(\bm{0},\bm{I}),$

where $\bm{D}=\mathrm{diag}\,(\sigma(v))_{v\in[n]}$,
$[\bm{D}]_{J}=\mathrm{diag}\,(\sigma(v))_{v\in J}$,
$[\hat{\bm{\beta}}]_{J}=(\beta_{v})_{v\in[J]}^{\top}$, and
$[\bm{\beta}_{s}]_{J}=(\beta_{s,v})_{v\in[J]}^{\top}$.

To use the above results to construct confidence sets for the parameters, we
need to consistently estimate the elements of the matrix $\bm{D}_{s}$. Note
that the natural plug-in estimate of $\sigma_{s}(v)$ is

$\displaystyle\hat{\sigma}_{s}(v)^{2}:=\sum_{\\{v_{2},\ldots,v_{s}\\}\in{{[n]\backslash\\{v\\}}\choose{s-1}}}\frac{e^{\hat{\beta}_{s,v}+\hat{\beta}_{s,v_{2}}+\ldots+\hat{\beta}_{s,v_{s}}}}{(1+e^{\hat{\beta}_{s,v}+\hat{\beta}_{s,v_{2}}+\ldots+\hat{\beta}_{s,v_{s}}})^{2}}.$
(2.14)

This estimate turns out to be consistent for $\sigma_{s}(v)$, leading to the
following result (see Appendix C.2 for the proof):

######  Theorem 2.4.

Suppose $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ is a sample from the
$r$-layered hypergraph $\bm{\beta}$-model as defined in (1.2). For each $2\leq
s\leq r$ fix a collection of $a_{s}\geq 1$ indices
$J_{s}:=\\{v_{s,1},\cdots,v_{s,a_{s}}\\}\in{[n]\choose a_{s}}$. Then

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}\left(\left\\{\sum_{s=2}^{r}([(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}})^{\top}[\hat{\bm{D}}_{s}^{2}]_{J_{s}}([(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}})\leq\chi^{2}_{\sum_{s=2}^{r}a_{s},1-\alpha}\right\\}\right)=1-\alpha,$
(2.15)

where $\hat{\bm{D}}_{s}^{2}=\mathrm{diag}(\hat{\sigma}_{s}(v)^{2})_{v\in[n]}$,
$[\hat{\bm{D}}_{s}^{2}]_{J_{s}}=\mathrm{diag}(\hat{\sigma}_{s}(v)^{2})_{v\in
J_{s}}$, for $2\leq s\leq r$, and for $a\geq 1$, $\chi^{2}_{a,1-\alpha}$ is
the $(1-\alpha)$-th quantile of the chi-squared distribution with $a$ degrees
of freedom.

##  3\. Goodness-of-Fit: Asymptotics of the Likelihood Ratio Test and Minimax
Detection Rates

In this section we consider the problem of testing for goodness-of-fit in the
hypergraph $\bm{\beta}$-model. In particular, given
$\bm{\gamma}\in\mathbb{R}^{n}$ and a sample
$H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$, with
$\bm{B}=(\bm{\beta}_{2},\ldots,\bm{\beta}_{r})$, we consider the following
hypothesis testing problem: For $2\leq s\leq r$,

$\displaystyle H_{0}:\bm{\beta}_{s}=\bm{\gamma}\quad\mbox{versus}\quad
H_{1}:\bm{\beta}_{s}\neq\bm{\gamma}.$ (3.1)

This section is organized as follows: In Section 3.1 we derive the asymptotic
distribution and detection rates of the likelihood ratio (LR) test for the
problem (3.1). In Section 3.2 we show that the detection rate of the LR test
is minimax optimal for testing in $L_{2}$ norm. Rates for testing in
$L_{\infty}$ norm are derived in Section 3.3.

###  3.1. Asymptotics of the Likelihood Ratio Test

Consider the LR statistic for the testing problem (3.1):

$\displaystyle\log\Lambda_{n,s}=\ell_{n,s}(\bm{\gamma})-\ell_{n,s}(\hat{\bm{\beta}}_{s}),$
(3.2)

where $\ell_{n,s}$ is the log-likelihood function (2.5) and
$\hat{\bm{\beta}}_{s}$ is the ML estimate (2.6). The following theorem proves
the limiting distribution of the LR statistic (3.2) under $H_{0}$.

######  Theorem 3.1.

Suppose $\bm{\gamma}\in\mathcal{B}(M)$. Then under $H_{0}$,

$\lambda_{n,s}:=\frac{2\log\Lambda_{n,s}-n}{\sqrt{2n}}\stackrel{{\scriptstyle
D}}{{\to}}\mathcal{N}(0,1),$ (3.3)

for $\log\Lambda_{n,s}$ as defined in (3.2).

The proof of Theorem 3.1 is given in Appendix D.1. To prove the result we
first expand $\log\Lambda_{n,s}$ around the null parameter $\bm{\gamma}$ and
derive an asymptotic expansion of $\lambda_{n,s}$ in terms of the sum of
squares of the $s$-degree sequence
$(d_{s}(1),d_{s}(2),\ldots,d_{s}(n))^{\top}$ (see (D.1)). Since the degrees
are asymptotically independent (recall Theorem 2.3), we can show that the sum
of squares of the degrees (appropriately centered and scaled) is
asymptotically normal (see Proposition D.1), establishing the result in (3.3).

Theorem 3.1 shows that the LR test

$\displaystyle\phi_{n,s}:=\bm{1}\left\\{|\lambda_{n,s}|>z_{\alpha/2}\right\\},$
(3.4)

where $z_{\alpha/2}$ is the $(1-\alpha/2)$-th quantile of the standard normal
distribution, has asymptotic level $\alpha$. To study the power of this test
consider the following testing problem:

$\displaystyle H_{0}:\bm{\beta}_{s}=\bm{\gamma}\quad\mbox{versus}\quad
H_{1}:\bm{\beta}_{s}=\bm{\gamma}^{\prime},$ (3.5)

where $\bm{\gamma}^{\prime}\neq\bm{\gamma}$ is such that
$\|\bm{\gamma}-\bm{\gamma}^{\prime}\|_{2}=O(1)$. Recall that
$\bm{d}_{s}=(d_{s}(1),d_{s}(2),\ldots,d_{s}(n))^{\top}$ is the vector of
$s$-degrees. Also, $\operatorname{Cov}_{\bm{\gamma}}[\bm{d}_{s}]$ will denote
the covariance matrix of the vector of $s$-degrees (see (C.2)).

######  Theorem 3.2.

Suppose (3.3) holds and $\bm{\gamma}^{\prime}$ as in (3.5). Then the
asymptotic power of the test $\phi_{n,s}$ defined in (3.4) satisfies:

$\lim_{n\rightarrow\infty}\mathbb{E}_{\bm{\gamma}^{\prime}}[\phi_{n,s}]=\begin{cases}\alpha&\mbox{if\;
$\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\ll n^{-\frac{2s-3}{4}}$,}\\\
1&\mbox{if \;$\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\gg
n^{-\frac{2s-3}{4}}$.}\end{cases}$ (3.6)

Moreover, if
$n^{\frac{2s-3}{4}}\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\rightarrow\tau\in(0,\infty)$,
then there exists $\eta\in(0,\infty)$ depending on $\tau$ such that

$\eta=\lim_{n\rightarrow\infty}\frac{(\bm{\gamma}^{\prime}-\bm{\gamma})^{\top}\operatorname{Cov}_{\bm{\gamma}}[\bm{d}_{s}](\bm{\gamma}^{\prime}-\bm{\gamma})}{\sqrt{n}},$

where the limit always exists along a subsequence, and

$\lim_{n\rightarrow\infty}\mathbb{E}_{\bm{\gamma}^{\prime}}[\phi_{n,s}]=\mathbb{P}\left(\left|\mathcal{N}(-\tfrac{\eta}{\sqrt{2}},1)\right|>z_{\alpha/2}\right).$
(3.7)

The proof of Theorem 3.2 is given in Appendix D.2. It entails analyzing the
asymptotic distribution of the scaled LR statistic $\lambda_{n,s}$ under
$H_{1}$ as in (3.5). Specifically, we show that when
$\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\ll n^{-\frac{2s-3}{4}}$, then
$\lambda_{n,s}\stackrel{{\scriptstyle D}}{{\to}}\mathcal{N}(0,1)$, hence the
LR test (3.3) is asymptotically powerless in detecting $H_{1}$. On the other
hand, if $\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\gg n^{-\frac{2s-3}{4}}$,
then the $\lambda_{n,s}$ diverges to infinity, hence the LR test is
asymptotically powerful. In other words, $n^{-\frac{2s-3}{4}}$ is the
detection threshold in the $L_{2}$ norm of the LR test. We also derive the
limiting power function of the LR test at the threshold
$n^{\frac{2s-3}{4}}\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\rightarrow\tau\in(0,\infty)$.
In this case, $\lambda_{n,s}\stackrel{{\scriptstyle
D}}{{\to}}\mathcal{N}(-\eta/\sqrt{2},1)$, where ‘effective signal strength’
$\eta$ is the limit of the scaled Mahalanobis distance between $\bm{\gamma}$
and $\bm{\gamma}^{\prime}$, where the dispersion matrix is the covariance
matrix of the degrees. In the next section we will show that this detection
rate is, in fact, minimax optimal.

###  3.2. Minimax Detection Rate in the $L_{2}$ Norm

In this section we will show that the detection threshold of the LR test
obtained in Theorem 3.6 is information-theoretically tight. To formalize this
consider the testing problem: For $\varepsilon>0$ and
$\bm{\gamma}\in\mathcal{B}(M)$,

$\displaystyle H_{0}:\bm{\beta}_{s}=\bm{\gamma}\quad\mbox{versus}\quad
H_{1}:\|\bm{\beta}_{s}-\bm{\gamma}\|_{2}\geq\varepsilon.$ (3.8)

The worst-case risk of a test function $\psi_{n}$ for the testing problem
(3.8) is defined as:

$\displaystyle\mathcal{R}(\psi_{n},\bm{\gamma})=\mathbb{P}_{H_{0}}(\psi_{n}=1)+\sup_{\bm{\gamma}^{\prime}\in\mathcal{B}(M):\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}\geq\varepsilon}\mathbb{P}_{\bm{\gamma}^{\prime}}(\psi_{n}=0),$
(3.9)

which is the sum of the Type I error and the maximum possible Type II error of
the test function $\psi_{n}$. Given
$H_{n}\sim\mathsf{H}_{n,s}(n,\bm{\beta}_{s})$, for some
$\bm{\beta}_{s}\in\mathcal{B}(M)$, and $\varepsilon=\varepsilon_{n}$
(depending on $n$), a sequence of test functions $\psi_{n}$ is said to be
asymptotically powerful for (3.9), if for all $\bm{\gamma}\in\mathcal{B}(M)$
$\lim_{n\rightarrow\infty}\mathcal{R}(\psi_{n},\bm{\gamma})=0$. On the other
hand, a sequence of test functions $\psi_{n}$ is said to be asymptotically
powerless for (3.9), if there exists $\bm{\gamma}\in\mathcal{B}(M)$ such that
$\lim_{n\rightarrow\infty}\mathcal{R}(\psi_{n},\bm{\gamma})=1$.

######  Theorem 3.3.

Given $H_{n}\sim\mathsf{H}_{n,s}(n,\bm{\beta}_{s})$ and
$\bm{\gamma}\in\mathcal{B}(M)$, consider the testing problem (3.8). Then the
following hold:

  * (a)

The LR test (3.1) is asymptotically powerful for (3.8), when $\varepsilon\gg
n^{-\frac{2s-3}{4}}$.

  * (b)

On the other hand, all tests are asymptotically powerless for (3.8), when
$\varepsilon\ll n^{-\frac{2s-3}{4}}$.

The result in Theorem 3.3 (a) is a direct consequence of Theorem 3.2. The
proof of Theorem 3.3 (b) is given in Appendix E.1. For this we chose
$\bm{\gamma}=\bm{0}\in\mathbb{R}^{n}$ and randomly perturb (that is, randomly
add or subtract $\varepsilon/\sqrt{n}$) the coordinates of $\bm{\gamma}$ to
construct $\bm{\beta}_{s}\in\mathcal{B}(M)$ satisfying
$\|\bm{\beta}_{s}-\bm{\gamma}\|_{2}\geq\varepsilon$. Then a second-moment
calculation of the likelihood ratio shows that detecting these two models is
impossible for $\varepsilon\ll n^{-\frac{2s-3}{4}}$. These results combined
show that $n^{-\frac{2s-3}{4}}$ is the minimax detection rate for the testing
problem (3.8) and the LR test attain the minimax rate.

######  Remark 3.1.

(Comparison between testing and estimation rates.) Recall from (2.8) and
(2.10) that the minimax rate of estimating $\hat{\bm{\beta}}_{s}$ in the
$L_{2}$ norm is $n^{-\frac{s-2}{2}}$. On the other hand, Theorem 3.3 shows
that the minimax rate of testing in the $L_{2}$ norm is
$n^{-\frac{2s-3}{4}}\ll n^{-\frac{s-2}{2}}$. For example, in the graph case
(where $s=2$), the estimation rate is $\Theta(1)$ whereas the rate of testing
is $n^{-\frac{1}{4}}$. This is an instance of the well-known phenomenon that
high-dimensional estimation is, in general, harder that testing in the
squared-error loss.

###  3.3. Testing in the $L_{\infty}$ Norm

In this section we consider the goodness-of-fit problem when separation is
measured in the $L_{\infty}$ norm. This complements our results on estimation
in $L_{\infty}$ norm in Theorem 2.1. Towards this, as in (3.8), consider the
testing problem: For $\varepsilon>0$ and $\bm{\gamma}\in\mathcal{B}(M)$,

$\displaystyle H_{0}:\bm{\beta}_{s}=\bm{\gamma}\quad\mbox{versus}\quad
H_{1}:\|\bm{\beta}_{s}-\bm{\gamma}\|_{\infty}\geq\varepsilon.$ (3.10)

In this case the minimax risk of a test function is defined as in (3.9) with
the $L_{2}$ norm $\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{2}$ replaced by the
$L_{\infty}$ norm $\|\bm{\gamma}^{\prime}-\bm{\gamma}\|_{\infty}$. Then
consider the test:

$\phi_{n,s}^{\max}:=\bm{1}\left\\{\|\hat{\bm{\beta}}_{s}-\bm{\gamma}\|_{\infty}\geq\,2C\sqrt{\frac{\log
n}{n^{s-1}}}\right\\},$

where $C:=C(s,M)>0$ is chosen according to (2.8) such that

$\mathbb{P}_{\bm{\kappa}}\left(\|\hat{\bm{\beta}}_{s}-\bm{\kappa}\|_{\infty}\leq\,C\sqrt{\frac{\log
n}{n^{s-1}}}\right)\rightarrow 1,$

for all $\bm{\kappa}\in\mathcal{B}(M)$. This implies,
$\mathbb{E}_{\bm{\gamma}}[\phi_{n,s}^{\max}]\rightarrow 0$. Also, for
$\bm{\gamma}^{\prime}\in\mathcal{B}(M)$ such that
$\|\bm{\gamma}-\bm{\gamma}^{\prime}\|_{\infty}\geq\varepsilon$,

$\displaystyle\mathbb{E}_{\bm{\gamma}^{\prime}}[\phi_{n,s}^{\max}]=\mathbb{P}_{\bm{\gamma}^{\prime}}\left(\|\hat{\bm{\beta}}_{s}-\bm{\gamma}\|_{\infty}\geq\,2C\sqrt{\frac{\log
n}{n^{s-1}}}\right)\geq\mathbb{P}_{\bm{\gamma}^{\prime}}\left(\|\hat{\bm{\beta}}_{s}-\bm{\gamma}^{\prime}\|_{\infty}\leq\,C\sqrt{\frac{\log
n}{n^{s-1}}}\right)\rightarrow 1,$ (3.11)

whenever $\varepsilon\gg\sqrt{\log n/n^{s-1}}$. This is because
$\|\hat{\bm{\beta}}_{s}-\bm{\gamma}^{\prime}\|_{\infty}\leq\,C\sqrt{\log
n/n^{s-1}}$ implies,

$\|\hat{\bm{\beta}}_{s}-\bm{\gamma}\|_{\infty}\geq\|\bm{\gamma}-\bm{\gamma}^{\prime}\|_{\infty}-\|\hat{\bm{\beta}}_{s}-\bm{\gamma}^{\prime}\|_{\infty}\geq\varepsilon-C\sqrt{\frac{\log
n}{n^{s-1}}}\geq 2C\sqrt{\frac{\log n}{n^{s-1}}},$

whenever $\varepsilon\gg\sqrt{\log n/n^{s-1}}$. This implies that the test
$\phi_{n,s}^{\max}$ in (3.11) is asymptotically powerful for (3.10) whenever
$\varepsilon\gg\sqrt{\log n/n^{s-1}}$. The following result shows that this
rate is optimal (up to a factor of $\sqrt{\log n}$) for testing in the
$L_{\infty}$ norm.

######  Theorem 3.4.

Given $H_{n}\sim\mathsf{H}_{n,s}(n,\bm{\beta}_{s})$ and
$\gamma,\bm{\beta}_{s}\in\mathcal{B}(M)$, consider the testing problem (3.10).
Then the following hold:

  * (a)

The test $\phi_{n,s}^{\max}$ in (3.11) is asymptotically powerful for (3.10),
when $\varepsilon\gg\sqrt{\frac{\log n}{n^{s-1}}}$.

  * (b)

On the other hand, all tests are asymptotically powerless for (3.10), when
$\varepsilon\ll\sqrt{\frac{1}{n^{s-1}}}$.

The proof of Theorem 3.4 (b) is given in Appendix E.2. Note that in this case
minimax rates of estimation and testing are the same, since the effect of
high-dimensional aggregation does not arise when separation is measured in the
$L_{\infty}$ norm.

##  4\. Numerical Experiments

In this section we study the performance of the ML estimates and the LR tests
discussed above in simulations. To begin with we simulate a 3-uniform
hypergraph $\bm{\beta}$-model $\mathsf{H}_{3}(n,\bm{\beta})$, with $n=400$
vertices and $\bm{\beta}=\bm{0}\in\mathbb{R}^{n}$. Figure 1(a) shows the
quantile-quantile (QQ) plot (over 200 iterations) of the first coordinate of
the ML estimate $[\bm{D}]_{1}([\hat{\bm{\beta}}-\bm{\beta}]_{1})$ (where
$\hat{\bm{\beta}}$ is computed using the fixed point algorithm described in
[45] and $\bm{D}$ is as defined in Corollary 2.2). We observe that the
empirical quantiles closely follow the quantiles of the standard normal
distribution, validating the result in Corollary 2.2.

(a)

(b)

(c)

Figure 1. (a) QQ plot of the ML estimate $\hat{\beta}_{1}$, (b) confidence
intervals for $\beta_{1}$, and (c) power of the LR test for the goodness of
fit problem (4.1), in the 3-uniform hypergraph $\bm{\beta}$-model.

In the same setup as above, Figure 1(b) shows the 95% confidence interval for
$[\bm{\beta}]_{1}$ over 50 iterations. Specifically, we plot the intervals

$\left[[\hat{\bm{\beta}}]_{1}-\frac{1.96}{[\hat{\bm{D}}]_{1}},[\hat{\bm{\beta}}]_{1}+\frac{1.96}{[\hat{\bm{D}}]_{1}}\right],$

where $\hat{\bm{D}}$ is the estimate of $\bm{D}$ as defined in Theorem 2.4.
This figure shows that 47 out of 50 of intervals cover the true parameter,
which gives an empirical coverage of $47/50=0.94$.

Next, we consider the goodness of fit problem in $s$-uniform hypergraph
$\bm{\beta}$-model:

$\displaystyle H_{0}:\bm{\beta}=0\quad\mbox{ versus }\quad
H_{1}:\bm{\beta}\neq 0,$ (4.1)

for $s=2,3$. For this we simulate $H_{n}\sim\mathsf{H}_{3}(n,\bm{\gamma})$,
with $n=250$ and $\bm{\gamma}=\alpha\cdot\bm{u}$, where $\bm{u}$ is chosen
uniformly at random from the $n$-dimensional unit sphere and $\alpha\in[0,1]$.
Figure 1(c) shows the empirical power of the LR test (3.4) (over 50
iterations) as $\alpha$ varies over a grid of $25$ uniformly spaced values in
$[0,1]$, for $s=2,3$. In both cases, as expected, the power increases with
$\alpha$, which, in this case, determines the signal strength. Also, the LR
test is more powerful in the 3-uniform case compared to the 2-uniform case.
This aligns with conclusions of Theorem 3.2, which shows that the detection
threshold of the LR test in the 3-uniform case is $n^{-\frac{3}{4}}$, while
for 2-uniform case it is $n^{-\frac{1}{4}}$. Hence, one expects to see more
power at lower signal strengths (smaller $\alpha$) for $s=3$ compared to
$s=2$.

### Acknowledgements

B. B. Bhattacharya was supported by NSF CAREER grant DMS 2046393, NSF grant
DMS 2113771, and a Sloan Research Fellowship.

## References

  * Agarwal et al. [2005] S. Agarwal, J. Lim, L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie.  Beyond pairwise clustering.  In _2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05)_ , volume 2, pages 838–845. IEEE, 2005.
  * Ahn et al. [2019] K. Ahn, K. Lee, and C. Suh.  Community recovery in hypergraphs.  _IEEE Transactions on Information Theory_ , 65(10):6561–6579, 2019.
  * Balasubramanian [2021] K. Balasubramanian.  Nonparametric modeling of higher-order interactions via hypergraphons.  _The Journal of Machine Learning Research_ , 22(1):6464–6498, 2021.
  * Battiston et al. [2020] F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, and G. Petri.  Networks beyond pairwise interactions: structure and dynamics.  _Physics Reports_ , 874:1–92, 2020.
  * Battiston et al. [2021] F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. Ferraz de Arruda, B. Franceschiello, I. Iacopini, S. Kéfi, V. Latora, Y. Moreno, et al.  The physics of higher-order interactions in complex systems.  _Nature Physics_ , 17(10):1093–1098, 2021.
  * Benson et al. [2016] A. R. Benson, D. F. Gleich, and J. Leskovec.  Higher-order organization of complex networks.  _Science_ , 353(6295):163–166, 2016.
  * Blitzstein and Diaconis [2010] J. Blitzstein and P. Diaconis.  A sequential importance sampling algorithm for generating random graphs with prescribed degrees.  _Internet Mathematics_ , 6:489–522, 2010.
  * Breza et al. [2023] E. Breza, A. G. Chandrasekhar, S. Lubold, T. H. McCormick, and M. Pan.  Consistently estimating network statistics using aggregated relational data.  _Proceedings of the National Academy of Sciences_ , 120(21):e2207185120, 2023.
  * Brown [1971] B. M. Brown.  Martingale Central Limit Theorems.  _The Annals of Mathematical Statistics_ , 42(1):59–66, 1971.
  * Chatterjee et al. [2011] S. Chatterjee, P. Diaconis, and A. Sly.  Random graphs with a given degree sequence.  _The Annals of Applied Probability_ , 21(4):1400–1435, 2011.
  * Chen et al. [2021] M. Chen, K. Kato, and C. Leng.  Analysis of networks via the sparse $\beta$-model.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 83(5):887–910, 2021.
  * Chen and Olvera-Cravioto [2013] N. Chen and M. Olvera-Cravioto.  Directed random graphs with given degree distributions.  _Stochastic Systems_ , 3(1):147–186, 2013.
  * Chen et al. [2022] P. Chen, C. Gao, and A. Y. Zhang.  Partial recovery for top-$k$ ranking: Optimality of mle and suboptimality of the spectral method.  _The Annals of Statistics_ , 50(3):1618–1652, 2022.
  * Chen et al. [2019] Y. Chen, J. Fan, C. Ma, and K. Wang.  Spectral method and regularized mle are both optimal for top-$K$ ranking.  _The Annals of Statistics_ , 47 4:2204–2235, 2019.
  * Chien et al. [2019] I. E. Chien, C.-Y. Lin, and I.-H. Wang.  On the minimax misclassification ratio of hypergraph community detection.  _IEEE Transactions on Information Theory_ , 65(12):8095–8118, 2019.
  * Elmer et al. [2020] T. Elmer, K. Mepham, and C. Stadtfeld.  Students under lockdown: Comparisons of students? social networks and mental health before and during the covid-19 crisis in switzerland.  _Plos One_ , 15(7):e0236337, 2020.
  * Ghoshal et al. [2009] G. Ghoshal, V. Zlatić, G. Caldarelli, and M. E. Newman.  Random hypergraphs and their applications.  _Physical Review E_ , 79(6):066118, 2009.
  * Ghoshdastidar and Dukkipati [2015a] D. Ghoshdastidar and A. Dukkipati.  A provable generalized tensor spectral method for uniform hypergraph partitioning.  In _International Conference on Machine Learning_ , pages 400–409. PMLR, 2015a.
  * Ghoshdastidar and Dukkipati [2015b] D. Ghoshdastidar and A. Dukkipati.  Spectral clustering using multilinear svd: Analysis, approximations and applications.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 29, 2015b.
  * Ghoshdastidar and Dukkipati [2017a] D. Ghoshdastidar and A. Dukkipati.  Consistency of spectral hypergraph partitioning under planted partition model.  _The Annals of Statistics_ , 45(1):289–315, 2017a.
  * Ghoshdastidar and Dukkipati [2017b] D. Ghoshdastidar and A. Dukkipati.  Uniform hypergraph partitioning: Provable tensor methods and sampling techniques.  _The Journal of Machine Learning Research_ , 18(1):1638–1678, 2017b.
  * Gracious et al. [2023] T. Gracious, A. Gupta, and A. Dukkipati.  Neural temporal point process for forecasting higher order and directional interactions.  _arXiv:2301.12210_ , 2023.
  * Graham [2017] B. S. Graham.  An econometric model of network formation with degree heterogeneity.  _Econometrica_ , 85(4):1033–1063, 2017.
  * Grilli et al. [2017] J. Grilli, G. Barabás, M. J. Michalska-Smith, and S. Allesina.  Higher-order interactions stabilize dynamics in competitive network models.  _Nature_ , 548(7666):210–213, 2017.
  * Hillar and Wibisono [2013] C. Hillar and A. Wibisono.  Maximum entropy distributions on graphs.  _arXiv:1301.3321_ , 2013.
  * Holland and Leinhardt [1981] P. W. Holland and S. Leinhardt.  An exponential family of probability distributions for directed graphs.  _Journal of the American Statistical association_ , 76(373):33–50, 1981.
  * Hu and Wang [2022] J. Hu and M. Wang.  Multiway spherical clustering via degree-corrected tensor block models.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1078–1119. PMLR, 2022.
  * Jackson et al. [2008] M. O. Jackson et al.  _Social and Economic Networks_ , volume 3.  Princeton University Press, 2008.
  * Ji and Jin [2016] P. Ji and J. Jin.  Coauthorship and citation networks for statisticians.  _The Annals of Applied Statistics_ , pages 1779–1812, 2016.
  * Karwa and Petrović [2016] V. Karwa and S. Petrović.  Discussion of “coauthorship and citation networks for statisticians”.  _The Annals of Applied Statistics_ , 10(4):1827–1834, 2016.
  * Karwa and Slavkovic [2016] V. Karwa and A. Slavkovic.  Inference using noisy degrees: Differentially private $\beta$-model and synthetic graphs.  _The Annals of Statistics_ , 44(1):87–112, 2016\.
  * Karypis and Kumar [1999] G. Karypis and V. Kumar.  Multilevel $k$-way hypergraph partitioning.  In _Proceedings of the 36th Annual ACM/IEEE Design Automation Conference_ , pages 343–348, 1999.
  * Ke et al. [2019] Z. T. Ke, F. Shi, and D. Xia.  Community detection for hypergraph networks via regularized tensor power iteration.  _arXiv preprint arXiv:1909.06503_ , 2019.
  * Lotito et al. [2022] Q. F. Lotito, F. Musciotto, A. Montresor, and F. Battiston.  Higher-order motif analysis in hypergraphs.  _Communications Physics_ , 5(1):79, 2022.
  * Lotito et al. [2023] Q. F. Lotito, F. Musciotto, A. Montresor, and F. Battiston.  Hyperlink communities in higher-order networks.  _arXiv:2303.01385_ , 2023.
  * Lunagómez et al. [2017] S. Lunagómez, S. Mukherjee, R. L. Wolpert, and E. M. Airoldi.  Geometric representations of random hypergraphs.  _Journal of the American Statistical Association_ , 112(517):363–383, 2017.
  * Michoel and Nachtergaele [2012] T. Michoel and B. Nachtergaele.  Alignment and integration of complex networks by hypergraph-based spectral clustering.  _Physical Review E_ , 86(5):056111, 2012.
  * Mukherjee et al. [2018] R. Mukherjee, S. Mukherjee, and S. Sen.  Detection thresholds for the $\beta$-model on sparse graphs.  _The Annals of Statistics_ , 46(3):1288–1317, 2018.
  * Mukherjee [2020] S. Mukherjee.  Degeneracy in sparse ergms with functions of degrees as sufficient statistics.  _Bernoulli_ , 26(2):1016–1043, 2020.
  * Pal and Zhu [2021] S. Pal and Y. Zhu.  Community detection in the sparse hypergraph stochastic block model.  _Random Structures & Algorithms_, 59(3):407–463, 2021.
  * Park and Newman [2004] J. Park and M. E. Newman.  Statistical mechanics of networks.  _Physical Review E_ , 70(6):066117, 2004.
  * Patania et al. [2017] A. Patania, G. Petri, and F. Vaccarino.  The shape of collaborations.  _EPJ Data Science_ , 6:1–16, 2017.
  * Petri et al. [2014] G. Petri, P. Expert, F. Turkheimer, R. Carhart-Harris, D. Nutt, P. J. Hellyer, and F. Vaccarino.  Homological scaffolds of brain functional networks.  _Journal of The Royal Society Interface_ , 11(101):20140873, 2014.
  * Rinaldo et al. [2013] A. Rinaldo, S. Petrović, and S. E. Fienberg.  Maximum lilkelihood estimation in the $\beta$-model.  _The Annals of Statistics_ , 41(3):1085–1110, 2013.
  * Stasi et al. [2014] D. Stasi, K. Sadeghi, A. Rinaldo, S. Petrovic, and S. Fienberg.  $\beta$ models for random hypergraphs with a given degree sequence.  _Proceedings 21st International Conference on Computational Statistics_ , pages 593–600, 2014.
  * Stein and Leng [2020] S. Stein and C. Leng.  A sparse $\beta$-model with covariates for networks.  _arXiv:2010.13604_ , 2020.
  * Tsybakov [2009] A. B. Tsybakov.  _Introduction to Nonparametric Estimation_.  Springer Series in Statistics. Springer, New York, 2009.
  * Vershynin [2010] R. Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  _arXiv:1011.3027_ , 2010.
  * Wahlström et al. [2017] J. Wahlström, I. Skog, P. S. La Rosa, P. Händel, and A. Nehorai.  The $\beta$-model–maximum likelihood, cramér–rao bounds, and hypothesis testing.  _IEEE Transactions on Signal Processing_ , 65(12):3234–3246, 2017.
  * Yadati et al. [2019] N. Yadati, M. Nimishakavi, P. Yadav, V. Nitin, A. Louis, and P. Talukdar.  Hypergcn: a new method of training graph convolutional networks on hypergraphs.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pages 1511–1522, 2019.
  * Yan and Xu [2013] T. Yan and J. Xu.  A central limit theorem in the $\beta$-model for undirected random graphs with a diverging number of vertices.  _Biometrika_ , 100(2):519–524, 2013.
  * Yan et al. [2016a] T. Yan, C. Leng, and J. Zhu.  Asymptotics in directed exponential random graph models with an increasing bi-degree sequence.  _The Annals of Statistics_ , 44(1):31–57, 2016a.
  * Yan et al. [2016b] T. Yan, H. Qin, and H. Wang.  Asymptotics in undirected random graph models parameterized by the strengths of vertices.  _Statistica Sinica_ , 26:273–293, 2016b.
  * Yan et al. [2019] T. Yan, B. Jiang, S. E. Fienberg, and C. Leng.  Statistical inference in a directed network model with covariates.  _Journal of the American Statistical Association_ , 114(526):857–868, 2019.
  * Yan et al. [2022] T. Yan, Y. Li, J. Xu, Y. Yang, and J. Zhu.  Wilks’ theorems in the $\beta$-model.  _arXiv:2211.10055_ , 2022.
  * Young et al. [2021] J.-G. Young, G. Petri, and T. P. Peixoto.  Hypergraph reconstruction from network data.  _Communications Physics_ , 4(1):135, 2021.
  * Yuan et al. [2022] M. Yuan, R. Liu, Y. Feng, and Z. Shang.  Testing community structure for hypergraphs.  _The Annals of Statistics_ , 50(1):147–169, 2022\.
  * Zhang and Tan [2022] Q. Zhang and V. Y. Tan.  Exact recovery in the general hypergraph stochastic block model.  _IEEE Transactions on Information Theory_ , 69(1):453–471, 2022.
  * Zhang et al. [2023] Y. Zhang, Q. Wang, Y. Zhang, T. Yan, and J. Luo.  L-2 regularized maximum likelihood for $\beta$-model in large and sparse networks.  _arXiv:2110.11856_ , 2023.

##  Appendix A Proof of Theorem 2.1

###  A.1. Convergence Rate in the $L_{2}$ Norm

As mentioned in the Introduction, the proof of Theorem 2.1 involves showing
the following: (1) a concentration bound on the gradient of negative log-
likelihood $\ell_{n,s}$ (recall (2.5)) at the true parameter value
$\bm{B}=(\bm{\beta}_{1},\bm{\beta}_{2},\ldots,\bm{\beta}_{r})$, and (2) the
strong convexity of $\ell_{n,s}$ in a neighborhood of the true parameter. We
begin with the concentration of the gradient $\nabla{\ell}_{n,s}$ in both the
$L_{2}$ and the $L_{\infty}$ norms:

######  Lemma A.1.

Suppose the assumptions of Theorem 2.1 hold. Then for each $2\leq s\leq r$,
there exists a constant $C>0$ (depending on $r$ and $M$) such that the
following hold:

$\displaystyle\|\nabla{\ell}_{n,s}(\bm{\beta}_{s})\|_{2}^{2}\leq
C\,n^{s}\quad\text{ and
}\quad\|\nabla{\ell}_{n,s}(\bm{\beta}_{s})\|^{2}_{\infty}\leq C\,n^{s-1}\log
n,$ (A.1)

with probability $1-O\left(\frac{1}{n^{2}}\right)$.

The next step is to establish the strong convexity of $\ell_{n,s}$. Towards
this we need to show that the smallest eigenvalue
$\lambda_{\min}(\nabla^{2}\ell_{n,s})$ of the Hessian matrix
$\nabla^{2}\ell_{n,s}$ (appropriately scaled) is bounded away from zero in a
neighborhood of the true value $\bm{\beta}_{s}$. This is the content of the
following lemma, which also establishes a matching upper bound on the largest
eigenvalue $\lambda_{\max}(\nabla^{2}\ell_{n,s})$ of the Hessian matrix
$\nabla^{2}\ell_{n,s}$.

######  Lemma A.2.

Suppose the assumptions of Theorem 2.1 hold. Fix $2\leq s\leq r$ and a
constant $K>0$. Then there exists a constants
$C_{1}^{\prime},C_{2}^{\prime}>0$ (depending on $r$ and $M$) such that the
following hold:

$\displaystyle
C_{1}^{\prime}e^{-s\|\bm{\beta}-\bm{\beta}_{s}\|_{2}}n^{s-1}\leq\lambda_{\min}(\nabla^{2}{\ell}_{n,s}(\bm{\beta}))\leq\lambda_{\max}(\nabla^{2}{\ell}_{n,s}(\bm{\beta}))\leq{C}_{2}^{\prime}n^{s-1}.$
(A.2)

As a consequence, there exists a constants $C_{1},C_{2}>0$ (depending on $r$,
$K$, and $M$) such that the following hold:

$\displaystyle
C_{1}n^{s-1}\leq\inf_{\bm{\beta}:\|\bm{\beta}-\bm{\beta}_{s}\|_{2}\leq
K}\lambda_{\min}(\nabla^{2}{\ell}_{n,s}(\bm{\beta}))\leq\sup_{\bm{\beta}:\|\bm{\beta}-\bm{\beta}_{s}\|_{2}\leq
K}\lambda_{\max}(\nabla^{2}{\ell}_{n,s}(\bm{\beta}))\leq{C}_{2}n^{s-1}.$ (A.3)

The proofs of Lemma A.1 and Lemma A.2 are given in Appendix A.1.2 and Appendix
A.1.3, respectively. We first apply these results to prove the rate of
convergence in the $L_{2}$ norm in Theorem 2.1.

####  A.1.1. Deriving the $L_{2}$ Norm Bound in (2.8)

To begin with suppose the ML equations (2.7) have a solution
$\hat{\bm{B}}=(\hat{\bm{\beta}}_{2},\ldots,\hat{\bm{\beta}}_{r})$. This
implies, $\nabla\ell_{n,s}(\hat{\bm{\beta}}_{s})=0$, for $2\leq s\leq r$,
where $\ell_{n,s}$ is as defined in (2.5). For $2\leq s\leq r$ and $0\leq
t\leq 1$, define

$\bm{\beta}_{s}(t):=t\hat{\bm{\beta}}_{s}+(1-t)\bm{\beta}_{s},$

and
$g_{s}(t):=(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})^{\top}\nabla\ell_{n,s}(\bm{\beta}_{s}(t))$.
Note that
$\nabla\ell_{n,s}(\bm{\beta}_{s}(1))=\nabla\ell_{n,s}(\hat{\bm{\beta}}_{s})=0$.
Hence, by the Cauchy-Schwarz inequality,

$\displaystyle|g_{s}(1)-g_{s}(0)|=|(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})^{\top}\nabla\ell_{n,s}(\bm{\beta}_{s})|\leq\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}\cdot\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{2}.$
(A.4)

Also,

$\displaystyle
g_{s}^{\prime}(t)=(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})^{\top}\nabla^{2}\ell_{n,s}(\bm{\beta}_{s}(t))(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})\geq\lambda_{\min}(\nabla^{2}\ell_{n,s}(\bm{\beta}_{s}(t)))\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}^{2}.$
(A.5)

We now consider two cases: To begin with assume $s\geq 3$. By Lemma A.2, given
a constant $K>0$ there exists a constant $C_{1}>0$ (depending on $r,K,M$) such
that

$\displaystyle\inf_{\bm{\beta}:\|\bm{\beta}-\bm{\beta}_{s}\|_{2}\leq
K}\lambda_{\min}(\nabla^{2}\ell_{n,s}(\bm{\beta}))\geq C_{1}n^{s-1}.$ (A.6)

Note that
$\|\bm{\beta}_{s}(t)-\bm{\beta}_{s}\|_{2}=|t|\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}$.
Then

$\displaystyle|g_{s}(1)-g_{s}(0)|\geq g_{s}(1)-g_{s}(0)$
$\displaystyle=\int_{0}^{1}g_{s}^{\prime}(t)\mathrm{d}t$
$\displaystyle\geq\int_{0}^{\min\\{1,\frac{K}{\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}}\\}}g_{s}^{\prime}(t)\mathrm{d}t$
$\displaystyle\geq
C_{1}n^{s-1}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}^{2}\min\left\\{1,\frac{K}{\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}}\right\\},$

where the last step follows from (A.5) and (A.6). Therefore, by (A.4) and
Lemma A.1, with probability $1-O(\frac{1}{n^{2}})$,

$\displaystyle\min\\{\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2},K\\}\lesssim_{r,K,M}\frac{1}{n^{s-1}}\cdot\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{2}\lesssim_{r,K,M}\sqrt{\frac{1}{n^{s-2}}}.$
(A.7)

Since $K>0$ is fixed and the RHS of (A.9) converges to zero for $s\geq 3$, the
$L_{2}$ norm bound in (2.8) follows, under the assumption that ML equations
(2.7) have a solution.

Next, suppose $s=2$. Since
$\|\bm{\beta}_{2}(t)-\bm{\beta}_{2}\|_{2}=|t|\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}$.
By Lemma A.2,

$\displaystyle\lambda_{\min}(\nabla^{2}\ell_{n,2}(\bm{\beta}_{2}(t)))\geq
C_{1}^{\prime}e^{-2|t|\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}}n,$ (A.8)

for some constant $C_{1}^{\prime}>0$ depending on $M$. Then

$\displaystyle|g_{2}(1)-g_{2}(0)|\geq g_{2}(1)-g_{2}(0)$
$\displaystyle=\int_{0}^{1}g_{2}^{\prime}(t)\mathrm{d}t$ $\displaystyle\geq
C_{1}^{\prime}n\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}^{2}\int_{0}^{1}e^{-2|t|\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}}\mathrm{d}t$
(by (A.5) and (A.6))
$\displaystyle\geq\frac{C_{1}^{\prime}}{2}n\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}\left(1-e^{-2\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}}\right).$

Therefore, by (A.4) and Lemma A.1, with probability $1-o(1)$,

$\displaystyle\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}\left(1-e^{-2\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}}\right)\leq\frac{2}{C_{1}^{\prime}n}\cdot\|\nabla\ell_{n,2}(\bm{\beta}_{2})\|_{2}\leq
C^{\prime},$ (A.9)

for some constant $C^{\prime}>0$ depending on $M$. Note that if
$\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}\geq 1$, then
$(1-e^{-2\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}})\geq 1-e^{-2}$. Hence,
(A.9) implies, $\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}\leq C$, for some
constant $C>0$ depending on $M$. Therefore,

$\|\hat{\bm{\beta}}_{2}-\bm{\beta}_{2}\|_{2}\leq\max\left\\{1,C\right\\}.$

This implies the $L_{2}$ norm bound in (2.8), under the assumption that the ML
equations (2.7) have a solution, for $s=2$.

To complete the proof we need to show that bounded solution to equation (2.7)
exists. To this end, for $2\leq s\leq r$, denote by $\mathcal{D}_{s}$, the set
of all possible degree sequences in an $s$-uniform hypergraph on $n$ vertices.
Moreover, let $\mathcal{R}_{s}$ be the set of all expected degree sequences in
a hypergraph on $n$ vertices sampled from the $s$-uniform model (1.3). The
following result shows that any convex combination of $s$-degree sequences in
$\mathcal{D}_{s}$ can be reached by the limit of expected degree sequences of
the $s$-uniform hypergraph $\bm{\beta}$-model. This was proved in the graph
case ($s=2$) by Chatterjee et al. [10, Theorem 1.4]. Here, we show that the
same holds for all $2\leq s\leq r$.

######  Proposition A.1.

Fix $2\leq s\leq r$ and let $\mathcal{D}_{s}$ and $\mathcal{R}_{s}$ be as
defined above. Then $\mathrm{conv}\,(\mathcal{D}_{s})=\bar{\mathcal{R}}_{s}$,
where $\mathrm{conv}\,(\mathcal{D}_{s})$ denotes the convex hull of
$\mathcal{D}_{s}$ and $\widebar{\mathcal{R}}_{s}$ is the closure of
$\mathcal{R}_{s}$.

The proof of the above result is given in Appendix F. Using this proposition
we now show the existence of bounded solutions of the ML equations (2.7). Note
that by Proposition A.1, given $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ the
$s$-degree sequence
$(d_{s}(1),\ldots,d_{s}(n))\in\mathcal{D}_{s}\subseteq\bar{\mathcal{R}}_{s}$.
This implies, there exists a sequence $\\{\bm{x}_{t}\\}_{t\geq
0}\in\mathcal{R}_{s}$ satisfying

$\lim_{t\rightarrow\infty}\bm{x}_{t}=(d_{s}(1),\ldots,d_{s}(n)).$

Since $\bm{x}_{t}\in\mathcal{R}_{s}$, there exists
$\\{\hat{\bm{\beta}}_{1}^{(t)},\ldots,\hat{\bm{\beta}}_{r}^{(t)}\\}$ such that

$\bm{x}_{t}=\sum_{\\{v_{2},\ldots,v_{s}\\}\in{{[n]\backslash\\{v\\}}\choose{s-1}}}\frac{e^{\beta^{(t)}_{s,v}+\beta^{(t)}_{s,v_{2}}+\ldots+\beta^{(t)}_{s,v_{s}}}}{1+e^{\beta^{(t)}_{s,v}+\beta^{(t)}_{s,v_{2}}+\ldots+\beta^{(t)}_{s,v_{s}}}},$
(A.10)

for $2\leq s\leq r$. In other words, for each $t\geq 0$,
$\\{\hat{\bm{\beta}}_{1}^{(t)},\ldots,\hat{\bm{\beta}}_{r}^{(t)}\\}$ is a
solution of the ML equations (2.7) with $(d_{s}(1),d_{s}(2),\ldots,d_{s}(n))$
replaced by $\bm{x}_{t}$. By the previous argument, there exists $C>0$ (not
depending on $t$) such that with probability $1-o(1)$,

$\max_{2\leq s\leq r}\|\hat{\bm{\beta}}^{(t)}_{s}\|_{\infty}\leq C,$

for all $t\geq 0$. Therefore, the sequence
$\\{(\hat{\bm{\beta}}^{(t)}_{1},\hat{\bm{\beta}}^{(t)}_{2},\ldots,\hat{\bm{\beta}}^{(t)}_{r})\\}_{\geq
0}$ has a limit point. This limit point is a solution to (2.7) (by taking
limit as $t\rightarrow\infty$ in (A.10)) and is bounded. Finally, since
$\ell_{n,s}$ is strongly convex for $\bm{\beta}\in\mathcal{B}(M)$ (see (A.2)),
if the gradient equations have a bounded solution, it is the unique minimizer.
Therefore, there exists a unique bounded solution to (2.7) which is the
minimizer of $\ell_{n,s}$.

####  A.1.2. Proof of Lemma A.1

Recalling (2.7) note that, for $v\in[n]$, $v$-th coordinate of the gradient of
$\nabla\ell_{n,s}$ is given by:

$\displaystyle\nabla\ell_{n,s}(\bm{\beta}_{s})_{v}$
$\displaystyle=\mathbb{E}[d_{s}(v)]-d_{s}(v)$ (A.11)

where

$\displaystyle\mathbb{E}[d_{s}(v)]=\sum_{\\{v_{2},\ldots,v_{s}\\}\in{{[n]\backslash\\{v\\}}\choose{s-1}}}\frac{e^{\beta_{s,v}+\beta_{s,v_{2}}+\ldots+\beta_{s,v_{s}}}}{1+e^{\beta_{s,v}+\beta_{s,v_{2}}+\ldots+\beta_{s,v_{s}}}}.$
(A.12)

Since $d_{s}(v)$ is the sum of $O(n^{s-1})$ independent random variables, by
Hoeffding’s inequality and the union bound,

$\displaystyle\mathbb{P}\left(\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{\infty}^{2}\geq
4\,C_{s,M}n^{s-1}\log n\right)\leq\frac{1}{n^{2}},$

for some constant $C_{s,M}>0$ (depending on $s$ and $M$). This establishes the
second bound in (A.1).

Next, we prove the first bound in (A.1). Denote by
$\mathbb{B}^{n}:=\\{\bm{x}\in\mathbb{R}^{n}:\|\bm{x}\|_{2}\leq 1\\}$ the unit
ball in $\mathbb{R}^{n}$. By [48, Lemma 5.2], we can construct an
$\frac{1}{2}$-net $\mathcal{V}$ of $\mathbb{B}^{n}$ satisfying
$\log|\mathcal{V}|\leq C_{1}n$ for some constant $C_{1}>0$. Now, for any unit
vector $\bm{a}=(a_{1},a_{2},\ldots,a_{n})^{\top}\in\mathbb{B}^{n}$ and the
corresponding point $\bm{b}=(b_{1},b_{2},\ldots,b_{n})^{\top}\in\mathcal{V}$,
recalling (A.11) gives,

$\displaystyle\sum_{v=1}^{n}a_{v}\nabla\ell_{n,s}(\bm{\beta}_{s})_{v}=\sum_{v=1}^{n}a_{v}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)$
$\displaystyle=\sum_{v=1}^{n}b_{v}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)+\Delta,$
(A.13)

where

$\displaystyle\Delta$
$\displaystyle:=\sum_{v=1}^{n}(a_{v}-b_{v})\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)$
$\displaystyle\leq\sqrt{\sum_{v=1}^{n}(a_{v}-b_{v})^{2}\sum_{v=1}^{n}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)^{2}}$
$\displaystyle\leq\frac{1}{2}\sqrt{\sum_{v=1}^{n}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)^{2}}=\frac{1}{2}\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{2},$
(A.14)

by the Cauchy-Schwarz inequality and the fact that
$\|\bm{a}-\bm{b}\|\leq\frac{1}{2}$. Using the above in (A.13) gives,

$\displaystyle\sum_{v=1}^{n}a_{v}\nabla\ell_{n,s}(\bm{\beta}_{s})_{v}$
$\displaystyle\leq\sum_{v=1}^{n}b_{v}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)+\frac{1}{2}\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{2}.$
(A.15)

Maximizing over $\bm{a}\in\mathbb{B}^{n}$ and $\bm{b}\in\mathcal{V}$ on both
sides of (A.15) and rearranging the terms gives,

$\displaystyle\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{2}\leq
2\max_{\bm{b}\in\mathcal{V}}\sum_{v=1}^{n}b_{v}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right).$
(A.16)

For $\bm{e}=(u_{1},u_{2},\ldots,u_{s})\in[n]^{s}$ denote
$\bm{\beta}_{s,\bm{e}}=(\beta_{s,u_{1}},\beta_{s,u_{2}},\ldots,\beta_{s,u_{s}})^{\top}$.
Hence, by (A.16), Hoeffding’s inequality, and union bound,

$\displaystyle\mathbb{P}\left(\|\nabla\ell_{n,s}(\bm{\beta}_{s})\|_{2}^{2}>4C^{2}n^{s}\right)$
$\displaystyle\leq\sum_{\bm{b}\in\mathcal{V}}\mathbb{P}\left(\sum_{v=1}^{n}b_{v}\left(\mathbb{E}[d_{s}(v)]-d_{s}(v)\right)>2Cn^{\frac{s}{2}}\right)$
$\displaystyle=\sum_{\bm{b}\in\mathcal{V}}\mathbb{P}\left(\sum_{v=1}^{n}\sum_{\bm{e}\in{[n]\choose
s}:v\in\bm{e}}b_{v}\left\\{\frac{e^{\bm{\beta}_{s,\bm{e}}^{\top}\bm{1}}}{1+e^{\bm{\beta}_{s,\bm{e}}^{\top}\bm{1}}}-\bm{1}\\{\bm{e}\in
E(H_{n})\\}\right\\}>2Cn^{\frac{s}{2}}\right)$
$\displaystyle\leq\sum_{\bm{b}\in\mathcal{V}}e^{-\frac{2C^{2}n}{\sum_{v=1}^{n}b_{v}^{2}}}\leq
2^{C_{1}n}e^{-2C^{2}n}\rightarrow 0,$

by choosing $C>C_{1}$ to be large enough. This proves the first inequality in
(A.1). $\Box$

####  A.1.3. Proof of Lemma A.2

For $\bm{e}=(u_{1},u_{2},\ldots,u_{s})\in{[n]\choose s}$ and
$\bm{\beta}=(\beta_{1},\beta_{2},\ldots,\beta_{n})\in\mathbb{R}^{n}$, denote
$\bm{\beta}_{\bm{e}}=(\beta_{u_{1}},\beta_{u_{2}},\ldots,\beta_{u_{s}})^{\top}$.
Recalling (2.7) note that, the Hessian matrix $\nabla^{2}\ell_{n,s}$ can be
expressed as:

$\displaystyle\nabla^{2}\ell_{n,s}(\bm{\beta})=$
$\displaystyle\sum_{u,v\in[n]}\sum_{\bm{e}\in{[n]\choose
s}}\frac{e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}}}{(1+e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}})^{2}}\bm{\eta}_{u}\bm{\eta}_{v}^{\top}\bm{1}\\{u,v\in\bm{e}\\},$

where $\bm{\eta}_{u}$ is the $u$-th basis vector in $\mathbb{R}^{n}$, for
$1\leq u\leq n$.

Note that for $\bm{\beta}\in\mathbb{R}^{n}$ and
$\bm{\beta}_{s}\in\mathcal{B}(M)$,

$|\bm{1}^{\top}\bm{\beta}_{\bm{e}}|\leq s\|\bm{\beta}\|_{\infty}\leq
s\|\bm{\beta}_{s}\|_{\infty}+s\|\bm{\beta}_{s}-\bm{\beta}\|_{\infty}\leq
sM+s\|\bm{\beta}_{s}-\bm{\beta}\|_{2}.$

Hence,

$\displaystyle\frac{1}{4}e^{-s(M+\|\bm{\beta}_{s}-\bm{\beta}\|_{2})}\leq\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}})^{2}}\leq
1.$ (A.17)

For $\bm{x}\in\mathbb{R}^{n}$, consider

$\displaystyle\bm{x}^{\top}\nabla^{2}\ell_{n,s}(\bm{\beta})\bm{x}$
$\displaystyle=\sum_{u,v\in[n]}\sum_{\bm{e}\in{[n]\choose
s}}\frac{e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}}}{(1+e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}})^{2}}x_{u}x_{v}\bm{1}\\{u,v\in\bm{e}\\}$
$\displaystyle=\sum_{\bm{e}\in{[n]\choose
s}}\frac{e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}}}{(1+e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}})^{2}}\left(\sum_{u,v\in[n]}x_{u}x_{v}\bm{1}\\{u,v\in\bm{e}\\}\right)$
$\displaystyle=\sum_{\bm{e}\in{[n]\choose
s}}\frac{e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}}}{(1+e^{\bm{\beta}^{\top}_{\bm{e}}\bm{1}})^{2}}\left(\sum_{u\in[n]}x_{u}\bm{1}\\{u\in\bm{e}\\}\right)^{2}$
$\displaystyle\geq\frac{1}{4}e^{-s(M+\|\bm{\beta}_{s}-\bm{\beta}\|_{2})}\sum_{\bm{e}\in{[n]\choose
s}}\left(\sum_{u\in[n]}x_{u}\bm{1}\\{u\in\bm{e}\\}\right)^{2},$

where the last step uses (A.17). Observe that for any
$\bm{x}\in\mathbb{R}^{n}$

$\sum_{\bm{e}\in{[n]\choose
s}}\left(\sum_{u\in[n]}x_{u}\bm{1}\\{u\in\bm{e}\\}\right)^{2}=\bm{x}^{\top}\bm{L}\bm{x},$

where

$\bm{L}:=\sum_{u,v\in[n]}\sum_{\bm{e}\in{[n]\choose
s}}\bm{\eta}_{u}\bm{\eta}_{v}^{\top}\bm{1}\\{u,v\in\bm{e}\\}=\left({n-1\choose
s-1}-{n-2\choose s-2}\right)\bm{I}_{n}+{n-2\choose s-2}\bm{1}\bm{1}^{\top},$

where $\bm{I}_{n}$ is the $n\times n$ identity matrix and
$\bm{1}=(1,1,\ldots,1)^{\top}$. Similarly, we can show from (A.17) that for
any $\bm{x}\in\mathbb{R}^{n}$

$\bm{x}^{\top}\nabla^{2}\ell_{n,s}(\bm{\beta})\bm{x}\leq\bm{x}^{\top}\bm{L}\bm{x}.$

Thus, for $\bm{\beta}\in\mathbb{R}^{n}$

$\displaystyle\frac{1}{4}e^{-s(M+\|\bm{\beta}_{s}-\bm{\beta}\|_{2})}\lambda_{\min}\left(\bm{L}\right)\leq\lambda_{\min}(\nabla^{2}\ell_{n,s}(\bm{\beta}))\leq\lambda_{\max}(\nabla^{2}\ell_{n,s}(\bm{\beta}))\leq\lambda_{\max}\left(\bm{L}\right).$
(A.18)

Note that $\bm{L}$ is a circulant matrix with 2 non-zero eigenvalues:

${n-1\choose s-1}\quad\text{ and }\quad{n-1\choose s-1}-{n-2\choose s-2}.$

Hence, there exists constants $C_{1}^{\prime\prime},C_{2}^{\prime\prime}>0$
(depending on $r$), such that

${n-1\choose s-1}\leq
C_{1}^{\prime\prime}n^{s-1}\quad\mbox{and}\quad{n-1\choose s-1}-{n-2\choose
s-2}\geq C_{2}^{\prime\prime}\,n^{s-1}.$

This implies, from (A.18), that there exists constants
$C_{1}^{\prime},C_{2}^{\prime}>0$ (depending on $r$ and $M$) such that (A.2)
hold. The result in (A.3) from hold from (A.2) directly.

###  A.2. Convergence Rate in the $L_{\infty}$ Norm

Suppose $H_{n}\sim\mathsf{H}_{n,[r]}(n,\bm{B})$ as in the statement of Theorem
2.1. From the arguments in Appendix A.1 we know that, with probability
$1-o(1)$, the ML equations (2.7) have a bounded solution
$\hat{\bm{B}}=(\hat{\bm{\beta}}_{1},\hat{\bm{\beta}}_{2},\ldots,\hat{\bm{\beta}}_{r})$,
that is, $\nabla\ell_{n,s}(\hat{\bm{\beta}}_{s})=0$, for $2\leq s\leq r$, and
$\max_{2\leq s\leq r}\|\hat{\bm{\beta}}_{s}\|_{\infty}=O(1)$. To establish the
rate in $L_{\infty}$ norm we decompose the likelihood for the $s$-th layer as
follows.

$\displaystyle\ell_{n,s}(\bm{\beta})$
$\displaystyle=\sum_{\\{v_{1},v_{2},\ldots,v_{s}\\}\in{[n]\choose
s}}\log\left(1+e^{\beta_{v_{1}}+\ldots+\beta_{v_{s}}}\right)-\sum_{v=1}^{n}\beta_{v}d_{s}(v)$
$\displaystyle=\sum_{\bm{e}\in{[n]\choose
s}}\left\\{\log\left(1+e^{\bm{\beta}^{\top}_{e}\bm{1}}\right)-\bm{1}\\{\bm{e}\in
E(H_{n})\\}\bm{\beta}^{\top}_{e}\bm{1}\right\\}$
$\displaystyle=\ell^{+}_{n,s}(\beta_{u}|\bm{\beta}_{\bar{u}})+\ell^{-}_{n,s}(\bm{\beta}_{\bar{u}}),$
(A.19)

where
$\bm{\beta}_{\bar{u}}=(\beta_{1},\ldots,\beta_{u-1},\beta_{u+1},\ldots,\beta_{n})$,

$\displaystyle\ell^{+}_{n,s}(\beta_{u}|\bm{\beta}_{\bar{u}})$
$\displaystyle:=\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\left\\{\log\left(1+e^{\bm{\beta}^{\top}_{e}\bm{1}}\right)-\bm{1}\\{\bm{e}\in
E(H_{n})\\}\bm{\beta}^{\top}_{e}\bm{1}\right\\}$
$\displaystyle\ell^{-}_{n,s}(\bm{\beta}_{\bar{u}})$
$\displaystyle:=\sum_{\bm{e}\in{[n]\choose
s}:u\notin\bm{e}}\left\\{\log\left(1+e^{\bm{\beta}^{\top}_{e}\bm{1}}\right)-\bm{1}\\{\bm{e}\in
E(H_{n})\\}\bm{\beta}^{\top}_{e}\bm{1}\right\\}.$ (A.20)

Fix a constant $K>0$ and define

$\displaystyle\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}=\mathrm{arg}\min_{\bm{\beta}_{\bar{u}}:\|\bm{\beta}_{\bar{u}}-\bm{\beta}_{s,\bar{u}}\|_{2}\leq
K}\ell^{-}_{n,s}(\bm{\beta}_{\bar{u}}),$ (A.21)

where
$\bm{\beta}_{s,\bar{u}}=(\beta_{s,1},\ldots,\beta_{s,u-1},\beta_{s,u+1},\ldots,\beta_{s,n})$.
This is the leave-one-out ML estimate on the constrained set
$\|\bm{\beta}_{\bar{u}}-\bm{\beta}_{s,\bar{u}}\|_{2}\leq K$. First we bound
the difference (in $L_{2}$ norm) of constrained leave-one-out ML estimate
defined above and the leave-one-out true parameter $\bm{\beta}_{s,\bar{u}}$.

######  Lemma A.3.

Let $\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}$ and $\bm{\beta}_{s,\bar{u}}$ be as
defined above. Then, for $u\in[n]$, with probability $1-o(1)$,

$\displaystyle\max_{u\in[n]}\,\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}}\|_{2}^{2}\lesssim_{s,M,K}\frac{1}{n^{s-2}}.$
(A.22)

###### Proof.

To begin with, observe that

$\displaystyle\ell^{-}_{n,s}(\bm{\beta}_{s,\bar{u}})$
$\displaystyle\geq\ell^{-}_{n,s}(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}})$
$\displaystyle=\ell^{-}_{n,s}(\bm{\beta}_{s,\bar{u}})+(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}})^{\top}\nabla\ell^{-}_{n,s}(\bm{\beta}_{s,\bar{u}})+\frac{1}{2}(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}})^{\top}\nabla^{2}\ell^{-}_{n,s}(\tilde{\bm{\beta}})(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}}),$

where
$\|\tilde{\bm{\beta}}-\bm{\beta}_{s,\bar{u}}\|_{2}\leq\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}}\|_{2}\leq
K$. This implies,

$\displaystyle\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}}\|_{2}\cdot\|\nabla\ell^{-}_{n,s}(\bm{\beta}_{s,\bar{u}})\|_{2}$
$\displaystyle\geq-(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}})^{\top}\nabla\ell^{-}_{n,s}(\bm{\beta}_{s,\bar{u}})$
$\displaystyle\geq\frac{1}{2}(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}})^{\top}\nabla^{2}\ell^{-}_{n,s}(\tilde{\bm{\beta}})(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}}).$
(A.23)

By Lemma A.2,

$(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}})^{\top}\nabla^{2}\ell^{-}_{n,s}(\tilde{\bm{\beta}})(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}})\gtrsim_{s,M,K}\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\bm{\beta}_{s,\bar{u}}\|^{2}n^{s-1}.$

Also, by Lemma A.1,
$\|\nabla\ell^{-}_{n,s}(\bm{\beta}_{s,\bar{u}})\|^{2}_{2}\lesssim_{s,M,K}n^{s}$
with probability $1-O(\frac{1}{n^{2}})$. Plugging in the above inequalities in
(A.2), and using the union bound we get (A.22). ∎

Next, we bound the difference between the constrained leave-one-out ML
estimate $\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}$ and the (unconstrained) leave-
one-out ML estimate
$\hat{\bm{\beta}}_{s,\bar{u}}=(\hat{\beta}_{s,1},\ldots,\hat{\beta}_{s,u-1},\hat{\beta}_{s,u+1},\ldots,\hat{\beta}_{s,n})$.

######  Lemma A.4.

Let $\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}$ and $\hat{\bm{\beta}}_{s,\bar{u}}$
be as defined above. Then, with probability $1-o(1)$,

$\displaystyle\max_{u\in[n]}\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}\|^{2}_{2}$
$\displaystyle\lesssim_{s,M,K}\frac{1}{n^{s-1}}+\frac{\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty}}{n^{s-1}},$
(A.24)

where $X_{\bm{e}}=\bm{1}\\{\bm{e}\in E(H_{n})\\}$,
$\psi(x)=\frac{e^{x}}{1+e^{x}}$, and
$\bm{\beta}_{s,\bm{e}}=(\beta_{s,u_{1}},\beta_{s,u_{2}},\ldots,\beta_{s,u_{s}})^{\top}$,
for $\bm{e}=(u_{1},u_{2},\ldots,u_{s})\in[n]^{s}$.

###### Proof.

By the definition of $\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}$ (recall (A.21))

$\displaystyle\ell^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})$
$\displaystyle\geq\ell^{-}_{n,s}(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}})$
$\displaystyle=\ell^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})+(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}})^{\top}\nabla\ell^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})+(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}})^{\top}\nabla\ell^{-}_{n,s}(\bar{\bm{\beta}})(\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}),$

where
$\|\bar{\bm{\beta}}-\hat{\bm{\beta}}_{s,\bar{u}}\|_{2}\leq\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}\|_{2}$.
Note that
$\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}\|_{2}=O(1)$,
since $\|\hat{\bm{\beta}}_{s}\|_{\infty}=O(1)$ and
$\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}\|=O(1)$. Then by Lemma A.2,

$\displaystyle\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}\|^{2}_{2}\lesssim_{s,M,K}\frac{\|\nabla\ell^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})\|^{2}_{2}}{n^{2(s-1)}}.$
(A.25)

Since $\nabla\ell_{n,s}(\hat{\bm{\beta}}_{s})=0$, that is,
$\frac{\partial}{\partial\beta_{v}}\ell_{n,s}(\hat{\bm{\beta}}_{s})=0$, for
$v\in[n]$. Hence, we have from (A.2),

$\displaystyle\frac{\partial}{\partial\beta_{v}}\ell^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})=-\frac{\partial}{\partial\beta_{v}}\ell^{+}_{n,s}(\hat{\beta}_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})$
$\displaystyle=-\sum_{\bm{e}\in{[n]\choose
s}:\\{u,v\\}\in\bm{e}}\\{X_{\bm{e}}-\psi(\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}})\\},$

where $\psi(x):=\frac{e^{x}}{1+e^{x}}$. This implies,

$\displaystyle\|\nabla\ell^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})\|^{2}_{2}$
$\displaystyle=\sum_{v\in[n]\backslash\\{u\\}}\left(\sum_{\bm{e}\in{[n]\choose
s}:\\{u,v\\}\in\bm{e}}\\{X_{\bm{e}}-\psi(\hat{\bm{\beta}}^{\top}_{s,\bm{e}}1)\\}\right)^{2}$
$\displaystyle\lesssim\sum_{v\in[n]\backslash\\{u\\}}\left[\left(\sum_{\bm{e}\in{[n]\choose
s}:\\{u,v\\}\in\bm{e}}\\{X_{\bm{e}}-\psi(\bm{1}^{\top}\bm{\beta}_{s,\bm{e}})\\}\right)^{2}+\left(\sum_{\bm{e}\in{[n]\choose
s}:\\{u,v\\}\in\bm{e}}\\{\psi(\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}})-\psi(\bm{1}^{\top}\bm{\beta}_{s,\bm{e}})\\}\right)^{2}\right]$
$\displaystyle\lesssim_{r}\sum_{v\in[n]\backslash\\{u\\}}\left(\sum_{\bm{e}\in{[n]\choose
s}:\\{u,v\\}\in\bm{e}}\\{X_{\bm{e}}-\psi(1^{\top}\bm{\beta}_{s,\bm{e}})\\}\right)^{2}+n^{s-1}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty},$
(A.26)

using

$|\psi(\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}})-\psi(\bm{1}^{\top}\bm{\beta}_{s,\bm{e}})|\lesssim|\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}-\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}|\lesssim_{r}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty}.$

By (A.25) and (A.2), to prove the result in (A.24) it suffices show the
following holds with probability $1-o(1)$,

$\displaystyle\max_{1\leq u\leq
n}\sum_{v\in[n]\backslash\\{u\\}}\left(\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{\bm{1}\\{\bm{e}\in
E(H_{n})\\}-\psi(\bm{\beta}_{s,\bm{e}}^{\top}\bm{1})\right\\}\right)^{2}\lesssim
n^{s-1}.$ (A.27)

This is proved in Appendix A.2.1. ∎

We now apply the above lemmas to derive the bound in the $L_{\infty}$ norm. To
begin with note that since
$\ell_{n,s}(\hat{\bm{\beta}}_{s})=\min_{\bm{\beta}_{s}}\ell_{n,s}(\bm{\beta}_{s})$,

${\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})+{\ell}^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}})\geq\ell_{n,s}(\hat{\bm{\beta}}_{s})={\ell}^{+}_{n,s}(\hat{\beta}_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})+{\ell}^{-}_{n,s}(\hat{\bm{\beta}}_{s,\bar{u}}).$

The above inequality implies

$\displaystyle{\ell}^{+}_{n,s}$
$\displaystyle(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})$
$\displaystyle\geq{\ell}^{+}_{n,s}(\hat{\beta}_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})$
$\displaystyle={\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})+(\hat{\beta}_{s,u}-\beta_{s,u})\frac{\partial}{\partial\beta_{u}}{\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})+\frac{1}{2}(\hat{\beta}_{s,u}-\beta_{s,u})^{2}\frac{\partial^{2}}{\partial\beta_{u}^{2}}{\ell}^{+}_{n,s}(\tilde{\beta}|\hat{\bm{\beta}}_{s,\bar{u}}),$

where $\tilde{\beta}$ is a convex combination of $\hat{\beta}_{s,u}$ and
$\beta_{s,u}$. Therefore,

$\displaystyle(\hat{\beta}_{s,u}-\beta_{s,u})^{2}\leq\frac{4|\frac{\partial}{\partial\beta_{u}}{\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})|^{2}}{|\frac{\partial^{2}}{\partial\beta_{u}^{2}}{\ell}^{+}_{n,s}(\tilde{\beta}|\hat{\bm{\beta}}_{s,\bar{u}})|^{2}}.$
(A.28)

From arguments in Appendix A.1 we know that with probability $1-o(1)$,
$\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}\leq\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{2}\lesssim
1$. Note that for $\bm{\beta}\in\mathbb{R}^{n}$ such that
$\|\bm{\beta}-\bm{\beta}_{s}\|_{\infty}\lesssim 1$, we have
$\|\bm{\beta}\|_{\infty}\lesssim 1$ and hence,
$|\bm{1}^{\top}\bm{\beta}_{\bm{e}}|\lesssim 1$. This implies,
$\psi(\bm{1}^{\top}\bm{\beta}_{\bm{e},s})(1-\psi(\bm{1}^{\top}\bm{\beta}_{\bm{e},s}))\gtrsim
1$ and hence,

$\frac{\partial^{2}}{\partial\beta_{u}^{2}}{\ell}^{+}_{n,s}(\tilde{\beta}|\hat{\bm{\beta}}_{s,\bar{u}})=\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\psi(\bm{1}^{\top}\bar{\bm{\beta}}_{\bm{e},s})(1-\psi(\bm{1}^{\top}\bar{\bm{\beta}}_{\bm{e},s}))\gtrsim
n^{s-1},$

where
$\bar{\bm{\beta}}_{s}=(\hat{\beta}_{s,1},\ldots,\hat{\beta}_{s,u-1},\beta_{s,u},\hat{\beta}_{s,u+1},\ldots,\hat{\beta}_{s,n})^{\top}$.
Hence, (A.28) implies,

$\displaystyle(\hat{\beta}_{s,u}-\beta_{s,u})^{2}\lesssim\frac{|\frac{\partial}{\partial\beta_{u}}{\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})|^{2}}{n^{2s-2}}.$
(A.29)

Now, we bound
$|\frac{\partial}{\partial\beta_{u}}{\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})|^{2}$.
For this define

$\bar{\bm{\beta}}_{s}^{\circ}=([\hat{\bm{\beta}}_{s,\bar{u}}^{\circ}]_{1},\ldots,[\hat{\bm{\beta}}_{s,\bar{u}}^{\circ}]_{u-1},\beta_{s,u},[\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}]_{u+1},\ldots,[\hat{\bm{\beta}}_{s,\bar{u}}^{\circ}]_{n})^{\top}.$

Then we have

$\displaystyle\left|\frac{\partial}{\partial\beta_{u}}{\ell}^{+}_{n,s}(\beta_{s,u}|\hat{\bm{\beta}}_{s,\bar{u}})\right|$
$\displaystyle=\Bigg{|}\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\\{X_{\bm{e}}-\psi(\bm{1}^{\top}\bar{\bm{\beta}}_{\bm{e},s})\\}\Bigg{|}\leq
T_{1}(u)+T_{2}(u)+T_{3}(u),$ (A.30)

where

$\displaystyle T_{1}(u)$ $\displaystyle:=\Bigg{|}\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\\{X_{\bm{e}}-\psi(1^{\top}\bm{\beta}_{\bm{e},s})\\}\Bigg{|},\quad
T_{2}(u):=\Bigg{|}\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\\{\psi(1^{\top}\bar{\bm{\beta}}^{\circ}_{\bm{e},s})-\psi(1^{\top}\bm{\beta}_{\bm{e},s})\\}\Bigg{|},$

and

$\displaystyle T_{3}(u)$ $\displaystyle:=\Bigg{|}\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\\{\psi(1^{\top}\bar{\bm{\beta}}_{\bm{e},s}^{\circ})-\psi(1^{\top}\bar{\bm{\beta}}_{\bm{e},s})\\}\Bigg{|}.$

Note that since $\\{X_{\bm{e}}\\}_{\bm{e}\in{[n]\choose s}}$ are independent
and bounded random variables, using Hoeffding’s inequality and union bound
gives

$\max_{u\in[n]}T_{1}(u)\lesssim\sqrt{n^{s-1}\log n},$

with probability $1-o(1)$. Next, we consider $T_{2}(u)$. By Lemma A.3, with
probability $1-o(1)$,

$\displaystyle\max_{u\in[n]}\,T_{2}(u)\lesssim\max_{u\in[n]}\,\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\Bigg{\\{}\sum_{v\in\bm{e}}|\beta_{s,v}-[\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}]_{v}|\Bigg{\\}}$
$\displaystyle=\max_{u\in[n]}\,\sum_{v\in[n]\backslash\\{u\\}}n^{s-2}|\beta_{s,v}-[\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}]_{v}|$
$\displaystyle\lesssim
n^{s-\frac{3}{2}}\max_{u\in[n]}\,\|\bm{\beta}_{s,\bar{u}}-\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}\|_{2}\lesssim\sqrt{n^{s-1}}.$

A similar argument shows that, with probability $1-o(1)$,
$\max_{u\in[n]}\,T_{3}(u)\lesssim
n^{s-\frac{3}{2}}\|\hat{\bm{\beta}}_{s,\bar{u}}-\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}\|_{2}$.
Combining the bounds on $T_{1}$, $T_{2}$ and $T_{3}$ with (A.29) and (A.30)
gives, with probability $1-o(1)$,

$\displaystyle\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}$
$\displaystyle\lesssim\sqrt{\frac{\log
n}{n^{s-1}}}+\frac{\max_{u\in[n]}\,\|\hat{\bm{\beta}}_{s,\bar{u}}-\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}\|_{2}}{\sqrt{n}}.$
(A.31)

Applying (A.31) in (A.24) now gives, with probability $1-o(1)$,

$\displaystyle\max_{u\in[n]}\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}\|_{2}$
$\displaystyle\lesssim_{s,M,K}\sqrt{\frac{1}{n^{s-1}}}+\frac{\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}}{\sqrt{n^{s-1}}}$
$\displaystyle\lesssim_{s,M,K}\sqrt{\frac{1}{n^{s-1}}}+\frac{\max_{u\in[n]}\|\hat{\bm{\beta}}^{\circ}_{s,\bar{u}}-\hat{\bm{\beta}}_{s,\bar{u}}\|_{2}}{\sqrt{n^{s}}}\lesssim\sqrt{\frac{1}{n^{s-1}}}.$

Using this inequality with (A.31) gives, with probability $1-o(1)$,

$\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}\lesssim_{s,M,K}\sqrt{\frac{\log
n}{n^{s-1}}},$

establishing the desired bound in (2.8).

####  A.2.1. Proof of (A.27)

###### Proof.

Denote by $\mathbb{B}^{n-1}=\\{\bm{x}\in\mathbb{R}^{n-1}:\|\bm{x}\|_{2}\leq
1\\}$. Using [48, Lemma 5.2], we can construct an $\frac{1}{2}$-net
$\mathcal{V}_{1}$ of $\mathbb{B}^{n-1}$ satisfying $\log|\mathcal{V}_{1}|\leq
C_{2}n$ for some constant $C_{2}>0$. Now, for any $u\in[n]$, any unit vector
$\tilde{\bm{a}}=(\tilde{a}_{1},\tilde{a}_{2},\ldots,\tilde{a}_{n-1})^{\top}\in\mathbb{B}^{n-1}$
and the corresponding point
$\tilde{\bm{b}}=(\tilde{b}_{1},\tilde{b}_{2},\ldots,\tilde{b}_{n-1})^{\top}\in\mathcal{V}_{1}$,

$\displaystyle\sum_{v\in[n]\backslash\\{u\\}}\tilde{a}_{v}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}$
$\displaystyle=\sum_{v\in[n]\backslash\\{u\\}}\tilde{b}_{v}\left\\{\sum_{\bm{e}\in{[n]\choose
s},u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}+\Delta_{u},$
(A.32)

where

$\Delta_{u}:=\sum_{v\in[n]\backslash\\{u\\}}(\tilde{a}_{i}-\tilde{b}_{i})\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}.$

Proceeding as in (A.1.2), for all $u\in[n]$, we can show

$|\Delta_{u}|\leq\frac{1}{2}\sqrt{\sum_{v\in[n]\backslash\\{u\\}}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}^{2}}.$

Maximizing over $\tilde{\bm{a}}\in\mathbb{B}^{n-1}$ and
$\tilde{\bm{b}}\in\mathcal{V}_{1}$ on both sides of (A.2.1) we get

$\sqrt{\sum_{v\in[n]\backslash\\{u\\}}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}^{2}}\leq
2\max_{\tilde{\bm{b}}\in\mathcal{V}_{1}}\sum_{v\in[n]\backslash\\{u\\}}\tilde{b}_{v}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}.$

As the above relation holds for all $u\in[n]$ we get

$\displaystyle\sqrt{\max_{u\in[n]}\sum_{v\in[n]\backslash\\{u\\}}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}^{2}}$
$\displaystyle\leq
2\,\max_{u\in[n]}\max_{\tilde{\bm{b}}\in\mathcal{V}_{1}}\sum_{v\in[n]\backslash\\{u\\}}\tilde{b}_{v}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}.$
(A.33)

Hence, using (A.2.1), Hoeffding Inequality and union bound we get

$\displaystyle\mathbb{P}\left(\max_{u\in[n]}\sum_{v\in[n]\backslash\\{u\\}}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}^{2}>4K^{2}n^{s-1}\right)$
$\displaystyle\leq\sum_{u=1}^{n}\sum_{\tilde{\bm{b}}\in\mathcal{V}_{1}}\mathbb{P}\left(\sum_{v\in[n]\backslash\\{u\\}}\tilde{b}_{v}\left\\{\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\left\\{X_{\bm{e}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{\bm{e}}}}\right\\}\right\\}>2Kn^{\frac{s-1}{2}}\right)$
$\displaystyle\leq\sum_{u=1}^{n}\sum_{\tilde{\bm{b}}\in\mathcal{V}_{1}}e^{-\frac{2K^{2}n}{\sum_{v=1}^{n-1}\tilde{b}^{2}_{v}}}$
$\displaystyle\leq n\;2^{C_{2}n}e^{-2K^{2}n}\rightarrow 0,$

for $K$ large enough. ∎

##  Appendix B Estimation Lower Bounds: Proof of Theorem 2.2

The lower bound in the $L_{2}$ norm is proved in Appendix B.1 and the lower
bound in the $L_{\infty}$ norm is proved Appendix B.2.

###  B.1. Estimation Lower Bound in the $L_{2}$ Norm: Proof of (2.10)

For $\bm{\gamma}\in\mathbb{R}^{n}$, denote the probability distribution of
$s$-uniform model $\mathsf{H}_{s}(n,\bm{\gamma})$ by
$\mathbb{P}_{\bm{\gamma}}$. To prove the result (2.10) recall Fano’s lemma:

######  Theorem B.1 ([47, Theorem 2.5]).

Suppose there exists
$\bm{\gamma}^{(0)},\cdots,\bm{\gamma}^{(J)}\in\mathbb{R}^{n}$, with
$\|\bm{\gamma}^{(j)}\|\in\mathcal{B}_{M}$ for all $0\leq j\leq J$, such that

  1. $(1)$

$\|\bm{\gamma}^{(j)}-\bm{\gamma}^{(\ell)}\|_{2}\geq 2s\,>0$ for all $0\leq
j\neq\ell\leq J$,

  2. $(2)$

$\frac{1}{J}\sum_{j=1}^{J}\mathsf{KL}(\mathbb{P}_{\bm{\gamma}^{(j)}},\mathbb{P}_{\bm{\gamma}^{(0)}})\leq\alpha\log
J$,

where $\alpha\in(0,1/8)$. Then

$\displaystyle\min_{\hat{\bm{\gamma}}}\max_{\bm{\gamma}}\mathbb{P}\left(\|\hat{\bm{\gamma}}-\bm{\gamma}\|_{2}\geq
s\right)\geq\frac{\sqrt{J}}{\sqrt{J}+1}\left(1-2\alpha-\sqrt{\frac{2\alpha}{\log
J}}\right).$ (B.1)

To obtain $\bm{\gamma}^{(0)},\ldots,\bm{\gamma}^{(J)}\in\mathbb{R}^{n}$ as in
the above lemma we will invoke the Gilbert-Varshamov Theorem (see [47, Lemma
2.9]) which states that there exists
$\bm{\omega}^{(0)},\ldots,\bm{\omega}^{(J)}\in\\{0,1\\}^{n}$, with $J\geq
2^{n/8}$, such that $\bm{\omega}^{(0)}=(0,\cdots,0)^{\top}$ and

$\displaystyle\|\bm{\omega}^{(j)}-\bm{\omega}^{(\ell)}\|_{1}\geq\frac{n}{8},$
(B.2)

for all $0\leq j\neq\ell\leq J$. For
$\bm{\omega}^{(0)},\ldots,\bm{\omega}^{(J)}\in\\{0,1\\}^{n}$ as above and
$\delta\in(0,1/8)$ define,

$\bm{\gamma}^{(j)}=\varepsilon_{n}\bm{\omega}^{(j)},\quad\text{ for }0\leq
j\leq J,$

where $\varepsilon_{n}=16Cn^{-\frac{s-1}{2}}$, with $C=C(\delta,s)\,>0$ a
constant depending on $\delta$ and $s$ to be chosen later. By (B.2) we have

$\|\bm{\gamma}^{(j)}-\bm{\gamma}^{(\ell)}\|_{2}\geq 2Cn^{-\frac{s-2}{2}}.$

Now,

$\displaystyle\mathsf{KL}(\mathbb{P}_{\bm{\gamma}^{(j)}},\mathbb{P}_{\bm{\gamma}^{(0)}})$
$\displaystyle=\sum_{t=0}^{s}{\|\bm{\omega}^{(j)}\|_{1}\choose
t}{n-\|\bm{\omega}^{(j)}\|_{1}\choose
s-t}\Big{\\{}\psi\left(t\varepsilon_{n}\right)\log\left(2\psi\left(t\varepsilon_{n}\right)\right)+\left(1-\psi\left(t\varepsilon_{n}\right)\right)\log\left(2\left(1-\psi\left(t\varepsilon_{n}\right)\right)\right)\Big{\\}},$

where $\psi(x)=\frac{e^{x}}{1+e^{x}}$ is the logistic function defined in
Lemma A.4. By a Taylor expansion,

for small enough $x>0$,

$\psi(x)\log(2\psi(x))+(1-\psi(x))\log(2(1-\psi(x)))=\frac{x^{2}}{8}+O(x^{3}).$

Hence, using ${\|\bm{\omega}^{(j)}\|_{1}\choose
t}{n-\|\bm{\omega}^{(j)}\|_{1}\choose s-t}\lesssim_{s}n^{s}$ gives

$\frac{1}{J}\sum_{j=1}^{J}\mathsf{KL}(\mathbb{P}_{\bm{\gamma}^{(j)}},\mathbb{P}_{\bm{\gamma}^{(0)}})\lesssim_{s}n^{s}\varepsilon^{2}_{n}\lesssim_{s}C^{2}n\leq\delta\log
J,$

for $C=C(\delta,s)$ chosen appropriately. Hence, applying Theorem B.1 and
taking $J\rightarrow\infty$ in (B.1) gives

$\min_{\hat{\bm{\gamma}}}\max_{\bm{\gamma}}\mathbb{P}\left(\|\hat{\bm{\gamma}}-\bm{\gamma}\|_{2}\geq
Cn^{-\frac{s-2}{2}}\right)\geq 1-2\delta.$

This completes the proof of (2.10).

###  B.2. Estimation Lower Bound in $L_{\infty}$ Norm: Proof of (2.11)

Choose 2 points $\bm{\gamma},\bm{\gamma}^{\prime}\in\mathbb{R}^{n}$ as
follows: $\gamma=\bm{0}$ and
$\bm{\gamma}^{\prime}=(\gamma^{\prime}_{1},\gamma^{\prime}_{2},\ldots,\gamma^{\prime}_{n})$
such that

$\gamma_{i}^{\prime}=\begin{cases}Cn^{-\frac{s-1}{2}}&\mbox{if $i=1$,}\\\
0&\mbox{otherwise, }\end{cases}$

for some constant $C>0$ to be chosen later. Clearly,
$\|\bm{\gamma}-\bm{\gamma}^{\prime}\|_{\infty}=Cn^{-\frac{s-1}{2}}:=\varepsilon$.
Denote the probability distribution of the $s$-uniform models
$\mathsf{H}_{s}(n,\bm{\gamma})$ and $\mathsf{H}_{s}(n,\bm{\gamma}^{\prime})$
by $\mathbb{P}_{\bm{\gamma}}$ and $\mathbb{P}_{\bm{\gamma}^{\prime}}$,
respectively. Observe that

$\displaystyle\mathsf{KL}(\mathbb{P}_{\bm{\gamma}},\mathbb{P}_{\bm{\gamma}^{\prime}})$
$\displaystyle=\frac{1}{2}\sum_{\bm{e}\in{[n]\choose
s}:1\in\bm{e}}\left[\log\left\\{\frac{(1+e^{\varepsilon})}{2\,e^{\varepsilon}}\right\\}+\log\left\\{\frac{1}{2}(1+e^{\varepsilon})\right\\}\right].$
(B.3)

By Taylor’s theorem, we get

$\log\left\\{\frac{(1+e^{\varepsilon})}{2\,e^{\varepsilon}}\right\\}+\log\left\\{\frac{1}{2}(1+e^{\varepsilon})\right\\}=\varepsilon^{2}+O(\varepsilon^{3})=\frac{C^{2}}{n^{s-1}}+O\left(\frac{1}{n^{\frac{3}{2}(s-1)}}\right).$

Hence, from (B.3),

$\mathsf{KL}(\mathbb{P}_{\bm{\gamma}},\mathbb{P}_{\bm{\gamma}^{\prime}})=L_{s}C^{2}+o(1),$

for some constant $L_{s}$ depending on $s$. This implies, by Le Cam’s two-
point method (see [47, Theorem 2.2]), for $\delta\in(0,1)$,

$\displaystyle\min_{\hat{\bm{\gamma}}}\max_{\bm{\gamma}}\mathbb{P}\left(\|\hat{\bm{\gamma}}-\bm{\gamma}\|_{\infty}\geq
C\sqrt{\frac{1}{n^{s-1}}}\right)\geq\max\left\\{e^{-\frac{1}{4}L_{s}C^{2}},\frac{1}{2}-\frac{1}{2}\sqrt{\frac{L_{s}C^{2}}{2}}\right\\}\geq
1-\delta,$

by choosing $C$, depending on $\delta$ and $s$, small enough.

##  Appendix C Proof of Theorem 2.3 and Theorem 2.4

We begin with the proof of Theorem 2.3 in Section C.1. The proof of Theorem
2.4 is given in Section C.2.

###  C.1. Proof of Theorem 2.3

Recall that, for $2\leq s\leq r$,
$\bm{d}_{s}=(d_{s}(1),d_{s}(2),\ldots,d_{s}(n))^{\top}$ is the vector of
$s$-degrees. The first step in the proof of Theorem 2.3 is to derive a
linearization of $\hat{\bm{\beta}}_{s}$ in terms of the $s$-degrees as in
Proposition C.1 below. The proof is given in Appendix C.1.1.

######  Proposition C.1.

Fix $2\leq s\leq r$. Then under the assumptions of Theorem 2.3, with
probability $1-o(1)$ as $n\rightarrow\infty$,

$\displaystyle\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}-\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])\|_{\infty}=O\left(\frac{\log
n}{n^{s-1}}\right),$ (C.1)

where $\bm{\Sigma}_{n,s}=((\sigma_{s}(u,v)))_{u,v\in[n]}$ is a $n\times n$
matrix with

$\sigma_{s}(u,v):=\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\frac{e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}})^{2}}\text{
and }\sigma_{s}(u,u):=\sigma_{s}(u)^{2}=\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\frac{e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}})^{2}},$
(C.2)

where $\sigma_{s}(u)^{2}$ is also defined in (2.12).

Next, define the matrix $\bm{\Gamma}_{n,s}=((\gamma_{s}(u,v)))_{u,v\in[n]}$ as
follows:

$\gamma_{s}(u,v):=\frac{\bm{1}\\{u=v\\}}{\sigma_{s}(u)^{2}}.$ (C.3)

The following lemma shows that it is possible to replace the matrix
$\bm{\Sigma}_{n,s}^{-1}$ in (C.1) with the matrix $\bm{\Gamma}_{n,s}$
asymptotically. The proof of the lemma is given in Appendix C.1.2.

######  Lemma C.1.

Suppose $\bm{\Sigma}_{n,s}$ and $\bm{\Gamma}_{n,s}$ be as defined in (C.2) and
(C.3), respectively. Then under the assumptions of Theorem 2.3,

$\displaystyle\|\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1}\|_{\infty}\leq
O\left(\frac{1}{n^{s}}\right),$ (C.4)

where $\|\bm{A}\|_{\infty}=\max_{u,v\in[n]}|a_{u,v}|$ for a matrix
$\bm{A}=((a_{u,v}))_{u,v\in[n]}$. Furthermore,

$\displaystyle\|\operatorname{Cov}[(\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1})(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])]\|_{\infty}\leq\|\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1}\|_{\infty}+O\left(\frac{1}{n^{s}}\right).$
(C.5)

To complete the proof of Theorem 2.3, consider $J_{s}\in{[n]\choose a_{s}}$,
for $a_{s}\geq 1$ fixed. Proposition C.1 and Lemma C.1 combined implies,

$\|[(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}}-[\bm{\Gamma}_{n,s}(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])]_{J_{s}}\|_{\infty}=O\left(\frac{\log
n}{n^{s-1}}\right),$

with probability $1-o(1)$. Now, recall from the statement of Theorem 2.3 that
$\bm{D}_{s}=\mathrm{diag}\,(\sigma_{s}(v))_{v\in[n]}$. From (C.2) observe that
$\max_{v\in[n]}\sigma_{s}(v)^{2}\asymp n^{s-1}$, since
$\|\bm{\beta}_{s}\|_{\infty}\leq M=O(1)$. Hence,

$\|[\bm{D}_{s}(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}}-[\bm{D}_{s}(\bm{\Gamma}_{n,s}(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])]_{J_{s}}\|_{\infty}=O\left(\frac{\log
n}{\sqrt{n^{s-1}}}\right).$

Note that for $v\in J_{s}$,

$\displaystyle\sigma_{s}(v)[\bm{\Gamma}_{n,s}(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s})]]_{v}$
$\displaystyle=\frac{d_{s}(v)-\mathbb{E}[d_{s}(v)]}{\sigma_{s}(v)}.$ (C.6)

Therefore, from (C.6),

$\displaystyle[\bm{D}_{s}]_{J_{s}}([(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}})$
$\displaystyle=\left(\left(\frac{d_{s}(v)-\mathbb{E}[d_{s}(v)]}{\sqrt{\operatorname{Var}[d_{s}(v)]}}\right)\right)_{v\in
J_{s}}+O\left(\frac{\log n}{\sqrt{n}}\right)$
$\displaystyle\stackrel{{\scriptstyle
D}}{{\to}}\mathcal{N}_{a_{s}}(\bm{0},\bm{I}),$

using the central limit theorem for sums of independent bounded random
variables. Since $\hat{\bm{\beta}}_{s}$ are independent across $2\leq s\leq
r$, the result in (2.13) follows.

####  C.1.1. Proof of Proposition C.1

For $2\leq s\leq r$ and $\bm{e}=(u_{1},u_{2},\ldots,u_{s})\in{[n]\choose s}$,
let
$\bm{\beta}_{s,\bm{e}}=(\beta_{s,u_{1}},\beta_{s,u_{2}},\ldots,\beta_{s,u_{s}})^{\top}$
and
$\hat{\bm{\beta}}_{s,\bm{e}}=(\hat{\beta}_{s,u_{1}},\hat{\beta}_{s,u_{2}},\ldots,\hat{\beta}_{s,u_{s}})^{\top}$.
Moreover, $\bm{1}$ will denote the vector of ones in the appropriate
dimension. To begin with, (2.7) and (A.12) gives, for $v\in[n]$,

$\displaystyle d_{s}(v)-\mathbb{E}[d_{s}(v)]=\sum_{\bm{e}\in{[n]\choose
s}:v\in\bm{e}}\left\\{\frac{e^{\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}}}{1+e^{\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}\right\\}.$
(C.7)

Note that for $\bm{e}\in{[n]\choose s}$, by a Taylor expansion,

$\frac{e^{\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}}}{1+e^{\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}{1+e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}=\frac{e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}})^{2}}\left(\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}-\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}\right)+\mathcal{R}_{s,\bm{e}},$

where

$|\mathcal{R}_{s,\bm{e}}|\leq\frac{1}{2}\left|\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}-\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}\right|^{2}\lesssim_{r}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty}.$
(C.8)

Then, from (C.7),

$d_{s}(v)-\mathbb{E}[d_{s}(v)]=\left[\bm{\Sigma}_{n,s}(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})\right]_{v}+R_{v,s},$
(C.9)

where $R_{v,s}=\sum_{\bm{e}\in{[n]\choose
s}:v\in\bm{e}}\mathcal{R}_{s,\bm{e}}$. From (C.9), we have

$\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}=\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])+\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s},$
(C.10)

where $\bm{R}_{n,s}=(R_{1,s},R_{2,s},\ldots,R_{n,s})^{\top}$. Note that from
(C.8),

$\displaystyle|R_{v,s}|\leq\sum_{\bm{e}\in{[n]\choose
s}:v\in\bm{e}}|\mathcal{R}_{s,\bm{e}}|\lesssim_{r}n^{s-1}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty}.$
(C.11)

To bound $\|\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s}\|_{\infty}$, note that for
$v\in[n]$,

$|[\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s}]_{v}|\leq|[\bm{\Gamma}_{n,s}\bm{R}_{n,s}]_{v}|+|[(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})\bm{R}_{n,s}]_{v}|.$
(C.12)

Observe that

$[\bm{\Gamma}_{n,s}\bm{R}_{n,s}]_{v}=\frac{R_{v,s}}{\sigma_{s}(v)^{2}}.$

Using $\sigma_{s}(v)^{2}\asymp n^{s-1}$, (C.11), and (2.8) gives,

$\displaystyle|[\bm{\Gamma}_{n,s}\bm{R}_{n,s}]_{v}|\lesssim\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty}=O\left(\frac{\log
n}{\;n^{s-1}}\right),$

with probability $1-o(1)$. Further, by Lemma C.1, (C.11), and (2.8),

$\displaystyle|[(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})\bm{R}_{n,s}]_{v}|\leq\|(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})\|_{\infty}\times
n\|\bm{R}_{n,s}\|_{\infty}$
$\displaystyle\lesssim\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{2}_{\infty}$
$\displaystyle\leq O\left(\frac{\log n}{\;n^{s-1}}\right),$

with probability $1-o(1)$. Hence, by (C.10) and (C.12) the result in (C.1)
follows. $\Box$

####  C.1.2. Proof of Lemma C.1

###### Proof of (C.4).

Denote
$\bm{\Delta}_{n,s}=\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1}=((\delta_{s}(u,v)))_{u,v\in[n]}$,
$\bm{Z}_{n,s}=\bm{I}_{n}-\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s}=((z_{s}(u,v)))_{u,v\in[n]}$,
and
$\bm{\Theta}_{n,s}=\bm{\Gamma}_{n,s}\bm{Z}_{n,s}=((\theta_{s}(u,v)))_{u,v\in[n]}$.
Then

$\bm{\Delta}_{n,s}=(\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1})(\bm{I}_{n}-\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s})-\bm{\Gamma}_{n,s}(\bm{I}_{n}-\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s})=\bm{\Delta}_{n,s}\bm{Z}_{n,s}-\bm{\Theta}_{n,s}.$

Hence, for $u,v\in[n]$,

$\displaystyle\delta_{s}(u,v)$
$\displaystyle=\sum_{w=1}^{n}\delta_{s}(u,w)z_{s}(w,v)-\theta_{s}(u,v)$
$\displaystyle=\sum_{w=1}^{n}\delta_{s}(u,w)\left\\{\bm{1}\\{w=v\\}-\sum_{b=1}^{n}\sigma_{s}(w,b)\gamma_{s}(b,v)\right\\}-\theta_{s}(u,v)$
$\displaystyle=\sum_{w=1}^{n}\delta_{s}(u,w)\left\\{\bm{1}\\{w=v\\}-\sum_{b=1}^{n}\sigma_{s}(w,b)\frac{\bm{1}\\{v=b\\}}{\sigma_{s}(v)^{2}}\right\\}-\theta_{s}(u,v)$
$\displaystyle=\sum_{w=1}^{n}\delta_{s}(u,w)\left\\{\bm{1}\\{w=v\\}-\frac{\sigma_{s}(w,v)}{\sigma_{s}(v)^{2}}\right\\}-\theta_{s}(u,v)$
$\displaystyle=-\sum_{w=1}^{n}\delta_{s}(u,w)\left\\{\bm{1}\\{w\neq
v\\}\frac{\sigma_{s}(w,v)}{\sigma_{s}(v)^{2}}\right\\}-\theta_{s}(u,v),$
(C.13)

since
$\sum_{b\in[n]\backslash\\{w\\}}\sigma_{s}(w,b)=\sigma_{s}(w,w)=\sigma_{s}(w)^{2}$.
The following lemma bounds the maximum norm of
$\bm{\Theta}_{n,s}=\bm{\Gamma}_{n,s}\bm{Z}_{n,s}=((\theta_{s}(u,v)))_{u,v\in[n]}$.

######  Lemma C.2.

For $u,v,w\in[n]$,

$\displaystyle\max\left\\{|\theta_{s}(u,v)|,|\theta_{s}(u,v)-\theta_{s}(v,w)|\right\\}\lesssim\frac{\sigma_{s,\max}}{\sigma_{s,\min}^{2}n^{2}},$
(C.14)

where $\sigma_{s,\min}:=\min_{1\leq u<v\leq n}\sigma_{s}(u,v)$ and
$\sigma_{s,\max}:=\max_{1\leq u<v\leq n}\sigma_{s}(u,v)$.

###### Proof.

Note that
$\bm{\Theta}_{n,s}=\bm{\Gamma}_{n,s}\bm{Z}_{n,s}=\bm{\Gamma}_{n,s}-\bm{\Gamma}_{n,s}\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s}$.
This means for $u,v\in[n]$,

$\displaystyle\theta_{s}(u,v)=\gamma_{s}(u,v)-\sum_{x,y\in[n]}\gamma_{s}(u,x)\sigma_{s}(x,y)\gamma_{s}(y,v).$
(C.15)

Then recalling the definition of $\gamma_{s}(u,v)$ from (C.3) gives,

$\displaystyle\sum_{x,y\in[n]}\gamma_{s}(u,x)\sigma_{s}(x,y)\gamma_{s}(y,v)$
$\displaystyle=\sum_{x,y\in[n]}\frac{\bm{1}\\{u=x\\}\bm{1}\\{y=v\\}\sigma_{s}(x,y)}{\sigma_{s}(u)^{2}\sigma_{s}(v)^{2}}$
$\displaystyle=\frac{\sigma_{s}(u,v)}{\sigma_{s}(u)^{2}\sigma_{s}(v)^{2}}.$

Hence, from (C.3) and (C.15),

$|\theta_{s}(u,v)|=\left|\frac{\sigma_{s}(u,v)\bm{1}\\{u\neq
v\\}}{\sigma_{s}(u)^{2}\sigma_{s}(v)^{2}}\right|\lesssim\frac{\sigma_{s,\max}}{\sigma_{s,\min}^{2}n^{2}}.$

This completes the proof of (C.14). ∎

Now, for $u\in[n]$, let $\overline{m},\underline{m}\in[n]$ be such that

$\delta_{s}(u,\overline{m})=\max_{w\in[n]}\delta_{s}(u,w)\quad\text{ and
}\quad\delta_{s}(u,\underline{m})=\min_{w\in[n]}\delta_{s}(u,w).$

The following lemma gives bounds on $\delta_{s}(u,\underline{m})$ and
$\delta_{s}(u,\overline{m})$.

######  Lemma C.3.

For $u\in[n]$,

$\displaystyle\sum_{w=1}^{n}\delta_{s}(u,w)\sigma_{s}(w,u)=0.$

This implies, $\delta_{s}(u,\overline{m})\geq 0$ and
$\delta_{s}(u,\underline{m})\leq 0$.

###### Proof.

Note that $\sum_{w=1}^{n}\delta_{s}(u,w)\sigma_{s}(w,u)$ is the $u$-th
diagonal element of the matrix
$\bm{\Delta}_{n,s}\bm{\Sigma}_{n,s}=\bm{\Gamma}_{n,s}\bm{\Sigma}_{n,s}-\bm{I}_{n}$
(recall that $\bm{\Delta}_{n,s}=\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1}$).
Note that the $u$-th diagonal element of $\bm{\Gamma}_{n,s}\bm{\Sigma}_{n,s}$
is given by

$\displaystyle\sum_{w\in[n]}\gamma_{s}(u,w)\sigma_{s}(w,u)$
$\displaystyle=\sum_{w\in[n]}\frac{\bm{1}\\{u=w\\}}{\sigma_{s}(u)^{2}}\sigma_{s}(w,u)=1,$

since $\sigma_{s}(u,u)=\sigma_{s}(u)^{2}$. Hence, $u$-th diagonal element of
$\bm{\Delta}_{n,s}\bm{\Sigma}_{n,s}$ is zero. ∎

Now, recalling (C.13) note that

$\displaystyle\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m})+(\theta_{s}(u,\overline{m})-\theta_{s}(u,\underline{m}))$
$\displaystyle=\sum_{w=1}^{n}\delta_{s}(u,w)\left\\{\frac{\bm{1}\\{w\neq\underline{m}\\}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}-\frac{\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\right\\}$
$\displaystyle=\sum_{w=1}^{n}(\delta_{s}(u,w)-\delta_{s}(u,\underline{m}))\left\\{\frac{\bm{1}\\{w\neq\underline{m}\\}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}-\frac{\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\right\\},$
(C.16)

since
$\sum_{w\in[n]\backslash\\{\underline{m}\\}}\sigma_{s}(w,\underline{m})=\sigma_{s}(\underline{m})^{2}$
and
$\sum_{w\in[n]\backslash\\{\overline{m}\\}}\sigma_{s}(w,\overline{m})=\sigma_{s}(\overline{m})^{2}$.
Define

$\Omega:=\left\\{w\in[n]:\frac{\bm{1}\\{w\neq\underline{m}\\}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}\geq\frac{\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\right\\},$

and $\lambda:=|\Omega|$. Then, we have

$\displaystyle\sum_{w\in\Omega}(\delta_{s}(u,w)-\delta_{s}(u,\underline{m}))\left\\{\frac{\bm{1}\\{w\neq\underline{m}\\}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}-\frac{\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\right\\}$
$\displaystyle\leq(\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m}))\left\\{\frac{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}-\frac{\sum_{w\in\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\right\\}.$
(C.17)

Note that

$\frac{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}=\frac{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})}{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})+\sum_{w\in[n]\backslash(\Omega\bigcup\underline{m})}\sigma_{s}(w,\underline{m})}=\frac{1}{1+\frac{\sum_{w\in[n]\backslash(\Omega\bigcup\underline{m})}\sigma_{s}(w,\underline{m})}{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})}},$

since $\underline{m}\notin\Omega$. Now, observe that

$\frac{\sum_{w\in[n]\backslash(\Omega\bigcup\underline{m})}\sigma_{s}(w,\underline{m})}{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})}\geq\frac{(n-\lambda-1)\sigma_{s,\min}}{\lambda\sigma_{s,\max}}$

This implies,

$\displaystyle\frac{\sum_{w\in\Omega}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}\leq\frac{\lambda\sigma_{s,\max}}{\lambda\sigma_{s,\max}+(n-\lambda-1)\sigma_{s,\min}}.$
(C.18)

Similarly,

$\frac{\sum_{w\in\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}=\frac{\sum_{w\in\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sum_{w\in[n]}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}=\frac{1}{1+\frac{\sum_{w\in[n]\backslash\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{\underline{m}})}{\sum_{w\in\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{\underline{m}})}}$

Therefore, since $\overline{m}\in\Omega$,

$\frac{\sum_{w\in[n]\backslash\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sum_{w\in\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}\leq\frac{(n-\lambda)\sigma_{s,\max}}{(\lambda-1)\sigma_{s,\min}}.$

Hence,

$\displaystyle\frac{\sum_{w\in\Omega}\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\geq\frac{(\lambda-1)\sigma_{s,\min}}{(\lambda-1)\sigma_{s,\min}+(n-\lambda)\sigma_{s,\max}}.$
(C.19)

Applying (C.18) and (C.19) in (C.1.2) gives,

$\displaystyle\sum_{w\in\Omega}(\delta_{s}(u,w)-\delta_{s}(u,\underline{m}))\left\\{\frac{\bm{1}\\{w\neq\underline{m}\\}\sigma_{s}(w,\underline{m})}{\sigma_{s}(\underline{m})^{2}}-\frac{\bm{1}\\{w\neq\overline{m}\\}\sigma_{s}(w,\overline{m})}{\sigma_{s}(\overline{m})^{2}}\right\\}$
$\displaystyle\leq(\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m}))f(\lambda),$
(C.20)

where

$f(\lambda)=\frac{\lambda\sigma_{s,\max}}{\lambda\sigma_{s,\max}+(n-1-\lambda)\sigma_{s,\min}}-\frac{(\lambda-1)\sigma_{s,\min}}{(\lambda-1)\sigma_{s,\min}+(n-\lambda)\sigma_{s,\max}}.$

Note that $f(\lambda)$ attains maximum at $\lambda=n/2$ over
$\lambda\in(1,n-1)$ and

$f(n/2)=\frac{n\sigma_{s,\max}-(n-2)\sigma_{s,\min}}{n\sigma_{s,\max}+(n-2)\sigma_{s,\min}}.$

Therefore, from Lemma C.2, (C.1.2), there exists a constant $C>0$ such that
(C.1.2),

$\displaystyle\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m})$
$\displaystyle\leq\frac{n\sigma_{s,\max}-(n-2)\sigma_{s,\min}}{n\sigma_{s,\max}+(n-2)\sigma_{s,\min}}(\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m}))+\frac{C\sigma_{s,\max}}{\sigma_{s,\min}^{2}n^{2}}.$

This implies,

$\displaystyle\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m})$
$\displaystyle\leq\frac{C\sigma_{s,\max}(n\sigma_{s,\max}+(n-2)\sigma_{s,\min})}{2(n-2)\sigma_{s,\min}^{3}n^{2}}\lesssim\frac{\sigma_{s,\max}^{2}}{\sigma_{s,\min}^{3}n^{2}}.$

Hence, from Lemma C.3,

$\displaystyle\max_{1\leq w\leq n}|\delta_{s}(u,w)|$
$\displaystyle\leq\delta_{s}(u,\overline{m})-\delta_{s}(u,\underline{m})\leq\frac{\sigma_{s,\max}^{2}}{\sigma_{s,\min}^{3}n^{2}}\lesssim\frac{1}{n^{s}},$

since $\sigma_{s,\min}\asymp n^{s-2}$ and $\sigma_{s,\max}\asymp n^{s-2}$,
using $\|\bm{\beta}_{s}\|_{\infty}\leq M=O(1)$. This completes the proof of
(C.4). ∎

###### Proof of (C.5).

Define

$\bm{U}_{n,s}=\operatorname{Cov}[(\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1})(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])]=\operatorname{Cov}[\bm{\Delta}_{n,s}(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])],$

since $\bm{\Delta}_{n,s}=\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1}$. Observe
that

$\displaystyle\bm{U}_{n,s}$
$\displaystyle=\bm{\Delta}_{n,s}\mathbb{E}[(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])(\bm{d}_{s}-\mathbb{E}[\bm{d}_{s}])^{\top}]\bm{\Delta}_{n,s}^{\top}$
$\displaystyle=\bm{\Delta}_{n,s}\bm{\Sigma}_{n,s}\bm{\Delta}_{n,s}^{\top}$
$\displaystyle=(\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1})-\bm{\Gamma}_{n,s}(\bm{I}_{n}-\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s})$
$\displaystyle=(\bm{\Gamma}_{n,s}-\bm{\Sigma}_{n,s}^{-1})-\bm{\Theta}_{n,s},$
(C.21)

since $\bm{\Theta}_{n,s}=\bm{\Gamma}_{n,s}\bm{Z}_{n,s}$ and
$\bm{Z}_{n,s}=\bm{I}_{n}-\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s}$. By Lemma C.2,

$\|\bm{\Theta}_{n,s}\|_{\infty}\lesssim\frac{\sigma_{s,\max}}{\sigma_{s,\min}^{2}n^{2}}\lesssim\frac{1}{n^{s}},$
(C.22)

since $\sigma_{s,\min}\asymp n^{s-2}$ and $\sigma_{s,\max}\asymp n^{s-2}$,
using $\|\bm{\beta}_{s}\|_{\infty}\leq M=O(1)$. By (C.4), (C.1.2), and (C.22)
the result in (C.5) follows. ∎

###  C.2. Proof of Theorem 2.4

For $\bm{x}=(x_{1},x_{2},\ldots,x_{n})\in\mathbb{R}^{n}$ and $u\in[n]$ define
the function

$g_{u}(\bm{x})=\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\frac{e^{\bm{1}^{\top}\bm{x}_{\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{x}_{\bm{e}}})^{2}},$

where $\bm{x}_{\bm{e}}=(x_{u_{1}},x_{u_{2}},\ldots,x_{u_{s}})$ for
$\bm{e}=(u_{1},u_{2},\ldots,u_{s})$. Then recalling (2.12) and (2.14),
$\sigma_{s}(v)^{2}=g_{v}(\bm{\beta}_{s})$ and
$\hat{\sigma}_{s}(v)^{2}=g_{v}(\hat{\bm{\beta}}_{s})$. Hence, by a Taylor
expansion,

$\displaystyle|\hat{\sigma}_{s}(v)^{2}-\sigma_{s}(v)^{2}|=|g_{v}(\hat{\bm{\beta}}_{s})-g_{v}(\bm{\beta}_{s})|$
$\displaystyle=\left|\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\left\\{\frac{e^{\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}}}{(1+e^{\bm{1}^{\top}\hat{\bm{\beta}}_{s,\bm{e}}})^{2}}-\frac{e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{\beta}_{s,\bm{e}}})^{2}}\right\\}\right|$
$\displaystyle\lesssim_{r}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|_{\infty}.$
(C.23)

Recalling the definition of $J_{s}=\\{v_{s,1},\ldots,v_{s,a_{s}}\\}$ from
Theorem 2.4, this implies

$\displaystyle\sum_{s=2}^{r}([(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}})^{\top}[\hat{\bm{D}}_{s}^{2}]_{J_{s}}([(\hat{\bm{\beta}}_{s}-\bm{\beta}_{s})]_{J_{s}})$
$\displaystyle=\sum_{s=2}^{r}\sum_{j=1}^{a_{s}}\hat{\sigma}_{s}(v_{a_{j}})^{2}(\hat{\beta}_{s,v_{a_{j}}}-\beta_{s,v_{a_{j}}})^{2}$
$\displaystyle=\sum_{s=2}^{r}\sum_{j=1}^{a_{s}}\sigma_{s}(v_{a_{j}})^{2}(\hat{\beta}_{s,v_{a_{j}}}-\beta_{s,v_{a_{j}}})^{2}+\sum_{s=2}^{r}\sum_{j=1}^{a_{s}}(\hat{\sigma}_{s}(v_{a_{j}})^{2}-\sigma_{s}(v_{a_{j}})^{2})(\hat{\beta}_{s,v_{a_{j}}}-\beta_{s,v_{a_{j}}})^{2}$
$\displaystyle\stackrel{{\scriptstyle
D}}{{\to}}\chi^{2}_{\sum_{s=2}^{r}a_{s}}+o_{P}(1),$

by Theorem 2.3, (C.2) and (2.8). This completes the proof of (2.15).

##  Appendix D Proofs of Theorems 3.1 and 3.2

###  D.1. Proof of Theorem 3.1

Suppose $H_{n}\sim\mathsf{H}_{n,s}(n,\bm{\gamma})$ for $\bm{\gamma}$ as in
(3.1). Let $\bm{\Sigma}_{n,s}$ be as defined in (C.2) with $\bm{\beta}_{s}$
replaced by $\bm{\gamma}=(\gamma_{1},\gamma_{2},\ldots,\gamma_{n})^{\top}$.
Then $\nabla^{2}\ell_{n,s}(\bm{\gamma})=\bm{\Sigma}_{n,s}$. Then by a Taylor
expansion,

$\displaystyle\ell_{n,s}(\bm{\gamma})-\ell_{n,s}(\hat{\bm{\beta}}_{s})$
$\displaystyle=(\hat{\bm{\beta}}_{s}-\bm{\gamma})^{\top}\nabla\ell_{n,s}(\bm{\gamma})+\frac{1}{2}(\hat{\bm{\beta}}_{s}-\bm{\gamma})^{\top}\bm{\Sigma}_{n,s}(\hat{\bm{\beta}}_{s}-\bm{\gamma})+\mathcal{T}_{n,s},$
(D.1)

where

$\displaystyle\mathcal{T}_{n,s}=\mathcal{T}_{n,s}^{(1)}+\mathcal{T}_{n,s}^{(2)}+\mathcal{T}_{n,s}^{(3)},$
(D.2)

with

$\displaystyle\mathcal{T}_{n,s}^{(1)}$
$\displaystyle:=\frac{1}{6}\sum_{u=1}^{n}\frac{\partial^{3}\ell_{n,s}(\bm{\gamma}+\theta(\hat{\bm{\beta}}_{s}-\bm{\gamma}))}{\partial(\beta_{s,u})^{3}}(\hat{\beta}_{s,u}-\gamma_{u})^{3},$
$\displaystyle\mathcal{T}_{n,s}^{(2)}$ $\displaystyle:=\frac{1}{3}\sum_{1\leq
u\neq v\leq
n}\frac{\partial^{3}\ell_{n,s}(\bm{\gamma}+\theta(\hat{\bm{\beta}}_{s}-\bm{\gamma}))}{\partial(\beta_{s,u})^{2}\partial\beta_{s,v}}(\hat{\beta}_{s,u}-\gamma_{u})^{2}(\hat{\beta}_{s,v}-\gamma_{v}),$
$\displaystyle\mathcal{T}_{n,s}^{(3)}$ $\displaystyle:=\frac{1}{6}\sum_{1\leq
u\neq v\neq w\leq
n}\frac{\partial^{3}\ell_{n,s}(\bm{\gamma}+\theta(\hat{\bm{\beta}}_{s}-\bm{\gamma}))}{\partial\beta_{s,u}\partial\beta_{s,v}\partial\beta_{s,w}}(\hat{\beta}_{s,u}-\gamma_{u})(\hat{\beta}_{s,v}-\gamma_{v})(\hat{\beta}_{s,w}-\gamma_{w}),$

for some $\theta\in(0,1)$.

Now, by arguments as in (C.10) it follows that

$\hat{\bm{\beta}}_{s}-\bm{\gamma}=\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])+\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s},$
(D.3)

where $\bm{R}_{n,s}$ is as defined in (C.9) and (C.10) with $\bm{\beta}_{s}$
replaced by $\bm{\gamma}$. Using this and noting that
$-\nabla\ell_{n,s}(\bm{\gamma})=\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}]$,

$\displaystyle(\hat{\bm{\beta}}_{s}-\bm{\gamma})^{\top}\nabla\ell_{n,s}(\bm{\gamma})$
$\displaystyle=(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Sigma}_{n,s}^{-1}\nabla\ell_{n,s}(\bm{\gamma})+\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}\nabla\ell_{n,s}(\bm{\gamma})$
$\displaystyle=-(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])-\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}]).$
(D.4)

Similarly, using (D.3),

$\displaystyle(\hat{\bm{\beta}}_{s}-\bm{\gamma})^{\top}\bm{\Sigma}_{n,s}(\hat{\bm{\beta}}_{s}-\bm{\gamma})$
$\displaystyle=(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])+2\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])+\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s}.$
(D.5)

Combining (D.1), (D.1), and (D.1) gives,

$\displaystyle\ell_{n,s}(\hat{\bm{\beta}}_{s})-\ell_{n,s}(\bm{\gamma})$
$\displaystyle=-\frac{1}{2}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])+\frac{1}{2}\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s}+\mathcal{T}_{n,s}.$
(D.6)

We begin by showing that
$\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s}=o_{P}(\sqrt{n})$. To
this end, (C.11) and $\sigma_{s}(u)^{2}\asymp n^{s-1}$ gives,

$\displaystyle\left|\bm{R}_{n,s}^{\top}\bm{\Gamma}_{n,s}\bm{R}_{n,s}\right|=\left|\sum_{u=1}^{n}\frac{R_{s,u}^{2}}{\sigma_{s}(u)^{2}}\right|\lesssim
n^{s}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{4}_{\infty}\lesssim\frac{\log^{2}n}{n^{s-2}},$
(D.7)

with probability $1-o(1)$ by (2.8). Next, observe that

$\displaystyle\left|\bm{R}_{n,s}^{\top}\bm{\Delta}_{n,s}\bm{R}_{n,s}\right|\leq
n\|\bm{\Delta}_{n,s}\bm{R}_{n,s}\|_{\infty}\cdot\|\bm{R}_{n,s}\|_{\infty}$
$\displaystyle\leq
n^{2}\|\bm{R}_{n,s}\|_{\infty}^{2}\cdot\|\bm{\Delta}_{n,s}\|_{\infty}$
$\displaystyle\lesssim
n^{s}\|\hat{\bm{\beta}}_{s}-\bm{\beta}_{s}\|^{4}_{\infty}$
$\displaystyle\lesssim\frac{\log^{2}n}{n^{s-2}},$ (D.8)

with probability $1-o(1)$ by (2.8). Combining (D.7) and (D.8) it follows that
with probability $1-o(1)$,

$\displaystyle\left|\bm{R}_{n,s}^{\top}\bm{\Sigma}_{n,s}^{-1}\bm{R}_{n,s}\right|\leq\left|\bm{R}_{n,s}^{\top}\bm{\Gamma}_{n,s}\bm{R}_{n,s}\right|+\left|\bm{R}_{n,s}^{\top}\bm{\Delta}_{n,s}\bm{R}_{n,s}\right|\lesssim\frac{\log^{2}n}{n^{s-2}}=o_{P}(\sqrt{n}).$
(D.9)

This implies, the second term in the RHS of (D.6) does not contribute to the
CLT of the log-likelihood ratio $\log\Lambda_{n,s}$.

Next, we show that the third term in the RHS of (D.6) is $o_{P}(\sqrt{n})$,
hence, it also does not contribute to the CLT of $\log\Lambda_{n,s}$.

######  Lemma D.1.

Suppose $s\geq 3$ and $\bm{\gamma}\in\mathcal{B}(M)$. Then
$\mathcal{T}_{n,s}=o_{P}(\sqrt{n})$.

###### Proof.

Define
$\tilde{\bm{\beta}}_{s}=\bm{\gamma}+\theta(\hat{\bm{\beta}}_{s}-\bm{\gamma})$,
for $\theta\in(0,1)$. Then recalling (D.2) observe that

$\displaystyle\mathcal{T}_{n,s}^{(1)}$
$\displaystyle=\frac{1}{6}\sum_{u=1}^{n}\left[\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\frac{e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}}(1-e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}})}{(1+e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}})^{3}}\right](\hat{\beta}_{s,u}-\gamma_{u})^{3},$
$\displaystyle\mathcal{T}_{n,s}^{(2)}$ $\displaystyle=\frac{1}{3}\sum_{1\leq
u\neq v\leq n}\left[\sum_{\bm{e}\in{[n]\choose
s}:u,v\in\bm{e}}\frac{e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}}(1-e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}})}{(1+e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}})^{3}}\right](\hat{\beta}_{s,u}-\gamma_{u})^{2}(\hat{\beta}_{s,v}-\gamma_{v}),$
$\displaystyle\mathcal{T}_{n,s}^{(3)}$ $\displaystyle:=\frac{1}{6}\sum_{1\leq
u\neq v\neq w\leq n}\left[\sum_{\bm{e}\in{[n]\choose
s}:u,v,w\in\bm{e}}\frac{e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}}(1-e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}})}{(1+e^{\bm{1}^{\top}\tilde{\bm{\beta}}_{s,\bm{e}}})^{3}}\right](\hat{\beta}_{s,u}-\gamma_{u})(\hat{\beta}_{s,v}-\gamma_{v})(\hat{\beta}_{s,w}-\gamma_{w}),$

where
$\tilde{\bm{\beta}}_{s,\bm{e}}=(\tilde{\beta}_{s,u_{1}},\tilde{\beta}_{s,u_{2}},\ldots,\tilde{\beta}_{s,u_{s}})^{\top}$,
for $\bm{e}=(u_{1},u_{2},\ldots,u_{s})$. Since $\bm{\gamma}\in\mathcal{B}_{M}$
and $\|\hat{\bm{\beta}}_{s}-\bm{\gamma}\|_{\infty}\lesssim_{s,M}\sqrt{\log
n/n^{s-1}}$ with probability $1-o(1)$,
$\hat{\bm{\beta}}_{s}\in\mathcal{B}_{2M}$ for large $n$ with probability
$1-o(1)$. This implies,

$\mathcal{T}_{n,s}^{(1)}\lesssim_{M}n^{s}\|\hat{\bm{\beta}}_{s}-\bm{\gamma}\|^{3}_{\infty}\lesssim_{M,s}\sqrt{\frac{(\log
n)^{3}}{n^{s-3}}}=o_{P}(\sqrt{n}),$ (D.10)

for $s\geq 3$. Similarly, we can show that for $s\geq 3$,
$\mathcal{T}_{n,s}^{(2)}=o_{P}(\sqrt{n})$ and
$\mathcal{T}_{n,s}^{(3)}=o_{P}(\sqrt{n})$. This completes the proof of the
Lemma D.1. ∎

######  Remark D.1.

Note that Lemma D.1 assumes that $s\geq 3$. This is because when $s=2$ (that
is, the graph case), the proof of Lemma D.1 gives the bound
$\mathcal{T}_{n,2}=O(\mathrm{polygon}(n)/\sqrt{n})$ which is not
$o_{P}(\sqrt{n})$ (see (D.10)). Nevertheless, it follows from the proof of
Theorem 1 (a) in Yan et al. [55], where the asymptotic null distribution of
the LR test for the graph $\bm{\beta}$-model was derived, that the result in
Lemma D.1 also holds when $s=2$, that is, $\mathcal{T}_{n,2}=o_{P}(\sqrt{n})$.
For this one has to expand
$\ell_{n,s}(\hat{\bm{\beta}}_{s})-\ell_{n,s}(\bm{\gamma})$ up to the fourth
order term, and show that the third order term is $o_{P}(\sqrt{n})$ at the
true parameter value and the fourth order term is $o_{P}(\sqrt{n})$ at an
intermediate point. For $s\geq 3$, the third order term at an intermediate
point is $o_{P}(\sqrt{n})$, hence, we do not have to consider the fourth order
term.

Now, recall the definition of $\log\Lambda_{n,s}$ from (3.2). Then by Lemma
D.1 and (D.6)

$\displaystyle\frac{2\log\Lambda_{n,s}-n}{\sqrt{2n}}=\frac{(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])-n}{\sqrt{2n}}+o_{P}(1).$
(D.11)

By the following lemma we can replace $\bm{\Sigma}_{n,s}^{-1}$ with
$\bm{\Gamma}_{n,s}$ in the RHS above. The proof of the lemma is given in
Appendix D.1.1.

######  Lemma D.2.

For $L>0$,

$\mathbb{P}\left(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])>L\right)\lesssim\frac{1}{L^{2}}.$

This implies,
$(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])$
is bounded in probability.

By Lemma D.2 and recalling (C.3),

$\displaystyle\frac{(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Sigma}_{n,s}^{-1}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])}{\sqrt{2n}}$
$\displaystyle=\frac{(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}\bm{\Gamma}_{n,s}(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])}{\sqrt{2n}}+o_{P}\left(1\right)$
$\displaystyle=\frac{1}{\sqrt{2n}}\sum_{u=1}^{n}\frac{(d_{s}(u)-\mathbb{E}_{\bm{\gamma}}[d_{s}(u)])^{2}}{\sigma_{s}(u)^{2}}+o_{P}\left(1\right).$
(D.12)

Proposition D.1 establishes the asymptotic normality of the leading term in
the RHS above. The proof is given in Appendix D.1.2. $\Box$

######  Proposition D.1.

Under the assumption of Theorem 3.1,

$\displaystyle\frac{1}{\sqrt{2n}}\left\\{\sum_{u=1}^{n}\frac{(d_{s}(u)-\mathbb{E}_{\bm{\gamma}}[d_{s}(u)])^{2}}{\sigma_{s}(u)^{2}}-n\right\\}\stackrel{{\scriptstyle
D}}{{\to}}\mathcal{N}(0,1).$ (D.13)

The result in (3.3) now follows from (D.11), (D.1), and Proposition D.1.

####  D.1.1. Proof of Lemma D.2

To begin with note that

$\displaystyle\mathbb{E}_{\bm{\gamma}}[(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])]$
$\displaystyle=\operatorname{tr}(\mathbb{E}_{\bm{\gamma}}[(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}](\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s}))$
$\displaystyle=\operatorname{tr}(\bm{I}_{n}-\bm{\Sigma}_{n,s}\bm{\Gamma}_{n,s})$
$\displaystyle=n-\sum_{u,v\in[n]}\sigma_{s}(u,v)\gamma_{s}(u,v)$
$\displaystyle=n-\sum_{u,v\in[n]}\sigma_{s}(u,v)\frac{\bm{1}\\{u=v\\}}{\sigma_{s}(u)^{2}}=0.$

Next, we will show that
$\operatorname{Var}_{\bm{\gamma}}[(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])]=O(1)$.
The result in Lemma D.2 then follows by Chebyshev’s inequality. Recall that
$\bm{\Delta}_{n,s}:=\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s}$. We shall denote
the entries of $\bm{\Delta}_{n,s}$ by $((\delta_{u,v}))$ for $u,v\in[n]$. Then

$(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])=\sum_{u,v\in[n]}\delta_{u,v}(d_{s}(u)-\mathbb{E}_{\bm{\gamma}}[d_{s}(u)])(d_{s}(v)-\mathbb{E}_{\bm{\gamma}}[d_{s}(v)]).$

Define $\bar{d}_{s}(u):=d_{s}(u)-\mathbb{E}_{\bm{\gamma}}[d_{s}(u)]$, for
$u\in[n]$. Then

$\displaystyle\operatorname{Var}_{\bm{\gamma}}[(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])^{\top}(\bm{\Sigma}_{n,s}^{-1}-\bm{\Gamma}_{n,s})(\bm{d}_{s}-\mathbb{E}_{\bm{\gamma}}[\bm{d}_{s}])]$
$\displaystyle=\sum_{u,v,u^{\prime},v^{\prime}\in[n]}\delta_{u,v}\delta_{u^{\prime},v^{\prime}}\operatorname{Cov}_{\bm{\gamma}}[\bar{d}_{s}(u)\bar{d}_{s}(v),\bar{d}_{s}(u^{\prime})\bar{d}_{s}(v^{\prime})].$
(D.14)

To analyze the RHS of (D.1.1) we consider the following 4 cases.

  * Case 1:

$u=v=u^{\prime}=v^{\prime}$. In this case we have

$\operatorname{Cov}_{\bm{\gamma}}[\bar{d}_{s}(u)\bar{d}_{s}(v),\bar{d}_{s}(u^{\prime})\bar{d}_{s}(v^{\prime})]=\operatorname{Var}_{\bm{\gamma}}[\bar{d}_{s}(u)^{2}].$

For $\bm{e}\in{[n]\choose s}$, denote $X_{\bm{e}}:=\bm{1}\\{\bm{e}\in
E(H_{n})\\}$ and $\bar{X}_{\bm{e}}:=\bm{1}\\{\bm{e}\in
E(H_{n})\\}-\mathbb{E}[\bm{1}\\{\bm{e}\in E(H_{n})\\}]$. Since
$\\{\bar{X}_{\bm{e}}:\bm{e}\in{[n]\choose s}\\}$ are independent and have zero
mean,
$\\{\bar{X}_{\bm{e}}\bar{X}_{\bm{e}^{\prime}}:\bm{e},\bm{e}^{\prime}\in{[n]\choose
s}\\}$ are pairwise uncorrelated. Hence,

$\displaystyle\operatorname{Var}_{\bm{\gamma}}[\bar{d}_{s}(u)^{2}]$
$\displaystyle=\operatorname{Var}_{\bm{\gamma}}\left[\sum_{\bm{e},\bm{e}^{\prime}\in{[n]\choose
s}:u\in\bm{e}\bigcap\bm{e}^{\prime}}\bar{X}_{\bm{e}}\bar{X}_{\bm{e}^{\prime}}\right]$
$\displaystyle=\sum_{\bm{e},\bm{e}^{\prime}\in{[n]\choose
s}:u\in\bm{e}\bigcap\bm{e}^{\prime}}\operatorname{Var}_{\bm{\gamma}}\left[\bar{X}_{\bm{e}}\bar{X}_{\bm{e}^{\prime}}\right]$
$\displaystyle=\sum_{\bm{e}\in{[n]\choose
s}:u\in\bm{e}}\operatorname{Var}_{\bm{\gamma}}[\bar{X}^{2}_{\bm{e}}]+\sum_{\bm{e}\neq\bm{e}^{\prime}\in{[n]\choose
s}:u\in\bm{e}\cap\bm{e}^{\prime}}\operatorname{Var}_{\bm{\gamma}}[\bar{X}_{\bm{e}}]\operatorname{Var}_{\bm{\gamma}}[\bar{X}_{\bm{e}^{\prime}}].$
(D.15)

Since $\|\bm{\gamma}\|_{\infty}\leq M$,

$\operatorname{Var}_{\bm{\gamma}}[\bar{X}_{\bm{e}}]=\operatorname{Var}_{\bm{\gamma}}[X_{\bm{e}}]=\frac{e^{\bm{1}^{\top}\gamma_{\bm{e}}}}{(1+e^{\bm{1}^{\top}\bm{\gamma}_{\bm{e}}})}\asymp_{M}1,$

where
$\gamma_{\bm{e}}=(\gamma_{u_{1}},\gamma_{u_{2}},\ldots,\gamma_{u_{s}})^{\top}$,
for $\bm{e}=(u_{1},u_{2},\ldots,u_{s})$. Similarly,
$\operatorname{Var}_{\bm{\gamma}}[\bar{X}^{2}_{\bm{e}}]\asymp_{M}1$. Hence,
(Case 1:) implies that

$\operatorname{Var}_{\bm{\gamma}}[\bar{d}_{s}(u)^{2}]\lesssim_{M}n^{2s-2}.$

  * Case 2:

$u\neq v=u^{\prime}=v^{\prime}$. Observe that

$\displaystyle\operatorname{Cov}_{\bm{\gamma}}[\bar{d}_{s}(u)\bar{d}_{s}(v),\bar{d}_{s}(u^{\prime})\bar{d}_{s}(v^{\prime})]$
$\displaystyle=\operatorname{Cov}_{\bm{\gamma}}[\bar{d}_{s}(u)\bar{d}_{s}(v),\bar{d}_{s}(v)^{2}]$
$\displaystyle=\sum_{\begin{subarray}{c}\bm{e}_{1},\bm{e}_{2},\bm{e}_{3},\bm{e}_{4}\in{[n]\choose
s}\\\
u\in\bm{e}_{1},v\in\bm{e}_{1}\cap\bm{e}_{2}\cap\bm{e}_{3}\end{subarray}}\left\\{\mathbb{E}_{\bm{\gamma}}[\bar{X}_{\bm{e}_{1}}\bar{X}_{\bm{e}_{2}}\bar{X}_{\bm{e}_{3}}\bar{X}_{\bm{e}_{4}}]-\mathbb{E}_{\bm{\gamma}}[\bar{X}_{\bm{e}_{1}}\bar{X}_{\bm{e}_{2}}]\mathbb{E}_{\bm{\gamma}}[\bar{X}_{\bm{e}_{3}}\bar{X}_{\bm{e}_{4}}]\right\\}.$

Note that the non-zero contributions in the RHS above come from the terms when
$\bm{e}_{i}=\bm{e}_{j}$ and $\bm{e}_{k}=\bm{e}_{\ell}$ for
$i,j,k,\ell\in\\{1,\ldots,4\\}$. Hence,

$\displaystyle\operatorname{Cov}_{\bm{\gamma}}[\bar{d}_{s}(u)\bar{d}_{s}(v),\bar{d}_{s}(v)^{2}]$
$\displaystyle=\sum_{\bm{e}\in{[n]\choose
s},u,v\in\bm{e}}\left(\mathbb{E}_{\bm{\gamma}}[\bar{X}^{4}_{\bm{e}}]-(\mathbb{E}_{\bm{\gamma}}[\bar{X}_{\bm{e}}^{2}])^{2}\right)+2\sum_{\begin{subarray}{c}\bm{e}_{1}\neq\bm{e}_{2}\in{[n]\choose
s}\\\
u,v\in\bm{e}_{1},v\in\bm{e}_{2}\end{subarray}}\mathbb{E}_{\bm{\gamma}}[\bar{X}^{2}_{\bm{e}_{1}}]\mathbb{E}[\bar{X}^{2}_{\bm{e}_{2}}]$
$\displaystyle\lesssim_{M}n^{2s-3},$

since $\mathbb{E}_{\bm{\gamma}}[\bar{X}^{4}_{\bm{e}}]\asymp_{M}1$ and