 Elad Hazan

Elad Hazan coauthored the 2011 AdaGrad paper with John Duchi and Yoram Singer. The work analyzes adaptive gradient methods in online learning and stochastic optimization, using accumulated subgradients to adapt the update geometry.^[ref]

A useful theoretical benchmark is cumulative regret. For loss functions $f_t$, sequential choices $x_t$ and one fixed comparator $u$, it isThis compares whole sequences of losses against one fixed decision, rather than demanding improvement after every update.^[ref]

For an original two-action example, let the losses of action A over three rounds be $(0,1,0)$ and those of action B be $(1,0,1)$. A learner choosing A, B, B incurs total loss $0+0+1=1$. Always choosing A also costs $1$, while always choosing B costs $2$. The learner therefore has zero cumulative regret against the best fixed action, even though it still suffered a positive loss in the third round. Choosing the best action separately in every round would give total loss zero, but that is a different comparator.

Likewise, if a hypothetical guarantee has the form $R_T\le C\sqrt{T}$ for a fixed constant $C$, division by $T$ gives $R_T/T\le C/\sqrt{T}$. This elementary implication explains how a growing total cumulative regret can coexist with a shrinking average gap. It does not establish such a guarantee for an arbitrary optimization algorithm.