- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The authors study an online prediction problem where the conditional probability given past observed realizations stays close (in terms of KL divergence) to a fixed distribution about which the learner has full or limited knowledge. They provide upper and lower regret bounds for some scenarios which match order-wise.
Critical strengths
S1) Theorem 2 establishes a sharp upper bound that matches the corresponding lower bound up to a constant factor. The resulting improvement in the convergence rate is significant, providing a strong theoretical contribution.
S2) Theorem 4.1 considers a practical case where the true reference is unknown and the learner only has limited information about it. The result exhibits an interesting insight: the regret is controlled by the known-reference regret and the additional cost arising from the incomplete knowledge of the reference. Notably, the latter term may dominate the former when the available reference information is inadequate.
Critical weaknesses
W1) My biggest concern is with respect to the presentation. The main text is poorly structured and hard to follow. The theoretical results seem scattered and insufficiently connected, making it challenging to identify the central contribution of this paper. The authors should make substantial efforts to improve the readability of the paper.
W2) From reading the paper, it seems that it may be (at best) lightly edited LLM output, which also matches the authors' disclosures in the AI statement. There seems to be no effort to make the paper fit for human consumption. It is unclear what value to readers publishing such a paper at a conference would have.
W3) The length of the paper including appendix exceeds 140 pages, and almost all of it is dense mathematical/technical material which by the authors' own disclosure is all AI generated. There is no discussion of why such an unusual amount of technical material is necessary to establish the technical results, and what value publishing it would bring to the theoretical understanding of online learning. After all, the publications at ICLR are still intended mainly for human reading. If the value is just establishing the technical validity itself with no insight into methodology or technique (at least for humans), it stands to reason that the proofs should also be published in a machine-friendly form (e.g., a theorem checker language). In any case, the 2.5 weeks review process of ICLR is in my view not remotely suitable to determine if a paper of this length should be published.
Questions for authors
Q1) Why is the problem important? It seems that the KL condition means that the underlying distribution is in some way "close to i.i.d.". I think the authors should at least give examples of practical problems that exhibit such properties.
Q2) If you can come up with an example for a practical problem regarding Q1, can you do numerical evaluations? If not, why not? (discuss as limitations!)
2 comments
Thank you for your response. I think it is good that the paper is more focused on the main results now (although it still is very long, it is just not quite as extreme as it was before). I am not fully clear from the response what exactly has been done to improve the readability of the paper (and there is also no highlighting in the revised version to help me find the changes). Also, while I respect that the focus of the paper is theoretical, I still think that if it is possible to evaluate numerically, there should at least be some numerical evaluation and if it is not possible there needs to be a discussion of why it is not possible and what additional research will be needed to close that gap. This is important so readers can get an idea of what exactly the nature of the gap between theory and practice is here.
Since a significant part of my main concerns seems to not be addressed, I have decided to keep my current score.
Response to Reviewer AexS
Thank you for the comments on presentation. I have reduced the paper from 141 to 64 pages, with ten pages of main text. Section 3 now presents the learner, its stability proof and the shared KL estimate together. Most secondary extensions have been removed.
You asked why the KL model is useful and whether the inputs are close to i.i.d. The condition still allows strong dependence: a single fair bit repeated forever has conditional KL at most log2 relative to the fair-bit reference. It also allows online inputs to visit rare regions much more often than reference samples do.
To make the model concrete, Section 2 gives a controlled adaptive-testing example whose sampling rule enforces the KL constraint. Section 7 now explicitly states that I have not validated the KL assumption in a practical application. The paper is theoretical and does not include numerical evaluations.