New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression
The authors establish a lower bound of $\Omega(\sqrt{T})$ for minimax regret in online sparse linear regression with additional observed attributes ($(d, b, b_0)$-OSLR). They then present algorithms with better upper bounds: $O(d^{b_0} / \sqrt{T \ln N})$ for $b_0 \ge 2$ and $O(\sqrt{NT \ln T})$ for $b_0 \le 1$. This work shows that the number of extra attributes ($b_0$) significantly impacts problem complexity.