グローバル収束性を持つ「勾配正則化付きニュートン・ブースティング・ツリー」の提案

概要: 勾配ブースティング決定木（GBDT）は表形式の機械学習を支配しており、XGBoost、LightGBM、CatBoostのような現代的な実装はニュートンブースティングに基づいています。すなわち、決定木の空間における2次の降下ステップです。経験的な成功にもかかわらず、ニュートンブースティングの大域的収束は、1次のブースティングに比べてその理解が不十分です。本論文では、制限付きニュートン降下を導入します。これは、余弦角と弱い勾配エッジの概念に基づき、ヒルベルト空間上でのニュートン法による不正確な反復を伴う凸最適化を研究します。この枠組みにより、ニュートンブースティングをGBDTと有限次元の古典的理論の特殊な場合として復元します。まず、素のニュートンブースティングが、ヘッセ行列優勢条件を満たす滑らかで強い凸損失に対して、線形収束率を達成することを証明します。リプシッツ連続なヘッセ行列を持つ一般の凸損失を扱うために、我々は、制限付き弱学習器の設定へ、最近の勾配正則化ニュートン手法を拡張します。この手法は、各反復において勾配ノルムの2乗に比例し、その平方根に比例する適応的な 1_2-正則化項を導入することで、古典的アルゴリズムを最小限にしか変更しません。我々は、この手法に対して2\mathcal{O}(\frac{1}{k^2})の収束率を確立し、それにより、ネステロフの運動量を用いた1次のブースティングと同じ率を満たす、大域的に収束する2次GBDTアルゴリズムを得ます。数値実験では、提案手法が収束する一方で、素のニュートンブースティングは発散し得ることを示します。