AdaBoost は常に循環するわけではない：計算機支援による反例
arXiv cs.LG / 2026/4/9
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、Rudin、Schapire、Daubechies による COLT 2012 の公開問題に対し、「網羅的（exhaustive）AdaBoost が最終的に有限の周期へ収束するかどうか」を扱ったコンピュータ支援の反例を提示する。
- 構成では、ブロック積（block-product）の「ガジェット」を用いる。ここでは 2 つの構成要素が、それぞれの 5 ステップの分岐写像（branch map）において同一の周期 2 の軌道を共有する一方、線形化したリターン写像（linearized return map）には、固有値の対数が互いに無理数比となるような支配的固有値が存在する。
- 固有値対数の無理数比は、その結果として得られる「バースト・ウィナー（burst-winner）系列」の漸近的な出現頻度が無理数になることを意味し、最終的な周期性を否定する。
- 著者らは、すべての主張が正確な有理演算によって証明（certified）されていると述べており、発表では GPT-5.4 Pro および Claude Opus 4.6 との共同で本研究が開発されたことが言及されている。
