Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 
The authors study the loss landscape of multilayer convolutional neural
networks, and in particular consider the construction of spurious minimizers of
networks trained on regression/classification tasks. They consider networks
with fully connected, convolutional, max-pooling, and average pooling layers,
as well as ReLU nonlinearities. Their main results (1) construct spurious
minimizers in a network assuming that a subnetwork construction is satisfied
and a certain nondegeneracy assumption holds at the local minimizer obtained
from this subnetwork construction; (2) show in a specific setting (slightly
nonstandard architecture) that a subnetwork can explicitly be constructed to
give a local minimizer. 

strength_and_weaknesses: ## Strengths

The authors argue that their approach to constructing local minima is modular,
in that the task is reduced to studying a local minimum of a subnetwork (which
can then be embedded into larger networks). This may be useful for obtaining
general conclusions. They mention on page 5 that this is new in the context of
CNNs (standard for feedforward nets).

The analysis seems highly technical and intricate, involving detailed
index-level manipulations of the filters in the network. (This also makes it
challenging to verify). The result considers fairly general CNN architectures
and various loss functions, including regression and classification losses. 

## Weaknesses

The claims of novelty in the introduction (end of first paragraph, end of third
paragraph) are not correct: the related work section even discusses a work of
Du et al. on one-layer CNNs that shows spurious minima (and see similar works
not cited, such as https://arxiv.org/abs/1909.03172). This is not hard to fix:
you can claim the first result on spurious minimizers in deep CNNs / CNNs with
several channels, etc. I would also recommend an additional literature search
for possible related references in this context, since the one I mention here
was missed.

Claim about argmax at bottom of page 3 and top of page 4: I do not think this
is correct in general -- consider the case where there are two distinct indices
$i$ which achieve the argmax corresponding to different filters, and suppose
the coordinates $o_p^{l-1}(i)$ are open mappings (is there any reason for them
not to be?). Then every neighborhood of the parameters $W, b$ contains points
at which the argmax is taken uniquely on a distinct coordinate involved in the
tie; it implies that there is no locally-valid way to define a *constant* matrix
that selects the right element of the max-pooling operation. The assumption that the 
coordinate maps are open is only sufficient; it should be possible to construct
counterexamples under more general conditions specific to the definition of the
feature maps.

The result relies on a technical assumption (Assumption 1) that seems to
significantly limit the scope of the theory (or even make it vacuous).
Assumption 1 is a nondegeneracy assumption on the network features at a local
minimizer (this is used to prove that the minimizer is spurious). As a result
of the dependence on this assumption, it does not seem that the theory makes
any predictions about the existence or non-existence of spurious minimizers in
any actual network architectures. Based on the way Section 4 and Theorem 2-3
are written, I understand that even in the authors' construction of a concrete
local minimum, it is still necessary to make assumption 1 in order to conclude
that the local minimum is spurious. In the rebuttal, I would appreciate if the
authors could enlighten me on whether assumptions like this are standard in
other works that study spurious minimizers in neural networks (say, in the
well-studied feedforward setting). From my perspective, I would find it hard to
understand why the natural extension from the results mentioned in the related
work section by Du et al. and the one I mentioned above for concrete spurious
minimizers non-overlapping-receptive-field and one-layer Convnets would not be
something for single-layer and overlapping receptive field networks, or
multi-layer and non-overlapping receptive field networks, rather than the
extremely general setting the authors consider here (given that there are no
concrete conclusions in this setting in the presented work). 

## Minor / Questions

Bottom of page 1 and elsewhere: "perturbated" -> "perturbed" ("perturbate" does
not sound correct)

clarity,_quality,_novelty_and_reproducibility: The paper is very technical and written in a nonintuitive way -- for example,
when the authors describe their results and techniques in the introduction of
the paper, it reads like a direct translation of some of the proof techniques
into natural language rather than as an elucidation of the ideas behind the
proof (why such a result is true, how one might arrive at it, etc.). This makes
the effort required to penetrate the paper for a nonspecialist unduly high.

In general (following comments in the previous section), the preliminaries
section 2 is written in an unclear and disorganized style that is overly
general and unnecessarily confusing.  For example, the definition of the max
pooling operation (3) is not clearly made with respect to its interaction with
distinct filters $T_{\ell}$ in a layer; the use of a matrix $W^{\ell}$ for all
operations does not accurately show the distinct structures of each operation
(average pool; convolution; fully connected) as functions of the actual weight
parameters of the network and architecture parameters, and hence makes it seem
unnecessary to define such intricate notation here (just put it in an appendix
instead, if it is not essential to understanding the main body of the paper?);
the discussion of feature map padding is done vaguely in an unhelpful way (one
wants to know here **what restrictions does this place on the various
parameters of the network**? In (2), the input feature map dimension is 5 and
the output dimension is 6. If I pad the input by 1, now the input dimension is
6 and the output dimension is 8. It does not seem to be possible to pad the
input feature map to make the input and output sizes equal!). I would recommend
the authors polish the writing and only introduce notation that will be
necessary to discuss the main results that are presented in the subsequent
sections of the main paper.


The technical presentation of the argument reads as though it is poorly
organized, as well. Lemma 1 is a technical result that seems rather abstruse,
and it also applies to a very limited setting (only Conv + ReLU layers); the
lemma has unnatural technical assumptions on nondegeneracy, and after
presenting it the authors then state that "the conclusion in Lemma 1 still
holds" for more general settings without any proof or connection to a result in
the appendices. Why not present this result informally, with the necessary
links to the fully general versions in the appendices made? The second
paragraph of section 3.1 says "for ease of presentation", but this seems to be
off to me -- the result presented is still very technical, and the
simplifications seem to rather have the effect of making it unclear what
networks the authors' result actually applies to, rather than the stated
intention. The same could be suggested for the following material that leads to
Theorem 1, although here the technicality may be essential.


summary_of_the_review: 
The strength of the assumptions made in the theory seems to significantly limit
its scope. As a result, although the work is technically impressive, it does
not seem to shed much novel light on when and why spurious minimizers exist in
convolutional neural networks trained on various practical tasks. The notation
and writing could do with additional polishing.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically investigates spurious local minima (i.e., local minima that are not globally optimal) that arise in the empirical risk of deep convolutional neural networks.

- By embedding a local minimum of a subnetwork to a larger network, the paper constructs a local minimum $\theta$ of the larger network (Lemma 1). Then, it is shown that a different point $\theta'$ can be perturbed in a way that the empirical risk at $\theta'$ is strictly smaller than $\theta$ (Lemmas 2, 3, and 4). This proves that the local minimum $\theta$ is spurious (Theorem 1).

- Theorem 1 relies on the existence of a local minimum of a subnetwork. Theorem 2 provides a construction of a local minimum that is "nontrivial"---in the sense that different ReLU activation patterns exist for different data points, unlike existing results.

strength_and_weaknesses: - Existence/absence of bad local minima is an important topic in the literature, and it is true that the investigation has mostly focused on fully-connected networks. This paper is one of the first attempts to characterize spurious local minima that arise from convolutional networks, and the authors seem to have overcome several technical barriers that arise in CNNs.

- However, while I got the main idea, reading the paper left me with some questions, mostly related to Theorem 1 and its proof. If all the issues are clarified I would be happy to raise my score.

- I'm confused about the relationship between the number of neurons $n_l = T_l P_{l-1}$ and the number of patches $P_l$. As one can see in Eq (1) and (2), the output $o^l \in \mathbb R^{n_l}$ is plugged in as the input for the next layer. Considering that we apply zero-padding and stride is equal to 1, it seems to me that the number of patches at layer $l$ would be the same as $P_l = n_l$. However, it seems that the paper is assuming $P_l = P_{l-1}$ by zero-padding (e.g., see $P_{L-2} = P_{L-3} = P_{L-4}$ right above Lemma 1). To me this looks like a contradiction unless we have $T_l = 1$. Can you clarify?

- In Lemma 1, we make portions of $W^{L-1}$ and $W^{L-2}$ equal to "identity" matrices by filling in the diagonal entries with 1. However, I wonder whether this is always possible? For example, if we look at Eq (2), there are certain entries that are *forced to be zero* by the structure of the weight matrix that arises from convolution. Also, it is mentioned that the conclusion of Lemma 1 still holds if the top layers are pooling layers. How? Take average pooling for example. One does not have the freedom to choose $W^{L-1}$ and $W^{L-2}$ arbitrarily; the matrices are just fixed, based on the number of patches and filter length.

- Lemma 1 requires that $\hat W^L \hat I^{L-1,i} \cdots \hat W^1$ is full-rank for all $i$. While this may look reasonable for networks of general size, for certain cases I think this condition can become a big restriction. For example, consider the case where all $\hat W^l$ are square matrices. Then necessarily all the diagonal matrices $\hat I^{l,i}$ must set their diagonal entry to one in order to satisfy the full-rank condition. This means that all ReLUs must be turned on for all datasets, which boils down to a linear model.

- For the local minimum $\theta$ constructed by Lemma 1, the rest of the proof assumes that the local minimum has $R (\theta) > 0$. How can you safely assume that? The conclusion that the local minimum $\theta$ is spurious becomes vacuous if this assumption $R (\theta) > 0$ actually does not hold for any local minimum. In other words, the theorem does not *disprove* the possibility that all the local minima are globally optimal because it relies on this assumption. Would there be a way to show the existence of $\theta$ that always satisfies $R (\theta) > 0$? Maybe by using the construction idea from Theorem 2?

- Why should Eq (10) necessarily hold? If $\eta$ is chosen based on $h$ with the biggest split threshold, why should the sum in Eq (10) suddenly become zero for all $j \neq h$?

- In Theorem 2, it is assumed that for any target $y_{i^*}$ there exists $\tilde y_{i^*}$ such that the loss $l(\tilde y_{i^*}, y_{i^*}) = 0$. What happens for losses for which such $\tilde y_{i^*}$ does not exist, e.g., cross-entropy loss? Also, in Theorem 2, is $R (\theta) > 0$ always satisfied?

clarity,_quality,_novelty_and_reproducibility: - The paper is heavy in notation and in many cases it uses multiple equivalent symbols to denote the same thing. For example, the output of the network for input $x_i$ is denoted by four symbols: $o_i, o(x_i), o^L(x_i), o^{L,i}$. I'm not sure if this improves readability; rather, it is likely to hurt readability.

- It is good to be explicit about the construction, but sometimes too many details can hurt. At first glance, Lemma 3 looked just overwhelming to me. Perhaps it would be better to avoid spelling out the explicit details in the statement?

- Other than the aforementioned issues, the paper is not too difficult to follow.

- As mentioned above, the paper seems to have developed novel techniques to overcome the difficulties that arise in the analysis of CNNs. Unfortunately, I didn't have a chance to check the details of the proofs though.
summary_of_the_review: This paper develops some novel techniques to show the existence of bad local minima in the empirical risk of CNNs. If fully correct, this looks like a good contribution to the literature. However, some issues (mostly with proof and notation) are raised and I set the recommendation to weak reject for now. If the authors clarify these issues through the rebuttal period, I would be happy to raise my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper constructs bad local minima for convolutional neural networks (CNN) with ReLU activation. Specifically, the paper establishes the following results:

1) If a neural network (termed "subnetwork") has a local minimum, then a network concatenating the subnetwork and 2 convolutional layers has a local minimum.
2) There exists another point with a smaller training loss than the above local minimum. Thus, the above local minimum is not a global minimum.
3) Construct a concrete example of the subnetwork, so as to validate the existence of a bad local minimum.

