In Stochastic First-and Zeroth-order Methods for Nonconvex page 5, we have the following algorithm:
I am trying to implement this algorithm with constant a stepsize which makes $P_R$ to be a uniform distribution. I am having trouble how it works at the third main line where we have $\textbf{Step} \quad k= 1, \cdots, R$. At this line, we need to pick $R$ randomly so suppose $N=1000$, and $R$ take on $3$ as its value. Do we have to do $3$ stochastic gradient descent and we are done?
I agree with VHarisop's answer. Using equation 2.20 in the paper, you will find an approximate $N$ which then can be used to give you the accuracy you are looking for. Obviously, you have to call the RSG algorithm not one time but rather many times as you can find the relevant information in the paragraph right under where they define the RSG algorithm.
For more information, refer to this post where I provided a brief proof of getting equation 2.20 in the paper (link). Good luck.