Convergence and Implicit Bias of Gradient Descent on Continual Linear Classification

We thank the reviewer for their detailed and insightful comments on our work. Below, we address the concerns raised by the reviewer.

W1+W2. Experiments with real-world datasets & realistic synthetic datasets.

• Thank you for pointing these out. Please check out our General Response handling all questions and concerns about experiments raised by all reviewers. For your specific concerns, please refer to #1 and #2.

W3. We know all training data in advance; why don’t we combine them and use SGD?

• Thank you for the insightful question. Indeed, if there are all training data for all tasks given a priori, one can combine them and run SGD. However, there can be scenarios where utilizing the combined training dataset becomes impossible, e.g., when the datasets for different tasks are stored in distributed data silos and communication of data points is expensive or prohibited.
• Moreover, we believe that our theoretical findings can be extended to a more general online continual learning setup, beyond the current setup that uses the same data points over and over again. Consider a finite number of tasks’ data distributions (with bounded supports) which are jointly separable, and let them be cyclically/randomly chosen one by one at each stage. Suppose a finite-size training dataset from each data distribution is sampled every time we encounter a task. Even in this case, we expect that the story would be the same: the continually trained linear classifier will eventually converge to the max-margin direction that jointly classify every task’s data distribution support. In our revised paper, we empirically demonstrate this in Appendix C.2.4.
• This example demonstrates that the intuitions gained from our analysis can extend to more realistic and complex scenarios. In our paper, however, we focus only on our data repetition setting so that precise theoretical guarantees are attainable; rigorous extensions to more general settings would be much more challenging.

W4. Batch = Task? It’s not surprising that SGD converges.

• As the reviewer pointed out, the algorithm we analyzed (sequential GD) and the usual online SGD share several properties. At every time step, they use some part of the dataset (called "batch") to update the model iteratively. Hence, both can be used when we cannot access the full dataset at every update.
• However, the critical difference between these two is in repetition. When we theoretically analyze (online) SGD, the most common assumption is that every stochastic gradient is independently sampled. Thus, if we collect many gradients, the overall update can eventually approximate the full-batch gradient update. When we run sequential GD in the continual learning setup, however, there must be certain dependencies between updates since we repeatedly use the same batch of data points for $K$ consecutive updates during each stage. Thus, if we do many updates for a single task (i.e., large $K$), the total update over each stage is significantly biased toward a specific task, not the joint/offline solution. These dependencies made it difficult to apply the usual convergence analysis of optimization algorithms, which was the main obstacle we had to overcome. Thus, we claim that our theoretical result is not a direct result of SGD convergence analysis.
• We also note that our theoretical analysis covers not only the convergence (in loss and the iterate direction) but also a non-asymptotic characterization of forgetting, which is one of the most important quantities in the literature on continual learning.

W5. It has to be specific in terms of standard datasets and real-world scenarios.

• Thank you for a great suggestion. Here we provide more precise references and citations about the cyclic/random task ordering. We also attached the corresponding references/citations in revised paper.
• Cyclic task ordering:
  • Number of hits for certain keywords (e.g., ‘dinner’) in search engine (trends.google.com/trends/)
  • Hourly revenue of a recommender system (Yang et al., 2022)
• Random task ordering:
  • Autonomous driving (Verwimp et al., 2023)

Dear reviewer sGag

Thank you for your important questions and insightful comments in the first review. We uploaded our developed manuscript which provides clearer real-world scenarios and supplementary experiments. As the discussion period is almost over, please check out our revised paper and our response if you haven’t done so. We hope that our revision and the rebuttal resolve your initial concerns. If you feel the same, we would appreciate if this could be reflected through an updated score. Also, please do not hesitate to let us know if you have any remaining questions. We appreciate your contribution to the reviewing process.

Sincerely, Authors

We sincerely appreciate the reviewer for taking the time and efforts to read and examine our paper closely. Your dedication helped us improve the paper significantly. Below, let us address your comments and questions:

W1. The results are only informative under certain task repetitions; cannot handle arbitrary task sequences.

