オンデマンドサンプリングにおけるサンプル適応性のトレードオフ

本研究では、オンデマンドサンプリングにおけるサンプルの複雑性とラウンドの複雑性のトレードオフを考察します。この場合、学習アルゴリズムは限られたラウンド数で複数の分布から適応的にサンプリングします。特に、実現可能な設定において、最適なサンプルの複雑性は、ラウンド数が増加するにつれて特定のスケールで変動することを示しました。また、一般的な不確実性のあるケースに対しても、ほぼ最適なサンプルの複雑性を持つアルゴリズムを提示し、これを新しいフレームワークである「オンデマンドサンプリングによる最適化（OODS）」を通じて解析しています。このフレームワークは、既存のMDLアルゴリズムの多くを抽象化し、ラウンドの複雑性に対する厳密な制約を確立します。研究の結果、サンプルの適応性に関する新たなインサイトと、今後の研究に向けた重要な知見が得られることが期待されます。