Identification and Estimation of Network Models with Nonparametric Unobserved Heterogeneity Thanks: The orignal JMP version is available here . Andrei Zeleneev Abstract Homophily based on observables is widespread in networks. Therefore, homophily based on unobservables (fixed effects) is also likely to be an important determinant of the interaction outcomes. Failing to properly account for latent homophily (and other complex forms of unobserved heterogeneity) can result in inconsistent estimators and misleading policy implications. To address this concern, we consider a network model with nonparametric unobserved heterogeneity, leaving the role of the fixed effects unspecified. We argue that the interaction outcomes can be used to identify agents with the same values of the fixed effects. The variation in the observed characteristics of such agents allows us to identify the effects of the covariates, while controlling for the fixed effects. Building on these ideas, we construct several estimators of the parameters of interest and characterize their large sample properties. Numerical experiments illustrate the usefulness of the suggested approaches and support the asymptotic theory. Keywords: network data, homophily, fixed effects 1 Introduction Unobserved heterogeneity is pervasive in economics. The importance of accounting for unobserved heterogeneity is well recognized in microeconometrics, in general, as well as in the network context, in particular. For example, since 1 , estimating a linear regression with additive (two-way) fixed effects has become a standard approach to analyzing interaction data. Originally employed to account for workers and firms fixed effects in the wage regression context, this technique has become a standard tool to control for two-sided unobserved heterogeneity and decompose it into agent specific effects. 1 1 1 For example, recent applications to employer-employee matched data feature 18 ; 38 ; 60 among others. The numerous applications of this approach also include the analysis of students-teachers ( 37 ; 56 ; 57 ) , patients-hospitals ( 27 ) , firms-banks ( 4 ) , and residents-counties matched data ( 22 ) . Since the seminal work of 5 , the importance of controlling for exporters and importers fixed effects has also been well acknowledged in the context of the international trade network, including nonlinear settings of 58 and 39 . 34 stresses the importance of accounting for agents’ degree heterogeneity (captured by the additive fixed effects) in network formation models. While the additive fixed effects framework is commonly employed to control for unobservables in networks, it is not flexible enough to capture more complicated forms of unobserved heterogeneity, which are likely to appear in many settings. This concern can be vividly illustrated in the context of estimation of homophily effects, one of the main focuses of the empirical network analysis. 2 2 2 The term homophily typically refers to the tendency of individuals to assortatively match based on their characteristics. For example, individuals tend to form social connections based on gender, race, age, education level, and other socioeconomic characteristics. Similarly, countries that share a border, have the same legal system, language or currency, are more likely to have higher trade volumes. Since homophily (assortative matching) based on observables is widespread in networks (e.g., 50 ), homophily based on unobservables (fixed effects) is also likely to be an important determinant of the interaction outcomes. Since observed and unobserved characteristics (i.e., covariates and fixed effects) are typically correlated, the presence of latent homophily significantly complicates identification of the homophily effects associated with the observables (e.g., 59 ). Failing to properly account for homophily based on unobservables (and other complex forms of unobserved heterogeneity, in general) is likely to result in inconsistent estimators and misleading policy implications. To address the concern discussed above, we consider a dyadic network model with a flexible (nonparametric) form of unobserved heterogeneity, where the outcome of the interaction between agents i and j is given by \displaystyle Y_{ij}=F(W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j}))+\varepsilon_{ij}. (1.1) Here, W_{ij} is a p\times 1 vector of pair-specific observed covariates, \beta_{0}\in\mathbb{R}^{p} is the parameter of interest, \xi_{i} and \xi_{j} are unobserved fixed effects, and \varepsilon_{ij} is an idiosyncratic error. The fixed effects are allowed to interact via the coupling function g(\cdot,\cdot) , which is treated as \emph{unknown} . Importantly, we do not require g(\cdot,\cdot) to have any particular structure and do not specify the dimension of \xi . Finally, F(\cdot) is a known (up to location and scale normalizations) invertible link function. The presence of F(\cdot) ensures that ( 1.1 ) is flexible enough to cover a broad range of the previously studied dyadic network models with unobserved heterogeneity, including important nonlinear specifications such as network formation or Poisson regression models. 3 3 3 For example, with F(\cdot) equal to the logistic CDF and g(\xi_{i},\xi_{j})=\xi_{i}+\xi_{j} , ( 1.1 ) corresponds to the network formation model of 34 . Being agnostic about the dimensions of the fixed effects and the nature of their interactions, ( 1.1 ) allows for a wide range of forms of unobserved heterogeneity, including homophily based on unobservables. Example 1 (Nonparametric homophily based on unobservables) . Let \xi=(\alpha,\nu)^{\prime}\in\mathbb{R}^{2} and \displaystyle g(\xi_{i},\xi_{j})=\alpha_{i}+\alpha_{j}-\psi(\nu_{i},\nu_{j}), where \psi(\cdot,\cdot) is some function satisfying \psi(\nu_{i},\nu_{j})=0 whenever \nu_{i}=\nu_{j} and increasing in \left|\nu_{i}-\nu_{j}\right| (e.g., \psi(\nu_{i},\nu_{j})=c\left|\nu_{i}-\nu_{j}\right|^{\zeta} for some c>0 and \zeta\geqslant 1 ). Here \alpha represents the standard additive fixed effect, and \psi(\cdot,\cdot) captures latent homophily based on \nu : agents with similar values of \nu tend to interact with higher intensity compared to agents distant in terms of \nu . Again, since the dimension of \xi is not specified, ( 1.1 ) can also incorporate homophily based on several unobserved characteristics (multivariate \nu ) in a similar manner. \blacksquare We study identification and estimation of ( 1.1 ) under the assumption that we observe a single network of a growing size. 4 4 4 The large single network asymptotics is standard for the literature focusing on identification and estimation of network models with unobserved heterogeneity. See, for example, 34 ; 25 ; 17 ; 42 ; 62 ; 31 ; 30 . First, we focus on a simpler version of ( 1.1 ) \displaystyle Y_{ij}=W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j})+\varepsilon_{ij}. (1.2) We argue that the outcomes of the interactions can be used to identify agents with the same values of the unobserved fixed effects. Specifically, we introduce a certain pseudo-distance d_{ij} measuring similarity between agents i and j in terms of their latent characteristics. We argue that (i) d_{ij}=0 if and only if \xi_{i}=\xi_{j} , and (ii) d_{ij} is identified and can be estimated from the data. Consequently, agents with the same values of \xi can be identified based on the pseudo-distance d_{ij} . Then, the variation in the observed characteristics of such agents allows us to identify the parameter of interest \beta_{0} while controlling for the impact of the fixed effects. Importantly, this result is not driven by the linearity or particular functional form of ( 1.2 ): we show that a similar identification argument also applies when W_{ij}^{\prime}\beta_{0} is replaced by an unknown (nonparametric) function of observables. Demonstrating that the introduced pseudo-distance d_{ij} is identified plays a central role in the argument outlined above. First, we show that, if the idiosyncratic errors \varepsilon_{ij} are homoskedastic, d_{ij} can be readily estimated from the data using simple pairwise-difference regressions. Second, we extend this argument to models with general heteroskedasticity by leveraging and advancing recent developments in the matrix estimation/completion literature. Specifically, we demonstrate that the error free outcomes Y_{ij}^{*}\coloneqq W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j}) are identified and can be uniformly (across all pairs of agents) consistently estimated. This is a powerful result allowing us to treat Y_{ij}^{*} as effectively observed and thus greatly simplifying the analysis. In particular, working with Y_{ij}^{*} instead of Y_{ij} effectively reduces ( 1.2 ) to a model without the error term \varepsilon_{ij} , which can be interpreted as an extreme form of homoskedasticity. This, in turn, allows us to establish identification of \beta_{0} by applying the same argument as in the homoskedastic model. Building on these ideas, we construct an estimator of \beta_{0} and characterize its rate of convergence. Following the identification argument, we first estimate the pseudo-distances \hat{d}_{ij} , which are used to find agents with similar latent characteristics. Then, we estimate \beta_{0} by combining pairwise-difference regressions of Y_{ik}-Y_{jk} on W_{ik}-W_{jk} for all pairs of agents i and j sufficiently similar in terms of \hat{d}_{ij} . Consistency of this estimator crucially relies on the matched agents being different in terms of their observables, resulting in sufficient residual variation in W_{ik}-W_{jk} . We characterize the asymptotic behavior of the estimator’s bias due to imperfect matching, and provide conditions under which it is consistent. In the general heteroskedastic case, construction of \hat{d}_{ij} also involves preliminary estimation of the error free outcomes Y_{ij}^{*} . To provide estimators of Y_{ij}^{*} and d_{ij} valid under heteroskedastic errors, we build on and extend the approach of 66 originally employed in the context of nonparametric graphon estimation. Moreover, to formally establish identification of the error free outcomes, we also propose a modified version of 66 ’s estimator and demonstrate its consistency in the max (matrix) norm, meaning that, in a large network, our estimator recovers Y_{ij}^{*} ’s for all pairs of agents with a high precision at once. To the best of our knowledge, this result is also new to the statistics literature on graphon estimation, which has previously focused on constructing estimators \hat{Y}_{ij}^{*} and deriving their rates of convergence in terms of the mean square error/Frobenius norm ( 20 ; 29 ; 46 ; 66 ; 47 ) . Finally, we want to stress that identification of the error free outcomes is a powerful result, which applies to a general class of dyadic network models beyond ( 1.1 ) and can be used as a foundation for establishing new identification results. To the best of our knowledge, this result has not been previously recognized and leveraged in the econometrics literature. In particular, building on it, we demonstrate how the proposed identification and estimation strategies can be naturally extended to cover model ( 1.1 ), as well as its nonparametric version. We also argue that the pair-specific fixed effects g_{ij}=g(\xi_{i},\xi_{j}) are identified for all pairs of agents i and j and can be (uniformly) consistently estimated. Identification of g_{ij} is an important result in itself since in many applications the fixed effects are the central objects of interest. Moreover, this result is also of special significance when F is nonlinear because identification of g_{ij} allows us to identify important policy relevant quantities such as pair-specific and average partial effects. This paper contributes to the literature on econometrics of networks and, more generally, two-way models. The distinctive feature of our model is allowing for flexible nonparametric unobserved heterogeneity: the fixed effects can interact via the unknown coupling function g(\cdot,\cdot) . Importantly, we do not require g(\cdot,\cdot) to have any particular structure (other than satisfying a weak smoothness requirement) and do not specify the dimensionality of the fixed effects. This is in contrast to most of the existing approaches, which either explicitly specify the form of g(\cdot,\cdot) or impose additional restrictive assumptions on its shape and smoothness. Among explicitly specified forms of g(\cdot,\cdot) , the additive fixed effects structure {g(\xi_{i},\xi_{j})=\xi_{i}+\xi_{j}} is by far the most popular way of incorporating unobserved heterogeneity in dyadic network models, e.g., see 34 , 19 , 42 , 25 , 64 , 17 , 31 and 62 among others. While this specification provides a practical way of controlling for degree heterogeneity, it does not account for more complicated forms of unobserved heterogeneity including latent homophily. Recent semiparametric extensions of 34 and related frameworks feature 30 relaxing separability between W_{ij}^{\prime}\beta_{0} , \xi_{i} , and \xi_{j} . However, 30 still require \xi to be scalar and assume that the linking probability is increasing in \xi_{i} and \xi_{j} , thus ruling out homophily based on unobservables. The linear factor specification g(\xi_{i},\xi_{j})=\xi_{i}^{\prime}\xi_{j} is widely used in both network and panel models as a generalization of the additive fixed effect framework. 5 5 5 Recent studies considering network models with unobserved effects having a linear factor structure include, among others, 21 ; 49 ; 65 . While, as argued in 21 , this specification allows for certain forms of latent homophily, approximating a general function g(\cdot,\cdot) by the linear factor model requires a growing number of factors (e.g., 26 ). Such low-rank approximations, for example, are utilized by 28 and 12 who consider a panel variation of ( 1.2 ). To control the accuracy of the proposed low-rank approximations, both of these papers require g(\cdot,\cdot) to have sufficiently many continuous derivatives and, more importantly, to ensure consistency of their estimator of \beta_{0} , they require regressors W to be ‘‘high-rank’’. Both of these requirements are restrictive in the network setting; 6 6 6 Non-differentiable functions g(\cdot,\cdot) , such as the one provided in Example 1 for \zeta=1 , are a common feature of popular latent homophily models (e.g., 40 ; 36 ). see Section 2.2.1 for a detailed comparison of the frameworks and approaches to identification. Allowing for both low-rank regressors W and possibly non-differentiable g(\cdot,\cdot) is an important and unique combination of features of our setting differentiating this paper from the rest of the literature. 7 7 7 Low-rank regressors are typically ruled out to ensure identification of \beta_{0} even in linear factor models; see, for example, 10 ; 52 ; 7 . Employing clustering methods to partition units into groups with similar unobserved characteristics is another method commonly employed to control for interactive (time-varying) unobserved heterogeneity. This approach was proposed and applied to likelihood panel models in the seminal work by 15 and then extended to semiparametric panel regressions by 12 . While the specific clustering methods (involving the observed covariates as well) employed in these papers proved to be instrumental in panel settings, they would not allow one to identify and estimate \beta_{0} in network models when the regressors take the typical form of W_{ij}=w(X_{i},X_{j}) , where X_{i} and X_{j} are observed characteristics of agents i and j . In this case, the previously employed methods would cluster units into groups with similar values of both \xi and X preventing one from disentangling the effects of observables and unobservables and thus from identifying \beta_{0} as well. 8 8 8 Moreover, the clustering methods employed in 15 and 12 are based on individual-specific moments. Such clustering methods might fail to meaningfully group units in network settings, in which informative individual-specific moments might not exist at all; see Section 2.2.1 and specifically Footnote 12 for details. Importantly, unlike the previously employed clustering methods, our approach can be used to find units with similar values of \xi and yet different values of X allowing us to identify \beta_{0} . Thus, we also complement the methodology of 15 by providing a new grouping approach which can be instrumental in both network and panel models with low-rank regressors. When \xi is discrete, the considered model ( 1.1 ) belongs to the class of stochastic block models (SBM) with covariates (e.g., 51 ; 49 ). While our framework and estimation approach are general enough to cover this special setup, in this paper, we focus on the case when unobserved heterogeneity is continuous. 9 9 9 In fact, when \xi is discrete, agents can be correctly classified into groups with the same values of \xi based on the already introduced pseudo-distance \hat{d}_{ij} , which greatly simplifies the asymptotic analysis; we will discuss this in more detail shortly after we introduce Assumption 3 in Section 4 . In a recent study, 45 study a nonseparable nonparametric variation of SBM with covariates. Since their approach crucially relies on the discreteness of \xi whereas ours exploits separability between the observables and unobservables as in ( 1.1 ), the frameworks considered in this paper and by 45 are non-nested and complementary. Another strand of the literature emphasizes the importance of using network data to control for endogeneity in peer effects and other related models (e.g., 32 ; 43 ; 9 ; 61 ). In these papers, the agents’ latent characteristics \xi affect both the individual outcomes of interest as well as the network formation process. To tackle this problem, 9 and 43 propose using certain network statistics to identify agents with the same values of \xi allowing the authors to control for the unobservables in the other (cross-sectional) regression of interest (e.g., in a peer effects model). The important difference between their and our work is that we use the same network data both to control for unobserved heterogeneity and to identify the parameters of interest, allowing us to disentangle the effects of observables and unobservables within a single network model. 10 10 10 For example, similarly to the clustering methods of 15 and 12 , a direct application of 9 ’s approach to the observed network only allows one to identify agents with the same values of both \xi and X once again precluding identification of \beta_{0} . Finally, we emphasize that the considered model ( 1.1 ) does not incorporate interaction externalities. Specifically, we assume that conditional on the agents’ observed and unobserved characteristics, the interaction outcomes are independent. This assumption is plausible when the interactions are primarily bilateral. For excellent recent reviews of econometrics of networks, with and without strategic interactions, we refer the reader to 33 ; 35 ; 23 . The rest of the paper is organized as follows. In Section 2 , we formally introduce the framework and provide (heuristic) identification arguments for the semiparametric regression model ( 1.2 ). Section 3 turns these ideas into estimators of the parameters of interest. In Section 4 , we establish consistency of the proposed estimators and derive their rates of convergence. In Section 5 , we generalize the proposed identification argument to cover more general settings including the nonlinear model ( 1.1 ) as well as its nonparametric analogue. Section 6 provides numerical and empirical illustrations. A supplementary appendix contains all proofs, and additional discussions and illustrations. 2 Identification of the Semiparametric Model In this section, we introduce the framework and provide a conceptual discussion of identification of the semiparametric regression model. This discussion is supposed to illustrate the anatomy of the model and to highlight the main insights of our identification strategy, and is deliberately not formalized here. In Section 3 , we will turn these ideas into practical estimators. Identification then is formally demonstrated in Section 4 , where establish consistency of our estimators and provide their rates of convergence. 2.1 The model We consider a network consisting of n agents. Each agent i is endowed with characteristics Z_{i}=(X_{i},\xi_{i}) , where X_{i}\in\mathcal{X} is observed by the econometrician, while \xi_{i}\in\mathcal{E} is not. We consider the following semiparametric regression model, where the (scalar) outcome of the interaction between agents i and j is given by \displaystyle Y_{ij}=w(X_{i},X_{j})^{\prime}\beta_{0}+g(\xi_{i},\xi_{j})+\varepsilon_{ij},\quad i\neq j. (2.1) Here, w:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}^{p} is a known function, which transforms the observed characteristics of agents i and j into a pair-specific vector of covariates W_{ij}\coloneqq w(X_{i},X_{j}) , \beta_{0}\in\mathbb{R}^{p} is the parameter of interest, and \varepsilon_{ij} is an unobserved idiosyncratic error. Note that unlike w(\cdot,\cdot) , the coupling function g:\mathcal{E}\times\mathcal{E}\rightarrow\mathbb{R} is unknown , and the dimension of the fixed effect \xi_{i}\in\mathcal{E} is not specified . For simplicity of exposition, we will suppose that \xi_{i}\in\mathbb{R}^{d_{\xi}} even though, in principle, the same insights apply when \mathcal{E} is a general metric space. For concreteness, we will also focus on an undirected model with Y_{ij}=Y_{ji} , so w(\cdot,\cdot) and g(\cdot,\cdot) are symmetric functions, and \varepsilon_{ij}=\varepsilon_{ji} . The methodology presented in this paper straightforwardly extends to directed networks and general two-way settings including panel models; see Section 5.3 for a more detailed discussion. The following assumption formalizes the sampling process. Assumption 1 . (i) \{Z_{i}\}_{i=1}^{n} are i.i.d.; (ii) conditional on \{Z_{i}\}_{i=1}^{n} , the idiosyncratic errors \{\varepsilon_{ij}\}_{i0 , we have \displaystyle\left|g(\xi_{1},\xi)-g(\xi_{2},\xi)\right|\leqslant\overline{G}\left\|\xi_{1}-\xi_{2}\right\|\quad\text{for all $\xi_{1},\xi_{2},\xi\in\mathcal{E}$;} (iv) for some c>0 , \mathbb{E}\left[e^{\lambda\varepsilon_{ij}}|X_{i},\xi_{i},X_{j},\xi_{j}\right]\leqslant e^{c\lambda^{2}} for all \lambda\in\mathbb{R} a.s. Conditions ( i ) and ( ii ) are standard. Condition ( iii ) requires g(\cdot,\cdot) to be (uniformly) Lipschitz continuous. Condition ( iv ) requires the conditional distribution of the error \varepsilon_{ij}|X_{i},\xi_{i},X_{j},\xi_{j} to be sub-Gaussian, uniformly over (X_{i},\xi_{i},X_{j},\xi_{j}) . It allows us to invoke certain concentration inequalities and derive rates of uniform convergence. 4.1 Rate of convergence for \hat{\beta} In this section, we provide necessary regularity conditions and establish the rate of convergence for the kernel based estimator \hat{\beta} introduced in ( 3.1 ). We will do that assuming that our candidate estimator \hat{d}_{ij}^{2} converges to d_{ij}^{2} (uniformly across all pairs) at a certain rate R_{n}\rightarrow\infty , i.e., \displaystyle\min_{i,j\neq i}|\hat{d}_{ij}^{2}-d_{ij}^{2}|=O_{p}(R_{n}^{-1}). (4.1) We will first derive the result treating ( 4.1 ) as a high-level assumption, and then verify that it holds and characterize R_{n} for the candidate estimators ( 3.3 ) and ( 3.4 ). We establish consistency and derive a guaranteed rate of convergence of \hat{\beta} under the following regularity conditions. For simplicity of exposition, we state these conditions for the case when \xi is scalar but the main result of this section still holds for multivariate \xi under minimal appropriate modifications of the assumptions below. Assumption 3 . (i) \xi\in\mathbb{R} , and \xi|X=x is continuously distributed for all x\in\text{supp}\left(X\right) ; its conditional density f_{\xi|X} (with respect to the Lebesgue measure) satisfies \sup_{x\in\text{supp}\left(X\right)}\sup_{\xi\in\mathcal{E}}f_{\xi|X}(\xi|x)\leqslant\overline{f}_{\xi|X} for some constant \overline{f}_{\xi|X}>0 ; (ii) for all x\in\text{supp}\left(X\right) , f_{\xi|X}(\xi|x) is continuous at almost all \xi (with respect to the conditional distribution of \xi|X=x ); moreover, there exist positive constants \overline{\delta} and \gamma such that for all \delta\in(0,\overline{\delta}) and for all x\in\text{supp}\left(X\right) , \displaystyle\mathbb{P}\left(\xi_{i}\in\{\xi:f_{\xi|X}(\xi|x)\text{ is continuous on }B_{\delta}(\xi)\}|X_{i}=x\right)\geqslant 1-\gamma\delta; (4.2) (iii) there exists C_{\xi}>0 such that for all x\in\text{supp}\left(X\right) and for any convex set \mathcal{D}\in\mathcal{E} such that f_{\xi|X}(\cdot;x) is continuous on \mathcal{D} , we have \left|f_{\xi|X}(\xi_{1}|x)-f_{\xi|X}(\xi_{2}|x)\right|\leqslant C_{\xi}\left|\xi_{1}-\xi_{2}\right| . Assumption 3 describes the properties of the conditional distribution of \xi|X . Note that we focus on the case when \xi|X=x is continuously distributed for all x\in\text{supp}\left(X\right) even though our framework straightforwardly allows for the (conditional) distribution of \xi to have point masses or to be discrete. In fact, the asymptotic analysis is substantially simpler in the latter case. Specifically, if \xi is discrete (and takes finitely many values), the agents can be consistently clustered into groups with the same values of \xi based on the same pseudo-distance \hat{d}_{ij}^{2} . In this case, \hat{\beta} is asymptotically equivalent to the oracle pairwise-difference estimator using the knowledge of the true cluster membership, and, as a result, it is asymptotically normal and unbiased. Moreover, in this case, \beta_{0} can also be estimated by the pooled linear regression, which includes additional interactions of the dummy variables for the estimated cluster membership. 17 17 17 Similar ideas are also explored in 53 in the context of grouped panel models. Conditions ( ii ) and ( iii ) are weak smoothness requirements. The second part of Condition ( ii ) bounds the probability mass of \xi|X=x , for which f_{\xi|X}(\xi|X) is not potentially continuous on a ball B_{\delta}(\xi) . It allows us to control the probability mass of \xi close to the boundary of its support, where f_{\xi|X}(\xi|X) is allowed to be discontinuous. Example (Illustration of Assumption 3 ( ii )) . Suppose \xi|X=x is supported and continuously distributed on [0,1] for all x\in\text{supp}\left(X\right) . Then f_{\xi|X}(\xi|x) is continuous on B_{\delta}(\xi) for all \xi\in[\delta,1-\delta] . Then ( 4.2 ) is satisfied with \gamma=2\overline{f}_{\xi|X} , where \overline{f}_{\xi|X} is as in Assumption 3 ( i ). \blacksquare Assumption 4 . (i) there exist \underline{\lambda}>0 and \underline{\delta}>0 such that \displaystyle\mathbb{P}\left((X_{i},X_{j})\in\left\{(x_{1},x_{2}):\lambda_{min}(\mathcal{C}(x_{1},x_{2}))>\underline{\lambda},\int f_{\xi|X}(\xi|x_{1})f_{\xi|X}(\xi|x_{2})d\xi>\underline{\delta}\right\}\right)>0, where \displaystyle\mathcal{C}(x_{1},x_{2})\coloneqq\mathbb{E}\left[(w(x_{1},X)-w(x_{2},X))(w(x_{1},X)-w(x_{2},X))^{\prime}\right]; (4.3) (ii) for each \delta>0 , there exists C_{\delta}>0 such that \displaystyle\inf_{\beta}\mathbb{E}\left[\left(g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})-\left(w(X_{i},X_{k})-w(X_{j},X_{k})\right)^{\prime}\beta\right)^{2}|X_{i},\xi_{i},X_{j},\xi_{j}\right]>C_{\delta} a.s. for (X_{i},\xi_{i}) and (X_{j},\xi_{j}) satisfying \left|\xi_{i}-\xi_{j}\right|\geqslant\delta ; (iii) d_{ij}^{2}\equiv d^{2}(X_{i},\xi_{i},X_{i},\xi_{j})=c(X_{i},X_{j},\xi_{i})(\xi_{j}-\xi_{i})^{2}+r(X_{i},\xi_{i},X_{j},\xi_{j}) , where \left|r(X_{i},\xi_{i},X_{j},\xi_{j})\right|\leqslant C\left|\xi_{j}-\xi_{i}\right|^{3} a.s. for some C>0 , and 0<\underline{c}\underline{\lambda}>0 , (ii) and yet \xi_{i} and \xi_{j} are increasingly similar. The latter is guaranteed by \int f_{\xi|X}(\xi|X_{i})f_{\xi|X}(\xi|X_{j})d\xi>\underline{\delta} , which implies that the conditional supports of \xi_{i}|X_{i} and \xi_{j}|X_{j} have a non-trivial overlap. Condition ( i ) is crucial for establishing consistency of \hat{\beta} . Condition ( ii ) ensures that d_{ij}^{2} is bounded away from zero whenever \left|\xi_{i}-\xi_{j}\right| is. Notice that it also guarantees that agents that are close in terms of d_{ij}^{2} , must also be similar in terms of \xi . Hence, Condition ( ii ) justifies using the pseudo-distance d_{ij}^{2} for finding agents with similar values of \xi in finite samples. It also can be interpreted as a rank type condition: for fixed agents i and j with \xi_{i}\neq\xi_{j} , g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k}) cannot be expressed as a linear combination of the components of W_{ik}-W_{jk} . Condition ( iii ) is a local counterpart of Condition ( ii ). It says that, as a function of \xi_{j} , d^{2}(X_{i},X_{j},\xi_{i},\xi_{j}) can be locally quadratically approximated around \xi_{j}=\xi_{i} , and the approximation remainder can be uniformly bounded as O(\left|\xi_{j}-\xi_{i}\right|^{3}) . Condition ( iii ) also explains why we divide \hat{d}_{ij}^{2} by h_{n}^{2} for computing the kernel weights. Indeed, locally d_{ij}^{2}\propto(\xi_{j}-\xi_{i})^{2} , so the bandwidth h_{n} effectively controls how large \left|\xi_{j}-\xi_{i}\right| can be for the pair of agents i and j to get a positive weight K(\frac{\hat{d}_{ij}^{2}}{h_{n}^{2}}) . Assumption 5 . (i) K:\mathbb{R}_{+}\rightarrow\mathbb{R} is supported on [0,1] and bounded by \overline{K}<\infty . K satisfies \mu_{K}\coloneqq\int K(u^{2})du>0 and \left|K(z)-K(z^{\prime})\right|\leqslant\overline{K}^{\prime}\left|z-z^{\prime}\right| for all z,z^{\prime}\in\mathbb{R}_{+} for some \overline{K}^{\prime}>0 ; (ii) h_{n}\rightarrow 0 , nh_{n}/\ln n\rightarrow\infty and R_{n}h_{n}^{2}\rightarrow\infty for some R_{n}\rightarrow\infty satisfying ( 4.1 ). Assumption 5 specifies the properties of the kernel K and the bandwidth h_{n} . Condition ( i ) imposes a number of fairly standard restrictions on K including Lipschitz continuity. Condition ( ii ) restricts the rates at which the bandwidth is allowed to shrink towards zero. The requirement nh_{n}/\ln n\rightarrow\infty ensures that we have a growing number of potential matches as the sample size increases. Additionally, to get the desired results we need R_{n}h_{n}^{2}\rightarrow\infty : the bandwidth cannot go to zero faster than R_{n}^{-1/2} . This requirement allows us to bound the effect of the sampling variability coming from the first step (estimation of \{d_{ij}^{2}\}_{i\neq j} ) on the second step (estimation of \beta_{0} ). Assumption 6 . There exists a bounded function G:\mathcal{E}\times\mathcal{E}\rightarrow\mathbb{R} such that for all \xi_{1},\xi_{2},\xi\in\mathcal{E} \displaystyle g(\xi_{1},\xi)-g(\xi_{2},\xi)=G(\xi_{1},\xi)(\xi_{1}-\xi_{2})+r_{g}(\xi_{1},\xi_{2},\xi); and there exists C>0 such that for all \delta_{n}\downarrow 0 \displaystyle\limsup_{n\rightarrow\infty}\frac{\sup_{\xi}\sup_{\xi_{1}:\left|\xi_{1}-\xi\right|>\delta_{n}}\sup_{\xi_{2}:\left|\xi_{2}-\xi_{1}\right|\leqslant\delta_{n}}\left|r_{g}(\xi_{1},\xi_{2},\xi)\right|}{\delta_{n}^{2}}\delta_{n} and \left|\xi_{2}-\xi_{1}\right|\leqslant\delta_{n} ). The goal of introducing these restrictions is to allow for a possibly non-differentiable g , e.g., g(\xi_{i},\xi_{j})=\kappa\left|\xi_{i}-\xi_{j}\right| , since such models of latent homophily are common in the literature (e.g., 40 ; 36 ). We provide an illustration of Assumption 6 in Appendix B . Theorem 1 . Suppose that ( 4.1 ) holds for some R_{n}\rightarrow\infty . Then, under Assumptions 1 - 6 , \displaystyle\hat{\beta}-\beta_{0}=O_{p}\left(h_{n}^{2}+\frac{R_{n}^{-1}}{h_{n}}+\frac{R_{n}^{-1}}{h_{n}^{2}}\left(\frac{\ln n}{n}\right)^{1/2}+n^{-1}\right). (4.4) Theorem 1 provides a guaranteed rate of convergence of \hat{\beta} and, thus, formally establishes identification of \beta_{0} . The derived rate consists of four terms. The h_{n}^{2} term accounts for the bias due to the imperfect \xi -matching. The terms involving R_{n} are due to the fact that \{d_{ij}^{2}\}_{i\neq j} are unknown and need to be estimated. Finally, n^{-1} is the standard sampling variability term in a regression with O(n^{2}) observations. In Section 4.2 , we will derive R_{n} for the considered estimators of \{d_{ij}^{2}\}_{i\neq j} and complete the characterization of the rate of convergence for \hat{\beta} provided in ( 4.4 ). In particular, we will demonstrate that, under certain conditions, the candidate estimators ( 3.3 ) and ( 3.4 ) satisfy ( 4.1 ) with R_{n}=(\frac{n}{\ln n})^{1/2} , or with an even slower-growing R_{n} depending on d_{\xi} . For such values of R_{n} , ( 4.4 ) effectively simplifies as \displaystyle\hat{\beta}-\beta_{0}=O_{p}\left(h_{n}^{2}+\frac{R_{n}^{-1}}{h_{n}}\right), (4.5) where we also used \frac{R_{n}^{-1}}{h_{n}^{2}}=o(1) implied by Assumption 5 ( ii ). In particular, under h_{n}\propto R_{n}^{-1/3} , \hat{\beta} is guaranteed to achieve the following rate of convergence \displaystyle\hat{\beta}-\beta_{0}=O_{p}\left(R_{n}^{-2/3}\right). (4.6) The rate of convergence established by Theorem 1 is not necessarily optimal and potentially can be improved, especially if additional smoothness conditions are imposed. The main goal of Theorem 1 is to demonstrate consistency of \hat{\beta} and thus complement Section 2 by formally establishing identification of \beta_{0} under minimal primitive conditions. Finally, we want to highlight again two important features of the setting differentiating it from the previously studied frameworks and complicating the asymptotic analysis. First, as discussed in more detail in Section 2.2.1 , we consider low-dimensional (or even low-rank) regressors W_{ij}=w(X_{i},X_{j}) typical for network models instead of relying on “high-rank” regressors like most of the related literature does. Second, we only impose minimal smoothness assumptions on g(\cdot,\cdot) and do not require it to be differentiable whereas the alternative approaches building low-rank approximations of interactive unobserved heterogeneity rely on the existence of multiple continuous derivatives of g(\cdot,\cdot) (e.g., 26 ; 28 ; 12 ); see also Remark 4.1 below for a clarification of the role of Assumption 6 . As discussed earlier, these features are highly representative of network models. Moreover, their unique combination makes the asymptotic analysis highly nonstandard, potentially invalidating the previously proposed methods and established statistical guarantees. For this reason, in this paper, we do not attempt to construct an asymptotically normal estimator of \beta_{0} or provide an inference method at the cost of imposing additional assumptions restrictive in network models. Instead, we focus on establishing identification of \beta_{0} by providing a new estimator and showing its consistency in the general setting of the paper. Remark 4.1 . Assumption 6 is not essential for consistency of \hat{\beta} . It can be dropped at the cost of increasing the magnitude of the bias of \hat{\beta} from h_{n}^{2} to h_{n} . Even when Assumption 6 is imposed, bounding the bias of \hat{\beta} is non-trivial. In particular, it requires careful accounting for the agents with \xi “close” to the boundary of its support because kernel smoothing methods suffer from larger biases on the boundary even when the estimated function is smooth. Remark 4.2 (Extension to d_{\xi}>1 ) . Importantly, the result of Theorem 1 remains the same for d_{\xi}>1 provided that the condition nh_{n}/\ln n\rightarrow\infty in Assumption 5 ( ii ) is generalized as nh_{n}^{d_{\xi}}/\ln n\rightarrow\infty , and the other conditions are analogously restated in terms of multivariate \xi , if needed. Also notice that, the rates provided in ( 4.4 ) and ( 4.5 ) would still implicitly depend on d_{\xi} through R_{n} (and the restrictions imposed on h_{n} by Assumption 5 ( ii )). 4.2 Rates of uniform convergence for \hat{d}_{ij}^{2} In this section, we complement the result of Theorem 1 by characterizing R_{n} , the rate of uniform convergence for \hat{d}_{ij}^{2} defined in ( 4.1 ), for the candidate estimators ( 3.3 ) and ( 3.4 ) in the homoskedastic and then in the general heteroskedastic settings. 4.2.1 Homoskedastic model First, we consider the homoskedastic case, i.e., we assume that the idiosyncratic errors satisfy ( 2.5 ). As discussed in Section 3.2 , in this case, the suggested estimator is given by \hat{d}_{ij}^{2}=\hat{q}_{ij}^{2}-2\hat{\sigma}^{2} , and d_{ij}^{2}=q_{ij}^{2}-2\sigma^{2} (see ( 3.3 ) and ( 2.9 ), respectively). Thus, \displaystyle\max_{i,j\neq i}\left|\hat{d}_{ij}^{2}-d_{ij}^{2}\right|=\max_{i,j\neq i}\left|(\hat{q}_{ij}^{2}-q_{ij}^{2})-(2\hat{\sigma}^{2}-2\sigma^{2})\right|\leqslant\max_{i,j\neq i}\left|\hat{q}_{ij}^{2}-q_{ij}^{2}\right|+\left|2\hat{\sigma}^{2}-2\sigma^{2}\right|. (4.7) This bound, together with the following lemma, allows us to characterize R_{n} . Lemma 1 . Suppose that ( 2.5 ) holds and \mathcal{B} is compact. Then, under Assumptions 1 and 2 , \displaystyle\max_{i,j\neq i}\left|\hat{q}_{ij}^{2}-q_{ij}^{2}\right| \displaystyle=O_{p}\left((\ln n/n)^{1/2}\right), (4.8) \displaystyle 2\hat{\sigma}^{2}-2\sigma^{2} \displaystyle=\overline{G}^{2}\min_{i\neq j}\left\|\xi_{i}-\xi_{j}\right\|^{2}+O_{p}\left((\ln n/n)^{1/2}\right), (4.9) where \hat{q}_{ij}^{2} , q_{ij}^{2} , 2\hat{\sigma}^{2} are given by ( 2.7 ), ( 2.6 ), ( 3.2 ), and \overline{G} is defined in Assumption 2 ( iii ). The bounds ( 4.8 ) and ( 4.9 ) established by Lemma 1 together with ( 4.7 ) allow us to provide R_{n} for the estimator ( 3.3 ) in the homoskedastic setting. To make this characterization complete, we also need to provide a bound on \left\|\xi_{i}-\xi_{j}\right\|^{2} in ( 4.9 ). In particular, since \mathcal{E} is bounded (Assumption 2 ( ii )), we can guarantee that \displaystyle\min_{i\neq j}\left\|\xi_{i}-\xi_{j}\right\|^{2}\leqslant Cn^{-2/d_{\xi}} (4.10) for some C>0 . While this bound is conservative, it ensures that, for d_{\xi}\leq 4 , the contribution of \left\|\xi_{i}-\xi_{j}\right\|^{2} is negligible, resulting in the following corollary of Lemma 1 . Corollary 1 . Suppose that the hypotheses of Lemma 1 are satisfied. Then, for d_{\xi}\leqslant 4 , \displaystyle\max_{i,j\neq i}\left|\hat{d}_{ij}^{2}-d_{ij}^{2}\right|=O_{p}\left((\ln n/n)^{1/2}\right), where \hat{d}_{ij}^{2} and d_{ij}^{2} are given by ( 3.3 ) and ( 2.4 ), respectively. Corollary 1 ensures that when the errors are homoskedastic and d_{\xi}\leqslant 4 , \hat{d}_{ij}^{2} given by ( 3.3 ) satisfies ( 4.1 ) with R_{n}=\left(\frac{n}{\ln n}\right)^{1/2} . Hence, when h_{n}\propto R_{n}^{-1/3}=\left(\frac{\ln n}{n}\right)^{-1/6} , ( 4.6 ) implies that \displaystyle\hat{\beta}-\beta_{0}=O_{p}\left((\ln n/n)^{1/3}\right), so the guaranteed rate of convergence for \hat{\beta} is \left(\frac{n}{\ln n}\right)^{1/3} . Remark 4.3 . For d_{\xi}>5 , it is still possible to provide a simple yet conservative bound on R_{n} by combining ( 4.10 ) with the result of Lemma 1 . In particular, in this case, we can guarantee that 2\hat{\sigma}^{2}-2\sigma^{2}=O_{p}\left(n^{-2/d_{\xi}}\right) , and, consequently, we also have \displaystyle\max_{i,j\neq i}\left|\hat{d}_{ij}^{2}-d_{ij}^{2}\right|=O_{p}\left(n^{-2/d_{\xi}}\right). We stress that these bounds are loose. With a more detailed analysis of the asymptotic behavior of \min_{i\neq j}\left\|\xi_{i}-\xi_{j}\right\|^{2} (which is outside the scope of this paper), these results can be substantially refined. 4.2.2 Model with general heteroskedasticity In this section, we establish the rate of uniform convergence for \hat{d}_{ij}^{2} under general heteroskedasticity of the errors. First, we suppose that X is discrete and derive R_{n} for the estimator given by ( 3.4 )-( 3.7 ). Then, we discuss how this estimator can be modified to accommodate continuously distributed X . Finally, we also provide a general result establishing R_{n} for \hat{d}_{ij}^{2} based on a generic estimator of Y_{ij}^{*} , potentially other than ( 3.7 ). Estimation of d_{ij}^{2} when X is discrete Now we formally derive the rate of uniform convergence for \hat{d}_{ij}^{2} given by ( 3.4 )-( 3.7 ). This rate crucially depends on the asymptotic properties of the denoising estimator \hat{Y}_{ij}^{*} . To formally state the asymptotic properties of \hat{Y}_{ij}^{*} , we introduce the following assumption. Assumption 7 . (i) X is discrete and takes finitely many values \{x_{1},\dots,x_{R}\} ; (ii) there exist positive constants \kappa and \overline{\delta} such that for all x\in\text{supp}\left(X\right) , for all \xi^{\prime}\in\text{supp}\left(\xi|X=x\right) , \mathbb{P}(\xi\in B_{\delta}(\xi^{\prime})|X=x)\geqslant\kappa\delta^{d_{\xi}} for all positive \delta\leqslant\overline{\delta} . As pointed out before, we suppose that X is discrete and takes finitely many values. Condition ( ii ) is a weak condition imposed on the conditional distribution of \xi|X . If \xi|X is continuously distributed, it is satisfied when the conditional density f_{\xi|X}(\xi|x) is (uniformly) bounded away from zero and its support is not “too irregular”. For any matrix A\in\mathbb{R}^{n\times n} , let \left\|A\right\|_{2,\infty}\coloneqq\max_{i}\sqrt{\sum_{j=1}^{n}A_{ij}^{2}} . Also let \hat{Y}^{*} and Y^{*} denote n\times n matrices with entries given by \hat{Y}_{ij}^{*} and Y_{ij}^{*} . Theorem 2 . Suppose that for all i , \underline{C}(n\ln n)^{1/2}\leqslant n_{i}\leqslant\overline{C}(n\ln n)^{1/2} for some positive constants \underline{C} and \overline{C} . Then, under Assumptions 1 , 2 , 7 , for \hat{Y}_{ij}^{*} given by ( 3.7 ) we have: (i) n^{-1}\|{\hat{Y}^{*}-Y^{*}}\|_{2,\infty}^{2}=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right) ; (ii) \max_{k}\max_{i}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}(\hat{Y}_{i\ell}^{*}-Y_{i\ell}^{*})}|=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right). Theorem 2 establishes two important asymptotic properties of \hat{Y}_{ij}^{*} . In fact, both results play key roles in bounding R_{n} , the rate of uniform convergence for \hat{d}_{ij}^{2} . Part ( i ) is analogous to the result of 66 . While 66 only consider binary outcomes and do not allow for observed covariates, we extend their result by allows for (i) d_{\xi}>1 , (ii) possibly non-binary outcomes and unbounded idiosyncratic errors, (iii) observed (discrete) covariates X . Part ( ii ) is new. It allows us to substantially improve on R_{n} compared to what Part ( i ) can guarantee individually. 18 18 18 See Lemma 2 for the comparison of the rates. Note that Theorem 2 requires n_{i} , the number of agents included into \hat{\mathcal{N}}_{i}(n_{i}) , to grow at (n\ln n)^{1/2} rate. As shown in 66 , this rate is optimal. 19 19 19 The optimal choice of n_{i} remains the same for d_{\xi}>1 . In applications, the authors also recommend taking n_{i}=C(n\ln n)^{1/2} with C\simeq 1 and document robustness of their numerical results to the choice of C . Building on Theorem 2 , we now provide rate of uniform convergence for \hat{d}_{ij}^{2} . Theorem 3 . Suppose that the hypotheses of Theorem 2 are satisfied and \mathcal{B}=\mathbb{R}^{p} . Then, \displaystyle\max_{i,j\neq i}|{\hat{d}_{ij}^{2}-d_{ij}^{2}}|=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right), where \hat{d}_{ij}^{2} and d_{ij}^{2} are given by ( 3.4 )-( 3.7 ) and ( 2.4 ), respectively. Theorem 3 establishes the rate of uniform convergence for the proposed estimator of d_{ij}^{2} . Specifically, it ensures that, for the considered \hat{d}_{ij}^{2} , ( 4.1 ) holds with R_{n}=\left(\frac{n}{\ln n}\right)^{\frac{1}{2d_{\xi}}} . Combined with ( 4.6 ), this guarantees that under the appropriate choice of the bandwidth h_{n} , we have \displaystyle\hat{\beta}-\beta_{0}=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{3d_{\xi}}}\right). Thus, when X is discrete, \beta_{0} can be estimated (at least) at \left(\frac{n}{\ln n}\right)^{\frac{1}{3d_{\xi}}} rate. If \xi is scalar, the guaranteed rate of convergence for \hat{\beta} is the same as in the homoskedastic case. Estimation of d_{ij}^{2} when X is continuously distributed The proposed estimator \hat{Y}_{ij}^{*} given by ( 3.6 )-( 3.7 ) can be straightforwardly modified to allow for continuously distributed (components of) X . Since, in this case, the probability of finding two agents with exactly the same values of X is zero, we have to modify the construction of \hat{\mathcal{N}}_{i}(n_{i}) previously provided in ( 3.6 ). One natural possibility is to consider \displaystyle\hat{\mathcal{N}}_{i}(n_{i};\delta_{n})\coloneqq\{i^{\prime}:\left\|X_{i^{\prime}}-X_{i}\right\|\leqslant\delta_{n},\text{Rank}(\hat{d}_{\infty}^{2}(i,i^{\prime})|\left\|X-X_{i}\right\|\leqslant\delta_{n})\leqslant n_{i}\}. (4.11) The parameter \delta_{n} controls the quality of matching based on X . To guarantee consistency of \hat{Y}_{ij}^{*} , we will need \delta_{n} to converge to zero but slowly enough to ensure that we can still find a growing number of good matches increasingly similar in terms of both X and \xi . Once the constructed neighborhoods are appropriately modified, \hat{Y}_{ij}^{*} can still be computed as in ( 3.7 ), and, with some work, the result of Theorem 2 can be generalized accordingly to allow for continuously distributed covariates. Remark 4.4 . Another possibility to allow for continuously distributed (components of) X is to simply treat it as unobserved, similarly to \xi . In this case, (X,\xi) becomes the effective latent variable and \hat{\mathcal{N}}_{i}(n_{i}) can be constructed without conditioning on X=X_{i} . Then the result of Theorem 2 can be applied to the resulting estimator delivering analogous rates of convergence with d_{\xi}+d_{X} taking of the place of d_{\xi} , where d_{X} denotes the dimension of X . While this construction of \hat{Y}_{ij}^{*} might not necessarily be optimal, it allows us to formally cover the case when X is continuously distributed by providing analogous consistency results. Estimation of d_{ij}^{2} using general matrix denoising techniques Theorem 3 establishes uniform consistency of \hat{d}_{ij}^{2} leveraging the specific structure of \hat{Y}_{ij}^{*} in ( 3.7 ) and requires X to be discrete. To complement Theorem 3 and formally establish identification of d_{ij}^{2} and \beta_{0} in the general setting, we will now provide a generic consistency result, which does not require \hat{Y}_{ij}^{*} to have any particular structure and holds regardless of whether X is discrete or continuously distributed. Lemma 2 . Suppose that \hat{Y}^{*} satisfies n^{-1}\|{\hat{Y}^{*}-Y^{*}}\|_{2,\infty}^{2}=O_{p}(\mathcal{R}_{n}^{-1}) for some \mathcal{R}_{n}\rightarrow\infty . Also suppose that \mathcal{B} is compact. Then, under Assumptions 1 and 2 , we have \displaystyle\max_{i,j\neq i}|{\hat{d}_{ij}^{2}-d_{ij}^{2}}|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}+\mathcal{R}_{n}^{-1/2}\right), where \hat{d}_{ij}^{2} and d_{ij}^{2} are given by ( 3.4 ) and ( 2.4 ), respectively. Lemma 2 guarantees that \hat{d}_{ij}^{2} in ( 3.4 ) is uniformly consistent for d_{ij}^{2} provided that \hat{Y}_{ij}^{*} is consistent for Y_{ij}^{*} in the (2,\infty) norm, and thus it justifies using alternative estimators \hat{Y}_{ij}^{*} available in the literature. Together with the result of Theorem 4.4 , Lemma 2 delivers consistency of \hat{\beta} and thus formally establishes identification of \beta_{0} in the general setting. In particular, as argued in Remark 4.4 , if X is continuously distributed, we can still construct \hat{Y}^{*} satisfying the requirement of the lemma with \mathcal{R}_{n}=\left(\frac{n}{\ln n}\right)^{\frac{1}{2(d_{\xi}+d_{X})}} . Thus, Lemma 2 guarantees that \beta_{0} can be consistently estimated when X is continuously distributed. 4.3 Uniformly consistent estimation of Y_{ij}^{*} One of the contributions of this paper is establishing identification of the error free outcomes Y_{ij}^{*} ’s. In Section 2.4.1 , we heuristically argued that Y_{ij}^{*} is identified. In this section, we construct a uniformly consistent estimator of Y_{ij}^{*} and, hence, formally prove its identification. As before, first, we suppose that X is discrete and takes finitely many values. The estimator we propose is an analogue of \hat{Y}_{ij}^{*} given by ( 3.7 ), which we used before to construct \hat{d}_{ij}^{2} . It utilizes exactly the same neighborhoods as in ( 3.6 ) but, unlike \hat{Y}_{ij}^{*} , averages over all unique outcomes Y_{i^{\prime}j^{\prime}} with i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i}) and j^{\prime}\in\hat{\mathcal{N}}_{j}(n_{j}) . 20 20 20 Recall that in the studied undirected model, Y_{ij}=Y_{ji} , and Y_{ij} is not observed for i=j . For example, if \hat{\mathcal{N}}_{i}(n_{i}) and \hat{\mathcal{N}}_{j}(n_{j}) have no elements in common, then the proposed estimator takes a simple form as in ( 3.8 ). More generally, for any i and j , let \displaystyle\hat{\mathcal{M}}_{ij}\coloneqq\{(i^{\prime},j^{\prime}):i^{\prime}0 , there exists C_{\delta}>0 such that \int(g(\xi_{i},\xi)-g(\xi_{j},\xi))^{2}dP_{\xi}(\xi)>C_{\delta} a.s. for \left|\xi_{i}-\xi_{j}\right|\geqslant\delta . Then, \displaystyle\max_{i,j}|{\tilde{Y}_{ij}^{*}-Y_{ij}^{*}}|=o_{p}(1). Theorem 4 demonstrates that \tilde{Y}_{ij}^{*} is uniformly consistent for Y_{ij}^{*} and, consequently, it formally proves that Y_{ij}^{*} is identified. We also stress that the previously employed estimator \hat{Y}_{ij}^{*} is not necessarily uniformly consistent since it averages over only n_{i} outcomes Y_{i^{\prime}j} . At the same time, \tilde{Y}_{ij}^{*} averages over m_{ij}=O(n_{i}n_{j}) outcomes, which allows us to establish the desired result. Remark 4.5 . Recall that, as discussed in Section 2.4.1 , the similarity distance \hat{d}_{\infty}^{2}(i,j) used to construct \hat{Y}_{ij}^{*} and \tilde{Y}_{ij}^{*} allows us to find agents i and j similar in terms of the L^{2} distance between functions g(\xi_{i},\cdot) and g(\xi_{j},\cdot) . The additional requirement imposed in Theorem 4 ensures that this similarity also translates into similarity between \xi_{i} and \xi_{j} , which helps us to establish uniform consistency of \tilde{Y}_{ij}^{*} . 21 21 21 This condition is a weaker version of Assumption 4 ( ii ). Together with Assumption 2 ( iii ), it allows us to guarantee that the matched agents i and j are also similar in terms of the L^{\infty} distance \left\|g(\xi_{i},\cdot)-g(\xi_{j},\cdot)\right\|_{\infty} . While it is also possible to characterize the rate of uniform convergence under additional conditions allowing one to translate the L^{2} rate into the L^{\infty} rate for \left\|g(\xi_{i},\cdot)-g(\xi_{j},\cdot)\right\| such as Assumption 4 ( iii ), we do not pursue this direction here because the primary goal of Theorem 4 is establishing identification of Y_{ij}^{*} . Remark 4.6 . Analogous uniform consistency results can also be obtained when X is continuously distributed if \tilde{Y}_{ij}^{*} is properly adjusted. As previously discussed, the possible adjustments include (i) constructing neighborhoods as in ( 4.11 ), or (ii) treating X as unobserved (see Remark 4.4 ). The result of Theorem 4 can be directly applied to the latter estimator to formally establish identification of Y_{ij}^{*} in this case. Remark 4.7 . To the best of our knowledge, identifiability of the error free outcomes Y_{ij}^{*} is a new result to the econometrics literature on identification of network and, more generally, two-way models. Moreover, Theorem 4 also contributes to the statistics literature on graphon and, more generally, the latent space model estimation. Specifically, most of the previous work focused on establishing consistency and deriving rates in terms of the mean squared error (MSE) for \hat{Y}^{*} (e.g., 20 ; 29 ; 46 ; 66 ; 47 ). Theorem 4 contributes to this literature by establishing \|{\tilde{Y}^{*}-Y^{*}}\|_{\max}=o_{p}(1) , i.e., demonstrating consistency of \tilde{Y}^{*} in the max norm. Another implication of Theorem 4 is that the pair-specific fixed effects g(\xi_{i},\xi_{j}) can also be consistently estimated and, hence, are identified for all pair of agents i and j . Consider \displaystyle\hat{g}_{ij}=\tilde{Y}_{ij}^{*}-W_{ij}^{\prime}\hat{\beta}, (4.14) where \tilde{Y}_{ij}^{*} is given by ( 4.13 ). Since we have already demonstrated consistency of \hat{\beta} and uniform consistency of \tilde{Y}_{ij}^{*} , \hat{g}_{ij} is also uniformly consistent for g_{ij}\coloneqq g(\xi_{i},\xi_{j}) . Corollary 2 . Suppose that the hypotheses of Theorem 4 are satisfied. Also, suppose that \hat{\beta}-\beta_{0}=o_{p}(1) . Then, \max_{i,j}\left|\hat{g}_{ij}-g_{ij}\right|=o_{p}(1) , where \hat{g}_{ij} is given by ( 4.14 ). Establishing nonparametric identification of the pair-specific fixed effects g_{ij} ’s is another contribution of the paper. This result is also of high empirical importance since in certain applications, the fixed effects are the primary object of interest. 5 Extensions 5.1 Identification of single index and nonparametric models In this section, we extend the identification arguments of Section 2 to cover a wide range of network models, both semiparametric and nonparametric, beyond the model ( 2.1 ). First, recall that, as discussed in Section 2.4.1 , the error free outcomes are still identified in the most general analogue of ( 2.1 ) given by \displaystyle Y_{ij}=f(X_{i},\xi_{i},X_{j},\xi_{j})+\varepsilon_{ij},\quad\mathbb{E}\left[\varepsilon_{ij}|X_{i},\xi_{i},X_{j},\xi_{j}\right]=0. (5.1) For example, we can formally establish identification of Y_{ij}^{*}=f(X_{i},\xi_{i},X_{j},\xi_{j}) by constructing a version of \tilde{Y}_{ij}^{*} introduced in ( 4.13 ), treating X as unobserved, and and showing its uniform consistency using the result of Theorem 4 . However, identification of Y_{ij}^{*} , the value of f(X_{i},\xi_{i},X_{j},\xi_{j}) , for any pair of agents i and j is fundamentally different from identification of function f . Importantly, Y_{ij}^{*} is not a causal object and cannot be directly employed in counterfactual analysis. Moreover, since \xi is not observed, function f or any features of it relevant for counterfactual analysis cannot be identified unless some additional structure is imposed on f . For example, in Sections 2 - 4 , we demonstrated that \beta_{0} is identified and can be consistently estimated when f(X_{i},\xi_{i},X_{j},\xi_{j})=W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j}) , which allows us to recover the ceteris paribus effect of W_{ij} (or X_{ij} ) on Y_{ij} in this model. Below, we extend these identification results to more general forms of f covering nonlinear and nonparametric models. 5.1.1 Identification of the semiparametric single index model One empirically relevant generalization of ( 2.1 ) is allowing f to have a single index structure \displaystyle f(X_{i},\xi_{i},X_{j},\xi_{j})=F(W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j})), (5.2) where F(\cdot) is a known invertible link function. Notice that the presence of the link function F(\cdot) ensures that ( 5.2 ) is flexible enough to cover a wide range of the previously studied nonlinear network models. For example, consider the following network formation model \displaystyle Y_{ij}=\mathbbm{1}\{W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j})-U_{ij}\geqslant 0\}, where Y_{ij} is a binary variable indicating whether agents i and j are connected or not, and U_{ij} ’s are iid draws from some distribution, e.g., logistic or N(0,1) . This model is covered by ( 5.2 ) with F(\cdot) standing for the CDF of U_{ij} . If F(\cdot)=\exp(\cdot) , then ( 5.2 ) generalizes the dyadic Poisson regression model commonly used to analyze trade networks. The previously developed arguments can be immediately applied to establish identification of \beta_{0} and to construct an analogue estimator. First, note that since Y_{ij}^{*}=F(W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j})) is identified and F(\cdot) is invertible, we can also identify \displaystyle\mathcal{Y}_{ij}^{*}\coloneqq W_{ij}^{\prime}\beta_{0}+g(\xi_{i},\xi_{j})=F^{-1}(Y_{ij}^{*}). Next, since \mathcal{Y}_{ij}^{*} are effectively observed, we are back in the additively separable setting previously studied in Sections 2 - 4 with \mathcal{Y}_{ij}^{*} replacing Y_{ij}^{*} , and all the relevant features of the model such as \beta_{0} and the pair-specific fixed effects g_{ij}=g(\xi_{i},\xi_{j}) are identified for all i and j . In particular, we can still estimate \beta_{0} as in ( 3.1 ) with \hat{\mathcal{Y}}_{ij}^{*} replacing Y_{ij} , using \hat{d}_{ij}^{2} given by ( 3.4 ) with \hat{\mathcal{Y}}_{ij}^{*} replacing \hat{Y}_{ij}^{*} . In this case, the preliminary step involves denoising the observed outcomes by constructing \hat{Y}_{ij}^{*} as before, and then computing \hat{\mathcal{Y}}_{ij}^{*}=F^{-1}(\hat{Y}_{ij}^{*}) . Finally, we want to highlight the importance of identification of the pair-specific fixed effects g_{ij}=g(\xi_{i},\xi_{j}) in the model ( 5.2 ). Since F(\cdot) is potentially nonlinear, the knowledge of \beta_{0} alone is not sufficient for identifying some policy relevant quantities such as partial effects. However, since the fixed effects g_{ij} ’s are identified for all pairs of agents, we can also identify both pair-specific and average partial effects as well as other policy relevant counterfactuals. 5.1.2 Identification of the nonparametric model In the previously considered models ( 2.1 ) and ( 5.2 ), the contribution of observables is parameterized by \beta_{0}\in\mathbb{R}^{p} , which was the primary object of interest in our analysis. In this section, we consider a nonparametric version of ( 2.1 ) with f given by \displaystyle f(X_{i},\xi_{i},X_{j},\xi_{j})=\mathscr{h}(X_{i},X_{j})+g(\xi_{i},\xi_{j}), (5.3) where both \mathscr{h}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R} and g:\mathcal{E}\times\mathcal{E}\rightarrow\mathbb{R} are unknown symmetric functions. In Sections 2 - 4 , we considered a special case of ( 5.3 ) with \mathscr{h}(X_{i},X_{j})=w(X_{i},X_{j})^{\prime}\beta_{0} and established identification of \beta_{0} . In this section, we will show that, in the studied setting, function \mathscr{h}(\cdot,\cdot) is nonparametrically identified. Importantly, nonparametric identification of \mathscr{h}(\cdot,\cdot) implies that the previously obtained identification results were not driven by the parametric restrictions or linearity imposed on \mathscr{h}(\cdot,\cdot) , justifying our focus on the semiparametric model ( 2.1 ) as a practical approximation of the general nonparametrically identified model ( 5.3 ). We establish identification of \mathscr{h}(\cdot,\cdot) and g_{ij} in ( 5.3 ) under the following assumption. Assumption 8 . Suppose that ( 5.3 ) holds and (i) \mathscr{h}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R} is a symmetric measurable function, and \mathscr{h}(x,x)=0 for all x\in\mathcal{X} ; (ii) For any x,\tilde{x}\in\text{supp}\left(X\right) , there exists {\mathcal{E}}_{x,\tilde{x}}\subseteq\mathcal{E} such that \mathbb{P}(\xi\in{\mathcal{E}}_{x,\tilde{x}}|X=x)>0 and \mathbb{P}(\xi\in{\mathcal{E}}_{x,\tilde{x}}|X=\tilde{x})>0 . Discussion of Assumption 8 ( i ). The requirement \mathscr{h}(x,x)=0 is a normalization. Indeed, since g(\cdot,\cdot) and the dimension of \xi are not specified, it is without loss of generality to let {g(\xi_{i},\xi_{j})=\alpha_{i}+\alpha_{j}+\psi(\theta_{i},\theta_{j})} , where \psi(\cdot,\cdot) is symmetric, and \xi=(\alpha,\theta^{\prime})^{\prime} . Consider \displaystyle f(X_{i},\xi_{i},X_{j},\xi_{j})=\mathscr{h}(X_{i},X_{j})+\alpha_{i}+\alpha_{j}+\psi(\theta_{i},\theta_{j}), (5.4) where \mathscr{h}(\cdot,\cdot) is symmetric. Then, we can construct an observationally equivalent model with \displaystyle\tilde{f}(X_{i},\tilde{\xi}_{i},X_{j},\tilde{\xi}_{j}) \displaystyle=\tilde{\mathscr{h}}(X_{i},X_{j})+\tilde{\alpha}_{i}+\tilde{\alpha}_{j}+\psi(\theta_{i},\theta_{j}), (5.5) \displaystyle\tilde{\mathscr{h}}(X_{i},X_{j}) \displaystyle=\mathscr{h}(X_{i},X_{j})-(\mathscr{h}(X_{i},X_{i})+\mathscr{h}(X_{j},X_{j}))/2, where \tilde{\xi}_{i}=(\tilde{\alpha}_{i},\theta_{i}^{\prime})^{\prime} with \tilde{\alpha}_{i}=\alpha_{i}+\mathscr{h}(X_{i},X_{i})/2 . Note that \tilde{\mathscr{h}}(\cdot,\cdot) is symmetric, continuous, and satisfies \tilde{\mathscr{h}}(x,x)=0 for all x\in\mathcal{X} . Since \tilde{f}(X_{i},\tilde{\xi}_{i},X_{j},\tilde{\xi}_{j})=f(X_{i},\xi_{i},X_{j},\xi_{j}) for any pair of agents i and j , the normalized model ( 5.5 ) is equivalent to the original model ( 5.4 ). \blacksquare Remark 5.1 . While the normalization introduced in Assumption 8 ( i ) is not the only possible one, it is natural for network models, especially when \mathscr{h}(X_{i},X_{j}) captures homophily based on observables (e.g., similar normalizations are also imposed in 62 and 31 ). First, we argue that \mathscr{h}(x,\tilde{x}) is identified for any fixed x,\tilde{x}\in\text{supp}\left(X\right) . Specifically, fix X_{i}=x and X_{j}=\tilde{x} , and consider \displaystyle\mathscr{d}_{ij}^{2}(\mu;x,\tilde{x})\coloneqq \displaystyle\mathbb{E}\left[\left(Y_{ik}^{*}-Y_{jk}^{*}+\mu\right)^{2}|(X_{i},X_{j},X_{k})=(x,\tilde{x},x),\xi_{i},\xi_{j}\right] \displaystyle+\mathbb{E}\left[\left(Y_{ik}^{*}-Y_{jk}^{*}-\mu\right)^{2}|(X_{i},X_{j},X_{k})=(x,\tilde{x},\tilde{x}),\xi_{i},\xi_{j}\right], \displaystyle\mathscr{d}_{ij}^{2}(x,\tilde{x})\coloneqq \displaystyle\min_{\mu\in\mathbb{R}}d_{ij}^{2}(\mu;x,\tilde{x}),\quad\quad\quad\mu^{*}_{ij}(x,\tilde{x})\coloneqq\argmin_{\mu\in\mathbb{R}}\mathscr{d}_{ij}^{2}(\mu;x,\tilde{x}). (5.6) Note that since Y_{ik}^{*} and Y_{jk}^{*} are identified in the general model ( 5.1 ), \mathscr{d}_{ij}^{2}(x,\tilde{x}) and \mu_{ij}^{*}(x,\tilde{x}) are also identified. \mathscr{d}_{ij}^{2}(x,\tilde{x}) is a nonparametric analogue of the previously considered pseudo-distance d_{ij}^{2} . Since we are interested in identifying \mathscr{h}(x,\tilde{x}) , we additionally condition on (X_{i},X_{j})=(x,\tilde{x}) and only consider X_{k}=x and X_{k}=\tilde{x} . Notice that when \xi_{i}=\xi_{j} , then we have \displaystyle\mathscr{d}_{ij}^{2}(x,\tilde{x})=\min_{\mu\in\mathbb{R}}\left((-\mathscr{h}(x,\tilde{x})+\mu)^{2}+(\mathscr{h}(x,\tilde{x})-\mu)^{2}\right)=0, where the minimum is achieved at \mu_{ij}^{*}(x,\tilde{x})=\mathscr{h}(x,\tilde{x}) . The following lemma establishes that the converse is also true: if \mathscr{d}_{ij}(x,\tilde{x})^{2}=0 , then we also necessarily have \mu_{ij}^{*}(x,\tilde{x})=\mathscr{h}(x,\tilde{x}) . Lemma 3 . Suppose that Assumption 8 holds, and that the expectations in ( 5.6 ) exist for any agents i and j , and for any x,\tilde{x}\in\mathcal{X} . Then, for any x,\tilde{x}\in\text{supp}\left(X\right) , x\neq\tilde{x} , \mathscr{d}_{ij}^{2}(x,\tilde{x})=0 implies that \mu_{ij}^{*}(x,\tilde{x})=\mathscr{h}(x,\tilde{x}) . Lemma 3 establishes identification of \mathscr{h}(x,\tilde{x}) by showing that \mathscr{h}(x,\tilde{x})=\mu^{*}_{ij}(x,\tilde{x}) for all agents i and j , with X_{i}=x and X_{j}=\tilde{x} , satisfying \mathscr{d}_{ij}(x,\tilde{x})=0 ; notice that Assumption 8 ( ii ) guarantees that such agents exist. Moreover, since the value of \mu_{ij}^{*}(x,\tilde{x}) should be the same for all such i and j (and this is true for any fixed x,\tilde{x}\in\text{supp}\left(X\right) ), the nonparametric model ( 5.3 ) as well as the previously considered models including ( 2.1 ) are overidentified, and, in principle, can be falsified. Next, notice that since \mathscr{h}(X_{i},X_{j}) is identified for any pair of agents i and j , we can also identify the pair-specific fixed effect as g_{ij}=Y_{ij}^{*}-\mathscr{h}(X_{i},X_{j}) . As a result, we conclude that both \mathscr{h} and the pair-specific fixed effects are nonparametrically identified in model ( 5.3 ). Finally, consider a nonlinear single index version of ( 5.3 ) \displaystyle f(X_{i},\xi_{i},X_{j},\xi_{j})=F(\mathscr{h}(X_{i},X_{j})+g(\xi_{i},\xi_{j})), (5.7) where F(\cdot) is a known and invertible link function. This model is a nonparametric version of ( 5.2 ) considered in Section 5.1.1 . By first constructing \mathcal{Y}_{ij}^{*}=F^{-1}(Y_{ij}^{*})=\mathscr{h}(X_{i},X_{j})+g(\xi_{i},\xi_{j}) and then applying the results of this section, we conclude that \mathscr{h} , the fixed effects g_{ij} ’s, as well as both pair-specific and average partial effects are also identified in ( 5.7 ). 5.2 Incorporating missing outcomes From the beginning of Section 2 , to simplify the exposition and facilitate the formal analysis, we assumed that \{Y_{ij}\}_{i\neq j} are observed for all pairs of agents i and j . While this assumption is standard in the network formation context, where the absence of an interaction between agents i and j is still recorded as observing Y_{ij}=0 , in many other applications, interaction outcomes are available only for a limited number of pairs of agents (e.g., in the matched employer-employee setting). Hence, it is important to discuss (i) how to properly adjust the constructed estimators to account for missing outcomes, and (ii) under which conditions the proposed method remains valid in this case. For simplicity, we will stick with considering an undirected network as before. We will discuss directed networks and general two-way settings covering the important matched employer-employee example in Section 5.3 below. Let D_{ij} be a binary variable such that D_{ij}=1 if Y_{ij} is observed and D_{ij}=0 otherwise, with D denoting the resulting adjacency matrix (by construction, D_{ii}=0 ). Also, let {\mathcal{O}_{ij}\coloneqq\{k:D_{ik}=D_{jk}=1\}} denote a set of agents k such that Y_{ik} and Y_{jk} are observed. To fix ideas, consider the homoskedastic estimator first. We adjust ( 2.7 ) and ( 3.1 ) as \displaystyle\hat{q}_{ij}^{2}=\min_{\beta\in\mathcal{B}}\frac{1}{\left|\mathcal{O}_{ij}\right|}\sum_{k\in\mathcal{O}_{ij}}(Y_{ik}-Y_{jk}-(W_{ik}-W_{jk})^{\prime}\beta)^{2}, (5.8) \displaystyle\hat{\beta}=\left(\sum_{i0 such that, for sufficiently large n , (i) \left|\xi_{j}-\xi_{i}\right|>\alpha h_{n} implies that K\left({d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})}/{h_{n}^{2}}\right)=0 and K\left({c_{ij}(\xi_{j}-\xi_{i})^{2}}/{h_{n}^{2}}\right)=0 with probability one; (ii) \sum_{i\alpha h_{n}\}=0 with probability approaching one; (iii) \left|r_{K}(X_{i},X_{j},\xi_{i},\xi_{j};h_{n})\right|\leqslant Ch_{n}\mathbbm{1}\{\left|\xi_{j}-\xi_{i}\right|\leqslant\alpha h_{n}\} a.s. for some C>0 , where r_{K}(X_{i},X_{j},\xi_{i},\xi_{j};h_{n})\coloneqq K({d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})}/{h_{n}^{2}})-K({c_{ij}(\xi_{j}-\xi_{i})^{2}}/{h_{n}^{2}}) . Proof of Lemma A.1 . Note that Assumption 4 ( iii ) guarantees that there exists some \delta_{0}>0 and c^{*}\in(0,\underline{c}) such that d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})\geqslant c^{*}(\xi_{j}-\xi_{i})^{2} a.s. for \left|\xi_{j}-\xi_{i}\right|\leqslant\delta_{0} . This implies that there exists \alpha=1/\sqrt{c^{*}} such that d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})>h_{n}^{2} whenever \alpha h_{n}<\left|\xi_{j}-\xi_{i}\right|\leqslant\delta_{0} (notice that \alpha h_{n}<\delta_{0} for large enough n ). At the same, by Assumption 4 ( ii ), time, for large enough n , d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})>h_{n}^{2} a.s. for \left|\xi_{i}-\xi_{j}\right|\geqslant\delta_{0} . Hence, we conclude that \left|\xi_{j}-\xi_{i}\right|>\alpha h_{n} implies d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})>h_{n}^{2} and, by Assumption 5 ( i ), K\left({d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})}/{h_{n}^{2}}\right)=0 . Similarly, since c^{*}<\underline{c} , \left|\xi_{j}-\xi_{i}\right|>\alpha h_{n} also implies c_{ij}(\xi_{j}-\xi_{j})^{2}>h_{n}^{2} and K\left({c_{ij}(\xi_{j}-\xi_{i})^{2}}/{h_{n}^{2}}\right)=0 a.s. This completes the proof of part (i). Clearly, we can also choose \alpha such that d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})>ch_{n}^{2} for some c>1 whenever \left|\xi_{j}-\xi_{i}\right|>\alpha h_{n} . Consequently, for all pairs of agents i and j satisfying \left|\xi_{j}-\xi_{i}\right|>\alpha h_{n} , we have {d_{ij}^{2}}/{h_{n}^{2}}>c>1 . Using ( 4.1 ) and Assumption 5 ( ii ), we also conclude that, for all pairs of agents i and j satisfying that \left|\xi_{j}-\xi_{i}\right|>\alpha h_{n} , with probability approaching one we also have {\hat{d}^{2}_{ij}}/{h_{n}^{2}}>1 . Combining this with Assumption 5 ( i ) completes the proof of part (ii). Finally, notice that using the result of part (i), we obtain \displaystyle r_{K}(X_{i},X_{j},\xi_{i},\xi_{j};h_{n})=\left(K\left(\frac{d^{2}(X_{i},X_{j},\xi_{i},\xi_{j})}{h_{n}^{2}}\right)-K\left(\frac{c_{ij}(\xi_{j}-\xi_{i})^{2}}{h_{n}^{2}}\right)\right)\mathbbm{1}\{|\xi_{j}-\xi_{i}|\leqslant\alpha h_{n}\}. Combining this with Assumptions 4 ( iii ) and 5 ( i ) delivers the required bound. Q.E.D. Lemma A.2 . Suppose the hypotheses of Theorem 1 are satisfied. Then, for any \alpha>0 , we have: (i) h_{n}^{-1}\mathbb{E}\left[\mathbbm{1}\{\left|\xi_{j}-\xi_{i}\right|\leqslant\alpha h_{n}\}|\xi_{i}\right]\leqslant C_{\alpha} a.s. and, hence, h_{n}^{-1}\mathbb{E}\left[\mathbbm{1}\{\left|\xi_{j}-\xi_{i}\right|\leqslant\alpha h_{n}\}\right]\leqslant C_{\alpha} for some C_{\alpha}>0 ; (ii) \binom{n}{2}^{-1}h_{n}^{-1}\sum_{iC>0 ; (ii) \hat{B}_{n}=O_{p}(h_{n}^{2}+\frac{R_{n}^{-1}}{h_{n}}+n^{-1}) ; (iii) \hat{C}_{n}=O_{p}(\frac{R_{n}^{-1}}{h_{n}^{2}}\left(\frac{\ln n}{n}\right)^{1/2}+n^{-1}) , together delivering the desired result. For simplicity of exposition and consistency with the assumptions provided in Section 4.1 , we prove the result for d_{\xi}=1 . For d_{\xi}>1 and with the assumptions appropriately modified as discussed in Remark 4.2 , the proof of the theorem remains essentially the same with the exceptions that (i) \hat{A}_{n} , \hat{B}_{n} , and \hat{C}_{n} should be normalized by h_{n}^{-d_{\xi}} instead of h_{n}^{-1} , and (ii) all the quantities in the statements of Lemma A.2 should be normalized by h_{n}^{-d_{\xi}} instead of h_{n}^{-1} . A.1.3 Demonstrating consistency of \hat{A}_{n} In this section, we argue that \hat{A}_{n}=A+o_{p}(1) , where A is a symmetric invertible matrix. In particular, first, we argue that \hat{A}_{n}-A_{n}=o_{p}(1) , where \displaystyle A_{n}\coloneqq\binom{n}{2}^{-1}h_{n}^{-1}\sum_{iC for some C>0 by Assumption 4 ( i ), which completes the proof. A.1.4 Bounding \hat{B}_{n} First, we introduce the following notations and prove an auxiliary lemma stated below. \displaystyle q_{n}(Z_{i},Z_{j},Z_{k}) \displaystyle\coloneqq h_{n}^{-1}K\left(\frac{d^{2}(Z_{i},Z_{j})}{h_{n}^{2}}\right)(W(X_{i},X_{k})-W(X_{j},X_{k}))(g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})), \displaystyle p_{n}(Z_{i},Z_{j},Z_{k}) \displaystyle\coloneqq\frac{1}{3}(q_{n}(Z_{i},Z_{j},Z_{k})+q_{n}(Z_{k},Z_{i},Z_{j})+q_{n}(Z_{j},Z_{k},Z_{i})), (A.1) Lemma A.3 . Suppose that the hypotheses of Theorem 1 are satisfied. Then, (i) b_{n}\coloneqq\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})\right]=O(h_{n}^{2}) , and (ii) \zeta_{1,n}\coloneqq\mathbb{E}\left[\left\|\mathbb{E}\left[p_{n}(Z_{i},Z_{j},Z_{k})|Z_{i}\right]-b_{n}\right\|^{2}\right]=O(h_{n}^{3}) . Proof of Lemma A.3 . Before starting the proof, we introduce the following notations s_{n}^{(1)}(Z_{i})\coloneqq\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|Z_{i}\right]-b_{n} , s_{n}^{(2)}(Z_{i})\coloneqq\mathbb{E}\left[q_{n}(Z_{k},Z_{i},Z_{j})|Z_{i}\right]-b_{n} , and s_{n}^{(3)}(Z_{i})\coloneqq\mathbb{E}\left[q_{n}(Z_{j},Z_{k},Z_{i})|Z_{i}\right]-b_{n} , so \displaystyle\mathbb{E}\left[p_{n}(Z_{i},Z_{j},Z_{k})|Z_{i}\right]-b_{n} \displaystyle=\frac{1}{3}\left(s_{n}^{(1)}(Z_{i})+s_{n}^{(2)}(Z_{i})+s_{n}^{(3)}(Z_{i})\right), \displaystyle\zeta_{1,n}^{2} \displaystyle=\frac{1}{9}\mathbb{E}\left[\left\|s_{n}^{(1)}(Z_{i})+s_{n}^{(2)}(Z_{i})+s_{n}^{(3)}(Z_{i})\right\|^{2}\right]. (A.2) First, let us compute E_{q}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})\coloneqq\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|X_{i},\xi_{i},X_{j},Z_{k}\right] . Note that \displaystyle E_{q}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})= \displaystyle\underbrace{\mathbb{E}\left[h_{n}^{-1}K\left(\frac{c_{ij}(\xi_{j}-\xi_{i})^{2}}{h_{n}^{2}}\right)(W_{ik}-W_{jk})(g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k}))|X_{i},\xi_{i},X_{j},Z_{k}\right]}_{\coloneqq E_{q,2(X_{i},\xi_{i},X_{j},Z_{k};h_{n})}} \displaystyle+\underbrace{\mathbb{E}\left[h_{n}^{-1}r_{K}(Z_{i},Z_{j};h_{n})(W_{ik}-W_{jk})(g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k}))|X_{i},X_{j},\xi_{i}\right]}_{\coloneqq r_{E_{q}}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})}, where r_{K} is defined in Lemma A.1 . Combining Lemma A.1 (iii), boundedness of W , Assumption 2 ( iii ), and Lemma A.2 (i), we conclude that there exists C>0 such that \left|r_{E_{q}}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})\right|\leqslant Ch_{n}^{2} a.s. Next, we compute E_{q,2}(X_{i},\xi_{i},X_{j},Z_{k};h_{n}) . We start with considering \xi_{i} and \xi_{k} such that \left|\xi_{i}-\xi_{k}\right|>\alpha h_{n} . Using Lemma A.1 (i), Assumption 6 , and boundedness of W , we obtain \displaystyle\bigg\|K\left(\frac{c_{ij}(\xi_{j}-\xi_{i})^{2}}{h_{n}^{2}}\right)(W_{ik}-W_{jk})(\underbrace{g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})-G(\xi_{i},\xi_{k})(\xi_{i}-\xi_{j})}_{r_{g}(\xi_{i},\xi_{j},\xi_{k})})\bigg\|\leq Ch_{n}^{2}\mathbbm{1}\{\left|\xi_{j}-\xi_{i}\right|\leqslant\alpha h_{n}\} for some C>0 for all (Z_{i},Z_{j},Z_{k}) satisfying \left|\xi_{i}-\xi_{k}\right|>\alpha h_{n} . Then, using Lemma A.2 (i), \displaystyle E_{q,2}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})= \displaystyle\underbrace{\mathbb{E}\left[h_{n}^{-1}K\left(\frac{c_{ij}(\xi_{j}-\xi_{i})^{2}}{h_{n}^{2}}\right)(W_{jk}-W_{ik})G(\xi_{i},\xi_{k})(\xi_{j}-\xi_{i})|X_{i},\xi_{i},X_{j},Z_{k}\right]}_{\coloneqq E_{q,l}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})} \displaystyle+r_{E_{q,2}}(X_{i},\xi_{i},X_{j},Z_{k};h_{n}), where \left|r_{E_{q,2}}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})\right|\leqslant Ch_{n}^{2} a.s. for some C>0 for \left|\xi_{i}-\xi_{k}\right|>\alpha h_{n} . Next, consider \displaystyle E_{q,l}(X_{i},\xi_{i},X_{j},Z_{k};h_{n}) \displaystyle=(W_{jk}-W_{ik})G(\xi_{i},\xi_{k})\int h_{n}^{-1}K\left(\frac{c_{ij}(\xi_{j}-\xi_{i})^{2}}{h_{n}^{2}}\right)(\xi_{j}-\xi_{i})f_{\xi|X}(\xi_{j};X_{j})d\xi_{j} \displaystyle=\frac{h_{n}(W_{jk}-W_{ik})G(\xi_{i},\xi_{k})}{{c_{ij}}}\int K(u^{2})uf_{\xi|X}(\xi_{i}+h_{n}u/\sqrt{c_{ij}};X_{j})du, where the last equality follows from the change of the variable \xi_{j}=\xi_{i}+h_{n}u/\sqrt{c_{ij}} . Note \displaystyle\left|\int K(u^{2})uf_{\xi|X}(\xi_{i}+h_{n}u/\sqrt{c_{ij}};X_{j})du\right| \displaystyle\leqslant \displaystyle\int\left|K(u^{2})u\left(f_{\xi|X}(\xi_{i}+h_{n}u/\sqrt{c_{ij}};X_{j})-f_{\xi|X}(\xi_{i};X_{j})\right)\right|du\leqslant\frac{\overline{K}C_{\xi}h_{n}}{\sqrt{c_{ij}}} (A.3) where the first inequality used \int uK(u^{2})du=0 and the triangle inequality, and the second inequality holds for all \xi_{i} such that f_{\xi|X}(\cdot;X_{j}) is continuous on B_{h_{n}u/\sqrt{c_{ij}}}(\xi_{i}) thanks to Assumptions 3 ( iii ) and 5 ( i ). ( A.3 ) together with boundedness of W , G and c_{ij}^{-1} (Assumptions 2 ( i ), 6 , and 4 ( iii ), respectively) implies that there exists a uniform constant C such that \left|E_{q,l}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})\right|\leqslant Ch_{n}^{2} almost surely for all Z_{i} , Z_{j} , and Z_{k} such that \left|\xi_{i}-\xi_{k}\right|>\alpha h_{n} and f_{\xi|X}(\cdot;X_{j}) is continuous on B_{h_{n}u/\sqrt{c_{ij}}}(\xi_{i}) . Combining this with the previously obtained bounds on r_{E_{q}} and r_{E_{q,2}} , we conclude that there exists a uniform constant C>0 such that (for sufficiently large n ) \displaystyle\left|E_{q}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})\right|\leqslant Ch_{n}^{2} (A.4) almost surely for all Z_{i} , Z_{j} , and Z_{k} such that \left|\xi_{i}-\xi_{k}\right|>\alpha h_{n} and f_{\xi|X}(\cdot;X_{j}) is continuous on B_{h_{n}u/\sqrt{c_{ij}}}(\xi_{i}) . Moreover, for all (Z_{i},Z_{j},Z_{k}) without additional qualifiers, we also have \displaystyle\left|E_{q}(X_{i},\xi_{i},X_{j},Z_{k};h_{n})\right|\leqslant Ch_{n}, (A.5) for some C>0 . To inspect ( A.5 ), note \left\|q_{n}(Z_{i},Z_{j},Z_{k})\right\|\leqslant C\mathbbm{1}\{\left|\xi_{j}-\xi_{i}\right|\leqslant\alpha h_{n}\} a.s. for some C>0 thanks to Lemma A.1 (i) and Assumptions 2 ( i ) and ( iii ), and apply Lemma A.2 (i). Equipped with the bounds ( A.4 ) and ( A.5 ), now we want to bound b_{n}=\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})\right] . We start with considering \mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|Z_{i}\right] . Since c_{ij}>\underline{c}>0 (Assumption 4 ( iii )), Assumption 3 ( ii ) guarantees that there exists \gamma_{1}>0 such that the probability mass of \xi_{i} such that f_{\xi|X}(\cdot;X_{j}) is continuous on B_{h_{n}u/\sqrt{c_{ij}}}(\xi_{i}) is at least 1-\gamma_{1}h_{n} irrespectively of the values of X_{i} and X_{j} . Also, by Assumption 3 ( i ), the probability mass of \xi_{k} such that \left|\xi_{k}-\xi_{i}\right|>\alpha h_{n} is at least 1-\gamma_{2}h_{n} irrespectively of the value of \xi_{i} for some \gamma_{2}>0 . For such values of \xi_{i} and \xi_{k} , the bound ( A.4 ) applies. Moreover, the bound ( A.5 ) applies with probability one. Hence, integrating E_{q}(X_{i},\xi_{i},X_{j},Z_{k};h_{n}) over (X_{j},Z_{k}) ensures that there exists C>0 such that \left\|\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|Z_{i}\right]\right\|\leqslant Ch_{n}^{2} for all \xi_{i} such that f_{\xi|X}(\cdot;X_{j}) is continuous on B_{h_{n}u/\sqrt{c_{ij}}}(\xi_{i}) , which happens with probability 1-\gamma_{1}h_{n} at least. Moreover, ( A.5 ) immediately implies that \left\|\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|Z_{i}\right]\right\|\leqslant Ch_{n} with probability one. Combining these bounds and integrating over Z_{i} gives \displaystyle\left\|\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{j})\right]\right\|\leqslant\mathbb{E}\left[\left\|{\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{j})|Z_{i}\right]}\right\|\right]\leqslant(1-\gamma_{1}h_{n})\times Ch_{n}^{2}+\gamma_{1}h_{n}\times Ch_{n}=O(h_{n}^{2}), which completes the proof of the first statement of the lemma. To prove the second statement of the lemma, thanks to ( A.2 ), it is sufficient to verify that \mathbb{E}[{\|{s_{n}^{(\ell)}(Z_{i})}\|^{2}}]=O(h_{n}^{3}) for \ell\in\{1,2,3\} . We start with \ell\in\{1,2\} . By the same bounds on \left\|\mathbb{E}\left[{q_{n}(Z_{i},Z_{j},Z_{j})}|Z_{i}\right]\right\| as established above and b_{n}=O(h_{n}^{2}) , the following holds: (i) for some C>0 and \gamma_{1}>0 , we have \|{s_{n}^{(1)}(Z_{i})}\|^{2}\leqslant Ch_{n}^{4} with probability at least 1-\gamma_{1}h_{n} and \|{s_{n}^{(1)}(Z_{i})}\|^{2}\leqslant Ch_{n}^{2} with probability one. Hence, \mathbb{E}[{\|{s_{n}^{(1)}(Z_{i})}\|^{2}}]=\mathbb{E}[{\|{s_{n}^{(2)}(Z_{i})}\|^{2}}]\leqslant Ch_{n}^{3} for some C>0 . Finally, notice we can write s_{n}^{(3)}(Z_{k})=\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|Z_{k}\right]-b_{n} . Again, for a fixed \xi_{k} , the bound ( A.4 ) applies for all \xi_{i} satisfying (i) \left|\xi_{k}-\xi_{i}\right|>\alpha h_{n} and (ii) f_{\xi|X}(\cdot;X_{j}) is continuous on B_{h_{n}u/\sqrt{c_{ij}}}(\xi_{i}) . By the same reasoning as above, the probability mass of such \xi_{i} is at least 1-\gamma_{3}h_{n} for some \gamma_{3}>0 irrespectively of (X_{i},X_{j},Z_{k}) . At the same time, the bound ( A.5 ) applies with probability one. Hence, integrating E_{q}(X_{i},\xi_{i},X_{j},Z_{k};h_{n}) over (X_{i},\xi_{i},X_{j}) gives \left\|\mathbb{E}\left[q_{n}(Z_{i},Z_{j},Z_{k})|Z_{k}\right]\right\|\leqslant Ch_{n}^{2} a.s. for some C>0 . This, paired with b_{n}=O(h_{n}^{2}) , implies that \mathbb{E}[\|{{s_{n}^{(3)}(Z_{k})}}\|^{2}]=\mathbb{E}[\|{{s_{n}^{(3)}(Z_{i})}}\|^{2}]\leqslant Ch_{n}^{4} , which completes the proof. Q.E.D. Bounding \hat{B}_{n} Equipped with Lemma A.3 , we are now ready to bound \hat{B}_{n} . The first step of the proof is to bound B_{n} defined as \displaystyle B_{n} \displaystyle\coloneqq\binom{n}{2}^{-1}h_{n}^{-1}\sum_{i0 . To this end, we first show that \max_{i\neq k}\left\|\hat{\omega}_{n,ik}-\omega_{n,ik}\right\|=o_{p}(1) and then we verify that \max_{i\neq k}\left\|\omega_{n,ik}\right\|0 , where \displaystyle\omega_{n,ik}\coloneqq\underbrace{\mathbb{E}\left[K_{n,ij}(W_{ik}-W_{jk})|Z_{i},Z_{k}\right]}_{\coloneqq\kappa_{n,ik}}+\underbrace{\mathbb{E}\left[K_{n,kj}(W_{ik}-W_{ji})|Z_{i},Z_{k}\right]}_{\coloneqq\eta_{n,ik}}. Uniform consistency of \hat{\omega}_{n,ik} would follow from uniform consistency of \hat{\kappa}_{n,ik} and \eta_{n,ik} to \kappa_{n,ik} and \eta_{n,ik} , respectively. Next, we will establish this result for \hat{\kappa}_{n,ik} noting that the analogous result for \hat{\eta}_{n,ik} follows by the same argument. Note that, conditional on Z_{i} and Z_{k} , \{K_{n,ij}(W_{ik}-W_{jk})\}_{j\neq i,k} is a collection of bounded (given the sample size) independent variables with \left\|K_{n,ij}\left(W_{ik}-W_{jn}\right)\right\|\leqslant Ch_{n}^{-1} and \mathbb{E}\left[\left\|K_{n,ij}\left(W_{ik}-W_{jn}\right)\right\|^{2}|Z_{i},Z_{k}\right]\leqslant Ch_{n}^{-1} for all Z_{i} and Z_{k} for some C>0 , where we used boundedness of W and K combined with Lemmas A.1 (i) and A.2 (i). Hence, applying Bernstein inequality A.1 , we conclude that there exist positive constants a , b , and C such that for all Z_{i},Z_{k} and \epsilon>0 we have \displaystyle\mathbb{P}\left(\left\|\hat{\kappa}_{n,ik}-\kappa_{n,ik}\right\|\geqslant\epsilon|Z_{i},Z_{k}\right) \displaystyle\leqslant C\exp\left(-\frac{(n-2)h_{n}\epsilon^{2}}{a+b\epsilon}\right), \displaystyle\mathbb{P}\left(\max_{i\neq k}\left\|\hat{\kappa}_{n,ik}-\kappa_{n,ik}\right\|\geqslant\epsilon\right) \displaystyle\leqslant\binom{n}{2}C\exp\left(-\frac{(n-2)h_{n}\epsilon^{2}}{a+b\epsilon}\right)\rightarrow 0, where the second inequality follows from the union bound, and the convergence follows from Assumption 5 ( ii ). Hence, \hat{\kappa}_{n,ik} , and, consequently, \hat{\omega}_{n,ik} are uniformly consistent for \kappa_{n,ik} , and \omega_{n,ik} , respectively. Finally, using the boundedness of W and K and Lemmas A.1 (i) and A.2 (i) again, we conclude that \max_{i\neq k}\left\|\omega_{n,ik}\right\|\leq C for some C>0 , which delivers the desired result for \hat{\omega}_{n,ik} . We are now ready to bound C_{n} using that \max_{i\neq k}\left\|\hat{\omega}_{n,ik}\right\|0 , \displaystyle\mathbb{P}\left(\left\|C_{n}\right\|>\epsilon|\{X_{i},\xi_{i}\}_{i=1}^{n}\right)\leqslant C\exp\left(-\frac{\binom{n}{2}\epsilon^{2}}{a+b\epsilon}\right). Since the requirement \max_{i\neq k}\left\|\hat{\omega}_{n,ik}\right\|0 \displaystyle\mathbb{P}\left(\left\|\frac{1}{n-2}\sum_{k\neq i,j}(W_{ik}-W_{jk})(\varepsilon_{ik}-\varepsilon_{jk})\right\|>\epsilon|\{Z_{i}\}_{i=1}^{n}\right) \displaystyle\leqslant C_{2}\exp\left(-\frac{(n-2)\epsilon^{2}}{a_{2}+b_{2}\epsilon}\right), \displaystyle\mathbb{P}\left(\max_{i\neq j}\left\|\frac{1}{n-2}\sum_{k\neq i,j}(W_{ik}-W_{jk})(\varepsilon_{ik}-\varepsilon_{jk})\right\|>\epsilon\right) \displaystyle\leqslant\binom{n}{2}C_{2}\exp\left(-\frac{(n-2)\epsilon^{2}}{a_{2}+b_{2}\epsilon}\right), where the second inequality uses the union bound and the uniformity of those constants over \{Z_{i}\}_{i=1}^{n} . Hence, we have \max_{i\neq j}\|{\frac{1}{n-2}\sum_{k\neq i,j}(W_{ik}-W_{jk})(\varepsilon_{ik}-\varepsilon_{jk})}\|=O_{p}\left(\left(\frac{\ln n}{n}\right)^{1/2}\right) implying \displaystyle\left\|\Delta\hat{C}_{n}\right\|\leqslant\binom{n}{2}^{-1}h_{n}^{-1}\sum_{i0 and (almost) all Z_{i} and Z_{j} , we have \displaystyle\mathbb{P}\left(\left\|\frac{1}{n-2}\sum_{k\neq i,j}(W_{ik}-W_{jk})(W_{ik}-W_{jk})^{\prime}-\mathcal{C}(X_{i},X_{j})\right\|>\epsilon|Z_{i},Z_{j}\right)\leqslant C\exp\left(-\frac{(n-2)\epsilon^{2}}{a+b\epsilon}\right). Since a , b , and C are uniform over Z_{i} and Z_{j} , applying the union bound, we have \displaystyle\mathbb{P}\left(S_{1}>\epsilon\right)\leqslant\binom{n}{2}C\exp\left(-\frac{(n-2)\epsilon^{2}}{a+b\epsilon}\right), which implies S_{1}=O_{p}\left(({\ln n}/{n})^{1/2}\right) . The same argument can be applied to inspect that S_{\ell}=O_{p}\left(({\ln n}/{n})^{1/2}\right) for \ell\in\{2,3\} , which together with ( A.8 ) delivers the desired result for d_{ij,n-2}^{2} . Essentially the same argument applies to demonstrate the result for d_{ij,n}^{2} . Q.E.D. Proof of Lemma 1 . Recall that under ( 2.5 ), q_{ij}^{2}(\beta)=d_{ij}^{2}(\beta)+2\sigma^{2} . First, we show that \displaystyle\max_{i\neq j}\max_{\beta\in\mathcal{B}}\left|\hat{q}_{ij}^{2}(\beta)-q_{ij}^{2}(\beta)\right|=\max_{i\neq j}\max_{\beta\in\mathcal{B}}\left|\hat{q}_{ij}^{2}(\beta)-d_{ij}^{2}(\beta)-2\sigma^{2}\right|=O_{p}\left(({\ln n}/{n})^{1/2}\right). (A.9) Next, \hat{q}_{ij}^{2}(\beta) can be decomposed as \displaystyle\hat{q}_{ij}^{2}(\beta)= \displaystyle\underbrace{\frac{1}{n-2}\sum_{k\neq i,j}\left(Y_{ik}^{*}-Y_{jk}^{*}-(W_{ik}-W_{jk})^{\prime}\beta\right)^{2}}_{d_{ij,n-2}^{2}(\beta)}+\underbrace{\frac{1}{n-2}\sum_{k\neq i,j}(\varepsilon_{ik}-\varepsilon_{jk})^{2}}_{\coloneqq 2\hat{\sigma}^{2}_{ij}} \displaystyle+\underbrace{\frac{2}{n-2}\sum_{k\neq i,j}\left((W_{ik}-W_{jk})^{\prime}(\beta_{0}-\beta)+g_{ik}-g_{jk}\right)(\epsilon_{ik}-\epsilon_{jk})}_{\coloneqq\hat{\Delta}_{ij}(\beta)}. Thanks to the result of Lemma A.4 (i), to verify ( A.9 ), it is sufficient to show that (i) \max_{i\neq j}\max_{\beta}|\hat{\Delta}_{ij}(\beta)|=O_{p}\left(({\ln n}/{n})^{1/2}\right) , and (ii) \max_{i\neq j}|2\hat{\sigma}^{2}_{ij}-2\sigma^{2}|=O_{p}\left(({\ln n}/{n})^{1/2}\right) . To inspect (i), recall that \max_{i\neq j}\|{\frac{1}{n-2}\sum_{k\neq i,j}(W_{ik}-W_{jk})(\varepsilon_{ik}-\varepsilon_{jk})}\|=O_{p}\left(({\ln n}/{n})^{1/2}\right) has already been demonstrated in Section A.1.5 . By a nearly identical argument, we also have \max_{i\neq j}\left|\frac{1}{n-2}\sum_{k\neq i,j}\left(g_{ik}-g_{jk}\right)(\epsilon_{ik}-\epsilon_{jk})\right|=O_{p}\left(({\ln n}/{n})^{1/2}\right) . Together with boundedness of \mathcal{B} , these to convergence results imply that (i) holds. Next, to inspect (ii), note that, conditional on \{Z_{i},Z_{j}\} , \{\varepsilon_{ik}-\varepsilon_{jk}\}_{k\neq i,j} is a collection of iid sub-Gaussian random variables. Then Corollary A.1 guarantees that there exist some positive constants a , b , and C such that for all \epsilon>0 and (almost) all Z_{i} and Z_{j} \displaystyle\mathbb{P}\left(\left|\frac{1}{n-2}\sum_{k\neq i,j}\left((\varepsilon_{ik}-\varepsilon_{jk})^{2}-2\sigma^{2}\right)|Z_{i},Z_{j}\right|>\epsilon\right)\leqslant C\exp\left(-\frac{(n-2)\epsilon^{2}}{a+b\epsilon}\right). (A.10) Importantly, Assumption 2 ( iv ) guarantees that a , b , and C are uniform over Z_{i} and Z_{j} . Hence, (ii) following from turning ( A.10 ) into an analogous unconditional statement and combining it with the union bound. Inspecting (i) and (ii), completes the proof that ( A.9 ) holds. Finally, ( A.9 ), in turn, guarantees that \max_{i\neq j}\left|\hat{q}_{ij}^{2}-q_{ij}^{2}\right|=O_{p}\left(({\ln n}/{n})^{1/2}\right) , which completes the proof of the first part of the lemma. To prove the second part, note 2\hat{\sigma}^{2}=\min_{i\neq j}\hat{q}_{ij}^{2}=\min_{i\neq j}q_{ij}^{2}+O_{p}\left(({\ln n}/{n})^{1/2}\right) , and 2\sigma^{2}\leqslant\min_{i\neq j}q_{ij}^{2}\leqslant 2\sigma^{2}+\min_{i\neq j}\mathbb{E}\left[\left(g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})\right)^{2}|\xi_{i},\xi_{j}\right] . Note that Assumption 2 ( iii ) guarantees that \min_{i\neq j}\mathbb{E}\left[\left(g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})\right)^{2}|\xi_{i},\xi_{j}\right]\leqslant\overline{G}^{2}\min_{i\neq j}\left\|\xi_{i}-\xi_{j}\right\|^{2} , which delivers the result. Q.E.D. A.3 Proofs of the results of Section 4.2.2 A.3.1 Proof of Theorem 2 First, we state prove two auxiliary lemmas. Lemma A.5 . Suppose that the hypotheses of Theorem 2 are satisfied. Then, for any C>0 , there exists a_{C}>0 such that we have \min_{i}\frac{\left|\mathcal{B}_{i}(\delta_{n,C})\right|}{n-1}\geqslant C(n^{-1}\ln n)^{1/2} with probability approaching one, where \mathcal{B}_{i}(\delta)\coloneqq\{i^{\prime}\neq i:X_{i^{\prime}}=X_{i},\xi_{i^{\prime}}\in B_{\delta}(\xi_{i})\} , and \delta_{n,C}\coloneqq a_{C}(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}} . Proof of Lemma A.5 . Let p_{Z}(x,\xi;\delta)\coloneqq\mathbb{P}(X_{j}=x)\mathbb{P}(\xi_{j}\in B_{\delta}(\xi)|X_{j}=x) , \mathcal{Q}_{i}(\delta)\coloneqq\frac{\left|\mathcal{B}_{i}(\delta)\right|}{n-1} , and p_{r}\coloneqq\mathbb{P}(X=x_{r}) . Then, by Bernstein inequality A.1 , we have for all \epsilon\in(0,1) \displaystyle\mathbb{P}(\left|\mathcal{Q}_{i}(\delta)-p_{Z}(X_{i},\xi_{i};\delta)\right|\geqslant\epsilon|X_{i},\xi_{i})\leqslant 2\exp\left(-\frac{\frac{1}{2}(n-1)\epsilon^{2}}{1+\frac{1}{3}\epsilon}\right)\leqslant 2\exp\left(-\frac{1}{4}n\epsilon^{2}\right). Hence, we also have \mathbb{P}(\left|\mathcal{Q}_{i}(\delta)-p_{Z}(X_{i},\xi_{i};\delta)\right|\geqslant\epsilon)\leqslant 2\exp\left(-\frac{1}{4}n\epsilon^{2}\right) and, using the union bound, \mathbb{P}(\max_{i}\left|\mathcal{Q}_{i}(\delta)-p_{Z}(X_{i},\xi_{i};\delta)\right|\geqslant\epsilon)\leqslant 2n\exp\left(-\frac{1}{4}n\epsilon^{2}\right) . Hence, for any \tilde{C}>0 (and large enough n ), \mathbb{P}(\max_{i}\left|\mathcal{Q}_{i}(\delta)-p_{Z}(X_{i},\xi_{i};\delta)\right|\geqslant\tilde{C}(n^{-1}\ln n)^{1/2})\leqslant 2n^{1-\tilde{C}/4} . Using Assumption 7 ( ii ), for \delta\leqslant\overline{\delta} , we have p_{Z}(X_{i},\xi_{i};\delta)\geqslant\underline{\kappa}\delta^{d_{\xi}} a.s. where \underline{\kappa}=\kappa\min_{r}p_{r} . Then, we have \min p_{Z}(X_{i},\xi_{i};a(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}})\geqslant\underline{\kappa}a^{d_{\xi}}(n^{-1}\ln n)^{1/2} for \delta=a(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}} for a fixed a>0 and for large enough n . Hence, with probability at least 1-2n^{1-\tilde{C}/4} , we have \displaystyle\min_{i}\mathcal{Q}_{i}(a(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}})\geqslant(\underline{\kappa}a^{d_{\xi}}-\tilde{C})(n^{-1}\ln n)^{1/2}. (A.11) Take some fixed \tilde{C}>4 . In this case, ( A.11 ) holds with probability approaching one, and take any fixed a_{C}>\left(\underline{\kappa}^{-1}(C+\tilde{C})\right)^{1/d_{\xi}} . For such a_{C} , (\underline{\kappa}a^{d_{\xi}}-\tilde{C})(n^{-1}\ln n)^{1/2}>C(n^{-1}\ln n)^{1/2} . As a result, we conclude that with probability approaching one, we have \min_{i}\mathcal{Q}_{i}(a(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}})>C(n^{-1}\ln n)^{1/2} , which completes the proof. Q.E.D. Lemma A.6 . Suppose that the hypotheses of Theorem 2 are satisfied. Then we have: (i) \max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}n^{-1}\sum_{\ell}(Y_{i\ell}^{*}-Y_{i^{\prime}\ell}^{*})^{2}=O_{p}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right) ; (ii) \max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{k}\left|n^{-1}\sum_{\ell}Y_{k\ell}^{*}(Y_{i^{\prime}\ell}^{*}-Y_{i\ell}^{*})\right|=O_{p}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right) ; (iii) \max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\int(g(\xi_{i},\xi)-g(\xi_{i^{\prime}},\xi))^{2}dP_{\xi}(\xi)=O_{p}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right) . Proof of Lemma A.6 . Note that both statements of the lemma trivially hold when i=i^{\prime} . For this reason, below \max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})} should be read as \max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i}):i^{\prime}\neq i} . Proof of Part (i). First, take some C>\overline{C} , where \overline{C} is defined in the text of Theorem 2 . Lemma A.5 guarantees, that there exist some a_{C} and \delta_{n,C}=a_{C}(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}} such that with probability approaching one, we have \min_{i}\left|\mathcal{B}_{i}(\delta_{n,C})\right|\geqslant C(n\ln n)^{1/2} . Since we have \max_{i}n_{i}\leqslant\overline{C}(n\ln n)^{1/2}n_{i} holds with probability approaching one. For any agents i and i^{\prime}\in\mathcal{\hat{\mathcal{N}}}_{i}(n_{i}) , let k and k^{\prime} be two agents (other than i and i^{\prime} ) such that k\in\mathcal{B}_{i}(\delta_{n,C}) and k^{\prime}\in\mathcal{B}_{i^{\prime}}(\delta_{n,C}) (by Lemma A.5 , this happens simultaneously for all i and i^{\prime} with probability approaching one for large enough n ). By boundedness of Y^{*} and Assumption 2 ( iii ), for \mathcal{G}\coloneqq\left\|Y^{*}\right\|_{\infty}\overline{G} , we have \displaystyle|{n^{-1}\sum_{\ell}Y_{i\ell}^{*2}-n^{-1}\sum_{\ell}Y^{*}_{i\ell}Y^{*}_{k\ell}}|\leqslant\mathcal{G}\delta_{n,C},\quad|{n^{-1}\sum_{\ell}Y^{*}_{i^{\prime}\ell}Y^{*}_{i\ell}-n^{-1}\sum_{\ell}Y^{*}_{i^{\prime}\ell}Y^{*}_{k\ell}}|\leqslant\mathcal{G}\delta_{n,C}, \displaystyle|{n^{-1}\sum_{\ell}Y_{i^{\prime}\ell}^{*2}-n^{-1}\sum_{\ell}Y^{*}_{i^{\prime}\ell}Y^{*}_{k^{\prime}\ell}}|\leqslant\mathcal{G}\delta_{n,C},\quad|{n^{-1}\sum_{\ell}Y^{*}_{i\ell}Y^{*}_{i^{\prime}\ell}-n^{-1}\sum_{\ell}Y^{*}_{i\ell}Y^{*}_{k^{\prime}\ell}}|\leqslant\mathcal{G}\delta_{n,C} (A.12) with probability approaching one for all i , i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i}) . Then \displaystyle n^{-1}\sum_{\ell}(Y^{*}_{i\ell}-Y^{*}_{i^{\prime}\ell})^{2} \displaystyle\leqslant|{n^{-1}\sum_{\ell}Y_{i\ell}^{*2}-n^{-1}\sum_{\ell}Y^{*}_{i^{\prime}\ell}Y^{*}_{i\ell}}|+|{n^{-1}\sum_{\ell}Y_{i^{\prime}\ell}^{*2}-n^{-1}\sum_{\ell}Y^{*}_{i\ell}Y^{*}_{i^{\prime}\ell}}| \displaystyle\leqslant|{n^{-1}\sum_{\ell}(Y^{*}_{i\ell}-Y^{*}_{i^{\prime}\ell})Y^{*}_{k\ell}}|+|{n^{-1}\sum_{\ell}(Y^{*}_{i^{\prime}\ell}-Y^{*}_{i\ell})Y^{*}_{k^{\prime}\ell}}|+4\mathcal{G}\delta_{n,C}. Note that since Y^{*} is bounded, there exists \Delta>0 such that for all i , i^{\prime} , and k , \displaystyle|{n^{-1}\sum_{\ell}(Y^{*}_{i\ell}-Y^{*}_{i^{\prime}\ell})Y^{*}_{k\ell}}|\leqslant|{(n-3)^{-1}\sum_{\ell\neq i,i^{\prime},k}(Y^{*}_{i\ell}-Y^{*}_{i^{\prime}\ell})Y^{*}_{k\ell}}|+\frac{\Delta}{n}. (A.13) Moreover, as usual, combining Corollary A.1 with the union bound, we have \displaystyle r_{n}\coloneqq\max_{i\neq i^{\prime}\neq k}\left|\frac{\sum_{\ell\neq i,i^{\prime},k}(Y_{i\ell}-Y_{i^{\prime}\ell})Y_{k\ell}-\sum_{\ell\neq i,i^{\prime},k}(Y^{*}_{i\ell}-Y^{*}_{i^{\prime}\ell})Y^{*}_{k\ell}}{n-3}\right|=O_{p}\left(\left(\frac{\ln n}{n}\right)^{1/2}\right). (A.14) So, we have \displaystyle\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}n^{-1}\sum_{\ell}(Y_{i\ell}^{*}-Y_{i^{\prime}\ell}^{*})^{2}\leqslant\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{k\neq i,i^{\prime}}|{(n-3)^{-1}\sum_{\ell\neq i,i^{\prime},k}(Y_{i\ell}-Y_{i^{\prime}\ell})Y_{k\ell}}| \displaystyle+ \displaystyle\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{k^{\prime}\neq i,i^{\prime}}|{(n-3)^{-1}\sum_{\ell\neq i,i^{\prime},k}(Y_{i^{\prime}\ell}-Y_{i\ell})Y_{k^{\prime}\ell}}|+4\mathcal{G}\delta_{n,C}+\frac{2\Delta}{n}+2r_{n} \displaystyle= \displaystyle 2\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\hat{d}_{\infty}^{2}(i,i^{\prime})+O_{p}((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}), (A.15) where the last line uses the definitions of \hat{d}_{\infty}^{2}(i,i^{\prime}) and \delta_{n,C}=a_{C}(n^{-1}\ln n)^{\frac{1}{2d_{\xi}}} . Next, let \hat{d}_{\infty,*}^{2}(i,i^{\prime})\coloneqq\max_{k\neq i,i^{\prime}}|{(n-3)^{-1}\sum_{\ell\neq i,i^{\prime},k}(Y_{i\ell}^{*}-Y_{i^{\prime}\ell}^{*})Y_{k\ell}^{*}}| . For any i and i^{\prime} , ( A.14 ) guarantees that \max_{i}\max_{i^{\prime}\neq i}|{\hat{d}_{\infty}^{2}(i,i^{\prime})-\hat{d}_{\infty,*}^{2}(i,i^{\prime})}|=O_{p}\left((n^{-1}\ln n)^{1/2}\right) . Analogously to ( A.12 ), for all i and i^{\prime}\in\mathcal{B}_{i}(\delta_{n,C}) , we have \hat{d}_{\infty,*}^{2}(i,i^{\prime})\leqslant\mathcal{G}\delta_{n,C} and hence also \displaystyle\hat{d}_{\infty}^{2}(i,i^{\prime})\leqslant\mathcal{G}\delta_{n,C}+O_{p,n}\left((n^{-1}\ln n)^{1/2}\right). Then, by definition of \mathcal{N}_{i} and the fact that for all i we have n_{i}<\left|\mathcal{B}_{i}(\delta_{n,C})\right| with probability approaching one, we conclude \displaystyle\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\hat{d}_{\infty}^{2}(i,i^{\prime}) \displaystyle\leqslant\mathcal{G}\delta_{n,C}+O_{p,n}\left((n^{-1}\ln n)^{1/2}\right)=O_{p,n}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right), (A.16) which together with ( A.15 ) completes the proof of Part (i). Proof of Part (ii). We prove the result by bounding the quantity of interest for k\neq i,i^{\prime} and then for k=i (or k=i^{\prime} ). First, we consider k\neq i,i^{\prime} . Then, using ( A.13 ) and ( A.14 ), \displaystyle\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{k\neq i,i^{\prime}}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}(Y_{i^{\prime}\ell}^{*}-Y_{i\ell}^{*})}|=\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{k\neq i,i^{\prime}}|{(n-3)^{-1}\sum_{\ell\neq i,i^{\prime},k}Y_{k\ell}(Y_{i^{\prime}\ell}-Y_{i\ell})}| \displaystyle+ \displaystyle O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right)=\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\hat{d}_{\infty}^{2}(i,i^{\prime})+O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right)=O_{p,n}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right), (A.17) where the last equality uses ( A.16 ). To complete the proof, consider k=i (the case k=i^{\prime} is analogous). Then, as argued at the beginning of the proof of Part (i), for any pair agents i and i^{\prime} , there exist some \tilde{k}\in\mathcal{B}_{i}(\delta_{n,C}) (other than i and i^{\prime} ) with probability approaching one. Then, by boundedness of Y^{*} and Assumption 2 ( iii ), \displaystyle\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}|{n^{-1}\sum_{\ell}Y_{i\ell}^{*}(Y_{i^{\prime}\ell}^{*}-Y_{i\ell}^{*})}| \displaystyle=\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}|{n^{-1}\sum_{\ell}Y_{\tilde{k}\ell}^{*}(Y_{i^{\prime}\ell}^{*}-Y_{i\ell}^{*})}|+O(\delta_{n,C}) \displaystyle=O_{p,n}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right), where the second equality follows from ( A.17 ). This completes the proof of Part (ii). Proof of Part (iii). Recall that for i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i}) , we have Y_{i\ell}^{*}-Y_{i^{\prime}\ell}^{*}=g(\xi_{i},\xi_{\ell})-g(\xi_{i^{\prime}},\xi_{\ell}) . Hence, the result of Part (i) reads as \displaystyle\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}n^{-1}\sum_{\ell}(g(\xi_{i},\xi_{\ell})-g(\xi_{i^{\prime}},\xi_{\ell}))^{2}=O_{p}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right). (A.18) Applying Bernstein inequality A.1 conditional on \xi_{i} and \xi_{i^{\prime}} and the union bound, we obtain \displaystyle\max_{i,i^{\prime}}\Big|{n^{-1}\sum_{\ell}(g(\xi_{i},\xi_{\ell})-g(\xi_{i^{\prime}},\xi_{\ell}))^{2}-\int(g(\xi_{i},\xi)-g(\xi_{i^{\prime}},\xi))^{2}dP_{\xi}(\xi)}\Big|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right). (A.19) Finally, ( A.18 ) and ( A.19 ) together deliver the result. Q.E.D. Proof of Theorem 2 . Proof of Part (i). First, notice that \displaystyle n^{-1}\sum_{j}\left(\hat{Y}_{ij}^{*}-Y_{ij}^{*}\right)^{2}=n^{-1}\sum_{j}\left(\frac{\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}(Y_{i^{\prime}j}-Y_{ij}^{*})}{n_{i}}\right)^{2}\leq 2(\mathcal{S}_{i}+\mathcal{J}_{i}), (A.20) \displaystyle\mathcal{S}_{i}\coloneqq\frac{1}{n}\sum_{j}\left(\frac{\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}(Y_{i^{\prime}j}-Y_{i^{\prime}j}^{*})}{n_{i}}\right)^{2},\quad\mathcal{J}_{i}\coloneqq\frac{1}{n}\sum_{j}\left(\frac{\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}(Y_{i^{\prime}j}^{*}-Y_{ij}^{*})}{n_{i}}\right)^{2}. We start with bounding \mathcal{S}_{i} . Note that, for all i^{\prime} and j , Y_{i^{\prime}j}-Y_{i^{\prime}j}^{*}=\varepsilon_{i^{\prime}j} , with the convention \varepsilon_{i^{\prime}j}=-Y^{*}_{i^{\prime}i^{\prime}} when i^{\prime}=j . Then \mathcal{S}_{i} can be decomposed as follows \displaystyle\mathcal{S}_{i} \displaystyle=\frac{1}{nn_{i}^{2}}\sum_{j}\left(\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\varepsilon_{i^{\prime}j}^{2}+\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\sum_{i^{\prime\prime}\in\hat{\mathcal{N}}_{i}(n_{i}),i^{\prime\prime}\neq i^{\prime}}\varepsilon_{i^{\prime}j}\varepsilon_{i^{\prime\prime}j}\right) \displaystyle=\underbrace{\frac{1}{n_{i}^{2}}\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\frac{1}{n}\sum_{j}\varepsilon_{i^{\prime}j}^{2}}_{\coloneqq\mathcal{S}_{1i}}+\underbrace{\frac{1}{n_{i}^{2}}\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\sum_{i^{\prime\prime}\in\hat{\mathcal{N}}_{i}(n_{i}),i^{\prime\prime}\neq i^{\prime}}\frac{1}{n}\sum_{j}\varepsilon_{i^{\prime}j}\varepsilon_{i^{\prime\prime}j}}_{\coloneqq\mathcal{S}_{2i}}. First, \frac{1}{n}\sum_{j}\varepsilon_{i^{\prime}j}^{2}=\frac{1}{n}\sum_{j\neq i^{\prime}}\varepsilon_{i^{\prime}j}^{2}-\frac{Y_{i^{\prime}i^{\prime}}^{*}}{n} . Applying Corollary A.1 (conditional on Z_{i^{\prime}} ) and the union bound gives \max_{i^{\prime}}|{\frac{1}{n-1}\sum_{j\neq i^{\prime}}\varepsilon_{i^{\prime}j}^{2}-\sigma_{i^{\prime}}^{2}}|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right) , where \sigma_{i}^{2}\coloneqq\mathbb{E}\left[\varepsilon_{ij}^{2}|Z_{i}\right]\leqslant C a.s. by Assumption 2 ( iv ). Finally, since Y^{*} is bounded, we conclude \displaystyle\max_{i^{\prime}}\frac{1}{n}\sum_{j}\varepsilon_{i^{\prime}j}^{2}\leqslant C+O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right),\quad\max_{i}\mathcal{S}_{1i}\leqslant\frac{C}{n_{i}}+o_{p}(n_{i}^{-1}). (A.21) To bound \mathcal{S}_{2i} , note \frac{1}{n}\sum_{j}\varepsilon_{i^{\prime}j}\varepsilon_{i^{\prime\prime}j}=\frac{1}{n}\sum_{j\neq i^{\prime},i^{\prime\prime}}\varepsilon_{i^{\prime}j}\varepsilon_{i^{\prime\prime}j}-\frac{1}{n}(Y_{i^{\prime}i^{\prime}}^{*}\varepsilon_{i^{\prime\prime}i^{\prime}}+\varepsilon_{i^{\prime}i^{\prime\prime}}Y_{i^{\prime\prime}i^{\prime\prime}}^{*}) . First, as usual, applying Bernstein inequality A.2 (conditional on Z_{i^{\prime}} and Z_{i^{\prime\prime}} ) and the union bound gives \max_{i^{\prime}\neq i^{\prime\prime}}|{\frac{1}{n-2}\sum_{j\neq i^{\prime},i^{\prime\prime}}\varepsilon_{i^{\prime}j}\varepsilon_{i^{\prime\prime}j}}|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right) . Similarly, since \varepsilon_{i^{\prime}i^{\prime\prime}} ’s are (uniformly) sub-Gaussian, we have \max_{i^{\prime}\neq i^{\prime\prime}}\left|\frac{1}{n}\varepsilon_{i^{\prime}i^{\prime\prime}}\right|=O_{p}\left(n^{-1}(\ln n)^{1/2}\right) . Since Y^{*} is bounded, we conclude \displaystyle\max_{i^{\prime}\neq i^{\prime\prime}}|{\frac{1}{n}\sum_{j}\varepsilon_{i^{\prime}j}\varepsilon_{i^{\prime\prime}j}}|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right),\quad\max_{i}\left|\mathcal{S}_{2i}\right|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right). (A.22) Combining ( A.21 ) and ( A.22 ) gives \max_{i}\mathcal{S}_{i}=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right) . Finally, note \mathcal{J}_{i}\leqslant\frac{1}{n}\sum_{j}\frac{1}{n_{i}}\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}(Y_{i^{\prime}j}^{*}-Y_{ij}^{*})^{2}=\frac{1}{n_{i}}\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\frac{1}{n}\sum_{j}(Y_{i^{\prime}j}^{*}-Y_{ij}^{*})^{2} . Applying Lemma A.6 (i), we obtain \max_{i}\mathcal{J}_{i}=O_{p}\left((n^{-1}\ln n)^{\frac{1}{2d_{\xi}}}\right) . This, together with the bound on \mathcal{S}_{i} and ( A.20 ), delivers the desired result. Proof of Part (ii). First, notice that \displaystyle n^{-1}\sum_{\ell}Y_{k\ell}^{*}(\hat{Y}_{i\ell}^{*}-Y_{i\ell}^{*})=n_{i}^{-1}\sum_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\Big(n^{-1}\sum_{\ell}Y_{k\ell}^{*}(Y_{i^{\prime}\ell}^{*}-Y_{i\ell}^{*})+n^{-1}\sum_{\ell}Y_{k\ell}^{*}\varepsilon_{i^{\prime}\ell}\Big), \displaystyle\max_{k}\max_{i}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}(\hat{Y}_{i\ell}^{*}-Y_{i\ell}^{*})}|\leqslant\underbrace{\max_{i}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{k}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}(Y_{i^{\prime}\ell}^{*}-Y_{i\ell}^{*})}|}_{=O_{p}\left(\left(\frac{\ln n}{n}\right)^{\frac{1}{2d_{\xi}}}\right)}+\max_{k}\max_{i^{\prime}}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}\varepsilon_{i^{\prime}\ell}}|, where the bound on the first term on the right-hand side follows from Lemma A.6 (ii). To complete the proof, we need to to bound the second term, which can be represented as \displaystyle n^{-1}\sum_{\ell}Y_{k\ell}^{*}\varepsilon_{i^{\prime}\ell}=n^{-1}\sum_{\ell\neq k,i^{\prime}}Y_{k\ell}^{*}\varepsilon_{i^{\prime}\ell}+n^{-1}(Y_{kk}^{*}\varepsilon_{i^{\prime}k}+Y_{ki^{\prime}}^{*}\varepsilon_{i^{\prime}i^{\prime}}). (A.23) Again, applying Corollary A.1 (conditional on Z_{k} and Z_{i^{\prime}} ) and the union bound, we obtain \max_{k}\max_{i^{\prime}}|{n^{-1}\sum_{\ell\neq k,i^{\prime}}Y_{k\ell}^{*}\varepsilon_{i^{\prime}\ell}}|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right) . Similarly, since either \varepsilon_{i^{\prime}k} is (uniformly) sub-Gaussian (for i^{\prime}\neq k ) or is equal to -Y_{kk}^{*} (which is bounded), we have \max_{k}\max_{i^{\prime}}\left|n^{-1}Y_{kk}^{*}\varepsilon_{i^{\prime}k}\right|=O_{p}\left(n^{-1}(\ln n)^{1/2}\right) . Finally, since \varepsilon_{i^{\prime}i^{\prime}}=-Y_{i^{\prime}i^{\prime}}^{*} and Y^{*} is bounded, we have \max_{k}\max_{i^{\prime}}\left|n^{-1}Y_{ki^{\prime}}^{*}\varepsilon_{i^{\prime}i^{\prime}}\right|\leqslant C/n . These bounds, together with ( A.23 ), imply that \max_{k}\max_{i^{\prime}}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}\varepsilon_{i^{\prime}\ell}}|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right) , which completes the proof. Q.E.D. A.3.2 Proof of Theorem 3 First, we state and prove the following auxiliary lemma. Lemma A.7 . Suppose \mathcal{B}=\mathbb{R}^{p} . Then, under Assumptions 1 , 2 , 7 ( i ), we have \max_{i\neq j}\left|d_{ij,n}^{2}-d_{ij}^{2}\right|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}\right) , where d_{ij,n}^{2}\coloneqq\min_{\beta\in\mathbb{R}_{p}}d_{ij,n}^{2}(\beta) , and d_{ij,n}^{2}(\beta) is given by ( A.7 ). Proof of Lemma A.7 . First, we argue that there exists some compact \overline{\mathcal{B}} such that, for all pairs of agents, d_{ij,n}^{2}\coloneqq\min_{\beta\in\mathbb{R}^{p}}d_{ij,n}^{2}(\beta)=\min_{\beta\in\overline{\mathcal{B}}}d_{ij,n}^{2}(\beta) with probability approaching one. For all x,\tilde{x}\in\text{supp}\left(X\right) , let \Delta w(X_{k};x,\tilde{x})\coloneqq w(x,X_{k})-w(\tilde{x},X_{k}) and \displaystyle\hat{\mathcal{C}}(x,\tilde{x})\coloneqq\frac{1}{n}\sum_{k=1}^{n}\Delta w(X_{k};x,\tilde{x})\Delta w(X_{k};x,\tilde{x})^{\prime}=\sum_{r=1}^{R}\hat{p}_{r}H(x_{r};x,\tilde{x})^{\prime}, where \hat{p}_{r}=n^{-1}\sum_{k=1}^{n}\mathbbm{1}\{X_{k}=x_{r}\} and H(x_{r};x,\tilde{x})\coloneqq\Delta w(x_{r};x,\tilde{x})\Delta w(x_{r};x,\tilde{x})^{\prime} . Notice that since \text{supp}\left(X\right)=\{x_{1},\dots,x_{R}\} , there exists C_{\lambda}>0 such that the minimal non-zero eigenvalue of H(x_{r};x,\tilde{x}) is greater than C_{\lambda} uniformly over all x_{r},x,\tilde{x}\in\{x_{1},\dots,x_{R}\} . Formally, we have \lambda_{min,+}(H(x_{r};x,\tilde{x}))>C_{\lambda} for all x_{r},x,\tilde{x}\in\{x_{1},\dots,x_{R}\} such that H(x_{r};x,\tilde{x}) is non-zero, where \lambda_{min,+}(H) denotes the minimal positive eigenvalue of a positive semidefinite (non-zero) matrix H . Next, notice that there exists C_{p}>0 such that with probability approaching one, we have \min_{r}\hat{p}_{r}>C_{p} . Hence, we conclude that for some C_{\mathcal{C}}>0 we have, with probability approaching one, \lambda_{min,+}(\hat{\mathcal{C}}(x,\tilde{x}))>C_{\mathcal{C}} for all x,\tilde{x}\in\{x_{1},\dots,x_{R}\} such that \hat{\mathcal{C}}(x,\tilde{x}) is non-zero. Next, for all x,\tilde{x}\in\{x_{1},\dots,x_{R}\} , let \hat{O}(x,\tilde{x}) be an orthogonal matrix, which diagonalizes \hat{\mathcal{C}}(x,\tilde{x}) , i.e., \hat{O}(x,\tilde{x})\hat{\mathcal{C}}(x,\tilde{x})\hat{O}(x,\tilde{x})^{\prime}=\hat{\Lambda}(x,\tilde{x}) , where \hat{\Lambda}(x,\tilde{x}) is diagonal. Notice that non-zero elements \hat{\Lambda}(x,\tilde{x}) of are bounded away from zero by C_{\mathcal{C}} with probability approaching (uniformly over x,\tilde{x}\in\{x_{1},\dots,x_{R}\} ). Take any pair of agents i and j . Since \hat{O}(X_{i},X_{j})^{\prime}\hat{O}(X_{i},X_{j}) is an identity matrix, \displaystyle d_{ij,n}^{2} \displaystyle=\min_{\beta\in\mathbb{R}_{p}}\frac{1}{n}\sum_{k}(Y_{ik}^{*}-Y_{jk}^{*}-\Delta w(X_{k};X_{i},X_{j})^{\prime}\hat{O}(X_{i},X_{j})^{\prime}\hat{O}(X_{i},X_{j})\ \beta)^{2} \displaystyle=\min_{b\in\mathbb{R}_{p}}\frac{1}{n}\sum_{k}(Y_{ik}^{*}-Y_{jk}^{*}-\Delta w(X_{k};X_{i},X_{j})^{\prime}\hat{O}(X_{i},X_{j})^{\prime}b)^{2}, where the last equality follows from the change of the variable b=\hat{O}(X_{i},X_{j})\beta . The minimum is achieved at \displaystyle\hat{b}_{ij}=\left(\hat{\Lambda}(X_{i},X_{j})\right)^{+}\left(\hat{O}(X_{i},X_{j})n^{-1}\sum_{k}\Delta w(X_{k};X_{i},X_{j})(Y_{ik}^{*}-Y_{jk}^{*})\right), where + denotes the Moore–Penrose inverse. Notice that since the non-zero elements of diagonal matrix \hat{\Lambda}(X_{i},X_{j}) are bounded away from zero (uniformly in X_{i} and X_{j} ) with probability approaching one, we conclude that \max_{i\neq j}\lambda_{max}\left(\left(\hat{\Lambda}(X_{i},X_{j})\right)^{+}\right)<\overline{C}_{\Lambda} with probability approaching one. Since w and Y^{*} are bounded, we also have \max_{i\neq j}\left\|\hat{O}(X_{i},X_{j})n^{-1}\sum_{k}w(X_{k};X_{i},X_{j})(Y_{ik}^{*}-Y_{jk}^{*})\right\|0 , we have with probability approaching one \max_{i\neq j}\|{\hat{b}_{ij}}\|\leqslant C_{\beta} . Since b=\hat{O}(X_{i},X_{j})\beta , the minimum of d_{ij,n}^{2}(\beta) is achieved at \hat{\beta}_{ij}=\hat{O}(X_{i},X_{j})^{\prime}\hat{b}_{ij} , i.e., d_{ij,n}^{2}=d_{ij,n}^{2}(\hat{\beta}_{ij}) , and, with probability approaching one, we also have \max_{i\neq j}\|{\hat{\beta}_{ij}}\|\leqslant C_{\beta} . Then, if \overline{\mathcal{B}} includes all \beta such that \left\|\beta\right\|\leqslant C_{\beta} , we have d_{ij,n}^{2}=d_{ij,n}^{2}(\hat{\beta}_{ij})=\min_{\beta\in\overline{\mathcal{B}}}d_{ij,n}^{2}(\beta) . Such a compact set \overline{\mathcal{B}} clearly exists, the proof of the first part is complete. Second, note that by the same argument, we have d_{ij}^{2}=\min_{\beta\in\mathbb{R}_{p}}d_{ij}^{2}(\beta)=\min_{\beta\in\overline{\mathcal{B}}}d_{ij}^{2}(\beta) , where, without loss of generality, \overline{\mathcal{B}} can be taken the same as before. Finally, since \overline{\mathcal{B}} is compact, we can apply the result of Lemma A.4 , which guarantees that \max_{i\neq j}\sup_{\beta\in\overline{\mathcal{B}}}\left|d_{ij,n}^{2}(\beta)-d_{ij}^{2}(\beta)\right|=O_{p}\left((\ln n/n)^{1/2}\right) . This necessarily implies that \displaystyle O_{p}\left((\ln n/n)^{1/2}\right)=\max_{i\neq j}|{\min_{\beta\in\overline{\mathcal{B}}}d_{ij,n}^{2}(\beta)-\min_{\beta\in\overline{\mathcal{B}}}d_{ij}^{2}(\beta)}|=\max_{i\neq j}\left|d_{ij,n}^{2}-d_{ij}^{2}\right|, which completes the proof. Q.E.D. Proof of Theorem 3 . First, denote \displaystyle\mathbf{W}_{i-j}=\begin{pmatrix}(W_{i1}-W_{j1})^{\prime}\\ (W_{i2}-W_{j2})^{\prime}\\ \cdots\\ (W_{in}-W_{jn})^{\prime}\end{pmatrix},\quad\mathbf{Y}^{*}_{i-j}=\begin{pmatrix}Y^{*}_{i1}-Y^{*}_{j1}\\ Y^{*}_{i2}-Y^{*}_{j2}\\ \cdots\\ Y^{*}_{in}-Y^{*}_{jn}\end{pmatrix},\quad\hat{\mathbf{Y}}_{i-j}^{*}=\begin{pmatrix}\hat{Y}^{*}_{i1}-\hat{Y}^{*}_{j1}\\ \hat{Y}^{*}_{i2}-\hat{Y}^{*}_{j2}\\ \cdots\\ \hat{Y}^{*}_{in}-\hat{Y}^{*}_{jn}\end{pmatrix}. Then \displaystyle\hat{d}_{ij}^{2}=n^{-1}\left({\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}{\mathbf{Y}}_{i-j}^{*}+\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}{\mathbf{Y}}_{i-j}^{*}+{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}\Delta\hat{\mathbf{Y}}_{i-j}^{*}+\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}\Delta\hat{\mathbf{Y}}_{i-j}^{*}\right), where \Delta\hat{\mathbf{Y}}_{i-j}^{*}=\hat{\mathbf{Y}}_{i-j}^{*}-{\mathbf{Y}}_{i-j}^{*} and \mathbf{P}_{i-j}=\mathbf{I}_{n}-\mathbf{W}_{i-j}(\mathbf{W}_{i-j}^{\prime}\mathbf{W}_{i-j})^{+}\mathbf{W}_{i-j}^{\prime} , where + stands for the Moore–Penrose inverse. Note that n^{-1}{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}{\mathbf{Y}}_{i-j}^{*}=d_{ij,n}^{2} , where d_{ij,n}^{2} is as defined in Lemma A.7 , which ensures \max_{i\neq j}\left|d_{ij,n}^{2}-d_{ij}^{2}\right|=O_{p}((\ln n/n)^{1/2}) . Hence, to complete the proof, it would be sufficient to show that \max_{i\neq j}|{n^{-1}\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}{\mathbf{Y}}_{i-j}^{*}}|=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right) , and \max_{i\neq j}|{n^{-1}\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}\Delta\hat{\mathbf{Y}}_{i-j}^{*}}|=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right) . To inspect these, note \displaystyle\max_{i\neq j}|{n^{-1}\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}{\mathbf{Y}}_{i-j}^{*}}| \displaystyle\leqslant\max_{i\neq j}|{n^{-1}\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}{\mathbf{Y}}_{i-j}^{*}}|=\max_{i\neq j}|{n^{-1}\sum_{\ell}(Y_{i\ell}^{*}-Y_{j\ell}^{*})(\Delta\hat{Y}_{i\ell}^{*}-\Delta\hat{Y}_{j\ell}^{*})}| \displaystyle\leqslant 4\max_{k}\max_{i}|{n^{-1}\sum_{\ell}Y_{k\ell}^{*}(\hat{Y}_{i\ell}^{*}-Y_{i\ell}^{*})}|=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right), where the last equality follows from Theorem 2 (ii). Similarly, \displaystyle\max_{i\neq j}|{n^{-1}\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\mathbf{P}_{i-j}\Delta\hat{\mathbf{Y}}_{i-j}^{*}}| \displaystyle\leqslant\max_{i\neq j}|{n^{-1}\Delta\hat{\mathbf{Y}}_{i-j}^{*\prime}\Delta\hat{\mathbf{Y}}_{i-j}^{*}}|=\max_{i\neq j}|{n^{-1}\sum_{\ell}(\Delta\hat{Y}_{i\ell}^{*}-\Delta\hat{Y}_{j\ell}^{*})^{2}}| \displaystyle\leqslant 4\max_{i}n^{-1}\sum_{\ell}(\hat{Y}_{i\ell}^{*}-Y_{i\ell}^{*})^{2}=O_{p}\left(\left({\ln n}/{n}\right)^{\frac{1}{2d_{\xi}}}\right), where the last equality is due Theorem 2 (i), which completes the proof. Q.E.D. A.3.3 Proof of Lemma 2 Proof of Lemma 2 . Let \hat{d}_{ij}^{2}(\beta)\coloneqq\frac{1}{n}\sum_{k}(\hat{Y}_{ik}^{*}-\hat{Y}_{jk}^{*}-(W_{ik}-W_{jk})\beta)^{2} , so \hat{d}_{ij}^{2}=\min_{\beta\in\mathcal{B}}\hat{d}_{ij}^{2}(\beta) . \displaystyle\max_{i\neq j}|{\hat{d}_{ij}^{2}-d_{ij}^{2}}|=\max_{i\neq j}|{\min_{\beta\in\mathcal{B}}\hat{d}_{ij}^{2}(\beta)-\min_{\beta\in\mathcal{B}}d_{ij}^{2}(\beta)}|\leqslant 2\max_{i\neq j}\max_{\beta\in\mathcal{B}}|{\hat{d}_{ij}^{2}(\beta)-d_{ij}^{2}(\beta)}|. Hence, it suffices to show \max_{i\neq j}\max_{\beta\in\mathcal{B}}\|{\hat{d}_{ij}^{2}(\beta)-d_{ij}^{2}(\beta)}\|=O_{p}\left(\left({\ln n}/{n}\right)^{1/2}+\mathcal{R}_{n}^{-1/2}\right) . Let \Delta\hat{Y}_{ik}^{*}\coloneqq\hat{Y}_{ik}^{*}-Y_{ik}^{*} , and note that \hat{d}_{ij}^{2}(\beta)-d_{ij}(\beta) can be decomposed as \displaystyle\hat{d}_{ij}^{2}(\beta)-d_{ij}(\beta)=d_{ij,n}^{2}(\beta)-d_{ij}(\beta) \displaystyle+\frac{2}{n}\sum_{k}\left(Y_{ik}^{*}-Y_{jk}^{*}+(W_{ik}-W_{jk})^{\prime}\beta\right)(\Delta\hat{Y}_{ik}^{*}-\Delta\hat{Y}_{jk}^{*})+\frac{1}{n}\sum_{k}(\Delta\hat{Y}_{ik}^{*}-\Delta\hat{Y}_{jk}^{*})^{2}. (A.24) By the Cauchy-Schwartz inequality, \displaystyle\max_{i\neq j}\frac{1}{n}\sum_{k}(\Delta\hat{Y}_{ik}^{*}-\Delta\hat{Y}_{jk}^{*})^{2}\leqslant 4\max_{i}\frac{1}{n}\sum_{i}(\hat{Y}_{ik}^{*}-Y_{ik}^{*})^{2}=O_{p}(\mathcal{R}_{n}^{-1}), \displaystyle\max_{i\neq j}\max_{\beta\in\mathcal{B}}\left|\frac{1}{n}\sum_{k}(Y_{ik}^{*}-Y_{jk}^{*}+(W_{ik}-W_{jk})^{\prime}\beta)(\Delta\hat{Y}_{ik}^{*}-\Delta\hat{Y}_{jk}^{*})\right|\leqslant C\sqrt{\max_{i\neq j}\frac{1}{n}\sum_{k}(\Delta\hat{Y}_{ik}^{*}-\Delta\hat{Y}_{jk}^{*})^{2}}=O_{p}(\mathcal{R}_{n}^{-1/2}), where the second inequality guaranteed by the fact that Y^{*} , W , and \mathcal{B} are bounded. These bounds, paired with Lemma A.4 and ( A.23 ), deliver the result. Q.E.D. A.4 Proof of Theorem 4 Proof of Theorem 4 . First, we decompose \tilde{Y}_{ij}^{*} as \displaystyle\tilde{Y}_{ij}^{*} \displaystyle=\frac{1}{m_{ij}}\sum_{(i^{\prime},j^{\prime})\in\hat{\mathcal{M}}_{ij}}Y_{i^{\prime}j^{\prime}}=Y_{ij}^{*}+\frac{1}{m_{ij}}\sum_{(i^{\prime},j^{\prime})\in\hat{\mathcal{M}}_{ij}}\left((g(\xi_{i^{\prime}},\xi_{j^{\prime}})-g(\xi_{i},\xi_{j}))+\varepsilon_{i^{\prime}j^{\prime}}\right). To prove the result, it suffices to show that \max_{i,j}|{\frac{1}{m_{ij}}\sum_{(i^{\prime},j^{\prime})\in\hat{\mathcal{M}}_{ij}}(g(\xi_{i^{\prime}},\xi_{j^{\prime}})-g(\xi_{i},\xi_{j}))}| and \max_{i,j}|{\frac{1}{m_{ij}}\sum_{(i^{\prime},j^{\prime})\in\hat{\mathcal{M}}_{ij}}\varepsilon_{i^{\prime}j^{\prime}}}| are both o_{p}(1) . First, notice that Lemma A.6 (iii) combined with the hypotheses of the theorem implies that \max_{i}\max_{i^{\prime}\in\mathcal{\hat{\mathcal{N}}}_{i}(n_{i})}\left\|\xi_{i}-\xi_{i^{\prime}}\right\|=o_{p}(1) . Hence, Using Assumption 2 ( iii ), \displaystyle\max_{i,j}\Big|{\frac{1}{m_{ij}}\sum_{(i^{\prime},j^{\prime})\in\hat{\mathcal{M}}_{ij}}(g(\xi_{i^{\prime}},\xi_{j^{\prime}})-g(\xi_{i},\xi_{j}))}\Big| \displaystyle\leqslant\max_{i,j}\max_{i^{\prime}\in\hat{\mathcal{N}}_{i}(n_{i})}\max_{j^{\prime}\in\hat{\mathcal{N}}_{j}(n_{j})}\left|g(\xi_{i^{\prime}},\xi_{j^{\prime}})-g(\xi_{i},\xi_{j})\right| \displaystyle\leqslant 2\overline{G}\max_{i}\max_{i^{\prime}\in\mathcal{\hat{\mathcal{N}}}_{i}(n_{i})}\left\|\xi_{i}-\xi_{i^{\prime}}\right\|=o_{p}(1). Next, let \overline{\mathcal{M}} denote the set of all possible realizations of \hat{\mathcal{M}}_{ij} formed according to ( 4.12 ). Unlike \hat{\mathcal{M}}_{ij} , \overline{\mathcal{M}} is not random. Note that by construction \displaystyle\max_{i,j}\Bigg|{\frac{1}{m_{ij}}\sum_{(i^{\prime},j^{\prime})\in\hat{\mathcal{M}}_{ij}}\varepsilon_{i^{\prime}j^{\prime}}}\Bigg|\leqslant\max_{\mathcal{M}\in\overline{\mathcal{M}}}\Bigg|{\frac{1}{\left|\mathcal{M}\right|}\sum_{(i^{\prime},j^{\prime})\in\mathcal{M}}\varepsilon_{i^{\prime}j^{\prime}}}\Bigg|. (A.25) Note that, for \mathcal{M}\in\overline{\mathcal{M}} , \left|\mathcal{M}\right|\geqslant\underline{m}\coloneqq\underline{n}(\underline{n}-1)/2 , where \underline{n}=\min_{i}n_{i} . Applying Bernstein inequality A.2 conditional on \{X_{i},\xi_{i}\}_{i=1}^{n} and using uniform sub-Gaussianity of the errors, we conclude that there exist some positive constants C,a , and b such that for all \epsilon>0 and for all \mathcal{M}\in\overline{\mathcal{M}} \displaystyle\mathbb{P}\left(\left|\frac{1}{\left|\mathcal{M}\right|}\sum_{(i^{\prime},j^{\prime})\in\mathcal{M}}\varepsilon_{i^{\prime}j^{\prime}}\right|>\epsilon\right) \displaystyle\leqslant C\exp\left(-\frac{\left|\mathcal{M}\right|\epsilon^{2}}{a+b\epsilon}\right)\leqslant C\exp\left(-\frac{\underline{m}\epsilon^{2}}{a+b\epsilon}\right). (A.26) To apply the union bound, we need to bound the cardinality of \overline{\mathcal{M}} . Note that \left|\overline{\mathcal{M}}\right|\leqslant\left|\overline{\mathcal{N}}\right|^{2} , where \left|\overline{\mathcal{N}}\right| is the total number of possible realizations of \mathcal{\hat{N}}_{i}(n_{i}) also allowing for possible variability in n_{i} . For a given n_{i} , the number of possible realizations of \mathcal{\hat{N}}_{i}(n_{i}) is \binom{n}{n_{i}}\leqslant\binom{n}{\overline{n}} with \overline{n}=\max_{i}n_{i} , where we also used monotonicity of \binom{n}{k} for k\leqslant\lceil n/2\rceil . Hence, factoring in variability in n_{i} taking possible values from \underline{n} to \overline{n} , we conclude that \left|\overline{\mathcal{N}}\right|\leqslant\overline{n}^{2}\binom{n}{\overline{n}} . Thus, combining the union bound with ( A.26 ), we conclude \displaystyle\mathbb{P}\left(\max_{\mathcal{M}\in\overline{\mathcal{M}}}\left|\frac{1}{\left|\mathcal{M}\right|}\sum_{(i^{\prime},j^{\prime})\in\mathcal{M}}\varepsilon_{i^{\prime}j^{\prime}}\right|>\epsilon\right)\leqslant\overline{n}^{4}\binom{n}{\overline{n}}^{2}C\exp\left(-\frac{\underline{m}\epsilon^{2}}{a+b\epsilon}\right). (A.27) Since \binom{n}{\overline{n}}<(\frac{n\times e}{\overline{n}})^{\overline{n}} , we have \ln\left(\binom{n}{\overline{n}}\right)<\overline{n}\ln(n)<\overline{C}n^{1/2}(\ln n)^{3/2} for sufficiently large \overline{n} . Since \underline{m}>C_{m}n\ln n for some C_{m}>0 , we conclude that the probability in ( A.27 ) goes to zero for any fixed \epsilon>0 , which, together with ( A.25 ), completes the proof. Q.E.D. A.5 Proofs of the results of Section 5.1 Proof of Lemma 3 . The proof is by contradiction. Suppose that for some \mu_{ij}^{*}(x,\tilde{x})\neq\mathscr{h}(x,\tilde{x}) , we have \mathscr{d}_{ij}^{2}(x,\tilde{x})=\mathscr{d}_{ij}^{2}(\mu_{ij}^{*}(x,\tilde{x}),x,\tilde{x})=0 , which implies \displaystyle 0 \displaystyle=\mathbb{E}\left[\left(Y_{ik}^{*}-Y_{jk}^{*}+\mu_{ij}^{*}(x,\tilde{x})\right)^{2}|X_{i},\xi_{i},X_{j},\xi_{j},X_{k}=x\right] \displaystyle=\mathbb{E}\left[\left(-\mathscr{h}(x,\tilde{x})+g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})+\mu_{ij}^{*}(x,\tilde{x})\right)^{2}|X_{i},\xi_{i},X_{j},\xi_{j},X_{k}=x\right]. Since \mathcal{E}_{x,\tilde{x}}\subseteq\text{supp}\left(\xi_{k}|X_{k}=x\right) , the above implies \displaystyle g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})=\mathscr{h}(x,\tilde{x})-\mu_{ij}^{*}(x,\tilde{x})\neq 0 (A.28) for all \xi_{k}\in\text{supp}\left(\xi_{k}|X_{k}=x\right) . Next, consider \displaystyle\mathbb{E}\left[\left(Y_{ik}^{*}-Y_{jk}^{*}-\mu_{ij}^{*}(x,\tilde{x})\right)^{2}|X_{i},\xi_{i},X_{j},\xi_{j},X_{k}=\tilde{x}\right] \displaystyle= \displaystyle\mathbb{E}\left[\left(\mathscr{h}(x,\tilde{x})+g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})-\mu_{ij}^{*}(x,\tilde{x})\right)^{2}|X_{i},\xi_{i},X_{j},\xi_{j},X_{k}=\tilde{x}\right] \displaystyle\geqslant \displaystyle\mathbb{P}(\xi_{k}\in\mathcal{E}_{x,\tilde{x}}|X_{k}=\tilde{x})\mathbb{E}\left[\left(\mathscr{h}(x,\tilde{x})+g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})-\mu_{ij}^{*}(x,\tilde{x})\right)^{2}|X_{i},\xi_{i},X_{j},\xi_{j},X_{k}=\tilde{x},\xi_{k}\in\mathcal{E}_{x,\tilde{x}}\right] \displaystyle= \displaystyle 4\mathbb{P}(\xi_{k}\in\mathcal{E}_{x,\tilde{x}}|X_{k}=\tilde{x})(\mathscr{h}(x,\tilde{x})-\mu_{ij}^{*}(x,\tilde{x}))^{2}>0, (A.29) where the last equality follows from ( A.28 ), and the last inequality follows from ( A.28 ) and Assumption 8 ( ii ). Note that ( A.29 ) implies that \mathscr{d}_{ij}^{2}(x,\tilde{x})=\mathscr{d}_{ij}^{2}(\mu_{ij}^{*}(x,\tilde{x}),x,\tilde{x})>0 , which contradicts the initial hypothesis. Q.E.D. A.6 Bernstein inequalities In this section we specify the Bernstein inequalities, which we refer to in the proofs. A.6.1 Bernstein inequality for bounded random variables Theorem A.1 (Bernstein inequality; see, for example, 11 ) . Let Z_{1},\dots,Z_{n} be mean zero independent random variables. Assume there exists a positive constant M such that \left|Z_{i}\right|\leqslant M with probability one for each i . Also let \sigma^{2}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[Z_{i}^{2}\right] . Then, for all \epsilon>0 , we have \mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}Z_{i}\right|\geqslant\epsilon\right)\leqslant 2\exp\left(-\frac{n\epsilon^{2}}{2\left(\sigma^{2}+\frac{1}{3}M\epsilon\right)}\right) . A.6.2 Bernstein inequality for unbounded random variables Lemma A.8 (Moments of a sub-Gaussian random variable) . Let Z be a mean zero random variable satisfying \mathbb{E}\left[e^{\lambda Z}\right]\leqslant e^{v\lambda^{2}} for all \lambda\in\mathbb{R} , for some v>0 . Then for every integer q\geqslant 1 , we have \mathbb{E}\left[Z^{2q}\right]\leqslant q!(4v)^{q} . Proof of Lemma A.8 . See Theorem 2.1 in 16 . Q.E.D. Theorem A.2 (Bernstein inequality for unbounded random variables) . Let Z_{1},\dots,Z_{n} be independent random variables. Assume that there exist some positive constants \nu and c such that \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[Z_{i}^{2}\right]\leqslant\nu such that, for all integers q\geqslant 3 , \frac{1}{n}\sum\mathbb{E}\left[\left|Z_{i}\right|^{q}\right]\leqslant\frac{q!c^{q-2}}{2}\nu. Then, for all \epsilon>0 , we have \mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}(Z_{i}-\mathbb{E}\left[Z_{i}\right])\right|\geqslant\epsilon\right)\leqslant 2\exp\left(-\frac{n\epsilon^{2}}{2(\nu+c\epsilon)}\right) . Proof of Theorem A.2 . See Corollary 2.11 in 16 . Q.E.D. Specifically, we make use of the following corollary. Corollary A.1 . Let Z_{1},\dots,Z_{n} be mean zero independent random variables. Assume that there exists some v>0 such that \mathbb{E}\left[e^{\lambda Z_{i}}\right]\leqslant e^{v\lambda^{2}} for all \lambda\in\mathbb{R} and for all i\in\{1,\dots,n\} . Then, there exist some positive constants C , a , and b such that for all constants \alpha_{1} , …, \alpha_{n} satisfying \max_{i}\left|\alpha_{i}\right|<\overline{\alpha} and for all \epsilon>0 , \displaystyle\mathbb{P}\left(\left|n^{-1}\sum_{i=1}^{n}\alpha_{i}Z_{i}\right|\geqslant\epsilon\right)\leqslant C\exp\left(-\frac{n\epsilon^{2}}{a+b\epsilon}\right) and \displaystyle\mathbb{P}\left(\left|n^{-1}\sum_{i=1}^{n}\alpha_{i}\left(Z_{i}^{2}-\mathbb{E}\left[Z_{i}^{2}\right]\right)\right|\geqslant\epsilon\right)\leqslant C\exp\left(-\frac{n\epsilon^{2}}{a+b\epsilon}\right). Proof of Corollary A.1 . Follows from Lemma A.8 and Theorem A.2 . Q.E.D. Remark A.1 . Note that the constants C , a , and b depend on v and \overline{\alpha} only. Appendix B Illustration of Assumption 6 Suppose \xi is scalar and g(\xi_{i},\xi_{k})=\kappa\left|\xi_{i}-\xi_{k}\right| . Note that, as a function of \xi_{i} , g(\xi_{i},\xi_{k}) is non-differentiable at \xi_{i}=\xi_{k} . When \xi_{i},\xi_{j}\leqslant\xi_{k} , we have \displaystyle g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})=\kappa(\xi_{k}-\xi_{i})-\kappa(\xi_{k}-\xi_{j})=-\kappa(\xi_{i}-\xi_{j}). If \xi_{i},\xi_{j}\geqslant\xi_{k} , \displaystyle g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})=\kappa(\xi_{i}-\xi_{k})-\kappa(\xi_{j}-\xi_{k})=\kappa(\xi_{i}-\xi_{j}). So, we can take \displaystyle G(\xi_{i},\xi_{k})=\begin{cases}-\kappa,&\xi_{i}<\xi_{k}\\ \kappa,&\xi_{i}\geqslant\xi_{k}\end{cases}. Then, the remainder r_{g}(\xi_{i},\xi_{j},\xi_{k})=0 when \xi_{i},\xi_{j}\leqslant\xi_{k} or \xi_{i},\xi_{j}\geqslant\xi_{k} . However, if, for example, \xi_{i}\leqslant\xi_{k}\leqslant\xi_{j} , \displaystyle g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})=\kappa(2\xi_{k}-\xi_{i}-\xi_{j}). Since G(\xi_{i},\xi_{k})=-\kappa , \displaystyle g(\xi_{i},\xi_{k})-g(\xi_{j},\xi_{k})=-\kappa(\xi_{i}-\xi_{j})+2\kappa(\xi_{k}-\xi_{j})=G(\xi_{i},\xi_{k})(\xi_{i}-\xi_{j})+r_{g}(\xi_{i},\xi_{j},\xi_{k}), so r_{g}(\xi_{i},\xi_{j},\xi_{k})=2\kappa(\xi_{k}-\xi_{j}) when \xi_{i}\leqslant\xi_{k}\leqslant\xi_{j} . Clearly, in this case, the linearization remainder is no longer O(\left|\xi_{i}-\xi_{j}\right|^{2}) . Importantly, Assumption 6 allows for this possibility: the remainder r_{g} is bounded by C\delta_{n}^{2} only when \left|\xi_{i}-\xi_{k}\right|>\delta_{n} and \left|\xi_{j}-\xi_{i}\right|\leqslant\delta_{n} . Under these restrictions, \xi_{k} cannot lie between \xi_{i} and \xi_{j} implying that in this case r_{g}(\xi_{i},\xi_{j},\xi_{k})=0 , so the bound on r_{g}(\xi_{i},\xi_{j},\xi_{k}) imposed by Assumption 6 is trivially satisfied. Appendix C Imputation of \hat{Y}_{ij}^{*} with Missing Data In this section, we discuss how one can adjust the previously constructed estimator \hat{Y}_{ij}^{*} when some interaction outcomes are missing. We will stick with the notation previously introduced in Section 5.2 . We start with constructing \hat{d}_{\infty}^{2}(i,j) previously defined in ( 3.5 ). In the studied setting, \hat{d}_{\infty}^{2}(i,j) can be computed as \displaystyle\hat{d}_{\infty}^{2}(i,j)\coloneqq\max_{k\neq i,j}\Big|{\left|\mathcal{O}_{ijk}\right|^{-1}\sum_{\ell\in\mathcal{O}_{ijk}}(Y_{i\ell}-Y_{j\ell})Y_{k\ell}}\Big|, (C.1) where \mathcal{O}_{ijk}=\{\ell:D_{i\ell}=D_{j\ell}=D_{k\ell}=1\} . In practice, if \left|\mathcal{O}_{ijk}\right| is too small for a given k , this k can be dropped from the calculation of \hat{d}_{\infty}^{2}(i,j) above; it is sufficient to compute the maximum in ( C.1 ) over a subset of all the other agents so long as it is not too small (otherwise, we can set \hat{d}_{\infty}^{2}(i,j)=\infty ). Next, we proceed with calculation of \hat{Y}_{ij}^{*} . To this end, we need to introduce a j -specific neighborhood of i denoted by \hat{\mathcal{N}}_{ij}(n_{ij}) . As before, for simplicity, we will stick with discrete X . First, let us define a pool of candidate agents (donors) which can potentially be used to impute \hat{Y}_{ij}^{*} denoted by \mathcal{P}_{ij}\coloneqq\{i^{\prime}:X_{i^{\prime}}=X_{i},D_{i^{\prime}j}=1\} , where the requirement D_{i^{\prime}j}=1 ensures that Y_{i^{\prime}j} is observed. Then \hat{\mathcal{N}}_{ij}(n_{ij}) is constructed as a collection of n_{ij} agents from \mathcal{P}_{ij} closest to agent i in terms of \hat{d}_{\infty}^{2}(i,i^{\prime}) , i.e., \displaystyle\hat{\mathcal{N}}_{ij}(n_{ij})\coloneqq\{i^{\prime}\in\mathcal{P}_{ij}:\text{Rank}(\hat{d}_{\infty}^{2}(i,i^{\prime})|\mathcal{P}_{ij})\leqslant n_{i}\}, and \hat{Y}_{ij}^{*} can be estimated as \displaystyle\hat{Y}_{ij}^{*}=\frac{\sum_{i^{\prime}\in\hat{\mathcal{N}}_{ij}(n_{ij})}Y_{i^{\prime}j}}{n_{ij}}. When the observed matrix Y is so sparse and \mathcal{P}_{ij} is so limited in the first place to find enough decent matches for imputation of Y_{ij}^{*} , one can try to sequentially impute the elements of Y^{*} with a sufficient number of candidate donors in \mathcal{P} first, and then use the newly imputed \hat{Y}_{i^{\prime}j}^{*} ’s as observed outcomes Y_{i^{\prime}j} to expand the previously thin pool of potential donors \mathcal{P}_{ij} . One can apply this procedure sequentially if needed to impute the whole Y^{*} or a part of it. Once \hat{Y}^{*} is constructed, we can estimate \hat{d}_{ij}^{2} as in ( 3.4 ), or if some elements of \hat{Y}^{*} are still missing, we can modify ( 3.4 ) in the same fashion as in ( 5.8 ), where the overlaps should be defined based on whether the imputed \hat{Y}^{*} ’s are missing or not. Once \hat{d}_{ij}^{2} ’s are obtained, we can calculate \hat{\beta} as in ( 5.9 ), or even use the imputed outcomes instead of the plain outcomes in ( 5.9 ), including in the definition of the overlap \mathcal{O}_{ij} again.