Online Optimization, Regret, and Stochastic Gradient¶
Job: develop the online convex optimization (regret), the FTL / FTRL / mirror descent, the SGD convergence, and the bandit / explore-exploit — with the FTRL regret / SGD for ML as the worked example.
Core¶
The online convex optimization (OCO)¶
| OCO / regret / sequential | Description |
|---|---|
| OCO | \(x_t\to\ell_t(x_t)\) (the sequential, the online) |
| Regret | \(\sum\ell_t(x_t)-\min_x\sum\ell_t(x)\) (the regret, the game theory) |
The FTL / FTRL and the mirror descent¶
| FTL / FTRL / mirror descent | Description |
|---|---|
| FTL | \(x_t=\arg\min\sum_{s<t}\ell_s(x)\) (the Follow-the-Leader) |
| FTRL | \(x_t=\arg\min\sum\ell_s(x)+R(x)\) (the Follow-the-Regularized-Leader, the Shalev-Shwartz) |
| Mirror descent | the Bregman \(D_\phi(x,y)\) (the mirror, the information theory) |
The SGD and the convergence¶
| SGD / convergence / ML | Description |
|---|---|
| SGD | \(x_{k+1}=x_k-\eta_k g_k\) (\(g_k\) the stochastic gradient, the stochastic processes) |
| Convergence | convex \(O(1/\sqrt{k})\), strong convex \(O(1/k)\) (the ML mathematics) |
The bandit and the explore-exploit¶
| Bandit / UCB / Thompson | Description |
|---|---|
| Bandit | the partial info, the explore-exploit (the information theory) |
| UCB / Thompson | the UCB the upper confidence, the Thompson the posterior (the probability) |
See it¶
FTRL regret bound and the SGD for the ML. The FTRL: \(x_t=\arg\min\sum_{s<t}\ell_s(x)+R(x)\) (the Follow-the-Regularized-Leader), the regret \(\le O(\sqrt{T})\) (the Shalev-Shwartz, the \(R\) the regularization). The SGD: \(x_{k+1}=x_k-\eta_k g_k\) (\(g_k\) the stochastic gradient, the unbiased \(\mathbb{E}[g_k]=\nabla f\)), the convergence \(O(1/\sqrt{k})\) (the convex, the ML mathematics). The key point: the FTRL the regret \(\sqrt{T}\) (the online), the SGD the convergence \(1/\sqrt{k}\) (the stochastic) — the online / stochastic the optimization the ML.
Check¶
Show that the FTRL regret is \(O(\sqrt{T})\), and the SGD convergence \(O(1/\sqrt{k})\).
The FTRL: \(x_t=\arg\min\sum_{s<t}\ell_s+R(x)\) (the FTRL), the regret \(R_T=\sum\ell_t(x_t)-\min\sum\ell_t(x)\le O(\sqrt{T})\) (the Shalev-Shwartz, the \(R\) the regularization the stability, the FTL the be-the-leader the telescoping). The SGD: \(x_{k+1}=x_k-\eta_k g_k\) (\(g_k\) the unbiased), the \(\mathbb{E}[f(x_k)-f^*]\le O(1/\sqrt{k})\) (the convex, the \(\eta_k=1/\sqrt{k}\)), the \(O(1/k)\) the strong convex. So the FTRL the \(\sqrt{T}\), the SGD the \(1/\sqrt{k}\).
Explain the bandit and the UCB / Thompson sampling.
The bandit: the \(x_t\) the arm, the \(\ell_t\) the loss (the partial info — only \(\ell_t(x_t)\) observed, not \(\ell_t(x)\) for all \(x\)). The UCB: the \(x_t=\arg\min\hat\ell_t(x)-c_t\sqrt{\hat\sigma_t(x)}\) (the upper confidence bound, the explore-exploit, the probability). The Thompson: the \(x_t\sim\pi_t\) (the posterior, the Thompson sampling). The regret: the \(O(\log T)\) the stochastic (the UCB / Thompson), the \(O(\sqrt{T})\) the adversarial. So the bandit the UCB / Thompson, the explore-exploit.
Pitfalls¶
- The regret (the \(\sum\ell_t(x_t)-\min\sum\ell_t\), the game theory) — the regret the online, the FTL / FTRL the \(\sqrt{T}\).
- The SGD the stochastic (the \(g_k\) the unbiased, the stochastic processes) — the SGD the \(1/\sqrt{k}\), the ML.
- The bandit the partial (the explore-exploit, the UCB / Thompson) — the bandit the partial, the UCB / Thompson the \(O(\log T)\).
- The mirror descent (the Bregman, the information theory) — the mirror the Bregman, the online the mirror.
Refs¶
- Shalev-Shwartz, Online Learning and Online Convex Optimization (2012); the FTRL
- Hazan, Introduction to Online Convex Optimization (2016); the regret
- Robbins–Monro, "A stochastic approximation method" (1951); the SGD
- Auer–Cesa-Bianchi–Fischer, "Finite-time analysis of the multiarmed bandit problem" (2002); the UCB
Next¶
Opt index · Foundations · Conic & SDP · Nonconvex & Landscape · Variational & Monotone · ML mathematics · Game theory · Stochastic processes