オンライン最適化とRegret最小化 - DO++

大量のデータから、何か有益な情報を求める問題の多くは最適化問題を解くことに帰着されます． 最適化問題とは与えられた関数fの値を最小（最大）にするような変数xを探すといった問題です。 例えば、機械学習（これを利用する自然言語処理、情報検索など）、画像処理、AI(ロボットの経路制御）、 など多くの分野で最適化問題は登場します。 その中でもオンライン最適化（機械学習の文脈でいえばオンライン学習）と呼ばれる最適化手法は 実用性の高さと実装のしやすさから多く利用されるようになってきました。 このオンライン最適化は近年Regret（後悔）最小化というゲーム理論などで使われていた枠組みで 解析されることが多くなってきました。 今回はこのRegret最小化について簡単に解説してみようと思います。 （機械学習が詳しい人向けに補足すると、VC次元など他の機械学習を解析する手法と比べてRegret最適化の面白い