未知の滑らかさをもつノイズ関数のブラックボックス最適化

arXiv stat.ML / 2026/5/5

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、グローバル最適解の近傍での局所的な滑らかさが未知である場合に、ノイズを含む高次元の関数をブラックボックスで最適化する問題を扱います。
知識として滑らかさを事前に持たなくても機能する適応型アルゴリズムPOO（Parallel Optimistic Optimization）を提案します。
結果として、POOは滑らかさが既知であることを前提とした既存アルゴリズムに対して、性能がほぼ同等であることが示されます。
さらに有限時間解析により、n回のノイズ付き評価後の誤差が、滑らかさを知っている最良手法の誤差に対して最大でsqrt(ln n)倍で抑えられることが示されます。
本手法は従来よりも広いクラスの関数に適用可能で、とりわけ「最適化が難しい」と理論的に特徴づけられるケースにも対応すると主張しています。

要旨: 本論文では、ノイズによって摂動された関数評価が与えられるもとで、任意の次元の関数 f に対するブラックボックス最適化の問題を研究する。関数は、その全体最適解のうちの1つの近傍で局所的に滑らかであると仮定するが、その滑らかさは未知である。我々の貢献は、この設定に対処できる適応的最適化アルゴリズム POO、すなわち並列楽観的最適化である。POO は、滑らかさの知識を必要とする最良に知られたアルゴリズムとほぼ同等の性能を発揮する。さらに POO は、これまで考慮されていなかったより広いクラスの関数、特に非常に厳密な意味で最適化が難しい関数に対しても機能する。我々は、POO の性能に関する有限時間解析を与える。そこでは、評価回数 n の後の誤差が、滑らかさの知識を用いる最良に知られた最適化アルゴリズムの誤差から高々 √(ln n) 倍の範囲に収まることが示される。