  In this paper we extend the classical Follow-The-Regularized-Leader (FTRL)
algorithm to encompass time-varying constraints, through adaptive penalization.
We establish sufficient conditions for the proposed Penalized FTRL algorithm to
achieve $O(\sqrt{t})$ regret and violation with respect to strong benchmark
$\hat{X}^{max}_t$. Lacking prior knowledge of the constraints, this is probably
the largest benchmark set that we can reasonably hope for. Our sufficient
conditions are necessary in the sense that when they are violated there exist
examples where $O(\sqrt{t})$ regret and violation is not achieved. Compared to
the best existing primal-dual algorithms, Penalized FTRL substantially extends
the class of problems for which $O(\sqrt{t})$ regret and violation performance
is achievable.
