Unsupervised learning is a central challenge in artificial intelligence, lying at the intersection of statistics and machine learning. The goal is to uncover patterns in unlabelled data by designing learning algorithms that are both computationally efficient—that is, run in polynomial time—and statistically effective, meaning they minimize a relevant error criterion.
Over the past decade, significant progress has been made in understanding statistical–computational trade-offs: for certain canonical « vanilla » problems, it is now widely believed that no algorithm can achieve both statistical optimality and computational efficiency. However, somewhat surprisingly, many extensions of these widely accepted conjectures to slightly modified models have recently been proven false. These variations introduce additional structure that can be exploited to bypass the presumed limitations.
In these talks, I will begin by presenting a vanilla problem for which a statistical computational trade-off is strongly conjectured. I will then discuss a specific class of more complex unsupervised learning problems—namely, ranking problems—in which extensions of the standard conjectures have been refuted, and I will aim to explain the underlying reasons why.

High-dimensional high-order/tensor data refers to data organized in the form of large-scale arrays spanning three or more dimensions, which becomes increasingly prevalent across various fields, including biology, medicine, psychology, education, and machine learning.

In biomedical research, for example, longitudinal microbiome studies collect samples across individuals and time points to quantify microbial abundance across hundreds or thousands of taxa. In neuroscience, imaging techniques such as MRI, fMRI, and EEG generate inherently multi-dimensional data capturing spatial and temporal neural activity, naturally forming tensor structures.

These high-dimensional, high-order datasets present unique statistical and computational challenges. Classical matrix-based methods often fail to extend naturally to tensors, and naive approaches like vectorization or matricization can discard important structural information, resulting in suboptimal analyses. Moreover, fundamental operations—such as computing singular values, eigenvalues, or norms—become NP-hard in the tensor setting, highlighting the need for new algorithmic and theoretical frameworks.

From a methodological perspective, essential tasks like dimension reduction, regression, classification, and clustering require significant adaptation. These challenges give rise to fundamental statistical-computational trade-offs not present in lower-order settings.

This tutorial will provide a comprehensive overview of recent advances in tensor-based statistical methods, theoretical foundations, and applications.