
This multi-step combines the typical time-adaptive step appearing in online gradient-descent algorithms [1]} with a data-adaptive step that accounts for the prediction errors. This ensures that \(a_t\)  will induce enough regularization when the predictions are not satisfactory, but will also continue diminishing even in the case of perfect predictions – a condition that is necessary in order to tame the growth rate of the dual vector. The additional term \(4G^2\ge \xi _t^2, \forall t\)  corrects the off-by-one regularizer of the non-proximal dual update.
