Adaptive Online Learning with Varying Norms

Abstract

Given any increasing sequence of norms $\Vert \cdot {\Vert }_0,\dots ,\Vert \cdot {\Vert }_{T-1}$, we provide an online convex optimization algorithm that outputs points $w_t$ in some domain $W$ in response to convex losses ${\ell }_t:W\to \mathbb{R}$ that guarantees regret $R_T(u)={\sum }_{t=1}^T{\ell }_t(w_t)-{\ell }_t(u)\le \tilde{O}\left(\Vert u{\Vert }_{T-1}\sqrt{{\sum }_{t=1}^T\Vert g_t{\Vert }_{t-1,\star }^2}\right)$ where $g_t$ is a subgradient of ${\ell }_t$ at $w_t$. Our method does not require tuning to the value of $u$ and allows for arbitrary convex $W$. We apply this result to obtain new "full-matrix"-style regret bounds. Along the way, we provide a new examination of the full-matrix AdaGrad algorithm, suggesting a better learning rate value that improves significantly upon prior analysis. We use our new techniques to tune AdaGrad on-the-fly, realizing our improved bound in a concrete algorithm.

References in corpus (7)

• Adaptive Bound Optimization for Online Convex Optimization
• Shampoo: Preconditioned Stochastic Tensor Optimization
• No-Regret Algorithms for Unconstrained Online Convex Optimization
• Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
• Adaptive scale-invariant online algorithms for learning linear models
• Online Learning Without Prior Information
• Black-Box Reductions for Parameter-free Online Learning in Banach Spaces