# 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.