[1S3-GS-2] 機械学習：

[1S3-GS-2-02] 確率的に拡張された敵対的環境におけるオンライン劣モジュラ最小化

〇原田 翼¹、竹村 慧²、松岡 達也² (1. 東京科学大学、2. 日本電気株式会社)

キーワード：オンライン学習、リグレット解析、劣モジュラ最小化

オンライン劣モジュラ最小化は，逐次的意思決定問題の一種である．具体的には，各ラウンドで既知の有限集合から部分集合を1つ選択し，劣モジュラ性を満たす損失関数を受け取ることを繰り返しながら，累積損失の最小化を目指すものである．オンライン最適化における確率的に拡張された敵対的（Stochastically Extended Adversarial: SEA）環境では，各ラウンドの開始時に損失関数の確率分布が敵対的に決定され，その分布に従って損失関数が1つサンプルされる．この環境は，確率的環境と敵対的環境の両方を内包し，それらの中間的な環境も表現可能である．本論文では，当初オンライン凸最適化の文脈で提案されたSEA環境をオンライン劣モジュラ最小化に適用し，その設定に応じた新たなアルゴリズムを提案する．このアルゴリズムは，SEA環境におけるオンライン凸最適化の既存のリグレット上界に対応するリグレット上界を保証するとともに，確率的環境におけるオンライン劣モジュラ最小化に特有のリグレット上界も同時に保証する．