Research map / Learning theory and algorithms / Sample complexity
AKORN: Adaptive Knots generated Online for RegressioN splines
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.
Proposes AKORN, a parameter-free offline nonparametric regression method that uses change-points from an online TV1 denoiser (ADDLE) to select knots for a linear regression spline, achieving near-optimal instance-dependent rates.
Problem
Offline nonparametric regression over TV1-bounded functions normally requires tuning a smoothness hyperparameter (e.g., trend filtering) according to the unknown ground-truth smoothness; existing online-learning-based denoisers output non-smooth sequences of predictions rather than functions.
Approach
Run an online expert-aggregation denoiser (ADDLE, FLH over online linear regression experts) forward and backward over the data, place knots where its predictions drift from local linear fits (change-points), union forward/backward knots with crossover points, and fit a least-squares linear spline on those knots, yielding a parameter-free, adaptive, functional estimator.
Key results
- On the Doppler function, AKORN's empirical rate slope was about -0.91 versus -0.95 for oracle trend filtering and -0.7 on a highly irregular case where oracle trend filtering achieved about -0.84 (per Table 1 as reported).
- Theorem 6.2 shows AKORN's average squared error is O~(n^{-4/5} TV1[f]^{2/5}) with high probability without knowledge of TV1[f], and knot count O~(n^{1/5} TV1[f]^{2/5}).
- In MSE comparisons at n=1000 on the Doppler function, AKORN was competitive with oracle and DoF trend filtering and substantially better than wavelets (e.g., sigma=0.5: AKORN 0.007 vs oracle TF 0.0057, wavelets 0.046).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AKORN instead of Oracle Trend Filtering | Offline regression on PW-Lin · PW-Lin | estimated rate exponent: -0.95 -> -1 | Helped |
| Use AKORN instead of Oracle Trend Filtering | Offline regression on Doppler · Doppler | estimated rate exponent: -0.84 -> -0.91 | Helped |
| Use AKORN instead of Oracle Trend Filtering | Offline regression on Jump · Jump | estimated rate exponent: -0.37 -> -0.7 | Helped |
| Use AKORN instead of Oracle Trend Filtering | Doppler regression with σ=0.5 and n=1000 · Doppler (n=1000, σ=0.5) | MSE: 0.0057 vs 0.007 | No clear effect |
| Use AKORN instead of Wavelets | Doppler regression with σ=0.3 and n=1000 · Doppler (n=1000, σ=0.3) | MSE: 0.024 vs 0.0039 | Helped |
Surprising findings
- On the jump-type and highly irregular ground truths, AKORN outperformed even oracle-tuned trend filtering in the reported experiments.
- The online denoiser ADDLE alone performs much worse offline than AKORN, showing the knot-selection reduction is needed.
Limitations
- Only handles first-order TV1 classes; higher-order TVk extension is open.
- O(n^2) runtime for AKORN.
- Main theory assumes equally spaced covariates; uneven/random covariate extension requires modified VAW experts and extra assumptions.
Experimental setup
Datasets: synthetic piecewise-linear function Doppler function (Donoho & Johnstone) jump function simulated noisy observations
Benchmarks: piecewise-linear synthetic function Doppler function jump function
Metrics: MSE estimated convergence rate exponent (log-log slope)
Baselines: Oracle Trend Filtering DoF (SURE) Trend Filtering Wavelet soft-thresholding (Daubechies 2) ADDLE Local linear regression
Builds on: Aligator (Baby et al., 2021) Follow-the-Leading-History (Hazan et al., 2006) Trend Filtering (Tibshirani, 2014) Algorithm 5 of Baby et al., 2023 (low-switching)
Closest papers by meaning
- Adaptive Realizable Regression from Two Online Learners (NeurIPS 2026 · similarity 0.85)
- Adaptive Online Estimation of Piecewise Polynomial Trends (NeurIPS 2020 · similarity 0.84)
- Minimax Adaptive Online Nonparametric Regression over Besov spaces (NeurIPS 2025 · similarity 0.83)
- Adversarial Robustness of Nonparametric Regression (NeurIPS 2025 · similarity 0.83)
- Online Estimation via Offline Estimation: An Information-Theoretic Framework (NeurIPS 2024 · similarity 0.82)
- Adaptive Passive-Aggressive Framework for Online Regression with Side Information (NeurIPS 2024 · similarity 0.82)
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.