Primal-Dual Continual Learning: Stability and Plasticity through Lagrange Multipliers

We sincerely thank the reviewer for their time and feedback, and for their positive evaluation of our work.

• Sensitivity of $\lambda$

We believe that the sensitivity of $\lambda$ with respect to the forgetting tolerance $\epsilon$ and the hardness of the tasks is indeed a positive aspect of our approach. As mentioned in the general response, the regularization parameter associated to each rehearsal loss is meant to be adaptive. For instance, if the forgetting tolerance $\epsilon_k$ associated to task $k$ is relaxed, the effective difficulty of this task is reduced, decreasing its associated dual variable and leading to a smaller buffer partition. This adaptivity is the insight leveraged to partition the buffer and select samples.

• Re-computation of buffer partition.

Indeed, the buffer partition is computed at every iteration, which creates an additional cost with respect to fixed partitions. However, the computational overhead of running the Sequential Quadratic Programming algorithm is small (see Appendix A.8). More importantly, as mentioned in the previous response, the flexibility of recomputing the buffer partition after every iteration allows us to dynamically assess the relative difficulty of the observed tasks, which is a key positive aspect of the proposed approach.

As mentioned in Section 7, there are two non-efficient ways of addressing the problem of dual variable underestimation. Namely, one can fill the empty portion of the buffer with either augmented samples from the previously selected ones or samples from the current task, whose dataset is entirely available.

• Number of constraints

The number of constraints in our formulation of continual learning can be equal to the number of tasks or the number of samples. In the sample-level setting, our experiments show that one can effectively train constrained continual learners with up to 100000 constraints (Tiny-ImageNet). In view of the challenges and novel techniques deployed in this paper, we leave the experimental validation on larger datasets (e.g., ImageNet) as future work.

We thank the reviewer for their feedback and for the positive evaluation of our work.

• On the indirectness of empirical comparisons.

Indeed, the effect of adaptive weights for replay losses (as opposed to fixed hyperparameters) is evaluated only indirectly, along with the buffer partition strategy. We agree with the reviewer in that adding the explicit comparison against a primal-dual method that uses the same buffer partition as ER is pertinent (we refer to it as PD w. Reservoir). We provide the preliminary results of this comparison here (CIL setting) and will add the full experiments to the revised version. The main conclusion appears to be that adaptive weights alone provide an improvement with respect to fixed ones. Indeed, in the case of SpeechCommands with a buffer size of 2000, virtually all the gains are explained by the adaptivity of the task-loss weights. However, in many cases, this does not explain the performance improvement entirely.

Regarding the baseline Experience Replay, we use the standard implementation from (Chaudhry et al, 2019). At each iteration, a batch of samples from the buffer and a batch of samples from the current task are merged. This larger batch is used to perform a forward pass and to compute the gradient of the loss with respect to $\theta$. Thus, the relative weight associated to each task loss is proportional to the number of samples of that task available in the buffer. For instance, when using a uniform partition, the relative weights are also uniform.

Chaudhry, A., Rohrbach, M., Elhoseiny, M., Ajanthan, T., Dokania, P.K., Torr, P.H. and Ranzato, M.A., 2019. On tiny episodic memories in continual learning. arXiv preprint arXiv:1902.10486.

• Distinction task versus class incremental learning.

