acceptodds
Under review as a conference paper at ICLR 2027

False Learning in Sparse Parity: From Reversed Updates to Resonant Barriers

Abstract

We identify false learning in sparse parity: task-defined data subsets generate systematic updates away from the correct selector, and these reversed updates can be coherently amplified into population-loss barriers. In the factorized selector–evaluator architecture we study, training success forms strikingly non-monotone bands across the input size and task sparsity . We trace this behavior to population atoms that lie deterministically on the wrong slopes of the frozen evaluator's periodic loss, even though the labels and population gradients are exact and the evaluator is correct on its discrete support. During training, many such atoms can cross loss vertices within the same narrow interval, aligning their false-to-true transitions and creating a barrier. A Fourier analysis describes this collective effect through resonances of the atom-distribution characteristic function, coupled to evaluator-loss harmonics. The resonance condition reduces to simple integer relations , and the resulting barriers account for the observed bands of trainability. False learning is therefore not merely ordinary wrong-way motion inside an isolated spurious basin: sparse-parity structure makes the reversed updates and their collective amplification systematic and predictable.

Primary area:
learning theory
Keywords:
sparse parity, modular neural network, modular learning, learning theory

Reviews

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

The article is on analysis of the theoretical benchmark problem: sparse parity. The task in this problem can be defined as follows: input x is n binary digits. unknown subset with k elements (called task set) of the input has parity y, which is provided as label. From the input samples and the subset parity labels, we would like to identify the indices of the task set.

The article's contribution area is the learning characterization of a simple structure for this problem. The structure consists of convex combination of task bits passed through a frozen triangular function producing logits for predicting label. Binary cross entropy is used as the loss function, and only the combination weights are updated. convex combination operation is implemented as gate weights mi∈[0,1]m_i\in[0,1] for each input component xix_i normalized by their sum.

The main contribution, as far as I understand is providing a theoretical justification for the non-monotonic learning-success behaviour for the particular prediction setting with frozen readout. The analysis provided in the article is used to explain the non-monotonic (in n,k) failure behavior experimentally demonstrated at the beginning of the article.

Critical strengths

The main contribution, as far as I understand is providing a theoretical justification for the non-monotonic learning-success behavior for the particular prediction setting with frozen readout. The analysis provided in the article is used to explain the non-monotonic (in n,k) failure behavior experimentally demonstrated at the beginning of the article.

Critical weaknesses

While I do not directly work on the sparse parity problem, I consulted the relevant background and foundational methods to evaluate the submission thoroughly. Despite this effort, I found the manuscript highly difficult to follow in its current form. The paper lacks care about accessiblity: key theoretical intuition, intermediate narrative steps, and contextual framing for the optimization analysis are largely absent.

Because the presentation is overly dense and mechanically structured, it is very difficult to disentangle the manuscript's real technical novelty and theoretical contributions. For the paper to be impactful, the authors need to substantially rewrite the manuscript by explicitly motivating each analytical step while making references to existing results not only in the introduction section, but also in the sections where they are providing their own analysis, comparing their findings against the existing results/analysis methods in clear terms, and giving more emphasis to readability. I believe the article could still be written in a form that can be understandable by wider machine learning community, while providing deep theoretical frontier results for people directly work in that area.

COMMENTS ABOUT SECTIONS

Abstract It is hard to understand what exact problem the paper is addressing and what are the contributions offered about this problem, if you are not deeply familiar with sparse parity problem. I believe it should be written in a more accessible manner.

  1. SETUP
  • frozen parity readout requires more explanation such as what is it and why it is periodic, before introducing the BCE loss.

  • For completeness, it is better to indicate that σ\sigma is the sigmoid function.

  • "...it is alternating between vertices..." what is alternating? vertices of what? input vectors are the vertices of the hypercube and the z values are the projections of these vertices. However, I am not clear what this statement is intending.

  • why is the usual backprop model with loss differentiation is referred as DIFF? Only special case here is readout is frozen, and I do not think that this acronym reflects that?

  1. FALSE LEARNING MECHANISM

This section introduces falsely learned domains without proper motivation and clarification. The idea of partitioning the input space, the role of such partitioning in analysis, the roadmap of the false learning paradigm should better be clarified.

The conditional gradient of the loss (restricted to a domain) is introduced and its inner product with some indicator vector (which is nonnegative and constant in S^* and negative and constant outside) is introduced as a flag for false learning. This requires explanation. Why is it false learning? It makes sense to compare the alignment of the negative gradient with optimal selection vector m_* - the current m vector. However, the authors are looking the alignment with mean shifted optimal m_* only (not caring about the current m_w)

Regarding Figure 3: "Projected updates" term is not defined (in task or caption, is it G terms which looks at inner product over the indicator vector?) The text refers to this figure and claims that it represents theoretical and numerical values. how are they calculated is not clear.

Moving to the "Mechanism" subpart of this section, we can see definitions about h, conditional mass, that needed to be defined earlier. Overall, this key section is poorly written and it is hard to grasp these prerequisite concepts to understand the rest of the article.

SECTION 4 FALSE LEARNING AND TRAINABILITY The beginning of this section claims that Section 3 was on false learning at initialization. But this is not the title or underlined concept in Section 3. The term initialzation appears in Figure 4 only.

Questions for authors
  1. After (2), why "so are z=1/2"? z depends on x_i's no matter what the initialization of the gates.

  2. in (3) why do we look at projection to correct mask (well actually its mean shifted version?). Don't we need to look at the projection to correct mask- current mask?

  3. what is permutation-symmetric gates (the paragraph before (5))? I could not find its definition.

  4. which index i are we picking for the definition of \lambda=m_i/... in (8)?

  5. What would be the impact of removing the frozen constraint on the readout affect the conclusions of the article?

4 comments
AuthorsOpenReview ↗

Response to Reviewer WTAX (Weaknesses)

We thank the reviewer for the careful reading and the detailed, section-by-section comments. We respond to each point below.

Response to Critical Weaknesses.

