= Elad Hazan
{c}
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.<Adaptive Subgradient Methods for Online Learning and Stochastic Optimization by John Duchi and others>[Published byline and Abstract]{ref}
A useful theoretical benchmark is <cumulative regret>. For <loss functions> $f_t$, sequential choices $x_t$ and one fixed comparator $u$, it is
$$
R_T(u)=\sum_{t=1}^{T}\bigl(f_t(x_t)-f_t(u)\bigr).
$$
This compares whole sequences of losses against one fixed decision, rather than demanding improvement after every update.<Adaptive Subgradient Methods for Online Learning and Stochastic Optimization by John Duchi and others>[Section 1.1, regret definitions and sublinear-regret goal]{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\leq C\sqrt{T}$ for a fixed constant $C$, division by $T$ gives $R_T/T\leq 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.
\Image[https://collaborate.princeton.edu/files-asset/48145874/Hazan.jpg?f=jpg&w=160]
{title=Elad Hazan, portrait linked from Princeton University's named research profile}
{description=<Elad Hazan institutional profiles at Princeton>[Named research portal and portrait]{ref}}
Back to article page
