7cea8670b4806ef53feb81e04e9f2e2dfb49e4f3afd76d60d125d5424e

39b5d535ecdc3fb362bec4bc02c8696fb256f44e759206ade02f03dc462a1eb687ad9f842475ef63b42d62e2c0e78b83a8da0582058ddb06





Kimon Fountoulakis님(@kfountou)

GPT-5.2 solves our COLT 2022 open problem: “Running Time Complexity of Accelerated L1-Regularized PageRank” using a standard accelerated gradient algorithm and a complementarity margin assumption. Link to the open problem:

x.com



GPT-5.2가 COLT 2022 오픈 문제인 “가속화된 L1-정규화 PageRank의 실행 시간 복잡도(Running Time Complexity of Accelerated L1-Regularized PageRank)”를, 표준 가속 경사(Accelerated Gradient) 알고리즘과 상보성 마진(complementarity margin) 가정 하에서 해결했습니다.






모든 증명은 GPT-5.2 Pro가 생성했습니다.


(COLT’22 오픈-문제 세팅에서) 알고리즘의 총 작업량(total work)에 대한 핵심 경계는 GPT-5.2 Pro, @HarmonicMath님의 Aristotle, 그리고 Antigravity에서의 Gemini 3 Pro (High)를 조합해 자동 형식화(auto-formalized)되었습니다.










제가 사용한 GPT-5.2 프롬프트 링크: https://chatgpt.com/share/693e3ce6-229c-8008-97dc-ab720cb1f95a




주요 결과의 형식화(formalization)에 더해, 저도 증명을 두 번 직접 검토했습니다. 빠뜨린 게 없기를 바라지만, 혹시 제가 놓친 부분이 있다면 알려주시면 고쳐보겠습니다.




논문 뒤 이야기 및 관련 연구


2016년에 저는 l1-정규화 PageRank에 대한 Iterative Soft-Thresholding Algorithm(ISTA)의 수렴률(convergence rate)을 연구했습니다.






놀랍게도, 이 알고리즘의 실행 시간은 최적해에서 0이 아닌 노드(non-zero nodes)의 수에만 의존합니다. 그러니 FISTA 같은 가속 방법(accelerated methods)에도 같은 질문을 던지는 것은 자연스러웠습니다. 하지만 저희는 곧 FISTA가 (결국에는 같은 활성 집합(active set)으로 수렴함에도 불구하고) 최적해에서의 non-zero 개수보다 더 많은 노드를 활성화(activate)한다는 점을 빠르게 깨달았습니다. 그럼에도 실제로는 FISTA가 빠르다는 관측이 있었습니다.






저는 약 3개월 동안 FISTA 및 다른 가속 알고리즘들의 총 작업량(total work)을 경계로 묶어보려 했고, 박사후연구원 시절에도 종종 이 문제로 다시 돌아오곤 했습니다. 결국 포기했습니다. 2021년쯤 다시 시도했지만 또 실패했습니다. 훌륭한 제자였던 Shenghao Yang에게도 부탁했는데, 아쉽게도 그도 실패했습니다. 저명한 연구자 몇 분께 이 문제가 풀릴 수 있다고 보시는지 여쭤봤더니, 금방 “어려워 보인다”는 말씀을 하셨습니다. 그래서 COLT 2022에 오픈 문제로 출판하게 되었습니다.




2023년에 David Martínez-Rubio 등(David Martínez-Rubio et al.)이 최초의 성공적인 해법을 제시했습니다. 그들의 해법은 GPT-5.2가 증명한 것과는 “orthogonal(직교적)”입니다.


그들 논문 링크: https://proceedings.mlr.press/v195/martinez-rubio23b.html btw 그 작업 정말 좋아했습니다. ICML 2024에서 David도 직접 만났는데, 제가 참석한 몇 안 되는 ML 컨퍼런스 중 하나였습니다.




그들이 제안한 가속 알고리즘은 ISTA보다 반드시 더 빠른 것은 아닙니다. 하지만 PageRank의 텔,레포테이션 파라미터(teleportation parameter)와 반복당 총 작업량(total work per iteration) 사이의 새로운 트레이드오프를 제공합니다. 더 중요한 점은, 제안된 방법이 값비싼 서브문제(expensive subproblem)를 풀어야 하므로 실용적이지 않을 수 있다는 것입니다. 공정하게 말하면, COLT 2022 문제에서는 “표준 가속 방법을 사용해야 한다”는 추가적인 강한 제약을 두지 않았습니다. 그 문제는 이론적 문제로 제시되었습니다.


GPT-5.2가 증명한 해법은, 반복마다 경사 계산을 한 번만 수행하는 표준 FISTA 알고리즘에 대해 가속(Acceleration)을 확립합니다. 또한 상보성 마진(complementarity margin)에 대한 깨끗한 파라미터화(parameterization)로 총 작업량을 정리하며, 특정 그래프 구조에서는 ISTA 대비 명확한 속도 향상(speed-up)을 보여줍니다.




2024년에 Zhou 등(https://dl.acm.org/doi/10.5555/3737916.3742410)이 다시 도전했습니다. 하지만 제 관점에서는 그들의 작업에 중요한 단점이 있습니다. 특히, 가속화된 localized 방법(예: localized Chebyshev / Heavy-Ball)에 대한 그들의 보장은, 가속 경계를 얻기 위해 특정 active-ratio factor들의 기하평균(geometric mean)에 대한 조건(Θ(\sqrt{α})로 기술됨)을 가정합니다.




우리 세팅에서는 두 가지 구분이 중요합니다:


첫째, 그들의 가속 런타임 경계는 evolving-set 양(quantity)과 residual-ratio 가정으로 파라미터화되어 있는데, 이는 실행 중에 평가할 수는 있어도 그래프 구조만으로 사전에 해석하거나 검증하기가 보통은 어렵습니다.


반면 GPT-5.2의 해법은 표준적인 최적화-구조 조건(standard optimization-structure condition) 관점에서 명시적인 과도 구간(transient-phase) 경계를 제공하고, 이를 곧바로 총 작업량 경계로 변환합니다.



둘째, 그들은 FISTA 스타일의 가속이 반복당 접근 볼륨(per-iteration accessed volume)을 경계로 묶는 데 필요한 단조성(monotonicity) 성질을 위반한다고 명시적으로 지적하며, 가속 프레임워크에서 중간 단계 희소성(intermediate sparsity)을 보장하는 일이 어렵다는 점을 강조합니다.


GPT-5.2의 마진 기반 분석(margin-based analysis)은 바로 이 간극을 직접 겨냥합니다. 중간 지지집합(intermediate supports)의 단조성이 전혀 없더라도, GPT-5.2는 반복점(iterates)이 유일한 최소해(unique minimizer)의 근방(neighborhood)에 들어가기 전까지 “가짜 활성화(spurious activation)”가 얼마나 일어날 수 있는지를 경계로 묶어, 가속된 proximal-gradient 궤적(trajectory)에 대한 구체적인 지역성 인증서(locality certificate)를 도출했습니다.



2024년 이후로 OpenAI나 Google이 새로운 대형 모델을 낼 때마다 저는 매번 시도해 봤습니다. 이번에는 GPT-5.2로, 된 것 같습니다.

- dc official App