Efficient Continual Finite-Sum Minimization

Thank you very much for all the work and the positive feedback on our work.

We just want to mention that the primary scope of our work was to formally frame and investigate the problem of efficient updates of models upon the arrival of new data. We agree with the reviewer that going beyond the strong convexity assumption is a very important and interesting research direction. Investigating the strong convex case serves as an important first step towards this direction while it already tackles several challenges and reveals surprising properties (especially with respect to lower bounds).

We would also like to remark that we have added additional experimental evaluations for NNs (see Appendix K and our response to Reviewer jqUD and Reviewer s2LS) revealing interesting results for SIOPT-Grad.

We hope that our work will instantiate a research direction towards investigating efficient update methods with favorable empirical and theoretical performance.

Thank you for your work and the positive feedback on our paper. We will incorporate all the minor issues and thank you for spotting them.

Concerning your question: We believe that considering projection-free methods that even with higher FO complexity may result in better running time due to the lack of a projection step, is a very interesting research direction.

We would like to thank the reviewer for their work and comments.

Up next we provide the intuition behind our algorithm in $3$ main steps.

• Main Intuition of VR methods

  The main idea of VR methods is to compute a full-gradient at an anchor point $\tilde{x}$, $\tilde \nabla := \frac{1}{n}\sum_{j=1}^n \nabla f_j(\tilde x)$ and use the following unbiased gradient estimator.
  $\nabla_t = \nabla f_j(x_t)- \nabla f_j(\tilde x) + \tilde \nabla \text{ with }j \sim \mathrm{Unif}(1,\ldots,n)$

  The main idea behind this estimator is that the closer $\tilde{x}$ is to the optimal point $x^\star$ the smaller the variance of $\mathbb{E}\left[||\nabla_t - \nabla g(x_t)||^2\right]$ where $g(x) = \sum_{j=1}^nf_j(x)/n$.

  In order to understand the latter let $\tilde{x} := x^\star$. Initializing the above process for $x^0 = x^\star$ results in $\nabla_0= \nabla g(x^\star)$ meaning that the method stands still on the optimal point. On the contrary SGD even initialized at $x^\star$ will move before converging back in general (e.g., without the strong growth setting).

• Straight-forward Approach in Instance-Optimal Finite-Sum Minimization

  In order to tackle Problem $2$, probably the most intuitive idea is the following. During stage $i \in [n]$, set the anchor point $\tilde x_i = \hat x_{i-1}$ (the previous output of the method) and compute $\tilde \nabla_i = \frac{1}{i}\sum_{j=1}^i \nabla f_j(\tilde x_i)$. Then during stage $i \in [n]$ perform SGD starting from the point $x^0_i := \hat x_{i-1}$ and use the estimator $\nabla_t^i = \nabla f_j(x_t)- \nabla f_j(\tilde{x}) + \tilde{\nabla}_i \text{ with }j \sim \mathrm{Unif}(1,\ldots,n).$

  The intuition behind this approach is that for large values of $i$, $\hat{x}_{i-1}$ is close to $x^\star_i$ (optimal solution of stage $i$) which implies that the variance reduction mechanism that we described above is activated leading to accelerated rates.

  To understand why $\hat x_{i-1}$ is close to $x^\star_i$, notice that $||x_{i-1}^\star - x_{i}^\star|| \leq O(1/i)$ (see Lemma $6$) while we can inductively assume that $||\hat x_{i-1} - x_{i-1}^\star|| \leq \epsilon$.

  The caveat of this approach is that computing $\tilde \nabla_i = \frac{1}{i}\sum_{j=1}^i \nabla f_j(\hat x_{i-1})$ at each stage $i \in [n]$ results in overall $O\left(\sum_{i=1}^n i\right) = O(n^2)$ FOs.

Thank you to the others for their response. I would encourage them to add some of the intuition in any future version of the paper.

The new MNIST experiments are quite interesting. It is nice how the performance of SI-OPT is always an upper envelope to the performance of SGD in the ascending labels experiment.

I read the review of reviewer Reviewer jqUd. It seems like they are quite knowledgeable about grading descent based algorithms. So I will momentarily hold off on any updates until they have a chance to respond about their proposed algorithm. I see how the exact stated algorithm does not work. But it is stated in quite informal terms, so maybe it can be easily modified. Let's give them a chance to respond.

We thank the reviewer for the work and the valuable comments.

• "I can’t connect Problem 2 with its motivation. For example ... past and the new data”

  We believe that some confusion might have been created due to the use of $n$ in both for Problem $1$ and Problem $2$. In many cases the overall $n$ data points are not available from the beginning and are rather gathered in an online fashion as the system is deployed to the public.

  We agree with the reviewer that if we had access to all $n$ data points from the beginning, we could directly solve Problem $1$. However our work is motivated from settings where only a small fraction of $n_1$ data points is available in the beginning and most $n-n_1$ data points are gradually revealed (for simplicity we set $n_1 =1$). To avoid confusion, we will use the notation $n_1$ to denote the initial data corresponding to Problem $1$.

  To further illustrate the motivation of our work in the next item we provide a concrete example in the context of continual learning.