This paper studies a learning phenomenon in a controlled model. We use sparse parity as a testbed and ask what new behavior appears when it is learned in a factorized architecture. Learning sparse parity by gradients is already well understood (Barak et al., 2022), so behavior that departs from the known picture can be attributed to the factorized architecture. In this architecture, a trainable mask passes its output to a frozen readout that already computes the answer. The readout does the last step correctly, so a failure of training is a failure of selection. The architecture makes the learning mechanics analyzable, and it resembles settings in which one module learns through another, such as reinforcement learning, teacher–student training, and training a module through a pretrained model.

The correctly directed signal that drives sparse-parity learning (Barak et al., 2022) is also present in our model (App. G). The contribution of the paper is the finding that training can still fail for certain (n,k)(n, k), and that where it fails can be predicted before training. Wrong-way gradients in a non-convex problem are not new by themselves. False learning differs from them in two respects.

Systematically predictable. Which subsets of the data push the mask away from the correct one is fixed by the task and the architecture before any training run (Sec. 3). It does not have to be read off from a failed run.

Coherently amplified. Gradients are not just predictable, but can be coherently amplified into a barrier in loss. This occurs when many reversals act together: when n/kn/k is close to an integer, many of these subsets cross a peak of their loss within a narrow interval of training, and their contributions add up. The location is computed from nn and kk (Sec. 4.1, Fig. 6), and training fails where the computed barrier is high (Figs. 1 and 6; Sec. 4.2, Fig. 8).

The new insight is that these failures are organized by the task, so one can tell in advance which tasks will be hard to train and why. In a generic non-convex problem, wrong-way gradients also occur, but they cannot be located in advance.

The broader point is that optimization difficulty need not come only from weak or noisy gradients: strong updates that reduce the loss can be organized by the task and the architecture toward an incorrect state, and their coherence can make the resulting barrier calculable even before training.

We have revised the presentation so that this question and result are stated in plain terms and each analytical step is motivated.

AuthorsOpenReview ↗

Response to Reviewer WTAX (Comments about sections)

Abstract

It is hard to understand what exact problem the paper is addressing and what are the contributions offered about this problem, if you are not deeply familiar with sparse parity problem. I believe it should be written in a more accessible manner.

We have rewritten the abstract in plain terms, and revised the introduction to state the motivation and the contribution explicitly.

Setup.

frozen parity readout requires more explanation such as what is it and why it is periodic, before introducing the BCE loss.

We have revised Sec. 2 as suggested. Before the loss is introduced, it now explains how the readout is obtained (it is trained with the correct mask and then frozen) and why it is periodic (each additional active task bit flips the label).

For completeness, it is better to indicate that σ\sigma is the sigmoid function.

Sec. 2 now states that it is the sigmoid function.

"...it is alternating between vertices..." what is alternating? vertices of what? input vectors are the vertices of the hypercube and the z values are the projections of these vertices. However, I am not clear what this statement is intending.

We have rewritten this sentence. Sec. 2 now defines the vertices as the points z=h/kz = h/k on the zz axis, and says that what alternates is the loss for a fixed label: it is low at one vertex and high at the next.

why is the usual backprop model with loss differentiation is referred as DIFF? Only special case here is readout is frozen, and I do not think that this acronym reflects that?

It is ordinary back-propagation through the frozen readout, as the reviewer says. The name served only to contrast it with the sampled-gate learner of Sec. 5, and we have removed it from the paper.

Section 3 (False learning mechanism).

This section introduces falsely learned domains without proper motivation and clarification. The idea of partitioning the input space, the role of such partitioning in analysis, the roadmap of the false learning paradigm should better be clarified.

We have added this at the start of Sec. 3. The update of the mask is an average over all inputs, and the average hides that different inputs push the mask in different directions. We therefore look at the update from one subset of the data at a time; the natural subsets are the inputs with the same number hh of active task bits. Sec. 3 identifies which subsets push the mask away from the correct one, and Sec. 4 asks when these pushes combine into a barrier.

The conditional gradient of the loss (restricted to a domain) is introduced and its inner product with some indicator vector (which is nonnegative and constant in S^* and negative and constant outside) is introduced as a flag for false learning. This requires explanation. Why is it false learning? It makes sense to compare the alignment of the negative gradient with optimal selection vector m_* - the current m vector. However, the authors are looking the alignment with mean shifted optimal m_* only (not caring about the current m_w)

A negative projection means that the subset closes task gates and opens non-task gates although its labels are correct. Comparing with the correct mask minus the current mask, as the reviewer proposes, gives the same sign; we show this in our answer to the second question below.

Regarding Figure 3: "Projected updates" term is not defined (in task or caption, is it G terms which looks at inner product over the indicator vector?) The text refers to this figure and claims that it represents theoretical and numerical values. how are they calculated is not clear.

The projected updates are the quantities GG of Eq. 3 for each subset hh. The bars are the analytic values (Eq. 7 summed over the subset), and the error bars are the same projection measured numerically over random initial masks. Eq. 4 now defines them for each hh, and the caption refers to it.

Moving to the "Mechanism" subpart of this section, we can see definitions about h, conditional mass, that needed to be defined earlier. Overall, this key section is poorly written and it is hard to grasp these prerequisite concepts to understand the rest of the article.

Sec. 3 now recalls hh in its first paragraph. The conditional mass is used only in the "Mechanism" part, where it is defined.

Section 4.

The beginning of this section claims that Section 3 was on false learning at initialization. But this is not the title or underlined concept in Section 3. The term initialzation appears in Figure 4 only.

Sec. 3 gives the sign of the update for each subset and illustrates it at the initial mask (Figs. 3 and 4). Sec. 4 follows these signs along training.

AuthorsOpenReview ↗

Response to Reviewer WTAX (Q1–Q5)

Response to the 'Questions for Authors

Q1.

After (2), why "so are z=1/2z=1/2"? z depends on xix_i's no matter what the initialization of the gates.

The sentence is meant for the distribution of zz, not for individual inputs. With nearly equal gates, zz is the fraction of active bits, so its distribution is centered at 1/21/2. For an individual input, zz depends on xx, as the reviewer says. We have corrected the sentence.

