4
$\begingroup$

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!

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by StasK, Greenparker, gung♦, COOLSerdash, usεr11852 Aug 14 '16 at 17:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ The domain of the 2D Gaussian isn't [0,1]^2, but R^2. If your question is just to sample from the distribution, please read stats.stackexchange.com/questions/12953/…. $\endgroup$ – Vimal Nov 14 '15 at 1:23
  • 1
    $\begingroup$ The domain of the inverse cumulative density function of the 2D Gaussian is [0,1]^2, which is what I was refering to $\endgroup$ – zergylord Nov 14 '15 at 4:29
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you soo much! That quasi-Monte Carlo link just saved me a bundle of time :D $\endgroup$ – zergylord Aug 14 '16 at 22:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.