acceptodds
Withdrawn from ICLR 2027

Correct Labels Can Destroy Uniform Learnability: A Sharp Honest-Insertion Threshold

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

13 views

Abstract

Can adding correctly labeled examples make a learnable problem unlearnable? For each , we construct one fixed class of total binary functions and one fixed known marginal. A learning rule achieves uniformly vanishing risk against all honest insertion channels with fewer than additions to IID observations, whereas additions can force minimax risk toward . The adversary retains every original example, uses only target-correct labels, and acts before the test query, but hides which observations were IID. The proof swaps the roles of clean and inserted samples between two target mixtures. Their observed data have a common probability mass approaching one, but their predictions disagree on most queries. An exact transport characterization gives the largest overlap that honest additions can create between two target mixtures' observed data at each budget. Our example is a countable class of binary-digit formulas under the uniform law on , not a geometrically regular low-dimensional class. The failure is uniform over targets; each fixed target remains consistently learnable. For this class, marking one original IID observation, chosen independently of its value, restores uniformly vanishing risk at every budget without adding data. Thus correct labels and reliable sampling information play different roles in uniform learning.

Primary area:
learning theory
Keywords:
monotone adversarial corruption, honest data insertion, fixed-distribution learnability, minimax lower bounds, statistical indistinguishability, data provenance

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_vVcqOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the recently introduced model of PAC learning with "monotone adversarial corruptions." This model allows for an adversary to observe the usual iid training set S, along with the data-generating process (D, h*), and then inject correctly-labeled datapoints into S. S is then shuffled and presented to the learner.

The paper's primary result is that there exists a hypothesis class of infinite VC dimension that exhibits a sharp degradation in error rates from n−1n - 1 adversarial insertions to nn insertions. As the class has infinite VC dimension, this result holds in the distribution-family model, for certain instances that hold fixed the marginal distribution over unlabeled data. Various other properties of these particular learning instances are also explored, including the effects of identifying an iid datapoint for the learner.

Critical strengths

The paper's primary claims are stated precisely and appear to be sound.

Critical weaknesses

First, the paper is extraordinarily difficult to read. To my eye, it seems to have been generated entirely by an LLM and then left virtually untouched. The writing is constantly using jargon that has not been introduced yet, and I found the technical portions very difficult to follow. Even if its results were notable, I think the paper would need to be rewritten from scratch in order to be fit for publication. Consider the abstract. What is the role of κ≥3\kappa \geq 3 in the second sentence? It does not appear in any property of the hypothesis class. What is an "honest insertion channel"? Why is an "exact transport characterization" being discussed? As with the rest of the paper, the writing is very clunky and quickly becomes hard to follow.

Second, the primary results seem very limited. They only concern the effects of monotone corruption for a specific class of infinite VC dimension on a particular easy-to-learn marginal. In particular, this means that the results: 1) Concern a hypothesis class that is nonlearnable in the usual distribution-free setting; 2) Hold for only particular distribution-family instances, that are constructed ad hoc. I would consider this to be insufficient for publication at a tier-1 conference such as ICLR, COLT, NeurIPS, etc.

Questions for authors

I found the paper nearly impossible to read. On line 51, how can I interpret "At high levels of our class, a target is almost constant"? On lines 75-77, how can I interpret "Product panels provide an exact efficient conditional sampler"?

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

The paper follows up on a recent line of work on monotone adversaries for classification tasks in a model introduced by Larsen et al. The literature has found that an monotone adversary that gives additional correct samples to the algorithm may do this in a way that significantly worsens the learning rate.

This paper studies binary classification for distribution specific settings and showing a sharp threshold for learning. When the number of original iid examples are strictly less than the (correct) labels added by an adversary, the learner achieves vanishing error. In the different regime, every learner can be forced to achieve 12\frac{1}{2} error.

Critical strengths

The setting and the construction seem novel from what I could understand.

Critical weaknesses

The paper is extremely hard to follow.

The authors introduce notation without sufficient explanation. For example, the abstract introduces parameter κ\kappa without defining it. Furthermore, parameters mm and nn are only formally defined later in the text. The paper uses informal terminology like "honest" e.g. "honest insertion channels" as if it is an established term but has not been defined.

It is not sufficiently clear how the claims are structured and what their roles are in the overall argument. Finally, the contribution appears limited. It just says that in a specific distribution and concept class, an adversary can destroy learning. The sharp threshold of n-1 to n seems like a weird artifact of the specific model. The prior work instead focused more on guiding algorithm design to satisfy this property.

Questions for authors
Reviewer_VxeGOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In the honest-insertion setting, the adversary can only add correctly labeled points to a set of nn IID samples. In this setting, this work proves that there exists a binary class such that when the adversary inserts <n< n points, the learner can still achieve vanishingly small risk, but when the adversary inserts ≥n\geq n points, the learner's risk is forced to 1/21/2. This paper establishes a sharp threshold for learnability in the honest insertion setting.

Critical strengths

The paper characterizes a sharp risk threshold (from learnable to unlearnable) for binary functions. Previously, the destruction of learnability had only been characterized in the multiclass and partial binary settings.

Critical weaknesses

The construction of the class is highly artificial and requires infinite precision. Is it possible to characterize the structural properties of H∞\mathcal{H}_{\infty} that lead to the sharp risk threshold phenomenon? Could we see similar behavior in more structured classes?

The construction of the lower bound relies on the sample size nn. The lower bound requires a prior on level Hn\mathcal{H}_n. The target becomes more complicated as nn grows, instead of fixing a target. For a fixed target and a growing sample size, the lower-bound characterization does not hold. I think that this type of learnability should be more properly characterized, and the implications of the result should be more carefully interpreted. Is the structure of increasingly difficult targets necessary to construct the lower bound?

Questions for authors

See the questions in weaknesses.

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

Related papers

Discussion (0)

Sign in to comment.