Cet article résume et étend notre travail récent publié à AISTATS 2019, dans lequel nous avons revisité la méthode des Random Fourier Features (RFF) de Rahimi et al. (2007) par le biais de la théorie PAC-Bayésienne. Bien que l'objectif principal des RFF soit d'approximer une fonction noyau, nous considérons ici la transformée de Fourier comme une distribution \emph{a priori} sur un ensemble d'hypothèses trigonométriques. Cela suggère naturellement d'apprendre une distribution a posteriori sur cet ensemble d'hypothèses. Nous dérivons des bornes en généralisations qui sont optimisées en apprenant une distribution pseudo-posterior obtenue à partir d'une expression en forme close. À partir de cette études, nous proposons deux stratégies d'apprentissage basées sur des points d'intérêts : (i) la procédure en deux étapes proposée dans notre article précédent, où une représentation compacte des données est apprise, puis est utilisée pour apprendre un modèle linéaire, (ii) une nouvelle procédure, où l'on apprend en un seul temps la représentation et le modèle suivant une approche de type Boosting.