Adaptive Online Estimation of Piecewise Polynomial Trends
Adaptive Online Estimation of Piecewise Polynomial Trends
复制标题
DOI：
--
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Dheeraj Baby;Yu-Xiang Wang
中科院分区：
文献类型：
--
作者：
Dheeraj Baby;Yu-Xiang Wang
我们考虑了非平稳随机优化框架[Besbes等人，2015]，其中包含平方误差损失和噪声梯度反馈，其中研究了在线学习者对时变比较器序列的动态后悔。从非参数回归理论出发，我们引入了一个新的变分约束，强制比较序列属于半径为$C_n$的离散$k^{th}$阶全变分球。这种变分约束模型具有分段多项式结构，具有许多相关的实际应用[Tibshirani， 2014]。通过与基于小波的非参数回归理论建立联系，我们设计了一个多项式时间算法来实现$\tilde{O}(n^{\frac{1}{2k+3}}C_n^{\frac{2}{2k+3}})$的近最优动态后悔。提出的策略对未知半径具有自适应能力$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.