ネステロフ加速スケッチングによるオンラインニュートン法の推論

arXiv stat.ML / 2026/4/28

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

この論文はストリーミングに基づく意思決定を目的にし、オンライン最適化における不確実性推定を改善します。既存の一次手法では共分散行列更新が必要で、O(d^2)の時間・メモリコストがかかる点が課題です。
Hessian averaging（ヘッセ平均化）を用いるオンラインニュートン法を提案し、各ステップのニュートン方向を、Nesterovの加速を伴うsketch-and-projectソルバで近似します。これにより、通常のニュートン方程式のボトルネックであるO(d^3)ではなく一次手法と同等のO(d^2)計算量を狙います。
著者らは、不確実性の要因を「ランダムなデータ」と「ランダム化された計算」の両方から分析し、全体的なほぼ確実収束を示すとともに、最後の反復に関する漸近正規性と、極限共分散をLyapunov方程式で特徴づけることを証明します。
さらに、非漸近的な収束保証を持つ完全オンラインの共分散推定器を開発し、得られる不確実性推定を、Nesterov加速なしのスケッチド・ニュートン法や厳密ニュートン法のものと関連付けます。
回帰モデルでの実験では、提案手法がオンライン推論においてベースラインより優れていることを示しています。

Abstract

ストリーミングデータによる信頼できる意思決定には、オンライン手法に対する、原理に基づく不確実性の定量化が必要である。一次手法は反復更新を効率的に可能にする一方で、その推論手続きでは適切な（共分散）行列の更新が依然として必要であり、

O(d^2)

の時間計算量およびメモリ計算量を要し、さらに問題の不良条件性やノイズの異質性に敏感である。この高コストな推論課題は、より頑健な二次手法のための機会を与えるが、二次手法はそれにもかかわらず、

O(d^3)

の計算量を伴うニュートン系の解法によってボトルネック化されている。本論文では、ヘッセ行列の平均化を行うオンライン・ニュートン法を研究することで、このギャップに取り組む。すなわち、各ステップにおけるニュートン方向を、Nesterov の加速を用いたスケッチ・アンド・プロジェクト型ソルバにより近似的に計算し、その計算量が一次手法と同じ

O(d^2)

になることを目指す。提案手法について、ランダムなデータとランダム化された計算の両方に起因する不確実性を定量化する。標準的な滑らかさおよびモーメント条件の下で、大域的なほぼ確実収束を確立し、リタレート（最後の反復）における漸近正規性を、Lyapunov 方程式によって特徴づけられる極限共分散を用いて証明し、さらに非漸近的な収束保証を備えた完全にオンラインな共分散推定器を開発する。加えて、その結果として得られる不確実性の定量化を、Nesterov の加速を用いない正確なニュートン法およびスケッチされたニュートン法の不確実性の定量化と結びつける。回帰モデルに関する大規模な実験により、提案手法がオンライン推論において優れていることを示す。