Online Learning of Combinatorial Objects via Extended Formulation
This provides a general framework for efficient online learning of combinatorial objects like Huffman trees and permutations, addressing scalability issues for applications in optimization and machine learning, though it is incremental as it builds on existing extended formulation techniques.
The paper tackles the computational expense of online learning for combinatorial objects by using extended formulations to encode polytopes in higher-dimensional spaces with polynomially many facets, resulting in algorithms with regret bounds that match or improve on state-of-the-art for permutations and Huffman trees, such as within a factor of O(√log(n)).
The standard techniques for online learning of combinatorial objects perform multiplicative updates followed by projections into the convex hull of all the objects. However, this methodology can be expensive if the convex hull contains many facets. For example, the convex hull of $n$-symbol Huffman trees is known to have exponentially many facets (Maurras et al., 2010). We get around this difficulty by exploiting extended formulations (Kaibel, 2011), which encode the polytope of combinatorial objects in a higher dimensional "extended" space with only polynomially many facets. We develop a general framework for converting extended formulations into efficient online algorithms with good relative loss bounds. We present applications of our framework to online learning of Huffman trees and permutations. The regret bounds of the resulting algorithms are within a factor of $O(\sqrt{\log(n)})$ of the state-of-the-art specialized algorithms for permutations, and depending on the loss regimes, improve on or match the state-of-the-art for Huffman trees. Our method is general and can be applied to other combinatorial objects.