We consider the framework of non-stationary stochastic optimization [Besbes
et al, 2015] with squared error losses and noisy gradient feedback where the
dynamic regret of an online learner against a time varying comparator sequence
is studied. Motivated from the theory of non-parametric regression, we
introduce a new variational constraint that enforces the comparator sequence to
belong to a discrete $k^{th}$ order Total Variation ball of radius $C_n$. This
variational constraint models comparators that have piece-wise polynomial
structure which has many relevant practical applications [Tibshirani, 2014]. By
establishing connections to the theory of wavelet based non-parametric
regression, we design a polynomial time algorithm that achieves the nearly
optimal dynamic regret of $\tilde{O}(n^{\frac{1}{2k+3}}C_n^{\frac{2}{2k+3}})$.
The proposed policy is adaptive to the unknown radius $C_n$. Further, we show
that the same policy is minimax optimal for several other non-parametric
families of interest.

文章探讨带有噪声梯度反馈的非平稳随机优化框架，在比较序列变化的动态策略中，研究在线学习算法的动态后悔，并引入了 Total Variation ball 等新颖变分约束来建模比较序列，并基于基于小波的非参数回归理论，设计出一个多项式时间算法，并证明了该算法达到了几乎最优的动态后悔，该策略适应未知的半径。