On the Universal Near Optimality of Hedge in Combinatorial Settings

In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector boldsymbolxt from a set X subseteq 0,1d, observes a full loss vector boldsymbolyt ∈ ℝd, and incurs a loss langle boldsymbolxt, boldsymbolyt rangle ∈ [-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 Obig(√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,1d, Hedge is near-optimal--specifically, up to a √log d factor--by establishing a lower bound of Omegabig(√T log(|X|)/log dbig) that holds for any algorithm. We then identify a natural class of combinatorial sets--namely, m-sets with log d ≤ m ≤ √d--for which this lower bound is tight, and for which Hedge is provably suboptimal by a factor of exactly √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.