📊 statistics

How AI settled the complexity of the oldest SGD algorithm

이 논문은 1937년 스테판 카차르츠(Stefan Kaczmarz)가 제안한 기초적인 확률적 경사 하강법인 카차르즈 알고리즘의 최악의 복잡도를 마침내 결정하기 위해 현대적 AI 모델이 어떻게 활용되었는지를 기술한다.

원저자: Michał Dereziński, Xiaoyu Dong

게시일 2026-06-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Michał Dereziński, Xiaoyu Dong

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이야기: AI가 어떻게 90년 된 수학 퍼즐을 풀었나

1937년부터 선반 위에 놓여 먼지만 쌓여가고 있는 수학 문제가 있다고 상상해 보세요. 이 문제는 거대한 연립 방정식(복잡한 질문에 대한 완벽한 답을 찾는 방법)을 푸는 방법에 관한 퍼즐입니다. 이 특정 방법인 **카차르츠 알고리즘(Kaczmarz algorithm)**은 사실 ChatGPT나 Gemini 같은 현대 AI를 움직이는 기술의 "증조할아버지" 격입니다.

수십 년 동안 수학자들은 이 알고리즘이 작동한다는 것은 알고 있었지만, 최악의 시나리오에서 정확히 얼마나 빨리 작동하는지는 증명하지 못했습니다. 이는 마치 자동차가 뉴욕에서 로스앤젤레스까지 달릴 수 있다는 것은 알지만, 모든 신호등과 교통 체증을 만났을 때 정확히 최대 몇 시간이 걸릴지는 계산할 수 없는 것과 같았습니다.

이 논문은 두 가지 서로 다른 AI 모델인 Gemini와 ChatGPT가 힘을 합쳐 마침내 이 미스터리를 해결하고, 알고리즘이 얼마나 빠르게 수렴하는지를 정확히 증명해 낸 이야기를 담고 있습니다.

등장인물과 임무

알고리즘 (카차르츠 방법): 당신이 지도에서 숨겨진 보물을 찾으려고 한다고 상상해 보세요. 정확한 위치는 모르지만, 단서(방정식) 목록을 가지고 있습니다. 카차르츠 알고리즘은 매 단계마다 하나의 무작위 단서를 골라 그 단서가 가리키는 지점을 향해 걷고, 그다음 또 다른 무작위 단서를 고르는 등산객과 같습니다. 시간이 흐를수록 등산객은 보물에 점점 더 가까워집니다.
미스터리: 등산객은 결국 보물을 찾겠지만, 수학자들은 그 속도를 두고 논쟁했습니다. 등산객이 오랫동안 제자리를 맴돌며 방황할 수도 있을까요? 아니면 보장된 속도 제한이 있을까요?
인간 연구자들: 두 명의 과학자(Michał과 Xiaoyu)는 전통적인 방식의 수학으로 이 문제를 풀려고 노력했습니다. 그들은 정답에 근접했지만 벽에 부딪혔습니다. 그들은 새로운 관점이 필요하다는 것을 깨달았습니다.
AI 팀: 연구자들은 AI로 눈을 돌렸습니다. 그들은 단순히 AI에게 "문제를 풀어줘"라고 요청한 것이 아닙니다. 대신, 그들은 지휘자처럼 행동하며 AI 모델들이 서로 대화할 수 있도록 유도했습니다.

"아하!" 모먼트: 아이디어의 릴레이 경주

해결책은 한 명의 AI가 혼자서 만들어낸 것이 아니었습니다. 그것은 두 명의 서로 다른 주자가 바통을 주고받는 릴레이 경주처럼 일어났습니다.

Gemini의 통찰 (함수 해석학자): 문제를 해결하라는 요청을 받았을 때, Gemini는 완전한 증명을 내놓지 않았습니다. 대신, 기발하고도 묘한 연결 고리를 만들어냈습니다. Gemini는 이 수학 문제를 보고 이렇게 말했습니다. "이것은 단순한 방정식에 관한 것이 아닙니다. 함수 해석학(구체적으로는 '양자 마르코프 반군'이라 불리는 개념)이라는 분야의 개념과 닮았습니다."
- 비유: 고장 난 엔진을 고치려는 정비사를 상상해 보세요. Gemini는 부품을 들여다보는 대신, "이 엔진은 사실 원자력 발전소와 동일한 물리 법칙으로 작동하고 있습니다"라고 말한 것입니다. 이는 인간 연구자들이 미처 보지 못했던 기이하고 높은 수준의 연결이었습니다.
- 함정: Gemini는 연결 고리는 정확히 짚어냈지만, 그것을 증명하지는 못했습니다. Gemini는 어떤 수학 논문들을 인용했지만, 정작 그 논문들에는 필요한 증명이 들어있지 않았습니다. 이는 마치 도서관의 책을 가리키며 "답은 저 책 안에 있어요"라고 말했지만, 정작 그 책은 빈 책이었던 것과 같습니다.
ChatGPT의 증명 (기초 해결사): 인간 연구자들은 Gemini의 이 "기이한 연결 고리"를 가져다가 ChatGPT에게 전달했습니다. 그들은 물었습니다. "좋아, 만약 이 연결이 사실이라면, 기초적인 수학을 사용해서 이것을 증명할 수 있겠니?"
- ChatGPT는 문제를 살펴보더니 "할 수 있다"라고 답했습니다. ChatGPT는 Gemini가 언급했던 복잡하고 혼란스러운 전문 용어를 사용하지 않았습니다. 대신, 속도 제한을 증명하기 위해 복소수(보통 고급 물리학이나 공학에서 쓰이는 수학의 한 종류)를 이용한 영리하고 기초적인 기술을 사용했습니다.
- 비유: 만약 Gemini가 멀리 떨어진 산을 가리키며 "보물은 저 봉우리 아래에 있습니다"라고 말한 사람이라면, ChatGPT는 실제로 그 산을 오르고 구멍을 파서 금을 찾아낸 사람입니다.

