🤖 machine learning

Constrained Learning with Universally Learnable Concept Classes

Cet article établit l'apprentissage universel des solutions aux problèmes d'apprentissage statistique contraints sur des classes d'hypothèses non convexes de dimension infinie en réconciliant la généralisation et la dualité lagrangienne à travers un cadre RKHS universel, tout en introduisant l'écart de clôture-réalisation pour caractériser la faisabilité exacte ou quasi-PACC des algorithmes duaux.

Auteurs originaux : Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

Publié 2026-08-11

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

L'équilibre délicat : Quand l'IA doit suivre les règles

Imaginez que vous enseigniez à un robot comment jouer à un jeu vidéo. Votre objectif est simple : obtenir le score le plus élevé possible. Mais il y a un piège. Le jeu possède des règles strictes : le robot ne peut pas s'écraser contre les murs, il ne peut pas tomber en panne de carburant et il doit respecter un temps imparti spécifique. Dans le monde de l'apprentissage automatique, on appelle cela l'apprentissage sous contraintes. Le « score » est la précision de la prédiction, et les « règles » sont les exigences de sécurité, d'équité ou de confidentialité.

Pendant longtemps, les scientifiques ont pensé que la meilleure façon d'enseigner ces règles à un robot était de rendre le jeu simple et prévisible (mathématiquement « convexe »). Dans un jeu simple, on peut facilement trouver le chemin parfait qui obtient le score le plus élevé tout en respectant chaque règle. Mais l'IA moderne, comme les réseaux de neurones profonds qui alimentent les voitures autonomes ou le diagnostic médical, joue dans un jeu incroyablement complexe et rempli de virages et de rebondissements (mathématiquement « non convexe »). C'est comme naviguer dans un labyrinthe où les murs bougent et où le sol est fait de gelée.

Lorsque vous essayez d'appliquer les anciennes règles simples à ce labyrinthe complexe, tout se casse. L'ordinateur peut trouver un chemin qui semble excellent sur le papier mais qui, en réalité, provoque l'accident de la voiture, ou il peut trouver un chemin qui respecte les règles mais qui obtient un score de zéro point. La grande question que les scientifiques se posent est la suivante : Peut-on enseigner à ces systèmes d'IA super intelligents et complexes à être à la fois brillants dans leur travail et parfaitement obéissants aux règles, sans avoir à simplifier le monde dans lequel ils vivent ?

La grande idée du papier : L'astuce de la « Bibliothèque Infinie »

Ce document, intitulé « Constrained Learning with Universally Learnable Concept Classes », s'attaque précisément à ce problème. Les auteurs, Herlock Rahimi, Spyridon Pougkakiotis et Dionysis Kalogerias, proposent une nouvelle méthode ingénieuse pour entraîner l'IA qui fonctionne même lorsque les règles sont difficiles et que l'IA est incroyablement complexe.

Voici l'histoire de leur découverte, racontée à travers une analogie simple.

Le problème : Le dilemme du « Trop Grand » vs « Trop Petit »

Imaginez que vous essayiez de trouver un trésor caché dans une bibliothèque géante et infinie.

La bibliothèque « Trop Grande » : Si vous cherchez dans l'entière bibliothèque infinie (qui contient tous les livres possibles, y compris ceux qui n'ont aucun sens), vous êtes garanti de trouver la carte au trésor parfaite. Cependant, la bibliothèque est si vaste que vous pourriez passer toute votre vie à chercher et ne jamais trouver le livre dont vous avez besoin. Vous avez le potentiel de trouver la réponse, mais vous ne pouvez pas prouver que vous l'avez trouvée dans un délai raisonnable.
La bibliothèque « Trop Petite » : Si vous cherchez dans une section minuscule et gérable de la bibliothèque (comme juste le rayon « Cuisine »), vous pouvez trouver un livre rapidement. Mais la carte au trésor parfaite ne se trouve peut-être pas dans le rayon « Cuisine ». Vous pourriez trouver une recette de soupe, alors que vous aviez besoin d'une carte pour l'or.

Les tentatives précédentes pour résoudre ce problème forçaient l'IA à choisir une bibliothèque et à s'y tenir. Si elles choisissaient la petite, elles manquaient la meilleure solution. Si elles choisissaient la grande, elles ne pouvaient pas prouver qu'elles avaient trouvé la bonne réponse.

La solution : La stratégie de l'« Étagère Croissante »

Les auteurs ont trouvé une stratégie brillante : Commencer petit, mais continuer à grandir.

Imaginez que vous avez une étagère magique qui commence avec un seul livre. Vous le cherchez. Si vous ne trouvez pas le trésor, vous ajoutez magiquement quelques livres de plus à l'étagère. Vous cherchez à nouveau. Puis vous en ajoutez d'autres. Vous continuez ainsi, en élargissant lentement votre zone de recherche.