This is the first paper that addresses the existence of bad local minima for CNN with ReLU activation.
strength_and_weaknesses: Studying the loss landscape, especially the existence of bad local minima is important for understanding neural network training. Most existing results are limited to fully-connected networks, hence an attempt to expand our understanding to CNN is valuable.

The proof of this paper consists of two major steps: 1) the construction of a local minimum, and 2) proof of the constructed local minimum to be spurious. However, in the first step (Lemma 1), the authors seem to intrinsically consider a fully-connected network. Below are detailed comments.

- The authors study the matrix-vector product formulation (2) for CNN. Due to weight sharing, some entries in matrix W and bias b represent the same network weights. That is, during the optimization, some entries in W and b should be kept identical. 

- However, in the construction of Lemma 1, entries of $W$ and $b$ seem to be freely designed. If this is the case, it reduces to the fully-connected networks, bypassing the most challenging issue of CNN. Otherwise, the authors should justify how the shared weight constraints are satisfied. For example, the form of W in (2) does not allow assigning nonzero values to all diagonal entries. Then, how is the construction of $W^{L-1}$ in Lemma 1 possible? 

Lemma 1 (construction of local minimum) serves as a foundation of this paper. If the problem of Lemma 1 can not be addressed properly, the paper has not really proven the existence of spurious local minima for CNN.

