Online Learning of Combinatorial Objects via Extended Formulation

Holakou Rahmanian, David P. Helmbold, S. V. N. Vishwanathan
Proceedings of Algorithmic Learning Theory, PMLR 83:702-724, 2018.

Abstract

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. We get around this difficulty by exploiting extended formulations, 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 $\Ocal(\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-rahmanian18a, title = {Online Learning of Combinatorial Objects via Extended Formulation}, author = {Rahmanian, Holakou and Helmbold, David P. and Vishwanathan, S. V. N.}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {702--724}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/rahmanian18a/rahmanian18a.pdf}, url = {https://proceedings.mlr.press/v83/rahmanian18a.html}, abstract = { 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. We get around this difficulty by exploiting extended formulations, 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 $\Ocal(\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. } }
Endnote
%0 Conference Paper %T Online Learning of Combinatorial Objects via Extended Formulation %A Holakou Rahmanian %A David P. Helmbold %A S. V. N. Vishwanathan %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-rahmanian18a %I PMLR %P 702--724 %U https://proceedings.mlr.press/v83/rahmanian18a.html %V 83 %X 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. We get around this difficulty by exploiting extended formulations, 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 $\Ocal(\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.
APA
Rahmanian, H., Helmbold, D.P. & Vishwanathan, S.V.N.. (2018). Online Learning of Combinatorial Objects via Extended Formulation. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:702-724 Available from https://proceedings.mlr.press/v83/rahmanian18a.html.

Related Material