• Thanks to the connection between weakly-regularized continual learning and SMM, Evron et al. (2023) obtain the exact trajectory of iterates over different stages obtained by sequential projections. On the other hand, in our sequential GD setting, it is very difficult to keep track of the exact location of the iterates, since the iterates are updated multiple times but training stops before convergence. To overcome this issue, we use different proof techniques motivated from (Soudry et al. 2018; Nacson et al. 2019) to analyze the direction in which sequential GD eventually converges to. We are not sure if any conclusions we draw from our analysis can extend to arbitrary sequences.
• Nonetheless, we believe that our theoretical results provide some useful insights to more general continual classification scenarios. Specifically, we believe that our theoretical findings can be extended to a more general online continual learning setup, beyond the current setup that uses the same data points over and over again. Consider a finite number of tasks’ data distributions (with bounded supports) which are jointly separable, and let them be cyclically/randomly chosen one by one at each stage. Suppose a finite-size training dataset from each data distribution is sampled every time we encounter a task. Even in this case, we expect that the story would be the same: the continually trained linear classifier will eventually converge to the max-margin direction that jointly classify every task’s data distribution support. In our revised paper, we empirically demonstrate this in Appendix C.2.4.

W2. Readability issues of appendices

• We are sorry for any confusion caused by our proofs. We have supplemented our explanations with more explanations for the involved steps. We aim to supplement appendices with proof sketches carefully delivering key technical challenges and insights, but due to the length/complexity of proofs and lack of time we were not able to finish this in time. We plan to do so after the discussion period.
• From Eq. (19) to Eq. (20): We found there was a missing factor inside Eq. (19). We corrected it by adding the gradient norm factor to (19).
• Eq. (26): we add a supplementary explanation. The third inequality comes from the property of the largest singular value, and the last equality holds by the definition of the gradient update rule.

Q. A collection of suggestions for improving the writing

• We greatly appreciate for the reviewer’s careful reading and insightful comments on improving our manuscript. Although the reviewer do not expect responses about these comments, we provide answers to some of them.
• Line 62: Thank you for an insightful comment. As per the reviewer’s suggestion, we toned down our claims about the existing work Evron et al. (2023); we realize we were overly critical as we try to motivate our setting. Please check out our updated introduction (Section 1).
• Figure 1: The reason why we opt for 3D visualization in Figure 1 is to represent the irrelevance between the directions of individual tasks’ max-margin and the joint max-margin classifiers. We also conducted 2D experiments and made a cleaner visualization of directional convergence to joint max-margin direction (e.g., Figure 2). For more details about experiments, please take a look at our General Response and the updated manuscript.
• Line 432: we assumed the data spanning whole space without loss of generality. This is because, as we mentioned in the same paragraph, every gradient update happens in the span of data points. In other words, the dynamics orthogonal to the data span is constant, so we simply neglect these components. We made it more clear in our updated manuscript by adding “without loss of generality”.
• Line 434: the original “strictly” is correct. The empirical risk function based on logistic function cannot be globally strongly convex (i.e., bounded below by positive-definite quadratic functions everywhere). In particular in the strictly non-separable case, however, the training loss becomes locally strongly convex near the optimum, which we prove to eventually obtain our convergence result for non-separable case.
• Theorem 5.2: since the total loss $\mathcal{L}(w)$ is $B$-smooth (where $B=\sum_{m=0}^{M-1} \beta_m$), it satisfies that $\mathcal{L}(w) - \mathcal{L}(w_\star) \le \langle \nabla \mathcal{L}(w_\star), w-w_\star \rangle + \tfrac{B}{2}\\|w-w_\star\\|^2 = \tfrac{B}{2}\\|w-w_\star\\|^2$. Thus, the iterate convergence naturally implies the loss convergence with an exactly the same rate. We made this clearer in the updated manuscript.

We highly appreciate the reviewer for their constructive feedback. Below, let us provide our response to the comments and questions raised by the reviewer:

W1. Misalignment with practical settings, e.g., cyclic ordering of tasks

Thank you for the insightful question. Indeed, our setting does not fully align with the practice of continual learning. However, we believe that our theoretical analyses are useful because 1) the insights can carry over to more general setups, 2) they offer a theoretical basis for a simple baseline algorithm, and 3) they can serve as a stepping stone for more sophisticated analyses on continual learning techniques.

