- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper analyzes how the spectral concentration happen along training in gradient optimizers. It shows update concentrates more often than gradient or momentum. It then proposes a more general algorithm class using LPS, and tested similar statistics.
Critical strengths
In my batch of reviews, this work stands out for being human. This is the only work I read where every notation follows a standard choice (e.g., g for gradient, u for update).
The different concentration behaviors between updates and gradients is unexpected to me. More studies can be interesting.
Critical weaknesses
I think this work is incomplete. It should be the start of interesting discoveries. Main questions remain not answered.
- Why do gradients and updates behave differently?
- When and why concetration is good for training or not desirable?
- Why use LPS but not other matrix to mix information?
- What about ADAM + ResNet ? How does diagonal / full preconditioning change results?
I would incline to accept because, though this work might not be accepted from past ICLR standards, it stands out this year when submissions seem to suffer from a great decline in quality.
Questions for authors
See weaknesses.
Thank you for you helpful comments, we have fleshed out the manuscript. Addressing your questions:
Do gradients and updates behave differently? Not really. As noted in our Introduction, we can describe a broad class of descent algorithms in a Nesterov-inspired framework: at step m+1, they compute a weighted version of gradients from the history Gm and use it to compute an update vector um+1. The gradient history Gm can be empty or unavailable, yet one must compute um+1. Both GT and UT typically have full algebraic rank. In terms of spectral representation, they again behave similarly: typically both have smaller effective rank and thus exhibit spectral collapse. Our starting point was the broad observation that signals in audio, video, and physical systems are often spectrally compact, and that algorithmic histories can exhibit analogous spectral compaction, as in the Tao–Candès versions of the restricted isometry property (RIP).
When concentration helps or hurts. During the iterations after spectral collapse occurs, the update vectors become smaller in magnitude and diffuse, which affects their learning rates. Intuitively, one can think of this in terms of an uncertainty theorem: localization of UT in the frequency domain prevents localization in the space domain, making update vectors small in magnitude and directionally unlocalized or diffuse. So can we gain LR by fixing this spectral collapse? Experiments indicate Adam and its variants do catch this collapse and fix it, but with some delay. In addition, a smaller LR leads to a proportional reduction in convergence rate. We do not present experimental data or analysis directly on this Adam-related mechanism, but we show that RDLPS graphs whose spectral properties yield mixing (i.e., norm-reducing) properties fix this collapse and also lead to effective speedup. See the table attached in this response that was missing in the submitted version.
We experimentally verify the concentration properties of Mgood(κ). Mgood(κ) is defined in this response to replace C1 and C2 in the submission and address the caveat that they admittedly had only “limited experimental evidence”. Mgood(κ) is the number of good updates in the first κ steps that improve the reciprocal gap Γi=1/Δi by at least some fixed b>0, where Δi=f(xi)−fmin. Concentration can be benign when the dominant directions contain the displacement needed to reach the target and have favorable curvature. It is obstructive only relative to the target and the actual trajectory's useful motion. But this is hard to characterize, measure, or detect for a general loss function, especially when provided as a black box or a deep circuit. It is desirable to have a provable algorithm under some robust hypothesis. Concentration is a ubiquitous phenomenon.
Why LPS rather than another matrix. LPS is a sparse Ramanujan graph (i.e., it has an optimal spectral gap for a given degree d), and the ERH graphs in the submission are almost Ramanujan. So are random d-regular graphs, but they have small girth, whereas LPS graphs have precise bounds on girth and clique sizes. We construct randomly directed multigraphs colored with two colors that have no sources or sinks and can be used to construct circuits in lieu of DNNs. The cut-set balance properties and small diameter emerging from the spectral-gap property help balance the flow of gradient information across the network, whereas in a DNN it is constrained to adjacent layers. The lower bound on the girth ensures this flow does not bounce back in a few steps. We tested all kinds of variants of the reference RDLPS construction from LPS in the early part of the paper; this led to inconsistent and confusing descriptions of our graphs in the submission, as Reviewer 1 observed. In our experiments, we could not get sparse random regular graphs to work so well. In our limited experiments, large cliques lead to instability under mild perturbations of input training data. Recent literature aims at keeping graphs of connections sparse.
Adam, ResNet, and preconditioning. The submission documents spectral-collapse studies across DNNs and CNNs, including ResNet models, and across optimizer families, including Adam and its variants. These spectral studies do not constitute a matched Adam-plus-ResNet speedup study. Adam's adaptive diagonal scaling changes the relationship between gradient and update histories and can change their spectral energy distributions. A fixed invertible preconditioner preserves algebraic rank but need not preserve effective rank; for adaptive diagonal or full preconditioning, we make no universal monotonic claim about spectral concentration. A matched Adam-plus-ResNet speedup study, analogous to the convex ladder, remains necessary; the existing spectral-collapse measurements do not establish that result.