Q2.

in (3) why do we look at projection to correct mask (well actually its mean shifted version?). Don't we need to look at the projection to correct mask- current mask?

The two comparisons are the same, and they give the same sign. The readout sees only the pooled value zz, and zz depends only on the relative sizes of the gates: multiplying all gates by a common factor changes nothing (Eq. 2). Masks should therefore be compared after dividing by the sum of their gates. Take a mask in which all task gates share one value and all non-task gates share another; the uniform starting mask and the correct mask are both of this form. Compared in this way, the correct mask minus the current mask raises the task gates and lowers the non-task gates. This is the direction dd of Eq. 3. Wherever the current mask lies between the uniform mask and the correct one, the direction is the same and only its length changes. This is why the current mask does not appear in dd.

The reviewer's projection can also be computed directly. The loss does not change when all gates grow together, so the update gg of Eq. 3 satisfies g⋅m=0g \cdot m = 0 for the current mask mm. With the correct mask m∗m^{\ast}, this gives g⋅(m∗−m)=g⋅m∗g \cdot (m^{\ast} - m) = g \cdot m^{\ast}: the current mask drops out. For the masks described above, g⋅m∗g \cdot m^{\ast} and g⋅dg \cdot d differ only by a positive factor.

A negative projection means that this subset of the data closes task gates and opens non-task gates although its labels are correct. This is what we call false learning. Sec. 3 now explains the direction dd right after Eq. 3.

Q3.

what is permutation-symmetric gates (the paragraph before (5))? I could not find its definition.

It means that all task gates share one value, mam_a, and all non-task gates share one value, mim_i. The uniform initial mask and the correct mask are both of this form. The paragraph before Eq. 5 now states this definition.

Q4.

which index ii are we picking for the definition of λ=mi/...\lambda=m_i/... in (8)?

No index is picked. Here mim_i is the common value of the non-task gates and mam_a that of the task gates, as in the previous answer, so λ\lambda is the non-task gate divided by the mean gate. It equals 11 at the uniform mask and 00 at the correct mask. Sec. 4 now recalls this where λ\lambda is defined.

Q5.

What would be the impact of removing the frozen constraint on the readout affect the conclusions of the article?

The frozen readout is the intended setup, because it models training one module through another. In the factorized architecture, the mask and the readout can also be trained jointly. We find that similar (n,k)(n, k) tasks remain difficult to train, as in the frozen case. In joint training, the mask receives correct gradients only after the readout has begun to learn the alternating landscape.

We hope these responses clarify the points raised, and we are happy to answer any further questions.

I would like to thank authors for their responses. I believe the revision improved the article's presentation in the positive direction. However, I still believe that there is still room for significant improvement. I preserve my initial score.

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

This paper studies sparse parity learning in a model that trains an input selector through a frozen evaluator. The authors show that certain predefined subsets of the data produce updates away from the correct selection and explain how these updates can combine to create population-loss barriers, producing non-monotone patterns of training success. A Fourier analysis predicts the structure of these barriers. Experiments compare SGD and AdamW, with additional analyses of sampled gates, modular addition, and departures from symmetry.

Critical strengths
  1. The paper is generally clear. The progression from individual misleading updates to collective barriers gives the analysis a coherent structure.
  2. The misleading data subsets are defined from the task itself, and the authors explain when their contributions reinforce or cancel each other. This provides a more informative account than identifying wrong-way gradients after observing an unsuccessful run.
  3. The authors did a good job explaining why nearby parity tasks can have very different training outcomes, which is a useful contribution within the studied setting.
Critical weaknesses
  1. Can the author provide more evidence to support your claim? I find this paper interesting but impractical because it lacks of more direct experiments.
  2. Fig. 2 shows encouraging agreement with a learned evaluator, but only for one task configuration. This is limited scope and experiments.
Questions for authors
  1. Can the author provide more evidence to support your claim? I find this paper interesting but impractical because it lacks of more direct experiments. Any experiments (baselines) will be helpful for me to understand.
2 comments
AuthorsOpenReview ↗

Response to Reviewer noaj

We thank the reviewer for the encouraging assessment and the constructive suggestions. We respond to each point below.

To support this response, we have added a new Appendix H (in red) to the revised PDF, with new experiments and figures (Figs. 12–15). The rest of the paper is not changed yet; App. H will be integrated into the paper in the coming revision.

W1.

Can the author provide more evidence to support your claim? I find this paper interesting but impractical because it lacks of more direct experiments.

The direct experiment in the paper is Fig. 1: every cell is a set of training runs, and the runs fail where the barrier computed before training is high (Fig. 6). Over the whole grid and for both optimizers, every task that fails has a barrier, and the failed runs that we followed stop at the local minimum in front of the barrier, at the location computed before training. Neighboring tasks serve as a baseline: the architecture and the training are the same, and tasks without a barrier are learned while their neighbors with a high barrier are not.

To test the link more directly, we changed only the barrier and kept everything else. The paper shows that the barrier needs the discrete structure of the data: when this structure is smoothed out, the barrier disappears from the loss (Fig. 7). We did this in training by mixing a small continuous (Gaussian) component into the non-task bits; the task, the evaluator and the training protocol are unchanged. For the task of Fig. 7, (n,k)=(16,5)(n, k) = (16, 5), the success rate rises from near 0 to 1 once the computed barrier disappears. When the inputs are fully continuous, the tasks that failed between successful neighbors are learned. The new App. H adds two results. Rounding the vertices of the evaluator, which lowers only the barrier, gives the same: in three tasks the success rate goes from 0 to 1 near the rounding at which the computed barrier disappears (Fig. 15). And over all tasks, we compute the smoothing at which each barrier disappears, and the success rate is mostly near zero when the initial smoothing is below it, and rises above it (Fig. 14).

W2.

Fig. 2 shows encouraging agreement with a learned evaluator, but only for one task configuration. This is limited scope and experiments.

