PROMETHEUS: PRObability Mass Estimation in Tensors with Hidden Elements Using Structure (Methods, Theory, and Applications)

• Applicant: Professor Dr.-Ing. Martin Haardt
• Subject Area: Communication Technology and Networks, High-Frequency Technology and Photonic Systems, Signal Processing and Machine Learning for Information Technology
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 462458843

In the PROMETHEUS project, we will devise, explore, and analyze new tools for learning the statistical behavior of discrete random vectors (RVs) from partial realizations thereof. More specifically, the joint probability mass function (PMF) of the discrete-valued elements of the RV takes the form of a multi-way tensor. Our goal is to estimate the PMF tensor from multiple realizations of the RV, mainly when in most realizations some of its elements are missing. The ability to estimate (or to learn) the PMF can be paramount in a variety of statistical inference tasks, ranging from collaborative filtering for recommender systems, or automated recruiting in hiring processes, to higher education admission systems or computer-aided diagnostics.The total number of elements in the PMF tensor grows exponentially with the dimension of the RV and can become huge relative to the number of available observations. Consequently, reliable estimation of a general PMF is practically hopeless. However, structural constraints on the estimated PMF tensor, such as a low-rank assumption (whenever justified), can reduce the number of free parameters dramatically. However, the estimation of these parameters calls for the design of properly constrained loss-functions, giving rise to non-linear and nonconvex constrained optimization problems.In recent related work, it was shown that full recovery of a complete low-rank PMF tensor using joint factorization of its sub-tensors of a fixed order is possible under mild conditions. When the sub-tensors can be consistently estimated from the available partial observations, their (approximate) joint factorization can, therefore, yield a consistent estimate of the full tensor. However, in our own recent work, we have shown that the choice of a criterion function for the approximate joint factorization affects the accuracy and the computational complexity of the estimates. We have proposed a different estimation and factorization scheme which yields the Maximum Likelihood (ML) estimate of the tensor (subject to the low-rank constraint) and therefore enjoys the asymptotic optimality of ML estimation.Based on this observation and on our accumulated experience in tensor factorization in general and in conjunction with PMF estimation in particular, we will develop and analyze novel methods for this challenging estimation (or learning) problem. We seek estimation schemes realizing trade-offs between computational complexity, estimation accuracy, robustness, and reliability. To this end, we will also explore different theoretically and practically justified succinct statistical models which help to further reduce the number of estimated parameters. Moreover, we will propose and test approaches for a data-driven determination of the model order parameters, analyze the resulting estimation accuracy, derive practical performance bounds, and evaluate these new algorithms for some selected application examples with real data.

• DFG Programme: Research Grants
• International Connection: Israel
• International Co-Applicant: Professor Dr. Arie Yeredor