Pourquoi cela fonctionne : Parce que vous commencez petit, vous pouvez prouver que votre recherche est efficace et fiable (vous ne perdez pas de temps sur des absurdités).
Pourquoi c'est puissant : Parce que vous continuez de croître, vous finirez par couvrir l'intégralité de la bibliothèque infinie. Vous êtes garanti de trouver la carte au trésor parfaite tôt ou tard, sans jamais vous perdre dans le chaos de la bibliothèque entière d'un seul coup.

Dans le langage du papier, ils utilisent un « Espace de Hilbert à noyau reproducteur universel » (un nom très sophistiqué pour une bibliothèque mathématique très expressive) et cherchent à l'intérieur de « balles de norme » (les étagères) qui deviennent de plus en plus grandes à mesure que l'ordinateur voit de nouvelles données.

L'« Écart » dans les règles

Il existe un tournant délicat. Même avec cette étagère croissante, les auteurs ont découvert que parfois, la solution « parfaite » qui respecte les règles n'existe pas sous la forme d'un livre unique et net. Parfois, les règles sont si complexes que la solution « parfaite » est un mélange de nombreux livres différents, et aucun livre unique dans la bibliothèque ne peut représenter ce mélange parfaitement.

Ils appellent cela l'« Écart de Clôture-Réalisation » (Closure–Realization Gap).

Si l'écart est nul : L'IA trouve un livre unique et parfait qui respecte les règles et obtient le meilleur score. Cela se produit lorsque les règles sont « lisses » et bien comportées (plus précisément, quand la géométrie duale est bénigne, comme lorsque la fonction duale est différentiable). Dans ce cas, la solution est exactement réalisable.
Si l'écart n'est pas nul : L'IA trouve un livre qui est presque parfait. Il peut enfreindre une règle d'un montant infime, fixe et impossible à supprimer, peu importe la quantité de données que vous donnez à l'IA. Les auteurs ont prouvé que cette minuscule erreur n'est pas un échec de l'IA ou des mathématiques ; c'est une propriété fondamentale et immuable du problème lui-même. C'est comme essayer de dessiner un cercle parfait avec un crayon carré ; le crayon n'est pas mauvais, la forme ne s'ajuste simplement pas parfaitement, et l'erreur est exactement de la taille de l'angle du crayon.

Ce qu'ils ont prouvé

Le papier ne se contente pas de suggérer que cela pourrait fonctionner ; ils l'ont prouvé mathématiquement.

Valeur exacte : Ils ont montré que l'IA peut apprendre le meilleur score possible, même dans ce monde complexe et non convexe.
Faisabilité : Ils ont montré que l'IA peut trouver une solution qui respecte les règles. Crucialement, si la géométrie du problème est « bénigne » (l'écart est nul), la solution est parfaitement réalisable. Si la géométrie est « non bénigne » (l'écart n'est pas nul), la solution présentera une marge d'erreur spécifique et non nulle qui est intrinsèque au problème, et non une limitation de l'algorithme.
Pas de raccourcis : Ils ont prouvé que l'on ne peut pas simplement supposer que les règles sont simples (convexes) pour faciliter les mathématiques. La complexité est réelle, et leur méthode est la seule capable de la gérer sans perdre la garantie de trouver la réponse.

Pourquoi cela importe

C'est une avancée majeure car cela nous donne un moyen de construire une IA qui soit à la fois puissante et sûre. Qu'il s'agisse d'une IA décidant de l'octroi d'un prêt (équité), d'un robot conduisant une voiture (sécurité) ou d'une IA médicale diagnostiquant des patients (précision), nous avons besoin qu'elles suivent des règles strictes. Ce papier montre que nous n'avons pas à choisir entre « intelligence » et « sécurité ». Nous pouvons avoir les deux, à condition d'utiliser la bonne stratégie d'« étagère croissante » pour les enseigner.

Les auteurs précisent que, bien que les mathématiques soient solides, transformer cela en un outil logiciel réel qui s'exécute sur votre téléphone est la prochaine étape. Mais le fondement théorique est désormais posé : Oui, nous pouvons enseigner à une IA complexe à suivre les règles parfaitement (si le problème le permet), ou, si les règles sont intrinsèquement complexes, à les suivre aussi parfaitement que les règles le permettent mathématiquement, avec une limite d'erreur connue et fixe.

Résumé Technique : Apprentissage Contraint avec des Classes de Concepts Universellement Apprenables

1. Cadre du Problème

