Transformers have reshaped modern artificial intelligence, yet their theoretical foundations remain incomplete. This thesis investigates the approximation power and memory limitations of transformers. I combine tools from approximation theory and statistical learning theory to provide provable guarantees on expressivity, memorization capacity, and inherent architectural constraints. My contributions include the first rigorous proof of memory bottlenecks in prompt tuning and new results on the expressivity of transformers. The long-term goal of my doctoral research is to develop a principled theoretical framework that grounds the empirical behavior of large-scale transformer models in formal approximation-theoretic results.

International audience

Quantum state tomography, the task of learning an unknown quantum state, is a fundamental problem in quantum information. In standard settings, the complexity of this problem depends significantly on the type of quantum state that one is trying to learn, with pure states being substantially easier to learn than general mixed states. A natural question is whether this separation holds for any quantum state learning setting. In this work, we consider the online learning framework and prove the surprising result that learning pure states in this setting is as hard as learning mixed states. More specifically, we show that both classes share almost the same sequential fat-shattering dimension, leading to identical regret scaling. We also generalize previous results on full quantum state tomography in the online setting to (i) the $\epsilon$-realizable setting and (ii) learning the density matrix only partially, using smoothed analysis.

Phishing remains a pervasive security threat, necessitating effective and universally comparable detection systems. The use of supervised machine learning models for phishing detection has been generalized in the literature to automate predictions and increase the detection capacities of security systems. These models rely on large amounts of annotated data for their training, evaluation and maintenance. Thus, there is a need to efficiently collect significant amount of annotated data to improve phishing detection. This paper introduces WikiPhish, a novel, renewable, and open-access dataset for phishing website classification. It consists of 110,606 webpages harvested from URLs drawn from Wikipedia's references and the popular phishing databases OpenPhish and PhishTank. The dataset is designed to address the challenges of phishing detection by leveraging Wikipedia's contribution verification and wide-ranging content. WikiPhish offers a more diverse and robust baseline for developing phishing detection models. We highlight the importance of gathering diverse URLs for building phishing website datasets, and demonstrate the practical utility of WikiPhish by employing it in the training and evaluation of phishing detection machine learning models.