결과: "마지막 단계"는 빠르다

이 논문은 구체적인 사실을 증명합니다: 카차르츠 알고리즘은 우리가 기대했던 만큼 빠릅니다.

이러한 알고리즘의 세계에는 답을 확인하는 두 가지 방법이 있습니다:

평균: 등산객이 거친 모든 단계를 모아 평균을 내면 좋은 답이 나옵니다. (우리는 이미 이것이 빠르다는 것을 알고 있었습니다).
마지막 단계: 마지막에 등산객이 멈춘 지점만을 봅니다. (이것이 바로 미스터리였습니다).

논문은 마지막 단계 역시 평균만큼 빠르다는 것을 증명합니다. 등산객은 마지막에 "안착하기" 위해 방황할 필요가 없습니다. 최종 위치는 이미 완벽한 해답입니다.

이것이 왜 중요한가 (논문에 따르면)

완전한 순환: 현대 AI를 훈련시키는 가장 오래된 버전의 알고리즘(SGD)이 현대의 AI에 의해 해결되었습니다.
새로운 연구 방식: 이 논문은 단순한 수학 논문이 아닙니다. 인간과 AI가 어떻게 협력할 수 있는지에 대한 사례 연구입니다. 인간은 증명을 직접 쓰지 않았습니다. AI가 썼습니다. 인간은 단지 두 AI 사이의 대화를 조율했을 뿐입니다.
더 큰 문제의 해결: 이 특정 퍼즐을 해결함으로써, 그들은 일반적인 AI 훈련 알고리즘이 얼마나 빨리 작동하는지에 대한 광범위하고 오래된 질문도 함께 해결했습니다.

핵심 요약

이 논문은 인간의 힘만으로는 깨기 너무나 완고했던 90년 된 수학 문제에 관한 이야기입니다. 두 가지 서로 다른 AI 모델이 협력하게 함으로써—하나는 기이하고 높은 수준의 연결 고리를 찾고, 다른 하나는 실제 증명을 구축하게 함으로써—마침내 미스터리가 풀렸습니다. 이 결과는 이 고전적인 알고리즘의 "마지막 단계"가 매우 효율적임을 확인해주며, 인간이 AI를 가이드하고 AI가 힘든 일을 수행하는 파트너십으로서의 미래 과학 연구가 어떤 모습일지 엿보게 해줍니다.

기술적 요약: 가장 오래된 SGD 알고리즘의 복잡성 해결

문제 정의
본 논문은 1937년 스테판 카차르츠(Stefan Kaczarach)가 제안한 카차르츠(Kaczmarz) 알고리즘의 최악의 경우 계산 복잡도(worst-case computational complexity)에 관한 오랜 미해결 문제를 다룬다. 이 알고리즘은 현대 대규모 언어 모델(LLM) 학습의 근간이 되는 패러다임인 확률적 경사 하강법(SGD)의 가장 초기 사례이다. 카차르츠 알고리즘은 현재의 추정치를 무작위로 선택된 방정식 위로 반복적으로 투영함으로써 선형 방정식계 $Ax = b$를 해결한다.

무작위 카차르츠의 평균 반복값(averaged iterate)의 수렴 속도는 행렬 조건수(condition number)와 무관하게 $O(1/\epsilon)$ 임이 알려져 있었으나, 실제 현장에서 표준 출력으로 사용되는 마지막 반복값(last iterate)의 수렴 속도는 여전히 미해결 상태로 남아 있었다. 응용 수학자와 컴퓨터 과학자 모두의 이전 시도들은 부분적인 결과만을 내놓거나 하위 최적의 바운드(예: $\alpha < 1$ 인 $O(1/\epsilon^{1/\alpha})$ )만을 제시했다. 핵심 질문은 무작위 카차르츠 알고리즘의 마지막 반복값이 평균 반복값의 성능 및 노이즈 없는 최소제곱 회귀(noiseless least squares regression)의 이론적 하한선과 일치하는 최적의 $O(1/\epsilon)$ 수렴 속도를 달나할 수 있는지 여부였다.

