No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths

We thank the referee for their careful consideration and feedback.

Weakness 1 We agree with the reviewer that architectural improvements are likely a big contributor to the phenomenon we observe. In fact, in Appendix D, we list architectural characteristics as a possible factor to the behavior we observe, and discuss it (see architectural characteristics paragraph). While we observe that the stable behavior of cosine similarity is, in fact, preserved on simple architectures (vanilla MLP with ReLU activations), our experiments cannot conclude on the contribution of e.g. batch norm, skip connections, etc. We agree this is an interesting line of research for future work. However, as our experiments are quite expensive (requires double computation as each training run needs to be computed twice), the range of ablations we have conducted is already quite extensive.

Most importantly, the main goal of our work is to characterize the properties of neural loss landscapes in practical settings, i.e. using modern architectures. As we discuss, our main goal is not to explain why these properties are present, but to quantify them and their relation with various factors (such as optimizers, depth and width, seeds, task, etc...). Since these properties seem very relevant to training dynamics, better understanding them mean we can better understand training behavior, and build a more practically relevant theory. Thus, while indeed our observations are only validated on heavily engineered architectures, we argue that this instead makes our work more relevant, and validating our claims on simple architectures that are not deployed in practice would be less meaningful.

Weakness 2 The values of RSI and EB appear close to $0$ in Figure 2 due to being small compared to the late stages of training, where both RSI and EB go to infinity (see late training behavior paragraph). But this is just a matter of scale, and the cosine similarity in fact quickly stabilizes. The speed at which the iterates $w_t$ approach $w_T$ is in fact entirely determined by RSI, EB, and the learning rate (see Equation 4), and the value of RSI and EB in the early stages, while small in comparaison to late training, are not negligible. For a fixed cosine similarity $\frac{RSI}{EB}$, observing smaller values of RSI and EB simply means the ideal learning rate should be larger. "RSI and EB follow predictable trends" does mean that the optimization trajectory advances toward its last convergence point at a steady pace, and that despite non-convexity and stochasticity, all iterations (with very few exceptions) contribute similarly in term of parameter space progression. The stability of the values of RSI and EB across minibatches, and its predictability across phases of training, mean that ideal values of the LR are stable across minibatches, and predictable across phases of training. This explains why simple LR schedules can be so efficient in training neural networks despite their non-convexity and the stochasticity of gradient sampling.

Weakness 3 We do compare to the baseline where gradients are replaced by noise, as suggested by the referee, in Section 6 (paragraph "induced Bias"). We also discuss the low value of cosine similarity in Section 4 (paragraph "low value of cosine similarity") and remark that in fact, if it wasn't very low, we would be able to train neural networks in very few steps, which know not to be the case. The cosine similarity being low can be compared to a quadratic function being badly conditioned: optimization is difficult, but follows a simple underlying structure, which eventually drives the convergence. Interestingly, RSI and EB would also follow predictable trends in the case of a random walk due to the high dimensionality having a regularizing effect. This can be interpreted as random walks having a stationary update rule. The complex structure of neural networks suggest the training dynamics could be highly complex (see contrasting examples in Section 6). Our work finds that it is not the case.

Weakness 4 As stated in our reply to Weakness 1, our work does not provide direct insights on which architectural features enable such properties. The goal of our work is to improve our understanding of the fundamental properties of neural loss landscapes that make first order optimization so surprisingly efficient, rather than exploring their origin. Once a sufficiently refined characterization of empirical neural loss landscapes is obtained, we will be able to derive theoretical results in more realistic settings than previous works, which will hopefully be able to guide the design of more efficient optimization algorithms. A few more steps in this direction are therefore necessary to lead to immediate algorithmic improvements.

We thank the referee for their careful consideration and feedback.

Weakness 1:

This is an excellent point. We were surprised to find that "SGD Converges to Global Minimum in Deep Learning via Star-convex Path" [1] is not already part of our bibliography, as it is a paper that has inspired our work and was one of the first added to our bib file. We intended to discuss differences with this seminal work in detail, and to be transparent, we forgot. We will add a paragraph contextualizing our work with respect to this paper.

The limitations in [1] that we try to address in ours are the following:

