(MPO)²: Multivariate Polynomial Optimization based on Matrix Product Operators

Central to machine learning is the ability to perform universal function approximation and learn complex input-output relationships from limited numbers of observations. Multivariate polynomial models offer a natural way to express such relationships through multiplicative feature interactions, but their coefficient tensors grow exponentially with the polynomial degree. Existing tensorized polynomial models reduce this cost, yet canonical polyadic decompositions have rank-limited expressivity and tensor train formulations are feature order dependent. We introduce (MPO)$^2$, a multivariate polynomial optimization framework based on matrix product operators that combines learned MPO feature embeddings with compact MPO polynomial weight tensors. This yields feature order independent polynomial representations that can incorporate structured operators such as projections, convolutions, and masks for weight tensor symmetries. Across regression and classification benchmarks, (MPO)$^2$ improves over existing tensor decomposition based polynomial models and provides a flexible alternative for efficient polynomial function approximation.