Other comments:

- Lemma 1 requires the matrix product $W^L I^{L-1,i} W^{L-1}\cdots W^1$ to be full-rank. This may not be possible since some of the rows in $W^{L-2}$ (and some of the columns in $W^{L}$) are set to 0. Are there any dimension constraints (on $n_{L-1}, n_{L-2}, n_{L-3}$) missing in Lemma 1?

- In the last sentence of page 3, $i^*_p$ may not be able to keep constant in its neighborhood if two or more features are equal.

- Assumption 1 needs further justification. If neural collapse happens, the inputs to the final layer may be identical for different samples in the same class.

clarity,_quality,_novelty_and_reproducibility: Please see above.
summary_of_the_review: Extend an existing technique to construct a spurious local minimum for CNN, which is the first attempt in this field. However, the construction of the local minimum is not sufficiently justified to be a CNN point.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper theoretically proved the existence of spurious local minima in deep convolutional neural networks by construction. Specifically, for a convolutional neural network whose last three layers before the final fully-connected layer are all convolutional layers, the authors constructed a spurious local minimum for square loss or cross-entropy loss under some non-degeneracy assumptions for the input data and model weights. The construction and proof in this paper mainly follow the framework in (He et al., 2020) which deals with fully-connected layers, and the authors solved two main technical challenges (limited receptive field, and parameter sharing) to extend their proof to the convolutional case. Experiments of a 7-conv-layer CNN on CIFAR-10 are also provided to validate the theoretical results.
strength_and_weaknesses: -Strengths:

