# Can a model of P(Y|X) be trained via stochastic gradient descent from non-i.i.d. samples of P(X) and i.i.d. samples of P(Y|X)?

When training a parameterized model (e.g. to maximize likelihood) via stochastic gradient descent on some data set, it is commonly assumed that the training samples are drawn i.i.d. from the training data distribution. So if the goal is to model a joint distribution $P(X,Y)$, then each training sample $(x_i,y_i)$ should be drawn i.i.d. from that distribution.

If the goal is instead to model a conditional distribution $P(Y|X)$, then how does the i.i.d. requirement change, if at all?

1. Must we still draw each sample $(x_i,y_i)$ i.i.d. from the joint distribution?
2. Should we draw $x_i$ i.i.d. from $P(X)$, then draw $y_i$ i.i.d. from $P(Y|X)$?
3. Can we draw $x_i$ not i.i.d. from $P(X)$ (e.g. correlated over time), then draw $y_i$ i.i.d. from $P(Y|X)$?

Can you comment on the validity of these three approaches for stochastic gradient descent? (Or help me rephrase the question if necessary.)

I would like to do #3 if possible. My application is in reinforcement learning, where I'm using a parameterized conditional model as a control policy. The sequence of states $x_i$ is highly correlated, but the actions $y_i$ are sampled i.i.d. from a stochastic policy conditioned on the state. The resulting samples $(x_i,y_i)$ (or a subset of them) are used to train the policy. (In other words, imagine running a control policy for a long time in some environment, gathering a data set of state/action samples. Then even though the states are correlated over time, the actions are generated independently, conditioned on the state.) This is somewhat similar to the situation in this paper.

I found a paper, Ryabko, 2006, "Pattern Recognition for Conditionally Independent Data," which at first seemed relevant; however, there the situation is reversed from what I need, where $y_i$ (the label/category/action) can be draw not i.i.d from $P(Y)$, and $x_i$ (the object/pattern/state) is drawn i.i.d. from $P(X|Y)$.

Update: Two papers (here and here) mentioned in the Ryabko paper seem relevant here. They assume the $x_i$ come from an arbitrary process (e.g. not iid, possibly nonstationary). They show that nearest-neighbor and kernel estimators are consistent in this case. But I'm more interested in whether estimation based on stochastic gradient descent is valid in this situation.

• Maybe I'm missing something, and I haven't read the paper, but: you're drawing $x_i$ non-iid from $P(X)$ and then sampling $y_i$ iid from $P(Y \mid X)$. Ryabko (2006) is drawing $y_i$ non-iid from $P(Y)$ and then sampling $x_i$ iid from $P(X \mid Y)$. These seem the same up to renaming. Is there something fundamentally different about the objects $x$ and $y$ that makes this not the same situation? – Dougal Apr 20 '13 at 4:33
• @Dougal: The difference is that conditional distribution models, like conditional random fields, treat $X$ and $Y$ (the "inputs" and "outputs") differently... they model only one direction ($P(Y|X)$ but not $P(X|Y)$). – Tyler Streeter Apr 20 '13 at 14:01
• I would consider the following analogy in this case. Suppose $Y_i$ and $X_i$ are two correlated time series (correlation in time). We would like to figure out a function $Y_i = f(X_i;\theta)$, which is equivalent to finding $P(Y_i|X_i;\theta)$. If $P(Y_i|X_i;\theta)$, which is the residual, is IID (hence stationary and uncorrelated) then the estimation procedure converges without bias. Basically processing the time series in time order or any randomized order shouldn't matter in a MLE procedure as long as the conditional likelihood is correctly specified and residuals are IID. – Cagdas Ozgenc Nov 17 '13 at 9:33

• If there is no data at or near a point x$_1$ then you can't even estimate P(Y|X=x$_1$) and if there are only a few points the variance of the estimate will be large. – Michael R. Chernick Aug 21 '12 at 20:53