- Rating
- 4
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper contributes a new lower bound for randomized algorithms in an LMO oracle model, and this improves over existing deterministic algorithm.
Overall the contribution is solid and substantial. One concern I have is the following: A natural leap from lower bound to randomized algorithm in the span to general algorithm is via embedding in a large ambient space. This seems like the natural approach, I suggest explaining in the paper why this is not the approach taken here, and what are the technical challenges. (I also raise it as a question here for the authors).
In terms of presentation the definition of LMO is almost invisible. It's an inline in the introduction, but a central notion of this paper. It should either appear in the model setup or be better highlighted.
Also in the abstract. the authors write : "However, upon close inspection both lower bounds are somewhat brittle: " This sounds suggestive of a mistake or oversight in previous work. However, both work that are then discussed acknowledge the reported limitations. I would rephrase this to make it clear that the contribution is for existing and known limitations, not something that requires close inspection.
Critical strengths
See paper summary
Critical weaknesses
see paper summary.
Questions for authors
in paper summary, about random embedding.
2 comments
Thanks.
Thank you for the positive assessment and the suggestions on the model and related-work presentation; all suggestions have been implemented in the revision of the paper (uploaded here).
Why not a random embedding? We agree this is a natural alternative. A span lower bound alone does not control what unrestricted adaptive queries reveal through exact LMO answers. An embedding-based proof would need a separate argument controlling this information. We chose the uniform permutation prior because it lets us describe the posterior and bound expected one-query progress directly, in dimension d=64(T+1). We added a short explanation in the introduction.
LMO definition. We have now displayed the definition of the Linear Minimization Oracle prominently in Section 2.1, immediately before the query/answer interface.
“Brittle” wording. We agree that this wording was unfortunate in hindsight. We intended to distinguish the algorithmic scopes of the results, not to suggest an error in the prior work. We have removed “upon close inspection” and “brittle” from the abstract. The abstract now simply distinguishes the earlier method classes and states the inherited geometric coupling; the contribution opening identifies the extension to unrestricted randomized methods.