Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation
Online sparse linear regression is the task of applying linear regression analysis to examples arriving sequentially subject to a resource constraint that a limited number of features of examples can be observed. Despite its importance in many practical applications, it has been recently shown that there is no polynomialtime sublinear-regret algorithm unless NP⊆BPP, and only an exponential-time sublinear-regret algorithm has been found. In this paper, we introduce mild assumptions to solve the problem. Under these assumptions, we present polynomialtime sublinear-regret algorithms for the online sparse linear regression. In addition, thorough experiments with publicly available data demonstrate that our algorithms outperform other known algorithms.
The paper considers the online sparse regression problem introduced by Kale (COLT'14), in which the online algorithm can only observe a subset of k features of each data point and has to sequentially predict a label based only on this limited observation (it can thus only use a sparse predictor for each prediction). Without further assumptions, this problem has been recently shown to be computationally hard by Foster et al (ALT'16). To circumvent this hardness, the authors assume a stochastic i.i.d. setting, and under two additional distributional assumptions they give efficient algorithms that achieve sqrt(T) regret. 
The results are not particularly exciting, but they do give a nice counter to the recent computational impossibility of Foster et al, in a setting where the data is i.i.d. and well-specified by a k-sparse vector. One of the main things I was missing in the paper is a proper discussion relating its setup, assumptions and results to the literature on sparse recovery / compressed sensing / sparse linear regression. Currently, the paper only discusses the literature and previous work on attribute efficient learning.
In particular, I was not entirely convinced that the main results of the paper are not simple consequences of known results in sparse recovery: since the data is stochastic i.i.d., one could implement a simple follow-the-leader style algorithm by solving the ERM problem at each step; this could be done efficiently by applying a standard sparse recovery/regression algorithm under a RIP condition. It seems that this approach might give sqrt(T)-regret bounds similar to the one established in the paper, perhaps up to log factors, under the authors' Assumption (a) (which is much stronger than RIP: it implies that the data covariance matrix is well conditioned, so the unique linear regression solution is the sparse one).
While the authors do consider an additional assumption which is somewhat weaker than RIP (Assumption b), it is again not properly discussed and related to more standard assumptions in sparse recovery (e.g, RIP), and it was not clear to me how reasonable and meaningful this assumption is. 
Questions / comments:
* The "Online" in the title of the paper is somewhat misleading: the setting of the paper is actually a stochastic i.i.d. setting (where the objective is still the regret), whereas "online" typically refers to the worst-case non-statistical online setting.
* The description of Alg 1 is quite messy and has to be cleaned up. For example:
	- line 192, "computing S_t": the entire paragraph was not clear to me. What are the "largest features with respect to w_t"?
	- line 196: what are i,j?
	- line 199, "computing g_t": many t subscripts are missing in the text.
* Thm 2: Why k_1 is arbitrary? Why not simply set it to k'-2 (which seems to give the best regret bound)?
* Can you give a simpler algorithm under Assumption (b) for the easier case where k <= k'+2 (analogous to Alg 1)?
Minors / typos:
* line 14: the references to [11,10] seems out of context.
* line 156, Assumption (a): use an explicit constant in the assumption, rather than O(1); in the analysis you actually implicitly assume this constant is 1.
* line 188: "dual average" => "dual averaging".
* Lem 3 is central to the paper and should be proven in the main text.
* Lem 4 is a standard bound for dual averaging / online gradient descent, and a proper reference should be given. Also, it seems that a simpler, fixed step-size version of the bound suffices for your analysis.
* line 226: "form" => "from".
* line 246: "Rougly" => "Roughly".