Abstract
Traditional statistical regression relies on the fundamental assumption of independent and identically distributed (i.i.d.) observations. However, real-world data in social networks, finance, and physical sciences often exhibit significant dependencies. This paper addresses the challenge of performing regression on a single snapshot of networked data. We demonstrate that for both logistic and linear regression models, it is possible to recover model parameters with $O(1/\sqrt{n})$ convergence rates, matching the efficiency of traditional independent regression under mild dependency conditions. Our approach utilizes Maximum Pseudo-Likelihood Estimation (MPLE) for discrete responses and a convexifying reparameterization for continuous responses, supported by concentration of measure techniques for dependent variables.
Introduction
In standard regression analysis, the independence of samples $(x_i, y_i)$ is a cornerstone for proving the consistency of estimators. In many modern applications, such as analyzing peer effects in social networks or spatial correlations in meteorology, this assumption is frequently violated. The primary difficulty lies in the "single-sample" regime: we often observe only one realization of the entire network rather than multiple independent trials.
Previous research has struggled to provide strong consistency results in this setting without imposing restrictive conditions. This work bridges the gap by showing that internal variation within a single large network can substitute for independent samples, allowing for efficient parameter recovery even when data points influence one another.
Methodology and Assumptions
The authors extend regression frameworks to incorporate an interaction matrix $A$, representing the network topology, and a scalar $eta$, representing the strength of interactions.
Logistic Regression (Ising Model)
For binary outcomes, the dependency is modeled using a generalized Ising model. Because the standard Maximum Likelihood Estimate (MLE) involves an intractable partition function, the authors employ Maximum Pseudo-Likelihood Estimation (MPLE). MPLE focuses on the conditional probability of each node given its neighbors, transforming a global optimization problem into a series of local ones solvable via Projected Gradient Descent (PGD).
Linear Regression (Gaussian Graphical Models)
In the linear case, error terms are correlated according to the network structure. The resulting log-likelihood is typically non-convex. To overcome this, the authors introduce an over-reparameterization, defining $\kappa = \beta \cdot \theta$. This transformation renders the objective function convex, enabling global convergence through PGD.
As shown in Table 1, the authors define specific mathematical constraints for both models. Notably, the interaction matrix $A$ is assumed to be known, and its influence is bounded to ensure the system remains in a "high-temperature" regime where dependencies do not overwhelm the signal from covariates.
Theoretical Innovation
The core of the proof relies on concentration of measure for dependent random variables. By using the method of "exchangeable pairs," the authors show that the noise in the system cancels out at a rate sufficient to achieve $O(1/\sqrt{n})$ error. This matches the optimal rate for i.i.d. data, suggesting that the "cost" of dependency is negligible in the large-sample limit.
Key Results
- Strong Consistency: Both the covariate effect $\theta$ and the interaction strength $\beta$ can be estimated with $O(1/\sqrt{n})$ error.
- Algorithmic Efficiency: Parameters are recoverable in $O(\log n)$ iterations of gradient descent, with each iteration scaling linearly with the number of observations $n$ and features $d$.
- Convexification: The discovery that over-reparameterization can convexify the linear regression objective is a significant algorithmic contribution that simplifies the optimization landscape.
Discussion and Limitations
While the results are robust, they rely on the interaction matrix $A$ being known a priori. In practice, $A$ may be latent or partially observed, presenting a significant direction for future research. Furthermore, the "weak dependency" bound (e.g., $\|A\|_\infty \leq 1$) is necessary to prevent the system from entering a phase where network effects drown out the underlying signal from the features. Future work may explore tighter bounds for the scaling of error with respect to the feature dimension $d$ in the linear case.
Summary updated