Lipschitz and Comparator-Norm Adaptivity in Online Learning

Abstract

We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models.

arXiv comment30 Pages, 1 Figure

References in corpus (5)

• Adaptive Bound Optimization for Online Convex Optimization
• Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
• MetaGrad: Multiple Learning Rates in Online Learning
• Adaptive scale-invariant online algorithms for learning linear models
• ZigZag: A new approach to adaptive online learning

Cited by in corpus (8)

• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• Universal Online Convex Optimization Meets Second-order Bounds
• Risk-Monotonicity in Statistical Learning
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory
• Parameter-free Gradient Temporal Difference Learning
• Online Linear Optimization with Many Hints