Regression from dependent observations

Constantinos Daskalakis, Nishanth Dikkala, Ioannis Panageas

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.

Table 1: Summary of parameter spaces and assumptions for Logistic and Linear regression models under dependency.

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

Abstract

The standard linear and logistic regression models assume that the response variables are independent, but share the same linear relationship to their corresponding vectors of covariates. The assumption that the response variables are independent is, however, too strong. In many applications, these responses are collected on nodes of a network, or some spatial or temporal domain, and are dependent. Examples abound in financial and meteorological applications, and dependencies naturally arise in social networks through peer effects. Regression with dependent responses has thus received a lot of attention in the Statistics and Economics literature, but there are no strong consistency results unless multiple independent samples of the vectors of dependent responses can be collected from these models. We present computationally and statistically efficient methods for linear and logistic regression models when the response variables are dependent on a network. Given one sample from a networked linear or logistic regression model and under mild assumptions, we prove strong consistency results for recovering the vector of coefficients and the strength of the dependencies, recovering the rates of standard regression under independent observations. We use projected gradient descent on the negative log-likelihood, or negative log-pseudolikelihood, and establish their strong convexity and consistency using concentration of measure for dependent random variables.
BibTeX
@inproceedings{daskalakis2019regression,
  author = {Constantinos Daskalakis and Nishanth Dikkala and Ioannis Panageas},
  title = {{Regression from dependent observations}},
  booktitle = {STOC},
  year = {2019},
  url = {https://openreview.net/forum?id=RzqkOLBfUpB},
}
Figure