- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies “strategy proof linear regression” It assumes that all the “X” information is available and folks can misreport only their “Y” coordinates. Also, that they wish the ML to learn a function that get as close as possible to their y on their x. Finally, it uses a worst case ration of the optimal loss (a kind of welfare measurement) compared to the loss reported using a strategy proof mechanism. Here they have a variety of results that paint an interesting picture. For deterministic mechanisms they should that d+1 is the best one can do. For randomized mechanisms the picture is more complicated. They show that one can do better than d+1 iff and only if p \neq 2. Where p is the power in the loss and d is the number of parameters.
Critical strengths
Picks up an open question from prior work. The problem of strategy proof linear regression is reasonable. However, the paper does not point to it being run anywhere, so it is more “potentially useful” than “useful”. Still a reasonable problem.
They make a nice amount of progress on this problem through their "price of strategyproofness" lens and get nice, clean, and surprising results.
They clearly spent a long time on the writing and seem to get technical results correct.
Critical weaknesses
The two big weaknesses are motivation and writing.
The intro tries to motivate the problem. However, none of the examples for motivation seem to apply to strategy proof linear regression. Moreover, the particular model requires that the features are all public and only 1 label is not. This seems even harder to motivate and the paper does not even try. Finally, one needs to motivate the “price of strategyproofness”. While this sounds cool and seems reasonable, the paper makes no attempt to justify it. In the end we are solving a problem that the authors have found no instance of, using a metric that they did not even try to justify. On the one hand, the metric is somewhat natural. But on the other, it is a worst case ratio that might not tell us very much insight about typical instances.
The second weakness is writing. This is partly related to the above in that the motivation should be paper.
I found the introduction somewhat annoying. The paper cites papers from the last few years as if it had never occurred to anyone before that that agents could report untruthfully when data was going to be fed into an ML like linear regression. Also, much more importantly, as stated above their motivating examples rarely, if ever work. The problem they solve is a specific form of manipulation where you would like the point close to you. This works well if the ML is learning preferences. In the Zara’s case, they just want more inventory. They precisely do NOT want an accurate assessment of their ability to push goods. It seems like most of their motivations also fit this. It would be great to have a single motivation for the actual problem at hand: strategy proof linear regression (where agents want the line to fall through their point).
I am not entirely sold on the key value studied in the paper. The “price of strategyproofness”. Why is this an appropriate metric? Are worst case examples really particularly interesting? This is never discussed. I do think it is the most straightforward metric, so the complaint is not that it is cherry picked. Rather the complaint is that it never justifies this as an important problem beyond a natural problem (given how things are typically defined).
I do find the problem intrinsically interesting. Authors I highly respect have written about this very problem. But the manuscript’s failure to motivate strategyproof regression much less their particular metric rather frightening.
I am not sure in the new (AI) regime where half the proofs are done by AI it is enough to give some vague motivation that is not accurate.
Secondly, the technical write up is so dense as to be unreadable. The authors tried to squeeze a summary of over pages of proofs into a few pages. Unfortunately, this does not work. The paper reads like something by Serre. While I am sure that if the reader took the time everything is there. However, as it is written it is very hard to get through. The audience for reading up a result of this importance this densely written is very small. Likely only authors of the work it builds on. I am a prime candidate for reading this paper given my background (though, I might be a little light on ML versus typically theory background), but the result is not sufficiently important to slog through a write up like this.
For example, the write up does not build up much intuition. It could talk about what happens in the 1-dimensional case and try to build up intuition there about why the solution would need to weight different agents differently. (I did figure this out, but nearly on my own). It could also build up intuition in the 1-d case for how the randomized algorithm works (I don’t really see the intuition, only the proof).
I think that a fair counter for this is that it may very well be an impossible task to write up a theory result like this in 9 pages and give both the results and intuition. If so, then holding this as a bar may prohibit theory paper like this from appearing in ICLR at all. That may very well be, and should be taken into consideration. But it does not change the fact that (in this reviewer's estimation) that the human audience for the paper, as written, is vanishingly small.
Questions for authors
Is strategy proof linear regression used anywhere? Do you have a particular motivating example for the particular setting studied? Would your metric be interesting in this setting?
If not, do you think this is an unfair criteria?
I thank the authors for clarifying their statements and improving the clarity of the paper.
I still find the paper difficult to read. In the unavoidable trade-off for space, intuition and discussion are often sacrificed in favor of lengthy linear algebra computations, and the paper is not particularly pedagogical. That said, the statements are now clear enough for the proofs to be rigorous, and I raise my score.
I agree with Reviewer W33i that, in an era where AI tools make rigorous results easier to obtain, pedagogical exposition and well-motivated problems should carry more weight. For this reason, I now rate the paper as a weak reject. However, I do not have direct research experience on this topic, so I would not object to its acceptance. If it is not accepted, I encourage the authors to work on the presentation, the motivation, or ideally both.