• Their work assume interpolation regime and only evaluates on CIFAR and MNIST, without typical training components such as batch normalization, weight decay, momentum, etc. By evaluating in realistic settings, with popular architectures and optimizers, on a variety of more advanced tasks (including in the non-interpolation regime), our work is closer to empirical practice.
• The epoch-wise star-convexity is fairly limited as it only considers the average of first-order developments over a full epoch. The iteration-wise star-convexity is only verified with respect to the last iterate of the sequence (just like in our work) but their theoretical results require star-convexity with respect to all minimizers of the given minibatch, which seems impossible to confirm empirically (and is in fact unlikely due to permutation invariance). Our theoretical results do not have such limitations and apply directly from our observations.
• [1] Assumes L-smoothness of each $l_i$. Even when the loss is made smooth, it typically entails an extremely high constant $L$ which is unlikely to explain the good behavior of training, and it is intractable to estimate in practice. In our work, the role of smoothness is played by EB.
• Perhaps most importantly, our work quantifies the properties of optimization paths on neural networks. In [1], the paths are simply observed to be star-convex, which would be akin to only observing the non-negativity of RSI (or $\gamma$) in our work. This quantification allows us to suggest LR schedules, guarantee linear convergence, etc.

In summary, prior works ([1], Goodfellow et al. (2015) and Lucas et al. (2021)) observed that the loss landscapes is simpler than expected, whereas we attempt to formally characterize and quantify this simplicity, providing more advanced tools to build theoretical results, and making a significant step toward practical relevance in our opinion.

Question 1 : since we train in realistic settings, we inevitably observe jumps in the training loss. The reason this does not contradict EoS observations is that small perturbations in high-curvature directions (like a small modification of very impactful features) can lead to large variations of the training loss, without impacting significantly the trajectory in the parameter space.

Question 2 : We believe this is due to numerical issues due to the gradients and $||w-w_T||_2$ becoming very small, and the fact that not all samples are interpolated as closely, and a few samples are not well interpolated at all. While this is insignificant in term of average training loss, and not noticeable before convergence, when nearing convergence this induces significant variance in RSI and EB. Indeed, minibatches containing samples that are not well interpolated will suffer form the same fate as training in the non-interpolation regime. While these samples are rare, since the shadowed area correspond to the minimum and maximum values over all steps in a epoch, this effect can become signifiant.

Question 3: We assume RSI and EB would be even better behaved by taking out the stochasticity. We did not conduct these experiments, first because it would be very computationally expensive to train until convergence on datasets like ImageNet, and second because we believe the observations in the deterministic setting would be less significant due to being empirically unrealistic. A major surprise in our work is that RSI and EB remain remarkably well behaved despite stochastic gradients having high variance. Such observations would be much less significant in the full batch setting.

We thank the referee for their careful consideration and feedback.

Nature of the cosine similarity in high dimensions (Weakness 1): Interpreting the significance of our observations is the most challenging component of our submission and the referee is right to point out that it is difficult to grasp.

Regarding the low value of the cosine similarity (~1e-3 for ImageNet), we discuss it explicitly in page 6 (“Low Value of Cosine Similarity” paragraph). If the cosine similarity was stable at a high value, then SGD would converge at an unreasonably fast pace. It is thus expected that cosine similarity would be low on average. We encourage the reviewer to compare our observations to a very badly dimensioned quadratic, for which optimization is slow and difficult, but the dynamics are simple, stable, and efficiently captured by the curvature.

The relationship between sampled gradients and $w-w^\star$ is also discussed in detail in all of page 8, where we compare to anisotropic random walks in very high dimension as the referee suggests.

Finally, the referee seems to oppose our claim about the stability of the cosine similarity to its low value (near orthogonality). The stability of the cosine similarity is relevant to the regularity of the convergence (in the parameter space), while its value is relevant to the rate of that convergence. Thus we argue these observations are not contradictory. Optimization trajectories on neural nets effectively progress at a slow pace, but with surprising regularity, encountering no significant setbacks… or wrong turns.

