Open Problem: Efficient Online Sparse Regression
; Proceedings of The 27th Conference on Learning Theory, PMLR 35:1299-1301, 2014.
In practical scenarios, it is often necessary to be able to make predictions with very limited access to the features of any example. We provide one natural formulation as an online sparse regression problem with squared loss, and ask whether it is possible to achieve sublinear regret with efficient algorithms (i.e. polynomial running time in the natural parameters of the problem).