1. Indeed, if there are all training data for all tasks given a priori, one can combine them and run SGD. However, we note that there can be scenarios where utilizing the combined training dataset becomes impossible, e.g., when the datasets for different tasks are stored in distributed data silos and communication of data points is expensive or prohibited. Moreover, we believe that our theoretical findings can be extended to a more general online continual learning setup, beyond the current setup that uses the same data points over and over again. Consider a finite number of tasks’ data distributions (with bounded supports) which are jointly separable, and let them be cyclically/randomly chosen one by one at each stage. Suppose a finite-size training dataset from each data distribution is sampled every time we encounter a task. Even in this case, we expect that the story would be the same: the continually trained linear classifier will eventually converge to the max-margin direction that jointly classify every task’s data distribution support. In our revised paper, we empirically demonstrate this in Appendix C.2.4.
2. Our theoretical analyses may not immediately offer any guidelines or suggestions for practitioners interested in general continual learning problems. However, we believe that our work provides a theoretical basis for a concrete baseline: “you should do better than this.” Our theory reveals that when the same (or similar) tasks appear repeatedly, a naive algorithm without any techniques (e.g., regularization or replay) specialized for continual learning will eventually “work,” in terms of convergence to a desirable offline solution and vanishing forgetting. Thus, we expect that such a naive algorithm does not always fail in more practical scenarios, and any new approach for continual learning should be able to outperform this simple baseline.
3. Furthermore, we believe our analysis can serve as a stepping stone to more advanced theoretical analyses on more practical approaches such as regularization- and replay-based methods.

W2. Empirical results to validate the theoretical findings

• Thank you for pointing this out. As all reviewers raised similar concerns, we posted a General Response specifically about experiments; please have a look. To be a bit more specific, we performed several experiments on synthetic 2D datasets in order to validate our theoretical results under cyclic/random task ordering. Also, we provide an experiments on a more realistic dataset (CIFAR10). Besides, we also plan to conduct deep learning experiments and will put the results in our paper.

Q3. Regarding the definition of task similarity

• To the best of our knowledge, there is no single widely accepted definition of task similarity. In the well-studied continual linear regression setting, various notions of task similarity have been proposed by several previous works (Doan et al., 2021; Evron et al., 2022; Lin et al., 2023). The task similarity is of great interest in this line of work because it is often closely connected to the continual learning performance (e.g., catastrophic forgetting or knowledge transfer). In continual classification setup like ours, we do not know much of works studying the relevance between task similarity and forgetting.
• In our paper, we theoretically characterize the connection between the amount of forgetting per cycle and a form of “alignment” between different tasks. The term $N_{p,q}$ ($\bar {N}\_{p,q}$, resp.) captures positive (negative, resp.) alignment of the data pairs between tasks $p$ and $q$. We view these terms as positive/negative alignments, because they are sums of positive/negative inner products between data points in two tasks. We originally explained $N_{p,q}$ and $\bar{N}\_{p,q}$ as “task similarities” for simplicity because, similar to the previous works revealing connection between task similarity and forgetting, we figure out they are closely related to the amount of forgetting: high $N_{p,q}$ and low $\bar{N}\_{p,q}$ yield low forgetting (and thus high knowledge transfer), while low $N_{p,q}$ and high $\bar{N}\_{p,q}$ yield high forgetting. However, we realized that the terminology “task similarity” may be slightly misleading, because even two identical tasks (say $p$) may have negative $\bar{N}\_{p,p}$. We revised the writing in our manuscript.
• Lastly, we comment on the reviewer’s intuition on the relationship between task similarity and loss convergence. We totally agree with the reviewer’s intuition on the connection between the task similarity (or our specific notion of task alignments) and loss convergence. However, we remark that our loss convergence analysis in Theorem 3.3 does not quite capture that intuition. The non-asymptotic convergence upper bound we presented only captures the worst-case scenario (which is due to the nature of upper bounds), where the model experiences the largest possible forgetting during each cycle. This would correspond to the case of significantly dissimilar but jointly separable tasks, as we illustrate in Appendix C.3 through a toy example.

Q4. Regarding the definition of cycle-averaged forgetting

• As you correctly pointed out, the convergence of $\mathcal{C}\mathcal{F}(J)$ to zero may not imply the convergence of the “conventional forgetting” to zero. There can be cases where $\mathcal{C}\mathcal{F}(J)$ decays to zero but the overall loss increases over cycles, hence resulting in larger and larger conventional forgetting. For the question “can you guarantee the model performs better on task $m$ in the current cycle $J$ than before?”, the answer is “not always.” We presented an example in Appendix C.3 where the loss on a certain task increases over some early stages of training. In Figure 9(a), one can see that the loss for Task 1 (green line) initially increases during early cycles.
• However, we can see from the Figure 9(b) that the loss eventually decreases, as predicted by our Theorem 3.3. Indeed, Theorem 3.3 guarantees that the total loss will eventually converge to zero, which also implies that the individual task losses will also converge to zero. From this, we expected that the model will eventually enter a stage where the individual task losses will monotonically decrease over cycles, in which case the cycle-averaged forgetting coincides with the conventional forgetting. Also, convergence of individual losses to zero already implies that the conventional forgetting will also eventually converge to zero. For these reasons, we chose to focus on the analysis of cycle-averaged forgetting.
• It is possible to extend our analysis of cycle-averaged forgetting to conventional forgetting. However, due to limitations of our proof techniques, the upper and lower bounds become looser as we have to accumulate the task alignment terms over multiple cycles.

