“representative sampling” from a distribution [closed]

Question

I'm drawing samples from a distribution to train a machine learning classifier (training it via mini-batches of 32 samples at a time). It's just a toy dataset, so I know that the samples are coming from a multivariate Gaussian with an identity co-variance matrix.

Since the quantile function (inverse CDF) is tractable for such a distribution, I could evenly space the samples across the domain (0,1) of this function (e.g. points of the unit square in the 2D case) and presumably get a mini-batch of sample the encompass the entire distribution. Obviously I'd have to add a random offset to this grid of samples such that every mini-batch isn't identical, but otherwise it seems like this should speed up learning alot. My question is: is this approach reasonable or is there something I'm missing? And if it is, then is there name for it or literature around it?

Thanks!

Answer 1

Frame the problem this way:

You have a distribution $P$ over a set $\mathcal X$, a classification loss function $L : \mathcal X \to \mathbb R$, and the gradient of the loss function with respect to an input sample $g : \mathcal X \to \mathbb R^d$. You want to know $\mathbb E_{X \sim P}[ g(X) ]$ in order to take a step in your optimization algorithm.

The typical way to do this in machine learning is to suppose that you have a sample $\{ x_i \}_{i=1}^N \sim P$, and estimate $$\mathbb E_{X \sim P} [ g(X) ] \approx \frac{1}{N} \sum_{i=1}^N g(x_i).$$ (Thinking about it this way makes clear the motivation for stochastic gradient descent, where you simply take a subset of your training sample at each step.)

What you're proposing instead is that instead of just taking a random sample $\{ x_i \}$, you carefully choose a set of points to represent the distribution. It turns out this is an idea that makes a lot of sense, and is generally known as quasi-Monte Carlo. If you assume that the function $g$ is relatively smooth, and the dimension of $\mathcal X$ is not too high, then there are specially designed sequences of points you can use to guarantee that your estimate is not too different from the true expectation.

---

Note that everything I just said only applies to a single step of the optimization algorithm. As you noted in the question, if you choose the same $\{ x_i \}$ every time, you may end up at a weird optimum that works well for those points but not in general. A satisfying theoretical answer to this problem will probably take some work, but I think in practice if you just randomly shift the points (as you suggested) then it should be okay in "reasonable" cases.