Online learning
2018-09-30 — 2022-10-19
Wherein the Framework of Online Learning Is Presented and the Notion of Regret Bounds Is Explained, and an Incremental Covariance Update (Welford’s Recurrence) Is Given as a Concrete Method.
An online learning perspective gives bounds on the regret: the gap in performance between online estimation and the optimal estimator when we have access to the entire data.
A lot of things are sort-of-like online learning; stochastic gradient descent, for example, online-ish. However, if you meet someone who claims to study “online learning” they usually mean to emphasize some different regime: especially the adversarial or non-stochastic setting, where the data is not assumed to be drawn from a fixed distribution, but can be chosen by an adversary.
Hazan’s Introduction to online convex optimization looks fresh.
1 Adversarial regret
As seen in Open-world inference: where I note that it look like it satisfies embedded computability. It refuses to model the world at all; the closedness reappears in the comparator class, an object the agent can enumerate and edit, and regret against that class is a statistic, computable per step. Its failure mode — “my whole comparator class is bad against this world” — is announced, not smuggled into an uncomputable prior. It does not solve openness; it relativizes openness to something bounded.
Online learning estimates no measure, adjoins no lump, and needs no \(\mathcal{A}\): its guarantee is worst-case over all sequences, relativized to a comparator class \(\mathcal{C}\) of rival predictors — signature \((\mathrm{regret}_N,\ \text{none},\ \mathcal{C})\), the assumption slot empty and the price paid entirely in the comparator. Conservation holds here too, in its own currency: what the estimation rows keep in \(\mathcal{A}\), regret keeps in \(\mathcal{C}\). The game-theoretic machinery, the reading list, and the open question of when regret bounds go vacuous as \(\mathcal{C}\) grows toward everything — the \(\mathcal{C}\)-side analogue of the regress conjecture are here.
Unlike the stochastic setting, here there is no measure to estimate only a worst-case regret against a comparator class \(\mathcal{C}\). I don’t know much about this. What follows is a reading list for my future self.
- Shafer and Vovk on game-theoretic probability — probability refounded on sequential games, hence the native machinery for guarantees without measure.
- Defensive forecasting (Vovk, Takemura, Shafer) — the constructive counterpart: forecasting strategies built to defeat any betting strategy the sceptic names in advance.
- Foster and Vohra on asymptotic calibration — calibrated forecasts are achievable against arbitrary sequences, an instance of a guarantee with no stochastic assumptions at all.
- Merhav and Feder on universal prediction of individual sequences — the information-theoretic branch of the same programme.
- Rakhlin and Sridharan’s sequential complexities — the learnability theory of the adversarial setting.
- Cesa-Bianchi and Lugosi, Prediction, Learning, and Games
- Online-to-batch conversion — the bridge back to the stationary world: averaging the online iterates turns regret bounds into risk bounds, which somehow gets us back to measure-theoretic guarantees (?)
In what sense are online learning guarantees universal? It seems that the comparator \(\mathcal{C}\) constrains the classes of world we can do well in. Regret bounds presumably go vacuous as the comparator class grows toward everything — the classical lower bounds already scale with the size of \(\mathcal{C}\).
2 Follow-the-regularized leader
TBD
3 Parameter-free
4 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).\]
5 Anomaly detection
See also anomaly detection.