Introduction
In online combinatorial optimization, a learner is tasked with choosing a complex structure—such as a spanning tree in a graph or a specific permutation of items—in each round of a sequence, without prior knowledge of the associated costs. The ultimate goal is to minimize regret, defined as the difference between the learner's total accumulated loss and the loss of the best fixed structure chosen in hindsight.
Historically, this problem has faced two major hurdles. First is computational complexity: the number of possible structures often scales exponentially (e.g., $n!$ permutations), rendering naive approaches like the standard Hedge algorithm computationally intractable. Second is the representation gap: previous efficient algorithms were largely siloed. Some were strictly designed for Boolean (0-1) representations, while others were highly tailored to specific submodular functions. Until now, there has been no unified theoretical framework capable of handling arbitrary vector representations of a combinatorial space.
This paper bridges that gap by introducing Low-Dimensional Online Mirror Descent (LDOMD), a unified framework that represents complex decision spaces as low-dimensional convex polytopes, achieving tighter regret bounds and generalizing several state-of-the-art methods.
The LDOMD Framework
Instead of maintaining a probability distribution over every possible exponential structure, LDOMD operates within a lower-dimensional vector space where the combinatorial structures are represented simply as vertices of a convex polytope.
The algorithm is driven by two key geometric operations:
- Bregman Projection Step: After receiving a loss vector and updating the current "state" in the dual space, the algorithm projects that state back onto the polytope using a Bregman divergence (such as KL-divergence or squared Euclidean distance).
- Decomposition Step: The algorithm takes this projected point inside the polytope and efficiently expresses it as a convex combination (a weighted average) of the polytope's vertices. This allows the learner to sample and play a specific, valid combinatorial structure.
By formalizing these steps, LDOMD generalizes previous methods like the Component Hedge algorithm (typically used for 0-1 polytopes) and recent advances in submodular polytopes. It provides a universal "recipe" for online learning: if one can find an efficient way to decompose and project for a specific polytope, one can derive a regret-optimal algorithm.
Key Insights and Theoretical Applications
A central insight of the paper is that the polytope is the key. The framework shifts the analytical focus away from the discrete structures themselves and toward the geometry of the convex polytope formed by their vector representations. The "shape" of the regret bound is fundamentally determined by whether a representation is Boolean or continuous.
While most prior work focused exclusively on 0-1 (Boolean) vectors, this paper demonstrates that LDOMD is equally powerful for general polytopes where vertices are not necessarily 0-1. The authors evaluate their framework by deriving regret bounds and algorithmic complexities for several fundamental combinatorial structures:
- Matroid Polytopes (e.g., Spanning Trees)
- Submodular Base Polytopes
- Permutahedrons (useful for ranking and scheduling)
- Transportation Polytopes (a novel application introduced in this work)
Main Results
The theoretical guarantees provided by LDOMD match or exceed the best-known specialized algorithms:
- Optimal Regret for 0-1 Polytopes: For 0-1 polytopes of "size" $m$ in $d$ dimensions, LDOMD achieves a regret bound of $O(m\sqrt{T \ln(d/m)})$, which is essentially optimal.
- Breakthrough in Online Transportation: The authors provide the first specialized treatment of the online transportation problem. They develop a novel $O(m^3n^3)$ decomposition algorithm based on spanning forests in bipartite graphs, utilizing Sinkhorn balancing for efficient projection.
- Transportation Regret Bounds: For a transportation problem with a total supply $q$, the framework guarantees a regret bound of $O(q\sqrt{T \ln(\max(mn, q))})$.
Limitations and Future Directions
While LDOMD offers a powerful unifying theory, its practical application is entirely dependent on the algorithmic efficiency of the decomposition and projection steps. For many complex polytopes, these operations remain computationally expensive or currently lack known polynomial-time algorithms.
Furthermore, for the online transportation problem, the projection step relies on Sinkhorn balancing, which is an approximate method. Although the authors argue this approximation does not significantly degrade the regret, a more rigorous theoretical analysis of the trade-off between approximation error and regret is a promising area for future research. Finally, the current framework operates in the "full information" setting, where the learner observes the entire loss vector after each round. Adapting LDOMD to the "bandit" setting—where the learner only observes the loss of the specific structure they chose—remains a critical next step for the field.
Summary updated