The learned evaluator is used in every training run of the paper, where it is trained and then frozen (Sec. 2); Fig. 2 shows its shape for one task as an example. To widen the comparison, we note that the evaluator depends on the task only through kk, and we repeated the comparison of Fig. 2 for k=3k = 3–88. The trained evaluators again follow the triangle wave, and the barriers computed with them agree with those of the triangle wave, typically within 2–3% (new App. H, Fig. 12).

Q1.

Can the author provide more evidence to support your claim? I find this paper interesting but impractical because it lacks of more direct experiments. Any experiments (baselines) will be helpful for me to understand.

See W1 and W2 for related answers.

We hope these responses clarify the points raised, and we are happy to answer any further questions.

Thanks authors for their detailed rebuttal, and I feel confident to keep my current score.

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

This paper investigates an optimization failure phenomenon termed false learning in sparse parity problems. The authors study a factorized architecture consisting of a trainable feature selector and a frozen parity evaluator. They show that certain subsets of training data can systematically produce gradients that move the selector away from the ground-truth solution, despite having correct labels. Furthermore, they demonstrate how these misleading gradients can collectively create barriers in the population loss. Through Fourier analysis, the authors characterize these barriers and explain the non-monotonic training success patterns observed across different problem dimensions and sparsity levels. Experiments with SGD and AdamW support the theoretical analysis.

Critical strengths

Interesting optimization phenomenon. The paper identifies and characterizes a structured form of misleading gradient updates. The observation that correct supervision can systematically produce updates opposing the desired feature-selection direction is interesting.

Insightful theoretical analysis. The Fourier decomposition of the population loss provides an analytical explanation for the emergence of resonant barriers. In particular, the connection between barrier formation and integer relationships between the problem dimension (n) and sparsity (k) is an interesting contribution.

Supporting experimental evidence. The authors conduct experiments across a range of problem configurations and optimizers. The observed non-monotonic training success patterns are consistent with the proposed theoretical mechanism. The additional investigations of symmetry breaking and alternative learning rules also strengthen the analysis.

Critical weaknesses

Limited generality of the problem setting. The analysis relies on a highly specialized architecture with a trainable mask and a frozen parity evaluator. The evaluator is constructed using knowledge of the parity structure and exhibits a particular periodic loss landscape. It remains unclear whether the identified phenomenon is relevant to conventional end-to-end neural network training or is primarily an artifact of this architecture.

Dependence on the evaluator's interpolation. The parity task only constrains the evaluator's predictions at discrete input values, while the proposed mechanism depends heavily on its behavior and gradients between these points. The theoretical results rely on a triangle-wave approximation, and the robustness of the phenomenon to substantially different interpolations is not sufficiently established.

Limited theoretical guarantees regarding optimization failure. Although the authors derive an analytical approximation of the barrier height, they do not establish rigorous barrier bounds or a convergence result connecting the barriers to optimization failure. Furthermore, the barrier analysis is largely restricted to a permutation-symmetric trajectory, whereas actual optimization takes place in the full parameter space. The relationship between barrier height and training success is primarily supported empirically.

Questions for authors

How sensitive are the false-learning phenomenon and resonant barriers to the choice of frozen evaluator? Would similar results hold for alternative smooth interpolations that are equally accurate on the discrete parity inputs?

Would the observed non-monotonic training success patterns persist if the selector and evaluator were trained jointly, or if a conventional neural network directly predicted the parity label from the input?

Can the authors establish rigorous upper or lower bounds on the barrier height, or provide theoretical guarantees connecting barrier height to SGD convergence behavior?

To what extent do the barriers identified along the permutation-symmetric trajectory remain genuine optimization obstacles in the full parameter space? Could symmetry-breaking directions allow gradient descent to bypass these barriers?

4 comments
AuthorsOpenReview ↗

Response to Reviewer TfXv (W1)

We thank the reviewer for the careful reading and the constructive comments. We respond to each point below.

To support this response, we have added a new Appendix H (in red) to the revised PDF, with new experiments and figures (Figs. 12–15). The rest of the paper is not changed yet; App. H and the other changes mentioned below will be integrated into the paper in the coming revision.

W1.

Limited generality of the problem setting. The analysis relies on a highly specialized architecture with a trainable mask and a frozen parity evaluator. The evaluator is constructed using knowledge of the parity structure and exhibits a particular periodic loss landscape. It remains unclear whether the identified phenomenon is relevant to conventional end-to-end neural network training or is primarily an artifact of this architecture.

This paper studies a learning phenomenon in a controlled model. We use sparse parity as a testbed and ask what new behavior appears when it is learned in a factorized architecture. Learning sparse parity by gradients is already well understood (Barak et al., 2022), so behavior that departs from the known picture can be attributed to the factorized form. The architecture makes the learning mechanics analyzable, and it resembles settings in which one module learns through another, such as reinforcement learning, teacher–student training, and training a module through a pretrained model.

The evaluator. The evaluator is not hand-designed. It is trained on the correct support points and then frozen (Sec. 2). The periodic landscape is not our artificial choice either (W2).

Not an artifact of the architecture alone. Neighboring values of nn or kk give opposite outcomes (Fig. 1) even though everything else in the setup is the same. What separates them is the resonance relation between nn and kk, a property of the task. Even when the evaluator is trained jointly with the selector, we find that similar (n,k)(n, k) tasks remain difficult to train, as in the frozen case (Q2). The architecture makes the phenomenon possible, and the task decides where training fails.

Conventional networks. A conventional network that predicts the label directly does not have a useful alternating map from inputs to the label. We therefore do not expect false learning or the non-monotone pattern there; its training should follow the known picture of sparse parity learning (Barak et al., 2022). False learning is a statement about the factorized setting.

Significance. We do not claim that false learning occurs generically in factorized systems (Sec. 6). The broader point is that optimization difficulty need not come only from weak or noisy gradients: strong updates that reduce the loss can be organized by the task and the architecture toward an incorrect state, and their coherence can make the resulting barrier calculable even before training. We think this is a useful insight into learning dynamics, and a concrete lesson for systems in which one module or agent learns from another. We will make this scope and the motivation of the setting explicit in the introduction.

