Understanding Nonlinear Implicit Bias via Region Counts in Input Space

We thank the reviewer for the time spent on reviewing our work and for the very detailed comments. Please find the details below.

Q1: How to use the region count metric for regularization?

A1: Due to the word limit, we respectully refer the reviewer to Reviewer VXuC's response A2.

Q2: How to extend the theorem to multi-dimensional region counts?

A2: The choice of one-dimensional region count is primarily for technical simplicity. The core idea of the proof is that the region count can be upper bounded by the number of activation pattern changes. This holds regardless of the hyperplane’s dimensionality, probably with a different dependency in the exponent. This observation suggests a natural direction for extending the analysis to the multi-dimensional case, which we leave for future work.

Q3: For which types of analysis is the parametrization-independence of your metric important?

A3: Our primary goal is to develop a metric that characterizes the implicit bias of nonlinear neural networks. Since we focus on understanding the solutions the network converges to rather than how it is trained, a parametrization-independent metric is essential for properly capturing this implicit bias.

Q4: Conduct experiments to find whether region count can distinguish between "very good" and "good" models.

A4: We fixed the learning rate at 0.1 and batch size at 256, and varied only the weight decay to compute the correlation.

The correlation plot is shown in Figure 3 of https://anonymous.4open.science/r/icml-rebuttal-B813/icml%202025%20rebuttal.pdf. The generalization gaps range from 17 to 20, and the region counts range from 2.5 to 3, making them relatively close. We observe a correlation of 0.84, indicating that even under strong generalization settings (small learning rate, large batch size), our region count metric can effectively distinguish between "very good" and "good" models.

Q5: Clarify the hyperparameters for which your metric is well-suited/ill-suited.

A5: As shown in Figures 6 and 7, our metric maintains a strong correlation under mixup augmentation. This aligns with mixup’s implicit effect of reducing region count by enforcing smooth label transitions, which may partly explain its performance benefits. For random crops and flips, high correlation is observed when evaluated separately. However, pre-crop and post-crop data are not directly comparable, as cropping fundamentally changes the data distribution. Such cases are better treated as distinct distributions rather than as hyperparameter variations.

Q6: Reporting rank-correlation.

A6: We add experiments reporting the rank correlation[3]. All networks are trained on CIFAR-10 using the hyperparameters in Table 1. The results are as follows:

These results show consistently high rank correlation, further validating the effectiveness of our metric.

Q7: Do regression analysis where the generalization gap is regressed on all metrics.

A7: We train ResNet18 on CIFAR-10 and conduct regression analysis using five metrics:sharpness, margin, normalized margin, 1D region count, and 2D region count. We compute the $R^2$ values. The results are as follows:

Both our proposed 1D and 2D region count metrics achieve high $R^2$ values, nearly matches the overall $R^2$, demonstrating strong predictive power for the generalization gap compared to existing measures.

Q8: Discuss the paper [1][2].

A8: [1] attributes the generalization difference to the learning order of examples: large learning rates delay fitting hard-to-fit but generalizable patterns until after annealing, while small learning rates prioritize them early. [2] proposes a phase-based view of training dynamics, where large learning rates in the “catapult” phase reduce curvature and lead to flatter minima. In contrast, our paper offers a new perspective: large learning rates improve generalization by reducing the number of region counts. We will include a discussion of [1][2] in the next version.

We thank the reviewer once again for the valuable suggestions.

References

[1] Li, Yuanzhi, Colin Wei, and Tengyu Ma. "Towards explaining the regularization effect of initial large learning rate in training neural networks." Advances in neural information processing systems 32 (2019).

[2] Lewkowycz, Aitor, et al. "The large learning rate phase of deep learning: the catapult mechanism." arXiv preprint arXiv:2003.02218 (2020).

[3] Kendall, Maurice G. "A new measure of rank correlation." Biometrika 30.1-2 (1938): 81-93.

