Lipschitz and Comparator-Norm Adaptivity in Online Learning
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improving Adaptive Online Learning Using Refined Discretization
We study unconstrained Online Linear Optimization with Lipschitz losses. Motivated by the pursuit of instance optimality, we propose a new algorithm that simultaneously achieves ($i$) the AdaGrad-style second order gradi…
Scale-free Unconstrained Online Learning for Curved Losses
A sequence of works in unconstrained online convex optimisation have investigated the possibility of adapting simultaneously to the norm $U$ of the comparator and the maximum norm $G$ of the gradients. In full generality…
Computational EfficiencyregressionParameter-free, Dynamic, and Strongly-Adaptive Online Learning
We provide a new online learning algorithm that for the first time combines several disparate notions of adaptivity. First, our algorithm obtains a ``parameter-free'' regret bound that adapts to the norm of the comparato…
Comparator-adaptive Convex Bandits
We study bandit convex optimization methods that adapt to the norm of the comparator, a topic that has only been studied before for its full-information counterpart. Specifically, we develop convex bandit algorithms with…
Universal Online Convex Optimization with Minimax Optimal Second-Order Dynamic Regret
We introduce an online convex optimization algorithm which utilizes projected subgradient descent with optimal adaptive learning rates. Our method provides second-order minimax-optimal dynamic regret guarantee (i.e. depe…