On the Universal Near Optimality of Hedge in Combinatorial Settings
Authors: Zhiyuan Fan
Arnab Maiti
Lillian J. Ratliff
Kevin Jamieson
Gabriele Farina
Venue: NeurIPS 2025 spotlight ()
Keywords: Online learning
Hedge algorithm
Regret minimization
Combinatorial Games
Directed Acyclic Graphs
Dilated entropy
Online Mirror Descent
Primary area: theory

Abstract: In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector $\mathbf{x}_t$ from a set $\mathcal{X} \subseteq$ {$0,1$}$^d$, observes a full loss vector $\mathbf{y}_t \in \mathbb{R}^d$, and incurs a loss $\langle \mathbf{x}_t, \mathbf{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 $\mathcal{O}\big(\sqrt{T \log |\mathcal{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 $\mathcal{X} \subseteq$ {$0,1$}$^d$, Hedge is near-optimal—specifically, up to a $\sqrt{\log d}$ factor—by establishing a lower bound of $\Omega\big(\sqrt{T \log(|\mathcal{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.

On the Universal Near Optimality of Hedge in Combinatorial Settings
Zhiyuan Fan"
Arnab Maiti
MIT fanzyemit.edu
University of Washington arnabm2@uv edu
Kevin Jamieson University of Washington jamieson8cs, washington edu
Lillian J. Ratliff
Gabriele Farina MIT g gfarina@mit.eem
University of Washington ratliffl@uv edu
Abstract
In this paper, we study the classical HEDGE algorithm in combinatorial settings.
In each round, the learner selects vector at; from set X' C {0, 1)d, observes a full loss vector Y/ ggd and incurs loss (z,, y:) [-1, This setting captures several important problems, including extensive-form games, resource allocation, m-sets, online multitask learning, and shortest-pate problems on di- rected acyclic graphs (DAGs). It is well known that HEDGE achieves a regret of (v (Tloo [XT] after 7 rounds of interaction. In this paper, we ask whether HEDGE is optimal across all combinatorial settings. To that end, show that for any X C {0, 1)dd HEDGE is
to a vlog factor-by establishing lower bound of O /T log((>())/ log d) that holds for any algo- rithm. We then identify natural class of combinatorial sets-namely, m-sets with log d m I Vd-for for which this lower bound is tight, and for which HEDGE provably suboptimal by factor of exactly vlggd. d. At the same time, we show that HEDGE is optimal for online multitask learning, generalization of the classical K Keexperts problem. Finally, we leverage the near-optimality of HEDGE to establish the existence near-optimal regularizer for online shortest-patt problems DAGs setting that subsumes broad range of combinatorial domains. Specifi- cally, we show that the classical Online Mirror Descent (OMD) algorithm, when instantiated with the dilated entropy regularizer, is iterate- ceuiveeequivleent to HEDGE, and therefore inherits its near-optimal regret guarantees for DAGs.
Introduction
2 In this of experts 21, K) in each round. After making the choice, the learner observes the losses all experts, which may be assigned adversarially within [-1, 1]. The goal is to minimize the cumulative regret, defined the difference between the learner's expected total loss and the loss of the best expert in hindsight after T rounds. A simple and widely used algorithm for this setting is HEDGE, introduced by Freund and Schapire 24 which guarantees a regret bound of (VoTlog K')
Prediction with expert advice is a central problem online learning 31 13 problem, learner selects probability distribution
Since its introduction, the HEDGE algorithm has been extended to variety of settings, including adversarial bandits (3], continuous action spaces (30], stochastic regimes (34), discounted losses
'Equal contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

23], and adaptive learning rates [8]] An important special case is combinatorial settings, where the learner selects vector 22 from combinatorial set X S {0, 1] in each round, observes loss vector yt, and incurs a loss of (æ:, vt) E [-1, The objective remains to minimize regret against the best fixed vector E X' hindsight.
The combinatorial setting captures a wide variety of problems. including extensive-form games, resource allocation games (e.g., Colonel Blotto problems), online multitask learning problem, {0, 1 hypercube, perfect matchings, spanning trees, cut sets, m-sett, and online shortest paths in directed acyelic graphs (DAGs). These problems have wide-ranging applications. For instance, extensive- games provide foundational framework for modeling sequential games with imperfect information and have been used to build human-level and even superhuman-less Al agents for real-world games Online shortest path problems in DAGs arise naturally in applications like network routing Resource allocation games have been widely studied the context of military strategy, political campaigns, sports, and advertising 66
33 7
Given their broad relevance, these combinatorial problems have been extensively studied through the lens of online learning [44 28 29 12
16 36 45). In the full-information setting, where the learner observes the entire loss vector, an important class of extensive-form games admits optimal algorithms that are efficiently implementable, with HEDGE shown to satisfy both properties in this context
[9]. Another example the work of Takimoto and Warmuth 44, which provided an efficient implementation of variant of HEDGE for online shortest path problems in DAGs. In the bandit setting, refined variants of HEDGE achieve minimax -pttimall regret 12 TO though a recent work shows they can still be significantly suboptimal for certain combinatorial families (32
In this paper, we return the full-information setting and revisit natural approach for addressing combinatorial problems: treating each element æ E A' as an expert and directly applying the HEDGE algorithm. This yields a regret bound of O (yTT) Tollo (1) While this naive approach is often computationally intractable due the size of X. Farina al. (20) (building
prior ideas by Takimoto and Warmuth [44) recently showed that HEDGE and its optimistic variants can be
implemented efficiently variety of important combinatorial settings that admit an efficient kernel. Given HEDGE'S 's fundamental advantages- booth its simplicity and its broad applicability- we are motivated to ask the following natural question:
Does HEDGE achieve optimal regret guarantees for every combinatorial set X' {0, 1)??
1.1 Our Contributions
In this paper, we address the above question by establishing the following results:
Theorem 4.6
HEDGE Upper Bound (Folklore)
Theorems 5.1 6.1
Tlog [
Suboptimality of HEDGE
HEDGE can be optimal
Optimal regret range
Optinal Regret
General Lower Bound (Theorem 3.2
log | T
log d
Theorem 4.4
Multitask Learning (Section S Online Shortest Path (Section 6
m-sets (Section
Figure 1: An overview of results. The z-axis indexes different combinatorial decision sets X' C {0,1)* 13dd and the y-axis shows the optimal regret over T' rounds. We show that HEDGE is near-optimal for all X, up Vlog d factor. For m-sets, HEDGE is provably suboptimal by factor of vlog d, whereas in structured settings such as online multitask learning and important families of DAGs, it in fact optimal.

---

Universal Near-Optimality; In Theorem 3.2 we show that HEDGE is universally near optimal for combinatorial games by proving that the regret lower bound for any algorithm on any combinatorial set X' S {0, 1]. d is (2( max ( X log d, vT)).
Suboptimality in Specific Cases: In Theorems 4.4 and 4.6 we show that the lower bound from Theorem 3.2 is tight for a natural class of combinatorial sets X' and that HEDGE is provably suboptimal for these sets, Specifically, for m-sets with log d S m S Vd, we prove that HEDGE log I while we design an Online Mirror Descent (OMD) algorithm that achieves an optimal regret of O ( log / log d).
necessarily incurs regret of 52( log
Optimality in Specific Cases: In Theorem 5.1] we show that HEDGE is optimal for a specific class of combinatorial sets X. In particular, for online multitask bearinngwhiie generalizes the classical K Keexperts problem-we prove that any algorithm must incur a regret of S2 T log (
Beyond these results, we further investigate the optimality of HEDGE and its connection to regularization--asse baaettioo--aadddddeee algorithms in the structured setting of directed acyclic graphs (DAGs), which cap- ture a broad class of combinatorial problems-ing iiniuudinnn extensive-form games, resource allocation game, m-sets, multitask learning, and the {0, 1 ]dd hypercube:
we show that HEDGE is minimax optimal when X' corresponds to the set of paths from source to sink a DAG.
In Theorem 6.1
In Section 6.1 we show that OMD with the dilated entropy regularizer achieves a minimax- optimal regret of O /Tlo (21) for DAGs.
In Theorem 6.5 we show that OMD with the dilated entropy regularizer is iterate-cquivalent to HEDGE therbyy inheriting the regret guarantees of HEDGE and demonstrating that HEDGE can be implemented efficiently on DAGs via OMD.
1.2 Related Works
Prediction with Expert Advice. One of the earliest works online prediction was by Littlestone
and Warmuth BI], who introduced the Weighted Majority algorithm. Cesa- Bianchi et al. [13] extended this line of work by studying the setting where experts predictions lie in the interval [0, 1]. while the outcomes are binary. Subsequently, Freund and Schapire (24] addressed the more general setting where both predictions and outcomes lie in [0. 1]. They proposed the HEDGE algorithm and established a regret bound of OoTTlo K), where is the time horizon and is the number of experts.
This foundational result gave rise to several important subsequent works. Erven et al. [8 introduced AdaHedge, variant of HEDGE with adaptive learning rates that achieves regret of roughly
V /Ly log K, where L is the cumulative loss of the best expert. Krichene et al. 30 studied
compact convex sets S C Rd. In the stochastic setting, Mourtada and Gaiffas [34] analyzed HEDGE with decreasing learning rates and obtained regret bound of (loog A), where A denotes the sub-optimality gap. For the bandit feedback setting, Auer et al. 3 developed ExP3, a bandit-feedback variant of HEDGE that achieves a regret of (VKT)).
continuous version of HEDGE for online optimization
Combinatorial Settings. Online learning in combinatorial games has recently received consider- able attention. Farina al. 20 showed that HEDGE and its optimistic variants [15] 37 can be implemented efficiently when the combinatorial game admits an efficient kernel. Examples of such problems include extensive-fore online shortest path problems in directed acyclic graphs (DAGs). Hoda et al. [27] introduced the dilated entropy regularizer for extensive-fore games and analyzed its properties (cf. also Farina et al. 21I.. Building on this, Bai et al. [5] demonstrated that Online Mirror Descent (OMD) with the specific variant of the dilated entropy regularizer is cerate-equivalent to HEDGE in extensive games. Fan et al. [19] subsequently provided the first OMD-based regret analysis for this regularizer, matching the known bounds for HEDGE. Their analysis introduced a new norm, called the treeplex norm, to facilitate the regret bounds.
games, resource allocation games, m-sets, and, more generally,
In the bandit feedback setting, Dssa-Bianchi and Lugosi 12 analyzed online learning over specific combinatorial sets X' C {0, 1) and proposed variant of HEDGE called COMBAND, achieving an
3

---

expected regret bound of (V d' log (21) for those sets. Bubeck et al. [T0] subsequently extended this result any combinatorial set X' S {0. using variant of HEDGE known as EXP2 with John's 's exploration. Recently, Maiti et al. [32] showed that this bound sub-optimal by a factor of dz/4 for a specifie family of directed acyclic graphs, thereby demonstrating that these variants of HEDGE can, in fact, be substantially sub-optimal.
While the above prior works as well as our own-focus on loss vectors yr such that (zz ye) [-1, 1] for all æ E X, other works (44, 29 36) consider coordinate-wise bounded losses, where each y.li] [0, 1] for all E [d]. Under coordinate-
bounded losses, Takimoto and Warmuth 44 were the first to implement a variant of HEDGE efficiently on DAGs by leveraging the additivity of losses across the edges of path. Koolen et [9 subsequently analyzed the COMPONENT HEDGE algorithm over various combinatorial sets, including m-sets and DAGs. Rahmanian and Warmuth 36 further extended COMPONENT HEDGE the k-multipaths problem.
Rademacher Complexity. Orabona and Pál 35 provided a non-asymptotic lower bound of M(yTlog N) for the experts problem by analyzing the supremum of sum of Rademacher random variables. A series of works [39] 38 22 extended this analysis to more general online lcarning prob- lems-including combinatorial settings by characterizing regret in terms of sequential Rademacher complexity. Srebro et al. [42) showed that there always exists an instance of Seoowwth--egglarizeee Leader (FTRL) that nearly optimal for online linear optimization. This was recently strengthened by Gatmiry et al. 255, who showed that an optimal FTRL instance always exists for online linear optimization. However, the construction of an optimal regularizer for FTRL may incur significant computational overhead.
Preliminaries
In this paper. we study the repeated online decision-making problem in combinatorial setting. Denote by d the dimension of the problem. The agent is given set of discrete actions X' S {0, 1)dd At each round simultaneously chooses loss vector y: y, potentially adversarially based on the interaction history F, := {(xr, yリ } The agent then incurs a loss of (æx, yr) and observes the loss vector ye The goal of the agent is to minimize the total loss over T rounds, or equivalently, to minimize the cumulative regret:
1.2,... the agent selects an action æ, from the decision set X. The environment
Regret = Σ De ya)
min x. EX
(a. yr).
We focus on the combinatorial game setting, in which the loss vector is restricted so that the loss incurred each round is bounded within [-1, 1]. In this case, the loss vector set y is the polar set of the convex hull co(2)) We note that this assumption covers various settings in the literature, including extensive-form games (20 5). Formally, we make the following assumption:
Assumption 2.1. The loss vector set is defined as y { E Ed max (zz 8)1 S 1}.
The Hedge Algorithm A classical approach for solving this problem the HEDGE algorithm 24. also known as Multiplicative Weight Updates (MWU). In this algorithm, the agent chooses actions in a randomized manner based on the past performance of the actions. Specifically, let n > be the learning rate, the probability of choosing an action æ in round is proportional to
Σ a u.))
P. (x(x)) xc (x) := exp
Vx X.
classical result shows under learning rate 1) = Vlog |/T this algorithm has regret upper bound of ( (VTToo (T)) in the combinatorial game setting (i.e., under Assumption 2.1 Furthermore, the algorithm requires (d) time per round to compute the updates. This may be exponential in d when only a succinct representation of the decision set X' is provided. It is known that when possible to simulate the MWU
the kernel of the decision set X' can be computed efficiently, algorithm in polynomial time using the KERNELIZED MWU algorithm 20)).

---

Proximal Methods We recall the foundational concepts and notations commonly used in proximal optimization methods. Let X denote the decision set. The proximal methods built upon on some regularizer şp co(22) IR, which is required to be j-strongly convex with respect to chosen norm || || over co')). Such a function naturally gives rise a generalized measure of divergence known as the Bregman divergence, defined for any vectors x', X as:
(æ' || σ) == s(x") p(x) ['p(z),='=20 x).
Among proximal methods, a general approach to solving the online decision problem is the Online Mirror Descent (OMD) algorithm [15]. Let be the learning rate, and let yp co(X) R be a strongly convex regularizer. The algorithm maintains a policy in each round t. In the first round, the policy is set the regularizer is unique minimizer: D1 argmmn) (zz)) For each round t t= ......., the agent takes proximal step:
{1 (2) DDp(2) 1
argmin (
Then, the agent draws and plays an action E X by matching its expectation to the proposed policy, i.e. [xr]] He. known that this algorithm achieves the following regret upper bound:
Theorem 2.2 (Regret Bound for OMD, 37 43)
Let || and || ||+ be pair of primal-dual norm defined on Idd Let be a DGF that is j-strongly convex on ||. Denote as the reward gradient received in episode t. The cumulative regret of running OMD with DGF and learning rate > can be upper bounded by
T
Regret(T) Σ (T. Ui)
min x E.EX
Σ c. yi) S DD, || T1) 17
1
+
11 24
yo
General Notation We use lowercase boldface letters, such æ. to denote vectors. The notation |a]| denotes the element-wise absolute value. For an index set C, let a: [c] E RC denote the subvector of restricted entries indexed by C, and let |C] denote the cardinality of the set. We write [||]] = {1, 22....,k] and use Ø to denote the empty set. The probability simplex over finite set is denoted by P(C). We use log x to denote the logarithm of æ base 2 and In denote the natural logarithm of æ. For non-negative sequences } and {bp, J. we write < 3Obn) or equivalently bn 2 (a,,)) to indicate the existence of global constant C
such that a, S Cb, for all 0. Similarly, we write an = (b... to indicate the existence of global constants C1. C2 > 0 such that C, S on S C2b, for all 0. Lastly, we denote by co( the convex hull of set X.
Universal Near Optimality of Hedge
In this section, we show that for any given combinatorial decision set X {0, 104, 3d, the HEDGE algorithm achieves a near optimal regret bound in the combinatorial game setting. We begin by stating the following classical result.
Lemma 3.1 (Sauer-Shelah Lemma 40
41). Let C be family of sets whose union has n elements. set S is said to be shattered by C if every subset of S can be obtained as the intersection $ n C for some set C E C. C shatters set of size k, if the number of sets in the family satisfies
R-1
C
By the Sauer-Shelah Lemma, there exists an index set Z C [d] of size 2(log |x|] log d) such that the restriction of X' to the coordinates in I equals the full hypercube {0, 1,2, Consequently, any hard at least as hard as the corresponding
instance with loss vectors supported only on coordinates instance of the combinatorial game over the hypercube X' == {0, 1)T As any algorithm suffers regret lower bound 92( /T [Z) in the combinatorial game over the hypercube. This yields regret lower bound of 2 ( /olo / log d).
We formally state our main result in the following theorem. We defer the proof to Appendix A
5

---

Theorem 3.2. Let X C {0,1}² be a decision set and let y be the corresponding loss vector set that For any T 2 and any Algorithm ALG, there exists a sequence of loss
satisfies Assumption 2.1 vectors y1, -/,..... y such that the algorithm incurs an expected regret of at least
T
T
{ (1
log | log d
VT (T))
E| [TRegret(T)] = E
ae ya
min EX
c+ yi)
2 2
max
T
The expectation is taken over any potential randomness of the algorithm.
4 The Sub-Optimality of Hedge on m-Sets
In this section, we consider specific decision set X X-namely, the family of m-sets-to illustrate the suboptimality of the HEDGE algorithm. For an integer m E [d/2]. the m-sets problem corresponds to the decision set X' == x E (0, 13d Σi=1 a[i m )- We show that OMD, with suitable regularizer, matches the regret lower bound from Theorem 3.2 when log d v m S d/2, whereas HEDGE suffers regret lower bound 1 /TVllgogg [)), establishing a suboptimality gap of /log
4.1 The Regret Upper Bound of m--eet
We begin by presenting our OMD algorithm for m-sets, for any E [d/2]. Previous work 42 shows that there always exists regularizer that enables the OMD algorithm to achieve a near-optimal regret bound. However, the regularizer is not constructive, and the corresponding regret bound is implicit. Instead, we need to construct regularizer suitable for the decision set so that the regret bound in Theorem 2.2 is minimized. Specifically, we analyze the OMD algorithm with the following regularizer:
(xx))
= In m
(4.1)
According to Theorem 2.2 it suffices to pick pair of primal-dual norm || and || and analyze the strong convexity of yp and also the vector norm [| We define a pair of dual-primal norms:
|| == max (z, 2)1, |||||| := max (y.
meX
Illl
First, state the following proposition that establishes upper bound the primal norm ||
The proof is done by direct calculation, and we defer the details to Appendix B
Proposition 4.1. For any vector E Rd, the primal norm || norms together, namely,
is upper bounded by the & and loc
||||| S 311=1>< +
|||||--
m
By applying the above proposition, establish the strong convexity of the regularizer io with respect to the primal norm. defer the proof Appendix B
Lemma 4.2. The function 1/9 1/9-strongly convex with respect to the primal norm || [|-
The following lemma bounds the Bregman divergence under the regularizer yp. Lemma 4.3. We have Dyp (æ. || ( < m + In(d/m), for any vector s. E X.
We defer the proof Appendix B Using the above results, we are able to establish the regret upper bound for rumning OMD with the regularizer defined in (4.1).
Theorem 4.4. Let < m S d/2. With the choice rj = 22(m + In(d/m))/(9T) the expected regret of running OMD with the regularizer in (4.l over m-sets is upper bounded by
E [eegeet (T)) s <O(TTm+Tog((/mm) Tlog(d/m)).

---

Proof. According to the definition of || I.. we have that 1/ || - 1. Combining this with Lemma 4.2
and Lemma 4.3 and applying Theorem 2.2 together with I6 xc Tt we conclude that
1
E [Regret (T)
- - (ac [ + 2/1 t=
"
_ mm + In(d/m)) + 97
T
2
1 v 18Tm + 187 187'nnd//nn ind/mm)
where the last inequality is given by the choice 7).
We show that this regret upper bound is in fact optimal by establishing a matching lower bound. Specifically, we construct our lower bound using the hard instance from Theorem 3.2 along with the hard instance for the K Keexperts problem (see Lemma F.4b. Formally, we show the following:
Theorem 4.5. Consider integers m, d, T such that < m S d/2 S exp(T/3)/2 For the m-sets problem and any Algorithm ALG, there exists a sequence of loss vectors y1 1/:--- yr E y such that the algorithm incurs expected regret of at least
E[Regret (T)) E
min 20 EX
Σ x De) 2 -0(VTmm= T Tlog(d/m)).
We defer the proof Appendix B
4.2 The Regret Lower Bound of Hedge
We introduce the following theorem, showing that the HEDGE algorithm is strictly sub-optimal m-sets, when log d S Vd. The full proof is deferred to Appendix B
Theorem 4.6. Consider integers m, d, T such that
d/2 cxp(T/3)/2 and m log(d/m) s
T. For any 7 > O, there exists a there exists a sequence of loss vectors yı, y2..... Yr E y over m-sets such that the HEDGE algorithm with learning rate incurs expected regret of at least
T
E (RRegre((T)) = E
(1 Uv)
min 20 EX
Σ c yi) 2 22(VVTT (m(V/mlog(dd/m)
Proof sketch. We divide the proof into two cases based on how r) compares to the base learning rate VJo == ln(dm// e ( .T)..
When the learning rate is small, i.e., S %/o we construct a hard instance by assigning the same fixed loss vector Yt across all rounds, where y 1[ [m]l/m / for all [d]. In this case, we can show that HEDGE with a small learning rate incurs a constant regret for any round t I to = ( (m log(d/m)). Thus, we establish a regret lower bound of Ω (oml/g(/m)))
When the learning rate large, i.e., 1j > T/o, we construct hard instance by setting y: [c] = 0 for all coordinates > 2 across all rounds. For the first coordinate, the loss y, [1) is assigned in two phases, based on the threshold to ==
(assuming to E IN for simplicity). In Phase (rounds t < to), we set [1] - In Phase 2 (rounds to), the value of y: [1] alternates: it is 1 if to odd, and -1 if to even.
In this case, we can show that HEDGE with a large learning rate incurs regret of Q min((, 1}) for every two rounds after to. Thus, we establish regret lower bound via
Reegeet (T) 2 (T - to) 2 min (n. (n.1)) 1)) 2 2 (VTTmmoogd//i/
In general, we conclude that HEDGE has regret lower bound of 2 lold//mm on the mn-sets for any learning rate 7) > 0.
D
7

---

5 The Optimality of Hedge for Online Multitask Learning
In the previous section, showed that the HEDGE algorithm can be strictly suboptimal for certain combinatorial decision sets, such as m-sets. This naturally leads to the question: are there combina- torial settings where HEDGE remains optimal? In this section, we answer this in the affirmative by analyzing the Online Multitask Learning problem-a setting that generalizes the classical K Keexperts problem and has been studied in the bandit learning literature as the Multi-Task Bandit problem. In this problem, the learner is presented with m 2 1 separate expert problems, where the i-th problem involves d, 2 experts. In each round, the learner selects one expert from each problem and incurs a loss that is the sum of the losses associated with the chosen experts. The goal is to minimize regret with respect to the best expert in each problem in hindsight.
We parameterize the online multitask learning problem as follows: Let di =- Σj=1 dg be the total number of experts in the first expert problems, with d1-0 == O. The decision set X' of dimension d = d1am given by
duss
X' x 10,
xb1 = vi E [m]]
j=dmn-1+1
Recall that the adversary is restricted choose yr such that (ar, yz) [-1, for all æ X in each round & following from Assumption 2.T In this case, HEDGE has regret upper bound of
o ((VTlogg TTloo log X In the following theorem we show that HEDGE is optimal for the online multitask Learning problem. We construct hard instance by using the hard instance for the i-th expert problem over do log dj
T rounds. The full proof is deferred to Appendix C
Theorem 5.1. Consider any instance of the online multitask learning problem on X' of dimension d 2 2. Let the corresponding loss vector set y satisfy Assumption 2.1 Consider an integer T > 3 log I.a. Then for any Algorithm ALG, there exists a sequence of loss vectors y1, U/...... Ur E y such that the algorithm incurs a regret of least
T
E[Regret(T) = E
Σ Ji yi) - min Σ (a. vi) 2 2 ( x1)) EX 1=1
Minimax Optimal Regularizers for Directed Acyelic Graphs
We consider the online shortest path problem in the Directed Acyclic Graphs (DAGs), Let G = (V, E) be a DAG with the source vertex E V and the sink E V. We assume that every vertex is reachable from s and can reach t. Denote by X' C {0, _ the set of all s-t paths of the graph G, indexed by the edges in E. Each vertex a E X' encodes a s-t path in the graph, where afc) = indicates that e E E appears in the path. The convex hull of X' forms the flow polytope:
V
co(2))
E [0,1]
E Eadd==<le
-=(e]=== =1
x
and cE6 (0)
E=ld=Iadd VU VEV
(E (z)
eE
(v)
where ()( = {(u, v) E E} and (+( = (u, w) E} denotes the set of incoming edges and
outgoing edges, respectively. We note that in this case, the loss vector y y C R is an assignment of the weights such that any s-t path has a weight between -1 and 1.
In the following theorem, we show that HEDGE is minimax optimal for DAGs. The proof involves careful construction of a DAG, parameterized by upper bounds on the number of edges and paths. The full proof is deferred to Appendix
Theorem 6.1. For any integers d, N, T such that 16 S 2d S N < 2d and 3 log N < T, and for any algorithm ALG, there exists a DAG G with at most d edges and at most N paths from source to sink t, and a corresponding sequence of loss vectors yl, y2, ...,.... yr E y such that the algorithm incurs a regret lower bound of
E[Regret (T)) =
Σ
Crs yt)
min 2.
c. yi) 2 D(VT Tog N).
EX
8

---

6.1 OMD with Dilated Entropy Regularizer
While our main focus has been on the HEDGE algorithm, it natural to consider its close counterpart, Online Mirror Descent (OMD). With an appropriate distance-generee generating function, OMD is known to be -terate-equivalet HEDGE in extensive-fomm games [ 19]. Since DAGs can model such games 32) and HEDGE is minimax-optimal on DAGs, this motivates closer examination of OMD on DAGS. In this section, we analyze OMD with the dilated entropy regularizer on DAGS and show that it also achieves minimax-optima regret. Formally, the dilated entropy rh: co(2)) - R is defined by
a x
(x))
Σ x In [
Σ 2/u
Ina
E
Σ
x In
CEE
eVV
=(VV)(t)=m))>0eeen (w)
where, by standard convention, 0ln0 == Here, a|v] == Eeco-(o) x|e] for all o t. and ælt] := 1.
We note that the regularizer on the policy ã E co(X') is closely related the Shannon entropy over the chosen action æ E X. In fact, consider the following procedure for sampling an action D( E P(X): we start from the active vertex u s. each step, we first set x [u] then randomly pick an edge
(u,v) E (+) with probability øle]/ [u]. set æfe] = 1, and move to u < e. Following this Markovian sampling procedure, one can see that the drawn vector a: consistent with T. i.e., E [z] = Ø. Furthermore, we have the following:
Lemma 6.2. For any i E co()X), we have
(+)
((x)
[n P(z)];
a-~((a))
where H.) denotes the Shannon entropy of the random variable.
The proof of the above lemma is deferred to Appendix D We will now show that running OMD with the dilated regularizer enjoys regret upper bound of O (vV Tlog (.()), based the OMD regret bound in Theorem 2.2 From Lemma 6.2 we have that tb is equivalent to the negative entropy of distribution over X. This indicates D x. x S In |.' It remains to pick the norm functions and show the strong convexity. Consider a pair of primal dual norms
|| == max (2,, =)1b øEX
|| == max (y,
We note that since (o())) is the flow polytope, its dual, {y: : 1 S 1}, is closely related to the set of all cuts of the graph. The next lemma shows &b strongly convex over primal norm || We defer the proof to Appendix
Lemma 6.3. The function ss 1/10-stroogll convex with respect to the primal norm ||||| span(X)).
From the standard OMD analysis, running OMD under the dilated entropy vú achieves a regret upper bound of (VT log ( Hence, OMD with dilated entropy is minimax optimal for DAGs.
6.2 Equivalence of Dilated Entropy and HEDGE
As shown earlier, both OMD with the dilated entropy regularizer and HEDGE over the set of paths in a DAG achieve minimax optimal regret. This naturally raises a fundamental question: are these two approaches equivalent? In this section, we answer this question in the affirmative.
Let G (V, E) be a directed acyclic graph (DAG) with designated source vertex and sink vertex t. and let X' denote the set of all paths from to t. If G contains only a single source-to-sink path, the cquivalence immediate. Therefore, we focus on the case where G admits multiple such paths.
We begin by state the following lemma, the proof of which is deferred to Appendix D
Lemma 6.4. The dilated entropy is differentiable and strictly convex the relative interior C== relint (2))))) Moreover, lim [|Va Vi (x,,))l2 oo (ma), )n is sequence of points in C approaching the boundary of C.
Now, we present the following theorem, which demonstrate that OMD is, fact, iterate-equivalent to HEDGE. The proof proceeds by formulating the KKT conditions and applying Lemma 6.4 to establish the equivalence. The proof is deferred to Appendix D
Theorem 6.5. OMD with dilated entropy is iterate-cquivalent to HEDGE over the set of paths X.

---

7 Conclusion and Future works
We investigated the optimality the classical HEDGE algorithm in combinatorial online learning settings. While HEDGE achieves a regret of O ( log (x(), we established that this rate is nearly optimal-up to Vlgg d factor-for any set X' S {0, 1j2. We further identified class of m-sets for which HEDGE is provably suboptimal and showed that remains optimal for the multitask learning problem. Finally, we demonstrated that Online Mirror Descent with the dilated entropy regularizer is eurraee-quivalent to HEDGE on DAGs, providing computationally efficient regularization framework for broad family of combinatorial domains.
Our work opens up several interesting directions for future research. One natural question is whether there exists a family efficiently constructible regularizers that are near-optimal for the combinatorial sets. We conjecture that negative entropy in suitably lifted space may support of this, we refer the reader to Appendix E where we show that the conjecture holds for DAGs. Another compelling direction is to explore whether there exist near-optimal variants of the Follow- Certurbed-Leadee algorithm for the combinatorial sets. Since perturbations are often considered more iupllmmentation-rreende algorithm could yield both theoretical and practical advances. Finally, we ask whether there are variants of HEDGE that achieve near-optimal regret for arbitrary finite subsets of R".
such a regularizer. In
exploring near-optimal variants of the Besloo-the-Perturbede
Acknowledgments
Ratliff is funded in part by ONR YIP N000142012571, and NSF awards 1844729 and 2312775. Jamieson is funded in part by NSF Award CAREER 2141511 and Microsoft Grant for Customer Experience Innovation. Farina funded in part by NSF Award CCF-2443068, ONR grant N00014- 25-1-2296, and AI2050 Early Career Fellowship.
References
[1] AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini, and Saeed Seddighin. From duels to battlefields: Computing equilibria of blotto and other games. Mathematics of Operations Research, 44(4):1304-1355 2019.
[2] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: aega-algorithm and applications. Theory of computing, 8(1):121-164 2012.
[3] Peter Auer, Nicolo Desa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 2002
[4] Baruch Awerbuch and Robert D) Kleinherg. Adaptive routing with end-to-end feedback: Dis- tributed learning and geometric approaches. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 45-53, 2004.
[5] Yu Bai, Chi Jin, Song Mci, Ziang Song, and Tiancheng Yu. Efficient phi-regret minimization in extensive-form games via online mirror descent. Advances in Neural Information Processing Systems, 35:22313-22325, 2022.
[6] Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, Mohammedtaghi Hajiaghayi, and Saeed Seddighin. Fast and simple solutions of blotto games. Operations Research, (1(2):006-516, 2023.
[7] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 14756218) 2015.
[8] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-42 2018.
[9] Noam Brown and Tuomas Sandholm. Superhuman for multiplayer poker. Science, 365 (6456):885-890 2019.
10

---

[10] Sébastien Bubeck. Nicolo Basa-Bianchi, and Sham M Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages JMLR Workshop and Conference Proceedings, 2012.
[11] Nicolo Aasa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[12] Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404-142444 2012.
[13] Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David Helmbold, Robert Schapire, and Manfred K Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
[14] Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66:321-352, 2007.
[15] Chao-Kai Chiang, Tianbao Yang. Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6-1. JMLR Workshop and Conference Proceedings, 2012.
[16] Alon Cohen and Tamir Hazan. Following the perturbed leader for online structured learning. In International Conference Machine Learning, pages 1034-1042. PMLR, 2015.
[17] Alon Cohen, Tamir Hazan, and Tomer Koren. Tight bounds for bandit combinatorial optimiza- tion. In Conference on Learning Theory, pages 629-642. PMLR, 2017.
[18] Tim Erven, Wouter M Koolen, Steven Rooij, and Peter Grünwald. Adaptive hedge. Advances in Neural Information Processing Systems, 24, 2011.
[19] Zhiyuan Fan, Christian Kroer, and Gabriele Farina. On the optimality of dilated entropy and lower bounds for online learning in extensive-fomm games. In Neural Information Processing Systems (NeurIPS), 2024.
[20] Gabriele Farina, Chung- Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for -/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. In International Conference on Machine Learning, pages 6337-6357. PMLR, 2022.
[21] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Better regularization for sequential decision spaces: Fast convergence rates for nash, correlated, and team equilibria. Operations Research, 2025.
[22] Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. Advances in Neural Information Processing Systems, 28, 2015.
[23] Yoav Freund and Daniel Hsu. A new hedging algorithm and its application to inferring latent random variables. arXiv preprint arXiv:0806.4488 4802, 2008.
[24] Yoav Freund and Robert Schapire. A tecision-theoreticc generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 19-199999-13, 1997.
[25] Khashayar Gatmiry, Jon Schneider, and Stefanie Jegelka. Computing optimal regularizers for online línear optimization. arXiv preprint arXiv:2410.1723 17336, 2024.
[26] Uffe Haagerup. The best constants in the khintchine inequality. Studia Mathematica, 70(3): 231-283, 1981.
[27] Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
[28] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307) 2005.

---

[29] Wouter M Koolen, Manfred K Warmuth, Jyrki Kivinen, et al. Hedging structured concepts. In COLT, pages 93-105. Citeseer, 2010.
[30] Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. The hedge algorithm on continuum. In International Conference on Machine Learning, pages 924-832. PMLR, 2015.
[31] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2)2112-26) 1994.
[32] Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian J Ratliff, and Gabriele Farina. Efficient near-optimal algorithm for online shortest paths in directed acyclic graphs with bandit feedback against adaptive adversaries. arXiv preprint arXiv:2504. 00461, 2025.
[33] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6333):508-5111 513, 2017.
[34] Jaouad Mourtada and Stéphane Gaïffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20(83): 2019.
[35] Francesco Orabona and Dávid Pál. Optimal non-asymptotic lower bound on the minimax regret of learning with expert advice. arXiv preprint vrXXv:/511..2176. 2015.
[36] Holakou Rahmanian and Manfred KK Warmuth. Online dynamic programming. Advances in Neural Information Processing Systems, 30, 2017.
[37] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, PMLR, 2013.
[38] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Relax and localize: From value to algorithms. arXiv preprint arXiv: 2012.
[39] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. J. Mach. Learn. Res., 16(1):155-186, 2015.
[40] Norbert Sauer. On the density of families sets. Journal of Combinatorial Theory, Series A, 13(1):145-144 1972.
[41] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pucific Journal of Mathematics, 41(1):247-261, 1972.
[42] Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent. Advances in neural information processing systems, 24, 2011.
[43] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[44] Eiji Takimoto and Manfred K Warmuth. Path kernels and multiplicative updates. Journal of Machine Learning Research, 4(Occ):773-818, 2003.
[45] Dong Quan Vu, Patrick Loiseau, and Alonso Silva. Combinatorial bandits for sequential learning in colonel blotto games. In 20/9 IEEE 58th conference on decision and control (CDC), pages 867-872. IEEE, 2019.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Theorems match the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA].
Justification:
We don't see any limitations of our work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Every assumption our problem setting is clearly mentioned in the introduc-
tion.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.. cc/
pub i gu des Codeeubmies casionoollii icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/ wwwblic//uideen / //odiddee/Cdeeeeeeee Cooeeeooeeeeeeeeee SudeSuumiiee Swwmisssiiii wsssnooliccyyyyooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssw hopersswtccoee com/ dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification:
Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
18

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non- standard components.
httpppps...cccooeeeneee/////222 LLM) for what should should not be described.
Please refer to our LLM policy
19

