Polytime Decomposition of Generalized Submodular Base Polytopes with Efficient Sampling

Aadirupa Saha
Proceedings of The 12th Asian Conference on Machine Learning, PMLR 129:625-640, 2020.

Abstract

We consider the problem of efficient decomposition of a given point $x$ in an $n$-dimensional convex polytope into convex combination of its extreme points. Besides the widespread scopes of the problem in theory of convex polytopes in mathematics, the problem also has applications in online combinatorial optimization problems. Towards this we first propose a general class of convex polytopes–Generalized Submodular Base Polytopes (GSBPs)–that includes several well known convex polytopes as its special case including permutahedron, $k$-forest, spanning tree, combinatorial subset choice polytopes. We next propose a general decomposition algorithm for above class of GSBPs that uses the novel idea of first decomposing the given point into at most $n$ \emph{face centers}, and further decomposing each face center into \emph{extreme points} of their corresponding faces. In addition, we discover a few special class of \emph{partition-respecting} and \emph{symmetric} GSBPs for which the above two steps could be performed in respectively $O(n^2 + nT(f))$ and $O(n^2T(f))$ time. We also give a complete characterization of the underlying submodular function $f$, for which the associated GSBP satisfies the above properties. One interesting fact is we show that the support of the resulting decomposition with our proposed algorithm is only $poly(n)$ in the number of extreme points which respects \emph{efficient sampling} from the resulting distribution. Finally we corroborate our theoretical results with empirical evaluations.

Cite this Paper


BibTeX
@InProceedings{pmlr-v129-saha20a, title = {Polytime Decomposition of Generalized Submodular Base Polytopes with Efficient Sampling}, author = {Saha, Aadirupa}, booktitle = {Proceedings of The 12th Asian Conference on Machine Learning}, pages = {625--640}, year = {2020}, editor = {Pan, Sinno Jialin and Sugiyama, Masashi}, volume = {129}, series = {Proceedings of Machine Learning Research}, month = {18--20 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v129/saha20a/saha20a.pdf}, url = {https://proceedings.mlr.press/v129/saha20a.html}, abstract = {We consider the problem of efficient decomposition of a given point $x$ in an $n$-dimensional convex polytope into convex combination of its extreme points. Besides the widespread scopes of the problem in theory of convex polytopes in mathematics, the problem also has applications in online combinatorial optimization problems. Towards this we first propose a general class of convex polytopes–Generalized Submodular Base Polytopes (GSBPs)–that includes several well known convex polytopes as its special case including permutahedron, $k$-forest, spanning tree, combinatorial subset choice polytopes. We next propose a general decomposition algorithm for above class of GSBPs that uses the novel idea of first decomposing the given point into at most $n$ \emph{face centers}, and further decomposing each face center into \emph{extreme points} of their corresponding faces. In addition, we discover a few special class of \emph{partition-respecting} and \emph{symmetric} GSBPs for which the above two steps could be performed in respectively $O(n^2 + nT(f))$ and $O(n^2T(f))$ time. We also give a complete characterization of the underlying submodular function $f$, for which the associated GSBP satisfies the above properties. One interesting fact is we show that the support of the resulting decomposition with our proposed algorithm is only $poly(n)$ in the number of extreme points which respects \emph{efficient sampling} from the resulting distribution. Finally we corroborate our theoretical results with empirical evaluations.} }
Endnote
%0 Conference Paper %T Polytime Decomposition of Generalized Submodular Base Polytopes with Efficient Sampling %A Aadirupa Saha %B Proceedings of The 12th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Sinno Jialin Pan %E Masashi Sugiyama %F pmlr-v129-saha20a %I PMLR %P 625--640 %U https://proceedings.mlr.press/v129/saha20a.html %V 129 %X We consider the problem of efficient decomposition of a given point $x$ in an $n$-dimensional convex polytope into convex combination of its extreme points. Besides the widespread scopes of the problem in theory of convex polytopes in mathematics, the problem also has applications in online combinatorial optimization problems. Towards this we first propose a general class of convex polytopes–Generalized Submodular Base Polytopes (GSBPs)–that includes several well known convex polytopes as its special case including permutahedron, $k$-forest, spanning tree, combinatorial subset choice polytopes. We next propose a general decomposition algorithm for above class of GSBPs that uses the novel idea of first decomposing the given point into at most $n$ \emph{face centers}, and further decomposing each face center into \emph{extreme points} of their corresponding faces. In addition, we discover a few special class of \emph{partition-respecting} and \emph{symmetric} GSBPs for which the above two steps could be performed in respectively $O(n^2 + nT(f))$ and $O(n^2T(f))$ time. We also give a complete characterization of the underlying submodular function $f$, for which the associated GSBP satisfies the above properties. One interesting fact is we show that the support of the resulting decomposition with our proposed algorithm is only $poly(n)$ in the number of extreme points which respects \emph{efficient sampling} from the resulting distribution. Finally we corroborate our theoretical results with empirical evaluations.
APA
Saha, A.. (2020). Polytime Decomposition of Generalized Submodular Base Polytopes with Efficient Sampling. Proceedings of The 12th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 129:625-640 Available from https://proceedings.mlr.press/v129/saha20a.html.

Related Material