Mechanism works Re-invented 2026

Lag-Spectrum Online Newton

Implementation & benchmark of arXiv:2608.26515 — Sharp Minimax Regret for Infinite-Memory Logistic Prediction

Usefulness7/10
Difficulty4/10
Novelty6/10

Source paper: Sharp Minimax Regret for Infinite-Memory Logistic Prediction arXiv:2608.26515 · analyzed Aug 29, 2026

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

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.

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).$$

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.

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

Mechanism works

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not tested

Stage 2 · Practical benchmark result: Not run

Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works

Stage 1 — Mechanism check agent confidence 8/10

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.

Agent confidence
8/10
Baseline
AdaGrad: exponential cumulative log loss 1981.752, last-1000 loss 0.6522, coefficient MSE 0.003730; polynomial 2003.303, 0.6624, 0.003614. AdamW: exponential 2074.569, 0.6916, 0.022505; polynomial 2094.112, 0.7024, 0.020764.
Idea
Lag-Newton: exponential cumulative log loss 1966.641, last-1000 loss 0.6433, coefficient MSE 0.001638; polynomial 1991.130, 0.6543, 0.001617. The math checks gave Gamma=21.266, positive priors, valid curvature bound, and monotone H accumulation.

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.

How to run: python3 lag_spectrum_experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Artifacts

Implementation overview ⬇ Download all as ZIP 3 files · code, reports and structured results