Crafting Heavy-Tails in Weight Matrix Spectrum without Gradient Noise

Authors: Vignesh Kothapalli, Tianyu Pang, Shenyang Deng, Zongmin Liu, Yaoqing Yang
Primary area: learning theory
Keywords: Heavy Tails, Spectral Analysis, Generalization

Abstract:
Training strategies for modern deep neural networks (NNs) tend to induce a heavy-
tailed (HT) empirical spectral density (ESD) in the layer weights. While previous
efforts have shown that the HT phenomenon correlates with good generalization
in large NNs, a theoretical explanation of its occurrence is still lacking. Especially,
understanding the conditions which lead to this phenomenon can shed light on the
interplay between generalization and weight spectra. Our work aims to bridge this
gap by presenting a simple, rich setting to model the emergence of HT ESD. In
particular, we present a theory-informed analysis for 'crafting' heavy tails in the
ESD of two-layer NNs without any gradient noise. This is the first work to analyze a noise-free setting and incorporate optimizer (GD/Adam) dependent (large)
learning rates into the HT ESD analysis. Our results highlight the role of learning
rates on the Bulk+Spike and HT shape of the ESDs in the early phase of training,
which can facilitate generalization in the two-layer NN. These observations shed
light on the behavior of large-scale NNs, albeit in a much simpler setting. Last
but not least, we present a novel perspective on the ESD evolution dynamics by
analyzing the singular vectors of weight matrices and optimizer updates

Decision: reject
Reviewer scores: 3, 8, 6, 3

Reviews and discussion:
<thread>
creation date:
1729327337292

thread_type:
official_review

<thread_object>
creator: reviewer_pis8

<content>
summary:
The submission studies an interesting problem. When does HT-ESD happen? Why does it lead to good generalization?

The key results are below:

1. Using a toy model,  ADAM after one step can provably induce a spike in spetrum. (thm 4.1)

2. With experiments, the authors show that bulk decay happens (Fig 4), and that spike + decay leads to heavy tail.

3. With experiments, the authors show that successful feature learning happens when the spectrum has the right tail exponent. (fig 5)

##Strength:##

I like the experiment part of this work.  In particular, comparing ADAM vs GD in Fig2 Fig3, and demonstrating the decay in Fig 4. 

I think the perspective is novel. The spectrum distribution not only results from the minibatch noise but also from full batch updates.

##Weakness:##

Although I enjoy reading the work, I am not confident that the authors successfully answer the questions asked.

1. The spike after one large update is trivial. Given the backprop structure of neural net, one step update to the weight is rank one. When the step is large, one gets a rank-one spike.

2. The paper demonstrates that decay happens without explaining why. More specifically, does the decay happen just correctly such the spectrum is heavy tailed?

3. The paper demonstrates that the tail index should be in the correct range for the features to be learned. However, no explanation is given. Further, the experiments for this result are synthetic and toy.

I am happy to update my review if the authors could address the above concern.


##Minors:##

What is u in line 241?

strengths:
See summary

weaknesses:
See summary

questions:
See summary
</content>
</thread_object>

</thread>
<thread>
creation date:
1730679074440

thread_type:
official_review

<thread_object>
creator: reviewer_xtm5

<content>
summary:
This paper is interested in understanding the evolution of the empirical spectral distribution for the first-layer weight matrix in a two-layer neural network during training. The paper considers a student teacher (single index model) with Gaussian. It shows that early-stage feature learning occurs for a much smaller step size for Adam compared to GD. 

The paper also empirically studies the spectrum's evolution during further training and claims the existence of the initial spike is needed to transition to the heavy-tailed phase. Finally, the paper looks at various kernel alignment metrics, their evolution, and correlation with generalization.

**Justification for Score**

I think overall the paper presents intersting insights for a different optimizer. Hence I think it is worth accepting. However, the paper doesn't always position itselves in the most informative way compared to prior work and I have concerns about the significance of the spike that has been seen. Hence I do not give it a higher score.

strengths:
**Novelty:** As far as I know, the theoretical works on the early-stage emergence of spikes have been primarily limited to gradient descent. No theoretical work I know of analyzes Adam. Hence I think this is a novel contribution of the paper. Additionally, the insight that Adam requires a smaller step size than gradient descent to see the spike is important. 


**Clarity:** The paper is mostly well-written. My one concern is that when people talk about the spiked structure (Ba et al, Moniri et al). they mean for the features $F = \sigma(WX)$ and not for the weight matrix $W$. This was confusing at first.

weaknesses:
**Originality:** In terms of originality, the paper should do a better job of positioning itself with respect to Martin and Mahoney,  Ba et al., and Moniri et al. I think this is important. 


**Significance:** I think the result on smaller step size results in spikes is significant. If this were a result as presented in Moniri et al. However, as a result is currently presented, I am not sure the theory result says enough. Specifically, 

1. The paragraph after the corollary is clear to me. The step size scales are different for the spectral norm and the Frobenius norm. How do we rationalize this to show that there is a spike?

