Provable Benefit of Cutout and CutMix for Feature Learning

We would like to express our appreciation to the reviewer for your valuable and constructive comments. In the following, we address the points raised by the reviewer.

W1 & Q1. The use of smooth activation and generalization to non-smooth activation

We note that our activation function differs from those typically used in practice. However, smooth activation functions are widely employed in theoretical studies to analyze the generalization performance of two-layer neural networks. Numerous works have explored theory of deep learning under similar settings as discussed in lines 59–71. Therefore, we believe that studying two-layer networks with smooth activations is a valuable approach for bridging the gap between practice and theory.

Our theoretical analysis can be generalized to non-smooth activations, such as ReLU or Leaky ReLU, in the cases of ERM and Cutout. In fact, our proof did not rely on the smoothness of activations in these cases. However, the smoothness of activation plays a crucial role in the analysis of CutMix. The main difference between the analysis of ERM & Cutout and CutMix lies in our approach: for ERM and Cutout, we directly investigate learning dynamics, whereas for CutMix, we characterize the global minimum and demonstrate that CutMix training can achieve a near-stationary point. To show that the CutMix loss achieves a near-stationary point, we use the descent lemma (Lemma 3.4 in [7]), which is only applicable to smooth objective functions. This is why smoothness is necessary for the CutMix analysis.

Q4. Why does the result for Cutmix only guarantee the existence of an iteration that satisfies the properties?

The use of the descent lemma makes a distinction between the conditions on the iterations for ERM & Cutout and CutMix. The convergence of a smooth function $f(x)$ with optimizing variables $x$ is usually guaranteed by showing $\frac{1}{T} \sum_{t=0}^{T-1} \lVert \nabla f(x^{(t)}) \rVert^2 \leq \frac{C}{T},$ for some constant $C$. Therefore, $\min_{t =0,1, \dots, T-1}\lVert\nabla f(x^{(t)})\rVert^2 \leq \frac{C}{T}$ and it guarantees only the existence of an iteration that achieves a near-stationary point. We would like to emphasize that, even though our theory only guarantees this existence, our numerical validation (Section 5, Figure 1) shows consistent convergence behavior.

Q2. Why is the near convergence result only presented for the Cutmix setting but not for the Cutout setting?

The difference between ERM & Cutout and CutMix also results in different convergence criteria. We initially adopted training accuracy as the convergence criterion, following [1]. However, as discussed in lines 245–247, evaluating the training accuracy of augmented data is challenging because it uses augmented data with mixed labels. Therefore, we use the loss gradient as the convergence criterion, which can be guaranteed by the descent lemma. We note that we can also prove that ERM and Cutout achieve near convergence using the descent lemma. However, we adopted perfect training accuracy as the convergence criterion because it provides a more intuitive measure of how well the model fits all training data points. Moreover, due to the monotonic nature of ERM and Cutout training, we can show that the guarantees in our theorems hold for any sufficiently large polynomial time.

Q3. Can you provide stronger results about the margin besides its positiveness? What is the order/magnitude of the margin?

In our theoretical analysis, we proved that the model achieves an $\Omega(1)$ margin for test data with learned features. If you are interested, you can check line 802 for ERM, line 996 for Cutout, and line 1155 for CutMix.

Thanks for your time and consideration.

Best regards,

Authors

We would like to express our appreciation to the reviewer for your valuable and constructive comments. In the following, we address the points raised by the reviewer.

W1. Confusion on the notions of features

We have noticed that the notions of common features, rare features, and extremely rare features were not clearly explained in Definition 2.1. These features have significantly different frequencies, where common features appear much more frequently than rare features, and rare features appear more frequently than extremely rare features. While we describe this in the Assumptions (Section 2.4), we acknowledge that additional discussion near Definition 2.1 would be helpful to readers. We plan to include a more detailed explanation of these feature notions in Definition 2.1 in our next revision.

In global response, we provide clarification on the notions of features and more detailed motivation of our data model. We hope this resolves any confusion or misunderstanding. We will address the question raised due to this confusion.

Q1. Why learning extremely rare features improves the performance?

As we discussed in the global response, extremely rare features in our setting are still frequent enough to appear in a non-negligible fraction of the training set. These features also have a presence in the test distribution and provide valuable information for correct classification. Hence, learning these features contributes to improved performance.

W2. The technical contributions against Zou et. al. 2023 are not clearly stated.

We have discussed comparison to Zou et.al. 2023 in lines 123-130 and lines 313-318. While we believe this coverage is sufficient, we provide a more detailed comparison here.