Q5. Typo in Line 412

• Thank you for your careful reading. We reflected your suggestion to our updated manuscript.

---

References

• Doan et al., A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix, AISTATS 2021.
• Evron et al., How catastrophic can catastrophic forgetting be in linear regression?, COLT 2022.
• Ji et al., Gradient descent follows the regularization path for general losses, COLT 2020.
• Lin et al., Theory on Forgetting and Generalization of Continual Learning, ICML 2023.

We appreciate the reviewer for their insightful and positive review. Below, we address the reviewer’s concern and answer the raised questions.

W1. Limited setting: logistic loss and linear model.

• We remind the reviewer that logistic loss is a special case of cross-entropy loss for binary classification. Since cross-entropy loss shares the same shape as logistic loss, we should be able to extend our analysis to general multi-class classification as Soudry et al. (2018) did. We only considered the binary classification case just for simplicity of presentation.
• Due to its non-convexity, non-linearity, and the existence of local minima, theoretical understanding of deeper models is much more involved. In our work, we consider linear classifiers as a starting point of our theoretical analysis since they are more amenable to study. However, we believe some insights from our results can be extended to a larger model; for instance, when tasks are given repeatedly in a neural network setup, we expect that the total loss would eventually decrease even with the naive and problem-agnostic sequential GD algorithm. We plan to add an empirical verification of our claim later by the end of the discussion period.

W2. Lack of experiments, e.g., deep learning.

• Thank you for pointing this out. We plan to add some deep learning experiments later in our revisions. However, due to time constraint and computational burden, we will attach some of the results before the end of the discussion period, and will attach some other results later. Please check out our General Response handling all reviewer’s concerns about lack of experiments.

Q1. Intuition behind “Tight Exponential Tail” Assumption

• The tight exponential tail assumption means the loss gradient exponentially decreases as the prediction becomes more confident in the accurate direction. Loss functions such as logistic loss and cross-entropy loss satisfy this condition. Since those functions are practically used in classification, it is a standard assumption.
• Also, we would like to mention that the assumption is crucial in proving the desired directional convergence to the max-margin direction. If the loss function does not meet the tight exponential tail assumption, then it can induce a totally different implicit bias of the optimization algorithm (Ji et al., 2020).

Q2. Figure 1: Why all data have labels +1?

• In binary linear classification, a dataset $\\\{(x_i, y_i)\\\}$ which has labels $y_i\in \\\{-1,1\\\}$ is equivalent to a dataset $\\\{(y_i x_i, 1)\\\}$. That is, the two datasets result in exactly the same loss function, optimization trajectory, max-margin direction, etc. Thus, we choose all data to have labels +1 without loss of generality.

4. Deeper model: synthetic 2D data with ReLU nets

• Some reviewers including 1DCj pointed out that there are no deep learning experiments. To address the concern, we plan to train ReLU networks on our synthetic 2D datasets with sequential GD and see what will happen.
• For simple (e.g., 2D) datasets, in particular, there is a method for visualization of decision boundary of a neural network (Pezeshki et al., 2021). Observe that monitoring the trajectory of the parameter vector of a linear classifier is semantically equivalent to monitoring the evolution of decision boundary the model. Interpreting our implicit bias result as the convergence between decision boundaries of the continually learned model and a jointly trained model, we can also verify our theoretical insight through ReLU net experiments on 2D data by monitoring the decision boundary.
• Due to the time constraint, we are still running the experiments. We will update our manuscript before the discussion period finishes.
• (Update: 2024.11.25) Our new revision contains the experimental results with ReLU nets! Please check out our paper and an additional response below.

5. Large-scale experiments with even deeper models and more realistic datasets

