In an effort to address this issue and go beyond focusing only on asymptotic rates, [1]} have proposed the use of truncated linear models instead of linear models to obtain better stochastic Mirror Descent algorithms with negligible additional computational complexity. Truncated linear models are tighter lower bounds to the original function that do not require additional curvature while still yielding a closed form update for Mirror Descent algorithms. For example, a common issue with standard gradient descent methods is that they can overshoot the minimum of the loss during any given iteration. The use of truncated linear models significantly mitigates this concern by providing a “signal” that gradient descent might overshoot, allowing the learning algorithm to take a more conservative step. The same idea can be applied to the online (rather than stochastic) setting, but only for OMD. It is unknown how to use truncated linear models in parameter-free algorithms without having an explosion in the computational time.
<FIGURE>