---

A Deferred Proofs from Section 3
Theorem 3.2 Let C (0, 1]dd be a decision set and let y be the corresponding loss vector set that satisfies Assumption 2.1 For any T 2 1 and any Algorithm ALG, there exists a sequence of loss vectors y1, 1/,
yr y such that the algorithm incurs an expected regret of at least
T
{
log | log d VT )
E B(Regret(T)) = E
Bt yt)
min Ø.Ea
a. yt) 2 max
(V
The expectation is taken over any potential randomness of the algorithm.
Proof. If | = 1, the result holds trivially. Therefore, we assume | 2 2. We begin by considering deterministic algorithm ALG and establish regret lower bound for it. The result is then extended to randomized algorithms via Yao's lemma.
Let max
log [X]
Ei= (1) in general. This is clear when .1 11 We will show that |
log(2ed)
k = 1, as we have |X| 2 2>> 1 = Ex=o (1)
In the case where E [2, c]]. we have that
12ed h
2d
|2| 2 (2ed)* > k.
For every vector & X, we construct corresponding indicator set C2 : fi d
= 1).
Denote by = (Ca x E X be the collection of such sets. According Lemma
3.1 there exists
set I S [d]] of size l that is shattered by C. From the definition of shattering and the construction of C. we have that for any vector = E 10 there exists some vector æ E X such that x [
We now construct the hard instance. For the simplicity of presentation, we assume that I' divides [Z]. We partition the T' rounds into [Z] equal-length segments, each assigned a unique element of Z. Let & denote the unique element in I associated with the segment that round t belongs to. The loss vector in round is then generated as
y: : Ci2 E..
where & drawn from the Rademacher distribution, i.e., P(E: = =1) = = 1/2.
Now consider the expected loss incurred by the Algorithm ALG. The decisions generated by Algorithm ALG satisfy x; T Y: Fi, He conditionally independent of y given F,.. Therefore,
E
( Mi)
Σ E ( M.) 1F]
Σ B|x & [F] 0.
On the other hand, the loss of the optimal action T, E X' satifies
T
T x [b] E = min E. IET
min C.
xx. y1)
min a.
Σ x
Σ &.
E
According the selection of I. for any vector Rd there exists some vector E X such that x { = if and only if [i] < for every i E I. This implies that we can always choose some vector X' to minimize (x: [ [Z] simultaneously across all coordinates in I. Thus,
Σ 5.. fif
min
min
FET
SEI
Taking the expectation over the randomness of t., this implies
-
E min
De 3t)
=
min
Σ Ee. 0
E
Σ E
E.X
IEI
VEI
t:
Σ
TT/(8/] = TTI//8
-
iET
20