• Zou et.al. 2023 only consider two types of features (common features, rare features) while we consider three types of features(common features, rare features, extremely rare features). This is because Zou et.al.2023 investigate two training methods (vanilla, Mixup) while we study three training methods (ERM, Cutout, CutMix).
• Zou et.al. 2023 consider quadratic activation, whereas we focus on smoothed leaky ReLU activation. While our analysis of ERM shares the same spirit as the analysis of vanilla training in Zou et.al. 2023, detailed proofs differ due to variants in the network architecture.
• The main difference between the Mixup analysis in Zou et.al. 2023 and our CutMix analysis lies in the approach: Zou et.al. 2023 prove the benefit of Mixup by directly investigating its learning dynamics, while we show the benefit of CutMix by characterizing the global minimum of CutMix loss. Zou et.al. 2023 prove that Mixup can learn rare features in early phase since it is “boosted” by the learning of common features. In contrast, our analysis shows that global minimizers learn all kinds of features indicating that the benefit of CutMix arises as training approaches convergence. This distinction highlights the differences in the underlying mechanisms: Mixup has benefit in the early stage of training, while the benefits of CutMix arise from the later stages of training.

Limitations. Could not find the discussion of limitations in the Section 2

Our work has limitations related to the neural network architecture, specifically single-neuron leaky ReLU CNNs. We discussed this in lines 137-151, but we will add a Limitation section in the next revision to explicitly address these technical limitations.

Thanks for your time and consideration.

Best regards,

Authors

We would like to express our appreciation to the reviewer for your valuable and constructive comments. In the following, we address the points raised by the reviewer.

W1. It only analyzes Cutout and CutMix

As the reviewer would also agree, a complete theory is not built in a single day. We chose Cutout and CutMix as a starting point for understanding patch-level augmentation techniques, and even this first step required a considerable amount of efforts. Also, We would like to emphasize that there has been limited theory works even on CutMix, as we discussed in Section 1.2.

W2&3, Q1. More insights beyond theoretical analysis

We agree that exploring practical implications beyond the theoretical analysis of existing methods like Cutout and CutMix is valuable. We also believe that understanding the underlying mechanisms of these methods can lead to the development of even more effective techniques. With this in mind, we would like to discuss some potential directions for future applications.

One practical insight we can offer is related to the choice of cutting size $C$ in cutout. Our main intuition behind Cutout is that it outperforms by removing dominant noise patch, or “shortcuts,” which do not generalize to unseen data. Real-world image data contains features and noise across several patches. In practical scenarios, a larger cutting size can be effective in eliminating noise but may also remove important features that the model needs to learn. Thus, there is a trade-off in choosing the optimal cutting size. From this intuition, we believe that for images with a larger portion of background(noise), a larger cutting size is likely to be more effective.

In our theoretical analysis, we show that Cutout and CutMix can learn rare features even though still memorizing some noises. We believe that improving underlying mechanism we have demonstrated can lead to even more effective techniques. Below, we list a couple of potential directions that can not only enable effective feature learning, as Cutout and CutMix do, but also improve these methods by preventing the memorization of noise.

• One limitation of Cutout is that it does not always effectively remove dominant noise. As a result, dominant noise can still persist in the augmented data, leading to potential noise memorization. Developing strategies that can more precisely detect and remove these noise components from the image input could enhance the effectiveness of these methods.
• The main underlying mechanism of CutMix, as we have outlined in Section 4.2, is that it learns information almost uniformly from all patches in the training data, which allows it to capture even rarer features. However, this approach also involves the memorization of noise, which can potentially degrade performance in real-world scenarios. We believe that a more sophisticated cut and pasting strategy—one that considers the positional information of patches rather than using a uniform approach—could improve the model’s ability to learn more from patches containing label-relevant features and reduce the impact of label-irrelevant noise. Already some recent patch-level augmentation method, such as PuzzleMix[5] and Co-mixup[6], use these types of strategy.

W4. Suggestion regarding paper organization

We appreciate for your suggestion regarding the paper’s organization. We agree that moving some of the experimental results from the appendix to the main text could improve our draft. However, we also believe that fully presenting the assumptions in the main text is important for the completeness of our theoretical results. We will carefully consider how to balance these aspects in the next revision, keeping the page limits in mind.

Q2. The paper specifies that the NN architecture used is a 2-layer CNN, but shouldn’t it be considered a 1-layer CNN?

Whether our network is considered a 2-layer CNN or a 1-layer CNN depends on the perspective. Following the existing results in the literature, we regard it as a 2-layer CNN, where the weights in the second layer are fixed at 1 and -1, making only the first layer trainable. Many other works including [1,2,3] also consider neural networks similar to ours as 2-layer CNNs.

Q3. Is it not possible to perform a more general analysis with $C$ channels, as done by Shen et al.?

We believe that a more general analysis with multiple neurons as done by Shen et al. 2022 is also possible, and we numerically validate this scenario in Appendix A.2, Figure 3.

