# Lag-Spectrum Online Newton

- ID: 201
- Canonical URL: https://synthcore.org/idea/201/lag-spectrum-online-newton
- API JSON: https://synthcore.org/api/idea/201.json
- API Markdown: https://synthcore.org/api/idea/201.md
- Verification status: mechanism_works
- Source: [arXiv:2608.26515](https://arxiv.org/abs/2608.26515)
- Category: optimization
- Solves: speedup, stability, sample-efficiency
- ML areas: rnn, ssm, optimizer
- Math tags: information-theory, online-learning, optimization
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace a uniform optimizer on the coefficients of a causal long-memory filter with a lag-aware diagonal Online Newton update. The diagonal curvature and prior scale of lag j are normalized using its number of available prediction rounds and envelope radius, so frequently useful recent lags learn rapidly while weak, old lags receive conservative updates.

## Mathematical statement

The source model has independent Rademacher inputs U_t in {-1,+1} and a binary conditional mark Y_{t+1} with logit z_t = sum_{j=1}^t theta_j U_{t+1-j}, where |theta_j| <= r_j and sum_j r_j <= B. A lag j appears in n_{T,j} = T-j+1 prediction rounds, and the paper's minimax spectrum is Gamma_T(r) = sum_{j=1}^T log(1 + n_{T,j} r_j^2). We transplant this as a diagonal prior and curvature scale. For feature x_{t,j} = U_{t+1-j}, prediction p_t = sigmoid(z_t), binary log loss l_t = -y_{t+1} log p_t - (1-y_{t+1}) log(1-p_t), gradient g_{t,j} = (p_t-y_{t+1})x_{t,j}, and logistic Hessian upper bound h_{t,j} = p_t(1-p_t)x_{t,j}^2 + 1/(n_{T,j}r_j^2+epsilon), use the Online Newton-style update theta_{t+1,j} = Proj_{[-r_j,r_j]}[theta_{t,j} - eta g_{t,j}/H_{t,j}], where H_{t,j} = H_{t-1,j}+h_{t,j}. The logarithmic accumulation of H_{t,j} is the operational analogue of the paper's log(1+n_{T,j}r_j^2) complexity contribution.

## Key formulas

- $$z_t=\sum_{j=1}^{t}\theta_jU_{t+1-j},\qquad p_t=\sigma(z_t),\qquad |\theta_j|\le r_j,\qquad \sum_{j\ge1}r_j\le B.$$
- $$n_{T,j}=T-j+1,\qquad \Gamma_T(r)=\sum_{j=1}^{T}\log\!\left(1+n_{T,j}r_j^2\right).$$
- $$g_{t,j}=(p_t-y_{t+1})U_{t+1-j},\qquad h_{t,j}=p_t(1-p_t)U_{t+1-j}^2+\frac{1}{n_{T,j}r_j^2+\varepsilon},$$
- $$H_{t,j}=H_{t-1,j}+h_{t,j},\qquad \theta_{t+1,j}=\operatorname{clip}_{[-r_j,r_j]}\!\left(\theta_{t,j}-\eta\frac{g_{t,j}}{H_{t,j}}\right).$$

## Implementation notes

Integrate this into the coefficient-learning part of a causal convolution, FIR filter, SSM input filter, or lightweight RNN whose preactivation is z_t = sum_j theta[j] times U[t+1-j]. Keep the hidden architecture unchanged and compare its coefficient optimizer against AdamW and ordinary diagonal AdaGrad. Inputs are a lag buffer U, target y, envelope values r[j], horizon T, learning rate eta, and epsilon. Initialize theta[j] = 0 and H[j] = 1/(n[j] times r[j]^2 + epsilon), with n[j] = max(T-j+1, 1). At each step t, form z as the sum over active lags, p = sigmoid(z), compute g[j] = (p-y) times U_lag[j], and add h[j] = p times (1-p) times U_lag[j]^2 + 1/(n[j] times r[j]^2 + epsilon) to H[j]. Update theta[j] by the displayed clipped Newton step; inactive lags j greater than t receive no update. If T is unknown, replace n[j] by a running count c[j] of times lag j has been active, and use c[j]+1 in the prior term. The paper supplies the lag complexity and motivates the horizon weighting; the Hessian diagonal and clipping are computable directly, while r[j] can be fixed from an assumed exponential or polynomial envelope or estimated from a pilot run. First test on synthetic binary data generated by exponential and polynomial filters, then on an online event-stream benchmark. Measure cumulative excess log loss, loss versus optimizer steps and FLOPs, coefficient recovery by lag, and stability under long contexts. Success means lower regret at equal compute, especially for old lags, without increasing peak memory.

## Verification

- Status: mechanism_works
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built Lag-Spectrum Online Newton with horizon-weighted diagonal prior curvature, clipping, AdaGrad, and AdamW baselines. The formula checks passed: nonnegative spectrum, positive prior, monotone curvature accumulation, and the logistic curvature bound. Across three fixed-seed runs for both exponential and polynomial filters, Lag-Newton had lower cumulative loss and substantially lower coefficient MSE than both baselines, so the effect is promising in this tiny synthetic setting.

### Mechanism check

- Verdict: Built Lag-Spectrum Online Newton with horizon-weighted diagonal prior curvature, clipping, AdaGrad, and AdamW baselines. The formula checks passed: nonnegative spectrum, positive prior, monotone curvature accumulation, and the logistic curvature bound. Across three fixed-seed runs for both exponential and polynomial filters, Lag-Newton had lower cumulative loss and substantially lower coefficient MSE than both baselines, so the effect is promising in this tiny synthetic setting.
- Confidence: 8/10
- Limitations: Only three seeds and two synthetic binary-filter families were tested. No real event-stream benchmark, wall-clock/FLOP profiling, long-context stress test, hyperparameter sweep, or statistically powered significance analysis was performed. The implementation uses a known finite horizon and does not test the running-count variant.

## Artifacts

- [lag_spectrum_experiment.py](https://synthcore.org/code/12/lag_spectrum_experiment.py)
- [report.md](https://synthcore.org/code/12/report.md)
- [results.json](https://synthcore.org/code/12/results.json)
- [Download all files as ZIP](https://synthcore.org/download/12)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.