  We consider a general statistical estimation problem wherein binary labels
across different observations are not independent conditioned on their feature
vectors, but dependent, capturing settings where e.g. these observations are
collected on a spatial domain, a temporal domain, or a social network, which
induce dependencies. We model these dependencies in the language of Markov
Random Fields and, importantly, allow these dependencies to be substantial, i.e
do not assume that the Markov Random Field capturing these dependencies is in
high temperature. As our main contribution we provide algorithms and
statistically efficient estimation rates for this model, giving several
instantiations of our bounds in logistic regression, sparse logistic
regression, and neural network settings 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 {\em single}
sample. {We evaluate our estimation approach on real networked data, showing
that it outperforms standard regression approaches that ignore dependencies,
across three text classification datasets: Cora, Citeseer and Pubmed.}