As we discussed in line 144-151, using ReLU activation requires multiple neurons since neurons can be negatively initialized and remain unchanged throughout the training. In contrast, leaky ReLU activation always has positive slope, ensuring that a single neuron is often sufficient. Therefore, for mathematical simplicity, we focus on the case where the network has a single neuron for each output, and extension to multi-neuron case may require some additional techniques.

Limitation. There is no specified section for limitations in this paper

Our work has limitations related to the neural network architecture, specifically single-neuron leaky ReLU CNNs. We discussed this in lines 137-151, but we will add a Limitation section in the next revision to explicitly address these technical limitations.

We hope that our response clarifies your concerns. We would appreciate it if you could consider reassessing our submission.

Best regards,

Authors

We express our gratitude for your valuable comments. In the following, we address the points raised by the reviewer.

W1, Q1. The definitions of features

Please refer to our global response. We describe these features in Section 2.4, but we acknowledge that discussion near Definition 2.1 would be helpful to readers. We plan to include a more detailed explanation of these notions in Definition 2.1 in our next revision.

W2, Q2, L1. 2-layered CNN

Whether our network is 2-layer or 1-layer may depend on the perspective. Following existing works [1,2,3] in the literature, we regard it as a 2-layer CNN, where the weights in the second layer are fixed at 1 and -1, making only the first layer trainable. In addition, we agree that extension to a deeper neural network is not straightforward. However, we believe that our work sheds light on the benefits of patch-level augmentation, making it a valuable contribution. We will leave the extension to deeper networks as future work.

Q3. Numerical simulations

Our choice of frequencies is intended to highlight the distinctions between the three methods. Our findings suggest that applying Cutout and CutMix lowers the “threshold” for the frequency of a feature’s occurrence required for learning it. When we reduce the frequency of a feature from 1 to 0, initially all three methods can learn the feature. As the frequency decreases, ERM may fail to learn the feature while Cutout and CutMix continue to succeed. At even lower frequencies, only CutMix can learn the feature whenever it appears in the training data.

Q3, L2. Confusion regarding extremely rare features

We believe there may be some confusion regarding extremely rare features. We have provided explanations with examples for our framework in our global response, and we encourage you to refer to it. We address remaining questions here:

Is the assumption that .... extremely rare features negative?

Our training and test data distributions are identical. As detailed in our general response, learning more features generally improves performance. Although data with extremely rare features make up a small portion of the test distribution, learning these features can enhance test accuracy on that data, leading to overall test-time performance improvements. Thus, low performance of ERM on (extremely) rare features is negative for overall performance.

Limitation. One can not distinguish noise from extremely rare features

We think the reviewer may have confused. Extremely rare features are also label-dependent information that can appear nontrivially many times (albeit relatively rarer) across several data points, while similar or identical noise patches hardly reappear across different data points.

Q3. Non-monotonicity of CutMix

In Figure 1, the leftmost plot shows that the curve for CutMix initially rises, then slightly decreases before plateauing. This indicates a non-monotone behavior for CutMix, in contrast to the other methods. Let us clarify why: Due to the use of mixed labels, CutMix loss has global minimizers and they evenly learn all kinds of features. In the early stages of learning, the model tends to overshoot in learning common features because of their faster learning speed compared to other features. This initial overshooting leads to a temporary rise and subsequent decrease in the curve. This non-monotone behavior is precisely the reason why we had to devise a novel proof strategy different from ERM and Cutout.

W3, Q4, Q5. Real world evaluation

We experimented on CIFAR 10 to support our findings and address the reviewer’s concern.

We train ResNet18 using vanilla training without any augmentation, as well as with Cutout and CutMix, following the same experimental details described in Appendix A.1, except using only 10% of the training set. This data-hungry setting is intended to highlight the benefits of Cutout and CutMix. We then evaluated the trained models on the remaining 90% of the CIFAR training dataset. The reason for evaluating on the remaining training dataset is that we plan to analyze the misclassified data using C-score[4], which is publicly available only for the training dataset.

C-score measures the structural regularity of data, with lower values indicating examples that are more difficult to classify correctly. In our framework, data with harder-to-learn features (corresponding to rarer features) would likely have lower C-scores. Since directly extracting and quantitatively evaluating features learned by the models is challenging, we use the C-score as a proxy to evaluate the misclassified data across models trained by ERM, Cutout, and CutMix.

Figure 2 in our attached pdf in our global response illustrates that Cutout tends to misclassify data with lower C-scores compared to ERM, indicating that Cutout learns more hard-to-learn features than vanilla training. Furthermore, the data misclassified by CutMix has even lower C-scores than those misclassified by Cutout, suggesting that CutMix is effective at learning features that are the most challenging to classify. This observation aligns with our theoretical findings, demonstrating that CutMix captures even more difficult features compared to both ERM and Cutout.

