Deep Network Partition Density Exhibits Double Descent

• The biggest weakness in the paper seems to be that a critical part of it is missing. The experimental setup in section 4.1 states

We control the size of the local neighborhood by controlling the diagonal lengths via the $r$ parameter mentioned in section 3.2

But section 3.2 makes no mention of a parameter $r$, and it is difficult to make a full evaluation of the experiments in section 4 absent a definition of $r$.

• There is a line of prior work that seems closely related to the authors' own proposed work, which is the idea of polytope lenses by Black et al.. Briefly, this work attempts to look at polysemy of neurons by using ideas from casting neural networks as compositions of splines, though they are chiefly interested in interpretation rather than complexity. I think this paper would be made stronger by contrasting the ideas in Black et al to this work's own, by showing the benefit of viewing DNs as splines has multiple uses.

• The lack of a need for labels makes this measure ripe for helping to help explain the effects of self-supervised learning. I'm a bit surprised that the authors don't include experiments for why (e.g) BYOL can work by measuring the local complexity of teacher & student networks as they train, and iteratively replace each other.

• This is a minor point, but it would be helpful for the authors to spend a few words about why the cost of computing the $P$ orthonormal basis vectors for each $x$ either isn't prohibitive, or why it might be in certain cases.

• Re-reading section 3.1, I'm surprised to see no characterization of the properties of $[\mathbf{v}_1, \dots, \mathbf{v}_P]$ other than they form an orthonormal set, and that $x$ is within $conv(\mathbf{V})$. This latter point is implied but not stated. Maybe 3.1 could do with some more care in specifying the relation between $\mathbf{x}$ and $\mathbf{V}$?

Other minor points:

• italicized sentence at the end of the second paragraph of the introduction has some typos. But it's compelling!
• If this sampling procedure is for each sample input, it’s going to become really expensive computationally. How do they compute a succession of P orthonormal vectors, is this by Gram-Schmidt (or similar procedure?). Is there any way to amortize this complexity? I think it would help make this measure more practically helpful

Overall, I think that this paper has a number of significant shortcomings. To summarize, I think

1. the motivation is weak
2. the authors dodge the hard central research question of how to make the continuous piecewise affine (CPA) operator perspective useful at scale
3. the method is not well explained and is based on an approximation that, to the best of my ability to discern, goes untested
4. the experiments are too simple (e.g, 1k samples from MNIST) or odd (e.g., training MNIST for 100K training steps, which is massive overkill, or changing how the MNIST targets are encoded to induce grokking)
5. the experimental results are messy and at times unclear, with dubious connection to double descent

In detail:

Motivation

No other statistics about the DN has been found to be as informative as the loss func- tion

I think this claim is untrue. My understanding is that there is work in the deep kernel literature in both lazy learning and feature learning regimes, e.g., [1, 2] and mechanistic interpretability literature, e.g., [3, 4] about studying DN learning dynamics using more granular statistics than the loss function.

If the authors do wish to advocate for a CPA perspective, which is valid, they should make a case of (1) what properties we want deep network learning statistics to reveal, (2) why other existing approaches are better and (3) why CPA is the right way to go. But I don't see this, and thus I am left wondering "Sure, we can take a CPA approach, but what are we looking for that we don't already have and that CPA can provide?"

[1] Bordelon, Canatar & Pehlevan ICML 2022. Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks.

[2] Bordelon & Pehlevan NeurIPS 2022. Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networks.

[3] Nanda, et al. ICLR 2023. Progress measures for grokking via mechanistic interpretability.

[4] Liu, Kitouni, Nolte, Michaud, Tegmark, Williams. NeurIPS 2022. Towards Understanding Grokking: An Effective Theory of Representation Learning

In this study, we provide a novel statistic that measures the underlying DN’s local complexity, exhibiting two key benefits: [...] (ii) it is informative about the training loss and accuracy dynamics.

