✗ Mechanism failed 2026

Heavy-Tail Path-Adaptive Optimizer Pool

Implementation & benchmark of arXiv:2607.27073 — Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

Usefulness7/10
Difficulty5/10
Novelty6/10

Source paper: Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise arXiv:2607.27073 ⓘ · analyzed Aug 31, 2026

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

Idea description

Replace one fixed optimizer time scale with a geometric pool of restarted AdaGrad trajectories, and adaptively combine them online. Short-window experts react quickly when the fine-tuning optimum moves, while long-window experts average noisy gradients; the meta-controller shifts weight between them without requiring a known noise scale, path length, or horizon.

Formulas

$$\widetilde{O}\left(GD\sqrt{T(1+P_T/D)}+\sigma DT^{1/p}(1+P_T/D)^{(p-1)/p}\right)$$
$$P_T=\sum_{t=2}^{T}\lVert u_t-u_{t-1}\rVert,\qquad \mathrm{D\text{-}Regret}_T=\sum_{t=1}^{T}\left[\ell_t(x_t)-\ell_t(u_t)\right]$$
$$x_{t+1}^{(k)}=\Pi_{\mathcal X}\left[x_t^{(k)}-\eta_{k,t}g_t^{(k)}\right],\qquad \eta_{k,t}=\frac{\alpha}{\sqrt{\epsilon+\sum_{s\in B_k(t)}(g_s^{(k)})^2}}$$
$$\bar{\ell}_t=\sum_{k=1}^{K}q_{k,t}\hat{\ell}_{k,t},\quad z_{k,t}=\hat{\ell}_{k,t}-\bar{\ell}_t,\quad v_{k,t}=v_{k,t-1}+z_{k,t}^{2},\quad q_{k,t+1}=\frac{q_{k,t}\exp\left(-\beta z_{k,t}/\sqrt{\epsilon+v_{k,t}}\right)}{\sum_j q_{j,t}\exp\left(-\beta z_{j,t}/\sqrt{\epsilon+v_{j,t}}\right)}$$

Mathematical statement

The paper targets universal dynamic regret, defined for decisions x_t in a convex set X of diameter D and a comparator sequence u_1,...,u_T by D-Regret_T = sum_{t=1}^T [ell_t(x_t)-ell_t(u_t)]. Its stated guarantee is \widetilde{O}(GD\sqrt{T(1+P_T/D)} + \sigma D T^{1/p}(1+P_T/D)^{(p-1)/p}), where G is the Lipschitz constant of each convex loss, sigma controls stochastic-gradient noise, p in (1,2] is the finite central-moment order, and P_T = sum_{t=2}^T ||u_t-u_{t-1}|| is comparator path length. The construction combines restarted AdaGrad experts with geometrically spaced block lengths and a pathwise AdaGrad-Hedge meta-algorithm. For a directly implementable neural adaptation, expert k uses block length H_k=2^k and the diagonal AdaGrad update x_{t+1}^{(k)} = Pi_X[x_t^{(k)} - eta_{k,t} g_t^{(k)}], eta_{k,t}=alpha/(epsilon+sum_{s in current block} (g_s^{(k)})^2)^{1/2}, with elementwise squaring and division. The meta-loss is the expert validation loss ellhat_{k,t}; define the weighted loss ellbar_t=sum_k q_{k,t}ellhat_{k,t}, centered excess z_{k,t}=ellhat_{k,t}-ellbar_t, accumulator v_{k,t}=v_{k,t-1}+z_{k,t}^2, and normalized update q_{k,t+1} proportional to q_{k,t} exp[-beta z_{k,t}/sqrt(epsilon+v_{k,t})]. Here Pi_X is projection onto a parameter trust region, alpha and beta are dimensionless step scales, epsilon prevents division by zero, and q_{k,t} are normalized nonnegative expert weights.

Implementation notes

1. Integration point: apply this to a parameter-efficient fine-tuning module rather than an entire billion-parameter model. Use a frozen backbone plus one LoRA adapter or final classification head, and create K=5 or 6 copies of only that trainable parameter tensor. Set H_k=2^k optimizer steps, for example 16, 32, 64, 128, 256, and 512; each expert resets its AdaGrad accumulator and adapter parameters at the end of its block, either from the current weighted model or from a fresh checkpoint. At each minibatch, compute the shared backbone activations and per-expert adapter outputs, obtain gradient g_t^(k), and evaluate each expert on a small held-out minibatch to obtain scalar loss ellhat_k,t. 2. Pseudocode: initialize q_k=1/K, v_k=0, accumulator A_k=epsilon, and adapter theta_k. For each step t, compute g_k=grad(loss_train(theta_k)); A_k <- A_k + g_k squared; theta_k <- project(theta_k - alpha*g_k/sqrt(A_k)); compute ellhat_k on validation data; bar <- sum_k q_k*ellhat_k; z_k <- ellhat_k-bar; v_k <- v_k+z_k^2; q_k <- normalize(q_k*exp(-beta*z_k/sqrt(epsilon+v_k))); if expert age equals H_k, restart it and reset A_k and v_k. Produce the deployed prediction using the highest-q expert, or q-weighted logits for a cheaper ensemble. 3. Computed from the paper's mathematics: geometric block lengths, AdaGrad normalization, pathwise centered meta-losses, and parameter-free operation with respect to unknown drift and noise. Estimated empirically: the effective path length is not needed by the algorithm; monitor it afterward as sum_t ||theta_bar_t-theta_bar_(t-1)||, and estimate heavy-tail behavior from minibatch gradient norms using quantiles or a log-log tail plot. Use gradient accumulation or one shared backward pass where possible to reduce the K-fold cost. 4. First experiment: fine-tune a 2-layer MLP or ViT-small final head on CIFAR-10 with a distribution shift every 2,000 examples, comparing AdamW, AdaGrad, cosine-scheduled SGD, and the expert pool at equal total backward FLOPs. Add synthetic heavy-tailed noise g <- g + sigma*StudentT_p noise with p=1.3 and p=2.0. Measure cumulative validation loss, worst-window loss after shifts, final accuracy, gradient-spike frequency, and wall-clock overhead. Success is faster recovery after shifts, fewer catastrophic loss spikes, and higher accuracy than AdamW at equal training compute; under stationary Gaussian noise, the pool should not lose more than 1% accuracy.

Verification

Mechanism failed

Stage 1 · Toy mechanism gate: Failed ✗

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 9/10

Built a NumPy MVP of restarted diagonal AdaGrad experts with geometric horizons and the centered variance-normalized exponential meta-controller. Two quantitative checks matched the predicted mechanism: displacement had log-log slope 0.537 versus 0.5 for sqrt(H), and meta log-odds had slope 0.530 versus 0.5 with asymptotic ratios approaching 1. However, the dynamic recovery sweep did not show the claimed O(H) dependence (lags were 4, 6, 7, 7, 7, 8 for H=1,2,4,8,16,32), so the required mechanism criterion was not fully met; the exploratory comparison was also not equal-FLOP fair.

Agent confidence
9/10
Baseline
Shifted quadratic fixed AdaGrad: post-shift loss 6.19796, recovery lag 8 steps
Idea
Pool: post-shift loss 0.04840 +/- 0.00161, recovery lag 12.5 steps; the strong loss result is confounded by multiple expert updates and unequal compute

Limitations: Only a small scalar shifted-quadratic toy was tested; no neural fine-tuning, CIFAR, GPU, equal-backward-FLOP study, optimizer wall-clock analysis, or systematic heavy-tail noise-order sweep was performed. The restart implementation resets accumulators but does not reset expert parameters from the weighted model.

How to run: python3 optimizer_pool.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