• Continuing from the previous response (#4), we initially planned to conduct more experiments on various deep network architectures and more (high-dimensional) datasets other than synthetic ones. However, due to our constraints in time and computational resources, there was not enough time to build up a code base for these experiments.
• More importantly, as far as we know, it is not very straightforward which statement we should verify by these experiments. Considering a comparison between continually learned vs. jointly trained models (in terms of implicit bias), it is not really straightforward to judge whether two neural networks are close or not; for instance, simple L2 distance between parameter values is not enough for this because there can be many different model parameter configurations representing exactly the same mapping from input to output.
• Still, we believe we might be able to assess the (cycle-averaged) forgetting and loss convergence speeds for these realistic settings. We plan to include these results in a later revision.

We hope this general response will handle most reviewer’s concerns about lack of experiments. Thank you again for your time and effort in reviewing our work.

Best,

Authors

---

References

• Krizhevsky. “Learning Multiple Layers of Features from Tiny Images.” 2009.
• Pezeshki et al. “Gradient Starvation: A Learning Proclivity in Neural Networks.” NeurIPS 2021.

Dear all reviewers,

We just made an additional revision to our experiments and the paper, as we promised before. The updates in the paper are marked in green. Before describing the updates, please recall that the end of the discussion period is only a few days away. Since we have responded to all reviewers' concerns and incorporated corresponding changes in our revised paper, please look into our responses and the new manuscript. If these address your concerns, it would be appreciated if this could be reflected via updated assessments. If you have any remaining concerns or questions, we would be grateful to hear them and will do our best to address them as soon as possible.

For the rest of this official comment, we briefly summarize the key updates in our paper. Note that we also updated the codes provided in the supplementary material.

Overall changes throughout the paper

• We modified a bit misleading term "task similarity" into "task alignment" to capture the meaning of the terms $N\_{p,q}$ and $\bar{N}\_{p,q}$ in essence. For a detailed context on it, please refer to our response to the reviewer 1DCj's Q3.

Section 1: Introduction

• When describing a previous work (Evron et al., 2023), we toned down our previous criticism on it in the fourth paragraph, as per the reviewer a4PQ's suggestion.
• We slightly changed the visualization in Figure 1, which originally contained too many points and thus slowed down opening the paper. Instead of tracking every gradient update, we drew only the end-of-stage iterates in order to capture the stage-wise evolutions in each trajectory, which is enough to showcase the implicit bias of sequential GD in our toy example. The code for generating Figure 1 is modified as well, which can be found in our supplementary material.

Section 2: Problem setup

• As per the reviewer sGag's suggestion (Weakness 5), we cited explicit examples of cyclic and random task orderings.

Section 3: Cyclic Learning of Jointly Separable Tasks

• Figure 2: We conduct an experiment on a more sophisticated two-dimensional dataset and provide a clear visualization of the parameter trajectories, clearly exhibiting the expected implicit bias toward the joint max-margin in direction.
• Below Figure 2, we left comments about:
  • The experimental results on a more general continual learning setup where the total dataset is no longer fixed over time.
  • The experimental results with shallow (two-layer) ReLU networks.
• Figure 3: We provide a better visual description of the cases where the cycle-averaged forgetting is small ("aligned") and large ("contradict").

Section 5: Beyond Jointly Separable Tasks

• The original version of Lemma 5.1 misses the dependency on a parameter $G$ (introduced in Assumption 5.2): we corrected it.
• Below Theorem 5.2, We added a discussion on the loss convergence rate, naturally derived from the iterate convergence rate in the theorem.
• After that, we left a comment on a real-world dataset experiment (with CIFAR-10).

Appendix A: Other Related Works

• Due to the space limit, we moved this section to the very first appendix.

Appendix B: Brief Overview of Evron et al. (2023) and Comparisons

• We now provide a better description & discussion on Sequential Max-Margin (SMM) algorithm, especially in the last two paragraphs.
• We moved the plot about SMM (not converging to the joint max-margin in direction) to the next appendix (Appendix C).

Appendix C: Experiment Details & Omitted Experimental Results

• We put almost all experimental results produced during the discussion period in this appendix!
• All codes for generating every figure are now available in our supplementary material.
• Here is a list of experiments added during the discussion period:
  • More realistic synthetic 2D datasets + linear classifier, under cyclic and random task ordering. (Appendices C.2.1 - C.2.3, see #1 in our general response above.)
  • Constantly changing 2D datasets + linear classifier, under cyclic and random task ordering. (Appendix C.2.4, see #2 in our general response above.)
  • 2D dataset + two-layer ReLU nets. (Appendix C.4, see #4 in our general response above.) (NEW!)
    • Although we only present the cyclic ordering case in our paper, we had almost identical observations for random ordering and even under constantly changing datasets. You can find the plots in our supplementary material.
  • CIFAR-10 + linear classifier. (Appendix C.5, see #3 in our general response above.)

Again, we thank all the reviewers for their time and effort in reviewing our work. We hope these revisions address your concerns. Please do not hesitate to leave more comments and questions if you have any.

Warm regards,

Authors