Truncated Linear model
For any \(\hat{\ell }_t\)  such that \(\hat{\ell }_t({w}_t) = \ell _t({w}_t)\)  and \(\hat{\ell }_t({w}) \le \ell _t({w}),~ \forall {w}\) , we have \(\sum _{t=1}^T (\ell _t({w}_t) - \ell _t({u}))\le \sum _{t=1}^T (\hat{\ell }_t({w}_t) - \hat{\ell }_t({u}))\) . Linear models \(\hat{\ell }_t({w}) = \ell _t({w}_t) + \langle {g}_t, {w}- {w}_t\rangle \)  satisfy this property with \({g}_t \in \partial \ell _t({w}_t)\) , which motivates the popularity of online linear optimization. However, we might think to design tighter approximations. In particular, [1]} proposed truncated linear models:
\(\hat{\ell }_t({w}) \triangleq \max \lbrace \ell _t({w}_t)+\langle {g}_t, {w}-{w}_t\rangle , \inf _{{w}} \ell _t({w})\rbrace ~.\) 