We follow the formulation of class and task incremental learning of (Boschini et al. 2022), as implemented by the continual learning library Mammoth (https://github.com/aimagelab/mammoth). In this implementation, only the evaluation procedure is affected. The reviewer is correct in that this implementation provides an approximation to the TIL setting since it does not affect the training procedure. When evaluating the model in the TIL setting, only the relevant classes are taken into account. In CIL, however, the predictor can select any of the previously observed categories. We will clarify this distinction in the revised version. We will add the citation to the mentioned reference (van de Ven et al., 2022) and clarify this in the revised version.

Boschini et al, 2022. Class-Incremental Continual Learning into the eXtended DER-verse

• Other comments

Thank you very much for pointing these out. We will correct the formatting issues and appendix references in the revised version.

Thank you for responding to my review. I appreciate the additional experiment in which a direct comparison is performed between "standard ER" and "adaptive weights for replay". I note that the outcome of this experiment seems to challenge, at least to a certain degree, the conclusions from the original submission regarding the benefit of buffer partitioning.

Although I think that a difference in performance between "standard ER" and "adaptive weights for replay" would also be an interesting finding, I think it is unfortunate that based on the currently communicated results it is unclear which conclusions can be drawn from the experiments.

By proposing a principled framework for directly addressing continual learning as a constrained optimisation problem, I still think this paper makes an interesting and insightful contribution, and therefore has enough merit to be accepted. However, the current incompleteness of the results, and the resulting ambiguity with regards to what conclusions the authors will be able to draw, prevent me from raising my score further.

Further, reading the other reviews and the author rebuttals to them, I was surprised that the authors seem to find that A-GEM performs substantially better than "standard ER". (Comparing the results reported in the rebuttal to reviewer "Heyc" with the results reported in the rebuttal to my review.) I have not come across experiments before in which A-GEM clearly outperforms "standard ER". Based on my reading of the literature, it seems to be usually the other way around (e.g., De Lange et al., 2022; https://ieeexplore.ieee.org/abstract/document/9349197 or Van de Ven et al., 2022; https://www.nature.com/articles/s42256-022-00568-3). I think it would be good if the authors double-check their results, and if they are indeed correct, it would be useful to discuss why their results might differ from the ones in the above articles.

We thank the reviewer for their comments and acknowledgment of the contribution of the principled constrained learning framework. We are in agreement about the benefits of analyzing a Primal Dual method with no buffer partition to further assess the impact of adaptive weights. Regarding the extra baseline A-GEM. Indeed, it is well-known that the original version of A-GEM is outperformed (in many cases by a large margin) by ER, both with reservoir and ring buffer, as reported in: [On Tiny Episodic Memories in Continual Learning. Chaudhry et al. 2019]. Thus, it is not uncommon to use A-GEM gradient updates but to augment its loss with a replay term. This can be thought of as a mixture of strategies (AGEM with ER), present in some Continual Learning code bases, and recently formalized in [Two Complementary Perspectives to Continual Learning: Ask Not Only What to Optimize, But Also How. Hess, Tuytelaars, van de Ven]. We apologize for the confusion and will revise our response to clarify that this is the version of A-GEM used.

We thank the reviewer for their time and detailed feedback. In what follows, we provide answers and clarifications to the weaknesses and questions raised.

• Regarding Theorem 3.2/5.1 and the sub-differential $\partial P^*_t(\epsilon_k)$.

In this setting, the perturbation function $\partial P^{\star}\_t(\epsilon_k)$ is a convex function of the constraint upper bounds $\epsilon$. This is a well-known result from convex optimization (see e.g., (Bonnans & Shapiro, 1998) or (Rockafellar, 1997, Theorem 29.1)), and we agree with the reviewer in that it is pertinent to mention it before Theorem 3.2. We will also update the notation of the subdifferential to $P^*_{\epsilon_k}(\epsilon)$ as suggested to avoid confusion.

One could motivate the buffer partition approach without this sensitivity result. Note that dual variables accumulate the slacks (task-level constraint violations) over the continual learning procedure. Thus, it is not surprising that they carry information about task difficulty and that they can be used to manage the buffer. However, Theorem 3.2 provides a complete description of the induced task difficulty metric. Theorem 3.2 tells us that dual variables capture the minimum rate of degradation of the performance on the current task, when tightening the forgetting requirement in a previous task. This translates into a principled measure of how hard maintaining the performance in a past task is, relative to other observed tasks. Thus, we believe that Theorem 3.2 is a key component of this paper. We also provide an experimental interpretation of Proposition 5.1 (see Figure 3.b).

• On the estimation of dual variables.

Since we only have access to samples (not probability distributions) and we optimize over model parameters (not functions), in practice, we solve the empirical problem $(\hat{D}_t)$ instead of $P_t$. This corresponds to analyzing estimation and approximation errors of constrained learning, as done by e.g., (Vapnik 1999) or (Shai-Shalev Schwarz 2014) for supervised learning. For constrained learning, these errors were characterized, to a certain extent, in (Chamon et al. 2023). Theorem 4.2 bridges the gap between the optimal dual variables of $(P_t)$ and $(\hat{D}_t)$.

For the distance between these dual variables to be bounded, the dual function $g_u$ can not be flat. Observe that $g_u$ is the minimum of a family of affine functions; thus, it is concave, irrespective of whether the primal problem is convex. For it to be strongly-concave, we require three extra assumptions. Namely, strong convexity and smoothness of the loss and full-rankness of the constraint Jacobian.

The first two (strong convexity and smoothness) are widely used to prove convergence results for gradient descent algorithms even in the convex setting and are satisfied by typical losses used in ML when, e.g., the hypothesis class $\mathcal{F}$ is compact. Note that we require convexity of the objective with respect to the functionals, but not model parameters, which holds for both mean squared error and cross-entropy loss.

Although harder to guarantee, Assumptions 3.7 is a constraint qualification called LICQ (Linear Independence Constraint Qualification), which is ubiquitous in constrained optimization (Bertsekas 1995). The independence of the columns of $D_f \ell (f^*)$ reflects that, at the optimum, the constraints are not redundant and that they contribute in different ways to reach the optimal point. Although this is probably the stricter assumption, we believe that it can be lifted, being replaced by a stronger version of strict feasibility, but this is not immediate. With these assumptions, we can guarantee that $g_u$ is not linear, and that the optimal dual variables of $(P_t)$ and $(\hat{D}_t)$ are not too far away.

Although improvements to this bound could be obtained, we leave them for future work. We believe that the current version of the bound theoretically grounds the use of dual variables as sensitivity indicators.

• Other comments

We agree with the reviewer regarding the lack of comments on how the proof of Theorem 3.2 relates to the proof of Proposition 5.1 (i.e., sample-level sensitivity). These modifications are very minor since the only difference between Theorem 3.2 (task-level sensitivity) and Proposition 5.1 (sample-level sensitivity) is the dimensionality of the input to $P^*_t(\epsilon)$. We will add these comments to the revised version. We will also fix the typos mentioned in the revised version and add citations on universal approximation results for neural networks (e.g., Hornik 1989).

Hornik, K., Stinchcombe, M. and White, H., 1989. Multilayer feedforward networks are universal approximators. Neural networks, 2(5), pp.359-366.

Chamon, Luiz FO, et al. "Constrained learning with non-convex losses." IEEE Transactions on Information Theory 69.3 (2022): 1739-1760.

We greatly appreciate the reviewer's feedback. We strongly encourage them to read our general response to all reviewers as it will clarify the main motivations and contributions tackled by our work. We hope that our answers below will clarify specific points that might have been missed.

• On the availability of samples during training.

The notation used could have led to some confusion regarding the availability of samples during the execution of the Primal-Dual iterations and buffer partition. As explained in section 2, at iteration $t$, the following are available:

1. Samples associated to task $t$.

2. Samples from tasks $1, \dots, t-1$ that where stored in the buffer: $\mathcal{B}\_t = \cup_{k=1}^{t-1} \mathcal{B}\_t^k$ where $\mathcal{B}_t^k$ denotes the subset of the buffer allocated to task $k$ at iteration $t$.

This is the standard memory-based continual learning setting [1], where one can store a subset of the samples from previous tasks, revisiting them at future iterations. We will clarify this in the algorithm.

[1] GM van de Ven, Three types of incremental learning, 2022.

• On the computation of $\mathbf{\lambda}$ at each iteration.

Indeed, at each iteration $t$, we undertake the dual problem $\hat{D}_t$, from which we obtain a vector of dual variables $\mathbf{\lambda}$. This means that we assess the relative difficulty of the observed tasks and compute a new buffer partition at each iteration. However, we do not require access to the entire dataset of a previous task to compute this partition. Instead, it is estimated using the set of samples $\mathcal{B}_t$ stored in the buffer. As mentioned in section 7, this can give rise to the issue of dual variable underestimation.

• On the sub-optimality of $\theta^*$.

Indeed, the loss landscape on the parameter $\theta$ is non-convex, creating a duality gap. In other words, the value of the dual problem $\hat{D}^{\star}_t$ need not be a good approximation of the value of the primal problem $P^\star_t$. However, as mentioned in section 3, this was tackled in (Chamon et al, 2022, Theorem 1):

$| P^\star_t - \hat{D}^{\star}_t | \leq (M\nu+\zeta)(1+ \Delta ) \text{,}$ where $\Delta= \text{max} ( \Vert \tilde{\lambda}^* \Vert, \Vert \hat{\lambda^*} \Vert )$ and $\zeta = \text{max} \zeta_i(N_i, \delta)$ (see section 4.2 for the definition of $\zeta_i$ ).

Constrained Learning with Non-Convex Losses, 2022. Luiz F. O. Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro.

• On the reported metric.

We report the Top-1 Error, which is simple 100-Average Test Accuracy. We report this both in the Task Incremental Setup and Class Incremental Setup, both of which are standard in the continual learning literature. For completeness, we will add accuracy to the revised version in the Additional Experiments Appendix.

• On the baselines.

We agree with the reviewer that A-GEM is a relevant baseline. We attach the results of A-GEM on SpeechCommands here and will include them on the rest of the datasets in the camera-ready version. A-GEM appears to perform worse than PDCL on the Task Incremental setting (~2%), and slightly better on the Class Incremental setting.

Thank you for the thoughtful response. I have further questions to clarify as follows.

On the availability of samples during training

I have already understand that the main procedure of memory-based continual learning, so my main concern was that it is not clear how the data points of the current task $t$ stores in the buffer $B_t^t$ in Algorithm1. More specifially, the inner loop iterates $n_{iter}$ iterations on task $t$, which might allow the multiple epochs for task $t$ by the definition. After the inner loop, the samples that will be stored are chosen by the partition rule in line 11. It seems that some weird points can be arised as follows.

• After fininsing to learn task $t$, the algorithm tries to store data points for task $t$, which have already been streamed.
• First, multi-epoch learning is not a standard protocol for continual learning (even in the stage of a certain task).
• Second, we cannot access the streamed data after line 9, because the allowed memory size should be smaller than the size of dataset $D_t$.

By the above reason, building buffer at $t$ in line 11 does not make sense. I think the author should collect some data points in the inner loop with the memory limitation condition, then compute the buffer partition with a modified rule.

After reading the response, the computation $\lambda_t$ seems fair, but the authors should correct the statement of alogirhtm.

As far as I understand, there exists a critical mismatch in the experiment setting. GSS and Reservoir sampling are CL algorithms for online continual learning, but the experiments are conducted on the multi-epoch setting(Section A.7). This is not a fair comparison with baselines.

In addition, I still think that the author should report FWT and average ACC simultaneously in Figure 4.