- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper considers a problem: given a hierarchy of approximating algorithms with increased rate of computational-cost but also increased rate of accuracy, what is the optimal allocation when used in a first-order optimization task.
The paper biggest weakness is in that the introduction does an extremely poor job in framing the result, explaining it's purpose and describe the novel contributions. A reader whose research interest are weakly-aligned with the present scope will find it extremely hard to understand what this paper is about and what is it trying to achieve.
For example, the paper starts with listing as motivation - Neural Networks. Clearly in a conference like ICLR that would be the typical example. But, given the claimed purpose of this paper (estimating gradients) this is somewhat confusing. The claim seems not to be about gradient estimation, given that in standard models noisy and unbiased gradients are normally assumed making it an MC problem. So overall either this example should be further developed or the paper should distinguish approximation of a prediction function, approximation of a scalar objective, and approximation of its gradient. Its theorem assumes the third, while some of its motivating evidence concerns the first.
The relation to previous work and the contribution is also poorly developed:
"Randomized multilevel estimators for biased oracles have been studied by Hu et al. who obtain the same cost exponents in the regime that corresponds to γ > 2"
The comparison here should be further discussed it does not make the incremental contribution sufficiently explicit. As a reviewer, it is hard to assess the overall state of the art.
The contribution is summarized in the sentence:
In both, the oracle exposes a single accuracy knob. What is new here is an oracle with two, a bias and a variance bought at unrelated exponents, and the consequence that the iteration count leaves the bill altogether
This sentence, which summarizes the main contribution was very unclear. If this is the technical novelty then the introduction should be explain why this allows the acclaimed result, how it leads to reduction in total computational cost, and brief discussion on how it is achieved and what are the obstacles.
I think the overall direction and research question is interesting, so I am not pushing for rejection, but overall the lack of clarify makes it hard to assess the result within the existing literature and I think the author will do a great service to the paper if he made major revision in the exposition.
Critical strengths
Overall the formal results are interesting. The message that optimization is at the cost of a single gradient calculation is both surprising and conceptually smart.
Critical weaknesses
The paper is not presented well. Misses context, and is hardly accessible to a reader whos is not an expert in the field.
Questions for authors
I don't have special questions. I think the writing doesn't meet the standard.
We thank the reviewer for the insightful questions and remarks.
Regarding clarity of the introduction, we have added more explanation for the motivation of this paper, as well as an explanation of the "two knobs" technique. We have also added some clarification throughout the text, thanks to your and the other reviewer's remarks. Please tell us if there is any other aspect that should be clarified.
We have also discovered new things that have completely changed the way we compare our results to the work of (Hu et al. 2024): The first proposed algorithm (V-MLMC) is inadapted to our setting and yields suboptimal rates, and while comparing our work we have identified an error in the proofs for the three other algorithms which results in incorrect rates. We have added a more thorough comparison in Appendix A, but since the rates and proofs are incorrect we do not discuss them too much in the main.