Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The current work deals with linear classification in the streaming, limited space model. The assumption is that the available space is both o(n) and o(d), where n = #data points and d = dimension. The goal is to be able to answer two different types of queries about the weight vector-- either to return a vector that is close to the original weight vector in l2 norm, or to return estimates of any coordinate of the weight vector. 
main_review: 

Previous work has dealt with returning the weight vector estimate where the error is bounded by the L1 norm. The broad structure of the current algorithm is similar -- using a sketch (namely CountSketch) matrix to maintain an estimate of the weight vector, which is updated with the arrival of each point, and then to apply an (existing) recovery procedure in the CountSketch matrix. 
There are other results that show that SGD and L-BFGS can be run on sketched data-- while the authors do comment on MISSION, the differences are not entirely clear to me yet. The updates are different, using online gradient descent updates rather than SGD updates, and that reflects in the guarantees, but that does not seem to be the core novelty of the paper. 


The main novelty in this work, which allows for the new bounds, is to separate out the two matrices used for sketching -- one is used for storing the weight vector and the other to create a sketch for the incoming points. It is interesting that this simple change (plus its analysis) enables better guarantees. Beyond this observation, most of the techniques are reused from existing work. 

The experiments are too brief. The error metric is not exactly the one on which the bound has been proven -- that would be | w-hat_T - w*|_2. However, the authors use a metric that has been used before. Point queries are not empirically evaluated. 

There are a number of LateX issues that need to be addressed. 
------------
Post rebuttal: Thanks for the answers to the questions. I have upgraded my score. 

limitations_and_societal_impact: No negative societal impact. 

Limitations are discussed above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The submission is a follow up paper on prior works on performing online gradient descent in sketch space.   The premise here is that the dimension d is very large and therefore we do not want to maintain the parameters vector w* explicitly.   We may only want to know the heavy hitter entries of the vector or to be able to query for values at particular indices (with error of the order of a fraction of the norm).  The approach is to use sketches to "update" w*.

The submission improves over prior work using a “plug and play” approach of taking known results and methods from the streaming literature and applying them in the online gradient descent context. 
main_review: Strength: Natural problem that  was already highlighted in prior work and the submission improves over the results. 

Weaknesses:
The paper presentation is not easily accessible to people not familiar with the particular prior streaming literature. 

The solution is essentially a simply plug and play taking prior tools from streaming, adopted to the online gradient descent framework and the parameters vectors w*.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The focus of this paper is one linear and kernel classification in a streaming setting with limited working memory. I will focus on linear classification in this summary. Given a loss function l and a set of training samples {(x_t,y_t)}_{t=1}^T, the goal is to find the vector w minimizing $(1/T) \sum_{t=1}^T l(y_t w^T x_t) + \lambda\|w\|_2^2$. The twist is that this must be done using sublinear memory. Here sublinear is also in d - the number of features. Thus the optimal vector w cannot even be stored in memory.

What one does instead is to use techniques from streaming algorithms to extract the large coordinates of w, hoping that most of w is captured in a few coordinates of large magnitude. Formally, the setup is that training data arrives in a streaming fashion, with each item in the stream representing a coordinate of an x_t along with y_t. So we only see one single coordinate at a time.

In a standard streaming setting, one can use classic sketches such as the CountSketch to compute a small-memory representation of a given vector w, while allowing finding the heavy hitters (coordinates of magnitude at least $\varepsilon \|w\|_2$) efficiently. The tricky part in the problem considered in this paper, is to simultanously find the small coordinates AND figure out what the optimal solution w is.

A standard solution to linear classification with various loss functions, is to use online gradient descent. This however requires maintaining the current vector of parameters w. This is too expensive here, and the main idea in the work is to sketch w using one of the classic sketches for turnstile streaming heavy hitters / point queries. One can then "simulate" gradient descent via a gradient descent on the parameters in the sketch.

The results are also extended to tensor and kernel regression.
main_review: To summarize my impression of the paper, I find that the most questionable part is the motivation for studying this problem. How often do you really have so many features that you do not have sufficient memory to store them? And more importantly, when you do, how often are the coordinates of the optimal solution w collected on a few coordinates of very large magnitude? In particular this last point is not even discussed in the paper. If there are no eps-heavy hitters in w, then the heavy-hitters guarantees are meaningless. The paper also does not include experiments that show whether this happens on some real-life data sets. Instead the experiments only focus on the ratio between the quality of the solution found by the new algorithm and the solution found by a previous algorithm. Which I agree is an important experiment. But another very interesting value to know would be the ratio $\|w^K - w*\|_2/\|w*\|_2$ on practical data sets. It is not clear at all whether this number is close to 1 or to 0. If it is very close to 1, then the heavy hitters seems a bit meaningless.

The above being said, I think the solution is a clean combination of known techniques from turnstile streaming. It elegantly uses linearity of the turnstile streaming sketches and combines it nicely with gradient descent. The writing of the paper is pretty dense and there are also some places where notation is not introduced (like in the main algorithm, there is an A_t which is never defined, and one has to guess that QUERY(A_T) inside QUERY is a call to a sketch's query algorithm). There are also a number of polynomial dependencies on H lambda eps tau that are pretty nasty from a practical point of view.

All in all, the paper combines standard techniques from streaming to solve a low-space version of a fundamental problem. I'm not completely convinced of the importance of the problem, and the one experiment shown in the paper is not super-convincing. I thus find that the paper fall a bit short of the bar for NeurIPS.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tackles a very basic problem in machine learning, linear (and polynomial, and kernel) classification in the streaming model.  Such learned models can be represented as a coefficients vector w.  The task studied in this paper is to approximately identify the largest coefficients in the optimal coefficient vector w.  

This model was introduced in a SIGMOD 2018 paper.  This paper:
 - improves bounds under the l_1 model, including a deterministic option
 - provides new poly(dimension) bounds in the l_2 model
 - removes assumption that data is random ordered, it allows adversarial order
 - extends to polynomial and kernel SVM classifiers
main_review: If one accepts the model as important, these are sizable improvements.  They are achieved by layering many recent techniques on this setting.  The ideas do not appear entirely new (from a techniques point of view), but the application of them is nonetheless non-trivial and varied.  

However, I am not enthusiastic about the model.  It perpetuates the fallacy that high-weight coefficients are the most important elements of a model.  This may not be true if variables are not properly normalized (if that is even possible).  For instance, the even more involved Shapley values are not necessarily as powerful as often claimed (https://arxiv.org/abs/2002.11097).  
For instance, the paper does not make any claims about how well the compressed model approximates the loss function or generalizes to new data under any assumptions.  

Hence, while I like the technical improvements provided in this work, I am skeptical of the overall premise.  
limitations_and_societal_impact: As this is a theory paper, the authors do not really engage with this aspect.  It mostly removes limitations from prior work.  

As mentioned I am concerned with the focus on explainability by high weights -- but more a modeling issue than a serious societal one rooted in this paper.
review_title: null

Meta-review: The reviewers largely agreed that the paper provides a clear improvement over prior work on the problem of learning "heavy-hitter" weights. The reviewers initially debated the value of the problem studied by the authors, and were concerned it might be of limited interest. However, the author response did a good job of further justifying the setting studied. 
Decision: Accept (Poster)