Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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...

share|improve this answer
    
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. –  Jugurtha Jan 22 '13 at 10:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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