Truncated Linear Models and Implicit Updates
Truncated linear models were proposed in [1]} to create a tighter surrogate model for optimization.
While the use of convex linear lower bounds is also the core method in OCO algorithms [2]},
we are not aware of any other online learning algorithm with a regret guarantee based on truncated linear models.
[1]} incorporate truncated linear models into the Mirror Descent update [4]}, forming a
proximal/implicit update [5]}, [6]}, [7]}, [8]}, [9]}.
In online learning, [10]} provides the first regret bounds for implicit updates that
match those of OMD, while [11]} makes the first attempt to quantify the advantage of the implicit updates in the
regret bound. [12]} generalize the results in [11]} to Bregman divergences and strongly convex
functions, and quantify the gain differently in the regret bound. Finally, [14]} show that implicit
updates give rise to regret guarantees that depend on the temporal variability of the losses as well.
We will match the dependency on the subgradients in our final results to the one of FTRL with implicit
updates [11]}, which underlines the “implicit” nature of our algorithm.