L'article traite de l'apprentissage statistique contraint sur des classes d'hypothèses de dimension infinie dans un cadre entièrement non convexe. L'objectif est de minimiser un risque de prédiction primaire $R_0(\phi)$ sous $m$ contraintes $R_i(\phi) \leq 0$ (pour $i=1,\dots,m$ ), où les risques sont des espérances de fonctionnelles de perte potentiellement non convexes sous des distributions de données distinctes $D_i$ .

La difficulté fondamentale provient d'une tension structurelle entre deux exigences pour une théorie de l'apprentissage viable :

Dualité Forte (Niveau Population) : Pour garantir que le problème dual lagrangien caractérise fidèlement le problème primal contraint (écart de dualité nul), la classe d'hypothèses doit être décomposable (fermée par suture mesurable). Cette propriété, liée à la convexité de Lyapunov pour les mesures vectorielles, assure que l'ensemble des vecteurs de risques réalisables est convexe, même si les fonctionnelles individuelles ne le sont pas. Cependant, les espaces décomposables (ex: espaces $L_p$ ) sont trop vastes pour permettre des garanties de généralisation statistique (complexité de Rademacher décroissante) à partir de données finies.
Généralisabilité Statistique (Niveau Empirique) : Pour assurer l'apprenabilité à partir d'échantillons finis, la classe d'hypothèses doit avoir une complexité statistique contrôlée (ex: complexité de Rademacher décroissante). Les choix standards comme les boules de norme des Espaces de Reproductions à Noyau (RKHS) satisfont cette condition mais ne sont pas décomposables, ce qui conduit à des erreurs d'approximation irréductibles (résultats de type "near-PACC") où les violations de contraintes ne peuvent être ramenées à zéro, quel que soit la taille de l'échantillon.

Les approches existantes font souvent un compromis en utilisant une classe unique de complexité finie, ce qui résulte en des garanties "near-PACC" avec des résidus qui ne s'annulent pas avec l'augmentation des données. Cet article cherche à résoudre cette tension pour atteindre une apprenabilité exacte ou quasi-exacte sans de tels résidus irréductibles.

2. Méthodologie

Les auteurs proposent un cadre à complexité variable utilisant des classes RKHS denses et la Minimisation du Risque Empirique Dual (DERM).

Problème de Population sur un RKHS Universel : Le problème contraint de population est posé sur un RKHS universel $\mathcal{H}_K$ qui est dense dans un espace enveloppe décomposable $\mathcal{G}$ (ex: un espace $L_p$ ). Bien que $\mathcal{H}_K$ ne soit pas décomposable, sa densité dans $\mathcal{G}$ permet le transfert des propriétés de dualité forte de $\mathcal{G}$ vers $\mathcal{H}_K$ via des arguments de continuité.
Problème Empirique avec des Boules de Norme Croissantes : L'apprenant opère sur une séquence de boules de norme fermées $B_{Q_n} = \{f \in \mathcal{H}_K : \|f\|_{\mathcal{H}_K} \leq Q_n\}$ $B_{Q_{n}} = {f \in H_{K} : ∥ f ∥_{H_{K}} \leq Q_{n}}$ , où le rayon $Q_n$ $Q_{n}$ croît avec la taille de l'échantillon $n$ $n$ de telle sorte que $Q_n \to \infty$ $Q_{n} \to \infty$ mais $Q_n/\sqrt{n} \to 0$ $Q_{n} / n \to 0$ .
- Cela garantit que l'espace de recherche épuise éventuellement le RKHS (capturant la solution de la population).
- Simultanément, la complexité statistique (complexité de Rademacher) de la boule $B_{Q_n}$ tend vers zéro comme $O(Q_n/\sqrt{n})$ , assurant la convergence uniforme.
Algorithme DERM : L'apprenant maximise la fonction duale empirique sur des multiplicateurs non négatifs, puis minimise le lagrangien empirique sur la boule actuelle $B_{Q_n}$ .
Analyse de Faisabilité : Puisque la non-convexité empêche le lagrangien d'atteindre son infimum ou de garantir qu'un prédicteur unique réalise le sous-gradient dual, les auteurs introduisent l'écart clôture-réalisation $\varepsilon^\star_\infty$ . Cette constante géométrique mesure la distance entre le superdifférentiel de la fonction duale et l'ensemble des vecteurs de risques réalisables par des prédicteurs au sein du RKHS.

3. Contributions Clés

1. Apprenabilité Universelle (Near-)PACC :
L'article établit l'apprenabilité agnostique Probably Approximately Correct with Constraints (PACC) universelle. Contra à l'apprentissage PAC sans distribution, la complexité d'échantillonnage ici est autorisée à dépendre des distributions sous-jacentes (spécifiquement via la marge de Slater et la complexité de Tikhonov), ce que les auteurs considèrent comme nécessaire en raison de la haute expressivité des RKHS.

