- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper considers the problem of pointwise replicable learning, a notion introduced recently by Hopkins, Impagliazzo, and Ye (2026). Pointwise replicability requires that for a fixed test point, two runs of an algorithm on independent samples but with a shared random seed produce the same prediction with high probability. Hopkins et al. gave upper and lower bounds for the sample complexity of agnostic and realizable pointwise replicable learning, but noted that these bounds were not tight. This paper provides improved upper bounds for the sample complexity that are tight up to log factors.
Additionally, it has been known that some amount of shared randomness is necessary for pointwise replicability so that the predictions of the algorithm can be appropriately correlated. When considering sample complexity alone, this random string is allowed to have potentially infinite length, but Hopkins et al. also provided a sample complexity upper bound subject to finite randomness. The authors of this paper improve this upper bound.
Additionally, the paper provides a number of sample and randomness complexity results for a variety of specific learning settings such as unions of k intervals.
Critical strengths
- The paper closes a key open question posed by Hopkins et al. (up to log factors), and significantly improves the shared randomness result.
- The paper's results span a number of different settings, e.g. agnostic, realizable, finite randomness.
Critical weaknesses
- I know that there are a number of different results so there is a lot packed into a short page limit, but I feel that the exposition could be significantly improved to make the paper clearer and easier to follow. In particular,
- the introduction quotes a number of results from prior work without first introducing any of the notation (e.g. definition of , ).
- The organization of the results could have been cleaner, perhaps with a paragraph in the introduction laying out each result and the appropriate section.
- I appreciate that the authors included proof sketches, but they were not written clearly enough to add intuition. For instance, I am not clear on the definition of a "discovery block."
Questions for authors
Could the authors provide clearer intuition for the main agnostic sample complexity result, and discuss how the techniques compare to those of Hopkins et al.?