On the Universal Near Optimality of Hedge in Combinatorial Settings

We thank the reviewer for the positive feedback. We now address their concerns below.

Reviewer's question: Can the authors please comment on whether they are focusing on an adaptive or oblivious adversary?

Author's response: The 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.

Reviewer's question: Intuitively, 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.

Author's response: We 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.

In 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.

Nonetheless, 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.

Reviewer's comment: While 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.

Author's response: We thank the reviewer for the suggestion and will incorporate this change in the final version.

We thank the reviewer for the positive feedback. We now address their concerns below.

Reviewer's question: Are you aware of a setting where Hedge achieves the minimax lower bound $\sqrt{T \log |X| / \log d}$?

Author's response: We 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$.

Reviewer's comment: Consider including definitions of important quantities, such as worst-case and minimax regret, and iterate-equivalence.

Author's response: We thank the reviewer for the suggestion and will incorporate this change in the final version.

Reviewer's comment: In 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.

Author's response: Our result is in the appendix. We will state the result again in the main body.

Reviewer's comment: Line 198: What is the expectation over here? How does the expected regret relate to the original objective defined in line 142?

Author's response: The algorithm might be randomized and hence the expectation is over the randomness of the algorithm.

Reviewer's comment (limitations): 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$.

Author's response: We 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.

We thank the reviewer for the positive feedback. We now address their concerns below.

Reviewer's comment: All proofs are put in Appendices so it is a bit hard to have an immediate intuition where does the result come from. The notation $\Phi$ is used and reused repeatedly throughout various sections to refer to different choices/variants of the regularizer.

Author's response: We will provide more intuition and change the notation accordingly in the final version.

Reviewer's question: Line 776 (Appendix A) assume that $T$ divides $|\mathcal{I}|$. If this is not the case, how does Inequality in Line 787 work?

Author's response: The 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})$.

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])?

Author's response: Yes, 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$.

We thank the reviewer for the positive feedback. We now address their concerns below.

Reviewer's comment: The 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.

Author's response: We 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

via 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.

The 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.

Reviewer's question: Does Theorem 4.6 still hold if Hedge is run with a decreasing learning rate?

Author's response: We 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.

We thank the reviewer for the positive feedback. We now address their concerns below.

Reviewer's question: 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?)?

Author's response: It 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.