Optimistic Online Learning With Predictable Gradients

Why Forecast the Gradient?

In online convex optimization, a learner chooses an action, then receives information about the loss incurred at that action. Standard gradient descent uses the gradient from the previous round to choose the next action. When successive gradients are similar, that previous gradient may already be a useful forecast of the next one. Optimistic online learning makes this idea explicit: the learner supplies a forecast before acting, and the update responds to the difference between the forecast and the gradient that is eventually observed.

The key consequence is a regret guarantee that depends on forecast error, not just on the size of the gradients. This can improve the bound when gradients are large but predictable. We derive the result for an unconstrained Euclidean action space, where the update and its proof are especially transparent.

The measurability condition expresses the timing requirement: \(m_t\) cannot use information from the current loss that has not yet been observed. The regret inequality below is pathwise, so once the actions, forecasts, and gradients are specified, it holds without a probabilistic assumption on how they were generated.

The Optimistic Gradient Update

Maintain an auxiliary point \(y_t\), initialized at \(y_0\). Given a positive learning rate \(\eta\), use the forecast to choose the action and the observed gradient to update the auxiliary point:

The action \(x_t\) is chosen before observing \(g_t\). After the loss is revealed, \(y_t\) is updated using that gradient. Thus \(y_t\) is the point the learner would have reached by applying a gradient step from \(y_{t-1}\), while \(x_t\) is the point reached by substituting the forecast \(m_t\). Their difference is

This identity makes the design intuitive: when the forecast is accurate, the action is close to the gradient-updated auxiliary point. It also identifies the quantity that will appear in the regret bound. In practice, a forecast might be the previous observed gradient, or a prediction from a model built using past information; it must still be available before the current decision.

A Regret Bound in Terms of Forecast Error

For a fixed comparator \(u\in\mathbb{R}^d\), define linearized regret by \(\sum_{t=1}^T\langle g_t,x_t-u\rangle\). The next result is a pathwise inequality for any sequence of forecasts and gradients. In particular, it does not require the forecasts to be accurate; accuracy only makes the resulting bound smaller.

Proof. From the update, \(x_t=y_{t-1}-\eta m_t\) and \(y_t=y_{t-1}-\eta g_t\). Expanding the squared distance to \(u\) gives

Also,

Subtracting half the expanded distance difference from this last expression yields

The identity \(\|g_t-m_t\|^2=\|g_t\|^2-2\langle g_t,m_t\rangle+\|m_t\|^2\) shows that

because the right side minus the left side is \(\eta^2\|m_t\|^2/2\geq 0\). Therefore, for each round,

Summing over \(t\), the distance terms telescope to \(\big(\|u-y_0\|^2-\|u-y_T\|^2\big)/(2\eta)\). Dropping the nonpositive term \(-\|u-y_T\|^2/(2\eta)\) proves the result. \(\square\)

If each \(\ell_t\) is convex and \(g_t\in\partial\ell_t(x_t)\), the subgradient inequality gives \(\ell_t(x_t)-\ell_t(u)\leq\langle g_t,x_t-u\rangle\). Consequently, the theorem also bounds ordinary loss regret:

This conversion uses convexity at the played action \(x_t\); it does not require the losses to be linear. If the comparator is at distance \(R=\|u-y_0\|\) and the cumulative squared forecast error is \(S=\sum_{t=1}^T\|g_t-m_t\|^2\), then for \(R>0\) and \(S>0\), choosing \(\eta=R/\sqrt{S}\) makes the displayed bound \(R\sqrt{S}\). The learning rate balances the initial-distance term against the accumulated forecast-error term.

What the Guarantee Does—and Does Not—Say

The bound replaces a cumulative squared-gradient term with a cumulative squared forecast-error term. For example, if \(\|g_t\|\leq G\), a non-optimistic gradient method typically pays for a quantity on the scale of \(\sum_t\|g_t\|^2\). The optimistic guarantee can be substantially smaller when \(m_t\) tracks \(g_t\), even if the gradients themselves are not small. The benefit comes from predictable structure in the sequence, not from assuming that the losses are stochastic or that the forecasts are always correct.

A common mistake is to treat \(m_t\) as the gradient that has already been observed at the current round. That reasoning reverses the protocol: \(g_t\) is revealed only after \(x_t\) is chosen. The correction is to choose \(m_t\) using past information, form \(x_t=y_{t-1}-\eta m_t\), and then update \(y_t\) using the newly observed \(g_t\). Another mistake is to read the theorem as saying that regret is controlled by \(\sum_t\|g_t-m_t\|\); the proved quantity is the **sum of squared errors**, \(\sum_t\|g_t-m_t\|^2\), with the learning-rate factor shown explicitly.

Finally, this derivation is for unconstrained Euclidean actions. If actions must lie in a prescribed set, the update needs a projection or another geometry-compatible operation, and the corresponding regret proof must account for it. The unconstrained formula should not be applied to a constrained problem without that modification.