Physics Maths Engineering
CPD-Structured Multivariate Polynomial Optimization
Peer Reviewed
Related Subjects
Abstract
We introduce the Tensor-Based Multivariate Optimization (TeMPO) framework for use in nonlinear optimization problems commonly encountered in signal processing, machine learning, and artificial intelligence. Within our framework, we model nonlinear relations by a multivariate polynomial that can be represented by low-rank symmetric tensors (multi-indexed arrays), making a compromise between model generality and efficiency of computation. Put the other way around, our approach both breaks the curse of dimensionality in the system parameters and captures the nonlinear relations with a good accuracy. Moreover, by taking advantage of the symmetric CPD format, we develop an efficient second-order Gauss–Newton algorithm for multivariate polynomial optimization. The presented algorithm has a quadratic per-iteration complexity in the number of optimization variables in the worst case scenario, and a linear per-iteration complexity in practice. We demonstrate the efficiency of our algorithm with some illustrative examples, apply it to the blind deconvolution of constant modulus signals, and the classification problem in supervised learning. We show that TeMPO achieves similar or better accuracy than multilayer perceptrons (MLPs), tensor networks with tensor trains (TT) and projected entangled pair states (PEPS) architectures for the classification of the MNIST and Fashion MNIST datasets while at the same time optimizing for fewer parameters and using less memory. Last but not least, our framework can be interpreted as an advancement of higher-order factorization machines: we introduce an efficient second-order algorithm for higher-order factorization machines.
Key Questions about CPD-Structured Multivariate Polynomial Optimization
The article "CPD-Structured Multivariate Polynomial Optimization" by Muzaffer Ayvaz and Lieven De Lathauwer introduces the Tensor-Based Multivariate Optimization (TeMPO) framework, designed to address nonlinear optimization challenges prevalent in signal processing, machine learning, and artificial intelligence. This framework models nonlinear relationships using multivariate polynomials represented by low-rank symmetric tensors, effectively balancing model generality with computational efficiency. By leveraging the Canonical Polyadic Decomposition (CPD) format, the authors develop an efficient second-order Gauss–Newton algorithm for multivariate polynomial optimization. This algorithm demonstrates quadratic per-iteration complexity in the number of optimization variables in the worst-case scenario and linear per-iteration complexity in practice. The study showcases the algorithm's efficiency through illustrative examples, including blind deconvolution of constant modulus signals and classification tasks in supervised learning. Notably, TeMPO achieves comparable or superior accuracy to multilayer perceptrons (MLPs), tensor networks with tensor trains (TT), and projected entangled pair states (PEPS) architectures for classifying the MNIST and Fashion MNIST datasets, while optimizing for fewer parameters and utilizing less memory. Additionally, the framework can be interpreted as an advancement of higher-order factorization machines, introducing an efficient second-order algorithm for these machines. Source
1. How does the TeMPO framework model nonlinear relationships in optimization problems?
The TeMPO framework models nonlinear relationships by representing multivariate polynomials using low-rank symmetric tensors, effectively balancing model generality with computational efficiency. Source
2. What is the computational complexity of the second-order Gauss–Newton algorithm developed in the study?
The second-order Gauss–Newton algorithm exhibits quadratic per-iteration complexity in the number of optimization variables in the worst-case scenario and linear per-iteration complexity in practice. Source
3. How does TeMPO compare to other machine learning architectures in terms of accuracy and resource utilization?
TeMPO achieves comparable or superior accuracy to multilayer perceptrons (MLPs), tensor networks with tensor trains (TT), and projected entangled pair states (PEPS) architectures for classifying the MNIST and Fashion MNIST datasets, while optimizing for fewer parameters and utilizing less memory. Source
