Understanding Nonlinear Implicit Bias via Region Counts in Input Space
Authors: Jingwei Li
Jing Xu
Zifan Wang
Huishuai Zhang
Jingzhao Zhang
Venue: ICML 2025 poster (2025)
Keywords: implicit bias
region counts
non-linear neural network
generalization gap
Primary area: theory->deep_learning

Abstract: One explanation for the strong generalization ability of neural networks is implicit bias. Yet, the definition and mechanism of implicit bias in non-linear contexts remains little understood. In this work, we propose to characterize implicit bias by the count of connected regions in the input space with the same predicted label. Compared with parameter-dependent metrics (e.g., norm or normalized margin), region count can be better adapted to nonlinear, overparameterized models, because it is determined by the function mapping and is invariant to reparametrization. Empirically, we found that small region counts align with geometrically simple decision boundaries and correlate well with good generalization performance. We also observe that good hyper-parameter choices such as larger learning rates and smaller batch sizes can induce small region counts. We further establish the theoretical connections and explain how larger learning rate can induce small region counts in neural networks.

Understanding Nonlinear Implicit Bias via Region Counts in Input Space
Jingwei 1 Jing Xu 1 Zifan Wang" 12 Huishuai Zhang? Jingzhao Zhang
Abstract
implicit bias (Brutzkus et al., 2017; Soudry et al., 2018). Implicit bias refers to the inherent tendencies in how neural networks learn and generalize from the training data, even without explicit regularizations or constraints.
One explanation for the strong generalization abil- ity of neural networks is implicit bias. Yet, the definition and mechanism of implicit bias in non- linear contexts remains little understood. In this work, propose characterize implicit bias by the count of connected regions in the input space with the same predicted label. Compared with parameter-dependent metrics (e.g.. norm or normalized margin), region count can be better adapted to nonlinear, overparameterized models, because it determined by the function mapping and is invariant to reparametrization. Empiri- cally, we found that small region counts align with geometrically simple decision boundaries and correlate well with good generalization per- formance. We also observe that good hyper- parameter choices such as larger learning rates and smaller batch sizes can induce small region counts. We further establish the theoretical con- nections and explain how larger learning rate induce small region counts in neural networks.
The implicit bias of linear neural networks has been exten- sively studied. One of the classical setting is linear classi- fication with logistic loss. Brutzkus al. (2017); Soudry et al. (2018); Arora et al. (2019) show that the parameter converges to the direction that maximizes the Le margin. For regression problems, it is proved that gradient descent or stochastic gradient descent converges to parameter that is closest to the initialization in terms of L- norm (Gunasekar et al., 201 8a). The results of the linear regression model can be extended to deep linear neural networks by generalizing the definition of min-norm and max-margin solutions (Ji & Telgarsky, 2018at Vaskevicius et al., 2019; Woodworth et al., 2020).
Compared to linear models, defining implicit biases in non- linear networks poses significant challenges. One line of work studies homogeneous networks and demonstrates that gradient flow solutions converge to KKT point of the max- margin problem (Lyu & Li, 2019; Ji & Telgarsky, 2020; Wang et al., 2021; Jacot et al., 2022). Further research ex- tends this analysis, showing that gradient flow converges to a max-margin solution under various norms (Ongie et al., 2019; Chizat & Bach, 2020). Other studies focus on de- scribing the implicit bias of neural networks using sharp- ness, such as (Foret et al., 2020; Montúfar al., 2022: Andriushchenko et al., 2023).
1. Introduction
One mystery in deep neural networks lies in their ability to generalize, despite having significantly more learnable parameters than the number of training examples (Zhang et al., 2017a). The choice of network architectures, includ- ing factors such as nonlinearity, depth, and width, along with training procedures like initialization, optimization al- gorithms, and loss functions, result in vastly diverse generalization performance (Sutskever et al., 2013; Smith et al., 2017; Wilson et al., 2017: Li et al., 2019). The varied generalization abilities exhibited by neural networks are often explained by many researchers through the theory of
We note that previous definitions of implicit bias in neural networks mostly focus on certain metrics of network param- eters. While these approaches enable explicit analyses of training trajectories, they encounter new challenges when applied to nonlinear networks: reparametrization of the net- work can preserve the function mapping but give completely different parameters, and consequently, different implicit biases. We will discuss this point in detail in Section 3.
'Equal contribution 'Institute for Interdisciplinary Informa- tion Sciences, Tsinghua University 'Shanghai Qizhi Institute "Wangxuan Institute of Computer Technology, Peking University. Correspondence to: Jingwei Li <ljw22 @ www.iiistsnnuuua.ddeeoo Jingzhao Zhang <jingzhaoz @ mail .su..nu...cu..c.>
Motivated by the above studies, we focus on leveraging decision boundaries in the input space to characterize im- plicit bias. We adopt a metric called region count, which measures the average number connected components in the decision regions of predictor (see Figure 1). This idea was initially introduced by Somepalli et al. (2022), who
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Correlation ation
Region Counts vss. Hyperperameters
1.0
Resnet18
beich Vie
522=332
0.8
35
528-
Generalization Gap
Region Counts
0,6
30
0,4
25
0.2
3
20
0.0
0.2
0.6
0.8 1.0
3.0
3.5
4.0
4.5
0.301
0.005
0.01
0.05
0.1
Region Counts
Leomiigg Rate
Region counts: 4
Figure 1: A schematic illustration main results in this paper. Left: The region counts in 2-dimension input space. Each distinct region represents an area where the neural network makes the same prediction for all points within that region. Middle: A strong correlation between region counts and the generalization gap. Right: Larger learning rate smaller batch size induces smaller region counts.
used under the name fragmentation score study the double descent phenomenon by counting decision regions on two-dimensional planes defined by training examples. In contrast, we extend this idea beyond 2D subspaces and input
the generalization gap. This correlation remains robust across different learning methods, datasets, training parameters, and counting methods.
generalize the region count to subspaces, which enables more comprehensive geometric characterization.
2.
We assess the factors that induce small region count, discovering that training with larger learning rates and smaller batch sizes typically results in fewer regions. This provides possible cause for the implicit bias in neural networks.
To compute region count, we project the input space onto www-dimensional subspaces, the trained network to predict the labels of points within these subspaces, and count the number of connected regions that share the same predicted label. Unlike previous studies on linear region count (Hanin & Rolnick, 2019a;b; Safran et al., 2022), which focus on activation patterns and representational ca- pacity, the metric of region count is label-dependent and reflects the functional behavior of the classifier. We find that region count correlates strongly with the generalization gap defined as the difference between training and test er- rors. As illustrated in Figure I, models with fewer decision regions tend to generalize hetter.
3. We conduct theoretical analyses region counts, and show that for two-layer ReLU neural networks, gra- dient descent with large learning rate induces a small region count.
2. Related Works
Implicit Bias of Linear Neural Network The implicit bias in linear neural networks are thoroughly investigated in recent works. For linear logistic regression on linearly sepa- rable data, full-batch gradient descent converges in the direc- tion of the maximum margin solution (Soudry et al., 2018). This foundational work has various follow-ups, including extensions non-linearly-separahe data (Ji & Telgarsky, 201 8b; 2019), stochastic gradient descent (Nacson al., 2019), and other loss functions and optimizers (Gunasekar et al., 2018a).
Furthermore, we show that neural networks trained with large learning rate or small batch size, which are typically deemed beneficial for generalization, are biased towards solutions that have small region counts. Therefore, region count empirically serves as an accurate generalization met- ric as well as an implicit bias indicator. We also provide theoretical analyses to explain this phenomenon. We prove that for two-layer ReLU neural networks, gradient descent with large learning rate induces a small region count, which accords well with our empirical findings.
These findings in linear logistic regression are generalized to deep linear networks. For fully-connected neural networks with linear separable data, Ji & Telgarsky (2018a) shows that the direction of weight also converges La max-margin solution. For linear diagonal networks, the gradient flow maximizes the margin with respect to a specific quasi-norm that is related to the depth of network (Gunasekar et al., 2018b; Woodworth et al., 2020; Pesme et al., 2021), leading to a bias towards sparse linear predictors as the depth goes to infinity. This sparsity bias also exists in linear convolutional
The main contributions of this paper are listed as follows:
1. We use the region count to to systematically character- ize implicit bias. Through extensive experiments, we verify strong correlation between region count and
2

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
networks (Gunasekar et al., 2018b; Yun al., 2020).
fragmentation varies with network width and its connection to the double descent phenomenon. While their approach provides important empirical observations, the analysis re- mains largely qualitative and limited to specific architectural variations.
Implicit Bias of Non-linear Neural Network The non- linearity of modern non-linear neural networks pose chal- lenges to studying its implicit bias. Initial works in this area (Lyu & Li, 2019; Ji & Telgarsky, 2020) focus on homogeneous networks. These studies show that with exponentially-tailed classification losses, both gradient flow and gradient descent converge directionally to KKT point in a maximum-margin problem. Wang et al. (2021) consider a more general setup that includes different optimizers and prove that both Adam and RMSProp are capable of max- imizing the margin in neural networks while Adagrad is not. Ongie et al. (2019); Chizat & Bach (2020) showcased bias towards maximizing the margin in variation norm for infinite-width two-layer homogeneous networks. Lyu et al. (2021); Jacot et al. (2022) identified margin maximization in two-layer Leaky-ReLL. networks trained with linearly separable and symmetric data. More recent investigations into non-linear neural networks, such as (Jacot, 2022), focus on the homogeneity of the non-linear layer, demonstrating an implicit bias characterized by novel non- non-linear rank.
Our work extends this line of research in several key di- rections. First, we adopt a more general definition of re- gion count over
subspaces, rather than restricting two-dimensional planes. This allows us to capture more comprehensive geometric information and supports quantitative analysis. Second, we systematically investigate the correlation between region count and the generalization gap across a variety of architectures, training hyperparameters, and datasets. Third, we further offer a thcoretical analysis of region count and study its behavior under distribution shifts. To the best of our knowledge, we are the first to provide comprehensive empirical and the- oretical analysis that links region count to generalization ability.
3. Motivation
Norm-based and margin- -based characterizations belong to the most popular measures of implicit bias. Various defini- tions for norm and margin exist. For simplicity, we consider the following two definitions.
Region Counts of Neural Network Prior work has ex- tensively studied the number of linear regions ReLU networks (Hanin & Rolnick, 2019a;b), where a linear re- gion refers to set of imputs sharing the same activation pattern. For example, Safran et al. (2022) showed that for two-layer ReLU network with width gradient flow con- verges directionally to a network with at most (r)) linear regions. Other studies (Serra et al., 2018; Cai et al., 2023) demonstrated that increasing the number of linear regions can enhance representational capacity and potentially im- prove performance. However, linear regions are defined independently of output labels and thus primarily reflect the expressiveness of the network rather than its generalization behavior.
Example 1 (Norm and Margin). Let W = (W,,... Wi denote the post-training weight parameters of an l-layer neural network fw (z) Wio(W, ... ...Wa (21(W1))) with (-) the ReLU activation function. funccttooonn Denote the weight ini- tialization as W = {WP, W Consider the Frobe- nious norm between network weights and initialization:
d(w)= I - W
and the outpul-space margin
In contrast, decision regions are defined as connected sub- sets of the input space that correspond the same predicted label. Nguyen et al. (2018) investigated decision regions over the full input space and showed that, under certain con- ditions, each class tends to form single connected region. However, connectivity in the full space does not necessarily imply connectivity in a subspace-for instance, two points may be connected in 3D but disconnected in a 2D slice. Subspace analysis thus reveals a richer and more nuanced structure of decision boundaries.
>(W) = (B(..))
[(()) - max ((x)) 14
d(-)) and 7-)) are commonly used indicator for implicit bias of linear models (Soudry et al., 2018; Ji & Telgar- sky, 201 2018b). However, both of them are not invariant to network reparameterizztton. We can construct different set of network weight parameters by scaling the parame- ters as W = {2W1, _ WW2,... Wi}. such that sw = fw but d(W) + d(W) in general. Similarly, we can scale the last layer weights and get W -W,,.. .Wi), such that rW)) * >WW), but argmax,/w = argmax, (2). This reparameterization trick also works for more compli- cated based and margin-based generalization metric in (Jiang et al., 2019), or the sharpness-bas based metrics (An- driushchenko et al., 2023).
The paper (Somepalli et al., 2022) is the most relevant to our work, which is the first to systematically analyze the number of decision regions in input subspaces. They intro- duce the fragmentation score, defined as the average number of decision regions over 2D planes determined by triplets of training points. Their study focuses on illustrating how
3

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Correlation of d(W): 0.74
Correlation of y(W): 0.60
Correlation of y(W))d 0.16
Generalization Gap
Generalization Gap
Generalization Gap
35
35
35
30
30
30
25
25
25
20
20
20
15
15
36
42
48
54
2
4
0.05
0.10
0.15
d(W)
y(W)
v(W)/d(W)
Figure 2: Norm-based and margin-based measures may not be predictive of generalization gaps. We train ResNet18 on the CIFAR-10 dataset using various hyperparameters. These implicit bias measures can be ineffective for general non-linear neural networks.
We numerically investigate whether they effective mea- sures, by training 88 CIFAR-10 dataset, using different hyperparameters as in Table 1. The results are presented in Figure 2, which indicates that these measures have a low correlation with the generalization gap in the deep learning regime. One could choose other definitions of norms to achieve stronger correlations, but such choices often problem-specifie and require domain expertise, discussed in (Jiang et al., 2019).
4.1. Definition of Region Counts
Let d denote the training data dimension and IRd {1, .N} denote a neural network for classification task with N classes. For a subset U C Rd, we can define the connectedness of its element as follows:
Definition 4.1 (Connectedness)) We say the data points 31, 32 E U are (path) connected with respect to a neural network f if they satisfy:
The definition of margin may also be improved to the input- space margin, i.., the & distance input data x to decision boundary defined by the classifier, which is able to character- ize the quality and robustness of the classifier. This metric invariant reparameterizatiio and therefore more intrin- sic to the underlying classifier. However, due to the highly nonconvex loss landscape, the input-space margin is NP- complete to compute and even hard to approximate (Katz et al., 2017; Weng et al., 2018). Therefore, quantitatively analyzing the decision boundary of a neural network and characterizing its implicit bias remains a challenge.
f(x1) = f(x2) =
There exist continuous mapping [0, 1] U. 7() 21, x(1 I2, and for any [0, 1].
((+(1) =c
Then we define the connected region in this subset:
Definition 4.2 (Maximally Connected Region). We say V C. U is maximally connected region in U E with respect to neural network f if it satisfies the following property:
Our motivation stems from simple idea: although the margin in the input space is difficult to compute directly, we can instead quantify the number of regions partitioned by the decision boundary. This measure is invariant to model reparameterization and reflects the geometric complexity of the classifier, which are crucial ingredients for a robust and scalable indicator of implicit bias.
For any x, y E V, they connected.
For any x E V. E U V, they are not connected.
Finally, we formally define the region count as follows:
Definition 4.3 (Region Count). For subset U C [d, we define its region count Ry as the number of maximally connected regions in with respect to a neural network f:
4. Preliminary
Although region count is natural measure for the com- plexity of a predictor, and it depends only on the decision function rather than the model parameterization, its formal definition and computability remains unclear. In this sec- tion, first provide the definition and low-dimensional approximation of region counts. We then empirically verify that region counts correlate with generalization gap.
Rv = card(V c UVV is a maximally connected region).
where card is the cardinality of set.
4.2. Estimating Region Counts
Calculating the region count in the original high- dimensional input space can be computationally intractable.

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
We follow the estimation method in (Somepalli et al., 2022), computationally efficient surrogate by calculating the region counts low dimensional subspace spanned by training data points.
5. Region Counts Correlate with Generalization Gaps
In this section, we present our major empirical findings, which reveal strong correlation between region counts and the generalization error of neural networks'.
Definition 4.4 (Region Count in d-Dimennional Subspace). We randomly sample 1 datapoints in the training set Drrain to generate a convex region in I subspace. The d-dimensional region count Rg is defined as the expectation of number of maximally connected regions:
We conduct image classification experiments on the CIFAR-10 10 dataset, using different architectures, including (Tan & Le, 2019), and SeNet18 (Hu al., 2018). Results on other architectures are deferred to ablation studies, We vary the hyperparameters for training, such as learning rate, batch size and weight decay coefficient, whose numbers are re- ported in Table 1. The region count calculated using randomly generated ID hyperplanes, as described Exam- plc 2. We run each experiment 100 times and report the average number.
ResNet18 (He al., 2016), EfficientNeeBO
Ra= E2 Deruin [Conv(as (a,,,, .2 #a+1
where ø1, 22,..., yy....,TToo Id+1 are sampled from the training dataset, and Conv (2n, T2 T441) is the convex hull formed by these d + points.
1.0
1.0
We plot the region count and generalization gap of different setups in Figure 4, and calculate the correlation between them. For each network architecture, we observe a strong correlation as high as 0.98. The overall correlation for all the three networks still reaches 0.93. This reveals remarkably high correlation between region counts and generalization gap.
0.8
0.6
0.4
0.4
0.2
0.0
1.0
1D Region Counts: 5 2D Reglon Counts: 3
Table I: The hyperparameters for experiments. We vary the learning rate, batch size, and weight decay for training neural network, to modulate the model's generalization ability.
Figure 3: Illustrations of region counts in 1D and 2D subspace. We use different colors to represent different outputs of the neural network.
Hyperparameters
Value
This paper primarily focuses on low dimension spaces, which is illustrated as below. In practice, we randomly sample training data points for multiple times and take the average region counts. In Section 7, we show that the choice of subspace dimension d does not significantly affect the results. The details on how to count the regions and generate the polytopes are provided in Appendix B.
Learning rate
0.1, 0.01, 0.001
Batch size
256, 512, 1024
Weight decay
10-9. 10-6, 10-7
6. Region Counts Quantify Implicit Bias
Example 2 (Region counts in ID and 2D subspace). For re- gion count in I-dimensional subspace, we randomly sample two data points, denoted as xı and Zz Z. from the training set, and calculate the region count on the line segment connect- ing them:
In this section, we further investigate the implicit bias of neural networks via region counts. We show both empir- ically and theoretically that neural networks trained with appropriate hyperparameters tend to have smaller region counts, thus achieving better generalization performance.
{axı + (1-a))2,05aa
6.1. The Bias from Training Hyperparameters
Training neural networks requires careful selection of many hyperparameters, such as learning rates, batch sizes, op- timizers. epochs and so on. Here, we primarily focus on learning rate and batch size, and study their impact on the region count.
For the 2-dimensional case, we randomly sample three data points, Ii, X2, and V3, from the training set, and calculate the region count in the convex hull spanned by them:
faz1 + B22 + (1- +(1
- a --03s 2 0,
Code available https: cttps://github..com/ 1 1i figiiggi0000/// /mppmmppliii tit_bbiss
We provide an illustration Figure 3.
5

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Denote the GD trajectory as (We)200 For two input data Tay Let R(Fa; Rb, W) denote the region count the line segment connecting them, and N M W) denote the number of activated neurons with input za. i.e., the number of i such that wi Ta > 0.
Resner18 EfficientNetBO
Generalizzaioo Gap
SENet18
50
40
30
We make the following assumption on the data distribution.
Assumption 6.1. The training dataset D
(Li,,h)ssss satisfies the following two properties:
Region Counts
||:||| 2 for all ISiSN. N.
Figure 4: Strong correlation between region counts and generalization gap. We conduct experiments using three neural networks on the CIFAR-10 dataset, with various hyperparameters. There is a strong correlation between region counts and the generalization gap, with a correlation coefficient of 0.98 for each network and 0.93 across all networks.
2. With probability one, any W E (Wi)e0 satisfies w| 3jj * for all S S q. S i S N, where the randomness comes from weight initialization.
The validity of Assumption 6.1 comes from the fact that the bifurcation zone (Bertoin et al., 2021) of ReLU neu- ral networks, which contains its non-differentiable points, has Lebesgue measure zero (Bolte & Pauwels, 2020; 2021; Bianchi et al., 2022). Therefore, the distribution of weights are absolutely continuous with respect the Lebesgue measure, the bifurcation zone be avoided with probability one. We conjecture that it can be proved rigorously, but leave it as an assumption since the proof diverges from the main content in this paper.
Learning Rates. We provide the relationship between the learning rate and the region count in Figure 5. Our findings indicate that a larger learning rate tends to simplify the decision boundary and results in smaller region count in the hyperplane. This accords well with real practices, where large learning rates of 0.1 0.01 are often favored for better generalization.
The next assumption characterizes the sharpness along the training trajectory. This is actually from the well-known edge of stability phenomenon (Cohen al., 2020; Damian et al., 2022; Arora et al., 2022; Ahn al., 2024), which states that the sharpness of neural networks, characterized by the E norm of the Hessian matrix, hovers around? ;
Batch Sizes. Similarly, the training batch size can impact the number of regions. As shown in Figure 5, smaller batch sizes lead to model with fewer regions. This result reveals the advantage of small-batch training, which leads to better generalization accuracy.
Previous studies (Keskar et al., 2016; Jastrzkebski et al., 2017; Hoffer et al., 2017: Novak et al., 2018; Lewkowycz et al., 2020) find that certain hyperparameters, such as a large learning rate and a small batch size, can improve the generalization of the neural network. Our observations provide a possible explanation: these good hyperparameter choices lead to a reduced region count. Such simplicity bias can decrease the generalization gap of neural networks.
Assumption 6.2 (Edge of Stability). There exist a T' E N. such that for t 2 T, with we have
(
Amax V ((w))(W))) θ
where Amax denotes the maximum eigenvalue of a matrix.
We are now ready to present the main theorem, which estab- lishes a relationship between region count and learning rate.
6.2. Theoretical Explanations
Next, we present theoretical analysis to explain why some hyperparameter choices, such large learning rate, can lead to small region counts.
Theorem 6.3. Under Assumption 6.1 and 6.2, we have that for neural net weights W. at training step t 2 T, with probability one, the average region count R(X, X', W.) for random training data point X, X' can be bounded as:
Consider a two layer ReLU neural network fw) = Ei a,o (w; x).. The second layer weights a; are initial- ized uniformly from {1, -1} and fixed throughout training. Let D {(r,, (i)) ISIN denote the training set. Con- sider training fw on D using gradient descent (GD) with learning rate 17. We choose the quadratic loss I(W, xr y) (y- - -w(())) and denote L(W)- = 1/2 Σx> 1 (W, 24, Bi)-
Ex,x [RXx X', Wol
N R(a, Ws) 50
N
(22))
6

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
4.2
Resneti8 EMicientNet0 SENe118
Resnet18 Nfiic
SENeti8
Region Counts
3.0
Counts
3.2
2,44
3.0
2.8
2.6
255
Tearning
Size
Figure 5: Large learning rate and small batch size reduce region counts. We train three networks on the CIFAR-10 dataset, varying the batch sizes and learning rates. Our findings reveal that a smaller batch size higher learning rate results in smaller region counts, allowing the network to learn simpler decision boundary and generalize better.
The theorem demonstrates that with a larger learning rate, gradient descent has the implicit bias to yield solutions with smaller region counts. This aligns well with the previous observations. We defer the proof of this theorem to Ap- pendix D, and sketch the proof as follows. The proof begins with bounding the region count using the activation pattern of ReLU neurons, as stated in the following lemma.
main results of the correlation between region count and the generalization gap.
More Architectures, Datasets and Hyperplane Dimen- sions. We first examine the influence of neural network architectures and datasets on our results. We provide addi- tional results on various neural network architectures such as ResNet34 (He al., 2016), VGG19 (Simonyan & Zis- serman, 2014), MobileNetV2 (Sandler et al., 2018), Shuf- fVeNetV2 (Ma et al., 2018), 8), RegNer200MF (Radosavovic et al., 2020), and SimpleDLA (Yu et al., 2018). We also use various datasets such as CIFAR- 100 (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009). Region counts and generalization gaps are evaluated across various learning rates, batch sizes, and weight decay parameters as listed in Table 1.
Lemma 6.4. The region counts between pair of data points is upper-bounded by the number of active neurons. For two inputs Fas Tb. we have
R(Ea, Ib, W) S N(xa, - (xs, W) + 2.
Then we prove that the activation pattern gives bound on the smoothness of the training loss.
Lemma 6.5. The sharpness of neural network is lower- bounded by the number of active neurons:
We also explore the effects of different methods for gen- crating the hyperplane in the input space. In our previous experiments, we generate the 1-dimensional plane using random pairs of samples from the training set and calculate the region count on them. Here we explore region counts in higher dimensional planes, that are spanned by data mandolly-selecter points from the training set, using the CIFAR-10 10 dataset.
N
Amax (VW)(W))) N2
W).
Note that this lemma brings in an additional N in the denom- inator, which leads to N N-dependent bound in Theorem 6.3. The N dependency actually tight worst case analysis, by considering N points We conjecture that the N N-dependency can be optimized un- der further structural assumptions on the data distribution, and leave it for further investigations. Equipped with these two lemmas, Theorem 6.3 is a consequence of the sharpness condition Assumption 6.2.
line with alternating labels.
The experiment results of the correlation are presented in Table 2. We also provide correlation plots for each network in Appendix A.2. We observe that the strong correlation be- tween region count and the generalization gap remains con- sistent in various setups. The consistency indicates that our findings reveal a fundamental characteristic of non-linear neural networks.
7. A Alation Studies
We also provide evaluations by varying the optimizer and hyperplane generation algorithms. The results are deferred to Appendix C.
This section presents an ablation study to validate the ro- bustness and consistency of our findings. We systematically vary key aspects of our experimental setup, including the network architecture, dataset, optimizer, and the method of computing the plane, and evaluate their impact on our
Mixup (Zhang et al., 2017b) is a data augmentation technique that creates training samples
Data Augmentations.
7

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Table 2: Experimental consistency across networks, datasets, and counting methods. We conduct experiments on various types of networks across multiple datasets. We also alter the method calculating the region counts. The results of the correlation indicate that our findings are consistent across different setups.
Dataset
Counting Dimension
Network
CIFAR-10
CIFAR-100
ImageNet
ResNet18
0.98
0.96
0.91
0.96
0.97
0.97
0.96
ResNet34
0.98
0.98
0.82
0.98
0.98
0.98
0.99
VGG19
0.94
0,85
0.78
0.88
0.86
0.84
0.86
MobileNet
0.95
0.95
0.92
0.99
0.99
0.99
0.99
SENe118
0.98
0.85
0.80
0.97
0.97
0.97
0.93
ShuftleNetV2
0.95
0.92
0.92
0.94
0.95
0.95
0.93
EfficientNe(BO
0.98
0.84
0.93
0.99
0.99
0.99
0.98
RegNecX_200MEE
0.98
0.87
0.97
0.98
0.99
0.99
SimpleDLA 0.98
0.94
0.84
0.99
0.99
0.98
0.99
by linearly interpolating pairs of input data and their corre- sponding labels. We train a ResNet-18 model using mixup, with other hyperparameters in Table The plot in Figure illustrates that Mixup induces smoother decision boundaries with smaller region count and has better generalization performance. Random crop and random horizontal flip is another way to enhance the diversity of the training dataset. We apply random crop of size 32x32 32 with padding 4 and random horizontal flip with a probability of 0.5 as data augmentations. As depicted in Figure 7, we observe that compared with mixup, random crop and random flip result in more evident vertical shift in the performance curve.
Impact of Random Crop and Flip
No Augmented
35
Generalization Gap
Aug mented
30
25
20
15
Region Counts
Figure 7: The impact of random crop and random flip. Unlike mixup, data augmentation results in a vertical shift in the performance curve, accompanied by a decrease the number of regions and a more significant enhancement in test accuracy.
Although mixup and random crop affect region count dif- ferently, the correlation between region count and general- ization remains high after applying these data augmentation techniques. Detailed correlation results can be found in Appendix C. We will explore the underlying principles of this experimental phenomenon as a future direction.
8. Conclusions and Future Directions
Impact of Mixup
This paper introduces novel approach to characterizing the implicit bias of neural networks. We study the region counts in the input space and identify its strong correlation with generalization gap in non-linear neural networks. These findings are consistent across various network architectures, datasets, optimizers. Our analysis offers a new perspective to quantify and understand the generalization property and implicit bias of neural networks.
No Mixup
35
Generalization aizaaiizatonnnno Gap
Mixup
30
25
20
15
Our paper suggests several promising directions for future research. Firstly, our analyses of why large learning rate induces small region counts mainly focus simplified setup. The analyses for more general settings remain open. Secondly, extending the definition of region count to non- classification tasks, such as natural language generation, would be a worthwhile direction. Lastly, region count can be leveraged design new architectures or regularization,
3
Region Counts
Figure 6: The impact of mixup. This figure shows that mixup improves the model's generalization ability and re- duces the number of regions in the hyperplane.
8

---

Understanding Nonlinear Implicit Bias via Region Counts in Input Space
that can potentially improve the generalization performance of neural networks.
Cai, J., Nguyen, K.-N., Shrestha, N., Good, A., Tu, R., Yu, X., Zhe, S., and Serra, T.. Getting away with more network pruning: From sparsity to geometry and linear regions. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Re- search, pp. 200-218. Springer, 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chizat, L. and Bach, F. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory, pp. 1305-1338. PMLR, 2020.
References
Cohen, J., Kaur, S., Li, Y., Kolter, J. Z., and Talwalkar, A. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2020.
Ahn, K., Bubeck, S., Chewi, S., Lee, Y. T., Suarez, F,, and Zhang, Y. Learning threshold neurons via edge of stability. Advances in Neural Information Processing Systems, 36, 2024.
Damian, A., Nichani, E., and Lee, J. D. Self-stabilizatiin:: The implicit bias of gradient descent at the edge of stabil- ity. arXiv preprint arXiv: 15594, 2022.
Andriushchenko, M., Croce, F., Müller, M., Hein, M., and Flammarion, N. A modern look the relationship between sharpness and generalization. arXiv preprint arXiv:2302.00011, 2023.
Deng, J., Dong, W., Socher, R., Li, L..J., Li, K., and Fei-Fei, Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-248-22 258.255. Icee. 2009.
Arora, S., Cohen, N.. Hu, W. and Luo, Y. Implicit regular- ization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Foret, P., Kleiner, A., Mobahi, H., and Neyshabur, B. Sharpness-awand aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
Arora, S., Li, Z., and Panigrahi, A. Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning, pp. 948- 1024. PMLR, 2022.
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. Charac- terizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832-1841. PMLR, 2018a.
Bertoin, D., Bolte, J., Gerchinovitz, S., and Pauwels, E.
Numerical influence of (0) on backpropagation. Ad- vances in Neural Information Processing Systems, 34: 468-47 019,479,200 2021.
Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Im- plicit bias of gradient descent on linear convolutional networks. Advances in neural information processing systems, 31, 2018b.
Bianchi, P., Hachem, W., and Schechtman, S. Conver- gence of constant step stochastic gradient descent for non-smooth non-convex functions. Set- Valued and Varia- fional Analysis, 30(3):1 2022.
Hanin, B. and Rolnick. D. Complexity of linear regions in deep networks. In International Conference on Machine Learning, pp. 2596 2604. PMLR, 2019a.
Bolte, J. and Pauwels, E. A mathematical model for au- tomatic differentiation machine learning. Advances in Neural Information Processing Systems, 33:10809- 10819, 2020.
Hanin, B. and Rolnick, D. Deep relu networks have sur- prisingly few activation patterns. Advances in neural information processing systems, 32, 2019h.
Bolte, J. and Pauwels, E. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188: 19-51,, 2021.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Brutzkus, A., Globerson, A., Malach, E., and Shalev- Shwartz, S. SGD learns over- preamearmeter networks that provably generalize on linearly separable data. arXiv preprint arXiv: 10/74, 2017.
Hoffer, E., Hubara, I., and Soudry, D. Train longer, general- ize better: closing the generalization gap in large batch training of neural networks. Advances in neural informa- tion processing systems, 30, 2017.

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Hu, J., Shen, L., and Sun, G. Squeeze-and-excitatio networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 7132-7141, 2018.
Li, Y., Wei, C., and Ma, T. Towards explaining the regu- larization effect of initial large learning rate in training neural networks. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Jacot, A. Implicit bias of large depth networks: a no- tion of rank for nonlinear functions. arXiv preprint arXiv:2209. 15055, 2022.
Lyu, K. and Li, J. Gradient descent maximizes the mar- gin of homogeneous neural networks. arXiv preprint arXiv: htt::/906.r 996600599, 2019.
Jacot, A., Golikov, E., Hongler, C., and Gabriel, F. Feature learning in 2-regularized dnns: Attraction/repulsion and sparsity. Advances in Neural Information Processing Systems, 35:6763-6777 2022.
Lyu, K., Li, Z., Wang, R., and Arora, S. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34: 19978-12991, 2021.
Jastrzkebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. Three factors influencing minima in SGD, arXiv preprint arXiv: (1l1::171100022. 2017.
Ma, N., Zhang, X., Zheng, H.-T., and Sun, J. Shufflenet v2: Practical guidelines for efficient enn architecture design. Proceedings of the European conference on computer vision (ECCV), pp. 116-131, 2018
Ji, Z. and Telgarsky, M. Gradient descent aligns the layers of deep linear networks, arXiv preprint arXiv:1810.02032. 8a.
Montúfar, G., Ren, Y., and Zhang, L.. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618-66) 649, 2022.
Ji, Z. and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:/803.07:00,, 2b.
Nacson, M. S., Srebro, N., and Soudry, D. Stochastic gradi- ent descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3051-3059. PMLR, 2019.
Ji, Z. and Telgarsky, M. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pp. 1772-1798. PMLR, 2019.
Ji, Z. and Telgarsky, M. Directional convergence and align- ment in deep learning. Advances in Neural Information Processing Systems, 33:1716--77186 2020.
Nguyen, Q., Mukkamala, M. C., and Hein, M. Neural networks should be wide enough to learn disconnected decision regions. In International conference on machine learning, pp. 3740-3749 PMLR, 2018.
Jiang, Y., Neyshabur, B., Mobahi, H., Krishnan, D., and Bengio, S. Fantastic generalization measures and where to find them. arXiv preprint drXiv:1912.02178, 2019.
Novak, R., Bahri, Y., Abolañia, D. A., Pennington, J., and Sohl-Dickstein, J. Sensitivity and generalization in neural networks: empirical study, arXiv preprint 2018.
Katz, G., Barrett, C., Dill, D. L.., Julian, K., and Kochender- fer, J. J. Reluplex: An efficient smt solver for verifying deep neural networks. In Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30, pp- 97-117. Springer, 2017.
Ongie, G., Willetr, R., Soudry, D., and Srebro, N. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint N.X.v0990000633, 2019.
Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, T. P. large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04480 2016.
Pesme, S., Pillaud- Vivien, L., and Flammarion, N. Im- plicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity. Advances in Neural Information Processing Systems, 01222218-2230 2021.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Lewkowycz, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.00 022/ 2020.
Radosavovic, I., Kosaraju, R. P., Girshick, R., He, K., and Dollár, P. Designing network design spaces. In Proceed- ings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 00428-10436 2020.
10

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Safran, I., Vardi, G., and Lee, D. On the effective number of linear regions in shallow univariate relu networks: Con- vergence guarantees and implicit bias. Advances in Neu- ral Information Processing Systems, 35:32667-32679, 2022.
Weng, L., Zhang, H., Chen, H., Song, Z., Hsieh, C.-J., Daniel, L., Boning, D., and Dhillon, I. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, Pp. 5276-5285. PMLR, 2018
Sandler, M., Howard, A., Zhu, M., Zhmoginov, A., and Chen, L.-C. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510-4520, 2018.
Wilson, A. C.,, Roelofs, R., Stern, M., Srebro, N., and Recht, B. The marginal value of adaptive gradient methods in machine learning. Advances in neural information processing systems, 30, 2017.
Woodworth, B., Gunasekar, S., Lee, J. D., Moroshko, E., Savarese, P., Golan, I., Soudry, D., and Srebro, N. Ker- nel and rich regimes in overparametrized models. In Conference on Learning Theory, pp. 3635-3673, PMLR, 2020.
Serra, T., Tjandraatmadja, C., and Ramalingam, S. Bound- ing and counting linear regions of deep neural networks. In International conference machine learning, pp- 4558-4566 PMLR, 2018.
Yu, F., Wang, D., Shelhamer, E.,, and Darrell, T. Deep layer aggregation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2403-2412, 2018.
Simonyan, K. and Zisserman, A. Very deep convolu- tional networks for large-scale image recognition. arXiv preprint arXiv:1409) 1199.155 1556, 2014.
Smith, S. L.. Kindermans, P.-.,, Ying, C., and Le. Q. V. Don't ' decay the learning rate, increase the batch size. 2017.
Yun, C., Krishnan, S., and Mobahi, H. A unifying view implicit bias in training linear neural networks. arXiv preprint 2xxx::000000201111 2020.
arXiv preprint
Somepalli, G., Fowl, L., Bansal, A., Yeh-Chiang P., Dar, Y., Baraniuk, R., Goldblum, M., and Goldstein, T. Can neu- ral nets learn the same model twice? investigating repro- ducibility and double descent from the decision boundary perspective. In Proceedings of the ieee/cvf conference computer vision and pattern recognition, pp. 13699- 13708, 2022.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking general- ization, 2017a.
Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D. mixup: Beyond empirical risk minimization. arXiv preprint 1rXivv 2017b.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on sepa- rable data. The Journal of Machine Learning Research, 2881)28222-277, 2018
Sutskever, I., Martens, J., Dahl, G., and Hinton, G. On the importance of initialization and momentum deep learn- ing. In International conference on machine learning, pp. 1139- PMLR, 2013.
Tan, M. and Le. Q. Efficientnet: Rethinking model scal- ing for convolutional neural networks. In International conference machine learning, pp. 6105-6114. PMLR, 2019.
Vaskevicius, T., Kanade, V., and Rebeschini, P. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32, 2019.
Wang, B., Meng, Q. Chen, W., and Liu, T.-Y. The implicit bias for adaptive optimization algorithms on homoge- neous neural networks. In International Conference on Machine Learning, pp. 10849-10858. PMLR, 2021.

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
A. Experiment details
In this section, we provide the detailed experiment settings.
A.1. Details on Architectures and Datasets
We conduct experiments on different neural network architectures, including ResNet18 and ResNer34 (He et al., 2016), EfficientNetBO (Tan & Le. 2019), SENe118 (Hu et al., 2018), VGGI9 (Simonyan & Zisserman, 2014), MobileNetV2 (Sandler al., 2018), ShuffleNetV2 (Ma et al., 2018), RegNet200MF (Radosavovic al., 2020), SimpleDLA (Yu et al., 2018). We conduct all experiments using NVIDIA RTX 6000 graphics card.
We use CIFAR-10/100 (Krizhevsky et al., 2009) and Imagenet-Ik (Deng et al., 2009) as datasets. For CIFAR-10 and CIFAR-100 dataset, each network was trained for 200 epochs using the Stochastic Gradient Descent (SGD) algorithm with cosine learning rate schedule. We choose 27 combinations of hyperparameters in Table 1, and for each hyperparameter we use random seeds and report the average metrics. For the Imagenet- I dataset, each network was trained for 50 epochs with random data crop and random flip. We use the same optimizer and 27 combinations of hyperparameterss as in CIFAR-10 and CIFAR- 100 experiments. is worth noting that we make minor adjustments on hyperparameters for certain networks to ensure stable training. For example, in the case of VGGI9, the training is unable converge when the learning rate is 0.1; therefore, adjust it to 0.05.
A.2. Correlation Plots
We show the correlation plot of average regions and test accuracy in Figure 8. The figure consists of results from training different networks on CIFAR-10 10 dataset with SGD for 200 epochs, using the hyperparameters specified in Table 1. The results show that different networks have different number of regions, ranging from 2 to 20. However, the correlation of test accuracy and average number of regions are consistently high in all the networks.
B. How to Calculate the Number of Regions
In this section, we study different methods to calculate the region count, and discuss their impact on the results. Since it is impossible in practice calculate the predictions of an infinite number of data points the hyperplane, we select grid points from the hyperplane to calculate the region count.
Assume we have divided a region of the hyperplane into several equidistant small squares. We can use an algorithm similar to breadth-first search to calculate the number of connected components within these small squares, thereby determining the number of regions. Here, we use 2-dimensional hyperplane as an example (the I-dimensional case can be considered a degenerate version of this algorithm). The algorithm for calculating the number of regions in this setup given in Algorithm 1.
Therefore, it is necessary to determine the granularity of splits for the plane. We experimented with different setups of splitting parameters, and the results averaged by 100 independent trials are presented in Table 3. From the results, using 200 grid points in the ID case and 30x30 grid points in the 2D case is an optimal choice. Splitting the plane into fewer points results in an inadequate approximation of regions, while increasing the number of points does not significantly enhance accuracy but incurs greater computational costs. Therefore, in our experiments, we split the plane into 200 grid points for the 1D case and 30x30 grid points for the 2D case.
Table 3: The mean value of region counts with different splitting numbers in Id (left) and 2d (right) planes.
Splitting Numbers
Region Counts
Spliting Numbers
Region Counts
50
2.74
10x 10
2.76
100
2.76
20x
2.76
200
2.78
30x30
2.78
300
2.78
40x40
2.78
500
2.78
50x50
2.78
Subsequently, we study the number of random samples in calculating the average number of regions. We experiment with different numbers of hyperplanes, and the results are presented in Table From the results, we know that using 100 samples
12

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Correlation of Resnet18 0.98
Correlation of Resnet34 0.98
Correlation of EfficientNetBO 0.98
40
Generalization Gap
Generalization Gap
Generalization Gap
50
30
30
'st
25
40
20
15
20
3
4
5
Region Counts
Region Counts
Region Counts
Correlation of VGG19. 0.94
Correlation of MobileNet 0.95
Correlation of RegNetX 200MF
0.98
60
50
Generalization Gap
Generalization Gap
Generalization Gap
30
40
40
30
20
30
20
3
10
15
20
5
10
Region Counts
Region Counts
Region Counts
Correlation of SENet18 0.98
Correlation of ShuffleNetV2 0.95
Correlation of SimpleDLA 0.98
35
Generalization Gap
Generalization Gap
Generalization Gap
40
25
30
20
20
3.0
3.5
4.0
10
15
6
8
Region Counts
Region Counts
Region Counts
Figure 8: The correlation plot of all networks between average regions and test accuracy for CIFAR-10 dataset with optimizer SGD. From the graph we know that the correlations all very high for different non-linear networks. Different structures of neural networks incur different scope of the average regions.
to calculate the average provides a reliable answer with relatively low computational costs. Therefore, in the experiments we randomly generate 100 lines or planes and calculate the average number regions.
In our paper we use the convex hull of two points {aæ (1 -1-a0 ax22) to calculate the region counts in ID case with E [0, We also conduct ablation studies with varied coordinate ranges a. We train ResNet18 CIFAR10 using hyperparameter in Table in manuscript, where vary the range of and analyze the correlation. The results shown in Table 5. These studies confirm that expanding the range does not influence the strong correlation between region counts and test accuracy.
Table The impact of interpolation range on region counts.
The range of
Region Counts
Correlation
3.56
0.98
- 1,
4.47
0.96
- 2
5.86
0,92
3,4]
6.39
0.93
13

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Algorithm I Calculate the Number of Region
Input: Prediction Matrix P with dimension(us, h).
Output: Number of connected regions N.
1: Initialize mark matrix M zero matrix, with the same dimensions P
2: Initialize count of connected regions N +-
3: for i + 0 to w 1 do
4: for j <- 0 to do
5: [+]]] is already marked then
6: continue
7: end if
8: Mark position (i.5) in M visited
9:
Perform Breadth-First Search (BFS) starting from position (i,j)
10: In BFS, enqueue all neighboring points that have the same value as (i, in P and mark them as visited in M
11:
Continue BFS until the queue is empty
12: Increment count connected regions N - +1
end for
end for return N
15:
Table The mean value of region counts with different number of random samples.
Number of Samples
Region Counts
2.24
50
2.56
100
2.78
300
2.80
2.79
C. More ablation studies
Gradient Optimizers. We calculate the region count of models trained by different optimizers, including SGD, Adam, and Adagrad. The correlation between region count and the generalization gap consistent for them, detailed in Table 6.
Table 6: The impact of optimizers on the correlation between region counts and generalization gap.
Optimizer
SGD
Adam
Adagrad
Network
ResNet18
0.98
0.92
0.96
ResNet34
0.98
0.92
0.91
VGG19
0.94
0.92
0.87
MobileNet
0.95
0.95
SENe118
0.98
0.78
0.91
ShufflcNetV2
0.95
0.83
0.99
EfficientNetBO
0.98
0.97
0.99
BegNetX_2000M
0.98
0.95
SimpleDLA
0.98
0.95
0.88
Hyperplane Generation Methods. We explore the effects of different methods for generating the hyperplane in the input space. In the main experiments, we generate 1-dimensional plane using random pairs of samples from the training set and calculated the number of distinct regions between them. In this section, we apply various techniques for plane generation: selecting two data points from the test set, choosing one data point from the training set and extending direction by a fixed length. We calculate the number of regions for each of these setups. The results in Table are consistent across different hyperplane computational approaches.
a random
14

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
Table 7: The impact of calculation methods on the correlation between region counts and generalization gap.
Counting
Test
Train
Random
Network
R8
0.98
0,98
0,98
ResNet34
0.98
0.96
0.94
VGG19
0.94
0.89
0.78
MobileNet
0.95
0.94
0.88
SENe118
0.98
0.96
0,99
ShuffleNetV2
0,95
0,95
0,92
EfficientNelBO
0,98
0.98
0.92
RegNetX 200MF
0,98
0.97
0.92
SimpleDLA
0.98
0.97
0.96
Data Augmentations. Here, we present the correlation curves after applying mixup and random crop. The results show that the correlation between region count and generalization gap remains high after using these data augmentation techniques.
Correlation Mixup: 0.97
Correlation Random Crop and Flip: 0.96
Generalizatio alization Gap
Seneralization Gap
20
18
341
14
2.4
2.6
2.8
3.0
3.2
2.6
2.8
3.0
Region Counts
Region Counts
Figure The correlation graph after using data augmentation techniques. train Resnet18 on CIFAR-10 dataset, varying the hyperparameters in Table Our findings reveal that the correlation between region count and generalization gap remains high after using these techniques.
D. Proof
This section contains the proof of the theorem in this paper.
We first prove two lemmas.
Lemma 6.4. The region counts between pair of data points is upper-bounded by the number of active neurons. For two imputs Bas Tb. we have
R(xa, Tb, W) S (x W) + (xs, W) +
Proof. If R(x,, Tb, W) < 2, then the equation naturally holds. Next we consider R(Eas Ib, W) > 2. From the definition of region count, one can find R = R(Ia. Po. W) points on the line segment between and Tb, such that the neural network gives different predictions. Denote these points as T1, ... ,n We have
Jw (w( (B <0
Consider ã., 8, 8.42. Since the neural network gives alternating predictions these three points, it is nonlinear and has activation sign changes the line segment connecting them. Therefore, we can find 1 nx(1) S p. such that (w, (wT(1) (w ( (++2) < 0.
prove by contradiction. If for all < S p. such that (w) a.) T+42) 2 Suppose #+11 = AĀ; + (1 A) 2)5.42
15

---

Understanding Nonlincar Implicit Bias via Region Counts in Input Space
then have
fw( Σ aw 2(+1)
Σ a. (u; 2i) + ( xx42)
==1
(G:) + A)Jw((i+2)
Therefore fw (#1+1) has the same sign of fw (ū,) and fw (ā,42), contradict with the condition that they have alternative signs. So we can find 1 S n(i)= S p. such that (w (x) 2242 0.
Since w ( is linear x, this implies that
(w (1) (w) (z)) O.
We also prove by contradiction. they have the same sign then the convex combination of them have the same sign so (1) (w)) 22+2) 2
We have the following two observations about n(i). Firstly, we can choose an n(i) such that ( n(g
T Ti42 and fw (T++2 have the same sign, since there exists at least one such neuron that contributes to the sign change of fw. This implies that ni)) A níi + 1), since fw (Z;) have alternating signs. Secondly, since w (1 is a linear function in æ, can only changes sign for at most one time. This implies that n(i) * n(j) jf - i 2. Putting them together, we know that nii) o n(j) for i * j.
2, we have (w) Ta) (w (w xb) < Therefore, there exists neurons that are activated for either Fa or zg. This gives (Ir, W) - ( W) 2 R 2, 2, which completes the proof.
Recall that for each S
Lemma 6.5. The sharpness of a neural network is lower-bounded by the number of active neurons:
Amax (VW)(W))
Na W).
Proof. The Hessian of I(W, x. y) can be expressed as
Tolo
(W,l
where 1; = a,o'(w,Tx)) x)x. Suppose V = [vT, ... 1 As the nonzero eigenvalue of TTV and VVT is the same, this implies that
Amaxx Vir v)) Amax (VV
d' (w]x))<<11" 2 Σ dw x)r²
From the definition of L(W) and the positive definiteness of Hessian matrices, know that
Amax (Vi L(W))
Amax
Σ
VvillW,,,,90
Amax (W,,
N
Plug in the previous caleulation and use the definition of N(x),, we have
P
2
Amax (VW)LWW))
d (w. x.y)
N( W).
N2
==
16

---

Understanding Nonlinear Implicit Bias via Region Counts in Input Space
Proof of Theoorm 6.3. Theorem 6.3 is direct consequence of Assumption 6.2 and the following lemmas.
N
Ex,x (R(x, X" Wil
R( 22, W,)
N
(2 WT) + (I,, WT) +2)
2
N
(N WT) +1)
N
1=1
2N
Amaax L(W))(W)) +2
p2
N
222)
17


Reviews:
[{"review_id": "YMdfveiGde", "reviewer": "Reviewer_iwjY", "summary": "The authors propose using low-dimension region counts as a proxy for the generalization performance. They empirically test the correlation between region count and generalization performance, and provide a bound on the region count for two layer ReLU neural networks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n>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.\n\n**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**. \n\nWe 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:\n\n|Proxy|Correlation|\n|:----:|:----:|\n|Frobenious Norm|0.64|\n|Margin|0.02|\n|Margin/Frobenious Norm|-0.18|\n|Spectral Norm|0.77|\n|PB-I|-0.35|\n|PB-O|-0.31|\n|PB-M-I|0.79|\n|PB-M-O|0.78|\n|Region Count|**0.98**|\n\nThe 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.\n\n>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.\n\n**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.\n\nAlso, 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. \n\nFinally, 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.\n\n**Reference**\n\n[1] Jiang, Yiding, et al. \"Fantastic generalization measures and where to find them.\" arXiv preprint arXiv:1912.02178 (2019).\n\n[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).\n\n[3] Keskar, Nitish Shirish, et al. \"On large-batch training for deep learning: Generalization gap and sharp minima.\" arXiv preprint arXiv:1609.04836 (2016).\n\n[4] Neyshabur, Behnam, et al. \"Exploring generalization in deep learning.\" Advances in neural information processing systems 30 (2017).\n\n[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).", "claims_and_evidence": "The claims are not adequately supported by the evidence. 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.\n\nThe 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.", "methods_and_evaluation_criteria": "The evaluation criteria for how good region count would make more sense if it was compared to other possible methods, but as it stands it is not possible to evaluate whether region count is an appropriate proxy.", "theoretical_claims": "I did a cursory check for correctness and did not see any issues.", "experimental_designs_or_analyses": "See previous sections.", "relation_to_broader_scientific_literature": "This paper builds on a large prior literature investigating generalization.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The authors propose an interesting proxy for generalization performance which has potential. However, they do not provide adequate evidence for its effectiveness.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. What is the correlation between generalization performance and other potential proxies? For example: norm, margin, and number of GD iterations (this is not an exhaustive list).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "onJXcktemC", "reviewer": "Reviewer_VXuC", "summary": "In this work, authors propose region count as a metric to quantify implicit bias / generalizability of neural networks. A region is defined as a set of input points which are classified in the same way by the network; authors show that fewer regions lead to increased generalizability (quantified as gap between test error and train error). They empirically show that the number of regions exhibits a high correlation with the generalizability in a number of convolutional architectures.\n\n## Update after rebuttal\n\nAfter reading the author's comments and other reviewers' comments, I maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We address the main concerns below:\n\n>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?\n\n**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.\n\nAdditionally, 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:\n\n|Hyperparameters|Value|\n|:----:|:----:|\n|Depth|$3,4\\cdots, 17$|\n|Criterions|gini, entropy|\n|Splitter|best,random|\n\nThe 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.\n\n\n>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?\n\n**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.\n\nWhile 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:\n\n|Epoch|Correlation|\n|:----:|:----:|\n|10|-0.07|\n|20|0.24|\n|30|0.92|\n|40|0.95|\n|60|0.97|\n|80|0.96|\n|100|0.97|\n|200|0.98|\n\nThe 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.\n\n\n>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]? \n\n**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.\n\nWe 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.\n\n**Reference**\n\n[1] Dufumier, Benoit, et al. \"Integrating prior knowledge in contrastive learning with kernel.\" International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "- The main claim of this work is that the number of regions is correlated with the generalizability of the model \n\n- The evidence is convincing, and it indeed seems that better performing models tend to have fewer regions\n\n- This work may also provide theoretical justification as to why higher learning rate and smaller batch size can work well in practice", "methods_and_evaluation_criteria": "- I think the setup of the paper is rigorous and the evaluation criteria are satisfactory", "theoretical_claims": "- While I did not carefully check the details of the proofs in the appendix, I am convinced by the correctness of the presented analysis in the main text.", "experimental_designs_or_analyses": "I believe the experimental design is convincing. 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? I think this may be interesting to analyze also to derive potential regularization terms aimed at enforcing low region count [see below]", "relation_to_broader_scientific_literature": "I believe this work can potentially have a significant impact on the deep learning field in general.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- The work is clearly presented and understandable even if theoretical\n\n- I believe the experimental validation is done correctly, as it is often lacking in more theoretical works\n\n- Some empirical results are missing on the lower end of the generalization spectrum. As stated above, I think it would be interesting to see whether this correlation exists also in those cases", "other_comments_or_suggestions": "I think this work is very interesting and can have significant impact, thus may be considered for acceptance. I have some questions about its potential applications [see below]", "questions_for_authors": "- 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? Perhaps with some regularization term. 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? \n\n- 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? I would like to hear the author's thoughts about this. For this topic, I would suggest this work [1] which reminds of the connectedness property in your work \n\n[1] https://proceedings.mlr.press/v202/dufumier23a/dufumier23a.pdf", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jMkpM3mnbX", "reviewer": "Reviewer_aEL2", "summary": "This paper introduces the notion of connected region count in the input space and shows that it is strongly correlated with the generalization gap. Moreover, it is noted that larger learning rates and smaller batch sizes can lead to smaller region counts. Theoretically, It is proved that for a two-layer ReLU network under the edge-of-stability assumption, the average region count is bounded by O(1/learning rate).\n\n## update after rebuttal\n\nThanks for your response! I will keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and constructive suggestions. In the following, we address the main concern raised. Please find the details below. \n\n>Q1: It would be nice if more datasets and architectures can be analyzed.\n\n**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:\n\n|Hyperparameters|Value|\n|:---:|:----:|\n|Learning rate|1e-4,5e-5,1e-5|\n|Batch size|256,512,1024|\n|Weight decay|1e-5,1e-6,1e-7|\n\nThe 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.\n\n>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?\n\n**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.\n\nWe 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:\n\n|Network|Correlation|\n|:----:|:----:|\n|Resnet18|0.93|\n|Resnet34|0.95|\n|EfficientNetB0|0.87|\n|SimpleDLA|0.82|\n\nThe results confirm that the correlation remains strong, demonstrating that our method does not require selecting two training examples as endpoints.\n\nFinally, 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. \n\n**References**\n\n[1] Dosovitskiy, Alexey, et al. \"An image is worth 16x16 words: Transformers for image recognition at scale.\" arXiv preprint arXiv:2010.11929 (2020).", "claims_and_evidence": "The claims are well-supported in general; see more discussion below on the empirical results.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I didn't check the proofs.", "experimental_designs_or_analyses": "The empirical results look convincing overall: CIFAR-10, CIFAR-100 and ImageNet are tried, and multiple network architectures are tested. Data augmentation techniques such as mixup are also analyzed. One concern is that the discussion is focused on vision datasets and convolutional networks; it would be nice if more datasets and architectures can be analyzed.", "relation_to_broader_scientific_literature": "This paper introduces the notion of connected region count and shows that it is strongly correlated with the generalization gap. As far as I know no prior work has shown the relationship between region count and generalization, so I believe this is a nice contribution.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dX8MLOEd1L", "reviewer": "Reviewer_4je8", "summary": "The paper proposes a new region count metric for characterizing neural networks' implicit biases. This metric counts the number of connected regions in the input space with the same predicted label in a low-dimensional subspace. One of the advantages of this output-based metric over parameter-based metrics, such as sharpness and margins, is parametrization-independence. The authors empirically demonstrate that this metric strongly correlates with the generalization gap over a variety of convolutional architectures, datasets, and hyperparameters, making it suitable for the generalization analysis. Then, the authors experimentally show that region count decreases with an increased learning rate and a smaller batch size. The authors suggest a theoretical explanation for the learning rate behavior based on the edge of stability property of gradient-based algorithms.\n\n## update after rebuttal\n\nI will keep my current evaluation. The authors' feedback was useful, but it did not completely clarify my concerns expressed in my Rebuttal Comment.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent on reviewing our work and for the very detailed comments. Please find the details below. \n\n>Q1: How to use the region count metric for regularization? \n\n**A1:**  Due to the word limit, we respectully refer the reviewer to Reviewer VXuC's response A2.\n\n>Q2: How to extend the theorem to multi-dimensional region counts?\n\n**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.\n\n>Q3: For which types of analysis is the parametrization-independence of your metric important?\n\n**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.\n\n>Q4: Conduct experiments to find whether region count can distinguish between \"very good\" and \"good\" models.\n\n**A4:** We fixed the learning rate at 0.1 and batch size at 256, and varied only the weight decay to compute the correlation. \n|Parameter|Value|\n|:----:|:----:|\n|Weight Decay|5e-4,1e-4,5e-5,1e-5,5e-6,1e-6,5e-7,1e-7|\n\nThe 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.\n\n\n>Q5: Clarify the hyperparameters for which your metric is well-suited/ill-suited.\n\n**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.\n\n>Q6: Reporting rank-correlation. \n\n**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:\n|Network|Correlation|\n|:----:|:----:|\n|Resnet18|0.95|\n|Resnet34|0.94|\n|VGG19|0.74|\n|MobileNet|0.98|\n|SENet18|0.96|\n|ShuffleNetV2|0.99|\n|EfficientNetB0|0.97|\n|RegNetX 200MF|0.98|\n|SimpleDLA|0.86|\n\nThese results show consistently high rank correlation, further validating the effectiveness of our metric.\n\n>Q7: Do regression analysis where the generalization gap is regressed on all metrics. \n\n**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:\n|Measure|$R^2$|\n|:----:|:----:|\n|All|**0.96**|\n|Margin|0.41|\n|Normalized Margin|0.03|\n|Sharpness|0.61|\n|1d Region Count|0.94|\n|2d Region Count|0.92|\n\nBoth 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.\n\n>Q8: Discuss the paper [1][2].\n\n**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.\n\nWe thank the reviewer once again for the valuable suggestions. \n\n**References**\n\n[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).\n\n[2] Lewkowycz, Aitor, et al. \"The large learning rate phase of deep learning: the catapult mechanism.\" arXiv preprint arXiv:2003.02218 (2020).\n\n[3] Kendall, Maurice G. \"A new measure of rank correlation.\" Biometrika 30.1-2 (1938): 81-93.", "claims_and_evidence": "1. While the authors claim that their low-dimensional subspace region count metric is more computationally efficient than the whole space region count metric, I still feel that the region count metric is hard to analyze. For instance, while the sharpness metric directly motivates possible regularization methods, such as sharpness-aware minimization, I do not easily see how to use the region count metric for computationally efficient regularization. Moreover, while the authors manage to analyze the 1D-version region counts theoretically, I do not see how to extend this analysis to multi-dimensional region counts.\n2. Parametrization independence is indeed one of the main properties of the region count metric. However, I think the authors should also discuss situations where parametrization independence is indeed important. As I see it, the main advantage of parametrization-independent metrics is the ability to predict generalization performance conditional only on the final model and training data. At the same time, parametrization-dependent metrics might also potentially predict generalization performance, but they require more information, e.g., the final model, training samples, and optimizer hyper-parameters. In this sense, one could argue that parametrization-independent metrics are better suited for the generalization analysis. However, for me, it is not clear which metric is better suited for the design of regularizers since the effect of regularizers implicitly depends on all training hyper-parameters.\n3. The high correlation with the generalization gap is a strong piece of evidence of the region counts metric usefulness. However, I see two potential problems with this finding.\n    * First, from what I see, the dependence between the region counts and the generalization gap is non-linear. Specifically, the slope is increasing for the smaller region counts. Thus, the \"outlier\" models with a big generalization gap could cause a high correlation coefficient. If this is the case, the region counts metric could only distinguish between \"very good\" and \"very bad\" models but could not distinguish between \"very good\" and \"good\" models. Therefore, it could be interesting to conduct some experiments across \"good\" models, for example, in a situation where the learning rate and batch size are fixed, and weight decay is varied over a relatively tight range of values.\n    * Second, the results for augmentations show that the relation between the region counts and the generalization gap significantly depends on the training algorithm. This fact limits the applicability of the region counts metric for the generalization analysis since it suggests that the region count metric is ill-suited for analyzing how the introduction of augmentations affects generalization performance.", "methods_and_evaluation_criteria": "The proposed evaluation is comprehensive. However, the authors should clarify that they only test convolutional architectures on vision datasets.", "theoretical_claims": "Theoretical claims seem correct.", "experimental_designs_or_analyses": "The experimental design seems correct. I have minor comments. Given that the relation between the region counts metric and the generalization gap could be non-linear, it could be worth also reporting rank-correlation. Additionally, I would be interested in the regression analysis where the generalization gap is regressed on all discussed implicit bias metrics: sharpness, margins, normalized margins, 1D region counts, and 2D region counts. It would be interesting to compare the explanatory power of these metrics in terms of $R^2$.", "relation_to_broader_scientific_literature": "The paper is directly related to the deep network generalization literature. Specifically, the authors propose a new non-linearity-aware metric that could be useful for analyzing the generalization gap.", "essential_references_not_discussed": "I think all essential references are mentioned. However, I would like to see more comparisons with the literature on large learning rates. Specifically, I would like the authors to discuss the differences in mechanisms considered in their paper in the papers by Li et al. (2019) and Lewkowycz et al. (2020).\n\n**References**\n\nLi, Y., Wei, C., & Ma, T. (2019). Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in neural information processing systems, 32.\n\nLewkowycz, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., & Gur-Ari, G. (2020). The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218.", "other_strengths_and_weaknesses": "I think the paper is well-written, and the proofs are presented clearly. The proposed metric seems original, but it was inspired by the previous studies of activation patterns.", "other_comments_or_suggestions": "I do not have any.", "questions_for_authors": "1. Could you clarify the types of hyperparameters for which your metric is well-suited (e.g., learning rate) and ill-suited (e.g., augmentations)?\n2. For which types of analysis or applications is the parametrization-independence of your metric important?\n3. Do you think that your metric is well-suited for both big and small generalization gaps? What are the limitations of your metric?\n4. Can you give a practical application of your metric (e.g., for the design of regularizers)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies implicit bias by counting decision regions over subspaces in the input space. While a previous work by Somepalli et al. (2022) already counted decision regions over truncated planes (i.e., truncated two-dimensional subspaces), the current submission includes new contributions such as 
* a theoretical analysis of the decision region count over one-dimensional subspaces;
* an empirical analysis of the dependency of decision region count on the learning rate and batch size;
* empirical counting of decision regions on subspaces of dimension other than two.

These provide *sufficient novelty and significance to this submission*. 

Nevertheless, the submitted paper misses the important reference to the paper by Somepalli et al. (2022) that was the first to propose the idea of empirically analyzing deep networks based on counting decision regions on subspaces of the input space, and exemplifying its relation to generalization and double descent. In the work by Somepalli et al., the decision regions are counted on truncated planes defined by triplets of training samples. They defined a fragmentation score, which is the average number of decision regions over many planes, and showed it for a varying width of ResNet-18 and with respect to the generalization performance in terms of test error. Moreover, their paper used the decision regions over the planes to show the implicit bias of various deep network architectures. 

In an AC-Authors discussion during the rebuttal phase, the authors acknowledged the importance of the missing reference to the paper by Somepalli et al. and agreed to revise their paper accordingly. This issue was considered also in the AC-Reviewers discussion. 

Therefore, based on reading the paper, the reviews, the author rebuttal and following discussions, the recommendation is to Accept this paper *conditioned* on 
* adding a detailed discussion in the related work section that explains how the current paper extends the previous work by Somepalli et al.;
* revising the following places in the text to at least mention and cite the paper by Somepalli et al. and not giving the impression that the current paper is the first to count decision regions over subspaces:
    - Line 042, right: "Our research identifies a metric called region count..."

    - Line 088, left: "We introduce a novel measure..."
    - Lines 157-160, right: "Our motivation can be summarized by a simple idea..."
    - Lines 189-192, right: "we propose a computationally efficient surrogate by calculating the region counts on low dimensional subspace spanned by training data points."


Reference: 

Somepalli et al., "Can Neural Nets Learn the Same Model Twice? Investigating Reproducibility and Double Descent From the Decision Boundary Perspective", CVPR 2022.
Decision: Accept (poster)