방법론: AI 주도 연구
본 논문은 인간 연구자가 두 AI 모델인 Gemini Deep Think와 ChatGPT Pro 사이의 협업을 촉진하여 수학적 증명을 도출해내는 새로운 형태의 "AI 주도 연구(AI-led research)" 사례 연구를 제시한다. 방법론은 다음과 같은 궤적을 따랐다:

초기 인간-AI 상호작용: 저자들은 먼저 인간의 추론을 사용하여 문제를 이산 부등식(discrete inequality)으로 축소한 뒤, 이를 ChatGPT에게 해결하도록 과제를 부여했다. 이는 하위 최적의 바운드( $\alpha = 3/4$ )를 산출했다.
자율적 시도: 저자들은 두 모델에게 이 문제를 자율적으로 해결하도록 유도했다. ChatGPT는 이 문제가 미해결 문제임을 정확히 식별했으나, Gemini는 긍정적인 해법을 주장하면서도 존재하지 않는 정리와 잘못된 참조 문헌을 인용하며 엄밀한 증명을 제공하는 데 실패했다.
합성 및 검증: Gemini의 증명에는 결함이 있었음에도 불구하고, Gemini는 함수 해석학, 특히 대칭 양자 마르코프 반군(symmetric quantum Markov semigroups) 및 리트 연산자(Ritt operators) 이론과의 결정적인 연결 고리를 식별해냈다. 저자들은 Gemini의 통찰력을 합성하여 연산자 바운드에 관한 공식적인 가설을 수립했다.
최종 도출: 이 가설은 ChatGPT에 제시되었으며, ChatGPT는 복소 해석학(특히 해석 함수의 도함수에 대한 코시 추정치)과 연산자 이론을 사용하는 기법을 통해 문제를 성공적으로 해결하는 초등적인 증명을 도출하여 미해결 문제를 해결했다.

주요 기여 및 결과
본 논문의 주요 기여는 무작위 카차르츠 알고리즘의 마지막 반복값이 최적의 수렴 속도를 달성한다는 것을 증명한 것이다.

주요 정리 (Theorem 3.1): 저자들은 선형 연산자 $\Phi(X) = \mathbb{E}[BXB]$ (여기서 $B$ 는 무작위 양의 축약 연산자)에 대한 일반적인 바운드를 확립한다. 이들은 $T$ 와 $T+1$ 번의 합성 사이의 연산자 노름 차이가 다음을 만족함을 증명한다:
$\|\Phi^T - \Phi^{T+1}\|_{op \to op} \leq \frac{3}{T+1}$
카차르츠에 대한 적용 (Corollary 3.2): 카차르츠 업데이트를 이 연산자 프레임워크에 매핑함으로써, 본 논문은 행렬 $A$ 와 벡터 $b$ 에 대하여 마지막 반복값 $x^{(T)}$ 의 기대 제곱 오차가 다음을 만족함을 증명한다:
$\mathbb{E} \|A(x^{(T)} - x^*)\|^2 \leq \frac{C}{T} \|A\|_F^2 \|x^*\|^2$
이는 마지막 반복값에 대한 $O(1/\epsilon)$ 수렴 속도를 확인시켜 주며, 기존 문헌 [39, 6]에서 제기된 의문을 해결한다.
광범위한 함의 (Corollary 3.3): 이 결과는 노이즈 없는 최소제곱 회귀를 위한 SGD의 마지막 반복 분석으로 확장되며, LLM 학습 맥락에서의 SGD 수렴 역학에 관한 오랜 미해결 문제 [8, 41]를 해결한다.

의의 및 주장
본 논문은 두 가지 측면에서 의의를 가진다:

수학적 해결: 본 논문은 수십 년간 해결되지 않았던 확률적 최적화의 근본적인 미해결 문제를 해결함으로써, 이론적 분석(종종 평균에 의존함)과 실제 응용(마지막 반복값을 사용함) 사이의 간극을 메웠다. 이 증명은 함수 해석학과 복소 해석학을 활용하는 독특한 접근 방식을 사용하며, 이는 기존의 SGD 수렴 증명들과 차별화된다.
방법론적 사례 연구: 본 논문은 특정한 형태의 인간-AI 협업에 대한 기록 역할을 한다. 저자들은 수학적 증명은 AI에 의해 생성되었지만, 연구 과정에는 모델 간의 통찰력을 전달하고 출력의 타당성을 검증하기 위한 인간의 촉진이 필요했음을 강조한다. 저자들은 이것이 AI가 분석의 주요 동력 역할을 하되 인간의 감독 하에 있는, 즉 AI 주도 연구의 "중간 단계"를 나타내며, 수학적 발견에 있어 자율적 AI의 현재 능력과 한계를 동시에 보여준다고 주장한다.

저자들은 결과 자체의 참신함에 대해서는 겸손한 태도를 유지하며, 논증의 초등적인 성격을 고려할 때 인간 연구자들도 충분한 시간과 노력을 들였다면 결국 해결했을 문제라고 언급했다. 그러나 그들은 서로 다른 수학 분야(SGD와 함수 해석학)를 연결하기 위해 AI를 활용한 구체적인 경로가 과학적 발견의 새로운 잠재력을 보여준다고 주장한다.