---

where the second inequality follows from Khintchine Inequality (Lemma F.2) in which the expected absolute sum of n independent Rademacher variables is at least v n/n/2, and the size of set (t it i) exactly T/ [Z]- In general, we can conclude that
T
T yn)
T
Tlog |X log d
vT vr)
})
B[Regret = E
yd) min Ex
xx
2
S2
max
t=1
where the last equality follows from
[
(mmax([og] / log d, 1}).
By Yao's lemma, for any randomized algorithm ALG, there exists sequence of loss vectors y/ y2..... yrr E y such that the algorithm incurs regret of at least
E(Regrot(T)) Ω max {v
Toog [X] log d
VVT v=))
B Deferred Proofs from Section 4
Proposition 4.1 For any vector Rd the primal norm || is upper bounded by the l and Loo norms together, namely,
1
||||| S 31/2/1 + ||=||-
Proof. It is sufficient to show that (y. x) 3| (1/m)]l=[1 for any two vectors y, z Rd
with |y|| < 1. Let S = (i E [d] y 2 20} and S2 = (i E [d] : vl < 0}. Let us assume that
|S d/2.
Let us reindex the indices in S2 as (ii, 12, ........ 1 such that yla S y [ S ... S ylissal-
Observe that プ ز 1. Hence, y|úr] 2 11/m for m S S [S2].
Let us reindex the indices S₁ as {81, 82, , 815,1} } such that y(s1] 2 y[s²] 2 ... 2 g[sssu] Let us first consider the case when m S |Si| S d/2. Observe that ΣØ g[s,] < Hence, y|8; S 1/m for all m I j I |S2].
In this case, we have the following:
m
18aa
18 Σ
(z, v)
+
Σ
|
|
j=1
jmm+1
jmm-++
|S Σ
<
||0||00
M
+
Σ
|x[bg||
+ ||
Σ 5=1
|B[ss|1
+
|
+1
j=m++
1 |||||
< <211=|100
+
Next, let us consider the case when [S1| < m. If |S * O, then consider the set I S
(11, " }m- Now observe that Σ iEz ylil < 1. Hence, we have that E y1, <
1 1 Em-15: ylú51 < 2 as Em1 1Sil ylū,l
2 f=1 ylisl 2 1. In this case, we have the following:
18al
(2,8) 1 + 0} Σ
[
| + Σ | 1 +
Σ
|
|
j=++1
18a1
|8al
< 1([S) #0} ||
Σ
|ل| + ||
Σ
Σ
|=
j ml
1
< <3/l2/1 oc +
|
21

---

If |S1] > d/2, using analogous calculations we can again show that
(z, v) S 3/ + |z||1-
Lemma 4.2. The function is 1/9-strongly convex with respect to the primal norm ||
||.
Proof. Take Rd. Plugging (a (a++b) b)² < 2a + 212 for any o, b into Proposition 4.1 implies
| < 18 = 1 +
772 1
(B.1)
According to the definition of the regularizer the Hessian matrix of the function is diagonal matrix with (a)(()) = 2+ 1/(m- æli)). Considering the local norm of the vector with respect to p(z), we have
d = Σ =|1]? 22 2m 1
| | = =VVV<<x
2 2
(B.2)
mæ i
2m
I
I2
We note that
I Σ
=[1 max
x[1]
1|
(B.3)
Furthermore, by the definition of the m-Set, we have Σ x = m for a E X. Therefore, we can write
2
I2 =
x
-
(B.4)
i
m
where the inequality follows from the Cauchy- -chwarz inequality.
Plugging B.3 and (B.4 into B.2). get
| P())) 2 2112113
|
(mx)
m
where the last inequality follows from B. respect to the primal norm
This concludes that is 1 1/9-strongly convex with
||
Lemma 4.3, We have D (x. || [1) & m + Ind//m), for any vector æ. E X.
Proof. From the first-order optimality of क; argmin plx)), it satisfies that for any vector 31) 0. Therefore,
x, E X, (V
(n, || (1)))= S max (lx)) min ((xr). =cco(2))
(B.5)
=cco(X)
Consider a E co(2)). On the one hand, we have
(xx)
x=1 + x a
<
Σ
xc + 0 0= m,
(B.6)
where the first term is bounded by amii² s 2|i for a0i)] æ]i] In [0] 0.
[0. 1), and the second term satisfies
22

