Universal Online Convex Optimization with Minimax Optimal Second-Order Dynamic Regret. (arXiv:1907.00497v2 [math.OC] UPDATED)

Web: http://arxiv.org/abs/1907.00497

We introduce an online convex optimization algorithm using projected
subgradient descent with optimal adaptive learning rates, with sequential and
efficient first-order updates. Our method provides a subgradient adaptive
minimax optimal dynamic regret guarantee for a sequence of general convex
functions with no known additional properties such as strong-convexity,
smoothness, exp-concavity or even Lipschitz-continuity. The guarantee is
against any comparator decision sequence with bounded "complexity", defined by
the cumulative distance traveled via changes between successive decisions. We
show optimality by generating …

arxiv math minimax online optimization