위험한 대규모 단계로 최적화 문제를 더 빠르게 해결할 수 있습니다 | 콴타 매거진

최적화 문제는 까다로울 수 있지만 세상이 더 잘 작동하도록 만듭니다. 어떤 일을 하는 최선의 방법을 찾는 이런 종류의 질문은 절대적으로 어디에나 있습니다. 휴대전화의 GPS가 목적지까지의 최단 경로를 계산합니다. 여행 웹사이트는 여행 일정과 일치하는 가장 저렴한 항공편 조합을 검색합니다. 그리고 데이터의 패턴을 분석하여 학습하는 기계 학습 애플리케이션은 주어진 질문에 대해 가장 정확하고 인간적인 답변을 제시하려고 합니다.

간단한 최적화 문제의 경우 최상의 솔루션을 찾는 것은 단지 산술의 문제입니다. 그러나 수학자 및 과학자의 관심을 끄는 실제 질문은 거의 간단하지 않습니다. 1847년 프랑스 수학자 오귀스탱-루이 코시(Augustin-Louis Cauchy)는 현재 경사 하강법으로 알려진 일반적인 최적화 방법을 개척했을 때 적절하게 복잡한 예인 천문학적 계산을 연구하고 있었습니다. 오늘날 대부분의 기계 학습 프로그램은 이 기술에 크게 의존하며 다른 분야에서도 이 기술을 사용하여 데이터를 분석하고 엔지니어링 문제를 해결합니다.

수학자들은 150년 넘게 경사하강법을 완벽하게 해왔지만 지난 달, 연구 기술에 대한 기본 가정이 잘못되었을 수 있음을 증명했습니다. "내 직감이 망가진 것처럼 놀란 적이 몇 번 있었다"고 말했다. 벤 그리머, Johns Hopkins University의 응용 수학자이자 연구의 유일한 저자입니다. 그의 반직관적인 결과는 경사하강법이 주어진 질문에 대한 최선의 답을 찾는 방법에 대해 오랫동안 받아 들여진 규칙을 위반할 경우 거의 XNUMX배 더 빠르게 작동할 수 있음을 보여주었습니다. 이론적 진보는 기계 학습이 다루는 더 어려운 문제에는 적용되지 않을 가능성이 높지만, 연구자들은 이 기술에 대해 알고 있는 것을 재고하게 되었습니다.

경사 하강 이론에 대해 "우리가 완전히 이해하지 못한 것으로 밝혀졌습니다."라고 말했습니다. 슈보모이 다스 굽타, Massachusetts Institute of Technology의 최적화 연구원. 이제 그는 "경사 하강법이 무엇을 하는지 이해하는 데 더 가까워졌다"고 말했습니다.

기술 자체는 믿을 수 없을 정도로 간단합니다. 비용 함수라는 것을 사용하는데, 이는 그래프에서 위아래로 사행하는 부드러운 곡선처럼 보입니다. 해당 라인의 모든 지점에 대해 높이는 특정 설정으로 조정될 때 작업에 얼마나 많은 시간, 에너지 또는 오류가 발생하는지와 같은 비용을 나타냅니다. 포인트가 높을수록 이상적인 시스템에서 멀어집니다. 당연히 이 라인에서 비용이 가장 적은 가장 낮은 지점을 찾고 싶을 것입니다.

경사 하강법 알고리즘은 한 점을 선택하고 그 주변 곡선의 기울기(또는 기울기)를 계산한 다음 기울기가 가장 가파른 방향으로 이동하여 바닥으로 가는 길을 느낍니다. 어둠 속에서 산을 내려가는 느낌을 상상해보세요. 어디로 이동해야 하는지, 얼마나 오래 하이킹을 해야 하는지, 궁극적으로 해수면에 얼마나 가까워야 하는지 정확히 알지 못할 수도 있지만, 가장 급한 내리막을 내려가면 결국 해당 지역에서 가장 낮은 지점에 도착해야 합니다.

은유적인 등산가와 달리 최적화 연구원은 경사 하강법 알고리즘을 프로그래밍하여 모든 크기의 단계를 수행할 수 있습니다. 거대한 도약은 유혹적이지만 답을 넘어설 수 있기 때문에 위험하기도 합니다. 대신, 수십 년 동안 이 분야의 통념은 아기 단계를 밟는 것이었습니다. 경사 하강법 방정식에서 이것은 2보다 크지 않은 단계 크기를 의미하지만 아무도 더 작은 단계 크기가 항상 더 낫다는 것을 증명할 수는 없습니다.

컴퓨터 지원 증명 기술의 발전으로 최적화 이론가들은 더 극단적인 기술을 테스트하기 시작했습니다. 한 연구에서는 먼저 게시 2022 관련 최근에 출판 됨 in 수학 프로그래밍, Das Gupta 및 다른 사람들은 최적화를 최적화하려고 시도했기 때문에 일종의 메타 최적화 문제인 50단계만 실행하도록 제한된 알고리즘에 대한 최상의 단계 길이를 찾는 작업을 컴퓨터에 할당했습니다. 그들은 가장 최적의 50개 단계가 길이가 상당히 다양하다는 것을 발견했으며, 시퀀스의 중간에 있는 한 단계는 길이가 37인 일반적인 캡보다 훨씬 높은 길이 2에 거의 도달했습니다.