• Concerning the motivation of our work

  Efficiently updating a model upon the arrival of "fresh data'' is a fundamental problem in ML. For example in continual learning models are initially trained with an initial set of data and then they are constantly updated so as to incorporate new tasks/data that arrive online. To clarify things let us provide a continual learning point of view with respect to the MNIST data set.

  Let us assume that we are initially given $n_1$ data points from MNIST with only $0$ and $1$ labels. The initial goal is to train a model with parameters $x$ to correctly classify $0/1$ digits. As a result, one needs to solve the following finite-sum problem (Problem $1$)

  $\min_x \sum_{j=1}^{n_1} f_j(x)/{n_1}~~\text{where }f_j(\cdot) \text { captures the respective loss of data point j.}$

  After training the model (solving Problem $1$), an additional data point arrives with label $2$ (additional task). Our goal now is to update $x$ so that our model correctly classifies the $2$-example while preserving its classification ability for $0/1$'s. Thus we need to solve the following similar but different finite-sum problem $\min_x \sum_{j=1}^{n_1+1} f_j(x)/(n_1+1).$

  Now imagine the above process to be repeated for a stream of $n_2$ data points of label $2$. Namely, after each model-update a new $2$-data point arrives that then needs to be incorporated in the model. As a result, for each $i=1,\ldots,n_2$, we need to compute $\hat x_i$ such that $\sum_{j=1}^{n_1 + i} f_j(\hat x_i)/(n_1+i) - \min_x \sum_{j=1}^{n_1+i} f_j(x)/(n_1+i) \leq \epsilon.$ The latter can continue for streams of $n_3,n_4,\ldots,n_9$ data points (corresponding to the respective labels). However resolving Problem $1$ from stratch (even with a state-of-the art VR method) every time a new data point arrives leads to a huge computational burden. That is the reason Problem $2$ asks for sequence of approximate solutions with mimimum number of overall FO calls.

  We remark that for the clarity of presentation, in Problem $2$ we set $n_1 = 1$ however our framework is directly extendable for general $n_1$. Moreover for the clarity of presentation we also focus on the case of a new data point arriving at each stage $i$, however our setting can be directly extended to the case where several data points arrive at each stage.

• Concerning the analysis of the algorithm that you propose

  1. If $x_{i+1}$ is $\epsilon$-minimizer of $g_{i+1}$ then it is an $(1 + 1/i)\epsilon$-minimizer of $g_i$.

     We must be missing some hidden assumptions in your statement as the above statement is simply not true. Let $\epsilon =0$ then the above statement says that a minimizer of $g_{i+1}(x)$ is also a minimizer of $g_i(x)$. That is clearly not the case: e.g., if you solve the very first data term to full accuracy, then you do not need to care about the incoming data in the future.

  2. The number of iterations required to find $x_i$ starting from $x_{i+1}$ is $O\left(\frac{ \log (1 + 1/i)}{\epsilon}\right)$.

     We do not see how the above expression is derived. Please clarify if you make some assumptions in order to reach these conclusions.

     We remark that even GD initialized at $x_0$ requires $O(\log ( ||x_0 - x^\star||/\epsilon))$ iterations, with each iteration requiring $i$ FOs.

     We additionally remark that SGD does not admit such warm-start guarantees (even outside log), $O( (f(x_0) - f(x^\star))/\epsilon)$ in general. The reason is that such guarantees would imply that SGD initialized at $x_0 := x^\star$ would stand still with probability $1$ that is clearly not the case.

In order to facilitate further discussion we attach some new plots from Appendix K of the revised version of the manuscript that display the performance of SIOPT on training 2-layer Neural Networks.

On the first plot we display the performance of our method on data streams produced by stationary distributions. As we see in the ridge regression case our method achieves performance similar to SVRG with much fewer FOs.

Stationary Distributions

On the rest of the plots we present the performance of our method on data streams with ascending labels, a problem setting motivated by continual learning. In this problem we initially wish to classify two labels (0s and 1s on MNIST) and then as time progress new classes are introduced to the dataset (digits 3, 4, 5, etc), this setting is similar to the one we discussed above as motivation for our work. SIOPT here achieves higher performance than SGD and adapts to the new tasks faster.

Ascending Labels

Ascending Labels Train Accuracy

Ascending Labels Test Accuracy

As the discussion period is concluding tomorrow, we would like to ask the reviewer if our replies have covered all of your concerns about our work.

We remain at your disposal for any questions.