Research map / Optimization / Implicit bias and generalization
Optimal Rates in Continual Linear Regression via Increasing Regularization
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.
Shows that isotropic l2-regularized and finite-step-budget continual linear regression reduce to incremental GD on surrogate losses, yielding O(log k/k) for fixed regularization and an optimal O(1/k) for an increasing schedule under random task orderings.
Problem
Closing the gap between the best known O(1/k^{1/4}) upper bound for unregularized continual linear regression under random task orderings and the Omega(1/k) lower bound.
Approach
Reduce explicit l2-regularized and finite-step-budget continual regression to incremental gradient descent on smooth convex surrogate losses, then analyze SGD for time-varying objectives to obtain last-iterate O(1/k) rates with an increasing regularization schedule.
Key results
- Fixed regularization lambda = R^2(ln k - 1) yields expected loss bound 5||w0-w*||^2 R^2 ln k / k under random with-replacement orderings, versus O(1/k^{1/4}) for unregularized scheme.
- An increasing schedule lambda_t = (13R^2/3)(k+1)/(k-t+2) yields expected loss bound 20||w0-w*||^2 R^2/(k+1), matching the Omega(1/k) lower bound.
- Lower bound: any continual scheme incurs Omega(1/k) expected loss under random with-replacement orderings; isotropic regularization incurs Omega(1/k) seen-task loss under any coefficient sequence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the unregularized scheme with fixed regularization | Continual linear regression · Random with-replacement, jointly realizable tasks | worst-case expected loss rate: O(1/k^{1/4}) -> O(log k / k) | Helped |
| Replace fixed regularization with an increasing regularization schedule | Continual linear regression · Random with-replacement, jointly realizable tasks | worst-case expected loss rate: O(log k / k) -> O(1/k) | Helped |
| Use an increasing regularization coefficient schedule | Explicitly regularized continual linear regression · Random with-replacement, jointly realizable tasks | expected loss upper-bound rate: O(1/k) | Helped |
| Decrease the number of gradient steps per task over time | Finite-step-budget continual linear regression · Random with-replacement, jointly realizable tasks | expected loss upper-bound rate: O(1/k) | Helped |
| Use a fixed, horizon-dependent regularization strength | Explicitly regularized or finite-step-budget continual linear regression · Random with-replacement, jointly realizable tasks | expected loss upper-bound rate: O(log k / k) | Helped |
| Increase the fixed regularization coefficient with task angle in the two-task illustration | Explicitly regularized continual linear regression · Two-task setup | empirically optimal regularization coefficient | Mixed |
Surprising findings
- In a two-task numerical experiment, the empirically optimal fixed regularization grows roughly linearly with k, not logarithmically as the worst-case analysis suggests.
Limitations
- Analysis restricted to jointly realizable linear regression tasks with noiseless labels.
- Empirical validation on standard continual learning benchmarks is left to future work.
- Unregularized optimal rate remains open.
Experimental setup
Benchmarks: two-task numerical illustration of optimal fixed regularization
Metrics: expected worst-case loss upper and lower bound rates
Baselines: unregularized continual linear regression (Evron et al.) Incremental Proximal Method (cyclic) Constant-coefficient continual regression with C&D
Builds on: stochastic gradient descent last-iterate analysis incremental proximal method unregularized continual linear regression analysis (Evron et al.)
Closest papers by meaning
- A Statistical Theory of Regularization-Based Continual Learning (ICML 2024 · similarity 0.93)
- Are Greedy Task Orderings Better Than Random in Continual Linear Regression? (NeurIPS 2025 · similarity 0.92)
- Memory-Statistics Tradeoff in Continual Learning with Structural Regularization (ICLR 2026 · similarity 0.91)
- Convergence and Implicit Bias of Gradient Descent on Continual Linear Classification (ICLR 2025 · similarity 0.89)
- An Effective Dynamic Gradient Calibration Method for Continual Learning (ICML 2024 · similarity 0.89)
- Learning Continually by Spectral Regularization (ICLR 2025 · similarity 0.88)
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.