연구 결과는 최적화 연구자들이 놓친 것이 있음을 시사했습니다. 흥미롭게도 Grimmer는 Das Gupta의 수치 결과를 보다 일반적인 정리로 바꾸려고 했습니다. 임의의 50단계 제한을 넘기 위해 Grimmer는 반복할 수 있는 시퀀스에 대해 최적의 단계 길이가 무엇인지 탐색하여 반복할 때마다 최적의 답변에 가까워졌습니다. 그는 보폭 시퀀스의 수백만 순열을 통해 컴퓨터를 실행하여 답에 가장 빨리 수렴하는 시퀀스를 찾는 데 도움을 주었습니다.

Grimmer는 가장 빠른 시퀀스에는 항상 한 가지 공통점이 있다는 것을 발견했습니다. 바로 중간 단계가 항상 큰 단계라는 것입니다. 크기는 반복 시퀀스의 단계 수에 따라 다릅니다. 4.9단계 시퀀스의 경우 큰 단계의 길이는 15였습니다. 29.7단계 시퀀스의 경우 알고리즘은 길이가 127인 한 단계를 권장했습니다. 그리고 테스트된 가장 긴 370단계 시퀀스의 경우 큰 중앙 도약은 무려 XNUMX이었습니다. Grimmer는 처음에는 터무니없이 큰 숫자처럼 들리지만 그 거대한 도약을 만회하기에 충분한 총 단계가 있었기 때문에 바닥을 넘어 날아가더라도 여전히 빨리 되돌릴 수 있습니다. 그의 논문은 이 시퀀스가 ​​일정한 아기 단계를 밟는 것보다 거의 XNUMX배 더 빠르게 최적의 지점에 도달할 수 있음을 보여주었습니다. "때때로, 당신은 정말로 과도하게 커밋해야 합니다."라고 그는 말했습니다.

이 순환적 접근 방식은 경사 하강법을 생각하는 다른 방식을 나타냅니다. 아이메릭 디울레베트, 프랑스 Palaiseau에 있는 École Polytechnique의 최적화 연구원. "단계별로 생각하지 않고 연속적으로 여러 단계로 생각해야 하는 이 직관은 많은 사람들이 무시하는 것"이라고 그는 말했습니다. "가르치는 방식이 아닙니다." (Grimmer는 이 재구성이 제안 된 현재 펜실베이니아 대학의 최적화 연구원인 Jason Altschuler의 2018년 석사 논문에서 유사한 종류의 문제에 대해.)

그러나 이러한 통찰력은 연구자들이 경사 하강법에 대해 생각하는 방식을 바꿀 수 있지만 현재 기술이 사용되는 방식을 바꾸지는 않을 것입니다. Grimmer의 논문은 날카로운 꼬임이 없는 부드러운 함수와 그릇 모양이고 바닥에 하나의 최적값만 있는 볼록 함수에만 초점을 맞췄습니다. 이러한 종류의 기능은 이론의 기본이지만 실제로는 관련성이 적습니다. 기계 학습 연구원이 사용하는 최적화 프로그램은 일반적으로 훨씬 더 복잡합니다. 이를 위해서는 "너무 많은 종소리와 휘파람, 그리고 너무 많은 뉘앙스가 있는" 경사 하강법 버전이 필요하다고 Grimmer는 말했습니다.

이러한 향상된 기술 중 일부는 Grimmer의 대규모 접근 방식보다 더 빠르게 진행될 수 있다고 말했습니다. 고티에 지델, 몬트리올 대학의 최적화 및 기계 학습 연구원. 그러나 이러한 기술은 추가 운영 비용이 발생하므로 정기적인 경사 하강법이 올바른 단계 크기 조합으로 승리할 수 있다는 희망이 있었습니다. 불행하게도 새로운 연구의 XNUMX배 속도 향상만으로는 충분하지 않습니다.

Gidel은 "미미한 개선을 보여줍니다."라고 말했습니다. "하지만 진짜 질문은 다음과 같습니다. 이 격차를 정말 좁힐 수 있을까요?"

결과는 또한 Grimmer를 밤에 잠 못 들게 만든 추가적인 이론적 미스터리를 제기합니다. 스텝 크기의 이상적인 패턴이 모두 대칭적인 모양을 갖는 이유는 무엇입니까? 가장 큰 단계는 항상 중앙에 있을 뿐만 아니라 동일한 패턴이 양쪽에 나타납니다. 계속 확대하고 시퀀스를 세분화하면 더 작은 단계로 둘러싸인 더 큰 단계의 "거의 프랙탈 패턴"을 얻을 수 있습니다. . 반복은 아직 아무도 설명하지 못한 최상의 솔루션을 관리하는 기본 구조를 제안합니다. 그러나 Grimmer는 적어도 희망적입니다.

"내가 그것을 깨뜨릴 수 없다면, 다른 누군가가 그것을 깨뜨릴 것"이라고 그는 말했다.