Since directly visualizing features learned by a model is challenging, we present data that was misclassified by the model trained with ERM but correctly classified by the model trained with Cutout instead. In Figure 3 in attached file, we show 7 samples per class with the lowest C-scores, which are considered to have rare features. Similarly, we also visualize data misclassified by the model trained with Cutout but correctly classified by the model trained with CutMix to represent data points with extremely rare features. This approach allows us to interpret some (extremely) rare features in CIFAR 10 ,such as frogs with unusual colors.

Thanks for your time and consideration.

Best regards,

Authors

We express our gratitude for your time and valuable comments. We also thank you for bringing to our attention the typo in (4) and unclear statement in Lemma B.3 (we intended to claim the “existence” of such $\gamma_s^{(t)}, \rho_s^{(t)}$ for each training method). We will fix/clarify this in our next revision. In the following, we address the points raised by the reviewer.

W1. Motivation for data

We provide motivations with examples for our framework in our global response. We would appreciate it if you could refer to it.

W2, Q2&3. Choice of hyperparameters

We assume the number of data points $n$ is much smaller than the dimension $d$ which corresponds to the over-parameterization regime common in modern neural networks. This allows us to apply high-dimensional probability theory effectively, as you mentioned.

The assumptions on hyperparameters, such as the strength of noise and the frequencies of features, are designed to highlight the distinctions between the three training methods by satisfying the inequalities outlined below line 280. The choices for other hyperparameters are made to ensure convergence within our specific setting. These types of assumptions are also considered in several related works [1,2,3].

Also, we do not impose a strict condition on the total number of features. More important thing is the frequency of each feature rather than the total number of features. Any value of $K$ is possible as long as each $\rho_k$ can satisfies given conditions.

Even though most choices of hyperparameters arise from technical elements of our proof, we can provide intuition on choice of cutting size $C$ in cutout. Our intuition behind Cutout is that it outperforms by removing dominant noise, which do not generalize to unseen data. Thus, $C\geq 1$ is necessary to ensure that the analysis of training dynamics differs from that with $C=0$. The proof strategy for Theorem 3.2 heavily relies on the condition $C\geq1$. Hence, setting $C=0$ in Theorem 3.2 does not derive Theorem 3.1 directly.

In practice, image data contains features and noise across several patches. A larger cutting size can be effective in removing noise but may also remove important features that the model needs to learn. Thus, there is a trade-off in choosing the optimal cutting size. From this intuition, we believe that for images with a larger portion of background(noise), a larger cutting size is likely to be more effective.

W3. The computational costs

Since our work does not focus on proposing novel algorithms, we believe that a discussion on computational and memory costs is not essential and should not be considered a weakness of our work. However, we address this concern here for the reviewer's benefit.

In the practical implementation of Cutout, a squared region is randomly sampled and this same region is cut from all images within a batch. Similarly, in the implementation of CutMix, a squared region is randomly sampled and then used to cut and paste parts of pairs of data batch and its random permutation. Consequently, the computational and memory costs involved in each iteration of both Cutout and CutMix are comparable to those of vanilla training, differing only by a constant factor.

In our theoretical setting, we consider training using full-batch gradient descent for ERM, and gradient descent on the expected loss for Cutout and CutMix. These idealized training methods involve higher computational and memory costs per epoch since they require more augmented data. For example, Cutout requires $\binom{P}{C} n$ data points and CutMix requires $2^{P-1} n^2$ data points. However, we would like to emphasize that this setting is designed for a theoretical understanding; as outlined above, the practical versions are not computationally burdensome.

Q1&3. Recent works on feature learning theory

Thank you for suggesting recent works on feature learning theory and for raising questions related to comparisons with these literatures. We were not familiar with these works and have noted that they are somewhat orthogonal to our work due to differences in the definition of “features” compared to our approach and other related previous works.

The notion of features in our work refers to label-relevant information contained in the input that is useful for generalization to unseen data. In contrast, the notion of features in the works you suggested seems to be relate to the outputs of the last hidden layer (i.e., the representation of data point learned by the network). This distinction suggests that the concepts of "features" in these studies differ from those in our approach.

We believe that a large learning rate has less impact within our notion of feature learning since it does not affect trend in learning speed of features and noise which is essential as we described in Section 4.1.

Q5. The proof strategy for CutMix

The proof strategy for CutMix cannot be applied to ERM and Cutout because their training loss lacks a global minimum due to the exponential tail of the logistic loss ($\lim_{z \rightarrow \infty} \ell(z) = 0$). In contrast, CutMix loss has a global minimum due to its use of mixed labels ($\lim_{z \rightarrow \infty } \ell(z)+ \ell(-z) = \infty$).

Since main idea of our strategy is considering the training loss as a composition of reparameterization and convex functions, we believe that this technique could be extended to a broader class of architectures, datasets, and training methods involving mixed labels. However, the exact characterization of the global minimum in different settings would require techniques beyond those we have used.

Thanks for your time and consideration.

Best regards,

Authors