2点バンディットフィードバックを伴うオンライン凸最適化における最適な高確率レグレット

arXiv cs.LG / 2026/3/27

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、逆順（アドバーサリアル）な損失のもとでオンライン凸最適化（OCO）を研究し、学習者は2点のバンディットフィードバック（問い合わせた2点での関数値のみ）を受け取るとする。
著者らは、強凸損失に対するOCOのタイトな高確率レグレット境界を得るという、従来未解決だった問題に取り組む。これは、重い裾（heavy-tailed）のバンディット勾配推定器により困難とされていた。
著者らは、mu-強凸損失に対して、O(d(\log T + \log(1/\delta))/\mu)のオーダーの最初の高確率レグレット境界を証明する。
この境界は、時間範囲Tと次元dの両方に関してミニマックス最適であることが示され、先行研究が達成できていた理論保証を改善する。
全体として、本研究は、重い裾の推定器に起因する集中解析（concentration-analysis）の難しさを克服することで、バンディットフィードバックによる学習の理論的理解を前進させる。

要旨: 応力環境（adversarial environment）における2点バンディットフィードバックを伴うオンライン凸最適化（Online Convex Optimization, OCO）の問題を考えます。
この設定では、プレイヤーは敵対的に生成された一連の凸損失関数を最小化しようとしますが、各関数の値を2点で観測することしかできません。
2点フィードバックが勾配推定を可能にすることはよく知られていますが、強凸関数に対して高確率のタイトな後悔（regret）境界を達成することは、
\citet{agarwal2010optimal} で指摘されているとおり、依然として未解決でした。
主な課題は、バンディット勾配推定器の裾の重い（heavy-tailed）性質により、標準的な集中（concentration）解析が困難になることにあります。
本論文では、 $\mu$ -強凸損失に対して、 $O(d(\log T + \log(1/\delta))/\mu)$ の最初の高確率後悔境界を与えることで、この未解決課題を解決します。
本結果は、時間幅 $T$ と次元 $d$ の両方に関してミニマックス最適です。