Online estimation

An online learning perspective gives bounds on the regret: the gap between in performance between online estimation and the optimal estimator when we have access to the entire data.

Frequently seen in the context of bandit problems; connection TBD.


John D Cook:

This better way of computing variance goes back to a 1962 paper by B. P. Welford and is presented in Donald Knuth’s Art of Computer Programming, Vol 2, page 232, 3rd edition.

  • Initialize \(M_1 = x_1\) and \(S_1 = 0.\)
  • For subsequent \(x\)s, use the recurrence formulas \[M_k = M_{k-1} + (x_k – M_{k-1})/k\] \[S_k = S_{k-1} + (x_k – M_{k-1})(x_k – M_k).\]
  • For \(2 \leq k \leq n\), the \(k\)th estimate of the variance is \[s_k^2 = S_k/(k – 1).\]

Allen-Zhu, Zeyuan, Yuanzhi Li, Aarti Singh, and Yining Wang. 2017. “Near-Optimal Design of Experiments via Regret Minimization.” In PMLR, 126–35.

Chan, Tony F., Gene H. Golub, and Randall J. Leveque. 1983. “Algorithms for Computing the Sample Variance: Analysis and Recommendations.” The American Statistician 37 (3): 242–47.

Dasgupta, Sanjoy, and Daniel Hsu. 2007. “On-Line Estimation with the Multivariate Gaussian Distribution.” In Learning Theory, edited by Nader H. Bshouty and Claudio Gentile, 4539:278–92. Berlin, Heidelberg: Springer Berlin Heidelberg.

Feng, Jiashi, Huan Xu, and Shie Mannor. 2017. “Outlier Robust Online Learning,” January.

Igel, Christian, Thorsten Suttorp, and Nikolaus Hansen. 2006. “A Computational Efficient Covariance Matrix Update and a (1+1)-CMA for Evolution Strategies.” In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation - GECCO ’06, 453. Seattle, Washington, USA: ACM Press.

Koppel, Alec, Garrett Warnell, Ethan Stump, and Alejandro Ribeiro. 2016. “Parsimonious Online Learning with Kernels via Sparse Projections in Function Space,” December.

Ling, Robert F. 1974. “Comparison of Several Algorithms for Computing Sample Means and Variances.” Journal of the American Statistical Association 69 (348): 859–66.

Zarezade, Ali, Utkarsh Upadhyay, Hamid R. Rabiee, and Manuel Gomez-Rodriguez. 2017. “RedQueen: An Online Algorithm for Smart Broadcasting in Social Networks.” In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 51–60. WSDM ’17. New York, NY, USA: ACM Press.