{"ID":2852521,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17099","arxiv_id":"2510.17099","title":"On the Universal Near Optimality of Hedge in Combinatorial Settings","abstract":"In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector $\\boldsymbol{x}_t$ from a set $X \\subseteq \\{0,1\\}^d$, observes a full loss vector $\\boldsymbol{y}_t \\in \\mathbb{R}^d$, and incurs a loss $\\langle \\boldsymbol{x}_t, \\boldsymbol{y}_t \\rangle \\in [-1,1]$. This setting captures several important problems, including extensive-form games, resource allocation, $m$-sets, online multitask learning, and shortest-path problems on directed acyclic graphs (DAGs). It is well known that Hedge achieves a regret of $O\\big(\\sqrt{T \\log |X|}\\big)$ after $T$ rounds of interaction. In this paper, we ask whether Hedge is optimal across all combinatorial settings. To that end, we show that for any $X \\subseteq \\{0,1\\}^d$, Hedge is near-optimal--specifically, up to a $\\sqrt{\\log d}$ factor--by establishing a lower bound of $Ω\\big(\\sqrt{T \\log(|X|)/\\log d}\\big)$ that holds for any algorithm. We then identify a natural class of combinatorial sets--namely, $m$-sets with $\\log d \\leq m \\leq \\sqrt{d}$--for which this lower bound is tight, and for which Hedge is provably suboptimal by a factor of exactly $\\sqrt{\\log d}$. At the same time, we show that Hedge is optimal for online multitask learning, a generalization of the classical $K$-experts problem. Finally, we leverage the near-optimality of Hedge to establish the existence of a near-optimal regularizer for online shortest-path problems in DAGs--a setting that subsumes a broad range of combinatorial domains. Specifically, we show that the classical Online Mirror Descent (OMD) algorithm, when instantiated with the dilated entropy regularizer, is iterate-equivalent to Hedge, and therefore inherits its near-optimal regret guarantees for DAGs.","short_abstract":"In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector $\\boldsymbol{x}_t$ from a set $X \\subseteq \\{0,1\\}^d$, observes a full loss vector $\\boldsymbol{y}_t \\in \\mathbb{R}^d$, and incurs a loss $\\langle \\boldsymbol{x}_t, \\boldsymbol{y}_t \\rangle \\in [...","url_abs":"https://arxiv.org/abs/2510.17099","url_pdf":"https://arxiv.org/pdf/2510.17099v2","authors":"[\"Zhiyuan Fan\",\"Arnab Maiti\",\"Kevin Jamieson\",\"Lillian J. Ratliff\",\"Gabriele Farina\"]","published":"2025-10-20T02:05:22Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.GT\"]","methods":"[]","has_code":false}