Online estimation

Usefulness: 🔧
Novelty: 💡
Uncertainty: 🤪 🤪 🤪
Incompleteness: 🚧 🚧 🚧

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.

Covariance

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).$

Refs

Allen-Zhu, Zeyuan, Yuanzhi Li, Aarti Singh, and Yining Wang. 2017. “Near-Optimal Design of Experiments via Regret Minimization.” In PMLR, 126–35. http://proceedings.mlr.press/v70/allen-zhu17e.html.

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. https://doi.org/10.1080/00031305.1983.10483115.

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. https://doi.org/10.1007/978-3-540-72927-3_21.

Feng, Jiashi, Huan Xu, and Shie Mannor. 2017. “Outlier Robust Online Learning,” January. http://arxiv.org/abs/1701.00251.

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. https://doi.org/10.1145/1143997.1144082.

Koppel, Alec, Garrett Warnell, Ethan Stump, and Alejandro Ribeiro. 2016. “Parsimonious Online Learning with Kernels via Sparse Projections in Function Space,” December. http://arxiv.org/abs/1612.04111.

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

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. https://doi.org/10.1145/3018661.3018684.