Topological obstruction to the training of shallow ReLU neural networks

Summary

This works studies how topological properties affect loss landscape of neural networks, showing that the loss can be divided into disconnected regions where reaching one region from the other using GF is impossible. The theory is shown to have consequence for understanding the training of simple networks

Strengths

Studying topological properties of the loss landscape is interesting and should be encouraged, the theory is solid and convincing

Weaknesses

This paper has quite a few weaknesses in its current form, and these prevent me from recommending acceptance at this stage 1. Prior works. (a) it is unclear how different this work is from Safran et al. [35]. This point is never discussed, and this makes it difficult for me to judge the novelty of this work. (b) Incorrect reference. Eq. (11) appears the earliest in https://arxiv.org/abs/1312.6120, not in Du et al. [11]. (c) emergence of topological obstruction due to permutation/rescaling symmetries have been studied in https://arxiv.org/abs/2309.16932, and the authors need to compare the results to clarify what is novel in the present manuscript 2. The main result applies only to two layer bias-less ReLU nets, which I feel to be too weak 3. The meaningful implications (corollary 1) is only relevant when either the input or the output dimension is 1, which makes the theory very unlikely to the relevant to practice 4. The experiment also has very limited scope. If the authors can show that the effect they studied is relevant for training a much larger model on a more realistic dataset, I would be more convinced of the relevance and contribution of the theory

Questions

Does the results still hold when there is a bias term？

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The paper could also benefit by discussing more of its limitations

Summary

This paper considers the landscape topology of one hidden layer networks with non-negative homogeneous activations. The main result of this work is that in some cases, the loss landscape may consist of disconnected components that cannot be traversed by gradient flow dynamics. This leads to an obstruction, in the sense that certain initial conditions will result in closed paths away from the global minimum. They further count the number of effective components (in the sense of being equivalent under the symmetries of the problem) and show that this number grows linearly with the number of hidden neurons that cannot change their sign during the dynamics. The authors provide a full analytical treatment of the problem, supplemented by a simple toy example.

Strengths

I believe the paper has several strengths, in particular: - **Soundness and clarity** - The authors review some known results, and build upon them in an instructive way, that allows the reader to understand precisely what has been done. Additionally, they provide proofs, as well as intuition for all of their results. - **Novelty** - As far as I know, this topological analysis is new, with the closest work being Ref. [1], which is still very different. I believe this work can shed light on the training dynamics of GD in this setting. References: [1] - https://arxiv.org/pdf/2401.10791

Weaknesses

The main weakness of this work is its **scope**. The work studies in great detail a very specific architecture, but it is unclear how interesting their conclusions are for either theorists or practitioners. Additionally, their numerical/toy example is extremely simple, and it is a bit hard to see how their results extend to more complicated settings, even though they discuss some of these aspects in their limitations section. It would be useful to include more complicated examples, even in the single hidden layer case, as well as contrast these results with cases in which the activations are not ReLU-like, i.e., commenting on how these results break down.

Questions

Comments and questions below: 1) L52: “studied by under various…” incoherent sentence. 2) L51: “activation” should be “activations” I assume. 3) In Sec. 3.3, the authors consider an arbitrary dataset and a general empirical loss function. The analysis does not depend on these details and is therefore truly a property of the network and the initialization, and so these results should hold for any task. Is this correct? 4) The experimental setup in Sec. 6 is incomplete - the loss is never specified (MSE, CE?), it would be nice to see (empirically) that the results do not depend on it. 5) Can the authors comment on the relation of their work and Refs. [1,2]? 6) What happens to the topological structure if we consider the discrete GD instead of GF? the results should hold for small learning rate (as shown numerically), but there is a possible catapult regime (Ref. [3]) at large learning rate, will the paths not be restricted to connected parts in this case? could the catapult effect cause a transition between disconnected effective manifolds? [1] https://arxiv.org/pdf/2401.10791 [2] https://arxiv.org/pdf/2402.05626 [3] https://arxiv.org/abs/2003.02218

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors discuss their limitations in a dedicated section.

Summary

