Quelle peut être la longueur du chemin d'un flot de gradient sur une fonction convexe, sachant qu'il doit rester dans la boule euclidienne unité en dimension n ?
^ C'est la question que j'utilise depuis 2 ans maintenant pour tester les progrès de l'IA. Elle est d'une simplicité étrange à énoncer, mais diablement difficile à résoudre. En 168 minutes de réflexion, GPT-5.6 a réussi à battre très significativement l'état de l'art publié sur cette question, d'une manière qu'aucun autre modèle n'avait pu faire jusqu'à présent. Mais je vais trop vite, commençons par réfléchir un peu à la question, passons en revue la littérature, puis discutons de l'évolution des progrès d'o3 à gpt-5.6.
1. État de l'art
Naïvement, on pourrait dire : « Eh bien, la descente de gradient a un taux de convergence indépendant de la dimension — c'est pour ça qu'il est excitant de l'utiliser pour des problèmes à nombreux paramètres ! — donc probablement la longueur d'un tel flot devrait aussi être indépendante de la dimension ? ». Eh bien, parfois les intuitions naïves peuvent être complètement fausses. Pour commencer : de telles courbes sont-elles seulement rectifiables (c'est-à-dire de longueur finie, sans parler de la dépendance en dimension) ??? Même cela n'est pas facile à prouver, et en fait c'est FAUX pour la descente de gradient accélérée de Nesterov (voir cet article par @ErnestRyu , le tout fait avec gpt-5.5).
Bon, alors que sait-on exactement de cette question ? Eh bien, il y a un magnifique article de 1991 de Manselli et Pucci qui montre que ces courbes sont effectivement rectifiables, et de plus leur longueur est au plus n^O(n). Oui, vous avez bien lu, encore pire qu'exponentiel en dimension, c'est la meilleure borne d'il y a 35 ans !! D'ailleurs, cet article souligne également que ces courbes sont ce qu'on appelle « auto-contractées », c'est-à-dire qu'elles se rapprochent toujours de leur futur (prenez n'importe quel point sur la courbe au temps t, alors dist(x(s), x(t)) est non croissante pour s<t ; voir l'illustration ci-dessous).
Passons maintenant aux bornes inférieures, c'est-à-dire construire une courbe auto-contractée réellement longue. Un exemple standard dans la littérature d'optimisation convexe serait une quadratique mal conditionnée, quelque chose comme x_1^2 + grande_cst\x_2^2 + encore_plus_grande_cst\x_3^2 + ... L'idée est que la descente de gradient va d'abord aller presque tout droit le long de la direction avec la plus grande constante, puis dans la direction de la deuxième plus grande constante, etc. (voir l'illustration ci-dessous). Donc la longueur totale du chemin sera approximativement n, et le chemin est contenu dans l'hypercube qui est contenu dans une boule de rayon sqrt(n), donc en renormalisant on obtient une courbe auto-contractée de longueur sqrt(n).
C'est tout. C'est l'état de l'art publié : borne supérieure n^O(n) et borne inférieure sqrt(n). Quel écart pour une question aussi simple et naturelle !!!
Définition d'une courbe auto-contractée
Une courbe auto-contractée de longueur sqrt(n)
2. Travail non publié par des humains
J'ai réfléchi à cette question il y a 8 ans avec d'incroyables collaborateurs Omer Angel, Tomas Merchan Rodriguez et Fedja Nazarov. Nous avons pu faire pas mal de progrès et avons établi que la réponse est effectivement exponentielle en dimension !! Plus précisément, nous avions une borne inférieure de sqrt(2)^n et une borne supérieure de 4^n. L'article avec ces estimations est bien écrit et traîne dans mon dossier Dropbox depuis près d'une décennie, en partie parce que nous savions que ces bornes pouvaient être encore améliorées. Et effectivement, Tomas et Fedja ont fait plus de progrès, d'abord en poussant la borne inférieure à 2^n et en améliorant aussi la borne supérieure à 2,29...^n. Notez que ma propre compréhension du problème est restée à une borne inférieure légèrement meilleure que sqrt(2)^n et une borne supérieure de 4^n (en fait, j'avais oublié les 2^n et 2,29^n jusqu'à ce que l'IA commence à faire des progrès là-dessus... plus loin).
3. Progrès de l'IA
o3 a été le premier modèle d'IA à même comprendre la question. Oui, vous avez bien lu cette phrase. Peut-être avez-vous oublié, mais il y a deux ans, il n'était même pas clair qu'une IA puisse COMPRENDRE des questions d'une simplicité aussi trompeuse, sans parler de les résoudre. En particulier, o3 pouvait voir que la question concernait en fait les courbes auto-contractées, et connaissait l'état de l'art sur cette question. J'étais extrêmement impressionné à l'époque.
Mais ensuite les choses se sont compliquées, et avec l'arrivée de la série de modèles GPT-5, j'ai utilisé cette question comme une mise en garde : encore en février de cette année, je donnais cette question dans des conférences sur les progrès des LLM en mathématiques comme exemple de question à NE PAS poser aux LLM. La raison est que GPT-5 ou même GPT-5.2/5.4 essaieraient de donner des réponses compliquées, mais elles étaient invariablement erronées quelque part, et on perdrait beaucoup de temps à les vérifier. C'était donc un bon exemple que pour ne pas perdre de temps avec les LLM en mathématiques, il faut savoir poser le bon niveau de question.
Cela a changé avec GPT-5.5, et soudainement, avec beaucoup d'allers-retours et de sollicitations expertes, Mark Sellke a pu redécouvrir la construction de la borne inférieure 2^n (ce qui m'a CHOQUÉ, en partie parce que j'avais oublié que Tomer et Fedja la connaissaient déjà 😅). En revanche, aucune chance du côté de la borne supérieure.
Et maintenant arrive GPT-5.6, et les progrès de l'IA apparaissent pleinement :
- GPT-5.6-pro RÉSOLT EN UN SEUL COUP la borne inférieure 2^n. Vous pouvez voir le one-shot ici (80 minutes de réflexion) : https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro RÉSOLT EN UN SEUL COUP la borne supérieure 4^n, et le fait très rapidement dans son CoT, et à la fin de sa réflexion, il produit une borne supérieure 2.31...^n. Cela ne correspond pas tout à fait au 2.29...^n de Fedja (et en fait la stratégie 2.31...^n ne peut pas être améliorée sans nouvelles idées — d'ailleurs Fedja l'avait lui-même noté dans un post sur MathOverflow en 2018 : « [pour 2.31..] l'argument devient un peu brouillon et il est clair que cette voie ne mènera pas à l'estimation optimale »). Mais c'est quand même sacrément impressionnant et au-delà de ce que j'avais personnellement compris du problème quand j'y travaillais sérieusement. Vous pouvez voir le one-shot ici, fait en 88 minutes de réflexion : https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. Un défi pour l'avenir
Cette histoire a pour l'instant encore les humains comme vainqueurs. 2.29 pour les humains contre 2.31 pour les machines. Naturellement, la conjecture est que les courbes auto-contractées ne peuvent pas être plus longues que 2^n (ce qui serait alors la réponse optimale étant donné la borne inférieure 2^n). Cela semble très difficile à prouver et au-delà des capacités de GPT-5.6. Combien de temps vais-je pouvoir utiliser cette question pour suivre les progrès de l'IA ? Je soupçonne que cela pourrait être moins de 6 mois...
PS : J'ai copié-collé le post ci-dessus dans ChatGPT work et je lui ai demandé de revenir avec des illustrations. La collection d'images ici a été obtenue en un seul coup à partir de cette requête.
