- 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 for each input component 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.
- 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 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?
- 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
-
After (2), why "so are z=1/2"? z depends on x_i's no matter what the initialization of the gates.
-
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?
-
what is permutation-symmetric gates (the paragraph before (5))? I could not find its definition.
-
which index i are we picking for the definition of \lambda=m_i/... in (8)?
-
What would be the impact of removing the frozen constraint on the readout affect the conclusions of the article?
4 comments
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 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 on the 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 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 of Eq. 3 for each subset . 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 , 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 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.
Response to Reviewer WTAX (Q1–Q5)
Response to the 'Questions for Authors
Q1.
After (2), why "so are "? z depends on 's no matter what the initialization of the gates.
The sentence is meant for the distribution of , not for individual inputs. With nearly equal gates, is the fraction of active bits, so its distribution is centered at . For an individual input, depends on , 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 , and 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 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 .
The reviewer's projection can also be computed directly. The loss does not change when all gates grow together, so the update of Eq. 3 satisfies for the current mask . With the correct mask , this gives : the current mask drops out. For the masks described above, and 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 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, , and all non-task gates share one value, . 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 are we picking for the definition of in (8)?
No index is picked. Here is the common value of the non-task gates and that of the task gates, as in the previous answer, so is the non-task gate divided by the mean gate. It equals at the uniform mask and at the correct mask. Sec. 4 now recalls this where 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 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.
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), 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/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 n and k (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.