  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. dependent on the
sum of squared subgradient norms) for a sequence of general convex functions,
which may not have strong convexity, smoothness, exp-concavity or even
Lipschitz-continuity. The regret guarantee is against any comparator decision
sequence with bounded path variation (i.e. sum of the distances between
successive decisions). We generate the lower bound of the worst-case
second-order dynamic regret by incorporating actual subgradient norms. We show
that this lower bound matches with our regret guarantee within a constant
factor, which makes our algorithm minimax optimal. We also derive the extension
for learning in each decision coordinate individually. We demonstrate how to
best preserve our regret guarantee in a truly online manner, when the bound on
path variation of the comparator sequence grows in time or the feedback
regarding such bound arrives partially as time goes on. We further build on our
algorithm to eliminate the need of any knowledge on the comparator path
variation, and provide minimax optimal second-order regret guarantees with no a
priori information. Our approach can compete against all comparator sequences
simultaneously (universally) in a minimax optimal manner, i.e. each regret
guarantee depends on the respective comparator path variation. We discuss
modifications to our approach which address complexity reductions for time,
computation and memory. We further improve our results by making the regret
guarantees also dependent on comparator sets' diameters in addition to the
respective path variations.