We thank the reviewer for the comments and constructive suggestions. In the following, we address the main concern raised. Please find the details below.

Q1: It would be nice if more datasets and architectures can be analyzed.

A1: We thank the reviewer for the suggestion. We add a experiment to explore the applicability of our approach to transformer-based models. We conduct an experiment using Vision Transformers (ViT)[1] on CIFAR-10. Details of the hyperparameters used are summarized below:

The correlation figure is shown in Figure 2 in the anonymous github website https://anonymous.4open.science/r/icml-rebuttal-B813/icml%202025%20rebuttal.pdf. We achieve a correlation of 0.84, validating the applicability of our measure in this network architecture. We will include these experimental results in the next version of the paper.

Q2: If we calculate the expected 1D region count between two random points in the convex hull of training data, do we get similar results? In other words, do we need to choose two training examples as the endpoints?

A2: We thank the reviewer for the suggestions. In Appendix C, we have conducted with alternative approaches to generate hyperplanes for computing the region count, selecting a training data point and extending it in a random direction by a fixed length. Even with this method, the correlation remains high.

We further conduct experiments by calculating the expected 1D region count between two random points in the convex hull of the training data, using the hyperparameters from Table 1 to train the neural network and compute the correlation. The result are as follows:

The results confirm that the correlation remains strong, demonstrating that our method does not require selecting two training examples as endpoints.

Finally, we thank the reviewer once again for the effort in providing us with valuable suggestions. We will continue to provide clarifications if the reviewer has any further questions.

References

[1] Dosovitskiy, Alexey, et al. "An image is worth 16x16 words: Transformers for image recognition at scale." arXiv preprint arXiv:2010.11929 (2020).

We greatly appreciate the reviewer's comments and valuable suggestions. We added extensive experiments and summarize them below. We will include more detailed results in the revision.

Q1: It is unclear whether region count is a good proxy for generalization performance, because it is unclear what a good correlation metric is. What is the correlation metric for other possible proxies, like norm and margin, or even simpler ones like number of iterations of GD? There is no other connection provided between region count and generalization performance other than through this correlation.

A1: We appreciate the reviewer's feedback on the missing details. In Section 3(Figure 2), we have already shown that the correlations between generalization gap and frobenious norm, margin, or margin/frobenious norm are all weak.

We follow the reviewer's advice and conduct additional experiments on other generalization measures, including spectral norm[2], PB-I and PB-O (which are sharpness metrics from PAC-Bayesian bounds that use the origin and initialization as reference tensors), PB-M-I and PB-M-O[3][4][5] (which are derived from PAC-Bayesian Magnitude-aware Perturbation Bounds). We conduct experiments on CIFAR-10 using ResNet-18 and use the hyperparameters in Table 1. The results are summarized below:

The results are consistent with the results in [1] and demonstrate that our proposed region count measure exhibits a significantly higher correlation with the generalization gap compared to other measures. We will include these findings in the next version of the paper.

Q2: The theoretical bound provided gives region count bounds in terms of O(N), which is much larger compared to the empirical region counts in the 2-20 range. It's not clear how meaningful the theoretical bound is, and there is no theoretical generalization bound provided in terms of region count.

A2: Thank you for raising this question. The $O(N)$ dependency is actually tight, by considering N points on a line with alternating labels. The upper bound in the theorem is a worst case analysis, and it can possibly be tightened with additional assumptions on the data distribution.

Also, we believe generalization results in terms of region count is possible, since region counts might constrain the size of the function class, which connects to traditional ways of constructing generalization bounds based on function class complexity. We believe the strong empirical connection between region count and generalization shown in this paper is already a novel contribution to the generalization community, and leave a rigorous proof to the future work.

Finally, we thank the reviewer once again for the effort in providing us with valuable and helpful suggestions. We will continue to provide clarifications if the reviewer has any further questions.

Reference