1. This paper showed the existence of spurious local minima in deep convolutional neural networks, and this existence is mainly due to the use of convolutional layers. This indicates that convolutional layers can introduce spurious local minima themselves when equipped in a fully-connected neural network.

2. The network structure used for the theoretical proof is realistic and the ReLU activation pattern of the spurious local minima is non-trivial. The model structure can include fully-connected layers, convolutional layers, and max/average-pooling layers, which match the main ingredients of the convolutional neural networks used in practice.

3. This paper introduces new techniques to extend the framework in (He et al., 2020) to convolutional neural networks. Specifically, Lemma 2/Lemma 5 extends the output split to the convolutional case by solving a combinatorial problem, and Lemma 3/Lemma 4 uses a different way (3 consecutive convolutional layers) to perform local perturbation.

-Weaknesses:

1. The new proof techniques used in this paper seem to be specific about the setting in this paper and could not be easily generalized to solve other problems. The framework for constructing local minima mainly follows that of (He et al., 2020), and the additional technical lemmas seem to only work for the specific setting of convolutional layers. This might limit the technical significance of this paper.

2. It appears somewhat unclear what is the main message from the main theorems in this paper. Since the construction of spurious local minima of convolutional layers seems harder than fully-connected ones, does that mean convolutional layers are less likely to introduce spurious local minima? It would be better if the authors could include more implications and discussions of their theoretical results in this paper.

3. The notation in this paper is heavy and somewhat hard to follow, and it might be better if the authors could use more intuitive explanations/figures and fewer formulas to improve the understanding of the readers. Moreover, the organization of the formulas and lemmas can be further improved. For example, The margin around equations (9) and (10) seems too large. Section 3.2 could also be re-arranged to a place closer to Lemma 2 to help with the proof sketch.
clarity,_quality,_novelty_and_reproducibility: -Clarity: This paper is generally well-structured. However, the proof sketch might be a bit long with too many notations and minor structural problems, so it might need some improvements such as the ones suggested in the "Weaknesses" section above.

-Quality and Reproducibility: The theoretical results in this paper appear to be correct, and the experimental details are provided in the appendix, making it possible to reproduce the experimental results.

-Novelty: To the best of my knowledge, the techniques introduced in this paper to extend the previous framework to convolutional layers are novel.
summary_of_the_review: I tend to lean towards rejecting this paper. Although this paper introduces new techniques to construct spurious local minima for convolutional neural networks, these techniques might not be easily generalized to other settings, and the main message of the results might be somewhat unclear. Besides, the clarity of this paper also needs improvement.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the existence of spurious local minimum in deep CNN. It is shown that a type of CNNs with two consecutive convolutional layers before the output layer have spurious local minima. Reviewers raised two major issues regarding this paper. First, the condition that a subnetwork has a specific type of local minimum may be too strong, or even vacuous. Second, the network structure considered in this paper is substantially different from practical CNNs.
For the first issue, two reviewers mentioned that Assumption 1 and the degeneracy assumption in Lemma 6 (Lemma 1 in the original version) need more justifications. The rebuttal argued that Assumption 1 can be satisfied by using the techniques in the literature and showed that it was possible for practical image data set. The rebuttal also replaced the non-degeneracy condition in Lemma 6 by a weaker version. However, it is still not clear whether this degeneracy condition can be met by the local minimum of the subnetwork. Based my own reading, the authors' claim highly relies on the fact that the subnetwork has a local minimum. It is also implied that the subnetwork can be made rather general as long as it admits local minima satisfying several pre-set conditions. As the reviewers posted questions on the validity of these conditions, the authors should rigorously show under what assumptions on the subnetwork the local minima can meet all these conditions.
For the second issue, one reviewer commented that the framework for constructing local minima mainly follows that of (He et al., 2020), and the additional technical lemmas seem to only work for the specific setting of convolutional layers (with two convolutional layers before the output layer). The revised version claimed that the results could be directly extended to general CNN structures with two consecutive convolutional layers located anywhere (not necessarily the last two layers). After reading revised version, I am not fully convinced by the arguments. If the two convolutional layers are middle layers, the proof of Lemma 6 no longer applies. The perturbation of the two middle layers (under the weight construction of Lemma 6) may yield new activation patterns that the remaining subnetwork cannot achieve. 
In summary, both the network settings and the technical assumptions significantly limit the scope of the theory. The rebuttal did not fully address these issues. I think the paper is working on an interesting problem, but due to these reasons, I can only recommend rejection for this version. Hope the authors can address the issues in the future. 

justification_for_why_not_higher_score: Both the network settings and the technical assumptions significantly limit the scope of the theory. The rebuttal did not fully address these issues.
Decision: Reject