Adaptive Online Estimation of Piecewise Polynomial Trends
Authors: Dheeraj Baby, Yu-Xiang Wang
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design a polynomial time algorithm that achieves the nearly optimal dynamic regret of O(n 1 2k+3 C 2 2k+3 n ). The proposed policy is adaptive to the unknown radius Cn. Further, we show that the same policy is minimax optimal for several other non-parametric families of interest. |
| Researcher Affiliation | Academia | Dheeraj Baby Department of Computer Science UC Santa Barbara dheeraj@ucsb.edu Yu-Xiang Wang Department of Computer Science UC Santa Barbara yuxiangw@cs.ucsb.edu |
| Pseudocode | Yes | Ada-VAW: inputs observed y values, TV order k, time horizon n, sub-gaussian parameter σ, hyper-parameter β > 24 and δ (0, 1] 1. For t = 1 to k 1, predict 0 2. Initialize th = k 3. For t = k to n: (a) Predict ˆyt = xt, A 1 t Pt 1 s=th k ysxs (b) Observe yt and suffer loss (ˆyt θ1:n[t])2 (c) Let yr =recenter(y[th k : t]) and L be its length (d) Let (y1, y2) = pack(yr) (e) Let (ˆα1, ˆα2) = (T(W y1), T(W y2)) (f) Restart Rule: If ˆα1 2+ ˆα2 2> σ then i. set th = t + 1 |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of source code. |
| Open Datasets | No | The paper is theoretical and does not use or reference any specific dataset for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not report empirical experiments, hence no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not report empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not report empirical experiments, therefore no specific software dependencies with version numbers are provided for replication. |
| Experiment Setup | Yes | Ada-VAW: inputs observed y values, TV order k, time horizon n, sub-gaussian parameter σ, hyper-parameter β > 24 and δ (0, 1] ... If β = 24 + 8 log(8/δ) / log(n) , then with probability at least 1 δ, Ada-VAW achieves a dynamic regret of O n 1 2k+3 nk Dk+1θ1:n 1 2 2k+3 where O hides polylogarithmic factors of n, 1/δ and constants k,σ,B that do not depend on n. |