---

On the other hand, define p æ/m. Then, lies in the probability simplex by the definition of co(X).
d
((x))=
Σ
x]1]²
In
i=1
0
p
In pp]
p
Inm
1=1
1=1
d
p[i]
In
1mm
In(d/m).
(B.7)
where the first inequality uses æ [|]} 2 0, and the second inequality follows from the entropy upper bound over the probability simplex.
Finally, plugging (B.6) and [B.7
into B.5 yields
aa T1) S m + In(d/m).
Theorem 4.5
Consider integers m, d, 7 such that S m S d/2 exp(T/3)/2. For the m-sets problem and any Algorithm ALG, there exists a sequence of loss vectors y1, (2.-.-. yr E y such that the algorithm incurs expected regret of at least
T
T
E [(eegret = E
vI)
min EX I.. yid
Σ
2 00 20( Tm + T Tlog(d/m)
Proof. For every vector & E X, we construct a corresponding indicator set C2 := pi E [d] 2
1}. Denote by C = (C2 x E X3 the collection of these sets. We have [C] X Notice that the set I = {1, {l...., m). of size m, is shattered by C. Hence, by the same argument as in the proof of Theorem 3.2 for any randomized algorithm ALG there exists a sequence of loss vectors 91, ... yr y such that the algorithm incurs regret of at least (2 (TM).
To prove that (T) > PoyTloog(e log(d/m))) construct hard instance as follows. For Let K == d/m. Let Dк denote the In each round t, the environment first
simplicity of presentation, assume that d divides
zero-mean distribution over +11 from Lemma draws vector 2, DR and assigns
F.4
2
z1 [1]
2, [2]
23 [2]
2e [2]
2/ [K]
2 [
z |
=
m
Next for all i E [K], let (i) be a vector in X' that is defined as
(0) = 0,0, 0,0..... O,
0,0,
(-th block of no coordinates
that [0] if ((d--1yn 1)m + isisi- i m and x [( otherwise.
We begin by considering a deterministic algorithm ALG and establish a regret lower bound for it. The result is then extended to randomized algorithms via Yao's lemma. Let be the vector chosen by the Algorithm ALG in the round I. Observe that the expected loss of ALG is zero as Ex y:)l E[ yt [.]] B[(x,, [[yl On the other hand, we have
min øEX
ce, yr)
S
min K
3t
min [E(K]
(ei z.)
23

---

Hence, the regret of ALG is lower bounded as
E[Re E
Σ ( ye)
min ØEX
yi)
2 E
min iE|K]
Σ ee, 21) 2 26
where the last inequality follows from Lemma F.4
By Yao's lemma, for any randomized algorithm ALG, there exists a sequence of loss vectors yi U2..... Vr y such that the algorithm incurs regret of at least 5 (Tllo((/m))
Combining both the lower bounds, we conclude the desired regret lower bound:
E[Regret(TT) 12 maxx { (TTm (Tlooll/mmmmm Z (VTm+ lo log(d/m)
Theorem 4.6
Consider integers m. d, T such that I m S d/2 cxp(T/3)/2 and m loggd//m) S T. For any 77 > 0, there exists there exists sequence of loss vectors y/, 3/..... ....... yr E over m-sets such that the HEDGE algorithm with learning rate incurs expected regret of at least
E Regret = E
Σ (z). v.) min
a. yi) 2 2 ((VTmloo(d//m)
Proof. Recall that the HEDGE algorithm with learning rate 77 > 0 selects an action x E in round with probability proportional to:
(-1 (xr) x wxr = exp - Σ
(x, yz))
If 20, the regret lower bound of (LVmTTlndd// follows from Theorem 4.5 Hence, for the rest of the proof we assume that m 2 20.
l2 log d) for HEDGE directly
We divide the proof into two cases based on how 7) compares to the base learning rate
170 m in(d/m)
((v log |
T
T
Regime where the learning rate is small, / S njo
When the learning rate is small, we construct the hard instance by assigning fixed loss vector y across the rounds according to
ye [ == (1/m) [ e [m]]]
Let the set of bad actions that place small Hamming weight on the first m coordinates be defined as
S =
X { E [m]] æ + 13
m
20
From the calculation in Lemma whole decision set X::
G.3 we have that the subset S is relatively large with respect to the
XX'
S
m In
< exp
wg-
X
20
For any round / S to = V (m/ /40)) (lnmm/m), the weight of any action E S is at least
t-1
d
wx(xx) = exp
Σ (x, yn)) 2 exp(-no to) exp
In
=
Wo.
20
m
Furthermore, for any E X') S, it is clear that the weight satisfies wy (x) < 1. Now consider the probability that some bad action æ E S is chosen in round to. We have:
F(x, E S) Enex (x) 2 (1+ Emexis 11=e w((())
Exes we(x))
X S
maX w((x)
1
Enes W/ w)(x))
2 1+
S
minges W/ (xr)
2
24

---

Observe that in round t, if HEDGE chooses any action E S, then it incurs a regret of at least (1/m)- [m/20] 1/40, where the last inequality follows from Lemma G.1 Hence, HEDGE incurs constant regret in each round & I to. Note that as loss vector is fixed, HEDGE can not achieve negative regret any round. This indicates that HEDGE incurs a total regret of at least
1 40
E B[Regret(T)) 2 min T} P( E S)
2 ((VTmlog(d/mm)
for m log(d/m) & T, when the learning rate 1) S no is small.
Regime where the learning rate is large, 1) 7/6
When the learning rate is large, construct the hard instance follows. We set y [ coordinates i 2 2 across all rounds t E [[]] For the first coordinate, we define yr [1] in two phases, determined by to == In(d/m)/n & /T /Timdd/m)/m.
0 for all
Phase For the first < [fo] rounds, we assign y:[1] -1 la E N, then round [to], we assign y: (lo [fo]) In this way, the cumulative loss over the first
[to rounds is exactly o0 on the first coordinate.
Phase 2: For all remaining rounds >
[tu]. we assign ye [1] in an alternating manner as
follows:
+1 if t [t]] is odd,
v.[1]
if ( [66]]]]]] is even.
Let So = {x E X'
a=1] 0} and S (ar E X [=1] 1} denote partition of the action set based on whether mass is placed on the first coordinate. Note that
m
d
|Sp
S
m
According to the loss structure of the hard instance, every action in S₁ incurs same loss of y: in each round 4, while every action in Sp incurs zero loss. According to the HEDGE update rule, one can running HEDGE on X' is essentially equivalent running the algorithm
two aggregate actions zo and æ1. where represents playing uniformly random action from So and æ1 represents playing uniformly from S,. The initial weights are given by w1 (xo) = |So] and wi (æ1) |& In each round t, action I1 suffers loss of y: [1], and action Do suffers loss of O.
We analyze HEDGE actions Zo and æ1. For simplicity, assume that T [tto is Consider a round f := [to] + 2b, for some integer b 2 0. Let w and w denote the weights of actions 2g and 2 in round + 1, respectively. Then, HEDGE chooses action 21 with probability -exppxpp)) in round t + 2. Therefore, the total wo eexpl
number.
w² -h in round t + 1, and with probability expected loss incurred in these two rounds is
11+2
w
w exp(-1)
T w (1 - e= w (wo w e--)
Bi v.) = (+1)
+ (-1)
w + wi
w + w exp( ex)
(m)
(=++11
Since the cumulative loss in the first t rounds of action xy is 0, and that of action # - to we have
w |Sol exp( 11 - 0) =1So (1 m
d
)m)
d
m
d
w² =|11 exp( 1 n7
(-to)) S exp(In(d/m))=
m
From 1 < < d/2, it follows that 1 S w- /w0 0 < 2. Plugging this into the expression gives:
now² (1 -- E Dt, v.)l 2 (w) + w1 > l2( min 1}),
where the last inequality follows from 1 5 w /wo < and also (1 -=)) 2 (1 e1)) -mnn
for all x >0 0.
25

---

Now observe that any action a E S1 is the best action in hindsight over T rounds, incurring cumulative loss of -t. The HEDGE algorithm suffers least -tg expected loss the first phase and incurs an expected loss of at least Q(min(n; 1)) every two rounds in the second phase. Therefore, the total regret incurred by HEDGE least
E| ([ee
T [to
2( min(n. 1)) 2 2 (Tmllog(/mm)
for m log(d/m) & T, when the learning rate > To is large.
C Deferred Proof from Section S
Theorem 5.1, Consider any instance the online multitask learning problem on X' of dimension
d 2 2. Let the corresponding loss vector set D satisfy Assumption 2.1, Consider an integer T > 3 log |. Then for any Algorithm ALG, there exists sequence of loss vectors yı y2..... Yr E y such that the algorithm incurs regret of at least
E[Regret
= E
Σ t=1
( yt)
min 2. EX
a yi) 2 2 ( Toog log x1)
Proof. We begin by considering a deterministic algorithm ALG and establish a regret lower bound for it. The result is then extended to randomized algorithms via Yao's ' lemma.
Let assume that there that di Σj= dy and d1:0 0. For all i [m]] let Ti Σ lo T. For simplicity of
expert problems and the i-th problem has d, 2 experts. Recall log d.
presentation, let us assume that T; is positive integer for all i E [m]]] Let Tı Σj=1 Tj and d1.0 0. For any K 2 2, let Dx be the zero-mean distribution over (-1,+11) from Lemma F.4
begin by dividing the rounds into m phases, where i-th phase lasts for T3 rounds. round in the i-th phase, choose 21 Da, and define the loss vector y: follows:
[il if d 0
Ye [s]
otherwise.
Let æ, be the vector chosen by the Algorithm ALG in the round t. Observe that the expected loss of Given the structure of the loss vector yr. the problem reduces to solving m separate expert problems, each in its own phase. Consequently, the regret incurred by ALG can be decomposed as follows:
ALG zero [x y/t} [x y:) Fi]]
E (Regret(T))
E
min
Σ
tej, zt)
jeldi
==1
m
2 C0
logd, d
(due to Lemma
1=1
Li=1 (Em) log d,) VT
Co
TM
i= log d,
Co (Tlog X1,
(as I d, (2')
where co is the universal constant from Lemma F.4
By Yao's lemma, for any randomized algorithm ALG, there exists sequence of loss vectors
y1, .2....,..................... ........77 E y such that the algorithm incurs regret of at least (T/looo (T). D
D Deferred Proof from Section 6
Theorem For any integers d, N, T such that 16 S N 2d and log < T, and for any algorithm ALG, there exists DAG G with most d edges and at most N paths from source to sink
26

---

t, and corresponding sequence of loss vectors y1, U2... regret lower bound of
Ur E y such that the algorithm incurs
E(Regret(T)) E
t ye)
Σ 2. EX
min
, Ui)
25(( log N).
Proof. Let assume that d 2 8 and 2d < N S 24. Let do 8ld/8]. Due Lemma G.1 we have d/2 I do I d. Let No == min N, 2d0/4). Note that log((No) (log N). Let be the largest integer such that m do/8 and
No. Now claim that m log 2m 2 Allog N).
2m
m d./8. then we have m log( when m < da/8. Due to Lemma Hence, we have da ) S No 2(m++) 2m
log(() 2 (llog .N.. Let us consider the case (a/x)" is increasing in the range [1, a/33 for any > 3.
G.2
m+11 Next we have the following:
da (m + log(( 2(m+1)
(m + log( do log( do 2m
m +
2
m log(
da. 2m
Due to the above inequality, Lemma G.I and do/m 2 8, we have the following
m log
(L
do
m log
do
2 m
log
do
m + log
do
22 N).
2m
4m
2
2m
4
2(m + 1)
Consider a DAG G (V, E)) where the set of vertices V and the set of edges E are defined as follows:
do 2m
E ( (4f vx) I i [m] j E
do 2m
V = fo u e l [m], j E
|| S d. Also observe that the number of paths from source to sink in No S N. Hence, G is in the family of DAGs Fa,N. Now show that any algorithm incurs regret of Q /Toooo N) the DAG G.
Observe that [E| = 2m |||
do 2m
G da
For any K 2, let Dx denote the zero-mean distribution over (-1,+1) from Lemma F.4 We begin by dividing the I rounds into
phases: the first m phases each last for [T/m rounds, and the (m + 1)-th phase lasts for the remaining T m [T/m]]]] m] rounds. In any round the i-th phase with m, sample 2, D [ddo/(m))) and define the loss vector ye follows:
{
[ e == (vi-1, 0
y [e]
otherwise.
In round in the m 1-th phase, we choose y: 0.
We begin by considering a deterministic algorithm ALG and establish a regret lower bound for it. The result is then extended to randomized algorithms via Yao's lemma. Let be the vector chosen by the Algorithm ALGG in the round f. Observe that the expected loss of ALG is zero as [[ y+) B[ FF.] 0. Given the structure of the loss vector yı, the problem reduces to solving m separate expert problems, one in each phase i S m. Consequently, the regret incurred by ALG can be decomposed as follows:
i1T/ml
Regret (T) =
Σ
- E
min jelldo/(2n) (2m)
Σ
(e,,zz)
1=1
1= [T/////
2 (co/2)
(T/m) log( log([do/ (2m))
(due Lemma E.4 and Lemma G.1
(co/2) V mm log( (2mm)
= - (VTlog N)
(as mn (og([dd/(22m) 2 2(log N))
27

---

where co is the universal constant from Lemma F.4
By Yao's lemma, for any randomized algorithm ALG, there exists sequence of loss vectors y1, y2...... yr E y such that the algorithm incurs a regret of at least Q2( (oyTloog N).
Lemma 6.2 For any @ E co(2)) we have
(x))
EI
[m))))))
In
where H() denotes the Shannon entropy the random variable.
Proof.
From the procedure of Markovian sampling Section 6. have for any x E X
[[ v)]
Ex 3(e]
Exrlel=1
P(x)=
2 [4]
Iove 2[c]
((.,)))
Therefore, have
-1((x)
E
[n P(=)]
w~ x~D())
E
Σ
In 3 [0]
x~ a~D(@)
eE E:e 11
E
1 [x[e = 1} In [(c]
Σ
1 1xx[u]] 1) In [(v]
x~ D i
.EEE
NEV
In
in (T))
EE
"VV
where the fourth equality follows from [[x]] H. which concludes the proof for the equality.
Lemma 6.3 The function vi is 1/ 10--slyyyy convex with respect to the primal norm ||- in (2).
(y, 2)2 for any vector a E relint Proof. It sufficient to show that 10/|=|/2zv(a) 2 ||yl|+ I 1, and z E span
Consider weight assignment of the edges. For every vertex V, define dmain()) (v) E R the weight of the shortest path from v to t. and dmax (v) E R as the weight of the longest path from v to We have dinin (t) dmax (t) 0, well -1 dmmin(s) < dinax (s)
We construct vector y by assigning
y [u, u)] = v((u, v)] + dmin(v) dunn (u)
for every edge v) E E. By the triangle inequality, all values y [(u, u)] are nonnegative. Since span(('), have
2)) Σ
=I(u, v)] (vI(1, v)] + dini(()) (v) dmin( (u))
(u.D)E
Σ>eh y +
Σ
dmin(v)-
Σ (v)
z(c]
Σ (v)
z(el
d
d (s)
Σ
z(e]
eEE
(s.)
9E
eEd
eE (s)
(U,2) 2)
dmiu (s) =[s].
(D.1)
where z[s] Eccol (s) =[e] and the last equality follows from the flow constraints implied by span( X).. Note that this equality also holds for relint(co(22)). Combined with the facts
that (.. x) < 1, dmin (s) 2 -1, and æ[s] = 1. we have
0 ~ 5 (v) 5) 2.
(D.2)
28

---

Now, we define function da(2): V - R by assigning (v == dmax (v) - dmmi(() E [0, 2] for each vertex v V. In this case,
Iv = Σ
2x [0 In a//] = Σ da(v) xrll In +
Σ (2-da(v)) a0(v] In In
vEV
DEV
Σ (s)
da(u)
Σ (v)
[ec]|n +
Σ
(2- (2dd(()) Σ
x In m[c]
VEV
eEd
(D.3)
Furthermore, for every edge (u, v) E E, we define
""((u, v)] == dv( + y [u,, v)] da(u)= = dmax + yl(u, r)] dinax (u).
By the triangle inequality, we have y-(c] S 0 for all e E. Similarly, from the properties of y and da (-), we also have y"(e] 2 -2 for any edge E E. Furthermore, we can write
TB= = Σ
(2 + [e)) [n
EEE
Σ
(v) + y (1,,0) - (2-ds(w)) (w)) a[(u, w)] In 2: (u,
(u,u)E
Σ dv(v) Σ
Σ
[e] [e] +
Σ (2-ds(u)
Σ
are) In
VEV
eE)
eE
VE
eEδ+(v)
(D.4)
As result, we have
((xx)
1 Σ
(2 + [l(e))==le]lnn
In
Σ
v S/ee] [[c]]n
Σ
2x
In
2
2
EEE
EE
VEV
Iv
1 Σ
Ø|e|
2
(v)
x|c]
In
+ Σ
(2 da(u))
Σ
a|e] In
2
x x
(sV
eg
eEVi(t)
egd eEo+(w)
Z
I
+ 2
y'eel æle]
hale
Σ
v" jel [nle]]
where the second equality follows from (D.3 and (.4). Since da(v) [0,2] and y"(e] S 0, we have that I+, I-- and I are all sums of convex functions. Therefore, their sum is also convex. Thus, for any vector z E span(X'),
mm (I+ +I In) z 2 0.
Furthermore, from the second- ooder derivative (x In Inx:"" 1/x. have
y'eel [le]
y'le]
2 I'z
2le]2.
Σ æle] v'lel
[(e]
E
y'(el
1
Σ
z
|
y
[e]
2
(y''
2)²
2
EEE
The first inequality follows from (a. v²) < 2 in [.2]. and the second inequality follows from the Cauchy-Schwar inequality. Plugging in the two inequalities above gives
1 | == x (VD(E>>>>>> 4 (1/1
(D.5)
29

---

36. Furthermore, we can also decompose the regularizer as
b(x)= = Σ Σ
x(e] In
Σ (s)
x
(s.V( (w)
I
Z
Since Eh is the sum of convex functions, for any span(X), we have z V second order derivative (x in x²) = 1/x, we have that
I
0. From the
V IV
z[c]3-
Σ (E)+(s)
2|e]2
Σ
xle|
cE&+ (s)
(s)
2(c]
x|c]
CE
ddmin (s)
=[s))
where the second inequality follows from the Cauchy-Schwerr inequality, and the last inequality follows from (s) S This indicates
= p()) =TV2v(())=
(dmin (s) =(ss)²
(D.6)
Combining (D.)) and (D.6 concludes that
10 [0||=|| [|] (a)()) = 10z
V 2 (x)= 2 2 x)
2 (d (s) #2
((y +d (min(())))) (y. x)²
where the second inequality follows from 2a + 2 (a + b)² for any a, b R. and the last equality follows from (D.I. This completes the proof.
Lemma 6.4 The dilated entropy &e is differentiable and strictly convex on the relative interior := relint relinntcoo (o))))) Moreover, lim ([,)(a = oo {æn)n is sequence of points in C approaching the boundary of C.
Proof. Let := reoin)(co(X))) and let 8C == co(X) C. As every coordinate is positive inside the relative interior C, th is differentiable on C. Due to Lemma 6.3 it follows that also strictly convex on C.
Next consider sequence {rn)n with on E C' for all and lim In xx ôC. Consider vertex u E V such that x ["] > and there exists an edge = (u, v) such that x [e] = 0. Note that such vertex u exists otherwise xx E C. Now observe that
lim 200
lim [n m
In xn [w]l = ao.
Hence, we have lim
V 2 F l|a
Theorem 6.5
OMD with dilated entropy iterate-equivalent to HEDGE over the set of paths X'
Proof. Due Lemma 6.4 co(2'):
the solution of the following OMD equation lies in the relative interior of
3 < argmin { ( + Dos (x ( =cco(x
where (x)) is the dilated entropy and 17 log X/T.. That is, for all edges have Tr(e] 0.
30

---

For any vertex denote by 8 (v) and (v) the sets of incoming and outgoing edges from respectively. Recall that co(Xt is described by the following linear constraints:
9u (v) Σ
x|c|
Σ
2 = Vo V (s
cE (v)
CE)+(M) (n)
(x(x) =
Ø|c| =
(E)+(s)
(+(x)
Σ a|e|
eEO-(t) (t)
he(2)) ;= - [e] S
Let the Lagrangian be defined as:
Li(x, X, 11) = 7 Dy (1) (plaad( +
E (l))
vEV
eEE
By the KKT conditions, there exists tuple (ã des (4)) such that 0.. x.
0.
@x[e]
x== A=dr: p=
Due to complementary slackness and the fact that @c(e] > 0 for all E E, it follows that [4[e]] 0 for e E. Hence, we obtain:
In [c[c]
In T. 1/c1
X [u] xx(o))
3z 3z[u] Tr-1/u]
where (u, v).
Let (p) denote the probability of choosing path p round t. Observe that
P((p)
a.fel [2
x
zz-lee exp (-1)
(-n)
Σ
y yr-ile)
8z-1 [1]
6= Ep
6=
<=(u,)jp
(p-1 exp
Σ
y--2(e)
<=(u,))p
Thus, OMD with dilated entropy is equivalent to HEDGE over paths.
E Another Near-optimal OMD for DAGs
Let G = (V, E) be DAG, and let C (0, 1} represent all paths from the source vertex to the sink vertex According to Maiti et al. [32. there always exists strategically equivalent DAG in which the longest s-t path contains at most (log (2l)) edges. Therefore, without loss of generality, assume that the longest path from contains Olog (x() edges.
Let ye R be the loss vector observed round We construct modified non-negative loss vector
y _ such that:
There exists constant ar such that (æ, v() (x. yt) + 04 for any E X.
For any E X, it satisfies EeEF x 2 4.
Given the weight vector yt, we define, for each vertex E V, the quantities dmin (v) E R and druax (v) I. as the weights of the shortest and longest paths from s v, respectively. Clearly, d (s) (s) = 0, and -1 < dmiu (t) < d'mx(() <
We define the modified loss vector y I by assigning:
vil(u, v)] v ((, v)] + dmin (u) duann (v).
31

---

Then, for any a E X, we have (a, vi) (x, - -dmin (t).
We prove that Eee E 2 (elly < for any x X. Define function da : V R by da(r) ;= dmax(t) (v) dmin (v) [0.2] for each E V. Note that yl v) > 0 by the triangle inequality. Furthermore, using the inequality dmax 2 dmax + y: (u, vi], we get:
Vil(u, v)] S dmax(v) dmax(u) + dmin (u) dmin (v) = da(u) da(u).
Now, consider any path æ E X' with vertices vo = =s U1, Uk = t. We have:
Exlelu/lef=- Σ p S (da(v)) -ds(U--1))
<EB
k
2 (da(v:) - ds(o
= dda(t)² $4
Now consider the OMD update rule:
T argmin x)
T (V 3) + Do (()1)
where the regularizer is defined as
i
[ In [cc] H(c))
eEE
Let || ||l.II ((.))) denote the local norm induced by the Hessian of 6 at T,, and the corresponding dual 20(G.). norm is given by ( Using standard regret analysis, we have:
( max ( < 17 *cCo(X)
T
E(Regret(T)
min xcco(X)
(
+
t=1
T
1 max
(Hle) In(1 [(c)) + x(e)
+ 77
| 2 -
17 x)
eEE
T
C log |
log d + 17
Σ
11
t1
c log |X| log d + 4n T
where e is an absolute constant. The third inequality uses the fact that the number of edges in any path is upper bounded by Ollog (x)),, along with Jensen's 's inequality. The fourth inequality follows from the construction of y/- By setting n = /T log | log d, the regret is upper bounded by O( TT [ llog d).
Having established an alternative OMD algorithm for DAGs, we now outline general template for de- signing near-optimal OMD algorithms using the negative entropy regularizer for other combinatorial sets X C 1)
Lift the action set: Map X' to an equivalent higher-dimensional set X C (0, 1) where poly(d), such that the diameter of X small with respect to the negative entropy regularizer.
Change the loss vectors: Construct an equivalent non-negative loss vector such that the sum of squared dual norms is small.
F
Auxiliary Lemmas
Lemma E. (Yao's lemma). Let A be a set of deterministic algorithms, and ) a set of inputs. Let c(A, y) denote the cost incurred by deterministic algorithm A A on input y V, such as its regret.
32

---

Let 'D be distribution over inputs and R. be a class of distributions over deterministic algorithms. Then for any randomized algorithm R, we have:
min I8 DynDee(((A.))) AEA
max v)).
By Yao's lemma, to prove lower bound on the expected cost of any randomized algorithm. it suffices to exhibit a distribution over inputs under which every deterministic algorithm incurs high expected cost.
Remark:
Let {Ex) be T independent Lemma F.2 (Khintchine inequality (restated), Haagerup (66
Rademacher random variables with Pg(E+ = +1) = 1/2.. Let -1,.... TT E C. Then,
r
1
x
2
E
2
Lemma F.3 (Orabona and Pál (35). for any d E [ct, exp(333),) we have
There exists universal constants ej 2 8 and C2 > 0 such that
E
C2 Tolg d.
d
where (E, are i.i.d. Rademacher random variables with PPG,; =
Lemma F4. For any K < exp(T/3), there exists zero-mean distribution Dx over { {11, such that if y: ~ Dx for t 1, T. then
T le Bid
min [
Σ (=1
2 e0 log
where co > 0 some universal constant
Proof. Consider the universal constants and C2 from Lemma F3 If2 S K c1, define the distribution Dx k as the uniform distribution over {ei. -11) If y: Dx for t = 1.... T, then by
applying the same analysis in Theorem 3.2] obtain:
-E
min Σ KE[K] t=1
le vi) T/82 Tlog K/(8loge1)
On the other hand, if K 2 C₁. we define the distribution DR as the uniform distribution over (-1,+1} If yr Dr for l I,..., T,, then by applying the Lemma F33
obtain:
E
min iE K
fe Mi)
max BE K
(e
41)
2 c2 Vllg..
G
Numerical Lemmas
Lemma G.1. Let a, b > 0 be two numbers such that a 2 b. Then
a
b
2h
Proof. If we set
> 1, n |x]
then
z=n+k k, 0 1
33

---

s0
a
5
11 + k
11 1+
2b
2
2
2
Since 1,
1
5
11
11
+
2n
n21
Hence
a
S b
2b
Lemma G.2. For any > 3, (a/x)" is an increasing in the range [1, a/3].
Proof. It suffices to show that for every real E [1, a/4] the derivative of
f(x)
is strictly positive. Consider
g(x) == f(x) = ln
x In x 2
so
g'(x) = la (In + 1) In 1.
Whenever S a/3, have
(a)
3
In
> In
a/3
Since 3 ~ 1.098 > 1, it follows that
g'(x) in
a
2 I3
1>
x
Because f'(x) f(z)g (x) and f(x) > obtain
fl(x) > 0
for all s - a/3.
Lemma G.3. Denote by
X x (0, 13a
> m)
S x
x:
[m]
x11 +1/1
20
When m E [200, d/2], it satisfies that
X
S
< exp
X
20
m
34

---

Proof. We upper bound (X \\ S) by enumerating on possible values of l: := [ [m] x +
} = i $
[m]]
1 I-
Lmm/20j -1
11 | 8|=
=
Σ
m
d
m
k
k
k=0
d
[m/22]]
|lm/2///
em
[m/20]
ed
[m/20]
(as (m) [d )
m mm/20]
mm/20]
20ed
my/2
(20e)m/20
(due to Lemma G.2
20
(m/20)=
(20e) mn/10
(m/m)
m//20
d
(as (d/m) S (m)
(d/m))m
m
(m/20)
(20e) m1/10 (m01)
(m/d)m/20
(as m S d/2)
29m/110
exp
m
In
d
(as
(m/20)-(22) (20))(20))mm/))))))) 20m/ 10
S 1)
20
Since |
(a) we immediately reach the desired result.
35


Reviews:
[{"review_id": "5OiJ9GLs2y", "reviewer": "Reviewer_3jBY", "summary": "It is well known that the Hedge algorithm guarantees an external regret of O(sqrt{T log d}) in the learning with experts setting, and that this bound is tight up to constant factors. It is possible to apply Hedge to more general online learning settings -- for example, for online linear optimization when the action set is the polytope, one can run an instance of Hedge where each expert corresponds to a vertex of the polytope, getting an O(sqrt{T log V}) bound. But is this regret bound tight?\n\nThis paper studies this question for the case of *combinatorial action sets*, where the action set P of the learner is the convex hull of a subset of points in {0, 1}^d (named as it captures many combinatorial sets of interest). The authors prove the following set of results:\n\n1. First, they show that the regret bound of Hedge is within a sqrt(log d) factor of optimal -- in particular, that for any combinatorial polytope, there is a regret lower bound of Omega(sqrt{T log V / log d}). The proof of this result is a consequence of the Sauer-Shelah theorem (which bounds the number of distinct 0/1 points needed to contain a subset that projects to a hypercube).\n2. Second, they demonstrate cases where this separation is tight; specifically, they show that this separation is tight for m-sets (sets of points with Hamming weight m), by constructing a new optimal regularizer for these points (a convex combination of the quadratic and negative entropy regularizer).\n3. Thirdly, they show that Hedge is minimax optimal for all “Online Multitask Learning” problems (essentially, where the action set of the learner is the product of several simplices).\n4. Finally, they also show that Hedge is minimax optimal when P is the flow polytope in a DAG. They also show that Hedge can be interpreted as running FTRL with the dilated entropy regularizer.", "questions": "See above -- in general, feel free to reply to any aspect of the above review.", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "I think this is a very cool set of results! Surprisingly little is known about what the optimal minimax regret algorithms are for instance of online linear optimization -- while it is well understood in very classical settings (e.g. the learner plays actions in the l_1 or l_2 norm ball and the adversary plays actions in the polar), as soon as the learner / adversary action set becomes a little bit more complex it is not clear what the optimal regret bounds or algorithms are for. This is despite this being a very fundamental primitive in many applications (e.g. game theoretic applications, online learning in combinatorial domains). This paper provides a fairly thorough answer to this question for a very important class of action sets (aside from cases like the l_2 ball, it is hard to think of natural settings in the literature this does not capture). \n\nOne possible criticism of this paper is that the proofs are fairly simple (they are generally fairly immediate consequences of the correct observations). But I think despite this, these observations were certainly not well known to other practioners in the field (I have spent some time thinking about these questions, and none of these facts were obvious to me), and so I think there is a sizable subset of the NeurIPS audience that would appreciate these observations. \n\nQuestion: Section 6 only addresses the unit flow polytope formed by the convex hull of all single paths. Do you know if this result continues to hold for general flow polytopes (either allowing for any positive flow or a specific positive flow > 1?)? My guess is that the answer is no (and that the m-set example can be embedded in the higher flow polytope of some DAG -- e.g., maybe one where the max flow is m but there are d > m edges of capacity 1 connecting two vertices), but I haven’t thought carefully about this.", "was_revised": true, "final_justification": "After reading the other reviews and the author's response, my (positive) score remains unchanged. I think this is a very strong NeurIPS submission (making non-trivial progress on a very natural theoretical learning question), and was my favorite of submissions I reviewed this year.", "rebuttal": "We thank the reviewer for the positive feedback. We now address their concerns below.\n\n**Reviewer's question:**\nSection 6 only addresses the unit flow polytope formed by the convex hull of all single paths. Do you know if this result continues to hold for general flow polytopes (either allowing for any positive flow or a specific positive flow > 1?)?\n\n**Author's response:**\nIt remains an open question whether this result extends to general flow polytopes. We have given some thought to how one might design variants of Hedge to handle this general case. Resolving this case could yield tighter regret bounds for non-combinatorial sets."}, {"review_id": "oNDbRMZnnc", "reviewer": "Reviewer_vJEE", "summary": "This paper studies online learning over combinatorial decision sets $ \\\\mathcal{X} \\subset \\\\{0,1\\\\}^d $, \nwhere at each round the learner selects an action $x_t \\in \\mathcal{X}$, observes the loss vector $y_t$, and incurs loss$x_t^\\bot y_t$. The goal is to minimize cumulative regret with respect to the best fixed action in hindsight. The authors revisit the performance of the classical Hedge algorithm in the combinatorial setting. They show a general lower bound proving that Hedge is at most order $\\sqrt{\\log d}$ worst-case sub-optimal compared to its best known upper bounds.  The authors  demonstrate that this lower bound is tight for certain combinatorial structures; specifically, for m-sets where this bound is attained by an instance of mirror descent;  while Hedge  is provably suboptimal,  as proven by a lower bound on its regret for this combinatorial structure.  Finally, the authors show that Hedge is minimax optimal in other combinatorial structures such as online multitask learning and shortest-path problems in DAG.", "questions": "Does Theorem 4.6 still hold if Hedge is run with a decreasing learning rate? In particular, could an adaptive rate improve the result, or does the lower bound remain unaffected?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**: The problem studied is particularly relevant in applications, given the widespread use and simplicity of Hedge in practice. \nThe authors establish a worst-case lower bound for general combinatorial structures, showing that the Hedge algorithm is minimax optimal up to a$\\sqrt{⁡\\log d}$ factor. They demonstrate the tightness of this bound for m-sets, where the optimal regret is achieved by an instance of OMD, while also showing that it is provably not attainable by Hedge for some loss sequences. The authors show matching upper and lower bounds for Hedge on DAGs and in combinatorial structure for multitask learning. These results offers valuable insight into the complexity combinatorial online learning. \n\n**Weaknesses**:\n- the lower bounds presented are worst-case in nature, which makes it difficult to determine whether the (sub)optimality arises inherently from the combinatorial structure itself or from carefully constructed adversarial instances (that could belong to other strucutures as well). While this is understandable given the adversarial setting, it limits the interpretability of the results across broader classes of structures. \n- the results are somewhat ad hoc and tailored to each specific combinatorial domain, making it nontrivial to identify a unifying complexity measure that governs the complexity of combinatorial learning\n\n**Minor comments**: \n- typo in l.232\n- $co(X)$ is used l.145 before being introduced l.182", "was_revised": true, "final_justification": "The authors have successfully addressed my minor concerns during rebuttal.  And the results presented here could benefit the community in understanding the strengths and weaknesses of the well-adopted Hedge algorithm. I recommend acceptance.", "rebuttal": "We thank the reviewer for the positive feedback. We now address their concerns below.\n\n**Reviewer's comment:**\nThe lower bounds presented are worst-case in nature [...] The results are somewhat ad hoc and tailored to each specific combinatorial domain, making it nontrivial to identify a unifying complexity measure that governs the complexity of combinatorial learning.\n\n**Author's response:**\nWe appreciate the reviewer’s concern. While our lower bounds are worst-case, they do not stem from carefully constructed adversarial instances but rather arise inherently from the combinatorial structure itself. This is evident in the proof of our main general result (Theorem 3.2), where we establish that for any set $X \\subseteq ${$0,1$}$^d$, the regret is lower bounded by\n\n$$\n\\Omega\\left(\\sqrt{T \\cdot \\frac{\\log |X|}{\\log d}}\\right),\n$$\n\nvia a general reduction based on the Sauer–Shelah lemma. Combined with the $O(\\sqrt{T \\log |X|})$ regret bound of HEDGE, this shows that both the upper and lower bounds scale with $\\log |X|$, suggesting that it serves as a natural and interpretable measure of complexity.\n\nThe additional lower bounds we provide for specific domains such as m-sets and multitask learning are not tailored constructions, but are intended to demonstrate that the general bound is tight in some cases and loose in others—specifically up to a $\\sqrt{\\log d}$ factor. These examples clarify when HEDGE is optimal and when it is provably suboptimal.\n\n---\n\n**Reviewer's question:**\nDoes Theorem 4.6 still hold if Hedge is run with a decreasing learning rate?\n\n**Author's response:**\nWe thank the reviewer for raising this question. Decreasing learning rates are typically used to obtain anytime guarantees, while adaptive learning rates (e.g., AdaHedge) aim to improve regret on easier instances. However, these modifications are not known to improve the worst-case regret of HEDGE. Although Theorem 4.6 analyzes HEDGE with a fixed learning rate, we believe the lower bound should continue to hold, possibly under a modified construction, even for variants with decreasing or adaptive learning rates. Formalizing this remains an interesting direction for future work."}, {"review_id": "sluKUy9tEw", "reviewer": "Reviewer_v7MV", "summary": "This paper studies the problem of prediction with expert advice in a combinatorial setting (i.e., full-information setting). While most of previous works focus on characterizing regret's upper bounds of various algorithms, this paper focus on constructing hard examples for establishing regret's lower bounds and from there, analyze the optimality (or sub-optimality) of the famous HEDGE algorithm. In particular, the authors show that Hedge is near-optimality (up to a logarithm term of the dimension) in any setting, is strictly suboptimal in a special class, and optimal in another class of problem.", "questions": "- Line 776 (Appendix A) assume that $T$ divides $|\\mathcal{I}|$. If this is not the case, how does Inequality in Line 787 works? In particulatr, if we partition the T rounds into $|\\mathcal{I}| - 1$ equal-length segments and 1 last segment that is smaller than that. Does this mean that there is a set {t : it = i} whose size is strictly smaller than $T$ / |\\mathcal{I}|$. As a consequence Inequality in Line 787 is a \" strictly less than\" rather than a \"less or equal\" ? \n\n- Is Lemma F.3 a restatement of Theorem 7 of (Orabona and Pál [35])? If that's the case, can you explain where does the condition c1 >= 8 comes from (or which term is it equivalent to in Orabona andPal [35])? \nMoreover, while this is a bit picky, if it is possible, I think you should follow the  template of Orabona and Pal  to obtain the explicit value of the involved constant. The reason is because such constant in Orabona and Pal contains the term log(d) in it; therefore, it is better to check and make sure that we do not misjudge the order of log(d) when writing big-oh(sqrt(Tlog(d)).\nThis is quite important as this constant in Lemma F.3 leads to constant in Lemma F.4 and hence, directly involves in Theorem 5.1.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is quite clearly written and sufficiently easy to follow. \n- As far as I know, the contribution is clear and original.\n- Significance: While the key question is quite simple, it is interesting to establish the lower bound guarantees of HEDGE as it is a well-used algorithm.\n\nWeaknesses:\n- All proofs are put in Appendices so it is a bit hard to have an immediate intuition where does the result come from. \n- The notation  Phi $\\varphi$ is used and reused repeatedly throughout various sections to refer to different choices/variants of the regularizer. It would be better if the authors distinguish these notations; for example, denote Phi_{m-set} in (4.1) and  Phi_{entropy} in 6.1.\n- A minor point: all results contain implicit constants that might involve a leading term (for example, dimension d, see questions for more details).\nThe paper limits to the full-information setting. It would be interesting to make connection to previously known results of regret's lower bounds in other setting (for example, bandit). \n\nThe implicit constants make it hard to check the proof. \n\nLacks some numerical experiments or concrete example to confirm the results. For instance, construct a toy example of a hard-case and show the numerical regret of several algorithms would be interesting.", "was_revised": true, "final_justification": "The authors have provided adequate responses to my questions. The only remaining concern is the lack of a numerical experiment showing a hard-case where standard algorithms fall into the theoretically proven bound. \n\nAfter reading the other reviewers' opinions, I opt to maintain my original score.", "rebuttal": "We thank the reviewer for the positive feedback. We now address their concerns below.\n\n**Reviewer's comment:**\nAll proofs are put in Appendices so it is a bit hard to have an immediate intuition where does the result come from.\nThe notation $\\Phi$ is used and reused repeatedly throughout various sections to refer to different choices/variants of the regularizer.\n\n**Author's response:**\nWe will provide more intuition and change the notation accordingly in the final version.\n\n---\n\n**Reviewer's question:**\nLine 776 (Appendix A) assume that $T$ divides $|\\mathcal{I}|$. If this is not the case, how does Inequality in Line 787 work?\n\n**Author's response:**\nThe analysis for the case when $|\\mathcal{I}|$ does not divide $T$ proceeds identically to the case where $|\\mathcal{I}|$ divides $T$. The only difference is that for the first $T' = |\\mathcal{I}| \\cdot \\lfloor T/|\\mathcal{I}| \\rfloor$ rounds, we use the same hard instance, and for the remaining rounds $T'+1, T'+2, \\ldots, T$, we assign loss vectors that are zero across all coordinates. Since $T' \\geq T/2$, this still yields the lower bound $\\Omega(\\sqrt{T \\log |X| / \\log d})$.\n\n---\n\n**Reviewer's comment and question:** All results contain implicit constants that might involve a leading term (for example, dimension d). Is Lemma F.3 a restatement of Theorem 7 of (Orabona and Pál [35])? If that's the case, Where does the condition $c_1 \\geq 8$ come from (or which term is it equivalent to in Orabona and Pál \\[35])?\n\n**Author's response:**\nYes, Theorem F.3 in our paper is a restatement of Theorem 7. The expectation is lower bounded by $0.09\\sqrt{n \\ln d} - 2\\sqrt{n}$, which in turn is at least $0.01\\sqrt{n \\ln d}$ whenever $\\sqrt{\\ln d} \\geq 25$. Hence, there exists a universal constant $c_1$ (clearly greater than 8 which is arbitrarily chosen) and independent of $d$, such that Theorem F.3 holds for all $d \\in [c_1,\\exp(T/3)]$. As a result, none of the bounds and constants in the paper implicitly hide any dependence on $d$."}, {"review_id": "QtitXrCF3J", "reviewer": "Reviewer_fnGB", "summary": "The paper studies the classical Hedge algorithm for online learning in combinatorial settings. The main contribution is a series of upper and lower bounds on the regret that establish near-optimality of Hedge. In particular, the paper identifies subproblems of the combinatorial setting where Hedge is provable optimal respectively suboptimal by a factor $\\log(d)$.", "questions": "Are you aware of setting where Hedge achieves the minimax lower bound $\\sqrt{ T \\log|X|/\\log(d)}$?", "limitations": "While the paper addresses the regret bounds for the Hedge algorithm (and minimax bounds), one would hope to have a general characterisation of the regret for any given X, e.g. by introducing a complexity measure that depends on the set X (either combinatorial or even in the general case). Another open question is to design an algorithm that is near-optimal for a larger family or all combinatorial sets.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper makes an important contribution to the online learning literature. Hedge is a classical algorithms but there are still open questions around its optimality in various settings. This paper focuses on the combinatorial setting, where the decision set is a subset of $\\\\{0,1\\\\}^d$. The authors first establish that any algorithm suffers a worst-case regret of $\\Omega(\\sqrt{T \\log(|X|)/ \\log d})$ ,where X is the decision set. The known upper bound of Hedge is $O(\\sqrt{T \\log(|X|)}$, hence the question is if the gap is loose or if one of the bounds can be improved. The paper subsequently establishes further lower and upper bounds for the Hedge algorithm, showing cases where Hedge is provably suboptimal, and settings where the lower bound can be improved.\n\nThe paper is very well written and easy to follow. Related work is discussed appropriately.\n\nSome minor suggestions for improvement are as follows:\n* consider include definitions of important quantities, such es worst-case and minimax regret, and iterate-equivalence. \n* In line 194, I assume you invoke an existing regret lower bound over the set I. Consider citing or stating the result again in this context.\n* Line 198: What is the expectation over here? How does the expected regret related to the original objective defined in line 142?", "was_revised": true, "final_justification": "I would like to thank the authors for the detailed response. After reading the reviews and the author replies, my overall evaluation stays positive and I recommend acceptance.", "rebuttal": "We thank the reviewer for the positive feedback. We now address their concerns below.\n\n**Reviewer's question:**\nAre you aware of a setting where Hedge achieves the minimax lower bound $\\sqrt{T \\log |X| / \\log d}$?\n\n**Author's response:**\nWe are not aware of a setting where Hedge achieves the minimax lower bound $\\sqrt{T \\log |X| / \\log d}$. We conjecture that Hedge has a lower bound of $\\sqrt{T \\log |X|}$ for any combinatorial set $X$.\n\n---\n\n**Reviewer's comment:**\nConsider including definitions of important quantities, such as worst-case and minimax regret, and iterate-equivalence.\n\n**Author's response:**\nWe thank the reviewer for the suggestion and will incorporate this change in the final version.\n\n---\n\n**Reviewer's comment:**\nIn line 194, I assume you invoke an existing regret lower bound over the set $\\mathcal{I}$. Consider citing or stating the result again in this context.\n\n**Author's response:**\nOur result is in the appendix. We will state the result again in the main body.\n\n---\n\n**Reviewer's comment:**\nLine 198: What is the expectation over here? How does the expected regret relate to the original objective defined in line 142?\n\n**Author's response:**\nThe algorithm might be randomized and hence the expectation is over the randomness of the algorithm.\n\n---\n\n**Reviewer's comment (limitations):**\nOne would hope to have a general characterisation of the regret for any given $X$, e.g., by introducing a complexity measure that depends on the set $X$.\n\n**Author's response:**\nWe agree that a general characterization of regret in terms of a complexity measure tailored to the decision set $X$, as well as the design of algorithms that are near-optimal for broader families of non-combinatorial sets, are important directions for future work. In particular, identifying variants of HEDGE that achieve near-optimal regret for arbitrary sets $X$ remains a compelling and open research question. Our work takes a step in this direction by establishing the near-optimality of HEDGE up to a $\\sqrt{\\log d}$ factor for all $X \\subseteq ${$0,1$}$^d$, and showing regimes where this gap is provably unavoidable, but we fully agree that closing this gap in general remains an open challenge."}, {"review_id": "rveCGMXzNe", "reviewer": "Reviewer_aAm5", "summary": "The authors study the regret performance of HEDGE in combinatorial settings. They ask whether it’s universally optimal and conclude \"nearly\" by providing an algorithm-independent regret lower bound that match the well-known upper bound up to $\\sqrt{\\log d}$ factors.\n\nThey then provide some clarity on the nature of HEDGE's (sub-)optimality by studying two different combinatorial task instances where HEDGE is optimal and where it isn’t. \n\nFor the optimal case, they provide tighter algorithm-independent lower bounds for the online multiask learning setting, which match HEDGE's upper bound.\n\nFor the sub-optimal case, they show their original lower bound is tight for the $m$-sets task, and is enjoyed by a modified OMD algorithm. They also show that HEDGE incurs a strictly worse regret compared to the modified OMD by a $\\sqrt{\\log d}$ factor.\n\nFinally, they show how regularized OMD is iterate-equivalent to HEDGE, and therefore enjoys near-optimal regret for shortest-path problems on DAGs.", "questions": "1. In the introduction, the adversary is described as potentially reactive, in that it can choose loss vectors as a function of the history $\\mathcal{F}_t.$ However, in the main theorems, the adversary is described as oblivious, fixing the losses at the start of the trial. I may have misunderstood something, but can the authors please comment on whether they are focusing on an adaptive or oblivious adversary?\n\n2. Intuitively, why is the structure of the $m$-sets task poorly aligned with HEDGE while online multitask learning is well aligned? Currently the paper requires the reader to engage with the full proof to appreciate the differences. A discussion that helps the reader more readily appreciate the essential differences would be a valuable contribution to this work.", "limitations": "The authors should add some additional commentary addressing the weaknesses I mentioned.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "*Strengths:*\n- Compelling theoretical contributions to help clarify the nature of HEDGE’s (sub-)optimality on an important class of online learning problems\n- Organisation is very clear\n- Focus of the paper builds well, natural questions are addressed\n- FIgure nicely summarizes contributions\n\n*Weaknesses:*\n- While a gap of $\\sqrt{\\log d}$ is non-trivial, it may represent a very modest gap for many of the cited applications. The authors should add a short section discussing the significance of this gap in context of their cited motivations.\n- Although the main theorems are well stated and clear, the paper lacks a discussion on the essence of what makes $m$-sets a particularly challenging task in comparison to online multitask learning for HEDGE. The authors should add a short section providing some intuition for why one might expect HEDGE to be optimal in one but not in the other.\n- The paper mentions an adaptive adversary in the preliminaries (lines 139-140), but in the provided theorems the adversary is oblivious. The authors should address this inconsistency.", "was_revised": true, "final_justification": "This paper provides compelling theoretical contributions to help clarify the nature of HEDGE’s (sub-)optimality on an important class of online learning problems. The organisation is very clear, the focus of the paper builds well, and natural questions are addressed. The authors addressed my only questions sufficiently, and I stand by my original rating of accept.", "rebuttal": "We thank the reviewer for the positive feedback. We now address their concerns below.\n\n**Reviewer's question:**\nCan the authors please comment on whether they are focusing on an adaptive or oblivious adversary?\n\n**Author's response:**\nThe upper bound results for our algorithms hold against any type of adversary, including adaptive ones. For the lower bound, it suffices to consider an oblivious adversary, since a lower bound in this setting also implies a lower bound in the adaptive case.\n\n---\n\n**Reviewer's question:**\nIntuitively, why is the structure of the m-sets task poorly aligned with HEDGE while online multitask learning is well aligned? [...] A discussion that helps the reader more readily appreciate the essential differences would be a valuable contribution to this work.\n\n**Author's response:**\nWe appreciate the reviewer’s suggestion. At a high level, HEDGE operates without exploiting the underlying structure of the decision set and treats each element of $X$ as an individual expert. This aligns well with settings like online multitask learning, where the decision set is a Cartesian product of simplices (HEDGE is known to be optimal for simplices), and this structure allows HEDGE to perform optimally.\n\nIn contrast, m-sets impose a strong global constraint: each vector must contain exactly $m$ ones. This introduces dependencies among coordinates that HEDGE fails to leverage. As a result, HEDGE incurs regret scaling with $\\log |X|$, whereas more structure-aware algorithms (such as OMD with a tailored regularizer) can achieve strictly better bounds. We agree that adding this discussion would improve the paper and will incorporate a brief section to highlight this intuition.\n\nNonetheless, while the present work focuses on establishing regret bounds, a deeper understanding of the conditions under which HEDGE performs well or poorly could inform the development of more effective algorithms. We view this as a promising direction for future work.\n\n---\n\n**Reviewer's comment:**\nWhile a gap of $\\log d$ is non-trivial, it may represent a very modest gap for many of the cited applications. The authors should add a short section discussing the significance of this gap in context of their cited motivations.\n\n**Author's response:**\nWe thank the reviewer for the suggestion and will incorporate this change in the final version."}]

Author rebuttal:

Meta-review: This paper provides worst-case near-optimal bounds for Hedge in several combinatorial settings. The reviewing team was overwhelmingly positive about the submission. Clear accept. Good job!

Please, incorporate all the feedback received from the reviewers in the revised version.
Decision: Accept (spotlight)