Research map / Bandits and online learning / Online convex optimization and games
On the Universal Near Optimality of Hedge in Combinatorial Settings
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 Hedge is near-optimal (up to sqrt(log d)) for any combinatorial decision set in {0,1}^d, is suboptimal on m-sets, optimal on multitask learning and DAG paths, and that OMD with dilated entropy is iterate-equivalent to Hedge on DAGs.
Problem
Whether the classical Hedge algorithm (multiplicative weights over the set of combinatorial actions) achieves optimal full-information regret for every combinatorial decision set X in {0,1}^d.
Approach
Uses the Sauer-Shelah lemma to embed a hypercube of dimension Omega(log|X|/log d) in any combinatorial set, giving a universal lower bound; constructs a tailored OMD regularizer for m-sets that matches it while Hedge is provably sqrt(log d) worse; and shows dilated-entropy OMD on DAGs is iterate-equivalent to Hedge.
Key results
- Universal lower bound Omega(max{sqrt(T log|X|/log d), sqrt(T)}) for any algorithm on any combinatorial X in {0,1}^d, so Hedge is near-optimal up to sqrt(log d).
- For m-sets with log d <= m <= sqrt(d), Hedge incurs Omega(sqrt(T m log(d/m))) regret while an OMD regularizer achieves O(sqrt(Tm + T log(d/m))), a sqrt(log d) gap.
- Hedge is optimal for online multitask learning with Omega(sqrt(T log|X|)) lower bound, and OMD with dilated entropy is iterate-equivalent to Hedge on DAGs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Hedge on an arbitrary combinatorial set X ⊆ {0,1}^d | Combinatorial online learning · General combinatorial sets X ⊆ {0,1}^d | regret: Hedge: O(√(T log |X|)); any algorithm: Ω(max{√(T log |X| / log d), √T}) | Helped |
| Use OMD with the constructed regularizer instead of Hedge | Online learning over m-sets · m-sets | regret: OMD: O(√(Tm + T log(d/m))); Hedge: Ω(√(Tm log(d/m))) | Helped |
| Use Hedge on m-sets | Online learning over m-sets · m-sets, log d ≤ m ≤ √d | regret: Ω(√(Tm log(d/m))) | Hurt |
| Use Hedge for online multitask learning | Online multitask learning · Online multitask learning | regret: Hedge: O(√(T log |X|)); any algorithm: Ω(√(T log |X|)) | Helped |
| Use OMD with dilated entropy on DAG paths | Online shortest-path learning on DAGs · DAG source-to-sink paths | regret: O(√(T log |X|)) | Helped |
| Use OMD with dilated entropy instead of Hedge on DAG paths | Online shortest-path learning on DAGs · DAG source-to-sink paths | regret | No clear effect |
Surprising findings
- Hedge is provably suboptimal by a sqrt(log d) factor on m-sets, despite being near-optimal universally.
- Dilated-entropy OMD on DAGs is exactly iterate-equivalent to Hedge.
Experimental setup
Metrics: expected regret
Baselines: Hedge Kernelized MWU Component Hedge EXP2 with John's exploration ComBand
Builds on: Hedge Online Mirror Descent Kernelized MWU Component Hedge Sauer-Shelah lemma
Closest papers by meaning
- Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent (NeurIPS 2022 · similarity 0.88)
- Hedging in games: Faster convergence of external and swap regrets (NeurIPS 2020 · similarity 0.88)
- On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games (NeurIPS 2024 · similarity 0.87)
- Dynamic Thresholding and Pruning for Regret Minimization (AAAI 2017 · similarity 0.87)
- Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions (NeurIPS 2019 · similarity 0.87)
- Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.