Suppose $g(x_{1:n})$ is the estimate of a gradient, which is calculated at each step of a Stochastic Steepest Descent algorithm. A dataset $x_{1:n}$ is simulated at each step, so if $n$ is small the algorithm is fast but unstable, while if $n$ is large it is slow but stable. So far I have just experimented with many values of n, but maybe somebody knows a better way of determining n.

Suppose $Var(g(x_{1:n})) = f(n)$ is known (i.e. I know how the variance of the gradient varies with the sample size), I was considering:

a) To minimize a loss function of the type:

$$ Loss(n)=f(n)+n×c. $$

b) To plot $f(n)$ against $n \times c$ to try determine a good sample size n visually.

In my case $c$ is the time needed to simulate $x_{i}$, for example 0.1sec. I don't think that minimizing a function were different units are summed together makes much sense, so I was wondering whether there is any way to translate CPU times into something more sensible.


1 Answer 1


I would expect that you'd want to vary $n$ from step to step - start with a small sample to make large strides quickly, then slowly increase the size to stabilize once you're close to a minimum. And then maybe run this procedure many times if you expect you might get stuck in local minima.

This sounds a bit like simulated annealing in that you'd use the sample size in a similar way to the temperature in simulated annealing, a large sample corresponding to a low temperature. It is notoriously difficult to design a good cooling schedule for simulated annealing - as far as I know, essentially you need to choose and tweak the parameters by instinct. I expect that similarly you cannot really derive the correct schedule for changing $n$ - you'll have to guess and experiment...

  • $\begingroup$ Yes I was just wondering whether there was an automatic way to choose the sample size, but I think that I'll have to keep choosing it by trial and error. $\endgroup$
    – Jugurtha
    Commented Jan 22, 2013 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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