Apprenabilité Exacte : Lorsque l'écart clôture-réalisation $\varepsilon^\star_\infty = 0$ (ex: sous dualité différentiable), l'apprenant atteint une faisabilité et une optimalité exactes.
Apprenabilité Near-PACC : Lorsque $\varepsilon^\star_\infty > 0$ , l'apprenant atteint l'optimalité et la faisabilité avec un résidu exactement égal à $\varepsilon^\star_\infty$ . Crucialement, ce résidu est une propriété intrinsèque de la géométrie du problème, et non un artefact d'un choix de modélisation fixe, et il s'annule sous des conditions bénignes.

2. Certificats de Faisabilité sans Atteinte Primal :
Dans le régime pleinement non convexe, le problème primal contraint peut ne pas avoir de solution atteinte. L'article prouve que les sorties de DERM sont asymptotiquement faisables et quasi-optimales à un écart $\varepsilon^\star_\infty$ près, même sans supposer l'existence d'un minimiseur primal. Ceci est réalisé grâce à un argument variationnel du côté dual, utilisant la représentation de Levin–Valadier des superdifférentiels.

3. Taux Statistiques Explicites :
Les auteurs dérivent un seuil de complexité d'échantillonnage polynomial explicite pour apprendre la valeur optimale. Ils introduisent la complexité de Tikhonov $T^\varepsilon_n$ , définie comme la norme RKHS minimale requise pour atteindre un ensemble de niveau $\varepsilon$ -optimal du lagrangien. Sous une condition de source standard sur le chemin de régularisation, ils montrent que $T^\varepsilon_n$ est finie et dérivent une complexité d'échantillonnage de $O(\varepsilon^{-\max\{4, 2(1-\beta)/\beta\}})$ , où $\beta$ caractérise la condition de source.

4. Nécessité du Cadre Universel :
L'article prouve que dans la spécialisation non contrainte de leur cadre, aucun seuil d'échantillonnage indépendant de la distribution n'existe en raison de la capacité non bornée des RKHS universels. Ainsi, le cadre d'apprentissage universel (où les taux dépendent de la distribution) n'est pas seulement pratique, mais canonique pour les algorithmes duaux sur de grandes classes d'hypothèses.

4. Résultats Principaux

Théorème 1 : Établit que DERM sur des RKHS denses avec des boules de norme croissantes est universellement apprenable en mode PACC.
- Partie (i) : Apprenabilité exacte de la valeur optimale avec un seuil explicite.
- Parties (ii)–(v) : Garanties de faisabilité et de quasi-optimalité contrôlées par l'écart clôture-réalisation $\varepsilon^\star_\infty$ .
- Partie (vi) : Apprenabilité PACC exacte lorsque $\varepsilon^\star_\infty = 0$ .
Corollaire 1 : Fournit une borne explicite de complexité d'échantillonnage polynomiale sous une condition de source.
Lemme 1 : Caractérise l'écart clôture-réalisation, montrant qu'il s'annule si la fonction duale est différentiable à l'optimum.

5. Signification et Revendications

L'article prétend résoudre la tension structurelle fondamentale entre la dualité forte au niveau de la population (nécessitant la décomposabilité) et la généralisabilité à échantillon fini (nécessitant une faible complexité). En exploitant la densité des RKHS universels dans des enveloppes décomposables, les auteurs démontrent que l'on peut hériter des propriétés de dualité exactes des grands espaces tout en maintenant un contrôle statistique via des restrictions de boules de norme.

La signification réside dans le dépassement des résultats "near-PACC" avec des résidus irréductibles. L'article soutient que les résidus précédents étaient des artefacts d'approximations paramétriques fixes, alors que leur résidu ( $\varepsilon^\star_\infty$ ) est une constante géométrique du problème lui-même, qui s'annule de manière prouvable sous des géométries bénignes. Cela fournit un fondement théorique pour l'apprentissage contraint dans des contextes non convexes (ex: apprentissage profond avec des contraintes d'équité ou de sécurité) sans dépendre de surrogats convexes qui peuvent échouer à préserver la faisabilité des contraintes sous des distributions hétérogènes.

Limites reconnues par les auteurs :

La condition de récupération (Hypothèse 5) requise pour la faisabilité n'est vérifiée par un critère général que dans le régime exact ( $\varepsilon^\star_\infty=0$ ).
La revendication agnostique pour la faisabilité repose sur cette hypothèse, tandis que l'apprentissage de la valeur est sans atteinte (attainment-free).
La procédure DERM est une spécification d'un algorithme idéalisé ; la mise en œuvre computationnelle et la convergence des schémas primal-dual pratiques sont laissées aux travaux futurs.
Les taux explicites reposent sur une condition de source ; sans celle-ci, le seuil est fini mais non explicite.