# Online learning

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.

A lot of things are sort-of online learning; stochastic gradient descent, for example, is closely related. However, if you meet someone who claims to study “online learning” they usually mean to emphasis particular things. Frequently seen in the context of bandit problems; connection TBD.

Hazan’s Introduction to online convex optimization looks fresh.

TBD

TBD

## Covariance

Learning covariance online is a much more basic application than the other fancy things considered here, but I guess it still fits. 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).$

## References

Abernethy, Jacob, Peter L Bartlett, and Elad Hazan. 2011. “Blackwell Approachability and No-Regret Learning Are Equivalent.” In, 20.
Allen-Zhu, Zeyuan, Yuanzhi Li, Aarti Singh, and Yining Wang. 2017. In PMLR, 126–35.
Arora, Sanjeev, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. 2017. arXiv:1703.00573 [Cs], March.
Cesa-Bianchi, Nicolò, and Francesco Orabona. 2021. Annual Review of Statistics and Its Application 8 (1): 165–90.
Chan, Tony F., Gene H. Golub, and Randall J. Leveque. 1983. The American Statistician 37 (3): 242–47.
Dasgupta, Sanjoy, and Daniel Hsu. 2007. 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. arXiv:1701.00251 [Cs, Stat], January.
Igel, Christian, Thorsten Suttorp, and Nikolaus Hansen. 2006. 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. arXiv:1612.04111 [Cs, Stat], December.
Ling, Robert F. 1974. Journal of the American Statistical Association 69 (348): 859–66.
Lyu, Hanbaek, Deanna Needell, and Laura Balzano. 2020. Journal of Machine Learning Research 21 (251): 1–49.
McGee, Ryan Seamus, Olivia Kosterlitz, Artem Kaznatcheev, Benjamin Kerr, and Carl T. Bergstrom. 2022. bioRxiv.
Orabona, Francesco, David Pal, Orabona Com, and Yahoo-Inc Com. n.d. “Open Problem: Parameter-Free and Scale-Free Online Algorithms,” 6.
Vervoort, Marco R. 1996. In Statistics, Probability and Game Theory: Papers in Honor of David Blackwell, edited by T.S. Ferguson, L.S. Shapley, and J.B. MacQueen, 369–90. Institute of Mathematical Statistics.
Zarezade, Ali, Utkarsh Upadhyay, Hamid R. Rabiee, and Manuel Gomez-Rodriguez. 2017. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 51–60. WSDM ’17. New York, NY, USA: ACM Press.
Zinkevich, Martin. 2003. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, 928–35. ICML’03. Washington, DC, USA: AAAI Press.

### No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.