AuthorsOpenReview ↗

Response to Reviewer TfXv (W2)

W2.

Dependence on the evaluator's interpolation. The parity task only constrains the evaluator's predictions at discrete input values, while the proposed mechanism depends heavily on its behavior and gradients between these points. The theoretical results rely on a triangle-wave approximation, and the robustness of the phenomenon to substantially different interpolations is not sufficiently established.

We agree that the shape of the evaluator between the support points matters: it sets how high the barriers are. But what induces false learning is a periodic landscape with sharp vertices together with a discrete distribution of the scalar pool. Where the false gradients add up to a barrier is decided by the task, through the resonance conditions, which are integer relations between nn and kk.

The triangle wave is not chosen for the theory. The evaluator's alternation is forced by the parity label. Among alternating interpolations, the piecewise-linear one with sharp vertices is the natural choice: it is symmetric, it has the least curvature between the support points, and it is what a trained evaluator converges to (Fig. 2), and what weight decay selects (App. E). The theory uses the triangle wave as the idealized form of this trained evaluator. Any piecewise-monotonic interpolation has the same sign of slope on each branch, and therefore gives similar reversed updates.

New experiments. We varied the evaluator in two ways and recomputed the barrier (see new App. H, Figs. 12 and 13):

  1. The heights at the support points, set to those of trained evaluators, which differ from the triangle wave by about 7% on average.
  2. The sharpness of the vertices, rounded over a width of up to 10% of the spacing between support points, much larger than the natural size produced by training (at most about 0.1% of the spacing). So this is an artificial variation, but it tests substantially different interpolations and isolates the origin of false learning.

Under (1), the barrier changes by about 3% in the median over all tasks. Under (2), the barrier becomes lower, and it disappears at a width of about 7% of the spacing, at least 70 times the rounding of trained evaluators. The analysis predicts this. In Fourier space, rounding a vertex over width ss damps the qq-th harmonic by approximately e−π2q2s2/2e^{-\pi^2 q^2 s^2/2}, the same factor as the broadening analyzed in App. D (Eq. 41, Fig. 7) and App. H. In real space, a barrier forms when many atoms cross a loss vertex within a narrow training interval, and a rounded vertex spreads the crossings over a wider interval and weakens their synchronization. The rounding lowers the barriers without changing the resonance conditions, which come from the atom spectrum A(qλ)A(q\lambda).

In short, the evaluator's shape sets how high the barriers are, and (n,k)(n, k) sets where they can form. The sharp case is the relevant one, because it is what training produces.

AuthorsOpenReview ↗

Response to Reviewer TfXv (W3, Q1)

W3.

Limited theoretical guarantees regarding optimization failure. Although the authors derive an analytical approximation of the barrier height, they do not establish rigorous barrier bounds or a convergence result connecting the barriers to optimization failure. Furthermore, the barrier analysis is largely restricted to a permutation-symmetric trajectory, whereas actual optimization takes place in the full parameter space. The relationship between barrier height and training success is primarily supported empirically.

The barrier heights are computed, not approximated. The values of BB in Fig. 6 are obtained from the population loss for every (n,k)(n, k), using only nn and kk and no information from training runs (Sec. 4.1). The approximate formula in that section explains why the barriers form and at which tasks; the values in Fig. 6 do not rely on it.

The link to training success. We agree that this link is supported empirically, and deriving a convergence result is beyond the scope of this paper. We have now made the link more concrete: we show why the symmetric path is the relevant one, and how far training must depart from it to avoid the barrier.

  1. The symmetric path attracts training. The permutation-symmetric subspace is invariant, and small departures from it decay under the positive transverse curvature on typical paths to the first barrier (App. D). The departure produced by our initialization, μj∼N(0,0.12)\mu_j \sim \mathcal N(0, 0.1^2), corresponds to a spread σw≃0.03\sigma_w \simeq 0.03 at (16,5)(16, 5), and it lowers but preserves the barrier (Fig. 7).
  2. Symmetry breaking can bypass a barrier only when it is large. In the new App. H, we compute, from nn and kk alone, the size of symmetry breaking needed to go around a barrier. It is the width of the barrier along the symmetry-breaking direction.
  3. The success rate changes at this size. Across tasks, the success rate is mostly near zero when the initialization is below this size, and rises above it (Fig. 14). The link between the barrier and training success thus appears at a scale computed from the barrier itself. This comparison correlates with training success better than the height does.
  4. A direct test. With the task, the initial gates and the data fixed, we lowered only the barrier, by rounding the evaluator. In three tasks, the success rate goes from zero to one near the rounding at which the computed barrier vanishes (Fig. 15).

So the barrier on the symmetric path is a real obstacle for training that starts near the symmetric subspace, and we now quantify how robust it is to symmetry breaking. The training runs impose no symmetry, and every gate is trained separately; they fail where the computed barrier is high (Figs. 1 and 6). We have added these results as App. H.

Q1.

How sensitive are the false-learning phenomenon and resonant barriers to the choice of frozen evaluator? Would similar results hold for alternative smooth interpolations that are equally accurate on the discrete parity inputs?

The sensitivity to the trained evaluator is small. Varying the evaluator's heights at the support points as in trained evaluators changes the barrier by about 3% in the median over all tasks (W2). Their shape between the support points changes it by less than 1% (App. H, Fig. 13).

For alternative interpolations, false learning itself remains. Any evaluator that is correct on the discrete inputs must alternate between them, and any piecewise-monotonic interpolation has the same sign of slope on each branch, so it gives similar reversed updates. Smooth interpolations lower the barriers. Rounding the vertices, while keeping the values at the support points, lowers or removes the barrier (App. H, Fig. 13), as predicted by the damping of high harmonics (App. D, Eq. 41), but it does not change the resonance conditions, which are set by (n,k)(n, k). The sharp case is the relevant one, because it is what a trained evaluator converges to (Fig. 2, App. E).

AuthorsOpenReview ↗

Response to Reviewer TfXv (Q2–Q4)

