インスタンス最適な確率的凸最適化：サンプル平均法およびロバスト確率近似を改善できるのか？

arXiv stat.ML / 2026/3/27

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、加法ノイズと乗法ノイズの両方を付加する確率オラクルのもとで、制約なしの確率的凸最適化を解析し、これをオペレーションズ・リサーチ、信号処理、機械学習にわたる代表的な問題として位置づける。
サンプル平均近似やロバスト／平均化確率近似といった一般的な手法が、有限サンプル性能において劣った、しかも場合によっては任意に悪い結果をもたらし得ることを示す。
著者らは、同じサンプルサイズを用いながら、これらのベースラインよりも大幅に優れた性能を達成する分散低減戦略VISORを導入する。
理論結果として、有限サンプルにおける情報理論的な局所ミニマックス下界、およびあらゆる推定器の性能を制限するもののインスタンス依存的な特徴付けが含まれる。
加速版VISORは、対数因子の範囲でインスタンス最適であることが示され、一般化線形モデル—とりわけ線形回帰—への応用により、確率的手法における、非漸近的でインスタンス依存の汎化誤差境界が改善される。

Abstract

本稿では、加法ノイズと乗法ノイズの両方を導入する確率的オラクルのもとで、滑らかで強く凸な母集団損失関数の制約なし最小化を研究する。これは、オペレーションズ・リサーチ、信号処理、機械学習にまたがって現れる、典型的で広く研究されている設定である。まず、標準的な手法である標本平均近似（sample average approximation）や、ロバスト（または平均化された）確率近似（stochastic approximation）は、現実的な有限標本サイズにおいて、劣った—場合によっては任意に劣悪な—性能につながり得ることを示す。これに対し、VISOR（短くそう呼ぶ）と名付けた、注意深く設計された分散低減戦略は、同じ標本サイズを用いながら、これらの手法を大きく上回ることを示す。上界は、有限標本・情報論的な局所ミニマックス下界によって補完されており、いかなる推定量の性能も決定する基本的で、実例依存の要因を明らかにする。以上を合わせると、VISORの加速版は実例に対して最適（instance-optimal）であり、対数因子までの最良の標本複雑性を達成するだけでなく、最適なオラクル複雑性も達成することが示される。さらに、本理論を一般化線形モデルへ適用し、古典的な結果を改善する。特に、線形回帰においてさえ、確率的手法に対する、最良として知られる非漸近的で実例依存の一般化誤差境界を得る。