# Implementation of Fourier Online Gradient Descend

According to the algorithm, is it true that I have to sample 1,...,D u's from the normal distribution with mean 0 and variance 1 (not sure what sigma square here refers to)? And then I have to construct the z as shown in the algorithm. However, I wonder how this will speed up gradient descend because creating sin and cos in alternatingly in code will probably take a very long time(in python). Does anyone know what is the proper and efficient way to implement this algorithm? Thanks

• Please write your algorithm in pseudocode here. Where does it come from? Besides "I guess..." applied to programs is wrong 97.53% of the time. measure instead of guessing. Python does use the machine's implementation of elementary functions, your time drain will most probably be elsewhere. – vonbrand Nov 1 '15 at 23:32
• @vonbrand what do you mean by write in pseudocode here? isn't the algorithm above a pseudocode? – user10024395 Nov 2 '15 at 11:46
• $\sigma^{-2}I$ is the precision of the MVN distribution and is a free parameter defined by your Gaussian kernel. If this notation is unfamiliar I highly recommend reading an introductory statistics book. The pseudo-code is straightforward; what isn't explained is how to properly decide on $\eta$ for the line search step in the "if statement". If you check out Nocedal-Write's book on numerical optimization you will find plenty of methods to implement line search. – Nicholas Mancuso Nov 3 '15 at 6:43
• Also: please do not cross-post. – Nicholas Mancuso Nov 3 '15 at 6:44