Relation to Implicit Updates
Truncated linear models were introduced as an approximation of the implicit updates [1]}.
In this view, it is instructive to compare the dependency on the subgradients in Theorem  and the regret bounds for implicit updates. For example, [2]} gives a regret guarantee for FTRL with implicit updates and non-adaptive regularizer that depends on \(\langle {g}_t-\frac{1}{2}{g}^+_t,{g}_t^+\rangle \) . This quantity is exactly \(\frac{1}{2}(\Vert {g}_t\Vert ^2 - \Vert {g}_t^+-{g}_t\Vert ^2)\)  that appears in Theorem . This supports the idea that the decomposition in (REF ) “emulates” the idea of implicit updates in parameter-free algorithms. However, there is a subtle difference: in standard implicit updates \({g}_t^+ \in \partial \ell _t({w}_{t+1})\)  is a subgradient of the original loss function. Instead, here \({g}_t^+ \in \partial \hat{\ell }_t({w}_{t+1})\) , so it is a subgradient of the truncated linear model. We can see this as a price we pay to obtain a smaller computational complexity compared to standard implicit updates.
