Ce manuscrit s'intéresse à différents problèmes d'apprentissage automatique. En premier lieu, nous nous concentrons sur des problèmes de régression à modèles multiples~: la régression de fonctions lisses par morceaux et la régression à commutations. Deux types de contributions sont exposées. Les premières relèvent des domaines de l'optimisation et de la complexité algorithmique. Ici, on tente de savoir dans quelle mesure il est possible de minimiser exactement l'erreur empirique de modèles de régression dans les différents cadres évoqués plus haut. Dans une seconde partie, nous tentons de caractériser les performances en généralisation de ces modèles. Cette partie relève de la théorie statistique de l'apprentissage dont les outils sont introduits dans un chapitre traitant de la discrimination multi-classe. Celle-ci apparaît en effet de manière naturelle lorsque l'on définit les fonctions de régression lisses par morceaux au travers d'un ensemble de modèles lisses et d'un classifieur chargé de sélectionner un de ces modèles en fonction de l'entrée. Nous montrons dans ce manuscrit qu'il existe aussi un autre lien en termes du rôle joué dans les bornes sur l'erreur de généralisation par le nombre de catégories en discrimination et par le nombre de modèles en régression. Techniquement, la première partie contient des preuves de NP-difficulté, des algorithmes exacts polynomiaux par rapport au nombre de données à dimension fixée et une méthode d'optimisation globale à temps raisonnable en dimension modérée. La seconde partie repose sur l'estimation de complexités de Rademacher, au travers de lemmes de décomposition, de chaînage "à la Dudley" et de nombres de couverture. Les bornes obtenues dans cette dernière partie sont discutées avec une attention particulière à leur dépendance au nombre de catégories ou de modèles.