kiefer-wolfowitz algorithm in section we will see how stochastic gradient descent is employed in deep learning to minimize the training lossbased on "minibatchof training data it can be shown [ thatunder certain regularity conditions on the sequence converges to the true minimizer xwhen the step sizes decrease slowly enough to in particularwhen = bt and = kieferwolfowitz ( in practiceone rarely uses step sizes that satisfy ( )as the convergence of the sequence will be too slow to be of practical use an alternative approach to stochastic approximation is the stochastic counterpart methodalso called sample average approximation it can be applied in situations where the noisy objective function is of the form (xese(xx) xstochastic counterpart ( where is random vector that can be simulated and se(xxcan be evaluated exactly the idea is to replace the optimization of ( with that of the sample average xe (xs (xxi ) = ( where are iid copies of note that is deterministic function of and so can be optimized using any optimization algorithm solution to this sample average version is taken to be an estimator of solution xto the original problem ( example (determining good importance sampling parametersthe selection of good importance sampling parameters can be viewed as stochastic optimization problem considerfor instancethe importance sampling estimator in example recall that the nominal distribution is the uniform distribution on the square [-bb] with pdf fb ( ( ) [-bb] where is large enough to ensure that ub is close to uin that examplewe chose the importance sampling pdf is - + le gl (xfr,th (rthle-lr ( { } which depends on free parameter in the example we chose is this the best choicemaybe or would have resulted in more accurate estimate the important thing to realize is that the "effectivenessof can be measured in terms of the variance of the estimator in ( )which is given by