Previous work gave loss error bounds as a function of the number of non-overlapping regions in continuous piecewise affine operators in DN [1] and studied their performance empirically, so this manuscript’s second main claim (that changing local complexity results in changing loss and changing accuracy) seems unsurprising.

At a minimum, I would recommend the authors cite [1]. I also happened to attend a talk by the first author of [1] and Professor Shai Ben-David in the audience said that the authors of [1] were ignoring significant amounts of prior work from the 80s-2000s; while I myself don’t know the correct citations, I suspect that the authors of this manuscript might also want to do an older literature search. (Note: I am unaffiliated with [1] and with Professor Ben-David.)

I should also note that this manuscript’s Fig 2 almost exactly matches [1]’s Fig 1b.

[1] Ji, Pascanu, Hjelm, Lakshminarayanan, Vedaldi CoLLAs 2022. Test Sample Accuracy Scales with Training Sample Density in Neural Networks.

In fact, our development will heavily rely on the affine spline formulation of DNs Balestriero & Baraniuk (2018). Such formulation is exact for a wide class of DNs which naturally arise [...] nonlinearities such as max-pooling, (leaky-)ReLU.

I might be mistaken, but does the CPA perspective apply to more modern nonlinearities? Balestriero and Baraniuk 2018 studied ReLU, Leaky ReLu and absolute value, but many modern models use newer nonlinearities like GeLU and SwiGLU, used in ViT and LLMs e.g. Llama 2. I guess my question is: to what extent is CPA applicable only to certain classes of nonlinearities?

Method

Moving to deep layers involve a recursive subdivision Balestriero et al. (2019) that goes beyond the scope of our study.

My understanding is the key reason why the CPA perspective has struggled is because of the combinatorial complexity. Waving this aside amounts to waving aside the key research challenge with CPAs.

Equation 3

What is the notation $\partial \Omega$? Is equation 3 a definition?

The key insight we will leverage however is that the number of sign changes in the layer’s pre-activations is a proxy for counting the number of regions in the partition. To see that, notice how input space samples who share the exact same pre-activation sign effectively lie within the same region ω ∈ Ω and thus the DN will be the same affine mapping (since none of the activation functions vary). Therefore for a single layer, the local complexity for a sample in the input space can be approximated by the number of hyperplanes that intersect a given neighborhood V which is itself measure by the number of sign changes in the pre-activations that occur within that neighborhood.

I think this is a key point that should be explained in more detail, with examples and/or figures and/or equations.

Also, doubling back to my question, I’m unsure of whether the insight still holds with depth. One would imagine that multiple regions at layer $i$ might be mapped to the same region at layer $i+1$ or $i+2$.

Note that for deeper layers, our complexity measure is actually computing the number of hyperplane intersections with the convex hull of the embedded vertices instead of the convex hull of the vertices in the input space.

This comment is somewhat concerning. This comment suggests that the quantity one desires (the convex hull of the vertices in input space) has subtly shifted to a different quantity (the convex hull of the embedded vertices) and how these two are related (if at all) is not analyzed, discussed or explored mathematically or empirically.

We control the size of the local neighborhood by controlling the diagonal lengths via the r parameter mentioned in section 3.2.

I cannot identify an $r$ parameter in Section 3.2, and this $r$ parameter seems to be important for subsequent experiments.

Experiments

Before delving into the experiment, the proposed approximation (Section 3.1 & 3.2) is not yet validated. One would first want to know: how well does this method approximate the full (and extremely expensive) partition computation? How many orthogonal vectors are necessary to get a good approximation, and how does this depend on the data, architecture, and other implementation choices? What effect does the parameter $r$ have? As best as I can tell, there is no answer to these questions.

The closest answer I can find is Section 3.3, which compares this method against SplineCAM in 1 architecture (depth 3 width 200 MLP) on 500 MNIST samples. This feels inadequate to me for two reasons:

