Heavy-Tail Path-Adaptive Optimizer Pool
Implementation & benchmark of arXiv:2607.27073 — Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
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
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
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.