Research map / Bandits and online learning / Online convex optimization and games

A second order regret bound for NormalHedge

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online allocation with constraints · 0 citations (OpenAlex)

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.

Shows a variant of NormalHedge (with backward-heat-equation potential and a t^{-1/2} factor) achieves an adaptive second-order epsilon-quantile regret bound sqrt(V_T log(V_T/eps)) using a continuous-time SDE motivation and local self-concordance analysis.

Problem

Prediction with expert advice for easy sequences: achieving quantile regret bounds that simultaneously adapt to cumulative variance V_T (second-order) without knowing epsilon or V_T, an open problem posed by Freund (COLT 2016) conjecturing NormalHedge does so.

Approach

Frames hedge algorithms as constant-total-potential algorithms with good potentials satisfying the backward heat equation; NormalHedge.BH uses potential t^{-1/2} exp(y^2/2t), with variance weighted by second derivative q, and the time increment is bounded via local generalized self-concordance of the log total potential.

Key results

• NormalHedge.BH satisfies Regret_eps(T) <= sqrt((t0+2V_T)(log(t0+2V_T)+2log(1/eps))) with t0 = max{512e^2 B^2 log N,1}, adaptively without tuning.
• Lower bound: for any algorithm, Regret_eps/sqrt(V_T/4) >= sqrt(2 log(1/eps)) - 6 for random-walk adversary with N=Theta(1/eps^2), so the upper bound is optimal up to a log V_T factor.
• Exponential weights with tuned eta achieves Regret_eps = O(B log(1/eps) + sqrt(V_T log(1/eps))).

Surprising findings

• The lower-bound construction of prior work (Orabona/Negrea-style impossibility for variance over actions) does not contradict the result because V_T is defined via the potential's second derivative q rather than p and an additive log N term is allowed.

Limitations

• Upper bound has an extra log(V_T) factor relative to the lower bound and an additive log N term from t0.
• Bound holds only for V_T > log N; the SDE analysis is informal and not rigorous.
• Requires a burn-in t0 depending on B and log N.

Experimental setup

Metrics: epsilon-quantile regret

Baselines: Hedge NormalHedge Squint Ada-Normal-Hedge AdaHedge Adapt-ML-Prod FTRL with adaptive regularizer

Builds on: NormalHedge Exponential weights (Hedge) Squint Self-concordance

Closest papers by meaning

• Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm (NeurIPS 2022 · similarity 0.89)
• Prediction with expert advice under additive noise (NeurIPS 2025 · similarity 0.88)
• Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance (ICML 2020 · similarity 0.88)
• When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses (NeurIPS 2025 · similarity 0.88)
• Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization (AAAI 2024 · similarity 0.86)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.86)