1. I want a comparison to an exact baseline. But whether SplineCAM is exact is unclear. The authors call SplineCAM both an approximation (“with the local partition density approximated via SplineCAM”) and exact (“SplineCAM is an exact computation method”). SplineCAM also appears to be limited (“SplineCAM can only be used to compute the local complexity for 2D neighborhoods”), which an exact method should not be.
2. Even if SplineCAM is exact, I see no characterization of how the number of orthogonal dimensions, or $r$, or architecture, or dataset plays a role.

Consequently, I am left with no understanding of how good this approximation is or under what conditions the approximation is good. This makes me skeptical of the subsequent experimental results.

We perform experiments on MNIST with fully connected DNs and on CIFAR10 with CNN and Resnet architectures

Despite this claim, it appears to me that _most) of the experiments focus on a subset of 1k data from MNIST (Figures 1, 3, 6, 7, 8, 9, 10). The CIFAR experiments, while fewer and less prominent, are performed on 2.5k data. In 2023, such small networks trained on such simple data feels too inadequate. Moreover, the training diets seem bizarre. Most of the models appear to display high plateau accuracy within ~100 optimization optimization steps, but training continues till 100000 training steps without motivation or explanation. Models are known to exhibit strange behaviors with such long training diets (e.g., neural collapse) so I am skeptical that we should be studying networks in such late atypical stages. I personally have never seen anyone train MNIST to 100k gradient steps unless they're looking for atypical model behavior.

For the MNIST and CIFAR10 experiments with fully connected and convolutional networks, we use p = 25 as the dimensionality of the hypercubes that define the neighborhood.

I don’t know why p=25 was chosen, and it would be good to see some sensitivity analysis to how much $p$ affects the results.

As depicted in the top-right figure, the amount of region near training samples follow a double descent curve ultimately falling until training is stopped

There are two oddities with the Figure 1 result.

1. Double descent is almost always observed as a function of parameters to data, not optimization steps.
2. The train loss peaks, even though double descent is characterized by the test loss peaking.

Now, perhaps the authors do not mean “double descent” in the way that is commonly used. If so, I would urge them to avoid such terminology. But if not, this needs clarification.

For all the depths, the accuracy on both the train and test sets peak during the first descent phase.

Given that train and test accuracy plateau seemingly within ~10 gradient steps, I am confused why the models are trained to 100,000 gradient steps. Moreover, most fluctuations and interesting patterns of LC occur beyond ~100 gradient steps (typically past the point that accuracy has saturated), leading me to be skeptical why we are looking at such extremely late training dynamics.

Figure 3:

Why is the training LNL so spikey but the test LNL so smooth?

Figure 4: Effect of Batch Normalization on Double Descent

I see no divergence of the test loss near an interpolation threshold. What does this have to do with double descent? And again, double descent is a phenomenon typically described with data to parameters, not gradient steps.

Minor:

“ As such, as pose the following question,”

Add a subject to this sentence e.g., “As such, we pose the following question,”

which naturally arise form the

“form” should be “from”

1. While I appreciate the main double descent observation and some of the experimental findings supporting it, I find the extent of daylight between this work and some of the published results a weakness. The paper does acknowledge clearly that the development will rely on the affine spline. This is not a problem, but except the double descent observation, much of the development described here veers too close to the splinecam paper at CVPR 2023. It is not obvious whether to view this paper as an empirical evaluation of the splinecam work in the context of double descent. Even several figures from that work appear in this submission directly.

2. If the technical adjustments and modifications to the splinecam work are significant, it would be desirable to identify this more explicitly in the text to help the readers assess the distinction clearly.

3. In the absence of new theoretical findings, the paper would also be better served by a deeper analysis of some of the settings mentioned in passing in the Introduction (e.g., self-supervised). What does the proposed characterization of training dynamics reveal in that setting?

• I think that the writing of the paper can be improved, as in many parts it was quite hard to understand the actual information. Also, in some figures, some extra information is necessary, for example, in Fig. 6 what is the difference in each panel?
• Even if the proposed measure seems to capture the local complexity of the classifier, apart from some connections to related works, I think that a thorough analysis is missing.