Lack of clear insights that can be drawn (Weakness 2): Considering the well known complexity of neural loss landscapes, observing such “banal” (as the referee puts it) patterns for fundamental quantities is, paradoxically, surprising. We refer to Figure 5 for contrasting examples of what the cosine similarities could look like for trajectories computed on functions that are either non-convex or stochastic. The significance of our observations is discussed in the “significance” paragraph of page 6. Moreover, the stepwise optimal learning rate is directly tied to the local value of RSI and EB. This banal behavior of RSI and EB (which we denote as “predictable”) is thus what allows banal learning rate schedules to work so well. Unpredictable variations, as exhibited in Figure 5, would make it impossible to design a near-optimal learning rate schedule.

Dependence of the results on the chosen empirical setup (Weakness 3): While we haven’t explored every possible setting variation, we believe we are presenting a sufficiently varied set of experimental settings to make a convincing case that our observations are not a byproduct of a specific empirical setup. It is noteworthy that our experiments require us to complete two full training passes (one to compute $w^\star$ and one to compute RSI and EB, knowing $w^\star$), effectively doubling computation costs.

In order to make our experiments as relevant as possible, we tried to reproduce as closely as possible empirical practice, including in the tuning of hyperparameters. That is why we only measured RSI and EB on the best learning rates obtained by grid search. We do see jumps both in the training and validation losses, as is typically the case in practice. However, it appears RSI and EB are remarkably resilient to such jumps.

While all our ImageNet experiments indeed use residual architectures (which were convenient to isolate width and depth as contrasting factors), we also presented our experiments with a MLP, UNet, SegNet, and Transformer, with similar conclusions for all of them. Note that we also used different LR schedules across tasks (constant LR for language, linear warmup cosine decay for images, piecewise constant for segmentation), in line with typical practice. While our experiments certainly don’t cover all of relevant deep learning settings, and experimenting e.g. with label noise would be very interesting, we argue in the light of everything above and all the ablations in our submission that our work found consistent patterns across a sufficiently wide array of settings to be considered unspecific to our setup.

We thank the referee for their careful consideration and feedback.

Theoretical guarantees for local versions of RSI and EB (Weakness 1 and Question 2): Interestingly, the linear convergence guarantees induced by RSI and EB only hinges on the local values of RSI and EB in the iterates that are explored. While previous theoretical works indeed only considered RSI and EB as global properties, Eq. (4) only depends on the local values of RSI and EB. The optimal learning rate $\eta^\star$ in Eq. (5) [which we will rename $\eta^\star(w)$ to clarify that it is dependent on $w$], and the corresponding step-wise guarantee in Eq. (6), only depend on the local value of RSI and EB. To obtain the guarantee of Eq. (7), it is thus sufficient for RSI and EB to be bounded on explored iterates.

Alternatively, the interpolation conditions derived in “Gradient Descent is Optimal Under Lower Restricted Secant Inequality and Upper Error Bound” (NeurIPS 2022) state that as long as (local) RSI and (local) EB (wrt to some $w^\star$) are bounded by $\mu$ and $L$ on a finite set of points and gradients (e.g. the iterates), then there exists a function $f$ for which RSI and EB are bounded globally by $\mu$ and $L$, that exactly interpolates these points and gradients. Our trajectory is thus also a valid trajectory on $f$, and convergence guarantees obtained from global properties naturally convert to local properties for iterates.

Considering the referee’s remark, we agree that the above points are not sufficiently clear. We propose to add a short paragraph at the end of Section 3 to emphasize that bounds on (local) RSI and (local) EB for iterates provide the same guarantees as global bounds. (Same for bounds on cosine similarity with adequate lr schedules).

$w^\star$ in contrasting examples (Question 1):

We use the converged point to be in the same setting as our experiments. We will specify this explicitly.

Lack of practical guidance (Weakness 2):

We absolutely agree with the referee. We believe that optimization of neural networks has been largely guided by intuitive engineering instead of theory in recent times, mostly because the classes of functions involved are insufficiently understood for relevant theory to emerge. We believe our work to be a promising – but incomplete – step towards understanding the structure of neural loss landscapes most relevant to 1st order optimization. Our work is indeed explanatory, but we hope that after further contributions to our understanding of empirical neural loss properties, we will eventually be able to develop a more adequate theory leading to useful algorithmic prescriptions ! Perhaps the most immediate impact on theory is that we believe our work supports that RSI and EB are much more relevant assumptions to use in optimization theory for neural networks than e.g. smoothness and strong convexity.