Fast Equilibrium of SGD in Generic Situations

We would like to thank you for your valuable comments. Some explanations in response to your remarks are below and we will address these concerns in a revised version accordingly.

1. We are running an experiment with CIFAR 10 and will add it to the revised version.
2. We will correct the typos and inaccuracies you pointed out.
3. You are right about the exponents in the abstract. They should be $e^{O( (\eta\lambda )^{-1}) }$ and $\tilde{O}(\frac{1}{\eta\lambda})$ respectively. We will fix them.

We would like to thank you for your valuable comments. Some explanations in response to your remarks are below and we will address these concerns in a revised version accordingly.

0. Response to [“ I think you can attract the interest of many people if you have a headline figure showing the speed of convergence to the stationary”]. Thanks for this suggestion. Experiments where the empirically observed rates of convergence are polynomial were contained in the original paper (Li et. al 2020) where the Fast Equilibrium Conjecture was first asked. We will add references to figures from that paper.
1. Response to Question 1. Thanks for pointing out the unclarity of the writing here. The difference between the polynomial and exponential times is explained in the response 2 below. The difference between $(\eta\lambda)^{-1}$ and $(\eta\lambda)^{-\frac12}$, is due to the fact that (Bovier et al., 2004; Shi et al., 2020) studied neural networks without normalization, which involved an analysis on $R^d$. With normalization and weight decay together, (Li et al. 2020) proved that the problem, via the polar coordinate decomposition written as (4) and (5) in our paper, can be considered as a problem on $S^{d-1}$. After this polar decomposition step, the effective learning rate is $O((\eta\lambda)^{\frac12})$, which results in replacements of exponents appearing in convergence times.
2. Response to Question 2. In this case, the observed convergence to equilibrium is dominated by the diffusion. The drift regulates how fast the trajectories fall near the bottom of a basin (the “descent stage”), i.e. how fast the loss function value converges. However, the trajectories then start a random walk all around the bottom of the basin. This is the “diffusion stage”, whose time scale is regulated by the diffusion term. (The third stage takes an exponentially long time when trajectories leave the basin to nearby basins but this cannot be observed in practice because of the exponential time scale.)
3. Response to Question 3. Even though some earlier papers assumed a constant gradient noise structure, our current paper does not need to assume constant gradient noise. In fact, equations (4) and (5) were proved in (Li et al. 2022) and didn’t require constant noise structure.

We would like to thank you for your valuable comments. Some explanations in response to your remarks are below and we will address these concerns in a revised version accordingly.

1. Response to [Question 1]. The noise structure does affect the convergence rate. But as long as Assumption 1.2 is satisfied, the noise structure wouldn’t affect the asymptotic order of the convergence rate.
2. Response to [Question 2]. This is a very interesting question worth further exploration, but is not covered by our result as we rely on a polar decomposition of SDEs (written as (4), (5) and (6) in the original version, the one before current revision), from (Li et al. 2020) that depends on the current homogeneity structure.
3. Response to [Weaknesses] and [Question 3]. You are absolutely right that the conditions in Assumption in 1.2 are essential for our analysis and we will add explanations in a revision. To be precise:

• Assumption 1.2 (i) is essential because without this assumption, the SDE would not be equivalent to a SDE on the sphere $S^{d-1}$ (written as (6) in the original version, the one before current revision), which is crucial to our analysis. Without this assumption, similar analysis can probably be formulated on $R^d$ instead of the $S^{d-1}$ coordinate but there will be new technical obstacles to overcome. Since the original fast equilibrium conjecture was asked for normalized neural nets, we restrict our study to the current setting.
• Assumption 1.2 (ii) is important because if not, a trajectory may stay near a critical point (for example a saddle point) for a very long period of time, and thus it would not be able to converge within a polynomial time.
• The reason why we need Assumption 1.2 (iii) is that if the span is not the whole tangent space, but instead a subspace of the tangent space, then the diffusion will be restrained to this subspace, which a priori may be very fractal and existing mathematical theory is not sufficient to guarantee a unique equilibrium in limit.

4. We will fix this typo.

We would like to thank you for your valuable comments. Some explanations in response to your remarks are below and we will address these concerns in the revised version accordingly.

1. We would change the name of SWA to “weight average over trajectories”.
2. We will add the references you pointed out.
3. The previous assumption of analyticity is restrictive because the regularity of the loss function is decided by that of the activation function. Even though popular activation functions such as Sigmoid are analytic, a priori one could use smooth but not analytic functions. The one basin assumption is restrictive as we do not see empirical evidence of proof that $L$ only has one basin. In fact, the experiments at the end of the paper suggests that there are multiple basins.