2. Spikes in $W$ do not necessarily correspond to spikes in $F$. Especially if you have Gaussian Data. See [1] (flipping the role of $W$ and $X$). 

[1] Wang, Zhichao, Denny Wu, and Zhou Fan. "Nonlinear spiked covariance matrices and signal propagation in deep neural networks." arXiv preprint arXiv:2402.10127 COLT (2024).

questions:
1. Generalization with Heavy-Tailed models. Do the authors know of any works that theoretically characterize the generalization error of models with heavy tails? Even in the regression setting I know of [2]. Also, do the authors know about papers that consider generalization error for models with spiked covariance (besides the Ba et al. 2023 paper), again including regression. 

[2] Wang, Yutong, Rishi Sonthalia, and Wei Hu. "Near-interpolators: Rapid norm growth and the trade-off between interpolation and generalization." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

2. Emergence of heavy tails. For $\eta=0.1$, the experiment needed $t \sim 10^4$. However, the authors claim $t \sim 10^4$ was not enough for $\eta = 0.01$. I imagine we need more steps, maybe even something like $t \sim 10^7$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730712171302

thread_type:
official_review

<thread_object>
creator: reviewer_bo67

<content>
summary:
The paper aims to investigate the relationship between heavy tails in the weight spectrum distribution of neural networks and the ability of the network to generalize over unseen samples. The authors set up a teacher-student setting where a two-layer neural network learns a single-index model. First, the paper shows that for a sufficiently large step size, the full-batch Adam can align with the teacher's direction in just one step, corresponding to a spike in the ESD emerging from the initial mass. The analysis continues by empirically showing that the dynamics of the ESD evolves from the bulk to a heavy tail distribution. Finally, the paper shows the connection between the ESD heavy tails and the orientation of the singular vector of weight updates.

strengths:
- To my knowledge, this paper is the first to study the HT-generalization correspondence in the single-index teacher-student setting. Altough not bringing any revolutionizing idea, the paper establishes an important first step towards understating this phenomenon within the community.
- The analysis is comprehensive and precise, also taking into account techniques used in practice such as weight normalization and learning rate schedulers.

weaknesses:
- The paper is showing mostly empirical result. In this theoretical setting one might expect to have more theoretical support of the claims.

questions:
- In line 241, shouldn't we divide the similarity by the norm of $u_1$? Otherwise it can grow even if $u_1$ and $\beta$ are not getting more aligned
- In line 308 you talk about a sweet for $\eta$, but I can't see it in the figure, can you clarify?

Minor:
- Line 297: $\eta=0.1$, but the figures says $\eta=1.$
</content>
</thread_object>

</thread>
<thread>
creation date:
1730822338722

thread_type:
official_review

<thread_object>
creator: reviewer_uys5

<content>
summary:
The paper studies the heavy tail phenomenon of the spectrum of weight matrices and its impact on generalization.  The paper presents a theorem for single step of Adam which shows an emergence of "Bulk + spike" spectrum. It futher empirical evaluates how this spectrum evolves into a heavy tail.

strengths:
a) The paper extends the single step analysis of GD Ba et. al. for Adam.   
b) The observation that bulk + spike evolves into a heavy tail is interesting.

weaknesses:
a) The paper lacks sufficient motivation for the problem setting and the relevance of the chosen algorithm, leaving it unclear why this is an important quantity to study. Notably, both the heavy-tail mechanism and strong generalization stem from learning the single-index direction, making it uncertain whether the heavy tail is simply a byproduct of good generalization or its cause. Consequently, it is challenging to assess whether this problem setting and analysis truly captures the influence of the heavy-tail spectrum on generalization.

b) The empirical analysis is restricted to single-index teachers and two-layer networks, which limits the study's scope and makes it insufficient to determine whether any findings are broadly applicable.

c) The theoritical analysis does not capture how "BULK + spike" transition into a heavy tail phenomenon. Hence the paper falls short of theoritically understanding the emergence of HT-ESD - the theoritical analysis is only captures the BULK + spike shape of spectrum after a single step of Adam.

Minor :
- Make a consistent notation of $\beta^{*}$ through out the paper.
- The inline math can be formatted better to ensure better readbility.

questions:
discussed above
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper explores the emergence of heavy-tailed in the empirical spectral distributions of the neural network weights during training. It focuses on the transition from a bulk + spike to heavy tails. While the paper presents some interesting insights, such as Adam requiring smaller step sizes than GD for spike emergence, the reviews highlight mixed opinions.

### **Strengths**

- Novel exploration of HT-ESD emergence in Adam, extending prior work on GD.
- Interesting empirical analysis
- Insights into the spectral properties of weight matrices and their role in generalization.


### **Weaknesses**
- The theoretical contributions are limited to the bulk + spike phase after one step
- The experiments are restricted to toy models, raising concerns about generalizability.

### **Decision**
Two reviewers (bo67, xTm5) support acceptance while two (uys5, piS8) recommend rejection, citing insufficient depth and limited applicability. Overall, the paper offers valuable early-stage insights but lacks the theoretical and empirical depth to comprehensively address HT-ESD and its connection to generalization. I believe this requires additional work.