论文标题
分段多项式趋势的自适应在线估计
Adaptive Online Estimation of Piecewise Polynomial Trends
论文作者
论文摘要
我们考虑了非平稳随机优化的框架[Besbes等，2015]，它们具有平方误差损失和嘈杂的梯度反馈，其中研究了在线学习者对时间变化的比较器序列的动态遗憾。从非参数回归理论的动机中，我们引入了一种新的变分约束，该约束强制执行比较序列属于离散的$ k^{th} $订单订购总radius $ c_n $的总变体球。这种具有许多相关实际应用的分量多项式结构的变分约束模型比较器[Tibshirani，2014年]。通过建立与基于小波的非参数回归理论的联系，我们设计了一种多项式时间算法，该算法实现了$ \ tilde {o} {o}（n^{\ frac {1} {1} {2k+3} {2k+3}} {2k+3}} c_n^c_n^{\ frac {\ frac {2k {2k {2k {2k {2k {2k {2k {2k {2k {2k {2k {2k+3}} {2k {2提出的策略适应未知半径$ C_N $。此外，我们表明，对于其他几个非参数感兴趣的家庭，相同的政策是最佳选择。
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.
