볼록 함수 위에서의 기울기 흐름의 경로는 얼마나 길어질 수 있을까? - 단위 유클리드 공 내에 머문다는 제약 하에, n차원에서
^ 이것이 제가 지난 2년 동안 AI의 발전을 테스트하기 위해 사용해 온 질문입니다. 말로는 무척 간단하게 표현되지만, 풀기에는 악마처럼 어려운 문제입니다. GPT-5.6은 168분의 사고 시간 동안 이 질문에 대해 발표된 SOTA를 매우 유의미하게 뛰어넘는 결과를 보여주었으며, 이는 지금까지 다른 어떤 모델도 해내지 못한 방식이었습니다. 하지만 제가 너무 앞서 나가고 있군요. 먼저 이 질문에 대해 조금 생각해보고, 관련 문헌을 검토한 다음, o3에서 GPT-5.6으로의 발전이 어땠는지 논의해 보겠습니다.
1. SOTA
순진하게는 이렇게 말할 수도 있습니다: "음, 경사 하강법은 차원에 무관한 수렴 속도를 가지고 있는데 -- 이것이 바로 많은 파라미터 문제에 사용할 때 흥미로운 이유이기도 하지!-- 그러니 아마 그러한 흐름의 길이도 차원에 무관하지 않을까?" 음, 때로는 순진한 생각이 완전히 틀릴 수도 있습니다. 우선, 그러한 곡선들이 과연 정정 가능한가(rectifiable), 즉 유한한 길이를 가지는가(차원 의존성은 논외로 하고)??? 이것조차 증명하기 쉽지 않으며, 실제로 네스테로프 가속 경사 하강법(Nesterov's accelerated gradient descent)에 대해서는 거짓입니다 (이 논문 by @ErnestRyu, 모두 GPT-5.5로 수행됨).
좋습니다. 그렇다면 이 질문에 대해 정확히 알려진 것은 무엇일까요? 1991년 Manselli와 Pucci의 아름다운 논문이 있습니다. 이 논문은 그러한 곡선들이 실제로 정정 가능하며, 더 나아가 그 길이가 최대 n^O(n)임을 보여줍니다. 네, 맞게 읽으셨습니다. 차원에 대해 지수 함수보다도 더 나쁩니다. 그것이 35년 전의 최고의 한계입니다!! 덧붙이자면, 이 논문은 또한 그러한 곡선들이 소위 "자기 수축적(self-contracted)"이라고 불리는 것임을 지적합니다. 즉, 이 곡선들은 항상 미래의 자신에게 더 가까워집니다(곡선 위의 임의의 점을 시간 t에서 잡으면, s<t에 대해 dist(x(s), x(t))는 비증가합니다; 아래 그림 참조).
이제 하한, 즉 실제로 긴 자기 수축적 곡선을 구성하는 것에 대해 알아보겠습니다. 볼록 최적화 문헌에서 살펴볼 표준적인 것은 조건이 나쁜(ill-conditioned) 이차 함수입니다. 예를 들어 x_1^2 + 큰_상수\x_2^2 + 더_큰_상수\x_3^2 + ... 같은 것입니다. 요점은 경사 하강법이 먼저 가장 큰 상수를 가진 방향을 따라 거의 직선으로 이동한 다음, 두 번째로 큰 상수 방향으로 이동하는 식이라는 것입니다(아래 그림 참조). 따라서 경로의 총 길이는 대략 n이 되고, 경로는 반지름이 sqrt(n)인 공 안에 포함된 하이퍼큐브 안에 있으므로, 재조정을 통해 sqrt(n) 길이의 자기 수축적 곡선을 얻을 수 있습니다.
바로 그겁니다. 그것이 발표된 SOTA입니다: 상한 n^O(n)과 하한 sqrt(n). 이렇게 간단하고 자연스러운 질문에 대한 갭이 이 정도라니!!!
자기 수축적 곡선의 정의
sqrt(n) 길이의 자기 수축적 곡선
2. 인간에 의한 미발표 연구
저는 8년 전에 놀라운 공동 연구자들인 Omer Angel, Tomas Merchan Rodriguez, Fedja Nazarov와 함께 이 질문에 대해 생각했습니다. 우리는 상당한 진전을 이루었고 답이 실제로 차원에 대해 지수 함수임을 확립했습니다!! 구체적으로 우리는 sqrt(2)^n의 하한과 4^n의 상한을 가지고 있었습니다. 이러한 추정치를 담은 논문은 깔끔하게 작성되어 거의 10년 동안 제 드롭박스 폴더에 있었습니다. 부분적으로는 우리가 이러한 한계가 더 개선될 수 있다는 것을 알고 있었기 때문입니다. 그리고 실제로 Tomas와 Fedja는 더 많은 진전을 이루었습니다. 먼저 하한을 2^n으로 끌어올렸고 상한도 2.29...^n으로 개선했습니다. 제 개인적인 문제 이해도는 sqrt(2)^n보다 약간 나은 하한과 4^n 상한에 머물러 있었습니다(사실 저는 AI가 이 문제에 대해 진전을 보이기 시작할 때까지 2^n과 2.29^n을 잊고 있었습니다... 아래에서 더 자세히 설명합니다).
3. AI의 발전
o3는 이 질문을 이해한 최초의 AI 모델이었습니다. 네, 그 문장을 맞게 읽으셨습니다. 아마도 잊으셨을 수도 있지만, 2년 전만 해도 AI가 이렇게 교활하게 단순한 질문을 이해할 수 있을지조차 명확하지 않았고, 해결하는 것은 말할 것도 없었습니다. 특히 o3는 이 질문이 사실 자기 수축적 곡선에 관한 것임을 알아차렸고, 이 질문에 대한 SOTA가 무엇인지 알고 있었습니다. 저는 그 당시 깊은 인상을 받았습니다.
하지만 상황은 까다로워졌고, GPT-5 시리즈 모델이 등장하면서 저는 이 질문을 경고의 예시로 사용했습니다: 올해 2월까지만 해도 저는 수학에서 LLM의 발전에 관한 강연에서 이 질문을 LLM에게 해서는 안 되는 질문의 예로 제시했습니다. 그 이유는 GPT-5나 심지어 GPT-5.2/5.4가 복잡한 답변을 시도했지만, 항상 어딘가에서 틀렸고, 이를 확인하는 데 많은 시간을 낭비하게 되었기 때문입니다. 따라서 수학에서 LLM과 시간을 낭비하지 않으려면 적절한 수준의 질문을 알아야 한다는 좋은 예였습니다.
이것은 GPT-5.5와 함께 바뀌었고, 갑자기 많은 대화와 전문가 프롬프팅을 통해 Mark Sellke는 2^n 하한 구성을 재발견할 수 있었습니다(저는 이에 충격을 받았습니다. 부분적으로는 Tomer와 Fedja가 이미 그것을 알고 있었다는 것을 잊었기 때문입니다 😅). 반면 상한에 대해서는 전혀 운이 없었습니다.
그리고 이제 GPT-5.6이 등장하면서 AI의 발전이 완전히 드러납니다:
- GPT-5.6-pro는 2^n 하한을 원샷(one shot)으로 해결합니다. 여기서 원샷을 확인할 수 있습니다(80분의 사고 시간): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro는 4^n 상한을 원샷으로 해결하며, 실제로 사고 사슬(CoT)에서 매우 빠르게 이를 수행하고, 사고가 끝날 무렵에는 2.31...^n 상한을 생성합니다. Fedja의 2.29...^n과 완전히 일치하지는 않지만(실제로 2.31...^n 전략은 새로운 아이디어 없이는 더 이상 개선될 수 없습니다 -- 사실 Fedja 자신도 2018년 MathOverflow 게시물에서 이렇게 언급했습니다: "[2.31..의 경우] 논증이 상당히 지저분해지며 이 방법으로는 최적 추정치에 도달할 수 없음이 분명하다"). 하지만 여전히 꽤 인상적이고 제가 이 문제에 대해 진지하게 연구했을 때 개인적으로 이해했던 것 이상입니다. 여기서 88분의 사고 시간으로 수행된 원샷을 확인할 수 있습니다: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. 미래를 위한 도전
이 이야기는 현재까지 여전히 인간이 승자입니다. 인간의 2.29 대 기계의 2.31. 자연스럽게, 추측은 자기 수축적 곡선이 2^n보다 길 수 없다는 것입니다(그러면 2^n 하한이 주어졌을 때 최적의 답이 될 것입니다). 이것은 증명하기 매우 어려워 보이며 GPT-5.6의 능력을 넘어섭니다. 이 질문을 AI의 발전을 추적하는 데 얼마나 오래 사용할 수 있을까요? 6개월 미만이 될 것 같습니다...
추신: 위의 게시물을 ChatGPT Work에 복사하여 붙여넣고 이에 대한 삽화를 요청했습니다. 여기에 있는 그림 모음은 해당 쿼리에서 원샷으로 얻은 것입니다.
