In this talk, I will present two recent works related to the question of quantum advantages in machine learning. In the first work, we address a major obstacle to the widespread use of quantum machine learning models in practice: quantum models, even once trained, still require access to a quantum computer in order to be evaluated on new data. To solve this issue, we introduce a class of quantum models where quantum resources are only required during training, while the deployment of the trained model is classical. We prove that: (i) this class of models is universal for classically-deployed quantum machine learning; (ii) it does have restricted learning capacities compared to ‘fully quantum’ models, but nonetheless (iii) it achieves a provable learning advantage over fully classical learners, contingent on widely believed assumptions in complexity theory. In the second work, we expand our understanding of where quantum advantages can be found in quantum machine learning, by showing a PAC learning advantage in the realm of shallow-depth circuits. This learning advantage has the particularity that it is unconditional, meaning that we do not need to make assumptions such as the existence of classically hard, quantumly easy, cryptographic functions to show an advantage. The machine learning task we consider is that of learning probability distributions, or generative learning. We design this learning task building on recent results by Bene Watts and Parham on quantum advantages for sampling, which we technically uplift to a hyperplane learning problem, identifying non-local correlations as the origin of the quantum advantage.