Virtual extension complexity can vastly outperform classic extension complexity
Two Linear Programs are Better than One
Computational ComplexityDiscrete MathematicsMachine Learning
Summary
When trying to represent shapes called polytopes, it's important to measure how complicated that representation is. The authors study a new measure called virtual extension complexity, which looks at how combining two simpler shapes can represent a complex one more easily. They show that using two shapes instead of one can make this complexity much smaller, sometimes exponentially so. They also find examples where this simplification isn't enough and explore how complicated polygons behave under this measure.
What this means in practice
- •For optimization algorithm designers: Refine polytope representations in optimization models by considering virtual extension complexity to reduce problem size and potentially improve solver performance.
- •For neural network theorists: Use insights into virtual extension complexity to better understand the geometric complexity underlying neural network representations.
A theory result. No direct application yet.
Authors
Alexander E. Black, Christoph Hertrich, Stefan Kober, Georg Loho
Abstract
The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.