Online Convex Optimization

Let $\mathcal{K}$ have diameter $D = \sup_{u,v \in \mathcal{K}} \|u - v\|$ and suppose $\|\nabla f_t(w)\| \leq G$ for all $t, w$. With step size $\eta_t = D/(G\sqrt{t})$, OGD satisfies:

$\text{Regret}_T \leq \frac{3}{2} DG\sqrt{T}$

With the optimal constant step size $\eta = D/(G\sqrt{T})$ (requiring knowledge of $T$):

$\text{Regret}_T \leq DG\sqrt{T}$

Each step of OGD reduces regret against the comparator by following the gradient, but each step also incurs error from the noisy gradient. The $\sqrt{T}$ comes from balancing cumulative step errors ($\sim \eta T$) against cumulative gradient tracking ($\sim T/\eta$). Optimizing over $\eta$ gives $\sqrt{T}$.

The $O(\sqrt{T})$ regret bound is optimal for general convex losses (matching lower bounds). This means average regret $\text{Regret}_T/T = O(1/\sqrt{T}) \to 0$, so OGD is a no-regret algorithm. The proof technique (telescoping via Bregman divergences) is the template for analyzing nearly all first-order online methods.

The bound assumes bounded gradients and a bounded domain. For unconstrained optimization or heavy-tailed gradients, the guarantee breaks. For strongly convex losses, the $O(\sqrt{T})$ rate is loose; $O(\log T)$ is achievable and optimal.

Let $R$ be $\sigma$-strongly convex with respect to norm $\|\cdot\|$ on $\mathcal{K}$. Define the dual norm bound $G_* = \max_t \|\nabla f_t\|_*$. FTRL with regularizer $\eta^{-1} R$ satisfies:

$\text{Regret}_T \leq \frac{\max_{w \in \mathcal{K}} R(w) - \min_{w \in \mathcal{K}} R(w)}{\eta} + \frac{\eta}{2\sigma}\sum_{t=1}^{T} \|\nabla f_t(w_t)\|_*^2$

With optimal $\eta$, this gives $\text{Regret}_T = O(G_* \sqrt{T/\sigma} \cdot \sqrt{\max R - \min R})$.

FTRL balances two forces: the regularizer keeps decisions stable (preventing oscillation), while the cumulative loss pulls decisions toward the best action. The regret bound trades off the initial penalty from regularization against the stability gained.

FTRL generalizes OGD to arbitrary geometries via the choice of regularizer. With $R(w) = \frac{1}{2}\|w\|_2^2$, you recover OGD. With $R(w) = \sum_i w_i \log w_i$ (negative entropy) on the simplex, you recover the multiplicative weights/hedge algorithm. One framework, many algorithms.

Choosing the right regularizer requires knowing the geometry of the problem. A poorly matched regularizer (e.g., Euclidean regularization on the simplex) gives suboptimal regret. Computing the FTRL update requires solving a convex optimization problem at each step, which may be expensive for complex $R$ and $\mathcal{K}$.

AdaGrad (diagonal version) uses per-coordinate step sizes $\eta_{t,j} = D/(2\sqrt{\sum_{s=1}^{t} g_{s,j}^2})$ where $g_{t,j}$ is the $j$-th component of $\nabla f_t(w_t)$. Its regret satisfies:

$\text{Regret}_T \leq 2D \sum_{j=1}^{d} \sqrt{\sum_{t=1}^{T} g_{t,j}^2}$

If all gradient components are bounded by $G$, this is at most $2DG\sqrt{dT}$. But if gradients are sparse (most components are zero), the bound can be much smaller.

AdaGrad gives larger step sizes to infrequent features and smaller step sizes to frequent ones. Coordinates with small cumulative gradient magnitude get more aggressive updates. This is automatic adaptation without needing to know the gradient distribution in advance.

AdaGrad shows that adaptive step sizes emerge naturally from the OCO framework. The online-to-batch conversion of AdaGrad gives convergence guarantees for stochastic optimization that adapt to the gradient noise structure. This is the theoretical foundation for Adam and other adaptive gradient descent variants used in deep learning.

AdaGrad's step sizes monotonically decrease, which can be too aggressive for non-stationary problems. In deep learning, this motivates Adam (which uses exponential moving averages instead of cumulative sums). The diagonal approximation ignores correlations between coordinates.