An application of simultaneous perturbation stochastic approximation (SPSA) algorithm with two measurements per iteration to the problem of object tracking on video is discussed. The upper bound of mean square estimation error is determined in case of once differentiable functional and almost arbitrary noises. Weak restrictions on uncertainty allow to use random sampling instead of full pixelwise difference calculation. The experiments show significant increase in performance of object tracking comparing to the classical Lucas-Kanade algorithm. The results can be generalized to improve more recent kernel-based tracking methods.