In this paper, authors analyze the performance of gradient-descent optimization over a two-layer neural network. Authors reveal the presence of obstructions in the loss landscape and explore their topology. Finally, they identify the cause of those optimization obstructions in the so-called `pathological’ neurons—neurons that can’t change the sign of their output weight.

Strengths

1) An interesting and novel approach. 2) A step up from well studied gradient descent optimization of one hidden-layer networks. 3) Solid theoretical background and strict mathematical proofs of main results.

Weaknesses

1) This paper identifies pathological neurons that disrupt the performance of gradient descent over ReLU activations; however, nothing is said about how such obstructions can be avoided or how their effect can be mitigated. 2) The scope of the research is limited to neural networks with two hidden layers. 3) The possible benefits for further research and practical applications of the achieved results are somewhat vague.

Questions

See Weaknesses section.

Rating

6

Confidence

1

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes, the limitations are addressed. This is a purely theoretic work, dealing with a somewhat simplified example of a two layer fully-connected neural network.

Summary

This paper studies the topological obstruction in the loss landscape of two-layer ReLU neural networks under gradient flow. Using conserved quantities in gradient flow, the authors define invariant sets, to which gradient flow trajectories are constrained. They then show that when the input or output of the network is a scalar, the invariant set may have more than one connected components depending on initialization. This leads to a topological obstruction, as gradient flow cannot reach a global minimum if parameters are initialized in the component that does not contain one. After taking scaling and permutation symmetry into account, the number of effective components scales linearly with the number of pathological neurons, which are neurons that cannot change the sign of their output weight. On a toy example with two hidden neurons, the authors fully characterize the invariant sets and show theoretically and empirically that gradient flows that do not start in the same effective component as the global minimum cannot reach the global minimum.

Strengths

- This paper takes a novel approach of studying the topology of loss landscapes by examining invariant sets. While many work studies the loss landscape by proving topological properties of sub-level sets, this paper pursues an orthogonal direction by analyzing the topological properties of the set of reachable parameters by training trajectories. This approach combines the study of loss landscape and optimization dynamics, which leads to the original discovery of topological obstructions to the training of ReLU networks. - The paper provides concrete examples where gradient flows from certain initializations cannot converge to a global minimum and gives practical suggestions on how to choose initializations to avoid this issue, at least for two-layer ReLU networks. - The results on when invariant sets can be disconnected and the number of effective components provide valuable information on the loss landscape. These results could potentially lead to a new line of work on the trainability of various architectures under common optimization algorithms. - The paper is very well written. Setups and mathematical concepts are explained in an accessible way without losing rigor. The theorems and their implications are explained clearly. The visualizations (Figure 1-3) are informative and provide clear intuitions. The toy example in Section 6 is simple and effectively demonstrates a case where topological obstruction prevents gradient flow from reaching the global minimum.

Weaknesses

The scope of the analysis, which is restricted to two layer ReLU neural network and gradient flow, is rather limited. - While ReLU is a popular activation function, two-layer networks are rare in today’s machine learning models. The results in the paper do not readily extend to deeper networks, where invariant sets no longer factorize easily into product spaces. - Since SGD is known to have an implicit bias characterized by a drift of $c$, training trajectories in practical settings (with non-infinitesimal learning rate) will not stay in the same invariant set. Even if they stay close to an invariant set throughout training, the noise in each step may take the parameters to a different component. If extending the analysis beyond this setup is challenging, additional experiments on different settings could also help illustrate that the topological obstruction is a realistic hindrance in practice. For example, for deeper ReLU networks, it might be possible to investigate empirically whether there exist initializations that lead to similar obstructions as observed in Figure 3c.

Questions

- For ReLU networks with one hidden layer, does every invariant set contain a global minimum? If not, then even if an invariant set is connected, it is not guaranteed that all gradient flows starting from points on this set can reach a global minimum. This is not the type of obstruction considered in the paper, but I am curious about whether there are other considerations when choosing the initialization, besides ensuring the connectedness of the invariant set. - Assume that an invariant set contains a global minimum. Do all gradient flows in this invariant set converge to a global minimum? - For a wider two-layer ReLU network, using common initialization methods (such as Xavier initialization), what is the probability that the invariant set has more than one effective components? What is the probability that the initialization falls in the component that does not contain a global minimum? Is it nonzero? - Do the rest of Betti numbers, other than $\beta_0$, provide useful information about the loss landscape and the training process? **Minor issues / suggestions** - Line 135-136: While allowing a finite sequence of actions is arguably more intuitive, it might suffice to just define observationally equivalence as being related by a composition of one $T$ and one $P$. As a consequence of Lemma 3 in the appendix, for any finite sequence of T and P, there exists a sequence of T and P with length at most 2 that produces the equivalent transformation. - In Equation 11, is the second expression missing a factor of 2? - The sentence in line 483 is not grammatically correct.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors are upfront about the limitations and include a limitation section in the appendix.

Summary

Summary of the paper: * The paper undertakes a theoretical 'reachability' analysis for neural networks trained with gradient flow, identifying 'obstructions' separating certain regions of parameter space from each other. * The setting is one-hidden-layer networks with homogeneous activation functions, including ReLUs. The main paper considers the biasless case but the authors extend their results to the case with biases in the appendices, with only minor modifications to the results. * The authors consider training such networks with gradient flow and identify that regardless of the (output-dependent) loss function that gradient flow conserves a certain norm of the weights confining the training trajectory to a subset of the parameter space they call the 'invariant set' which is a product of hyperquadrics associated with each hidden unit in the network. * Through topological analysis the authors derive the Poincaré polynomial of such invariant sets and in turn their zeroth Betti number, in effect counting the number of connected components in the invariant set. * These components are of interest because if gradient flow is initialised in one component it is impossible for the training trajectory to find its way to another, and training is limited to the best solution available in the initial component. * In this setting the zeroth Betti number (the number of connected components) is only one for networks with multidimensional inputs and outputs, indicating no topological obstructions. * In contrast, for networks with scalar inputs or outputs, it is exponential in the number of hidden units (with a base depending on the network initialisation), indicating many topological obstructions. * (For networks with biases, the space is connected if and only if the network has a multidimensional output). * The authors then revise their count to take rescaling and permutation symmetries into consideration. * The reasoning is that if gradient flow can only explore its initial connected component, this is only a problem when the component is actually missing network functions rather than when it is merely missing some (but not all) implementations of those functions. Perhaps only one reachable implementation of the target function is needed. * The result is that there are fewer 'effectively' connected components, linear rather than exponential in the number of hidden units (with constants again depending on the initialisation). * However, the point is that there are still some topological obstructions to worry about. * The authors provide a clear 'proof of concept' of their work in the form of a numerical experiment simulating gradient flow by learning a small neural network with gradient descent using a small learning rate. The results clearly show that the learning trajectory is confined to the invariant set and obstructed from reaching the global minimum as predicted. I wrote a bit of a long review, so here is also a summary of my review: * The main contribution, demonstrating the existence of topological obstructions to gradient flow, appears novel, interesting, and an important contribution to our understanding of the structure of parameter space. * I also think the paper is exceptionally well written and clear and the analysis is elegant. I think the authors have discussed the limitations of the work well. I am left with only a small number of questions. * My main concern is that the results show topological obstructions only occur under some strong assumptions, and in fact they do not arise in more situations. I find this somewhat at odds with the framing of the contribution. Overall, I think the work is worthy of acceptance because it is elegant, interesting, informative, and thought provoking, but I maintain concerns about whether the framing is accurate.

Strengths

I thank the authors for submitting their elegant and well-presented theoretical analysis exploring an important topic. * Topological analysis of gradient flow is an interesting and apparently novel approach that stands to make a meaningful contribution to the field's theoretical understanding of the 'global' structure of parameter space. * The work clearly exhibits 'topological obstructions' in a restricted setting, which is a thought-provoking phenomenon (though I have some reservations about its relevance in practical settings, see below). * I appreciate the elegant and rigorous application of powerful, established tools from the field of topology. The theoretical results are also supported with a clear, small-scale proof-of-concept numerical experiment. * The presentation of the theory and experiments is very clear and accessible. The figures are carefully designed and informative. The technical details of the framework and results are complete and made the paper quite accessible to me, even though I have limited knowledge of topology (the primer in the appendix was appreciated). * Clear, thorough acknowledgement of related and prior work in the dedicated section and throughout the paper.

Weaknesses

The authors have convincingly demonstrated the existence of topological obstructions under the stated assumptions. My main concern about this work is the relevance of topological obstructions to deep learning practice. 1. I am not so concerned about the restriction to single-hidden-layer networks. The results may not generalise to the multi-layer case, or perhaps they will, it seems worth looking into with future work. However, I am concerned that *even in the single-hidden-layer setting* the main disconnectedness result holds only for networks with scalar output. The authors clearly show that networks with multidimensional outputs do not show obstructions. With this in mind, do the authors believe that the topological obstructions they have identified are relevant to deep learning practice? If so, can they clarify this point? 2. Furthermore, I have concerns about the gap between gradient flow and discrete gradient descent training. The authors explain that discretised gradient methods are not confined to the same invariant sets as gradient flow. It seems possible that this means discrete gradient methods count circumvent topological obstructions, even if they exist in practical settings. 1. Do the authors conjecture that the identified obstructions have implications for gradient descent training? 2. If the authors would support such an 'obstruction hypothesis', I would invite them to consider explicitly stating the hypothesis in their introduction and/or conclusion. 3. The authors could also consider extending their simple numerical experiments to explore whether and to what extent the demonstrated obstruction affects training with larger learning rates or momentum-based training methods. Pending the authors' clarification of these points, the framing of the work is somewhat confusing to me. It appears to me that the authors have shown that topological obstructions to gradient flow are actually quite a restricted phenomenon. An alternative framing for the paper's results would be to say that they show that deep learning is often *not* held back by topological obstructions. Could the authors comment on this alternative framing? I don't think this concern is fatal to the paper. The topological analysis approach and most of the results are still informative and worth sharing even if the topological obstructions themselves end up not arising in more practical settings.

Questions

1. The authors have presented a clear interpretation of the source of the topological obstruction in terms of the relationship between each unit's weights (lines 232 onwards). Do the authors have a similarly enlightening interpretation of the breakdown of the topological obstructions in the case with multidimensional outputs? 2. Another assumption of the work is that the loss function depends only on the network weights via the output of the network. Am I correct in understanding that if the loss function includes a regularisation term that depends on, for example, an $L_p$ norm of the weights, then this assumption would be violated and the analysis would not hold because gradient flow would no longer always be perpendicular to the invariant sets? This seems fine but might be worth acknowledging. 3. Appendix E extends the analysis to networks including biases, but stops after deriving the zeroth Betti number in this setting. Could you please clarify whether the analysis of section 5 is unchanged in this setting? 4. The contribution list does not mention the 'proof of concept' numerical experiments. It seems to me that these experiments are a reasonably important part of the paper's contribution and its evaluation to warrant mentioning in the introduction (as well as the abstract). 5. Line 118: The authors describe the transformations as sending parameters to different but observationally equivalent parameters. It is typically true that the parameter produced is different but for some parameters or for some transformations the transformations don't change the parameter.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

The paper accurately describes the contribution including its limitations. These limitations are adequately and carefully disclosed in multiple places in the main text and discussed in detail in appendix F. 1. One main limitation is the simplicity of the architecture, with only one hidden layer. The authors discuss barriers to extending the work to the multi-layer case, namely the interaction between layers, which is left to future work. 2. A second main limitation is the fundamental assumption of gradient flow. The authors explain that the conservation laws that are crucial to their analysis do not hold for discretised gradient descent. 3. A third main limitation is that the topological obstructions only exist in the case of networks with a scalar output. This is clearly acknowledged in the abstract and throughout the paper, but I think the authors could have more thoroughly discussed the implications of this restriction, namely that in many cases we should not expect topological constructions at all. If the work is to be accepted I would encourage the authors to include the valuable discussion in appendix F in the main text, and to extend this discussion along the lines of (3).

Thanks for the detailed reply

The reply addresses my main concerns. Although I still think the main problem is with its unclear relevance. I will raise the contribution rating to fair and the score to 6

Thanks for the clarification

I thank the authors for their clarifying rebuttals. I especially thank the authors for their intuitive explanation of the resolution of the obstruction in the multi-output case. I invite them to include this and their other clarifications in future revisions of the paper. The three new experiments are also a very welcome addition to the submission. At the moment I am maintaining my recommendation. I retain some of my concerns about the framing and relevance of the results. I am about to post a top-level comment on this topic since concerns about relevance were also raised by a few other reviewers.

Relevance of topological obstructions to deep learning practice [1/2]

It appears that the current consensus among reviewers is that this paper should be (weakly) accepted, with the primary remaining concern being about the relevance of the phenomenon of topological obstructions in practice (noting this is my impression and I don't speak for the other reviewers). On the question of relevance I have a couple of follow-up questions after reading the reviews and rebuttals and studying the new gradient descent experiments. I organise my questions by two key points of departure between the theoretical setting where topological obstructions found by the authors and those settings common in deep learning practice: on the learning algorithm (gradient flow) and on the architecture (scalar-output single-hidden-layer ReLU networks). I conclude with some suggestions on the paper's framing. ### Learning algorithms **1. Characterising when discrete GD bridges obstructions:** The additional experiments show that the phenomenon of discrete gradient descent training bridging the obstruction "can occur for some values of the learning rate, which are not too low nor too high" [from a rebuttal]. I would like to question the basis of this "not to low nor too high" characterisation. In the attachment I see that the `lr=0.533` run clearly bridges the obstruction in terms of loss and parameter-space trajectory. The `lr=0.6` run appears not to have bridged the obstruction (though I can't actually see where it went in the parameter space?), and this must be the basis for "not too low nor too high", but this is the only higher learning rate tested. I don't know that this is sufficient basis for characterising the bridging phenomena in this way. **2. On regularisation:** In my review I noted that learning with weight-based regularisation would violate the assumptions of the analysis, and the authors agreed with this observation. This difference would appear to me to be more severe than the difference between gradient flow and (stochastic) gradient descent, since it is not just about discretisation---regularised parameter updates may not even be *locally* orthogonal to the invariant set. This limitations are implicit in the assumptions listed throughout the analysis, but I would invite the authors to explicitly acknowledge this limitation at the level of the discussion of appendix F (alongside their existing acknowledgement of the difference with momentum-based methods). ### Architectures **3. On biases:** I was not completely convinced by the authors' reply to my question about the case with biases. It's true that networks with biases are the same as networks with additional input units, but those additional input units have to have their inputs restricted to a constant function. Thus analysis of network functions including, e.g., invariance, has to proceed in a subspace of the expanded architecture's function space. In general such a restriction can create new symmetries. I think this probably doesn't undermine the analysis, since the analysis is mainly based on the existence of certain symmetries which will not be removed by adding additional restricted dimensions. I would need to think about it more carefully to be sure. I would like to ask, have the authors taken this complexity into account in the claims in the paper that the results generalise to networks with biases? **4. On single-hidden-layer networks as building blocks:** A couple of times in the rebuttals the authors said that while single-hidden-layer networks are not commonly used in practice as a stand-alone architecture, they are commonly used as building blocks of other architectures. The authors cite CNNs as examples and I might add their use in transformer blocks and that an MLP can be viewed as a composition of single-hidden-layer networks in some sense. However, I wanted to point out that in such cases typically the building block layers have multiple outputs (with the exception of a final layer in an MLP or CNN used for binary classification). The authors have shown that such layers *would not* unilaterally suffer topological obstructions. Therefore, while the authors' analysis could be informative in studying architectures composed of hidden layers, their key finding won't necessarily generalise (there would have to be some other component of the architecture that restores the topological obstruction to this layer or introduces its own obstruction). In the case of networks with a final layer with a scalar output, the final layer may have a topological obstruction, as long as the interaction between this and prior layers does not allow it to be circumvented. I understand that the definitive answer would have to be left to future work, but I wonder, would the authors agree with this preliminary assessment of the prospects of that future work? [Part 1 of 2]

Thank you for the clarifications

Thank you for answering my questions and providing clarifications; I have also carefully read the reviews from other reviewers (and rebuttals to them). I found this paper quite interesting and I lean towards thinking it worthy of acceptance. Unfortunately, my prior experience in the optimization theory is rather limited, and I will hold on my current score for this paper (6).

Reply to the Authors

I thank the authors for their detailed reply, as well as their global reply and further experiments. I believe the paper should be accepted, but due to its limited scope, and after reading other reviews, including that of Reviewer JxYP, which addressed regularization and the "building block" argument etc., I believe that a higher score is not warranted. I do recommend that the authors delve deeper into the finite learning rate in future works, and especially the lr=0.533 example that was found, to understand how the obstruction is circumvented as a theoretically motivated reason for using large learning rates.