Optimal sample size for Stochastic Steepest Descent

Question

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.

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