Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning

We thank the reviewer for their comments. We address specific points below:

The online learning protocol discussed in this paper is not entirely clear to me. Could the authors provide with a more detailed formulation of the online learning procedure using SGD? In the online learning contexts I'm familiar with, such as Prediction with Experts' Advice, regret is typically employed as a performance measure. Could the authors clarify how the algorithm's loss is assessed in the online learning setting under consideration?

The definition of online learning is provided on the first line of Page 2 as single epoch training. In particular, we are considering the stochastic online learning setting, where at each instance the loss function is drawn from an underlying distribution, and the regret is measured according to the loss exhibited by the current algorithm and an underlying truth (which is assumed to be providing the correct labels at each step).

I'm curious about the relationship between the convergence rate and the choice of adaptive learning rate. Is the observed behavior consistent when using optimizers like Adam?

Yes, the experiments in section 2 on Imagenet and C4 dataset are with Adam. The CIFAR-5m experiments use SGD.

How does this research account for or negate the effects of the neural network's architecture?

This paper shows that the result holds on architectures including CNNs and Transformers, thus showcasing the agnostic nature of the results with respect to architecture.

I'm interested in understanding the design of the experiments. Given that in the real-world online learning setting, achieving comparable performance can be more challenging without full access to the dataset, yet it offers efficiency advantages. Were there particular measures or modifications incorporated to guarantee an fair comparison with the offline setting?

Note that in this work, we are considering the stochastic online setting, and thus the samples are indeed drawn from an underlying distribution even for the online setup, which does not change with time. In this sense, this is not the adversarial online setting. Moreover, the only difference between online and offline setting in this work is whether we run training for multiple epochs or not.

Please consider raising your score if you feel that your concerns were answered, and if not we are happy to continue discussing your comments.

We would like to thank the reviewer for their insightful comments. We appreciate the reviewer observing that our paper is interesting and their general curiosity towards the work. We address the comments raised by the reviewer below.

The experiments are performed on Resnet18, ConvNext-T, and GPT-2 small, which are relatively large models. I'm wondering if the main hypothesis of this paper also holds for smaller models, or if this phenomenon might be due to the overparameterization of the models?

We start by noting that for Resnet18 and GPT-2 small the number of parameters in the model is smaller than the dataset. Further we did experiments on narrower variants of Resnet18 (8 channels instead of 64) as well as small CNNs and found no differences in our results. We would be happy to add these to the final version. We would also be happy to share these in the rebuttal period if the reviewer thinks this is critical to their opinion of the paper.

A minor point: In the paper, your main findings and hypothesis are made for SGD, while in your experiments, the optimizers used are SGD with momentum (for ResNet18), AdamW (for ConvNext-T), and "default optimizer in Mosiac ML" . So the main hypothesis is not only for SGD but also for difference optimizers?

In general, by SGD noise, we refer to the noise induced due to mini-batch sampling and finite learning rates. Our general claim is about trajectory with and without SGD noise. We would clarify this in the paper that our results hold for other optimizers as well. We note that the MosaicML optimizer is also AdamW.

The experiments on reducing the step size are not very clear to me, since the step size also affects the sharpness of the solution SGD can find (as you the "edge of stability" phenomenon you mentioned in Appendix D). So it seems to me that the decrease of loss after decreasing the step size may be due to the fact that the dynamic is around a local minimum of certain sharpness, and a smaller step size allows it to go into this local minimum, rather than a better approximation of the "golden path" due to smaller SGD noise. Similar arguments could also made for the experiments on increasing step size.

Yes, we indeed agree that the drop in loss happens both due to Edge of Stability-like phenomena and due to reduction in noise. The main claim is that SGD noise doesn’t affect the overall dynamics in the sense that you can recover the golden path by reducing the noise during training. We are not claiming that the SGD path itself is a noisy version of the gradient flow/golden path.

The study of this paper focuses on SGD noise, i.e. the noise comes from not using full-batch. I'm wondering if the main hypothesis also holds for manually added noise (e.g. noisy gradient descent like Langevin dynamics) ?

This is an interesting question and our current intuition would be that it would not help in online learning tasks. But we do not have any experiments to this end since our work was focused on SGD noise.

As you mentioned in the discussion at the bottom of page 2, the "golden path" is the noiseless gradient flow. I'm wondering if you could compare the trajectory of SGD to the actual gradient flow (i.e. GD with full batch, and very small step size) ?

We do this in:

1. Loss trajectory: Figure 10 where we show that with smaller learning rates and larger batch sizes the loss trajectory converges to gradient flow and the performance improves with smaller learning rates and larger batch sizes.
2. Function space trajectory: In Figure 14 we decrease the learning rate by more than a factor of 100 and increase the batch size by a factor of 16 and find that after we decrease the SGD noise the TV distance curves match.

We note that the main claim is that SGD noise doesn’t affect the overall dynamics in the sense that you can recover the golden path by reducing the noise during training. We are not claiming that the SGD path itself is a noisy version of the gradient flow/golden path.

Please consider raising your score if you feel that your concerns were answered, and if not we are happy to continue discussing your comments.

We would like to thank the reviewer for their time reviewing our work. We appreciate the reviewer observing that our paper is interesting, well presented and their general curiosity towards the work. We address the comments raised by the reviewer below.

Details about the experimental results: We provided these in Appendix A across all three datasets, including details about all pertinent hyperparameters. Please let us know if there is specific information absent in this section; we are happy to discuss them and provide any other details.

Multiple epochs for Imagenet: Since the Imagenet dataset has fewer samples than the other two datasets we use (CIFAR-5m and C4) to achieve reasonable accuracy we had to train for more than one epoch. To that end, we used data augmentation as a way to remain in the “online regime”. We verified that we were in the online regime by checking that train and test loss/error were the same. We agree this is a valid limitation and will further discuss it in the final version.

Theoretical results: Yes, we do agree that we don’t have any theoretical results as of now. However, for convex setting, we can show that our arguments hold for specific cases, and we provide an example below. For non-convex settings, it is not difficult to come up with a counter-example in which small learning rate trajectories get stuck in local minima and hence perform worse. However, as our results hold in practical settings, we believe it would be interesting to come up with the correct assumptions in non-convex settings for which our results hold. Below we describe a simple convex setting where our results hold:

Certainly, here is the text with LaTeX formatting for the mathematical expressions, where each expression is enclosed in $ signs to render as math when compiled with LaTeX:

Consider a 1D convex optimization problem where $x \sim N(0, 1)$ and $y^* = 0$. The square loss is given by $0.5w^2x^2$. For SGD in online learning, with batch size 1 and learning rate $\eta$, the iterate at time $t$ is given by $w_t = \prod_{i=1}^{t} (1 - \eta x_i^2)w_0$. Then, the expected loss at time $t$ is given by $0.5w_0^2(1 - 2\eta + 3\eta^2)^t$.

Consider another SGD trajectory, with learning rate $\eta/2$; its loss at time $2t$ is given by $0.5w_0^2(1 - \eta + 0.75\eta^2)^{2t}$. Now, if at time $t$, we switch the first trajectory from $\eta$ to $\eta/2$, then the expected loss at time $t' > t$ is given by $0.5w_0^2(1 - 2\eta + 3\eta^2)^t(1 - \eta + 0.75\eta^2)^{t'-t}$. Thus, in this convex setting, the shape of the expected loss curve will be the same for the two curves, but only after an appropriate time shift to allow for the losses to match.

Unclear how many epochs are in each plot: We will add the number of epochs in the caption. For now we give the number of epochs in Fig 3. 3a (top): 15, 60, 240 epochs for batch size 32, 128 and 512 batch size respectively. 3a (bottom): 240, 60, 30 for LRs .025, .1 and .2 respectively. 3b (top): 56, 112, 224 for batch sizes 2048, 4096 and 8192 respectively. 3b (bottom): 168, 84, 56 epochs for LRs .0003, .0006 and .001 respectively.

Offline curves track online curves: The reason that offline curves track the online ones is not a coincidence. Rather, every offline training run starts with new data never seen before. Then, as data is repeated more and more, the train and test performance curves diverge and the difference between the regimes becomes noticeable. See Nakkiran et al. 2020 (https://arxiv.org/abs/2010.08127) for a detailed discussion of this phenomenon.

Effect of longer training in online regime: In all of our experiments, to the best of our budget, we never saw that the lower noise (with the right movement axis) was performing better than the high noise ones. This includes runs of larger scale than Figure 1.

Details of multiple-epoch training: The multi epoch training was done with full shuffle before each epoch.

Code: The codebase used for the C4 experiments is LLM foundry: https://github.com/mosaicml/llm-foundry/tree/main. We will add the codebases for CIFAR-5m and Imagenet in a few days.

Please consider raising your score if you feel that your concerns were answered, and if not we are happy to continue discussing your comments.