完全パラメータ不要な確率的最適化に向けて：自己上界づけ解析付きグリッドサーチ

概要: パラメータ不要の確率的最適化は、基礎となる問題パラメータに対して無頓着でありながら、最適に調整された手法と競合する収束率を達成するアルゴリズムの設計を目的とします。いくつかのパラメータ不要手法は、問題パラメータの具体的な値を要求しないものの、それでもそれらの下限または上限のような事前知識に依存しています。このような手法を「部分的パラメータ不要」と呼びます。本研究では「完全にパラメータ不要」な手法の実現を目指します。すなわち、アルゴリズムへの入力が、真の問題パラメータに関連する検証不可能な条件を満たす必要がありません。我々は、先行研究とは対照的に、パラメータの探索範囲を効果的に決定する新しい自己境界付け（self-bounding）解析手法を備えた、強力で一般的なグリッドサーチの枠組み extsc{Grasp} を提案します。我々の手法は、次の点で一般性を示します: (i) 非凸の場合において、対数因子までの範囲で、準最適な収束率を達成する完全にパラメータ不要な手法を提案すること; (ii) 凸の場合において、加速と普遍性の観点で優れた性能を示す、パラメータ不要手法が競争力を持つこと。最後に、補間された分散の特性評価に基づく、グリッドサーチ枠組みの最終ステップであるモデルアンサンブルに対する、より鋭い保証を提供します。