전역 수렴성을 보장하는 그래디언트 정규화 뉴턴 부스팅 트리

그래디언트 부스팅 의사결정 트리 (GBDTs) 는 표본 기반 머신러닝에서 우세한 위치를 차지하며, XGBoost, LightGBM, CatBoost 와 같은 최신 구현들은 뉴턴 부스팅을 기반으로 합니다. 뉴턴 부스팅은 의사결정 트리의 공간에서 2 차 하강 단계입니다. 실증적 성공에도 불구하고, 1 차 부스팅에 비해 뉴턴 부스팅의 전역 수렴성은 잘 이해되지 않았습니다. 본 논문에서는 Hilbert 공간에서 불완전한 반복을 가진 뉴턴 방법을 기반으로 코사인 각도와 약한 그래디언트 에지 개념을 도입하여 제한된 뉴턴 하강 (Restricted Newton Descent) 을 소개합니다. 이 프레임워크 내에서 GBDT 와 고전적 유한 차원 이론을 포함한 뉴턴 부스팅을 특수한 경우로 복원합니다. 먼저, Hessian 우도 조건을 만족하는 매끄럽고 강하게 볼록한 손실에 대해 원본 뉴턴 부스팅이 선형 수렴 속도를 달성함을 증명합니다. Lipschitzian Hessian 을 가진 일반적인 볼록 손실을 처리하기 위해 최근 그래디언트 정규화 뉴턴 스키마를 제한된 약 학습자 설정으로 확장했습니다. 이 스키마는 각 반복에서 그래디언트 노름의 제곱근에 비례하는 적응형 ℓ2-정규화 항을 도입하여 고전 알고리즘을 최소한으로 수정합니다. 우리는 이 스키마에 대해 O(1/k^2) 속도를 확립함으로써, Nesterov 모멘텀을 가진 1 차 부스팅과 일치하는 속도를 가지는 전역 수렴 2 차 GBDT 알고리즘을 얻었습니다. 수치 실험에서, 원본 뉴턴 부스팅이 발산할 수 있음에도 불구하고 우리의 스키마가 수렴함을 보여줍니다.