Αλγόριθμοι και Πολυπλοκότητα

ΤΙΤΛΟΣ: Statistical Estimation for Dependent Data

ΠΕΡΙΛΗΨΗ: Statistical estimation has largely focused on estimating models from independent and identically distributed observations. This assumption is, however, too strong. In many applications, observations 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.

We study statistical estimation problems wherein responses at the nodes of a network are not independent conditioning on the nodes’ features but dependent. We model their dependencies through a Markov Random Field with a log-density that captures individual effects and peer effects. Importantly, we allow dependencies to be substantial, i.e do not assume that the Markov Random Field is in high temperature. Our model generalizes the standard statistical estimation model with independent observations which is obtained by setting the temperature to infinity.

As our main contribution we provide algorithms and statistically efficient estimation rates for our model, giving several instantiations of our bounds in logistic regression, sparse logistic regression, and neural network estimation problems with dependent data. Our estimation guarantees follow from novel results for estimating the parameters (i.e. external fields and interaction strengths) of Ising models from a single sample.

Based on joint works with Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala and Surbhi Goel.