Tensor completion methods with provable consistency and fairness guarantees for recommender systems
Authors:   , Nguyen Tung 
Published: October 2023

[EMBARGOED UNTIL 8/1/2024] This thesis introduces novel consistency-based approaches for solving nonnegative/ positive matrix and tensor completion problems in the context of recommender systems. The proposed framework focuses on preserving unit-scale consistency as a single property, ensuring both the existence and uniqueness of solutions. Key theoretical contributions include a general unit-consistent tensor-completion framework with proofs of its properties, e.g., consensus-order and fairness, and algorithms with optimal runtime and space complexities, e.g., O(1) term-completion with preprocessing complexity that is linear in the number of known terms of the matrix/tensor. From a practical perspective, the seamless ability of the framework to generalize to exploit high-dimensional structural relationships among key state variables, e.g., user and product attributes, offers a means for extracting significantly more information than is possible for alternative methods that cannot generalize beyond direct user-product relationships. Finally, we propose our consensus ordering property as an admissibility criterion for any proposed RS method. In the context of recommender system (RS) applications, we prove that two reasonable properties that should be expected to hold for any solution to the RS problem are sufficient to permit uniqueness guarantees to be established within our framework. The theoretical contributions include a general unit-consistent tensor-completion framework with proofs of its properties, such as consensus-order and fairness. Efficient algorithms are developed with optimal runtime and space complexities, including O(1) term-completion with preprocessing complexity linear to the number of known terms. From a practical perspective, the framework leverages highdimensional structural relationships among user and product attributes, enabling the extraction of valuable information beyond direct user-product relationships. Additionally, a new constraint called shift-consistency is proposed for matrix/ tensor completion in recommender systems. The method guarantees key mathematical properties, satisfying a recently established admissibility criterion, fairness definition, and offering robustness through provable uniqueness of missing-value imputation. A rigorous mathematical description is provided, encompassing the generalization from matrix to tensor form to represent and exploit complex structural relationships among user and product attributes. The analysis suggests a structured means for defining latent-space projections, enabling provable performance properties for machine learning methods. The thesis further explores pre- and post-processing methods to induce desired consistency and invariance properties in blackbox systems, specifically AI-based approaches. We demonstrate our approach in the context of blackbox SVD-based matrix-completion methods commonly used in RS applications. Empirical results demonstrate the effectiveness of enforcing unit-consistency and shift-consistency, leading to improved performance according to generic RMSE and MAE metrics, irrespective of initial hyperparameter choices.