Q2.

Would the observed non-monotonic training success patterns persist if the selector and evaluator were trained jointly, or if a conventional neural network directly predicted the parity label from the input?

Joint training. The frozen evaluator is the intended setup, because it models training one module through another. In the factorized architecture, the selector and the evaluator can also be trained jointly. We find that similar (n,k)(n, k) tasks remain difficult to train, as in the frozen case. In joint training, the selector receives correct gradients only after the evaluator has begun to learn the alternating landscape.

Conventional network. A conventional network without factorization does not compress the inputs into a single scalar, and has no fixed alternating map from that scalar to the label. We therefore do not expect false learning or the non-monotone pattern there. Its training should follow the known picture of sparse parity learning (Barak et al., 2022). False learning is a statement about the factorized setting.

Q3.

Can the authors establish rigorous upper or lower bounds on the barrier height, or provide theoretical guarantees connecting barrier height to SGD convergence behavior?

Barrier height. For the triangle-wave evaluator, the barrier height on the symmetric path is computed exactly for every (n,k)(n, k) (Sec. 4.1), so a bound is not needed there. For trained evaluators, the barrier differs from this value by about 3% in the median over all tasks (W2, App. H), and the difference decreases as the margin ℓ0\ell_0 grows. For evaluators with rounded vertices, the analysis gives the dependence directly: rounding over width ss damps the qq-th harmonic by e−π2q2s2/2e^{-\pi^2 q^2 s^2/2} (Eq. 41), so the barrier becomes lower while the resonance conditions stay the same.

SGD convergence. A theoretical guarantee connecting the barrier to SGD convergence is beyond our scope. In its place, we quantify how large a symmetry breaking is needed to bypass the barrier, and show that the success rate changes at this size, across tasks and when the barrier alone is lowered (W3, Q4, App. H).

Q4.

To what extent do the barriers identified along the permutation-symmetric trajectory remain genuine optimization obstacles in the full parameter space? Could symmetry-breaking directions allow gradient descent to bypass these barriers?

We agree that symmetry breaking can bypass the barrier computed on the symmetric path, and that this can weaken the correlation between barrier height and training success. The question is how much symmetry breaking is needed.

Small departures decay. The symmetric subspace is invariant and attracting on typical paths to the first barrier: small differences between gates decay under the positive transverse curvature (App. D). A departure of the size present at initialization, σw≃0.03\sigma_w \simeq 0.03, lowers the barrier but leaves it in place (Fig. 7).

Large departures bypass the barrier. In the new App. H, we find that the symmetry breaking needed to go around a barrier is the width of the barrier along the symmetry-breaking direction. Across tasks, the success rate is mostly near zero when the initialization is below this size, and rises above it (Fig. 14). This comparison correlates with training success better than the height does. And when only the barrier is removed, by rounding the evaluator, the same runs that stopped in front of it train successfully (Fig. 15).

The barriers therefore remain obstacles in the full parameter space for training that starts near the symmetric subspace. This agrees with the training runs, which impose no symmetry and still fail where the computed barrier is high (Figs. 1 and 6).

We hope these responses clarify the points raised, and we are happy to answer any further questions.

Reviewer_WYBfOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a phenomenon called "false learning" in sparse parity learning using a selector–evaluator architecture. The authors show that certain subsets of training samples can produce gradient updates that move the selector away from the ground-truth feature set, even when the frozen evaluator is correct on its discrete support. The paper provides an analytical characterization of these reversed gradients by grouping samples into atoms based on the numbers of relevant and irrelevant active features. It further uses Fourier analysis to explain how these gradient contributions can synchronize under certain relationships between the input dimension and sparsity, potentially creating population-loss barriers. The authors validate their analysis through experiments showing non-monotonic patterns of training success across different and , and relate these patterns to the predicted resonance conditions.

Critical strengths

The main strength is its analytical characterization of the observed training behavior. In particular, the Fourier analysis provides a mathematical explanation for why certain gradient contributions can synchronize under specific relationships between the input dimension and sparsity. This helps explain the non-monotonic training patterns observed in the experiments.

Critical weaknesses
  1. Limited novelty and motivation of the proposed "false learning" phenomenon. The proposed learning method does not provide a theoretical guarantee that optimizing BCE loss through the frozen evaluator can recover the ground-truth feature selector. More importantly, the paper does not establish why these gradients should be expected to align with correct selector recovery in the first place. Therefore, I do not find the observed false learning particularly surprising. It seems that this phenomenon may be largely induced by the specific learning method and surrogate objective chosen by the authors, rather than reflecting an intrinsic difficulty of sparse parity learning. This raises concerns about the novelty and significance of the main contribution.

  2. Limited generality and significance of the Fourier analysis. The Fourier analysis mainly characterizes the periodic loss landscape induced by the chosen evaluator. Although it provides an analytical explanation for the observed resonance patterns, it is unclear how these findings generalize beyond this particular evaluator and learning architecture. In particular, the evaluator is only guaranteed to be correct on discrete parity support points, while its gradients between these points depend on the chosen interpolation. Different evaluators with identical predictions on the discrete support may produce different loss landscapes and resonance barriers. Therefore, I am not convinced that the Fourier analysis reveals a general property of sparse parity learning rather than explaining the behavior of a specifically constructed surrogate objective.

