acceptodds
Under review as a conference paper at ICLR 2027

The Sample and Randomness Complexity of Pointwise Replicable Learning

Abstract

Pointwise replicability requires independent training samples and shared randomness to produce agreeing predictions at each fixed test point with high probability. We close the additive sample-complexity gaps of Hopkins, Impagliazzo, and Ye (2026): binary VC classes admit agnostic learning with samples on countable domains and realizable learning with samples. At fixed small failure probability, these match known lower bounds up to logarithms, with the realizable comparison for . On arbitrary measurable domains, we improve the general agnostic finite-randomness sample bound from to using additional shared fair bits. With deterministic base learners these are total bits, at most one above the exact minimum when improper outputs are allowed. For three point functions, properness costs exactly one extra bit when and . One or two shared bits permit a improvement below disagreement , where is the seed count; for , the high-confidence infimum is exactly . We determine matching proper sample complexity just above this boundary. We also prove a dimension-dependent sample lower bound near the bit boundary and matching joint tradeoffs, including confidence, for public products of countable VC-one classes, countable tree intervals, and real intervals, and for unions of intervals without a known partition. The agnostic screen estimates normalized label signals; interval scores combine mass and component costs to make confidence additive. The general finite-bit accuracy gap remains open; a statistical lower bound identifies a limitation of the weighted-CDF compiler.

Primary area:
learning theory
Keywords:
replicable learning, sample complexity, randomness complexity, VC dimension, statistical learning theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_aUXCOpenReview ↗
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 ρ\rho, α\alpha).
    • 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.?

Reviewer_HYmEOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper focuses on the problem of pointwise replicable learning, i.e. independent training runs with shared randomness must agree at each fixed test point. It claims to close the sample-complexity gaps (not closed by Hokin's et al) on countable domains with a novel signal-based screening idea. Using a few shared random bits, it improves the agnostic bounds, almost matching the minimum bit count. The paper also proves matching sample–randomness tradeoffs for structured classes such as intervals, etc. All results are theoretical and proved in an extensive appendix, with no experiments.

Critical strengths

The paper builds towards resolving the Hopkin's model with the idea of working with pxμx\sqrt{p_x}\mu_x instead of pxp_x results in the optimal agnostic rate.

Nice characterizations of the randomness–sample tradeoff, including the improper bit minimum and the matching joint for nontrivial classes.

Critical weaknesses

I believe that given the broad theoretical nature of the paper and authors trying to condense results to nine pages with around 100 pages of results reduces readability and accessibility to a wider audience.

Minor: In abstract, lines 28-31 could be improved. The authors acknowledge that confidence dependence is unresolved in their Remark 2.4. A slightly longer discussion on how their techniques could help for general VC classes would help.

Questions for authors
  1. The paper claims that the realizable bound matches the lower bound of Hopkins et al. (Theorem 3.10) for dimension two or more, and defers the details to Appendix. Could the authors briefly explain in the main text how that lower bound applies in low dimensions, and under what settings such as failure probability the match holds?

  2. For general VC classes, the cost of higher confidence grows with the replicability requirement in the upper bound as mentioned in eq. 3. For the structured classes in theorem 5.1, the two costs only add up, and a matching lower bound is provided. How to assess if the general-VC upper bound is loose in its confidence dependence, and would it be possible for the signal screening to be adapted to give a better additive behavior?

Reviewer_eyXyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the sample and randomness complexity of pointwise replicable learning. It improves the sample complexity upper bound and closes sample-complexity gaps in countable-domain agnostic learning and in realizable learning, alongside additional results concerning finite shared randomness.

Critical strengths

I think the paper has an important theoretical contribution.

Critical weaknesses

The paper is written in a pretty dense way and is not self-contained, which makes it hard for readers not working in this area to follow.

Questions for authors

I didn't quite understand the technical details. So, any intuitive explanations would be helpful.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.