- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper extends the study of learning-augmented algorithms for metrical task systems (MTS) with dual predictions to a setting where the algorithm has an access to the prediction values of a given subset of states, called landmarks. From the algorithmic side, the paper presents an algorithm that additively incurs in the gap between the algorithm cost and the optimal cost, where is the time horizon and is the maximum distance to a nearest landmark. Complementing this positive result, the paper also shows that is essentially tight even for a stronger setting where the whole prediction values of the landmarks are known upfront and for simple line metrics. The paper also argues the learnability of the prediction values for landmarks, and demonstrates the result of some qualitative experiments.
Critical strengths
The paper studies a natural extension from the previous work on learning-augmented algorithms for MTS with dual predictions. It is also good to see the paper presents a lower bound result showing the proposed algorithm is essentially optimal for the accurate prediction case.
Critical weaknesses
Despite the strengths, the paper also reveals some clear weaknesses. After understanding the setting, I felt the upper bound of looked somewhat natural to obtain when following the previous work. Hence, I was interested in the lower bound result, but found it quite difficult to understand in the first reading, which is mainly because some terms are used without proper definitions, including the following:
- in Section 4: gadget, unhit, candidate, common baseline , and the optimal cost of a complete gadget,
- in Appendix C: the discrete state space when used in set membership, 1-Lipschitz continuation , a score of a non-target state , an exterior/interior state.
I don’t think these terms are standard enough in MTS or related problems, so they should be properly defined before used. I believe readability becomes a much more important factor in assessing research papers these days. From this perspective, the paper would benefit from revision, especially of the lower bound part.
Questions for authors
- In Line 326, is defined before?
- In Line 786, isn’t simply a function having at and at ? Do we need this complicated definition?
- In Line 899, a landmark satisfying -> a landmark satisfying
- In Line 902: a fixed tie rule -> a fixed tie-breaking rule?
2 comments
Thank you for the response. I will keep my original rating.
Thank you for pointing out these presentation issues. We have reorganized the lower-bound section and clarified Appendix C. Figure 1 now walks through all four rounds, and the terms you mentioned are explained where they first appear.
Regarding the four specific questions:
Definition of D. D=maxx,y∈Md(x,y) denotes the metric diameter, introduced in Section 2.
Definition of ϕ. The values h at a and −h at b are its extrema. The formula also specifies intermediate values, such as ϕ(a+1)=h−1, preserving the 1-Lipschitz property needed to realize fσ=C−σϕ as canonical remaining costs. Two isolated spikes would create a jump of h≥2 between adjacent states, violating this property. We have added this explanation alongside the definition.
Missing landmark symbol. Corrected to “a landmark ℓ∈L satisfying …”.
Tie-breaking terminology. Corrected to “a fixed tie-breaking rule”.