Questions for authors
  1. Motivation for the learning framework. The authors attempt to recover the ground-truth feature set by optimizing the BCE loss through a frozen evaluator. Could the authors provide more theoretical intuition or justification for why this optimization objective is expected to recover the correct feature selector?

  2. Novelty of the false learning phenomenon. The paper defines "false learning" as gradient updates moving away from the ground-truth feature set. However, gradient descent does not necessarily move toward the global optimum, especially in non-convex optimization problems. Could the authors clarify how the proposed false learning phenomenon differs from this well-known behavior, and what new insights it provides?

  3. Correctness of the frozen evaluator. The authors state that a perfectly correct evaluator can still produce misleading gradients. However, the evaluator's correctness is only guaranteed on the discrete support points corresponding to the ground-truth selector. Its behavior at intermediate points depends on how it is extended to the continuous domain. Could the authors clarify whether the observed misleading gradients are primarily a consequence of this continuous extension? In this sense, would it be more precise to state that correctness on the discrete support does not guarantee useful gradients for recovering the ground-truth selector?

  4. Relevance to sparse parity learning. Sparse parity can be efficiently solved using other established methods. Could the authors elaborate on why the proposed selector–evaluator architecture is a meaningful setting for studying sparse parity? In particular, how can we distinguish difficulties intrinsic to sparse parity learning from those introduced by the specific learning framework?

  5. Generality of the Fourier analysis. The authors use Fourier decomposition to explain resonance phenomena at certain ratios of n/kn/k. While this provides an interesting analytical characterization, the periodic structure appears to depend heavily on the chosen evaluator. Could the authors clarify what general insights this analysis provides about sparse parity learning beyond the optimization landscape induced by this particular periodic evaluator?

5 comments
AuthorsOpenReview ↗

Response to Reviewer WYBf (W1)

We thank the reviewer for the detailed comments and questions. We respond to each point below.

To support this response, we have added a new Appendix H (in red) to the revised PDF, with new experiments and figures (Figs. 12–15). The rest of the paper is not changed yet; App. H and the other changes mentioned below will be integrated into the paper in the coming revision.

Critical weakness W1.

Limited novelty and motivation of the proposed "false learning" phenomenon. The proposed learning method does not provide a theoretical guarantee that optimizing BCE loss through the frozen evaluator can recover the ground-truth feature selector. More importantly, the paper does not establish why these gradients should be expected to align with correct selector recovery in the first place. Therefore, I do not find the observed false learning particularly surprising. It seems that this phenomenon may be largely induced by the specific learning method and surrogate objective chosen by the authors, rather than reflecting an intrinsic difficulty of sparse parity learning. This raises concerns about the novelty and significance of the main contribution.

This paper studies a learning phenomenon in a controlled model. It does not propose a method for solving sparse parity. Learning sparse parity by gradients is already well understood (Barak et al., 2022), so we use it as a testbed and ask what new behavior appears when it is learned in a factorized architecture. In this architecture, a trainable selector passes its output to a frozen evaluator that already computes the answer. The analogous structure appears in reinforcement, behavioral, teacher-student learning and in training through a frozen pretrained model. The objective is not a surrogate: it is the ordinary supervised BCE loss with the true labels.

Why recovery is expected. There are good reasons to expect gradient training to recover the correct selector. The correct selector is the global minimum of the loss, because any wrong selection places some inputs where the evaluator gives a larger loss. And the correctly directed signal that drives sparse-parity learning (Barak et al., 2022) is also present in our model (App. G). The contribution of the paper is the finding that training can still fail for certain (n,k)(n, k), and that where it fails can be predicted before training from the collective behavior of the atoms.

What is new: the failures are predictable. False learning comes from two properties of the setting, not from an inefficient method:

  1. A periodic loss landscape with sharp vertices. The parity label flips each time one more task bit is active, so the correct evaluator alternates between neighboring support points.
  2. A discrete input distribution. Many inputs are projected to a common value of the scalar pool (an atom), so they move together and act collectively.

Because of these properties, the subsets of the data that push the selector away from the correct one are fixed before training (Sec. 3). During training, many of them cross loss vertices toward the correct basin at the same time, and this creates a barrier in the loss. When this happens is set by resonance conditions between nn and kk: the barrier is calculated from (n,k)(n, k) alone (Fig. 6), and it correlates with the success rates of actual training runs (App. C, Fig. 9). This predictability is what distinguishes false learning from the usual wrong-way gradients of a non-convex landscape.

Task or method? We agree that false learning is not an intrinsic property of sparse parity under every learner. It arises when sparse parity is learned in this factorized form. But it is not produced by the method alone either. Neighboring values of nn or kk can give opposite outcomes (Fig. 1) while everything else in the setup is the same. What separates them is the resonance relation between nn and kk, a property of the task. The architecture makes the phenomenon possible, and the task decides where training fails.

Significance. We do not claim that the same barriers occur generically in selector–evaluator systems (Sec. 6). The broader point is that optimization difficulty need not come only from weak or noisy gradients. Strong updates that reduce the loss can be organized by the task and architecture toward an incorrect state, and their coherence makes the resulting barrier calculable before training. We think this is a useful insight into learning dynamics, and a concrete lesson for those learning systems that are more prevalent in the multi-agent era, where one module learns through another.

We will make this scope and the motivation of the setting explicit in the introduction.

AuthorsOpenReview ↗

Response to Reviewer WYBf (W2, Q1)

W2.

Limited generality and significance of the Fourier analysis. The Fourier analysis mainly characterizes the periodic loss landscape induced by the chosen evaluator. Although it provides an analytical explanation for the observed resonance patterns, it is unclear how these findings generalize beyond this particular evaluator and learning architecture. In particular, the evaluator is only guaranteed to be correct on discrete parity support points, while its gradients between these points depend on the chosen interpolation. Different evaluators with identical predictions on the discrete support may produce different loss landscapes and resonance barriers. Therefore, I am not convinced that the Fourier analysis reveals a general property of sparse parity learning rather than explaining the behavior of a specifically constructed surrogate objective.

We agree that the shape of the evaluator between the support points matters quantitatively: it sets how high the barriers are. But it does not decide where reversals can add up to a barrier; that is decided by the task. The evaluator is also less arbitrary than it may appear. Its alternation is forced by the parity label, and its triangle shape is what training produces (Fig. 2, App. E; see Q3).

The analysis needs only two things: an evaluator that alternates with sharp turns, and the discrete atoms produced by projecting the binary inputs onto a single scalar. The exact shape of the evaluator enters only through the Fourier coefficients L~q\tilde L_q, so it changes barrier heights quantitatively. The resonance conditions come from the atom distribution A(qλ)A(q\lambda), which is fixed by nn and kk. Exact periodicity is not needed either. Fourier decomposition is the natural tool here because the barriers are built from high harmonics of the loss.

