- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the difference in the predictors obtained via SGD and offline kernel regression. They argue that by supplying SGD with modified targets, one can recover the offline estimator exactly. They further demonstrate improvements in continual learning experiments on MNIST, CIFAR-10, and CORe50 using the corrected targets.
Critical strengths
The paper provides an interesting perspective on how the predictors obtained via online SGD and offline kernel regression differs. Their proposed idea of correcting the targets so that online algorithm recovers the offline predictor exactly is also something that I found interesting. Experiments on continual learning benchmarks provides empirical evidence of the benefits of such (iterative) corrections.
Critical weaknesses
My main concern is that why does the fact that online learner finds a different predictor than offline learner posed as a critical limitation of online learning? Online algorithms are already known to enjoy strong regret guarantees and optimal convergence rates on excess risk via online to batch conversion. Therefore, deviation from the offline solution does not necessarily imply statistical suboptimality, and it is unclear why correcting for this discrepancy is necessary.
Also theoretical and experimental comparisons with stronger online algorithms such as online KRR and kernelized Online Newton Step are not studied. This makes it hard to accurately judge if target correction mentioned in the paper is something fundamentally meaningful or whether it is merely a mechanism to correct for the limitations of the particular online update rule they study. Further there are online algorithms with optimal strongly-adaptive / dynamic-regret guarantees which are particularly suited for problems with adversarially changing data distribution. Comparison to such methods will also be insightful.
Questions for authors
Please see the section on Critical Weaknesses.
W1: My main concern is that why does the fact that online learner finds a different predictor than offline learner posed as a critical limitation of online learning?...
We agree that a discrepancy between online and offline predictors does not necessarily imply suboptimality. However, we respectfully disagree that existing regret and convergence guarantees eliminate the importance of understanding and correcting this discrepancy, particularly in non-i.i.d. learning settings.
First, classical online-to-batch conversion results (e.g., Cesa-Bianchi et al., 2004) establish statistical generalization guarantees under i.i.d. sampling assumptions. Although some online learning algorithms satisfy regret guarantees even for arbitrary sample sequences, these guarantees do not necessarily imply that the final online predictor matches the offline solution or achieves comparable test performance under distributional shift (see our reply to W2 below). As emphasized in our Introduction, our primary interest is online learning under non-i.i.d. data streams, where distributional shift is common. A prominent example is continual learning, in which different tasks or classes are learned sequentially. By construction, the training data in such settings are not sampled i.i.d.
To illustrate this distinction, consider the class-incremental MNIST experiment in Fig. 2. Here, the network first learns from images of digit 0, then digit 1, and so forth, rather than receiving samples randomly drawn from all classes. Although this benchmark is synthetic, it captures an important aspect of distributional shift encountered in practical applications, including medical diagnosis and face recognition.
Fig. 2D compares the test accuracy of offline learning (blue dashed line), vanilla online learning (orange line), and online learning with target correction (green and red lines), evaluated on the MNIST test set containing all ten digits. Vanilla online learning consistently underperforms its offline counterpart, demonstrating that the discrepancy between online and offline solutions is associated with a substantial performance gap in this setting. By contrast, exact target correction recovers the offline performance at the end of learning, as shown in Theorem 4.1, while iterative target correction also substantially improves performance over vanilla online learning. Moreover, a similar, though smaller, discrepancy is observed even under i.i.d. sampling (Fig. 2C), indicating that the effect is not restricted to non-i.i.d. settings.
Our main contribution is to establish implicit target shift as a framework for understanding the discrepancy between online and offline solutions in feature-based learning, and to develop methods to correct it. Our numerical experiments further demonstrate that this perspective may offer algorithms for practical learning tasks with distributional shift. We therefore believe that the established regret and convergence guarantees for online learning does not contradict with the motivation and contributions of our work.
W2: Also theoretical and experimental comparisons with stronger online algorithms such as online KRR and kernelized Online Newton Step are not studied.
Thank you for raising an interesting point. Online learning algorithms with regret guarantees under arbitrary sample orders, such as Online Newton Step, could potentially be useful for online continual learning, as you suggested. However, to the best of our knowledge, such algorithms have received relatively little attention in the continual learning literature.
In the newly added Figs. 5A and B (p. 27 in Appendix of the revised manuscript), we compared iterative target correction with Kernelized Online Newton Step (KONS) on MNIST under random and class-incremental sample orders, using a ConvNet-based NTK. As before, we optimized the hyperparameters of each algorithm over logarithmically spaced grids. We did not include recursive kernel ridge regression (KRR) in this comparison because exact recursive KRR recovers the corresponding offline KRR solution, rather than approximating it through sequential gradient updates. Thus, unlike iterative target correction, it does not directly address the question of how to improve gradient-based online learning.
KONS outperformed vanilla online kernel regression in both settings, but generally performed worse than iterative target correction, except in the later phase of learning under random sample order (brown vs. red lines in Fig. 5A). Thus, iterative target correction showed an advantage even over this stronger online learning algorithm, particularly in the class-incremental setting. One possible explanation is that, although iterative target correction relies on first-order gradient updates, the correction mechanism incorporates additional information into the learning targets, which helps compensate for the limitations of standard online updates.