Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of using sketching techniques for logistic regression. It builds on the previous work of Munteanu et al.'21 which developed an approach to sketch n datapoints in d dimensions to poly(\mu,d,log n) weighted datapoints (in d dimensions) such that solving the logistic regression problem on the smaller dataset gives a log(n) approximation to the function value obtained by the solution on the original dataset. Here, \mu is a data-dependent parameter which captures the complexity of sketching. Though Munteanu et al.'21 obtain a poly(\mu,d,log n) sized sketch, the polynomial dependence on d is not optimal. The current paper closes this gap and shows that a sketching dimension only slightly superlinear in d suffices to obtain a constant approximation to the logistic regression problem. Similar approximation results are also obtained for the L1 loss. The improvement comes from a small modification in the algorithm, and a much tighter analysis. The modification in the algorithm is to hash each element to multiple buckets instead of a single bucket in the CountMin Sketch.

The paper validates the algorithm via similar experiments as in Munteanu et al.'21. The proposed algorithm generally performs better than the previous approach in the experiments.


strength_and_weaknesses: Strengths:

The proposed algorithm is a simple modification of the previous approach, but comes with much stronger guarantees and achieves better results in practice.

Weaknesses:

My main concern is that the paper is not written in a way such that it can really be self-sufficient without reading and understanding Munteanu et al.'21 and related literature. This makes the contribution harder to evaluate and makes it appear to be not as significant. There are several issues in the writing and discussion of the setup:

1. To begin with, a much better job needs to be done to motivate the problem. Since the goal is to solve the logistic regression problem without storing all the datapoints, why is SGD/online gradient descent not the right approach? It would only require memory linear in dimension, even better than the proposed approach. It comes with regret guarantees too, are those sub-optimal compared to the approximation ratios which the paper obtains?

2. Various approaches have been proposed to sketch solutions to linear classification problems, such as "Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters", "Sketching Linear Classifiers over Data Streams", "Random Projections for Classification: A Recovery Approach", "Finding needles in compressed haystacks", "Compressed Classification from Learned Measurements", how do the sketches in these paper compare with the proposed approach? It appears to me that these papers compress the dimensionality d of the datapoints, whereas the current paper compresses the number of datapoints n, but some more discussion of the pros and cons would be useful to situate the work better.

3. The discussion of related work is often that as well organized. For e.g. Sec 1.2 on L1 regression combines various discussions of the current paper with previous approaches in a way which makes it a bit hard to follow the thread.

4. The paper would benefit from an algorithm box with a detailed description of the algorithm (perhaps also pointing out the part where the algorithm differs from Munteanu et al.'21).

5. Similarly, it is nice that the authors included Section 3 on the proof overview, but I found it hard to follow without first going through Munteanu et al.'21.
clarity,_quality,_novelty_and_reproducibility: Most of this is discussed in the weaknesses above.
summary_of_the_review: In summary, I think this paper has a good contribution and achieves tight bounds for a natural problem. But especially for a venue like ICLR where much of the audience may be unfamiliar with the developments for this problem, it is important for the paper to be written and presented such that familiarity with prior work is not as essential. The paper falls short on this regard, and I would place it below the acceptance threshold for this reason.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper improves upon previous oblivious sketching and turnstile streaming results for $\ell_1$ and logistic regression, achieving constant factor approximation, and an efficient algorithm in the sketched space. They demonstrate:

1. Based on a modification of Munteanu et al. (2021) (with significant change of the analysis), they are able to achieve an $O(1)$-factor approximation algorithm with sketch size $\tilde{O}(\mu d^{1+c})$ for any $c > 0$, for the problem of logistic regression. Here $\mu$ is a data-dependent parameter which captures the complexity of compressing the data for logistic regression. 

2. To obtain a $1+\epsilon$ guarantee, they demonstrate that a sketch size of $(\mu d \log(n)/\epsilon)^{O(1/\epsilon)}$ is sufficient. 

3. They show that their sketch can also approximate variance-based regularized logistic regression
within an $O(1)$ factor if the dependence on $n$ in the sketching dimension is increased to $n^{0.5+c}$ for
any $c > 0$.

The authors then experimentally demonstrate the performance of their algorithms in comparison to prior work, with performance usually better, and just a little worse than prior work on one benchmark dataset. 




strength_and_weaknesses: Strengths: 
1. This is an interesting paper with a clear improvement over prior work. 
2. The analysis involves several new ideas.   

clarity,_quality,_novelty_and_reproducibility: Quality and Clarity: The paper is well-written and clear. 
Novelty: The paper introduces a new analysis for an existing algorithm, slightly modified. 
Reproducibility: The authors point the reader to prior work for code that can be modified to run the experiments. 
summary_of_the_review: I think this is a good paper and vote to accept it. The paper produces a clear improvement over prior work, building off the work while complementing it with a significant change of analysis.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents oblivious sketches for logistic regression with significantly improved sketching sizes both in terms of $d$- the dimension of the data and $\mu$ the measure of complexity of compressing the data. The paper also gives sketches for the $\ell_1$ regression and variance regularized logistic regression. Theoretical claims are supported by empirical evaluations on both real and synthetic data.
strength_and_weaknesses: Strengths:
1. Vast improvements in oblivious sketching dimension for logistic regression compared to previous works.
2.  Sketch for variance regularized logistic regression
3. Empirical evaluations

Weakness:

The only weakness I feel is that the paper may be difficult to read for those who are unfamiliar with the related works. There are a few points I mention in the section below which might help improving the clarity
clarity,_quality,_novelty_and_reproducibility: It would perhaps be more useful to describe the entire process of sketch and solve as an algorithm in place of describing it in a paragraph. There does not seem to be any empirical validation for the $\ell_1$- regression problem. I could not find details of how synthetic data is generated.

Although sketches have been applied to logistic and $\ell_1$ regression in earlier works, the improvement obtained here is vast. I did not check the proofs, but the technical ideas given in the main paper appear convincing. 
summary_of_the_review: Overall, the paper is more of theoretical nature and will be of great interest to the researchers working in the "sketch and solve" paradigm. Also, logistic regression being a very important problem in machine learning, the paper would be of interest to broader community too. I recommend an accept
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors present new algorithms for solving logistic and ell-one regression problems through “sketching”, i.e. projecting the problem onto lower dimensions.  While their algorithm is a slight modification of earlier algorithms, they establish much stronger guarantees for it – substantial new ideas are required for this analysis.

This is a significant step forward in an interesting and important line of research.

justification_for_why_not_higher_score: This is kind of a niche, if fundamental and reasonably well-motivated, problem.  At least so far, interest in this line of research is mainly from theoretical computer scientists, which make up a small fraction of ICLR attendees.  This paper’s results are a significant step forward, but arguably not a breakthrough.
justification_for_why_not_lower_score: Please see the above.
Decision: Accept: poster