New experiments. We varied the evaluator in two ways and recomputed the barrier (see new App. H, Figs. 12 and 13):

  1. The heights at the support points, set to those of trained evaluators, which differ from the triangle wave by about 7% on average.
  2. The sharpness of the vertices, rounded over a width of up to 10% of the spacing between support points. This is an artificial variation to understand the true origin of false learning, since training does not produce such rounding (at most about 0.1% of the spacing).

Under (1), the barrier changes by about 3% in the median over all tasks. Under (2), the barrier height decreases significantly, and the barrier disappears at a width of about 7% of the spacing, at least 70 times the rounding of trained evaluators. The analysis predicts this. In the Fourier-space picture, rounding a vertex over width ss damps the qq-th harmonic by approximately e−π2q2s2/2e^{-\pi^2 q^2 s^2/2}, the same factor as the broadening analyzed in App. D (Eq. 41, Fig. 7). In the real-space picture, a barrier forms when many atoms cross a loss vertex within a narrow training interval. A rounded vertex spreads the crossings over a wider interval and weakens their synchronization.

Rounding vertices of this kind does not arise in training, and it lowers the barriers without changing the resonance conditions, which come from A(qλ)A(q\lambda). In short, the evaluator's shape sets how high the barriers are, and (n,k)(n, k) sets where they can form.

Questions for Authors Q1.

Motivation for the learning framework. The authors attempt to recover the ground-truth feature set by optimizing the BCE loss through a frozen evaluator. Could the authors provide more theoretical intuition or justification for why this optimization objective is expected to recover the correct feature selector?

As discussed under W1, there are two reasons to expect recovery. First, the correct selector is the global minimum of the loss: with it, every input lands on a support point where the evaluator is correct, and any wrong selection gives a larger loss. Second, gradient training is known to learn sparse parity by amplifying a small, correctly directed signal (Barak et al., 2022), and this signal is also present in our model (App. G).

The expectation is met at the tasks without a barrier, which are learned (Figs. 1 and 6). The contribution of the paper concerns the remaining tasks. Even with both reasons in place, training fails for certain (n,k)(n, k), and where it fails can be computed before training from the collective behavior of the atoms.

AuthorsOpenReview ↗

Response to Reviewer WYBf (Q2, Q3)

Q2.

Novelty of the false learning phenomenon. The paper defines "false learning" as gradient updates moving away from the ground-truth feature set. However, gradient descent does not necessarily move toward the global optimum, especially in non-convex optimization problems. Could the authors clarify how the proposed false learning phenomenon differs from this well-known behavior, and what new insights it provides?

We agree that wrong-way gradients in a non-convex problem are not new by themselves. False learning differs from them in two respects.

Systematically predictable. Which subsets of the data push the selector away from the correct one is fixed by the task and the architecture before any training run (Sec. 3). It does not have to be read off from a failed run.

Coherently amplified. Gradients are not just predictable, but can be coherently amplified into a barrier in loss. This occurs when many reversals act together: when n/kn/k is close to an integer, many atoms cross loss vertices within a narrow interval of training, and their contributions add up. The location is computed from nn and kk (Sec. 4.1, Fig. 6), and its height correlates with the success rates of actual training runs (App. C, Fig. 9).

The new insight is that these failures are organized by the task, so one can tell in advance which tasks will be hard to train and why. In a generic non-convex problem, wrong-way gradients also occur, but they cannot be located in advance.

Q3.

Correctness of the frozen evaluator. The authors state that a perfectly correct evaluator can still produce misleading gradients. However, the evaluator's correctness is only guaranteed on the discrete support points corresponding to the ground-truth selector. Its behavior at intermediate points depends on how it is extended to the continuous domain. Could the authors clarify whether the observed misleading gradients are primarily a consequence of this continuous extension? In this sense, would it be more precise to state that correctness on the discrete support does not guarantee useful gradients for recovering the ground-truth selector?

We agree with the reviewer's formulation, and it states our point well: correctness on the discrete support does not guarantee useful gradients. By a correct evaluator we mean only that, with the correct selector, the two modules together give the right label on every input. No particular interpolation between the support points is required. We will state this precisely in Sec. 2.

The misleading gradients do arise between the support points, but they do not rely on a particular extension. Some extension is unavoidable, and the alternation is forced. Among alternating extensions, the piecewise-linear one with sharp vertices is the natural choice: it is symmetric, it has the least curvature between the true vertices, and it is what a trained evaluator converges to (Fig. 2), and what weight decay selects (App. E). Any piecewise-monotonic extension has the same sign of slope on each branch, and therefore gives similar reversed updates. Quantitatively, the heights of trained evaluators change the barrier by about 3% in the median over all tasks (W2), and their shape between the support points changes it by less than 1% (new App. H, Fig. 13).

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response: New Appendix H for Responses

We thank all reviewers for the careful reading and the constructive comments.

To support our responses, we have uploaded a revised PDF with a new Appendix H (in red). It contains new experiments and figures (Figs. 12–15) on the sensitivity of the barrier to the evaluator and on the link between the barrier and training success.

The rest of the paper is not changed yet. App. H and the other changes mentioned in our responses will be integrated into the paper in the coming revision.

AuthorsOpenReview ↗

Revised paper uploaded

We have uploaded the revised paper. Revised text is shown in red. The two main changes are:

  • Abstract and introduction. They are rewritten to make the motivation and the contribution explicit. The introduction now motivates the setting by trainable modules that are optimized through fixed downstream systems, and explains why sparse parity is used as a testbed.
  • Barrier under symmetry breaking (new Sec. 4.2). This new subsection examines the barrier when actual runs depart from the symmetric path used in the analysis. As shown in new Fig. 8, training success rises sharply where the barrier vanishes, so the computed barrier is correlated with actual training.

In addition, the new App. C shows that the barrier changes little when the triangle wave is replaced by trained readouts. App. H, added earlier for our responses, is kept as it is so that the figure numbers cited in the comments remain valid.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.