Grâce à l'utilisation de l'astuce du noyau dans les espaces d'entrée et de sorties, les méthodes subrogées à noyaux offrent une solution polyvalente avec des fondements théoriques au problème de prédiction structurée. Bien que sur des ensembles de données de tailles modérées elles constituent l'état de l'art, comme dans la chimie-informatique par exemple, elles échouent à passer à l'échelle lorsque le nombre de données d'entraînement devient élevé. Nous proposons d'équiper ces méthodes subrogées â noyaux avec des approximations â l'aide de projections aléatoires, appliquées aux noyaux d'entrée et de sortie. Nous prouvons une borne d'excès de risque sur l'estimateur du problème structuré, atteignant une vitesse de convergence proche de l'estimateur optimal avec des projecteurs de petite dimension en fonction des vitesses de décroissance des valeurs propres des opérateurs de covariance entrée/sortie. D'un point de vue computationnel, nous montrons que les deux approximations ont des impacts distincts mais complémentaires : en entrée on accélère principalement l'apprentissage, tandis qu'en sortie c'est l'inférence qui est accélérée.