[1] Jiang, Yiding, et al. "Fantastic generalization measures and where to find them." arXiv preprint arXiv:1912.02178 (2019).

[2] Bartlett, Peter L., Dylan J. Foster, and Matus J. Telgarsky. "Spectrally-normalized margin bounds for neural networks." Advances in neural information processing systems 30 (2017).

[3] Keskar, Nitish Shirish, et al. "On large-batch training for deep learning: Generalization gap and sharp minima." arXiv preprint arXiv:1609.04836 (2016).

[4] Neyshabur, Behnam, et al. "Exploring generalization in deep learning." Advances in neural information processing systems 30 (2017).

[5] Bartlett, Peter L., Dylan J. Foster, and Matus J. Telgarsky. "Spectrally-normalized margin bounds for neural networks." Advances in neural information processing systems 30 (2017).

We thank the reviewer for the detailed comments. We address the main concerns below:

Q1: Personally, I would like to see some results for networks which did not converge and exhibit a high test error (the lowest result in Tab. 2 is 0.78 on imagenet). To what extent (going down in generalizability) does the correlation hold?

A1: We appreciate the reviewer’s insightful question. We observed relatively low training and test accuracy on ImageNet, achieves about 70% accuracy on the training set and 45% on the test set. However, the correlation in Table 2 remains high, though slightly lower than on CIFAR-10/100.

Additionally, we conduct experiments with traditional ML models. When training decision trees and random forests on CIFAR-10 with various hyperparameters, most configurations failed to converge (yielding high test error). The hyperparameters are as follows:

The correlation figure is shown in Figure 1 in the anonymous github website https://anonymous.4open.science/r/icml-rebuttal-B813/icml%202025%20rebuttal.pdf. We achieve a correlation of 0.96 in decision trees and 0.98 in random forests, demonstrating that our measure remains robust despite low test accuracy.

Q2: Given the link between region count and generalizability, do you think it would be possible to explicitly aim for low region count in the objective function of a neural network training? Do you think this would help in training better models? Could this term be applied from the start of the training, or perhaps when the network has already "stabilized" after some iterations?

A2: We thank the reviewer for this thoughtful suggestion. Since the region count computation is currently non-differentiable, we cannot explicitly incorporate it as a regularization term. However, the data augmentation method mixup implicitly minimizes region count by encouraging smooth transitions between labels rather than predicting unrelated classes. This suggests our method may partially explain mixup’s performance benefits.

While it cannot be directly used as a regularization term, we find it effective for early-stage hyperparameter evaluation. We conduct experiments analyzing the correlation between early-training region counts and final generalization gap (distinct from Table 3’s per-timestep analysis). We train Resnet18 on CIFAR-10 with 200 epochs. The results are as follows:

The results show strong correlation between early region counts and final generalization(since epoch 30) and region counts stabilize quickly during training. This enables early stopping for poor hyperparameter configurations by monitoring initial region counts, reducing computational costs. We will add these findings to the paper.

Q3: I find very interesting the link between region count and data augmentation. I think that data augmentation can help in decreasing region count, thus helping generalization; perhaps this could explain the success of contrastive learning methods[1]?

A3: We thank the reviewer for this insightful question. For now, our analysis applies to supervised learning for overparameterized models. For contrastive learning methods, the pretrained representations obtained through this method can serve as feature extractors to improve performance in downstream classification tasks, particularly when labeled data is scarce. If we use kernel-based methods[1] to connect more positive samples when the initial label prediction of the neural network is uncertain, it will lead to simpler learned regions rather than mixed positive and negative samples. This also helps minimize the learned region count, thereby enhancing performance. We believe this is a promising direction for future research.

We thank the reviewer once again for the valuable and helpful suggestions. We would be happy to provide further clarifications if the reviewer has any additional questions.

Reference

[1] Dufumier, Benoit, et al. "Integrating prior knowledge in contrastive learning with kernel." International Conference on Machine Learning. PMLR, 2023.