# 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? Commented Apr 20, 2013 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)$). Commented Apr 20, 2013 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. Commented Nov 17, 2013 at 9:33

## 1 Answer

I think you could do either 2 or 3. However the problem with 3 is that in allowing arbitrary distributions for X you include distributions that would have all or almost all of the probability concentrated is a small interval in the x-space. This would hurt the overall estimation of P(Y|X) because you would have little or no data for certain values of X.

• So are you saying that with approach #3, I would get an unbiased result with potentially high variance? Commented Aug 21, 2012 at 20:06
• 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. Commented Aug 21, 2012 at 20:53
• Yes, that makes sense that the variance could be large. I guess my main concern is whether the estimated P(Y|X) will be biased. Commented Aug 21, 2012 at 20:56
• We didn't discuss a point estimate. If you have unbiased estimates for P(X), P(Y) and P(X|Y) and plug them into the formula P(Y|X)= P(X|Y) P(Y)/P(X) you will get a biased estimate. Commented Aug 21, 2012 at 21:11
• I should emphasize that I'm talking about estimating P(Y|X) via stochastic gradient descent, in which case the order of the training samples can influence how fast or whether it converges to the correct model. I'm not just using sample averages, where the order of the samples doesn't matter. Commented Aug 21, 2012 at 22:45