Research map / Learning theory and algorithms / Kernels and regression theory
Are Greedy Task Orderings Better Than Random in Continual Linear Regression?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes greedy (maximum distance and maximum residual) task orderings for continual linear regression under joint realizability, showing they beat random orderings empirically but can fail catastrophically in single-pass general-rank settings while greedy orderings with repetition converge at O(1/k^{1/3}).
Problem
Understanding how task ordering affects forgetting and loss convergence in continual learning, specifically whether similarity-guided (dissimilarity-maximizing greedy) task orderings beat random orderings.
Approach
Formalizes greedy dissimilarity-maximizing task orderings (Maximum Distance and Maximum Residual) via the Kaczmarz/projection view of continual linear regression, proves optimality and loss bounds for high-rank tasks, constructs adversarial single-pass failure cases, and shows repetition yields a dimension-independent bound.
Key results
- On random regression (T=50, r=10, d=100), greedy MD and MR orderings converge faster than random orderings in average loss, with MD and MR comparable.
- Single-pass greedy orderings can suffer Omega(1) loss (at least 1/8 - 1/(4d)) in adversarial constructions with T=d-1 tasks, while random orderings achieve O(1/sqrt(k)).
- Greedy orderings with repetition achieve an O(1/k^{1/3}) loss bound independent of dimension.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy dissimilarity-maximizing task orderings instead of random ordering | Continual linear regression on isotropic random data · Synthetic regression tasks | average loss | Helped |
| Use greedy dissimilarity-maximizing task orderings instead of random ordering | CIFAR-100 continual binary classification · CIFAR-100 | average test loss | Helped |
| Use Maximum Residual instead of Maximum Distance | Continual linear regression on isotropic data · Synthetic regression tasks | average loss | Hurt |
| Use Maximum Distance with repetition instead of single-pass Maximum Distance (ablation) | Continual linear regression · Random data | average loss | Helped |
| Allow task repetition in greedy ordering (ablation) | CIFAR-100 continual classification · CIFAR-100 | average test loss | Hurt |
| Remove regularization toward previous parameters (ablation) | Continual classification with task orderings · CIFAR-100 | average test loss | Hurt |
| Calculate Maximum Residual using only 1% of the data (ablation) | Greedy Maximum Residual · CIFAR-100 continual classification | average test loss | No clear effect |
| Switch from greedy selection to random ordering when update decrements fall below a threshold | Hybrid ordering · Continual learning | average loss | Mixed |
| Use single-pass greedy ordering instead of random ordering | Continual linear regression on adversarial task collections · General-rank regression | average loss: \ge \tfrac{1}{8}-\tfrac{1}{4d} | Hurt |
| Use Maximum Distance with repetition instead of single-pass greedy ordering (ablation) | Continual linear regression · General-rank regression | average loss: \bigO\bigprn{\hfrac{1}{\sqrt[3]{k}}} | Helped |
Surprising findings
- Single-pass greedy orderings may fail catastrophically, unlike random orderings without replacement, which converge.
- Allowing repetition hurts greedy orderings on CIFAR-100 classification, canceling their advantage over random orderings.
Limitations
- Analysis assumes joint linear realizability of training data, which the CIFAR-100 experiments only approximately satisfy.
- Greedy MD rule is costly to compute in general; MR is cheaper but its benefits vary with data correlation (underperforms on anisotropic high-rank data).
- Theoretical separation results are for linear regression and not extended to replay or regularization methods.
Experimental setup
Datasets: CIFAR-100 CIFAR-10
Benchmarks: CIFAR-100
Metrics: average loss across tasks distance to joint solution
Baselines: random ordering random ordering with replacement minimum distance ordering joint training
Builds on: Kaczmarz method random orderings without replacement analysis in continual linear regression similarity-guided task orderings (Bell et al.)
Closest papers by meaning
- Optimal Rates in Continual Linear Regression via Increasing Regularization (NeurIPS 2025 · similarity 0.92)
- Optimal Task Order for Continual Learning of Multiple Tasks (ICML 2025 · similarity 0.88)
- A Statistical Theory of Regularization-Based Continual Learning (ICML 2024 · similarity 0.87)
- Convergence and Implicit Bias of Gradient Descent on Continual Linear Classification (ICLR 2025 · similarity 0.87)
- LoRanPAC: Low-rank Random Features and Pre-trained Models for Bridging Theory and Practice in Continual Learning (ICLR 2025 · similarity 0.86)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.